A New High-Level Parallel Portable Language for Hierarchical Systems in Trasgo

P oceedings o he 15 h In e na ional Con e ence on Compu a ional and Ma hema ical Me hods in Science and Enginee ing, CMMSE 2015 6–10 July, 2015. A New High Le el Pa allel Po able Language o hie a chical sys ems in T asgo Ana Mo e on-Fe nandez1, A u o Gonzalez-Esc ibano1and Diego R. Llanos1 1Depa amen o de In o m´a ica, Uni e si y o Valladolid emails: [email p o ec ed],[email p o ec ed],[email p o ec ed] Abs ac Cu en ly, he gene a ion o pa allel codes which a e po able o di e en kinds o pa allel compu e s is a challenge. Many app oaches ha e been p oposed du ing he las yea s ollowing wo di e en pa hs. P og amming om sc a ch using new p og amming languages and models ha deal wi h pa allelism explici ly, o au oma ically gene a ing pa allel codes om al eady exis ing sequen ial p og ams. Using he cu en main- end pa allel languages, he p og amme deals wi h mapping and op imiza ion de ails ha o ces o ake in o accoun de ails o he execu ion pla o m o ob ain a good pe - o mance. In code gene a o s om sequen ial p og ams, p og amme s canno con ol basic mapping decisions, and many imes he p og amme needs o ans o m he code o expose o he compile in o ma ion needed o le e age impo an op imiza ions. This pape p esen s a new high-le el pa allel p og amming language named CMAPS, designed o be used wi h he T asgo pa allel p og amming amewo k. This language p o ides a simple and explici way o exp ess pa allelism in a highly abs ac le el. The p og amme does no ace decisions abou g anula i y, h ead managemen , o in e p o- cess communica ion. Thus, he p og amme can exp ess di e en pa allel pa adigms in a easy, uni ied, abs ac , and po able o m. The language suppo s he necessa y ea u es imposed by ans o ma ion models such as T asgo, o gene a e pa allel codes ha adap hei communica ion and synch oniza ion s uc u es o a ge machines composed by mixed dis ibu ed- and sha ed-memo y pa allel mul icompu e s. Key wo ds: pa allel languages, pa allel p og amming models 1 In oduc ion I is inc easingly in e es ing o gene a e applica ion p og ams wi h he abili y o au oma i- cally adap hei s uc u e and load o any gi en a ge sys em. Using cu en main- end c CMMSE ISBN: xxx-xx-xxx-xxxx-x High Le el Pa allel Po able Language pa allel p og amming echnology o his pu pose is challenging. One o he mos p omising echniques o amewo ks which au oma ically gene a e op imized lowe -le el pa allel code om exis ing sequen ial p og ams is he polyhed al model. I p o ides a o mal ame- wo k o de elop au oma ic ans o ma ion echniques a he sou ce code le el [3]. The polyhed al model is applicable o codes based on sequen ial s a ic loops wi h a ine exp es- sions. Howe e , i does no suppo dynamic loops dependen on in o ma ion no known o pa ame izable a compile- ime. On he o he hand, many success ul pa allel p og amming models and ools ha explici ly deal wi h pa allelism ha e been p oposed. en i onmen s. Message-passing pa adigms (e.g. MPI lib a ies) ha e been shown o be e y e icien o dis ibu ed-memo y sys ems. Global sha ed memo y models, such as OpenMP, In el TBBs, o Cilk, a e commonly used in sha ed-memo y en i onmen s o simpli y h ead and memo y managemen . Many pa allel p og amming models like PGAS (Pa i ioned Global Add ess Space) languages (Chapel, X10, o UPC), p esen a middle poin app oach by explici ly managing local and global memo y spaces. The PGAS language mo e ela ed o ou wo k is Chapel [1]. I p oposes a sepa a ion o domain and mapping modules o gene a e dis- ibu ed a ays. Bu , he bes communica ion agg ega ion me hods p esen ed so a o Chapel abs ac ions a e es ic ed o speci ic ope a ions, o domain mapping p ope ies. Thus, he applica ion p og amme s ill aces many impo an decisions no ela ed wi h he pa allel algo i hms, bu wi h implemen a ion issues ha a e key o ob aining e icien p og ams. Fo example, decisions abou pa i ion and locali y s. synch oniza ion/commu- nica ion cos s; g ain selec ion and iling; p ope pa alleliza ion s a egies o each g ain le el; o mapping, layou , and scheduling de ails. Mo eo e , many o hese decisions may change o di e en machine de ails o s uc u e, o e en wi h da a sizes. P oduc i e pa allel- so wa e de elopmen needs a common app oach a he p og amming le el, o simpli y he asks o implemen ing, es ing, and debugging, independen ly o he machine de ails. In his pape we p esen CMAPS, a new high-le el pa allel p og amming language o he T asgo amewo k [2]. This language suppo s a wide ange o pa allel s uc u es and applica ions. The p og ams exp ess coo dina ion a an abs ac le el. The p og amme easons in e ms o logical p ocesses using a global memo y space, no acing decisions abou g anula i y, h ead managemen , o in e p ocess communica ion. CMAPS app oach p esen s se e al ad an ages wi h ega d o: (1) polyhed al amewo ks which wo k om sequen ial codes [4, 5, 6], as i suppo s dynamic loops wi h condi ions dependen on ex- p essions in ol ing da a- alues o un ime pa ame e s and, (2) explici pa allel languages, because i makes anspa en o he p og amme he de ails ela ed o he lowe -le el p o- g amming model, o in eg a e mapping echniques o o adap he code o he a chi ec u e and de ails o he execu ion pla o m, managing only a global memo y space and, educing he code complexi y. We p esen he design guidelines o CMAPS in e ms o he equi emen s and capabili- ies o he T asgo amewo k o gene a e lowe -le el code ha adap s hei communica ion c CMMSE ISBN: xxx-xx-xxx-xxxx-x Mo e on-Fe nandez, Ana Figu e 1: S uc u e o he T asgo ans o ma ion amewo k. and synch oniza ion s uc u es o he a ge machine. In pa icula , hese guidelines impose he inclusion o in o ma ion needed o au oma ically gene a e code ha compu es exac ag- g ega ed communica ions o a ge machines including dis ibu ed-memo y a chi ec u es. The es o he pape is o ganized as ollows: Sec ion 2 p esen s he T asgo model and hei ools. Sec ion 3 desc ibes he new p og amming pa allel language. Sec ion 4 p esen s he conclusions and u u e wo k. 2 T asgo amewo k The T asgo model [2] p oposes he use o a high-le el s uc u ed and abs ac ep esen a ion o he pa allel algo i hms. I uses a es ic ed synch oniza ion model (nes ed-pa allelism) a he highe le el, le ing he ans o ma ion sys em o gene a e mo e e icien and less synch onized pa allel s uc u es a he lowe le el. The o iginal model is based on he SP (Se ies-Pa allel) p ocess model [7], and da a-dis ibu ion algeb as, p o iding clea and well-de ined seman ics [8], and allowing hie a chical composi ions. The model is ee o ace condi ions, and unexpec ed s ochas ic beha io s o dead-locks. The high-le el code uses a global iew app oach in hie a chical decomposi ions. The seman ics p o ide clea synch oniza ion poin s and hie a chical global s a es ha simpli y es ing and debugging. Figu e 1 shows he s uc u e o he T asgo ans o ma ion amewo k. The le column shows he p og am ep esen a ions, and he igh columns he ans o ma ion laye s. A on -end ansla es he inpu language o an in e nal ep esen a ion in XML. An XML ep esen a ion has been chosen due o he s anda d and powe ul ools ha exis o iden i y and loca e documen ea u es (XPa h), and o apply documen ans o ma ions (XSLT). c CMMSE ISBN: xxx-xx-xxx-xxxx-x High Le el Pa allel Po able Language These echnologies can be used o w i e in a compac o m code ans o ma ion modules. The main pa o he ans o ma ion laye is o ien ed o con e he global add ess space in o a pa i ioned add ess space. I analyses da a dependencies and builds exp essions o compu e a un- ime he communica ions needed ac oss i ual p ocesses, in e ms o he esul s o mapping and layou unc ions. The ans o med code is ew i en by a back-end ha gene a es C code wi h calls o he Hi map un- ime lib a y [9]. The esul ing sequen ial code gene a ed o he local dis ibu ed p ocess is inally il e ed h ough polyhed al ools (Plu o compile [10]) o gene a e iled and op imized pa allel code o sha ed-memo y using OpenMP ( he me hodology used o in eg a e hese echniques a he Hi map le el was desc ibed in [11]). Finally, he code is compiled wi h a na i e C compile . 3 The new pa allel p og amming language CMAPS In his sec ion we desc ibe he p oposed pa allel language ha will be used as inpu in he T asgo amewo k. This language will allow he p og amme o exp ess pa allel algo i hms in e ms o abs ac decomposi ion and mapping echniques. 3.1 Design p inciples We p esen bellow guidelines o he design o an inpu language o he T asgo amewo k. 1. The inpu language will be a coo dina ion language. Sequen ial code will be exp essed wi h a adi ional p og amming language and using un ime lib a y calls (Hi map [9]) o manage he access o he da a s uc u es. Ex ensions o a adi ional sequen ial language (new p imi i es, s uc u es and modi ie s) should be used o exp ess he coo dina ion be ween sequen ial asks. Func ions con aining coo dina ion p imi i es will be anno a ed using a new modi ie . Inside hem, i will be only possible o execu e da a modi ica ions h ough calls o sequen ial unc ions. 2. The inpu language will use a p imi i e (wi h clauses) o anno a e each sec ion ha we will be execu ed in pa allel. The p imi i e should allow o indica e an a bi a y numbe o logical p ocesses, in e ms o cons an s o exp essions, including hose exp essed in e ms o he numbe o elemen s in da a s uc u es. This p imi i e could be nes ed as many imes as needed, e en in a ecu si e way. Inside he scope o he p imi i e, a mechanism o associa e calls o o he coo dina ion o sequen ial unc ions o logical p ocesses should be p o ided. This p imi i e will imply a logical synch oniza ion poin o he p ocesses a e he compu a ion pe o med in pa allel. 3. The sequen ial unc ions will be designed o deal wi h elemen s o a bi a y g ain. Thus, i a oids he p og amme o ake decisions abou he p oblem g anula i y ac- co ding o he machine capabili ies. c CMMSE ISBN: xxx-xx-xxx-xxxx-x Mo e on-Fe nandez, Ana 4. The language should p o ide a mechanism o in oke modules ha implemen s pa i- ion policies. The inpu s will be index spaces. The ou pu will be a map o indexes o i ual p ocesses. This map can be used o: (1) pe o m a pa i ion, dis ibu ion and alloca ion o da a s uc u es o , (2) g oup and schedule logical p ocesses in o i ual p ocesses. The code should be independen o he mapping (pa i ion, dis ibu ion, alloca ion) policies. Wi h his echnique i will be possible o change he pa i ion o alloca ion policy wi hou modi y any o he pa o he code. 5. The compu a ion will ha e a single global s a e and a unique logical p ocess be o e he pa allel p imi i e. When he pa allel asks a e launched, each one has a local copy o he global s a e. In he logical synch oniza ion poin a he end o he pa allel compu a ion he global s a e is consolida ed again. To gene a e his global s a e he pa allel p imi i e mus p o ided a way o educing co ec ly di e en alues, ound in he eplica ed a iables o each logical p ocess, in o he global s a e. 6. The language should p o ide a mechanism o analyse he da a dependences be ween he unc ion calls which a e in o he scope o di e en pa allel pa s. To ind da a dependencies can be a complex ask a compile ime. The language should use anno a- ions in he unc ion de ini ion o indica e he inpu /ou pu ole o each pa ame e in he unc ion in e ace. This in o ma ion will be used o ob ain he da a dependencies. 3.2 S udy cases To show he ea u es o CMAPS in eal p og ams we will use ou cases o s udy. The Jacobi sol e is a PDE sol e using a Jacobi i e a i e me hod o compu e he hea ans e equa ion in a disc e ized wo-dimensional space. I is implemen ed as a cellula au oma a. On each i e a ion, each ma ix posi ion o cell is upda ed wi h he p e ious alues o he ou neighbo s. See CMAPS code in Fig.2 The Gauss-Seidel p og am compu es he same hea ans e equa ion desc ibed abo e, bu using a Gauss-Seidel i e a i e me hod. In his me hod, he con e gence is accele a ed using alues al eady compu ed du ing he cu en ime-s ep i e a ion ollowing sequen ial seman ics. The me hod simply uses one ma ix, wi h no copy o he old alues. Thus, when using he neighbo alues o he uppe and le ma ix posi ions, alues al eady upda ed a e used. See CMAPS code in Fig.2 The Classical Ma ix Mul iplica ion is he ypical sequen ial implemen a ion o he ma ix mul iplica ion wi h h ee nes ed loops. See CMAPS code in Fig.3 Cannon’s Algo i hm o ma ix mul iplica ion wo ks wi h a pa i ion o he ma ices in k×kpieces, equi ing no mo e han one local piece o he same ma ix a he same ime, and using a simple ci cula block shi pa e n o mo e da a ac oss p ocesses. Each ma ix-block p oduc is compu ed using he classical sequen ial algo i hm. See CMAPS code in Fig.3 c CMMSE ISBN: xxx-xx-xxx-xxxx-x High Le el Pa allel Po able Language 1/* Jacobi Sol e (Poisson equa ion): Func ion o upda e one cell elemen */ 2 oid upda eCell( in double up, in double down, in double le , in double igh , 3inou double esul , ou double di ) { 4double old = * esul ; 5* esul = ( up + down + le + igh ) / 4 ; 6*di = abs( * esul - old ); 7} 8 9/* Jacobi Sol e (Poisson equa ion): Pa allel sol e */ 10 coo dina ion oid jacobiSol e ( inou ile double M[][], 11 in in limi , in double h eshold) { 12 double inside[][] = M[1:$-1][1:$-1]; 13 Map dis ibu ion = Map( inside.shape, blocks, ec angula 2D ) ); 14 A ayMap( inside, dis ibu ion ); 15 16 double di , maxDi ; 17 loop( i in [1:limi ] and maxDi > h eshold ) { 18 ese Di ( maxDi ); 19 pa allel ( dis ibu ion ) { 20 do: upda eCell( M[ pidx(0)-1 ][ pidx(1) ], 21 M[ pidx(0)+1 ][ pidx(1) ], M[ pidx(0) ][ pidx(1)-1 ], 22 M[ pidx(0) ][ pidx(1)+1 ], M[ pidx(0) ][ pidx(1) ], 23 di ); 24 educe: MAX( di , maxDi ); 25 } } } 1/* Poisson equa ion: Func ion o upda e one cell elemen */ 2 oid upda eCell( in double up, in double down, in double le , in double igh , 3ou double esul ) { 4* esul = ( up + down + le + igh ) / 4 ; 5} 6 7/* Gauss-Seidel Pa allel Sol e */ 8coo dina ion oid gaussSol e ( inou ile double M[][], in in limi ) { 9double inside[][] = M[1:$-1][1:$-1]; 10 Map dis ibu ion = Map( inside.shape, blocks, opRec angula 2D ) ); 11 A ayMap( inside, dis ibu ion ); 12 13 loop( i in [1:limi ] ) { 14 pa allel ( dis ibu ion ) { 15 do : wai low( M[ pidx(0)-1 ][ pidx(1) ], M[ pidx(0) ][ pidx(1)-1 ] ) 16 upda eCell( M[ pidx(0)-1 ][ pidx(1) ], M[ pidx(0)+1 ][ pidx(1) ], 17 M[ pidx(0) ][ pidx(1)-1 ], M[ pidx(0) ][ pidx(1)+1 ], 18 M[ pidx(0) ][ pidx(1) ] ); 19 20 21 } } } Figu e 2: CMAPS code o wo S encils algo i hms: Jacobi sol e and Gauss-Seidel c CMMSE ISBN: xxx-xx-xxx-xxxx-x Mo e on-Fe nandez, Ana 1/* Pa allel Block Ma ix Mul iplica ion: Classical algo i hm */ 2coo dina ion oid mmP oduc Classical( in ile double A[][], in ile double B[][], 3ou ile double C[][] ) { 4Map mC = Map( C.shape, blocks, opRec angula 2D ) ); 5A ayMap( C, mC ); 6A ayMap( A, Map( A.shape, blocks, opRec angula 2D ) ) ); 7A ayMap( B, Map( B.shape, blocks, opRec angula 2D ) ) ); 8 9pa allel ( mC ) { 10 do: mmP oduc Seq( A[:][@0:@$], B[@0:@$][:], C[:][:] ); 11 } } 12 13 /* Pa allel Block Ma ix Mul iplica ion: Cannon’s algo i hm */ 14 coo dina ion oid mmP oduc Cannons( in ile double A[][], in ile double B[][], 15 ou ile double C[][] ) { 16 Map mC = Map( C.shape, blocks, opSqua e ) ); 17 A ayMap( C, mC ); 18 A ayMap( A, Map( A.shape, blocks, opSqua e ) ) ); 19 A ayMap( B, Map( B.shape, blocks, opSqua e ) ) ); 20 21 loop( i, [ 0 : max( mC.size(0), mC.size(1) ) ] ) { 22 pa allel ( mC ) { 23 do: mmP oduc Seq( dmap(A, mapidx(0),cyc(( mapidx(1) - mapidx(0) - i)) ), 24 dmap(B, cyc(( mapidx(0) - mapidx(1) - i )),mapidx(1) ), 25 dmap(C, mapidx(0), mapidx(1)) ); 26 } } } 27 28 /* Pa allel Block Ma ix Mul iplica ion: Hie a chical composi ion */ 29 coo dina ion oid mmP oduc Cannons( in ile double A[][], in ile double B[][], 30 ou ile double C[][] ) { 31 Map mC = Map( C.shape, blocks, opSqua e ) ); 32 A ayMap( C, mC ); 33 A ayMap( A, Map( A.shape, blocks, opSqua e ) ) ); 34 A ayMap( B, Map( B.shape, blocks, opSqua e ) ) ); 35 36 loop( i, [ 0 : max( mC.size(0), mC.size(1) ) ] ) { 37 pa allel ( mC ) { 38 do: mmP oduc Classical( dmap(A, mapidx(0),cyc(( mapidx(1) - mapidx(0) - i)) ), 39 dmap(B, cyc(( mapidx(0) - mapidx(1) - i )),mapidx(1) ), 40 dmap(C, mapidx(0), mapidx(1)) ); 41 } } } Figu e 3: CMAPS code o a mul ile el Ma ix Mul iplica ion. c CMMSE ISBN: xxx-xx-xxx-xxxx-x High Le el Pa allel Po able Language 3.3 No a ions and de ini ions A T asgo inpu p og amming language can be designed in se e al ways, as a as i complies wi h he T asgo model seman ic (which de i es in he guidelines o he sec ion 3.1). We ha e designed a coo dina ion language ex ension o classical C language named CMAPS. CMAPS has been c ea ed o exp ess pa allel algo i hms in a simple, explici and in ui i e way o C p og amme s. 3.3.1 Domains, mapping policies and da a s uc u es The CMAPS language p o ides he na i e da a ypes o he o iginal sequen ial language (C), and ile ypes o mo e complex da a s uc u es, such as a ays. Manipula ion o na i e da a ypes is di ec . Da a in iles will be managed a un- ime using he Hi map lib a y [9]. Domain decla a ions and subselec ion o ile domains, a e exp essed wi h an ex ended C a ay no a ion simila o he Fo an90 colon no a ion inside squa e b acke s [begin:end:s ide]. The language p o ides a Map cons uc o . I ecei es h ee pa ame e s: An index domain o be mapped, he name o a pa i ion and layou echnique, and he name o a i ual opology building policy. Layou and opology echniques a e plug-in modules in he un- ime sys em [9]. Map objec s anspa en ly map an index domain o he de ices o a a ge sys em (guideline 4). The A ayMap unc ion is used o map a ile o i ual p ocesses acco ding o he esul s in he Map objec . A mapped a ay can only be used in o a pa allel sec ion. Selec ions o a mapped a ay uses indexes ela i e o he local index space o he pa assigned by he map o he i ual p ocess in he pa allel sec ion. The language suppo s a symbol o ep esen he las index o he local index space in a dimensional domain ($). In he Jacobi and Gauss example in Fig. 2, he inne pa o a ma ix (wi hou he bo de ows and columns) is selec ed. The language also suppo s a symbol o exp ess da a accesses using he index space o he o iginal ile (@). See an example in line 10 o he Classical ma ix mul iplica ion in Fig. 3. To pe o m he classical do p oduc mul iplica ion, we need he da a o he whole ow a A and o a whole column o B. We can exp ess da a accessed ela ed wi h he global a ay using he symbol @. 3.3.2 CMAPS Func ions CMAPS suppo s wo di e en kinds o unc ions, sequen ial and coo dina ed. Bo h will use a compulso y modi ie o he o mal pa ame e s ha makes explici hei inpu /ou - pu beha iou . These modi ie s will be used o de i e he dependencies be ween pa allel asks (guideline 6). All da a modi ica ion s a emen s should be encapsula ed in o classical sequen ial C unc ions, ha a e called om he coo dina ion code. Each call o a sequen- ial unc ion is done in a logical p ocess. The sys em could g oup se e al logical p ocesses oge he o build a single p ocess ha execu es he code in he co esponding unc ion calls c CMMSE ISBN: xxx-xx-xxx-xxxx-x Mo e on-Fe nandez, Ana e icien ly. Coo dina ion unc ions a e he unc ions whe e pa allelism and synch oniza ion can be exp essed. They a e speci ied adding he coo dina ion modi ie in i s de ini ion. Nes ed pa allelism is exploi ed by encapsula ing each pa allelism le el in a coo dina ion unc ion (guideline 1). T asgo allows o gene a e codes wi h se e al le els o pa allelism. Figu e 3 shows he implemen a ion o he wo ma ix-mul iplica ion algo i hms. Cannon’s algo i hm [12] can be used a he uppe le el o educe he memo y usage, and he classical one a he sha ed memo y le el o educing synch oniza ions ime. Making a hie a chical composi ion o he wo algo i hms in CMAPS is i ial. Simply subs i u ing he name o he sequen ial unc ion in he Cannon’s algo i hm (see Fig.3 line 38) by he name o he Classical’s algo i hm. 3.3.3 Coo dina ion p imi i es CMAPS suppo s in o he coo dina ion unc ions se e al kind o p imi i es. An uni ied pa allel p imi i e and i e a i e (loop,while) and condi ional p imi i es (i ,else). S a emen s such as assignmen s a e no allowed in he p edica es o he coo dina ion p imi i es. The loop p imi i e subs i u es he unc ionali y o classical o p imi i e wi h a es ic ed syn ax o ypical coun e -con olled loops (see line 17 o Jacobi sol e in Fig 2). The pa allel p imi i e pe o ms compu a ions in pa allel (guideline 2). The pa allel p imi i e ecei es a Map objec as pa ame e . I spawns as many logical p ocesses as indica ed in he domain used o build he Map objec and hey a e assigned o i ual p ocesses acco ding o he in o ma ion con ained in he Map objec . Vi ual p ocesses a e au oma ically scheduled o eal p ocesso s ollowing he policies used o build he Map objec . The p imi i e con ains do clauses. In hei scope we can w i e coo dina ion code wi h unc ion calls o be execu ed by he logical p ocesses (see line 20 o Jacobi sol e in Fig.2). They can be ollowed by op ional educe clauses. Each logical p ocess wo ks in a i ual copy o he iles. The ans o ma ion sys em is esponsible o gene a ing copies o da a pa s, and empo al bu e s, i needed o p ese e he pa allel seman ics; e en when se e al logical p ocesses a e mapped o he same eal p ocess, and consequen ly should be execu ed sequen ially in he same eal p ocess scope (guideline 5). The do clauses may be ollowed by wai low(...) clause o exp ess da a- low es ic ions. Fo example, in he Gauss-Seidel s udy case each logical p ocess needs o wai o he da a p oduced by i s uppe and le logical p ocesses (see line 15 o Fig. 2). The calls in he do clauses o a pa allel p imi i e can use wo ypes o indexes o build subdomains exp essions and selec he sub iles used as eal pa ame e s in he unc ion calls, ha lead o locali y. Fi s , pidx(<dim>), which is he dimensional index o he logical p o- cess. Logical p ocesses a e g ouped au oma ically in i ual p ocesses by T asgo amewo k, a oiding he p og amme o ake decisions abou he p oblem g anula i y (guideline 3). The second is midx(<dim>). The exp ession midx(<dim>) ep esen s he index o he i ual p ocess in he ac i e p ocesses opology in a chosen dimension. I is possible use he unc ion c CMMSE ISBN: xxx-xx-xxx-xxxx-x