One Tie Da a low P og amming Model o
Hyb id Dis ibu ed- and Sha ed-Memo y Sys ems
Ja ie F esno A u o Gonzalez-Esc ibano Diego R. Llanos
Uni e sidad de Valladolid
{j esno,a u o,diego}@in o .u a.es
Abs ac
Da a low p og amming consis s in de eloping a p og am by de-
sc ibing i s sequen ial s ages and he in e ac ions be ween hem.
The un imes suppo ing his kind o p og amming a e esponsible
o exploi ing he pa allelism by concu en ly execu ing he di e en
s ages when hei dependencies ha e been me .
In his pape we in oduce a new pa allel p og amming model
and amewo k based on he da a low pa adigm. I s ea u es a e:
I is a unique one- ie model ha suppo s hyb id sha ed- and
dis ibu ed-memo y sys ems; i can exp ess ac i i ies a bi a ily
linked, including cycles; i uses a dis ibu ed wo k-s ealing mech-
anism o allow Mul iple-P oduce /Mul iple-Consume con igu a-
ions; and i has a un- ime mechanism o he econ igu a ion o
he dependences ne wo k which also allows o c ea e ask- o- ask
a ini ies.
We p esen an e alua ion using examples o di e en classes o
applica ions. Expe imen al esul s show ha p og ams gene a ed
using his amewo k deli e good pe o mance, and ha he new
abs ac ions in oduce minimal o e heads.
Ca ego ies and Subjec Desc ip o s D.3.2 [P og amming Lan-
guages]: Language Classi ica ions—Da a- low languages
Keywo ds Da a low p og amming, Dis ibu ed sys ems, Dynamic
compu a ion, Pa allel p og amming models, S eaming compu a-
ion
1. In oduc ion
The mos common p og amming ools o pa allel machines a e
based on message passing lib a ies, such as MPI [14], o sha ed
memo y APIs like OpenMP [6]. These ools allow he p og amme s
o exploi he capabili ies o he machines by explici ly de ine he
pa allel sec ions inse ed in he sequen ial code and p og am in e -
p ocess synch oniza ions and communica ions.
On he o he hand, s eam and da a low lib a ies and languages
(such as Fas Flow [4], CnC [5], OpenS eam [17], o S-Ne [13])
educe he complexi y o c ea ing a pa allel p og am because he
p og amme only has o de ine he sequen ial s ages and i s de-
pendencies. I is he un ime esposabili y o con ol he sequen ial
Pe mission o make digi al o ha d copies o all o pa o his wo k o pe sonal o
class oom use is g an ed wi hou ee p o ided ha copies a e no made o dis ibu ed
o p o i o comme cial ad an age and ha copies bea his no ice and he ull ci a ion
on he i s page. Copy igh s o componen s o his wo k owned by o he s han ACM
mus be hono ed. Abs ac ing wi h c edi is pe mi ed. To copy o he wise, o epublish,
o pos on se e s o o edis ibu e o lis s, equi es p io speci ic pe mission and/o a
ee. Reques pe missions om [email p o ec ed].
HLPGPU 2016, Janua y 19, 2016, P ague, Czech Republic.
Copy igh © 2016 ACM 978-1-nnnn-nnnn-n/yy/mm. . . $15.00.
h p://dx.doi.o g/10.1145/nnnnnnn.nnnnnnn
s ages execu ion and pe o m he da a synch oniza ions o exploi
pa allelism.
Howe e , hese models lack ei he : A unique ep esen a ion o
sha ed- and dis ibu ed-memo y a chi ec u es; dependences s uc-
u es in ol ing eedback loops, ee o concu ency p oblems; a
gene ic sys em o ep esen MPMC (Mul iple-P oduce /Mul iple-
Consume ) con igu a ions; mechanisms o econ igu e depen-
dences a un- ime; o hey do no ha e ways o in ui i ely exp ess
ask- o- ask a ini ies which would allow a be e exploi a ion o
da a-locali y ac oss s a e-d i en ac i i ies.
In his pape , we p opose Hi Flow, a new da a low pa allel p o-
g amming model ha ex ends a p e ious p oposal [10]. I uses
a single ep esen a ion o bo h sha ed- and dis ibu ed-memo y
models. I in oduces a gene ic o m o desc ibing a p og am
as a econ igu able ne wo k o ac i i ies and yped da a con-
aine s a bi a ily in e connec ed. I p esen s an abs ac ion o
an MPMC channel sys em ha includes a wo k-s ealing, load-
balancing mechanism. Ou solu ion also allows ask- o- ask a ini y
o be se o exploi da a locali y.
We p esen an e alua ion o ou p oposal using examples o
h ee di e en applica ion classes. We desc ibe how hey a e ep-
esen ed in ou model, showing how o exp ess di e en ypes o
pa allel pa adigms, and s a ic and dynamic synch oniza ion s uc-
u es. Mo eo e , expe imen al wo k has been ca ied ou o p o e
ha he p og ams gene a ed using ou amewo k achie e good pe -
o mance in compa ison wi h manual implemen a ions using mes-
sage passing, o compa ed wi h Fas Flow [4], ano he s a e-o - he-
a ool o da a low p og amming. These expe imen s show ha
he o e heads in oduced by he new abs ac ions do no ha e a sig-
ni ican impac .
The es o he pape is o ganized as ollows. Sec ion 2 desc ibes
ou p oposed pa allel p og amming model. A discussion abou i s
usage is gi en in Sec ion 3 while Sec ion 4 shows he implemen-
a ion de ails. Sec ion 5 p esen s he expe imen al wo k ca ied ou
o es he implemen a ion. Sec ion 6 desc ibes some ela ed wo k
in he ield. Finally, he conclusions o he pape a e in Sec ion 7.
2. Hi Flow model
In his sec ion we p esen Hi Flow, a new pa allel p og amming
amewo k implemen ed in C++ ha exploi s da a low pa allelism
o bo h sha ed- and dis ibu ed-memo y sys ems. The Hi Flow
p og amming model akes i s no a ion om Colo ed Pe i ne s [16].
A Hi Flow p og am is a ne wo k composed o wo kinds o nodes,
called places and ansi ions. The places a e sha ed da a con aine s
ha keep okens, while he ansi ions a e he sequen ial p ocessing
componen s o he sys em. T ansi ions a e connec ed by di ec ed
channels o places, wi h he di ec ion de e mining he inpu and
ou pu ole o places o each ansi ion. A ansi ion akes one
oken om each o i s inpu places and pe o ms some ac i i y
wi h hem. I may hen add okens o any/all o i s ou pu places.
This ac i i y is epea ed while he e a e okens a i ing o he inpu
places.
We p opose he compu a ion inside he ansi ions o be mode-
d i en. Using a ma hema ical no a ion, P={p1, p2,...,pn}is
a ini e se o places and T={ 1, 2,..., m}is a ini e se o
ansi ions composed o modes: i={m1, m2,...,mo}. Each
mode miis a uple h , I, O, nex iwhe e I⊆Pa e he inpu
channels, O⊆Pa e he ou pu channels, is he sequen ial
unc ion, and nex ∈ {m1, m2,...,mo} ∪ END is he selec ed
nex mode.
Modes a e used o de ine mu ually exclusi e ac i i ies inside he
ansi ions ha dynamically econ igu e he ne wo k. A mode en-
ables a subse o connec ions o inpu places o ou pu places. Fo
each mode, he use de ines a unc ion o p ocess inpu s, he asso-
cia ed places and he de aul nex mode ha will be execu ed when
he cu en one inishes. A ansi ion wi h se e al modes changes
i s mode when all he okens om he ac i e mode ha e been p o-
cessed. To de ec ha he e a e no mo e okens emaining o pend-
ing o a i e o he inpu places, special signal okens a e used o in-
o m o a mode change (mode-change signal). The change o mode
in a ansi ion au oma ically sends mode-change signals o all i s
ou pu places. Thus, signals a e p opaga ed au oma ically ac oss
he ne wo k, lushing okens p oduced on he p e ious mode, be-
o e changing each ansi ion o he new mode. When a ansi ion
change i s mode, inpu and ou pu places a e econ igu ed acco d-
ing o he new mode speci ica ion. An example o a ne wo k wi h
modes can be seen in Fig. 1. The ne wo k has a ansi ion (A) wi h
wo modes. On each mode, he ansi ion will send okens o a di -
e en des ina ion B o C.
Finally, he modes can be used o enable da a locali y, de ining
ask- o- ask a ini ies. Task implemen ed as unc ions o di e en
modes in he same ansi ion a e mu ually exclusi e and a e ex-
ecu ed by he same h ead so hey can sha e da a s uc u es. Fo
example, da a a ini y is used in he Smi h-Wa e man algo i hm,
which is one o he benchma ks discussed in he expe imen al sec-
ion. This benchma k pe o ms a wo-phase wa e on algo i hm.
In he i s phase, i calcula es he elemen s o a ma ix s a ing om
he op le elemen . The second phase is a back acking sea ch ha
s a s om he bo om igh elemen o he esul ing ma ix using
he da a ob ained om he p e ious phase. As is shown in Fig 2,
i is possible o c ea e a ne wo k o model his kind o p oblem
wi hou using he modes. Howe e , using he modes, we can old
ha ne wo k adding wo di e en ac i i ies in he ansi ions, one
o each phase o he algo i hm. Thus, each ansi ion can pe o m
he wo equi ed s ages sha ing i s assigned po ion o he ma ix,
a oiding communica ions o he ma ix po ions, ha would imply
sending big okens h ough places.
3. P og amming wi h Hi Flow
We ha e de eloped a p o o ype o a amewo k o implemen pa -
allel p og ams in acco dance wi h he p oposed model. The cu -
en p o o ype elies on POSIX Th eads P og amming (P h eads)
and he s anda d Message Passing In e ace (MPI) o suppo bo h
sha ed- and dis ibu ed-memo y a chi ec u es. This sec ion ex-
plains he key ea u es o he p og amming amewo k. I con ains
a summa y o he Hi Flow API, a desc ip ion o how o build a
p og am ne wo k, and de ails abou he mode seman ics. The main
Hi Flow classes a e shown in he UML diag am in Fig. 3. A able
wi h he API me hods can be ound in [11].
3.1 Building ansi ions
To use his amewo k, he use has o c ea e a class which ex ends
he p o ided T ansi ion class wi h he sequen ial ac i i ies o he
p og am (See example in Fig. 4). The ini and end me hods can
1class MyT ansi ion: public T ansi ion {
2public:
3 oid execu e(){ // Use ac i i y me hod
4double in ask;
5ge (&in ask); // Re i e a oken om he place
6double ou ask = p ocess(in ask)
7pu (&ou ask); // Pu he oken in o he ou pu
8}
9};
Figu e 4: Hi Flow example o he c ea ion o a T ansi ion ex ending
he basic T ansi ion class.
be ex ended o execu e s a ing and ending ac ions be o e and a e
he execu ion o he p og am. The use classes should in oduce
one o mo e new me hods wi h a bi a y names o encapsula e he
code o pa icula mode ac i i ies. The associa ion be ween modes
and ac i i y me hods is es ablished when building he ne wo k (see
sec ion 3.2).
The ac i i y me hod is au oma ically called when he e a e o-
kens o be p ocessed in he inpu places decla ed o i s mode.
I he e a e no inpu places o i s pa icula mode, i will be
called jus once. The use -de ined ac i i y me hods can use he
T ansi ion::ge o T ansi ion::pu me hods o e ie e o-
kens om, o append okens o, he cu en places. The ge me hod
e ie es one oken o each o he ac i e inpu places o he cu en
mode. On each ac i i y me hod in oca ion, Hi Flow ensu es ha
he ge me hod can be called once. Addi ional calls o ge will
block un il he e a e again a leas one oken in each inpu place. I
he amewo k de ec s ha he p oduce s ha eed he inpu places
ha e ended hei modes, meaning no mo e okens will be p oduced
(end-mode okens in he inpu places) and he inpu places a e al-
eady emp y o okens o he ac i e mode, he call o ge will h ow
an excep ion. The pu me hod adds a oken o a speci ic ou pu
place. The ou pu place can be selec ed by i s iden i ie using he
second a gumen o he pu me hod. I can be omi ed i he e is
only one ac i e ou pu place in he mode.
A mode au oma ically inishes when he p oduce ansi ions
ha e sen a mode-end signal indica ing ha hey ha e inished
he ac i i y in ha mode, and all he okens in he places, ha
we e gene a ed in he p e ious mode, ha e been p ocessed. A his
momen , he ansi ion sends end-mode signals okens o he ac i e
ou pu places and au oma ically e ol es o he nex -p og ammed
mode. The nex -p og ammed mode can be changed by calling he
T ansi ion::mode me hod a any ime. I i is no changed by
he use , he de aul nex mode is END ha is used o inish he
compu a ion.
The example in Fig. 4 ex ends he T ansi ion class by decla -
ing a use ac i i y me hod. The me hod e ie es a oken om one
place, p ocesses i , and sends he esul o an ou pu place.
The okens a e C++ a iables o any ype, handled using em-
pla e me hods. The ma shaling and unma shaling is done in e nally
wi h MPI unc ions. The basic ypes (cha , in , loa , ...) a e enabled
by de aul . Use de ined ypes equi e he p og amme o decla e a
da a ype wi h a Hi Flow unc ion (hi TypeC ea e) ha in e nally
gene a es and egis e s he p ope MPI de i ed ype.
3.2 Building he ne wo k
Once he ansi ion classes a e de ined, he p og amme builds he
ne wo k in he main unc ion o he C++ p og am. This implies
c ea ing ansi ion and place objec s, associa ing he ac i i y me h-
ods, inpu , and ou pu places o modes on he ansi ions, and inally
adding he ansi ions o a Ne objec . Fig. 5 shows a simple code
T ansi ion A T ansi ion B
modes:
Mode A1Mode A2
Ne wo k c ea ion Ne wo k execu ion
T ansi ion C
B
C
A2
B
C
A1
p1
p2
Figu e 1: Example o a ne wo k using modes. T ansi ion A has wo modes (A1and A2), each mode enables an ou pu channel connec ing A
wi h B o A wi h C.
Ne wo k wi hou modes Ne wo k wi h modes
Ma ix M1,0 M1,1 M1,2
M0,0 M0,1 M0,2
M2,0 M2,1 M2,2
M1,0 M1,1 M1,2
M0,0 M0,1 M0,2
M2,0 M2,1 M2,2
M1,0
M1,1
M1,2
M0,0
M0,1
M0,2
M2,0
M2,1
M1,0 M1,1 M1,2
M0,0 M0,1 M0,2
M2,0 M2,1 M2,2
Figu e 2: Smi hWa e man ne wo k s uc u e wi h and wi hou modes.
<<bind>>
Place
# Place(s ing name, ReduceOp op)
+ se MaxSize(in s)
T
Ne
add(T ansi ion* )
un()
T ansi ion
+ addMe hod(Me hod * me hod, s ing mode = "de aul ")
+ addInpu (Place * p, s ing mode = "de aul ")
+ addOu pu (Place * p, s ing mode = "de aul ", bool eedback = alse)
+ ini ()
+ end()
# ge (T1* 1, [T2* 2=NULL,...])
# pu (T& , in placeid=0)
# mode(s ing name)
Place<in >
Mode
s ing name
Use T ansi ion
Figu e 3: UML diag am o he amewo k.
1Place<double> placeA, placeB;
// Decla e he places
2placeA.se MaxSize(10); // Se he place size
3
4MyT ansi ion ansi ion;
5
6// Add he me hod and places o modeA
7 ansi ion.addMe hod(&MyT ansi ion::execu e,"modeA");
8 ansi ion.addInpu (&placeA,"modeA");
9 ansi ion.addOu pu (&placeB,"modeA");
10 ...
11
12 Ne ne ; // Decla e he ne
13 ne .add(& ansi ion); // Add he ansi ion
14 ne . un(); // Run he ne
Figu e 5: Hi Flow example o he ne wo k c ea ion.
wi h a ne wo k using he p e iously shown MyT ansi ion ansi-
ion.
The i s s ep is o c ea e he places ha will be used in he
applica ion (line 1). The Place class is a empla e class used o
build he in e nal communica ion channels. The size o he place
de ines he g anula i y o he in e nal communica ions: I is an
op imiza ion pa ame e ha ep esen s he numbe o packed okens
ha will be ans e ed oge he . The use can se i in acco dance
wi h he oken gene a ion a io o he ansi ion.
The nex s ep is o se he ac i i y me hod and he inpu s and ou -
pu s o each mode. The addInpu ,addOu pu , and addMe hod
me hods, ha e an op ional pa ame e o speci y he mode. When
his pa ame e is no speci ied, a de aul END mode is implic-
i ly selec ed. Lines s a ing a 7 se he ac i i y me hod, an inpu
place, and an ou pu place o he de aul mode. Mul iple calls o
he addInpu o addOu pu o he same ansi ion mode, allow
MPMC cons uc ions o be buil .
Finally, all he ansi ions a e added o a Ne class ha con ols
he mapping and he execu ion (lines 12 and 13). Line 14 in okes
he Ne :: un me hod ha s a s he compu a ion.
3.3 Mapping
Using Hi Flow, he p og amme can p o ide a mapping policy o
assign ansi ions o he a ailable MPI p ocesses. I i is no p o-
ided, he e is a de aul allback policy implemen ing a simple
ound- obin algo i hm. MPI p ocesses wi h mo e han one mapped
ansi ion au oma ically spawn addi ional h eads o concu en ly
execu e all he ansi ions. Hi Flow implemen a ion sol es he po-
en ial concu ency p oblems in oduced by synch oniza ion and
communica ion when mapping ansi ions o he same p ocess (see
Sec . 4.3). In he cu en p o o ype, he mapping policies should
p o ide an a ay associa ing indexes o ansi ions o MPI p ocess
iden i ie s.
4. Implemen a ion de ails
This sec ion discusses some o he implemen a ion challenges asso-
cia ed wi h he model, and how hey ha e been sol ed in he cu en
p o o ype amewo k.
4.1 Ta ge ing bo h sha ed and dis ibu ed sys ems
One o he main goals o he amewo k is o suppo bo h sha ed
and dis ibu ed memo y sys ems wi h a single p og amming le el
o abs ac ion. The use -de ined ansi ion objec s ha con ain he
logic o he p oblem a e mapped in o he a ailable MPI p ocesses.
Since he e may no be enough p ocesses o all o he ansi ions,
h eads a e spawned inside he p ocesses i needed.
4.2 Dis ibu ed places
The Hi Flow places a e no physically loca ed in a single p ocess.
Ins ead, hey a e dis ibu ed oken con aine s. A place is imple-
men ed as mul iple queues o okens loca ed in he ansi ions ha
use ha place as inpu . When needed, he okens a e ansmi ed
and ea anged be ween he queues an inpu place on he ansi-
ions. This solu ion builds a dis ibu ed MPMC queue mechanism
ha exploi s da a locali y, and is mo e scalable han a cen alized
scheme whe e a single p ocess manages all he okens o a place.
Howe e , his is a solu ion ha in oduces coo dina ion challenges.
In e nally, he dis ibu ed places a e implemen ed using po s
ha mo e he okens om he sou ce o one o he des ina ion
ansi ions. Inpu and ou pu po s a e linked using channels. Fig-
u e 6 shows how he a cs o he model a e implemen ed using po s.
The e a e i e si ua ions:
(a) When a place connec s wo ansi ions, a channel will be con-
s uc ed o send he okens om he sou ce o he des ina ion.
(b) When he e a e wo o mo e inpu places in a ansi ion, i will
ha e se e al inpu oken po s, each o hem connec ed o he
co esponding sou ce.
(c) When wo o mo e ansi ions send okens o a common place,
he des ina ion will ha e a single po ha will ecei e okens,
ega dless o he ac ual sou ce.
(d) I a place has se e al ou pu ansi ions, any o hem can con-
sume he okens. To allow his beha io , when a place is sha ed
by se e al des ina ions, he sou ce will send okens in a ound-
obin ashion o each ou pu po . This can lead o load unbal-
ance i he ime o consume okens in he des ina ions is no
compensa ed. To sol e his, a wo k-s ealing mechanism is used
o edis ibu e okens be ween he des ina ion ansi ions.
(e) When a ansi ion uses he same place as inpu and ou pu , he
oken will low di ec ly o he inpu po o e iciency easons.
4.3 Po s, bu e s, and communica ions
This sec ion shows he in e nal po objec s and explains he de-
ails abou he communica ions and bu e ing. Figu e 7 shows an
example o a wo- ansi ion ne wo k. The e is a p oduce ha gen-
e a es okens which a e sen o a consume using he place A. The
consume p esumably pe o ms a il e ope a ion on he okens and
sends some o hem back o he p oduce using he place B. Figu e 8
desc ibes he in e nal s uc u es o he p e ious example.
The in e nal communica ions a e handled by Po objec s. The
ansi ions ha e a po o e e y inpu o ou pu place. The po s
ha e a bu e whe e he okens a e s o ed. The size o he bu e is
de e mined by he maximum numbe o okens ha can be s o ed a
he same ime in he place ha i ep esen s, as de ined by he use
wi h he Place::se MaxSize me hod. The size o he bu e also
has an ex a space o he message heade s and o he in o ma ion
ha mus be sen along wi h he okens. When okens a e sen o
a place, hey a e i s s o ed in he ou pu po bu e . The Hi Flow
un ime lib a y decides when o pe o m he eal communica ion.
By de aul , i will y o maximize he po bu e usage, packing as
many okens as possible o minimize he numbe o MPI messages
o be sen , wi hou delaying communica ions.
In addi ion o he inpu po bu e s, he ansi ions ha e queues
o s o e he okens ecei ed. The e is a queue o each inpu place.
When an incoming MPI message is ecei ed, he inpu po bu e
associa ed o he channel is used o e ie e he okens and a e
s o e hem in he co esponding queue whe e hey can be accessed
by he ansi ion ge me hod. Unlike he bu e s, which ha e a
limi ed memo y space assigned, he queues g ow dynamically and
a e only limi ed by he hos memo y. Finally, he use me hod is
a) b) c) d)
WS
e)
Figu e 6: T ansla ion om he model design o i s implemen a ion. WS: wo k-s ealing.
P oduce Consume
Place
A
Place
B
Figu e 7: Small example ne wo k wi h wo ansi ions.
au oma ically called o p ocess he a ailable okens when he e is
a leas one oken in each inpu queue.
In Fig. 8, he p oduce ansi ion (2) and he consume ansi ion
(2’) a e execu ed in wo di e en p ocesses (1 and 1’, espec i ely).
Since bo h ansi ions ha e only one inpu place, hey ha e only one
inpu oken queue (3 and 3’). The size o he place Ais 5, hus he
ou pu po o he p oduce (5) and he inpu po o he consume
(4’) ha e a bu e o 5 elemen s. In con as , he size o Bis 3,
so i s po bu e s (4 and 5’) ha e ha same size. The igu e also
ep esen s he MPI communica ion bu e s o he wo p ocesses (6
and 6’).
Wi h he Hi Flow un ime, i is no possible o p oduce a dead-
lock due o po bu e exhaus ion, e en in unbalanced ne wo ks
wi h cycles. Conside o example he ne wo k depic ed in Fig. 8.
Assuming ha he p oduce and consume send okens wi h a e y
unbalanced a io, causing he po bu e o he wo ansi ions o
become exhaus ed, i will no cause a deadlock. The un ime will
keep ecei ing messages and s o ing hem in he local and unlim-
i ed ansi ion queue. Thus, he only limi a ion will occu when one
o he p ocesses deple es he hos memo y.
Howe e , due o a limi a ion o he MPI-3 s anda d ha only
allows one MPI bu e pe p ocess, i is possible o p oduce a
deadlock when se e al ansi ions a e mapped in he same MPI
p ocess using h eads. I wo ansi ions a e mapped o he same
p ocess, hey sha e he same MPI bu e . Thus, he messages o
one ansi ion could consume all he bu e memo y, p e en ing he
o he ansi ion om pe o ming i s communica ions. This opens
he possibili y o p oducing a deadlock on he p og ession o he
whole ne wo k. This p oblem can be sol ed using he new ea u es
ha a e being s udied o be included in MPI-4. Such as Alloca e
Recei e communica ions [15] ha alloca e memo y in e nally o
incoming messages o elimina e bu e ing o e head when ecei ing
unknown-size messages, and Communica ion Endpoin s [8] ha
allow he h eads inside a p ocess o communica e as i hey a e
sepa a e anks.
4.4 Wo k-s ealing
To sol e load unbalances when a place has se e al ou pu ansi-
ions, Hi Flow uses a wo k-s ealing mechanism o edis ibu e o-
kens be ween he consume s. The oken queues ha we e p esen ed
in Sec 4.3 a e in ac double-ended queues. The use unc ion
e ie es he okens om he bo om wi h he T ans ion::ge
me hod while he wo k-s ealing mechanism akes o adds okens
using he op end. When a ansi ion p ocesses all he okens in i s
queue, he Hi Flow un ime will y o ob ain mo e okens. Fi s i
will selec a ic im om wi hin he o he ansi ions in he wo k-
s ealing g oup, and hen i will send a eques message. Depending
on he numbe o a ailable okens in he ic im, i can send some
o i s okens back o send a message denying he eques . In o de
o de e mine when he e a e no mo e okens a ailable in any o he
ansi ions, a dis ibu ed o ing- ee scheme is pe o med.
5. Case S udies: Hi Flow E alua ion
In his sec ion, h ee case s udies a e discussed o es whe he he
model is sui able o ep esen di e en kinds o applica ions and o
check he pe o mance o he amewo k.
5.1 Benchma ks
The i s benchma k calcula es he Mandelb o se , an emba ass-
ingly pa allel p og amming applica ion ha helps us o es he ba-
sic unc ionali ies o ou p oposal, o de ec po en ial o e heads,
and also allows us o compa e wi h o he solu ions.
The nex wo benchma ks a e wo implemen a ions o a eal
applica ion. They p esen e y di e en implemen a ions o he
Smi h-Wa e man algo i hm, an algo i hm o pe o m local align-
men s o p o ein sequences. One o hem is swps3 [18], a highly
op imized implemen a ion ha ex ensi ely uses ec o ins uc ions.
The o he one is a pa alleliza ion based on he implemen a ion de-
eloped by Clo e [7]. The i s one is a simple ask- a m applica-
ion, while he second ep esen s a complex combina ion o wa e-
on and educ ion ope a ions.
5.2 Pe o mance
Expe imen al wo k has been conduc ed o show ha he imple-
men a ion o Hi Flow achie es a good pe o mance compa ed wi h
o he amewo ks and wi h manually op imized implemen a ions.
We use wo di e en expe imen al pla o ms wi h di e en a chi-
ec u es: A mul ico e sha ed-memo y machine and a dis ibu ed
clus e o sha ed memo y mul ico es. The sha ed-memo y sys em,
A las, has 4 AMD Op e on 6376 p ocesso s wi h 16 co es each
a 2.3GHz, and 256GB o RAM. The dis ibu ed sys em, CETA-
Ciema , is composed o se e al MPI nodes wi h wo Quad Co e In-
el Xeon p ocesso s (4 co es, 2.26GHz) each, hus each node con-

MPI
P oduce
Aou
MPI buffe
Bin
MPI
Consume
Bou
MPI buffe
Ain
1
2
3
5
6
4
1'
2'
3'
5'
6'
4'
Figu e 8: Desc ip ion o he di e en bu e s, da a s uc u es and con ol elemen s in ol ed in he communica ions. Legend: (1) MPI p ocess.
(2) Use ansi ion objec . (3) In e nal oken queue o he ansi ion. (4) Inpu bu e po . (5) Ou pu bu e po . (6) MPI communica ion
bu e .
ains 8 co es. Fo expe imen a ion in his pape , we ha e used 8
nodes o ma ch he 64 co es o A las.
5.2.1 Mandelb o se
Fo he Mandelb o benchma k, we compa e he Hi Flow e sion
agains a manual MPI e sion, and wo e sions using Fas Flow [4],
a s uc u ed pa allel p og amming amewo k o iginally a ge ing
sha ed memo y mul i-co e a chi ec u es wi h speci ic ex ensions o
suppo combined dis ibu ed- and sha ed-memo y pla o ms. The
i s Fas Flow implemen a ion only uses he sha ed-memo y laye .
The second implemen a ion includes he use o bo h he dis ibu ed
and he sha ed-memo y laye s. The sha ed-memo y pu e e sion is
di ec ly he implemen a ion included in he Fas Flow dis ibu ion
examples, ha uses he Fas Flow a m pa e n. We ha e de eloped
he dis ibu ed e sion using he wo- ie model o he ex ended
Fas Flow lib a y ha suppo s bo h sha ed and dis ibu ed memo y
using di e en classes [3]. This las e sion has a a m pa e n
inside each dis ibu ed node. The e is also an uppe ie p oduce
ha coo dina es he wo k and eeds asks o he nodes, wi h hei
lowe ie a ms.
All he implemen a ions use a a m s uc u e ha p ocesses he
g id by ows. The manually de eloped one implemen s a simple
a m algo i hm in MPI. The Hi Flow e sion uses a ne wo k wi h
a p oduce ansi ion and se e al wo ke ansi ions connec ed by a
single place, This is a e y simple benchma k used o es he Hi -
Flow channel implemen a ion, and he wo k-s ealing mechanism.
Figu e 9 shows he esul s o he Mandelb o implemen a ions.
The p og ams calcula e he se in a g id o 214 ×213 elemen s.
The p og ams use up o 1 000 i e a ions o de e mine i each ele-
men belongs o he se leading o many low cos asks o be p o-
cessed. Fas Flow sha ed-memo y implemen a ion scales be e in
A las, since he in e nal lock- ee queues ake ad an age o he a -
chi ec u e. Hi Flow implemen a ion is simple han he dis ibu ed
Fas Flow e sion because i uses a unique ie o bo h sha ed- and
dis ibu ed-memo y a chi ec u es. I shows wo se scalabili y in he
sha ed-memo y machine bu ob ains he same esul s as Fas Flow
in he dis ibu ed one. This shows ha Hi Flow channel and wo k-
s ealing implemen a ion ha e a g ea scalabili y in dis ibu ed en i-
onmen s, he e ha is s ill oom o imp o emen in sha ed mem-
o y machines.
5.2.2 Swps3
Fo he swps3, we compa e he o iginal e sion [18], which is im-
plemen ed using pipe and o k sys em calls o c ea e se e al p o-
10
100
0 10 20 30 40 50 60 70
Time (seconds)
Wo ke s
Mandelb o se benchma k (A las)
Manual
Hi Flow
Fas Flow
10
100
0 10 20 30 40 50 60 70
Time (seconds)
Wo ke s
Mandelb o se benchma k (CETA-Ciema )
Manual
Hi Flow
Dis ibu ed Fas Flow
Figu e 9: Mandelb o se benchma k esul s.
cesses in he same machine, wi h he Fas Flow and he Hi Flow
e sions. The s uc u e o his benchma k is a a m wi h an emi -
e . Fo a ai compa ison, we ha e de eloped he Fas Flow and
Hi Flow e sions s a ing wi h he sequen ial code o he o iginal
swps3 benchma k. We ha e no used he o iginal example included
in Fas Flow [2], since i uses some memo y alloca ion op imiza-
ions and does no wo k o he bigge sequences chosen as inpu
o ou expe imen s, needed o gene a e enough wo kload o ou
a ge sys ems. All he e sions ma ch a single p o ein sequence o
all he p o eins om a da abase o sequences. We ha e used he
UniP o Knowledgebase (UniP o KB) elease 2014 04, a p o ein
in o ma ion da abase main ained by he Uni e sal P o ein Resou ce
10
100
1000
0 10 20 30 40 50 60 70
Time (seconds)
Wo ke s
SWPS3 benchma k (A las)
Re e ence
Hi Flow
Fas Flow
10
100
1000
0 10 20 30 40 50 60 70
Time (seconds)
Wo ke s
SWPS3 benchma k (CETA-Ciema )
Hi Flow
Dis ibu ed Fas Flow
Figu e 10: Swps3 benchma k esul s using he p o ein sequence
Q8WXI7 as inpu se .
(UniP o ) [1]. This da abase consis s o 544 996 sequences which
minium leng h is 2, i s maximum is 35 213, and i s a e age is 355.
Each sequence in he da abase is a ask ha will be ed o a a m
wo ke , so hey can be ma ched concu en ly. Wi h his example,
we es he Hi Flow communica ion and wo k-s ealing pe o mance
on a eal applica ion.
Figu e 10 shows he expe imen al esul s o he sequence
named Q8WXI7, which has 22 152 p o eins. Fo he sha ed-
memo y machine, bo h Hi Flow and Fas Flow su pass he esul s
o he e e ence e sion. Fas Flow ob ains a sligh ly be e pe o -
mance han Hi Flow. In he clus e , he e is no signi ican di e ence
be ween bo h e sions. We can conclude ha Hi Flow can be used
o his kind o eal applica ions wi h minimum pe o mance deg a-
da ion hanks o he p oposed implemen a ion.
5.2.3 Clo e’s algo i hm
The hi d benchma k, Clo eSW, is a di e en implemen a ion o
he Smi h-Wa e man p o ein alignmen ha aims o compa e wo
big sequences [7]. Fo his benchma k, we compa e wo sequences
o 100 000 elemen s. They a e bigge han any o he sequences
used in he p e ious expe imen . Fo his case, he Smi h-Wa e man
algo i hm equi es a 100 000 x 100 000 elemen s ma ix o be cal-
cula ed wi h he alignmen . The compu a ion is b oken down in o
pieces, ollowing a dis ibu ed wa e on s uc u e. The benchma k
has se e al phases: Fi s , i popula es he alignmen ma ix ollow-
ing he wa e on s uc u e. Then, i pe o ms a educe ope a ion
o de e mine he maximum ma ch sequence. Finally, i uses a back-
acking me hod o compose he sequence a e sing he wa e on
s uc u e in he in e se o de . We ha e de eloped a manual C++ &
MPI e sion and a Hi Flow e sion. The Hi Flow implemen a ion
use he mode s uc u e desc ibed in Fig. 2. The use o he modes in
Hi Flow allows he da a a ini y be ween phases o he benchma k
10
100
0 10 20 30 40 50 60 70
Time (seconds)
Wo ke s/P ocesses
Clo eSW benchma k (A las)
Manual
Hi Flow
10
100
0 10 20 30 40 50 60 70
Time (seconds)
Wo ke s/P ocesses
Clo eSW benchma k (CETA-Ciema )
Manual
Hi Flow
Figu e 11: Clo e’s Smi h-Wa e man benchma k esul s.
o be de ined, a oiding ex a communica ions o coo dina ions. The
esul s a e shown in Fig. 11. Bo h e sions show a simila pe o -
mance.
6. Rela ed wo k
Hi Flow is a complemen o Hi map, a lib a y o au oma ic bu
s a ic hie a chical mapping, wi h suppo o dense and spa se da a
s uc u es [9, 12]. The Hi map lib a y ocuses on da a-pa allel ech-
niques and lacks suppo o da a low applica ions. In a p e ious
wo k [10], we in oduced a i s app oach o a da a low model ha
could be used as a Hi map ex ension. The model in oduced in his
pape gene alizes se e al es ic ions o he p e ious one, in oduc-
ing a comple e gene ic model o ep esen any kind o combina-
ions o pa allel s uc u es and pa adigms. The di e ences wi h he
p e ious Hi map ex ension can be summa ized as: (1) We p esen
a gene al MPMC sys em whe e consume s can consume di e en
ask ypes om di e en p oduce s. (2) I suppo s cycles in he
ne wo k cons uc ion. (3) The new model in oduces a concep o
mode inside he p ocessing uni s o econ igu e he ne wo k, allow-
ing mu ually exclusi e unc ions in a ansi ion, and o in ui i ely
de ine ask- o- ask a ini y.
Hi Flow has se e al simila i ies wi h Fas Flow [4], a s uc u ed
pa allel p og amming amewo k a ge ing sha ed memo y mul i-
co e a chi ec u es. Fas Flow is s uc u ed as a s ack o laye s ha
p o ide di e en le els o abs ac ion, p o iding he pa allel p o-
g amme wi h a se o eady- o-use, pa ame ic algo i hmic skele-
ons, modeling he mos common pa allelism exploi a ion pa e ns.
Hi Flow ansi ion API is simila o Fas Flow; Fig. 12 shows a ull
example o a simple pipeline applica ion o compa e bo h o hem.
The main di e ences a e ha he Hi Flow amewo k is designed
o suppo bo h sha ed- and dis ibu ed-memo y wi h a single ie
model. I includes a anspa en mechanism o he co ec e mi-
na ion o ne wo ks e en in he p esence o eedback-edges, and
mode-d i en con ol o c ea e a ini y be ween ansi ions in dis-
ibu ed memo y en i onmen s. Rega ding he sys em a ge ed, he
Fas Flow g oup has de elop a dis ibu ed memo y ex ension us-
ing a wo ie model [3]. Howe e , his solu ion o ces he p o-
g amme o manually di ide he p og am s uc u e o he a ailable
memo y spaces and use a di e en mechanism o ex e nal chan-
nels o communica e he asks. In his sense, Hi Flow makes he
p og am design independen om he mapping. An ex ended com-
pa ison including de elopmen e o me ics o he p e ious wo
s age pipeline example using dis ibu ed Fas Flow can be ound in
[11].
Hi Flow ne wo ks a e simila o CnC (Concu en Collec-
ions [5]) g aphs. CnC is a pa allel p og amming model whe e
he compu a ion is de ined by se ial unc ions called compu a ion
s eps and hei seman ic o de ing cons ain s. Like Hi Flow ansi-
ions, CnC s eps communica e h ough message-passing as well as
sha ed memo y using sha ed en i ies called i em collec ions. One
o he di e ences be ween Hi Flow and CnC is ha CnC allows he
p og amme o gi e he schedule hin s abou he h ead a ini y o
he s eps. Howe e , CnC s eps only execu e one ac i i y each one
wi h i s own memo y space. Thus i is no possible o de ine ask o
ask a ini ies in he way Hi Flow ansi ions do.
OpenS eam [17] is a da a low OpenMP ex ension whe e dy-
namic independen asks communica e h ough s eams. The p o-
g amme exposes da a low in o ma ion using p agmas o de ine
he s eam inpu and ou pu ask. This allows a bi a y dependence
pa e ns be ween asks o be c ea ed. A s eam can ha e se e al
p oduce s and consume s ha access he da a in he s eam using a
sliding window. The OpenS eam un ime ensu es he coo dina ion
o he di e en elemen s. These s eams a e equi alen o he Hi -
Flow places and hey also elay on wo k s ealing. Howe e , Open-
S eam does no na i ely suppo dis ibu ed memo y hence canno
handle load balancing a he clus e le el. T ying o ans e his
model o dis ibu ed memo y in ol es he same p oblems as he
use o dis ibu ed Fas Flow.
S-Ne [13] is a decla a i e coo dina ion language. I de ines he
s uc u e o a p og am as a se o connec ed asynch onous com-
ponen s called boxes. S-Ne only akes ca e o he coo dina ion:
The ope a ions done inside boxes a e de ined using con en ional
languages. Boxes a e s a eless componen s wi h only a single inpu
and a single ou pu s eam. F om he p og amme s’ pe spec i e, he
implemen a ion o s eams on he language le el by ei he sha ed
memo y bu e s o dis ibu ed memo y message passing is en i ely
anspa en .
7. Conclusions
This pape p esen s a new pa allel p og amming model and ame-
wo k based on a da a low pa adigm. I allows p og ams o be de-
sc ibed as a ne wo k o communica ing ac i i ies in an abs ac
o m. The sys em allows o implemen om simple s a ic pa al-
lel s uc u es o complex combina ions o da a low and dynamic
pa allel p og ams. The desc ip ion is decoupled om he mapping
echniques o policies, which can be e icien ly applied a un- ime,
au oma ically adap ing s a ic o dynamic s uc u es o di e en e-
sou ce combina ions. Ou cu en amewo k anspa en ly a ge s
hyb id sha ed- and dis ibu ed-memo y pla o ms.
We p esen an e alua ion wi h examples o di e en classes o
dynamic and s a ic applica ions. Expe imen al pe o mance esul s
show ha he o e head in oduced by ou abs ac ions has minimal
impac compa ed wi h manual implemen a ions. Mo eo e , he e-
sul s ob ained in a dis ibu ed-memo y en i onmen show a simila
pe o mance o Fas Flow, a da a low p og amming amewo k o
mul i-co e pla o ms.
This gene ic amewo k will allow us o ocus esea ch on
he bes mapping policies ha can anspa en ly a ge he e oge-
neous pla o ms o speci ic o gene ic combina ions o pa allel
pa adigms, allowing us o build powe ul pa allel pa e ns using a
common and gene ic amewo k. Al hough, he expe imen al e-
sul s show ha he dis ibu ed suppo in ou cu en p o o ype
achie es good pe o mance, he e is s ill oom o imp o emen on
he h ead-le el communica ion implemen a ion o sha ed mem-
o y sys ems.
Acknowledgmen s
This esea ch has been pa ially suppo ed by MICINN (Spain) and
ERDF p og am o he Eu opean Union: HomP og-He Sys p ojec
(TIN2014-58876-P), CAPAP-H5 ne wo k (TIN2014-53522-REDT),
and COST P og am Ac ion IC1305: Ne wo k o Sus ainable Ul-
ascale Compu ing (NESUS), and by he compu ing acili ies o
Ex emadu a Resea ch Cen e o Ad anced Technologies (CETA-
CIEMAT), unded by he Eu opean Regional De elopmen Fund
(ERDF). CETA-CIEMAT belongs o CIEMAT and he Go e nmen
o Spain.
Re e ences
[1] UniP o Knowledgebase (UniP o KB). www.unip o .o g/.
[2] M. Aldinucci, M. Meneghin, and M. To qua i. E icien Smi h-
Wa e man on Mul i-co e wi h Fas Flow. In M. Danelu o, J. Bou -
geois, and T. G oss, edi o s, P oceedings o he 18 h Eu omic o
Con e ence on Pa allel, Dis ibu ed and Ne wo k-based P ocessing
(PDP), pages 195–199, Pisa, I aly, 2010. IEEE Compu e Socie y.
ISBN 978-1-4244-5672-7.
[3] M. Aldinucci, S. Campa, and M. Danelu o. Ta ge ing dis ibu ed
sys ems in as low. In P oceedings o he Eu o-Pa 2012 Pa allel
P ocessing Wo kshops, olume 7640 o Lec u e No es in Compu e
Science, pages 47–56. Sp inge Be lin Heidelbe g, 2013.
[4] M. Aldinucci, M. Danelu o, P. Kilpa ick, and M. To qua i. Fas Flow:
high-le el and e icien s eaming on mul i-co e. In S. Pllana and
F. Xha a, edi o s, P og amming Mul i-co e and Many-co e Compu ing
Sys ems, Pa allel and Dis ibu ed Compu ing. Wiley, 1s edi ion, 2014.
ISBN 0470936908.
[5] Z. Budimli´
c, M. Bu ke, V. Ca ´
e, K. Knobe, G. Lowney, R. New on,
J. Palsbe g, D. Peixo o, V. Sa ka , F. Schlimbach, and S. Tasi la .
Concu en collec ions. Scien i ic P og amming, 18(3-4):203–217,
Aug. 2010. ISSN 1058-9244. . URL h p://dx.doi.o g/10.
1155/2010/521797.
[6] R. Chand a, L. Dagum, D. Koh , D. Maydan, J. McDonald, and
R. Menon. Pa allel p og amming in OpenMP. Mo gan Kau mann,
1 edi ion, 2001. ISBN 1-55860-671-8.
[7] P. Clo e. Biologically signi ican sequence alignmen s using
Bol zmann p obabili ies. Technical epo , 2003. URL h p:
//bioin o ma ics.bc.edu/~clo e/pub/bol zmannPa is03.
pd .
[8] J. Dinan, P. Balaji, D. Goodell, D. Mille , M. Sni , and R. Thaku .
Enabling MPI in e ope abili y h ough lexible communica ion end-
poin s. In 20 h Eu opean MPI Use s’s G oup Mee ing, Eu oMPI ’13,
Mad id, Spain - Sep embe 15 - 18, 2013, pages 13–18, 2013. . URL
h p://doi.acm.o g/10.1145/2488551.2488553.
[9] J. F esno, A. Gonzalez-Esc ibano, and D. R. Llanos. Ex ending a
hie a chical iling a ays lib a y o suppo spa se da a pa i ioning.
The Jou nal o Supe compu ing, 64(1):59–68, 2013. ISSN 0920-8542.
[10] J. F esno, A. Gonzalez-Esc ibano, and D. R. Llanos. Run ime Sup-
po o Dynamic Skele ons Implemen a ion. In P oceedings o he
19 h In e na ional Con e ence on Pa allel and Dis ibu ed P ocessing
Techniques and Applica ions (PDPTA), pages 320–326, July 22-25,
Las Vegas, NV, USA., 2013.
[11] J. F esno, A. Gonzalez-Esc ibano, and D. R. Llanos. Addi ional ma e-
ial o he pape : Da a low p og amming model o hyb id dis ibu ed
and sha ed memo y sys ems. Technical Repo IT-DI-2015-0003,
Depa men o Compu e Science, Uni e si y o Valladolid, Spain,
1#include <hi low.h>
2using namespace hi low;
3
4class S ageA: public T ansi ion {
5in num asks;
6public:
7S ageA(in ): num asks( ){};
8
9 oid c ea e(){
10 long ask;
11 o (in i=0; i<num asks; i++){
12 ask = i;
13 pu ( ask);
14
15 }
16
17 }
18 };
19
20 class S ageB: public T ansi ion {
21 long sum;
22 public:
23 oid ini (){
24 sum = 0;
25
26 }
27 oid p ocess(){
28 long ask;
29 ge (& ask);
30 sum += ask;
31
32 }
33 oid end(){
34 cou << "Sum " << sum << endl;
35 }
36 };
37
38 in main(in na gs, cha * a gs[]){
39
40 Hi Flow::ini (&na gs, & a gs);
41
42 S ageA s _a(10); S ageB s _b;
43
44 Place<long> place("long con aine ");
45
46 s _a.addOu pu (&place,"c ea eTasks");
47 s _a.addMe hod(&S ageA::c ea e,"c ea eTasks");
48 s _b.addMe hod(&S ageB::p ocess,"p ocessTasks");
49 s _b.addInpu (&place,"p ocessTasks");
50
51 Ne ne ;
52 ne .add(&s _a); ne .add(&s _b);
53 ne . un();
54
55 e u n 0;
56 }
1#include < /pipeline.hpp>
2using namespace ;
3
4class S ageA: public _node {
5in num asks;
6public:
7S ageA(in ): num asks( ){};
8
9 oid * s c( oid * in ask){
10
11 o (in i=0; i<num asks; i++){
12 long * ask = new long;
13 * ask = (long) i;
14 _send_ou ( ask);
15 }
16 e u n NULL;
17 }
18 };
19
20 class S ageB: public _node {
21 long sum;
22 public:
23 in s c_ini (){
24 sum = 0;
25 e u n 0;
26 }
27 oid * s c( oid * in ask){
28 long * ask = (long*) in ask;
29 sum += * ask;
30 dele e ask;
31 e u n GO_ON;
32 }
33 oid s c_end(){
34 cou << "Sum " << sum << endl;
35 }
36 };
37
38 in main() {
39
40 _pipeline pipe;
41 pipe.add_s age(new S ageA(10));
42 pipe.add_s age(new S ageB());
43 i (pipe. un_and_wai _end()<0)
44 e u n -1;
45 e u n 0;
46 }
Figu e 12: A ull pipeline example in bo h Hi Flow (le ) and sha ed-memo y only Fas Flow ( igh ) amewo ks.
2015. URL h p://www.in o .u a.es/~j esno/ epo s/
IT-DI-2015-0003.pd .
[12] A. Gonzalez-Esc ibano, Y. To es, J. F esno, and D. R. Llanos. An
Ex ensible Sys em o Mul ile el Au oma ic Da a Pa i ion and Map-
ping. IEEE T ansac ions on Pa allel and Dis ibu ed Sys ems, 25(5):
1145–1154, May 2014. ISSN 1045-9219.
[13] C. G elck, S.-B. Scholz, and A. Sha a enko. A gen le in oduc ion
o S-Ne : Typed s eam p ocessing and decla a i e coo dina ion o
asynch onous componen s. Pa allel P ocessing Le e s, 18(2):221–
237, 2008.
[14] W. G opp, E. Lusk, and A. Skjellum. Using MPI : Po able Pa allel
P og amming Wi h he Message-passing In e ace. MIT P ess, 2
edi ion, 1999. ISBN 0262571323.
[15] D. Holmes. Ideas o pe sis an poin o poin communica ion. Tech-
nical epo , MPI Fo um Mee ings, 2014. URL h p://mee ings.
mpi- o um.o g/2014-11-scbo -p2p.pd .
[16] K. Jensen, L. M. K is ensen, and L. Wells. Colou ed Pe i Ne s
and CPN Tools o modelling and alida ion o concu en sys ems.
In e na ional Jou nal on So wa e Tools o Technology T ans e , 9
(3-4):213–254, Ma . 2007. ISSN 1433-2779.
[17] A. Pop and A. Cohen. A OpenS eam: Exp essi eness and Da a-Flow
Compila ion o OpenMP S eaming P og ams. ACM T ansac ions on
A chi ec u e and Code Op imiza ion (TACO), 9(4):53:1–53:25, 2013.
[18] A. Szalkowski, C. Lede ge be , P. K ¨
ahenb¨
uhl, and C. Dessimoz.
SWPS3 - as mul i- h eaded ec o ized Smi h-Wa e man o IBM
Cell/B.E. and x86/SSE2. BMC esea ch no es, 1(107), 2008. ISSN
1756-0500.