Noname manusc ip No.
(will be inse ed by he edi o )
BFCA+: Au oma ic syn hesis o pa allel code wi h TLS
capabili ies
Se gio Aldea, Diego R. Llanos, A u o
Gonzalez-Esc ibano
he da e o eceip and accep ance should be inse ed la e
Abs ac Pa alleliza ion o sequen ial applica ions equi es ex ac ing in o -
ma ion abou he loops and how hei a iables a e accessed, and a e wa ds,
augmen ing he sou ce code wi h ex a code depending on such in o ma ion.
In his pape we p opose a amewo k ha a oids such an e o -p one, ime-
consuming ask. Ou solu ion le e ages he compile- ime in o ma ion ex ac ed
om he sou ce code o classi y all a iables used inside each loop acco ding
o hei accesses. Then, ou sys em, called BFCA+, au oma ically ins umen s
he sou ce code wi h he necessa y OpenMP di ec i es and clauses o allow
i s pa allel execu ion, using he s anda d sha ed and p i a e clauses o a i-
able classi ica ion. The amewo k is also capable o ins umen ing loops o
specula i e pa alleliza ion, wi h he help o he ATLaS un ime sys em, ha
de ines a new specula i e clause o poin ou hose a iables ha may lead o
a dependency iola ion. As a esul , he a ge loop is gua an eed o co ec ly
un in pa allel, ensu ing ha i s execu ion ollows sequen ial seman ics e en
in he p esence o dependency iola ions. Ou expe imen al e alua ion shows
ha he amewo k no only sa es de elopmen ime, bu also leads o a as e
code han he one manually pa allelized.
Keywo ds: Au oma ic pa alleliza ion, compile amewo k, OpenMP, sou ce
syn hesis, sou ce ans o ma ion, specula i e pa alleliza ion, XML.
1 In oduc ion
One o he main conce ns o cu en compu e science is he s udy o pa allel
capabili ies o bo h p og ams and p ocesso s ha execu e hem. Due o he
huge numbe o sequen ial p og ams al eady w i en o many decades un il
now, complexi y o pa allel p og amming languages, and knowledge equi ed
o pa allelize sou ce code, a echnique ha au oma ically pa allelizes hem is
ETS Ingenie a In o m ica, Uni e sidad de Valladolid, Paseo Beln 15, 47011 Valladolid, Spain
Tel.: +34-983185642, ax: +34-983423671. E-mail: {se gio,a u o,diego}@in o .u a.es.
2 Se gio Aldea, Diego R. Llanos, A u o Gonzalez-Esc ibano
qui e desi able. Howe e , au oma ic pa alleliza ion echniques cu en ly im-
plemen ed in many comme cial compile s a e no able o pa allelize mos o
he loops because o he possibili y o da a dependencies [3].
Th ead-Le el Specula ion (TLS) [6,8] is a un ime echnique ha can be
used o un loops in pa allel ha may p esen dependency iola ions. TLS
op imis ically assumes ha he code can be execu ed in pa allel, elying on a
un ime moni o o ensu e co ec ness. I a dependency iola ion appea s a
un ime, hese lib a y unc ions s op he o ending h eads and es a hem
in o de o use he upda ed alues, hus p ese ing sequen ial seman ics.
Un il now, specula i e echniques we e expe imen al, equi ing he manual
in e en ion o expe p og amme s. These p og amme s i s ly needed o ex-
ac ce ain in o ma ion abou he sou ce code ha hey aim o pa allelize,
such as a iable usages wi hin each loop, o I/O unc ions ha complica e, o
e en p eclude, he pa alleliza ion. The second s ep was o manually add all
he unc ions and s uc u es needed o handle he specula i e execu ion.
Ou esea ch g oup ha e been wo king se e al yea s in he p oblem o
au oma ic syn hesis o pa allel code wi h TLS capabili ies. Ou p io wo k
included he de elopmen o bo h an analysis amewo k, called BFCA, and a
TLS un ime sys em, called ATLaS.
–BFCA [2,4] is an analysis amewo k ha ex ac s p o iling and depen-
dency in o ma ion o o loops in C code, in o de o de ec which o
loops a e he bes candida es o pa alleliza ion.
–ATLaS is a Th ead-Le el Specula ion (TLS) compile [19] and un ime
sys em [1] ha ex ends OpenMP unc ionali ies wi h a new specula i e
clause, o allow he pa alleliza ion o o loops ha a e no gua an eed a
compile ime o be dependency- ee1. Du ing pa allel execu ion, a iables
ha we e labeled as specula i e a e moni o ed a un ime. I a dependency
iola ion occu , he h ead ha has consumed an inco ec alue is s opped
and es a ed, ensu ing sequen ial seman ics.
The use o bo h amewo ks g ea ly simpli ied he de elopmen o pa al-
lel code, bu he in e en ion o an expe p og amme was s ill needed o
ans o m he sequen ial code in o a pa allel e sion.
The amewo k p esen ed in his pape closes he loop, allowing o he i s
ime he au oma ic syn hesis o pa allel code wi h TLS capabili ies. BFCA+
elies on he da a e u ned by BFCA o au oma ically add he OpenMP di ec-
i es needed o un a chosen loop in pa allel, ei he using he classic OpenMP
di ec i es i he loop does no p esen dependencies among i e a ions, o us-
ing he new OpenMP specula i e clause p o ided by ATLaS i he lack o
dependencies canno be gua an eed a compile ime.
Despi e i s in e nal complexi y, BFCA+usage is simple. A i s un ob ains
p o ile in o ma ion o all loops in he applica ion, oge he wi h a classi ica ion
o a iables usage in all o hem. A e examining hese esul s, he use should
1Only well- o med o loops whe e he numbe o i e a ions a e known a he beginning
o he loop can be pa allelized by he ATLaS amewo k. See [1] o addi ional de ails.
BFCA+: Au oma ic syn hesis o pa allel code wi h TLS capabili ies 3
choose a loop o pa allel execu ion. A second un o BFCA+wi h he line
numbe o he chosen loop gene a es an OpenMP-based pa allel e sion o
he loop, using he sha ed,p i a e, and he non-s anda d specula i e clauses
o classi y loop a iables acco ding o hei usage. Thanks o his solu ion,
any a ge loop is gua an eed o co ec ly un in pa allel while p ese ing i s
sequen ial seman ics.
Rega ding pa allel pe o mance, ou expe imen al esul s, ob ained by he
execu ion o ou di e en benchma ks ha p esen dependency iola ions a
un ime, show bo h a no iceable speedup (up o 13.5×speedup wi h 56 co es in
he p esence o dependency iola ions) and good scalabili y. In e es ingly, he
au oma ic ans o ma ion o he sequen ial code leads o be e pe o mance
han hose ob ained when he use manually ans o ms he code o he same
pu pose using ATLaS un ime unc ions di ec ly.
2 Rela ed wo k
The gene a ion o sou ce code is a p oblem ha conce ns di e en a eas, such
as e ac o ing, op imiza ion, and pa alleliza ion o sou ce codes. In he case o
BFCA+, he e a e many di e en p oposals o he au oma ic pa alleliza ion
o sou ce codes, and mo e pa icula ly, ocused on he syn hesis o OpenMP
cons uc s.
One o he i s a emp s o au oma ize he gene a ion o OpenMP con-
s uc s is he POST p ojec [15], ha p o ides a simple en i onmen ha also
allows he in e en ion o he use . A mo e ad anced sys em is Pa aWise/-
CAPO [12,13,20], which uses a dependency analysis o c ea e he app op ia e
OpenMP di ec i es o pa allelize simple and nes ed loops in Fo an applica-
ions. I also applies a ce ain le el o op imiza ion ans o ma ions o enhance
he quali y o he gene a ed code. This is also he case o PLuTo [21], a sou ce-
o-sou ce amewo k ha uses he polyhed al model o op imize he code and
gene a e OpenMP pa allel code au oma ically.
G aphi e [14] is a b anch o GCC ha applies he polyhed al model o
di e en pu poses, including he gene a ion o pa allel code, and p oposes an
au o-pa alleliza ion op ion o GCC ha uses OpenMP s uc u es o de ine
pa allel sec ions. This wo k inspi ed Polly [22], a simila p oposal bu ocused
on a di e en compile : LLVM [24]. O he wo ks ha also use he polyhed al
model such as Pa 4All [18]and PYPS [23] a e based on PIPS [17], a sou ce- o-
sou ce amewo k. Pa 4All uses he analysis pe o med by PIPS o op imize
and c ea e OpenMP (among o he s anda ds) sou ce codes. PYPS is a Py hon-
based p og ammable pass manage , ha also gene a es OpenMP cons uc s.
Unlike mos o he app oaches, which a e sou ce- o-sou ce pa allelize s ha
au oma ically gene a e OpenMP di ec i es and clauses (e.g. Liao e al. [11],
Ce us [10], o se e al o he p oposals seen abo e), Gaspa d2 [25] ollows a
model- o-sou ce app oach. Gaspa d2 is a g aphical amewo k ha needs ha
he code and he a ailable pa allelism be exp essed by he use wi h an UML-
based model, which is hen ans o med in o an OpenMP model ha gene -
4 Se gio Aldea, Diego R. Llanos, A u o Gonzalez-Esc ibano
a es he pa allel e sion o he sou ce code. Finally, YAO [16] is a g aph-based
amewo k, ocused on he da a assimila ion mos ly o geophysical applica-
ions, able o gene a e no only OpenMP cons uc s o pa allelize code egions,
bu also a omic di ec i es o a oid ace condi ions.
As we will see, like mos o he app oaches desc ibed abo e, BFCA+ ol-
lows a sou ce- o-sou ce app oach, le e aging i s XML-based ep esen a ion
o he sou ce code o analyze and augmen he code wi h OpenMP pa al-
lel cons uc s, including ou specula i e clause [19]. This di e s om o he
app oaches: BFCA+is able o syn hesize he code needed o handle he spec-
ula i e execu ion o a ce ain p og am, c ea ing an OpenMP-based pa allel
e sion om he sequen ial sou ce code.
3 BFCA+a chi ec u e and usage
As we s a ed in Sec . 1, ou p oposal has been buil upon wo di e en solu-
ions ha , un il now, wo ked independen ly o each o he . The i s solu ion is
BFCA [4], an XML-based amewo k ha combines s a ic analysis o sou ce
code wi h p o iling in o ma ion o gene a e comple e epo s ega ding all
loops in a C applica ion, including loop co e age, loop sui abili y o pa al-
leliza ion, a axonomy o hei a iables based on hei accesses, as well as
o he hu dles ha es ic he pa alleliza ion. BFCA a chi ec u e is depic ed
inside a dashed-line box in Fig. 1. BFCA+ex ends his amewo k o enable
he syn hesis o sou ce code augmen ed wi h OpenMP di ec i es and clauses,
in ended no only o au oma ically classi y a iables acco ding o hei usage
(sha ed o p i a e), bu also o inse app op ia e OpenMP di ec i es o enable
he au oma ic pa alleliza ion o he a ge loop (see he solid box in Fig. 1).
In ce ain si ua ions, howe e , he pa allel execu ion o a gi en loop may
ail due o he possibili y o un ime dependencies among i e a ions. This is
whe e specula i e pa alleliza ion comes in o scene. When BFCA+de ec s such
a si ua ion, i is also able o label as specula i e all a iables whose de ini ion o
use may po en ially lead o a dependency iola ion. Unlike sha ed and p i a e
clauses, he specula i e clause is no pa o he OpenMP s anda d, bu a new
clause i s p oposed by ou g oup [2]. This p oposal was la e implemen ed in
he ATLaS amewo k, he second solu ion BFCA+is buil upon.
Wi h espec o he ATLaS compile and un ime amewo k [1], i is com-
posed by wo main elemen s. The i s one is he compile suppo , hanks
o a specialized GCC compile plugin ha de ec s he use o he specula i e
clause, and augmen s he sou ce code wi h so wa e ha con ols he spec-
ula i e execu ion o he loop. The second one is he un ime suppo , wi h
unc ions ha moni o s a un ime he exis ence o dependency iola ions,
and pe o ms co ec i e ac ions i such a iola ion akes place.
These wo building blocks, BFCA and ATLaS, a e used oge he in BFCA+
o gi e a comple e solu ion o he au oma ic syn hesis o pa allel e sions o
o loops. The use should i s un he amewo k o see which loops can
be pa allelized, choose one, and le he au oma ic ans o ma ion sys em o
BFCA+: Au oma ic syn hesis o pa allel code wi h TLS capabili ies 5
Inpu se P ofiling
In o ma ion
Sequen ial
C sou ce
code
Loop co e age
and a iables
cha ac e iza ion
XMLCe us
In el
Compile
Bina y
code
XML sou ce code
ep esen a ion
P ofilaze
XML sou ce code
wi h p ofiling da a
BonaFide C Analyze and T as o me (BFCA+)
(Builds XML ee)
(Me ges XML in o ma ion)
Si ius
(Rebuilds C sou ce)
GCC 4.6.2
+
plugin
Run ime pa ame e s, including:
- Th eads
- Block size
- Max. numbe o i e a ions
- Max. numbe o specula i e elemen s
TLS un ime lib a y
Pa allel
bina y
execu able
The ATLaS amewo k
Linke
XML sou ce code
wi h OpenMP
di ec i es
(Queues XML ee)
Loopes
OMPlize
(Augmen s XML ee)
BFCA line numbe o
he loop o be
pa allelized
(p og amme 's
decision)
C sou ce code anno a ed
wi h OpenMP di ec i es
(possibly including new specula i e clause)
Fig. 1 O e iew o he BFCA+plus ATLaS a chi ec u e, ha analyzes he code, gene a es
an OpenMP-based specula i ely-pa allel e sion o he code, and inally compiles i o c ea e
an execu able ha uns in pa allel specula i ely.
BFCA+
./b ca+ -c <file>.c
C sou ce
code
XML
file BFCA+
./b ca+ -x <file>.xml
-p <loop_line>
Loop epo + a iable classifica ion
Specula i ely
pa allelized
C sou ce code
Fig. 2 O e iew o he p ocess ha ans o ms a sequen ial C code in o a pa allel one.
BFCA+au oma ically gene a es he OpenMP cons uc s, including he specula i e clause.
gene a e an execu able ha is gua an eed o un co ec ly in pa allel. Wi hou
BFCA+, p og amme s needed o manually classi y a iables o he loop ha
hey aim o pa allelize, and hen, inse all he OpenMP cons uc s equi ed by
ATLaS o pa allelize i specula i ely. BFCA+also sol es his p oblem, eeing
p og amme s om his e o -p one, edious ask.
Figu e 1 shows he a chi ec u e o BFCA+, and how i gene a es an OpenMP-
based sou ce code ha is compilable by ATLaS o gene a e a specula i ely
pa allel e sion o he code. As can be seen in he igu e, BFCA+ elies hea ily
on BFCA, composed in u n by h ee main subsys ems: (1) XMLCe us, a mod-
i ied e sion o Ce us [10] ha builds an XML ee ep esen ing he o iginal C
sou ce code; (2) P o ilaze , ha execu es he code and augmen s he XML ee
wi h p o iling in o ma ion; and (3) Loopes , ha exploi s XML capabili ies o

6 Se gio Aldea, Diego R. Llanos, A u o Gonzalez-Esc ibano
1#de ine NITER 1000000, MAX 100
2in a ay[MAX];
3...
4
5 o (P=0;P<NITER;P++)
6Q = P % (MAX) + 1;
7aux = a ay[Q −1];
8Q = (4 ∗aux) % (MAX) + 1;
9a ay[Q −1] = aux;
10 }
Fig. 3 File p og am.c: F agmen o C code ha depic s a loop whe e he use o a da a
s uc u e (a ay) may lead o a dependency iola ion.
cha ac e ize e e y loop in he sou ce code, and pe o ms a axonomy o he
a iables based on how hey a e accessed. BFCA+adds o his solu ion a new
module, called OMPlize , ha syn hesizes OpenMP-based cons uc s o spec-
ula i ely pa allelize he code. Finally, a i h module, called Si ius, ans o ms
he XML ep esen a ion back o C.
Figu e 2 summa izes he p ocess ha ans o ms a sequen ial sou ce code
in o a pa allel one. In a i s execu ion, BFCA+ epo s abou each loop and
how i s a iables a e accessed. Then, he p og amme only needs o poin ou
he line numbe o he loop o be pa allelized. In a second execu ion, BFCA+
uses he in o ma ion on he a iable accesses o au oma ically augmen he
XML ep esen a ion o he code by using OMPlize . OMPlize modi ies he
XML node ha ep esen s he FOR loop, and inse s a new XML node wi h
he OpenMP pa allel di ec i e and he co esponding clauses, acco ding o he
a iable classi ica ion ha Loopes c ea es. This includes he inse ion o he
specula i e clause wi h hose a iables ha may lead o a dependency iola-
ion. Once OMPlize has augmen ed he XML ep esen a ion o he sou ce
code, Si ius ans o ms i back in o a C ep esen a ion. Du ing his p ocess,
he o iginal sequen ial code has been anno a ed wi h OpenMP cons uc s ha
pa allelize i . Finally, ATLaS p ocesses hese OpenMP anno a ions, and pe -
o ms all he changes needed in he loop o be un in pa allel using ou TLS
un ime lib a y, including he eplacemen o he accesses o e specula i e
a iables wi h he co esponding specula i e e sions o hese accesses. I is
impo an o ema k ha , i he FOR loop being pa allelized does no con ain
specula i e a iables, BFCA+gene a es he OpenMP cons uc s in o de o
be pa allelized acco ding o he OpenMP s anda d.
Despi e he complexi y o he ans o ma ion p ocess, he usage o he
BFCA+ amewo k is simple. As an example, conside he sequen ial code de-
pic ed in Fig. 3. A i s in oca ion o BFCA+(shown in Fig. 4) analyzes he
sequen ial code s a ically and dynamically, p oducing bo h a epo wi h he
cha ac e iza ion o he loop, and an XML ile ha me ges his s a ic cha ac-
e iza ion wi h he p o iling in o ma ion o he loop co e age (Fig. 5).
A second un o BFCA+, also shown in Fig. 4, allows he p og amme
o indica e he s a ing line o he loop ha should be pa allelized. This
second in oca ion gene a es an augmen ed e sion o he XML ile, called
BFCA+: Au oma ic syn hesis o pa allel code wi h TLS capabili ies 7
$ b ca+ −c p og am.c
...
p og am.c:5: Line numbe : 5
p og am.c:5: Numbe o lines: 5
p og am.c:5: Inclusi e Time Pe cen : 34.2
p og am.c:5: Exclusi e Time Pe cen : 34.2
p og am.c:5: I doesn’ con ain poin e a i hme ic.
p og am.c:5: Numbe o Loop Con ol Va iables: 1
p og am.c:5: Loop Con ol Va iable: (in ) P.
p og am.c:5: Va iables ead and w i en: (in ) Q,
(in ) aux, (in ) a ay[100].
p og am.c:5: Va iables only ead: (in ) P.
p og am.c:5: P i a e Va iables: (in ) Q, (in ) aux,
(in ) P.
p og am.c:5: Specula i e Va iables: (in ) a ay[100].
p og am.c:5: I is a well- o med FOR Loop.
...
$ ls
p og am.c p og am.xml
$ b ca+ −x p og am.xml −p 5
$ ls
p og am.c p og am.spec.c
p og am.xml p og am.spec.xml
$ ./a las − h eads 4 −block 100 −c p og am.spec.c −e p og am
$ ls
p og am.c p og am.spec.c p og am
p og am.xml p og am.spec.xml
Fig. 4 Usage o BFCA+in he pa alleliza ion o he loop in line 5 o he p og am.c ile
depic ed in Fig. 3. The in oca ion o he ATLaS compile amewo k is also shown.
p og am.spec.xml, ha includes he di ec i es needed o pa allelize he loop
(Fig. 6). In addi ion, his second in oca ion ans o m he augmen ed XML
ep esen a ion back o C. The esul , shown in Fig. 7, is a C ile con ain-
ing a pa allel, specula i e e sion o a loop ha can no be pa allelized by
pa allelizing compile s due o he possibili y o dependency iola ions.
Finally, ATLaS is esponsible o ans o m he pa allel e sion o he code
ha con ains he non-s anda d specula i e clause in o s anda d OpenMP di-
ec i es plus addi ional code. The in e media e esul (be o e being e ec i ely
compiled) is shown in Fig. 8.
4 E alua ion
In o de o e alua e he capabili ies o BFCA+, we ha e used i o gene a e
he OpenMP cons uc s (including ou p oposed specula i e clause) o some
syn he ic and eal-wo ld benchma ks. The expe imen s ha e been designed o
e i y ha he use o BFCA+leads o execu able iles ha a e unc ionally
equi alen o hose manually pa allelized by an expe ienced p og amme .
All he benchma ks used in he expe imen s a e no pa allelizable a com-
pile ime due o se e al da a dependencies, equi ing un ime specula i e pa -
alleliza ion. We ha e used se e al eal-wo ld applica ions whose main loops
a e no pa allelizable a compile ime because o he possibili y o depen-
dence iola ions, and he e o e equi e TLS o un in pa allel. They a e he
8 Se gio Aldea, Diego R. Llanos, A u o Gonzalez-Esc ibano
1<Fo Loop condi ion="P<1000000" ini ial="P=0;" leng h="7" lineNumbe ="6"
2s ep="P ++" en yCoun ="1" absTime="3161466" absTimePe cen ="41.6"
3sel Time="3161466" sel TimePe cen ="41.6">
4<S a emen lineNumbe ="−1">
5<Exp essionS a emen lineNumbe ="−1">
6<Exp ession>
7<Bina yExp ession lhs="P" ope a o ="=" hs="0">
8<Assignmen Exp ession>
9<Exp ession>
10 <IDExp ession>
11 <Iden i ie a ay="" name="P" opUna y="" ype="in "/>
12 </IDExp ession>
13 </Exp ession>
14 <Exp ession>
15 <Li e al>
16 <In ege Li e al alue="0"/>
17 </Li e al>
18 </Exp ession>
19 </Assignmen Exp ession>
20 </Bina yExp ession>
21 </Exp ession>
22 </Exp essionS a emen >
23 </S a emen >
24 <Exp ession>
25 <Bina yExp ession lhs="P" ope a o ="<" hs="1000000">
26 <Exp ession>
27 ...
Fig. 5 File p og am.xml: F agmen o he XML ep esen a ion c ea ed by BFCA o he
loop in line 5 o Fig. 4 be o e being pa allelized.
1<Fo Loop anno a ion="OpenMP" condi ion="P<1000000" ini ial="P=0;" leng h
="5"
2lineNumbe ="6" s ep="P ++" en yCoun ="1"
3absTime="3161466" absTimePe cen ="41.6" sel Time="3161466"
sel TimePe cen ="41.6">
4
5<Anno a ion anno a ion="#p agma omp pa allel o de aul (none)
6schedule(s a ic) specula i e(a ay)
7p i a e(Q, aux, P)"/>
8
9<S a emen lineNumbe ="−1">
10 <Exp essionS a emen lineNumbe ="−1">
11 <Exp ession>
12 ...
Fig. 6 File p og am.spec.xml: XML ep esen a ion o Fig. 5 augmen ed by OMPlize (high-
ligh ed code).
2-dimensional Con ex Hull p oblem (2D-Hull) [7], he Delaunay T iangula ion
using he Jump-and-Walk s a egy [9], he 2-dimensional Minimun Enclosing
Ci cle (2D-MEC) p oblem [26], and a C implemen a ion o TREE [5]. The
loops conside ed in he i s h ee applica ions a e he main loop o he codes,
ha consumes almos 100% o he execu ion ime. Fo TREE, we ha e pa -
allelized he ACCEL loop, ha consumes 95.17% o he o al execu ion ime.
2D-Hull and 2D-MEC a e execu ed wi h a en-million-poin da ase , Delaunay
wi h a one-million-poin da ase , and TREE wi h a da ase o 4096 nodes.
BFCA+: Au oma ic syn hesis o pa allel code wi h TLS capabili ies 9
1#de ine NITER 1000000, MAX 100
2in a ay[MAX];
3...
4#p agma omp pa allel de aul (none)
5p i a e(P, Q, aux) specula i e(a ay)
6 o (P=0;P<NITER;P++)
7Q = P % (MAX) + 1;
8aux = a ay[Q −1];
9Q = (4 ∗aux) % (MAX) + 1;
10 a ay[Q −1] = aux;
11 }
Fig. 7 File p og am.spec.c: C ep esen a ion o p og am.spec.xml as e u ned by he
Si ius module o BFCA+.
1#de ine NITER 1000000, MAX 100
2in a ay[MAX];
3...
4specbegin(NITER)
5#p agma omp pa allel de aul (none)
6p i a e(P, Q, aux, ini, cu en , id, e lag, alue)
7sha ed(a ay, wheel_ns, wheel_ms, wheel, uppe _limi , a block)
8{
9#p agma omp o schedule(s a ic) nowai
10 o ( id = 0; id <= 3; id = id + 1) {
11 ini = 0;
12 cu en = id;
13 P = a block[0][cu en ]+ini;
14 i (i > uppe _limi - 1)
15 go o labelSquash_1;
16 a block[2][cu en ] = a block[2][cu en ]+1;
17 labelS a I e a ion_1:
18 Q = P % (MAX) + 1;
19 //aux = a ay[Q −1];
20 i (specload_poin e ((unsigned cha *) &(a ay[Q-1]),
21 sizeo (a ay[Q-1]), cu en , (unsigned cha *) & alue) == -1)
22 ea lySquash(1);
23 aux= alue;
24 Q = (4 ∗aux) % (MAX) + 1;
25 //a ay[Q −1] = aux;
26 specs o e_poin e ((unsigned cha *) &(a ay[Q-1]),
27 sizeo (a ay[Q-1]),cu en ,(unsigned cha *) & alue);
28 labelEndI e a ion_1:
29 i ((P != a block[1][cu en ] + ini) && (i < NITER - 1)) {
30 P=P+1;
31 go o labelS a I e a ion_1;
32 }
33 labelSquash_1:
34 e lag = h eadend_poin e (¤ );
35 i ( e lag == JOBDONE) go o labelEndLoop_1;
36 i ( e lag == JOBTODO) {
37 i = a block[0][cu en ] + ini;
38 a block[2][cu en ] = a block[2][cu en ] + 1;
39 go o labelS a I e a ion_1;
40 }
41 labelEndLoop_1:
42 ;
43 }// o loop
44 }// p agma omp pa allel
Fig. 8 Code gene a ed by ATLaS a e p ocessing he sou ce code o he syn he ic bench-
ma k augmen ed by BFCA+(shown in Fig. 7).