Full text
DDT: A Research Tool for Automatic Data Distribution in High Performance Fortran EDUARD AYGUADE, JORDI GARCIA, MERC:E GIRONES, M. LUZ GRANDE, AND JESUS LABARTA Computer Architecture Department, Polytechnic University of' Catalunya, cr. Gran Capita s/num, Modul D6, 08034 -Barcelona, Spain ABSTRACT This article describes the main features and implementation of our automatic data distribution research tool. The tool (DDT) accepts programs written in Fortran 77 and generates High Performance Fortran (HPF) directives to map arrays onto the memories of the processors and parallelize loops, and executable statements to remap these arrays. DDT works by identifying a set of computational phases (procedures and loops). The algorithm builds a search space of candidate solutions for these phases which is explored looking for the combination that minimizes the overall cost; this cost includes data movement cost and computation cost. The movement cost reflects the cost of accessing remote data during the execution of a phase and the remapping costs that have to be paid in order to execute the phase with the selected mapping. The computation cost includes the cost of executing a phase in parallel according to the selected mapping and the owner computes rule. The tool supports interprocedural analysis and uses control flow information to identify how phases are sequenced during the execution of the application. © 1997 John Wiley & Sons, Inc. INTRODUCTION Data distribution is mw of the topics of curr<>nt IT- s<>arch in parallelizing environment~ for nonuniform memory an:t•ss (:\l 1!\L\) massiYt> paralld proct>ssors (MPP). In thes<> systems. each pro<Tssor has direct aut>ss to its local (or dost>) memorv and indirect access to th<> remote memories of other processors through the int<>rTonnection network. The cost of acc<>ssing a local m<>mon location can lw more than on<> ordn of magnit tJ<le faster than th<> cost of acct>ssing a remote men1ory location. In th<>s<> systems. th<> choice of a good data distribution can dramatically affect performance lwr:ausf' of the nonunifonnity of the nwmory system. H•·c•·i"·d \I:" I '19:; H<·yis.·d F.-ln:ll:trv 1 'I<J(J © 1 <)()'7 I" John \\ iln lx Sotb. Inc. Sci.-ntific l'ro~rammin~. \'ol. (J. pp. Tl-'J.-1 ( 1'N?) ( :( :(: 1 OSIJ-CJ:2+t/'1'7 /01 OOT~-~~ Several rest>archers havf' targeted tht>ir research pfforts to this topic. For instance, the Crystal con1piler and language project [1]. the implt>mentation ofPAH- ADIC.\1 [2] on top of Parafrase-2 and its continuation 011 tlw PTHA\ II mmpiln [:3] at IB.\1. the framP\\ork for the automatic determination of array mappin~s prt>sf'ntt>d in [4. 5]. or the automatic data-mapping strategy [ 6 J for usc in the D-programming euvironmcnt !'\IITf'ntly under dt>vclopment at Hice l :nivt·rsity arc t•xamplt>s of projt>cts iu this arf'a. Other groups have tar~f'tNI their efforh to the t>fft>ctivc compilation of programs containing the srwcification of the data mapping. such as the YFCS system [7] for tlw Vienna Fortran language [8]. tlw Fortran-D compiler [9] and language [1 OJ. or the cnrrcut conmu•rical cornpilt>rs (xi IPF [11 ]. PGHPF [12]) for High Performancf~ Fortran (HPF) [UJ. Automatic data distribution maps arrays into ttw physically distrihutt>d mnnories of the processors according to the array access patterns and para lit> I f'x.ccution of operations within computationally intf'nsivc
74 \\Cl'ADI~ ET ;\L. phase~. This mapping nm lw ~ither static or dynamic. In a static mapping. the layont of the arrays dews not changf' during the execution of the program; in a dynamic mapping. r~mapping opt>rations are performed in onlf'r to change tlw layout of arrays in different computational phasf's. \lost static data distribution methods [ L 2. -f. 1 "f. 1.)] perform thf' joh in two main independent steps: alignment and distribution. Th~ alignment stf'p triPs to relate thf' dimensions of thf' arravs used in a block of nHlf' with the dinwnsions of another arrav called tlw template (interdimf'nsional alignmf'nt ). and for each aligned dinwnsion. to find tlw appropriate shift hetwf'f'n their elements ( intradimensional alig111nellt). A good aligmrwnt willminimizP tlw overhead of intPrprm-cssor data mm·cment. The main differences lwtween the previous methods is the kind of st ructnrf' selected to n·prf's~nt the problt>m, and tlw way used to fonnulate and solvt> it. For the al igmrwnt step .. Li and Cheu [ 1] dt>finp and usc the Cornponmt Affinity Craph (CAC) to represent align11wnt prden·n<:f's. and it usPs a hf'uristic algorithm to solw it. Cupta [2] also uses the CAC .. but wt>ighted with data move11wnt costs. To do this. a default distribution has to lw assumed. This proposal is more accuratf' thau the previous one ,,·hen w~ighting the edges of the CAG, hut tlw solver is basf'd on the same heuristic algorithm.\\ holey [ 14]ust>s the preferem:e graph defined by [ 1 ()] in the franwwork of ~illgl~ inst ruction nmltiplc-data (SIMD) rnachinf's. This f!Taph irwludt>s alignment preferences to pr~scrve parallcli~lll.. but the rPsolntion \\hen tlw graph is in conllict is also based on heuri~tics. Schcfllcr et al. [4] define the alignment distrilmtion graph \\~hPrP nodes n•ptTsent program operations and edgt>s f"otmect definitions of array objects to thf'ir uses in tires~ operations. Edges are wf'ightcd with tlw numlwr of data items comrnunicatf~d along tlw edge. The alignnwnt is found using a grt>t·dy algorithm as a heuristic to detennirw the minimtun cost .. and applying graph contraction opt>rationb to rt>duce the complexity of tlw problem. Kf·Imedy and Kremer [ 1;)] design a framP\HJrk to he used i11side a data layout assi~tant tool for HPF. lt i~ bast>d on the CAC. and they solvf' the alignment pmblf'm using a 0-1 iutf·ger programming nHHlf'L thus avoidin;r tlw usc of heuristics. Onn· tlw alignrnent has been decidt>d. the distribution ~tep df'cide~ which dimension(s) of IIH' ternplatP arc distributed and the uurnLwr of processors assignf'd to each of them .. \ good distribution maxirnizPs tlw potential parallelism of the codf• and offers the possibility of furtlwr reducing data lllO\TnH'Ilt hy snializing. This goal could b~ tri\ially ~atisfit>d by assigning a datum to each JJJ"Ocf'ssor. whif·l1 maximize~ parallt>lisrn. Li and Chcu [ 17] match the aligned reference patterns with a predefined sPt of data mmernent routines. Each routine has an architecture-dependent cost parameterized in t~rms of the Jlllrnber of processors involved in thf' data motion and th~ amount of data being mov~d. The cost function for all the patterns is minimized hy selecting the appropriate distribntion strategy. Gupta [2] decides the dinwnsious to distribute (maximum 1\nJ dimensions). assuming a defau It mnnlwr of processors in Pach one and minimizing th~ total data movem~nt plus computation timf'. When more than mre dimf'nsion is distrihutf'fL he decides the number of processors to assign to f'ach dimension by generating all possible cmnbinations. Wholey [ 14] uses a hill climbing search m~thod \vhich initially assigns all array dements to on~ processor and f'stinwt~s tlw cost. Then it doublt> the munl_)('r of prof·essors and chooses the dinwnsion to assign the nf'w cmes. until all availablt' processors arf' ntilized or the total cost is not further n·duct>d. In large problems where differPnt computational!) intensive phasf's occur.. remapping actions between phases can increase the dfici~ncy of the solution. In this case. a good solution is indqwwkntly found for each phasf' .. and realigmnf'nt and/or redistribution statenwnts are inserted whf'rT m·ccssary. Data rf'mapping is also one of thf' topics in this suhjt>ct area of cmTf'nt research. Some of the proposals presented in the literature about array r~mapping [:'i. 13-20] art> ~umm:uized in the rest of this section. The D-System. currently under dt•vf'lopmcnt at Hice Lni\·ersity, considers the profitability of dynamic data n~1napping by exploring a st~arch space of reasonahlf' alignnH·nt a11d distribution spacPs [18]. In their work. each phas.o has a set of candidate mapping scht·mes. Selecting a mapping schenw for each phase in the entire program is dow· by n·prf'senting the problf'm with the data layout graph. Each possible mapping for a phase is rt>presented with a nodt·. Edges lwtween t\\O nodes in different phasf's n~present the n·rnapping that has to lw carrit>d out to execute each phase ,,-ith thf~ corresponding mapping. :\odt·s and edges have weights rt>prt>st·nting tlw on•ral cost of f'Xecuting a phase with mapping and remapping costs. respectively. in tnms of execution tinw. The problcrn is translated into a 0-1 integer progn11nmiug problem suitable to lw solved by a statf'-of-tlw-art gt>JH'ralpurpose intPgPr progrannning solver. Tlw FC:S system [1 f)] considers tlw proldt·rn in the franwwork of a data distribution tool for Fortran <)() source codt•o. ln this scO]H'. array-s~ ntax assignment statf'lllt'llts and \\~liE HE masks are f'Xamim·d to determine candidatt• data mappings. \ phase is basically a DO-loop cfmtaining array-syntax a~sigrn1wnt ,;tate-
ments or WT JERE masks in its body. Instead of lookinp: for tlw optimal solution. it uses a lre('-exhaustive algorithm with some heuristics to prune the search spacf'. A conflict table storing the conflicts lwtwf'en the mappings of the arrays from OTif' phase to tlw other is the basis of the n·mapping algorithm. This table determim~s which redistrilmtion options are worth considf'ring at t'11Ch transition. From this information. a tree showing all tlw different alternatives of remapping is built. Tht> aim is to determine the path in the treP with tlH~ lowest COb I. The fu 11 remapping tree can easily grow to intractahiP proportions. Chatterjet> el a!. [;)]usc a divide-awl-conquer approach to the dynamic mapping problem. Ttwy initially assign a static mapping valid for all the nodes and tlwn recnrsivPiy dividt> tht>m into regions which an~ assigned difft>rt'nl mappings. Two regions are merged wht>n dw cost oft lw dynamic mapping is worse than tht> static mapping, taking computation. data movPnwnl. and rt>mapping costs into account. Palermo and Barwrjcc [20] also usc a dividc-and-cmi<pu:'r approach in which the program is n·cllrsivt>ly decomposed into a hierarchy of nmdidatP phases. Then. takin!-( into a<:<'mmt thf' cost of remapping bel\\een the different phases. the scqtwncc of phases and phrb<' transitions with tlw lowPst cost is sPIPctt><l. Thev usc [2] to assign mappings 10 thP phases generated. Tht> Data Distribution Tool (DDT) is a research tool designed to generate hoth static ami dynamic solutions. Since it is a research tool. it can use tedmiqut>s that may lw too CO!tl£Httationall~ expensive to lw included in a final compiler; however. this allows ns to explore a rich set of solutions. The static modu!t· is based on the CAG hut Pxtended with somf' information regarding parallelism. W <'haw also modified the ori!-(inalalgorithmsin [1. l'?]toimprovcthe(IUalityofthe mappings generated [21]. The curn·nt version of the static module gt~Jwrates both inter- and intradimensional alignments and BLOCK and CYCLiC distributions. The dynamic llHH!ult> explores a rich sci of cmnbinalions: it is not ('xhaustivc thanks to mechanisms included to cut dmvnthc search space [22]. Tlw dynamic analysis is interpruccdttral and considers control flow to cktcnnine \\·here the rcmappin!-( actions havP to lw 1wrfonned (betW('f~n ('0111putational phast>s or across pron~durP houndari(~s). Tlw rt>st of tht• artidP is organized as follO\\S. In tlw JH'XI section\\"(' give an O\Trvin\ of the\\ hole datamapping process in DDT. Section :~ details how the static solutions an· found. Section-+ dt>snilws tllf' al!-(orithm \\·hich finds dynamic solutions and inserb remapping actions if they arc found proJitahle. Sections :) and () describe the nlcnsions to the previous algorithm to handle control Jim, and intcrprocedural anal- DDT: A RESEARCH TOOL 75 yses. respectively. In St>ction 7 we prese11t thf' main results from a set of experiments to test the validity and quality of the solutions generatt>d by DDT. Finally. Sect ion 8 gives sonw concluding remarks. 2 AN OVERVIEW OF THE DATA DISTRIBUTION PROCESS IN DDT Om research tool (DDT) analyzes Fortran 77 code and annotates it with a st't of HPF directives and execlltabiP statemt>nts that specify ( 1) !10\\~ a nays are alignt>d to a set of lt>mplate arrays and how the dimensions of these templates art' distrilmted among processors: (2) the sPt of rt>alignment and redistribution statPnwnts if thf' solution found is dynamic:, ami (:3) the parallelization strategies for the loops that access distributed arraYs. These decisions arf' done so that thP amount of rentolc accesses is rPduct:d as much as possible .. whilt> maximizill!-( the paralldism achieved. Tht> cxt('rnal shell of DDT is the intcrprocedmal analysis module: this module is based on the call graph for the Pntire program. ln a bottom-up pass over the call graph. each proccdun~ is analyzNi when all the procedures called by it haYt' already been processed. "\otin· that Fortran 77 docs not allow rPcursion. so 110 cyclt>s can he found in the call graph. From the analysis of a procedure. a set of candidate mappings are generated for it and stored in the DDT interprocedural database. For each procedure. DDT can generate two diffPrenl kiJH!s of solutions: static and dvnamic. Static solutiom define an initial mapping for each array. and it does not change during the execution of the whole procedure. In a dynamic solution. tfw statements in tlw miginal source code are grouped into a ('ollcction of phases: each one nwy have different mappings for the arrays at't'f'SSPd so remapping operations might be nPt·essary to ext>cule each phase "·ith its mappirt!-(. i\otice that static solutions are a particular case of dynamic solutions wlwre no remapping operations arc needed. A phase is either the outPnnosl loop in a nest wiJOst• control variable is used to subscript au array or a call to a procedun·. If tlw phase is a loop rw-;t. the candidate ntappinf!s for it are obtained by performing an analysis of rPff'rt'IH'P paiiPnts within the 1wst. If th(· phase is a calL the candidate ntappings art' imported front tlw DDT interprocedural database. The contml flow module guides tlw g<'JH'ration of all possibiP sPqm·nces of phast's for t•ach procedure. DDT is targeted to !-(t'IIPric J\l .\L\ architectun's with local and remo1t' ac<Tsscs. Each processor has its owntnemon· hierardtY and can access the nwmoriPs in . .
76 AYGU,DJ;: ET AL. other JH'occssors through the interconnection network. Data movemrllt costs are estimated as the numlwr of remote accesses multiplied by the remote access time. Given a parallelization strategy. computation costs are f'St imated from a profile of tlw seqtwntial execution on a worksta1ion based on the same proet>ssor and with the same memory hierarchy than tlw parallel machine. Profiling tlw srquwtial f'Xeeution of the original Fortran 77 program is requirPd in onler to obtain some problf'm-speeifie parameters. such as array sizes. the number of iterations for the loops and tbeir executiml time.. and tlw prohabilities of the different branches in conditional statements. There exists a configuration file that allows the user to specify sonH' machine-specific parameters (number of processors. overhead of parallel thread creation. local and remote memory access costs, and so on) and restricts the kind of solutions exploreci by DDT (number of distributed dimensions .. static or dynamic solutions, number of eandidatt> mappings for the phases and procedures. and so on). All cost estimations in DDT are dmw numerically assuming the above-mentioned problem and machine-specific parameters. 2. 1 An Example: Alternate Direction Implicit ln this Sf'ction we introduce the Altemating Direction Implicit (ADI) integration kernel to show the main features of the DDT intraproccdural data-rf'mapping HHHiule. The source code of ADI defines a !\Yodimensional data space of size 256 in each dimension: it ha~ a sequenee of loops that initializes tlw data space followPd hy an iterative loop that perfor111s the eomputatiom. In each iteration of this loop. forward and backward sweeps alontr rows and collUnns are done in sequence. In this example. and for simplit~ity .. DDT only ronsiders mw-dimensional distributions:. we have also set the eonfignration file ;;o that llw overhead due to parallf'l Pxecution is zero. remote aceess!'s take 1 J.LS per byte. and the parallel machine has 16 proccs,;ors. The source eode is shown in Figure 1 for completeness. DDT identifies nine plias<~s in this program. Each phase corresponds to one of the nested loops (labeled fmm 1 to 9) in Fi~ure 1. For each phase. DDT estimates the data movement and the execution costs for different data-mappi11g and loop parallf'!ization alteruative;;. For inslance. while analyzing phase 4. the two possihle mapping" shmvn in Table 1 are taken into account .ln this case, DDT suggests a perfect alignnwnl of all the arrays used in the phase and two possiblr· distrilmtions: (BLOCK, *) and(*. RU)CK). For the first time, DDT also suggests to parallelizP the outer program adi double precision x(256,256) double precision a(256,256), b(256,256J do 1 i 1, 256 a{i, 1) = 0.0 b{i, 1) = 3,0 x(i, 1) = 4.0 continue do 2 j do 2 "" 1, 10 C AD1 backward sweeps along rows = 2' 256 ;:: 1~ 256 j} = x{i, j} - x(i, j 1) "' j} = b(i, j} - ali, j) "' a{i, 256 ) I b(i, 256 } Phase 1 Phase 2 Phase 3 Phase 4 b(L j 1) j - 1} Phase 5 = 255 , L -l Phase 6 i = 1' 256 x(i, j) = (x(i, j} - a(i, i + 1) * :x:{i, j- 1)) I b(i, j) 6 continue C ADl forward & backward sweeps along columns do 7 j "' 1, 256 do 7 =- 2, 256 j) - x{i, j) ~ x{i j) "'b{i, j) - a(i, a(i, j) I bl256 , j) conti::1ue Phase 7 b{i - 1, :i) - 1, j) Phase 8 do 9 j = 1, 256 Phase 9 do9i=255 -1 x(i, j) "' j) - a(i + 1, j) * x{i + 1, j)) 1 b(i, j) 9 continue 10 continue end FIGURE 1 Sonrce eode for ADl. i loop sinee there an~ no data dependencies preventing the loop from running in paralleL For the S<'eond altt>rnativt~. the depe!Hlence in the second dimension of arra\'S band :t· forces DDT to sequt,ntialize the execution of the j loop. For each alternative. an estimate of the data movenwnt costs is performed by matching refen·nee pall ems within the phase with a predefined set of data movement patterns. The computalion time of a phase with a parallelization strategy is estimated from the profile of a setjuential execution. For in- ;;tance. the f'Stimation for phase <-± concludes that three shift-like data movement pattern~ appear due to trw accesses to arrays .r and b when the second dimension is distributed (each shift movcnwut in- Ynlves a t·olumn of an arTay. i.e .. :2;)6 elclllellts or 2.048 byte). The profile for this phase reports a sequential execution rime of o.:3S292:J s. which is the cost for Solution 2. However. the computation cost for this phase with Solution 1 is estimated as 1 I 1 () of this sf~quential execution time plus the overhead due to parallel thread creation (zero in thi;:; example). The first row in Table 2 shows the data movt'ment and computation time::; estimated for pha;,;e <-± for the two solutions evaluated by DDT. From the analysis of the different possible mappings for a phase. n SPI of them are ~dectf'd as candidate 111appings (this selection is done based on cost
DDT: A RESEARCH TOOL 77 Table 1. Array Mapping Alternatives and Associated Loop Parallelization Strategies Analyzed by DDT for Phase 4 in ADI Array \1apping Loop Parallelization Solution 1 CHPF$ TE\1PLATE targct(256, 2;)6) CHPF$ ALIGN WITH target::x. :L b CHPF$ DISTRIBCTE target(BLOCK, *) CIIPFS INDEPENDENT DO 4 i = L256 DO 4 j = 1.256 Solution 2 CHPF$ TEMPLATE target(2.S6, 256) CHPF$ ALIGN WITH target::x, a. b CHPF$ DISTRIBUTE target(*, BLOCK) DO 4 i = 1.256 DO 4 j = 1.256 criteria). Once they are selected, an algorithm to check the compatibility of phases is used; we say that two phases are compatiblt> when they have preferences for the same data mappings so no remapping is required when sequencing from one phase to the other. For instance, consider the sequence {4, 5, 6} of phases. From the source code in Figure L one can see that these three phases have the same preferred mapping (BLOCK,*) and loop parallelization strategy (execute the i loop in parallt>l). Similarly, ont> can conclude that the preferred mapping for each phase in the sequence {7, 8 .. 9} of phases is(*. BLOCK) and the parallelization of the j loop. Table 2 shows the costs of the candidate mappings for all the phases within the iterative loop do iter. Table 2 shows that the favorite solution for phases {4, S. 6} and {7. 8, 9} is not the same. Therefore, they are not compatible in their mapping and parallelization strategies. Three main alternatives are evaluated by the intraprocedural algorithm: 1. Assign Solution 1 to all the phases. In this case the cost per iteration is 0.5479-H and the t>stirnated cost for the outer iterative loop .5.47944. 2. Assign Solution 2 to all the phases. In this case the cost per iteration is O.S7:'i59 and the estimated cost for the outer iterative loop 5.7559. 3. As~ign tht> preferred solution to each phase. Tn this case the computation time is 0.061886 and we have to remap the arrays betwcen inrompatiblt> phases. In particular, arrays a, b, and x will be remapped from row to column distribution before the execution of phase 7, which has an approximated cost of (2.56 * 256)/16 = 4,096 array clements each (or 32,768 byte each). This remapping action is performed 10 times during the execution of the iterative loop. Due to the same loop, phase 4 is executed again after executing phase 9. So we have to consider the compatibility between these two phases and the pos- ~ible remapping costs if their mappings are not compatible. In particular, arrays a, b, and x have to be remapped from column to row distribution before the execution of pha~e 4 with the same estimated cost. This remapping action is performed nine times ( ~ince the last iteration of the iterative loop forces the t>xecution to t>xit it). The total cost for the sequence of phases within the iterative loop is estimated as: (10*0.064886) + (10*3*0.0:32768) + (9 * 3 * 0.0:32768) = 2.5166:36. In this t>xmnple, the cost of the dynamic alternative is lower thm1 the costs of the two static alternatives. In Section 7. Wf~ analyze and evaluate the validity of the different solutions when changing architt>ctural parameters such as data movement and thc number of processors. Table 2. Data Movement and Computation Costs (in seconds) for Phases 4 through 9 in ADI for Two Candidate Solutions Phase ;J (J 7 8 9 M ovem Pn t 0 0 0 0.0061-t-t 0 0.0040% Solution 1 Computation 0.022058 0.000212 0.01109;) 0 .. '32-tS(J:=i 0.002261 0.177;)13 Solution 2 Movement Computation 0.0061 +± 0.332£)25 0 0.0():3:391 0. 00-tO% 0.177-)Ll 0 0.020285 0 0.000 1-t 1 0 0.01109:)
3 DATA DISTRIBUTION FOR A PHASE The basic compilation stcps for a computational pha~e an~ dc~cribed rwxt. First of all. a weighted graph called the Dimension Alignment Craph (DAC) is constructcd from the analvsis of thc array reft>n•nces in tlw source . . program and it records preft>rt>nct>s for alignment. The DAC is similar to the CAC hut it indudcs preferenccs for aligmrwnt based on parallelization in addition to data lllOYt'IIH~nt. Tlwn, an array alignment phase follows. In thi~ ~t<>p. all dimensions of the arrays in tlw program are rclated to each other by ( 1) mapping each array dimcnsion into a dimension of a template array (intenlimensio11al alignment) and (:Z) applying an offset between 1 hem (intradimensional aligmncnt). Data movement requirements for those nonaligned refert>nct>s and loop parallelization strategies are analyz<>d in order to deci<k the dimensions of the templat<> to distribute .. the numlwr of JH·oct>s~ors allocatcd. and the kind of distribution applicd to them. 3. 1 Reference Patterns and the DAG Tlw DAG is a 'wighted undirected graph built from the analysis of array reference patt<>rns in loop statemenh. In this section we rev in\ how rt>ference patterns arc defined and analvzt>d to detect affinitY. and how . . the DAC is built from this analv~is. Reference Paffern Analysis and DAG Building The analysis of reference patterns is perfonrwd within tlw scop<' of rwsted loops. A refere11ce pattern is detined in .. II, ..... i,) ~ !J(j, .. . .. .f,r· .. .. j,). wlwrc /1 is an array that appears in tlw left-hand sidt> (!hs) of an a~signment statement locat<·d insidt> the loop and B i~ an array in tlw right-hand sidt> (rhs) of the same assignment statemcnt. lf the assignment is under control of conditional statements. then all tlw arrays in thc cxpr<>ssions that e\·alnate the conditions an· nmsiden·d as if they wert> in the rhs of tlw assignlllt'IIt statenwnt. ,\n affinity rclation can appear bet\n'<'n t\vo dinwnsions of the data arrays in a reference pattf•rn. Dinwnsiorl R, 1 is said to lw aftinc with dinwnsion A1 ,( denoted ("1 1 ,. R,)) if j, 1 and i1, are linear functions of tlw ~a me loop control variable. From the analysis of referenct' patterns. tlw D"\C is lmilt. \"odt>~ of the DAC rcpn·,;ent dinwnsions of data arrays and edges r<>prcscnt affinity relation~ lwtween array dimensions obtained by exam1111ng erossrt>fercnce pattcrn~ (patterns in which the rfts and lhs arrays are different). Self-reference patterns are not considt>red in the DAC building step. 1\odes in the DAC are grouped in columns; each column contains those nodes representing dimensions from tlw same data array. An edg<> (4 1 ,. B,) in the D\C sho\\·s a preft>n·nce for alignment of dirrwnsions AI, and n,l. According to [1]. edges in tlw DAC are weighted in two ways. On the one hand (and to solve tlw intt>nlimensional alignment problem) .. each edg<> is \\Tighted depending on whetlwr it is competing or mmcom peting with another edge ( e if it is compcting and 1 if not). Tw~o edges are said to be competing if the~ arc generatt>d by the same reference pattern and are incidt·nt on the sanw node. A DAC so <lelined rnay contain multiplt> edges betw~een a pair of node~ since there might he several r<>ft>n·nce pattt·rns involving t \\ o data arrays: each set of multiple t>dgt•s caJI he rcplact>d with a singlt> t>dge \\hose w~eight is the sum of tlwir \wighh. On tlw other hand (and to soh-e tlw intradimensional aligmncnt problem). each edge is weight<·d with the offset between the two subscripts in the array dinwnsions innJlvt>d. ln tl1i~ case" multiple edges art> not mcrged into a single edge lwca use each 011e may store information ahottt a differcnt shift preference. Prefer- Pnces for stride alignnwnt arP not reconlt•d in tht> DAG in tlw <·nncnt version of the DDT. DDT abo perform~ a set of wdl-knmn1 optirnizations such as cxpression substitution. subscript substitution. and imluction variable detection. In [2] the authors evaluate the effectiveness of these optimizations in terms of amount of llt'W reference patterns analyzed and affinity rclation~ ohtairwd. They also analyz<> the complexity of the DAC in real code~ 111 terms of numlwr of node~. edges. and offscts . 3.2 Including Parallelization Constraints in the DAG Loop paralldization 1s not independent of tlw way arrays in the phase are aligned and di~trihuted. It would he interesting to have a dt>ar relationship betw·<>en loop levcls in a ph as<> that is parallel ized and dimensions of arrays that arc aligned and distributed: this nm cas<' the application of tIre owrwr computes rule and of a more t>ft1eient generation of parallel code. For each loop in a phase eligible for paralld execution (according to dqwndcnce analysi:;). a set of edgt's linking dimensions of array~ (in tfw lhs of a~sigmrwnt stat<>ments) ~uhscriptcd by its loop control variable art> added in tlw D"\C. :\"ote that these <'dges arc differ- PHI than the indqH·ndt>nC<' antiprcfcn·nce edgPs delined in [16]. Tlwy characterize potentially paralleli-
1 cr==;== FIGLRE 2 DAG for plHN' 4 in \Dl including affinity all(! parallf'lization edgf's. zahlf' dimensions of arrays (in both sidt>s of the assignment statements) if the subscript is not a scalar. In ottr DAC. tlw edge'i record pref<:>rf'nccs for alignnwnt of tfw dimensions that arf' accessed by a loop eligible to be paralldizcd. For instance .. consider phase -l in the ADI program in Figm<:> 1. If the alignment and distribution for arrays x and b were the following: !HPF$ TEMPLATE target(256, 256) !HPF$ ALIGN x(i,j) WITH target(i,j) !HPF$ ALIGN b(i,j) WITH target(j,i) !HPF$ DISTRIBUTE target(BLOCK,*) then there would not he an easy paralldization strategy for the loop nest. According to the owner computes rulf'. tfw lhs of the first assignment statenwnt suggc~h a parallclization of tlw i loop \\bile the st•cond one suggests a parallelization of the j loop. If the rule is brokt>n in one of the two statements. additional data mon•rncnt arises. Figure 2 shows the DAC for phasf' 1: in ADT. Notice that in addition to the edgeb that show af!lnity lwtwf'Pn dinwm;ions in array r<:>f<:>r<:>nces (thin edg<:>s (.r1• a1 ). (.1·". a'!.)· (a 1• b1 ). (a". h"). (:r1• b1 ). and (.r". b")). a rww edge betwe<:>n (.1· 1• b1) is added. This edge lws a wf'ight big <:>nongh to ensure that tlw D.\C partitioning algorithm described in tlw nf'xt section will align all the nodes linked by it. 3.3 DAG Partitioning and Array Alignment Two probl<:>ms arc faced wlwn solving the array align- IIH'Jit stPp. First. tl1e int<:>rdimensional aligmrwnt probl<·m tries to deride l10w array dimensions are aligned into the dimensions of a common template array. This tctnplate has dimensionality <:>qnal to the larg<:>st di- IIWJJsionality of' all the arrays analyzed. Each dimension of each array is aligned \\itl1 a dimension of the tf·mplatc. S<:>nmd. the intradinwnsional aligrnnent problem tries to decide how all the array dimensions aligned into a dil!H'nsion of tlw template arc shift<:>d DDT: A RESEARCH TOOL 79 f'ach other. Although thi!-i includes offset and stride aligmrwnts and reflections (stride -1). only offset alignments ha\'e be<:>n implemellt<:>d in the CliiT<:>nt Ycrsion of DDT. lnterdimensional Alignment Civen a DAG G. the intenlimensional alignment problem can be btated as follows [ 1 J: Let n be the ma.rimum nwnber r~( nodes in a column <d' G. Partition the node set ~~l G into 11 di.~joint subsets T1 ••••• I 11 • !l'ith the restriction that no tu·o nudes belonr:ing· to the sanu' data arra.1· are allo!l'ed to be in the sante subset. :-.Jodcs in the same subset correspond to dimension' to be aligned. As a consequence. we want to partition tlw DAG so as to minimize tlw total weight of edges that arc between nodes in diff<:>rPnt subs<:>ts. The problt>m .c;tatcd abow is :\P-complete and [1 J propose a lwnristic algorithm (greedy) to soh·e it. In this algorithm. a single data array is ramloruly dwscn at f'ach step for alignment with the ternplatt> (which is chosen among the data arrays that haY<:> maximum dimensionality). The algorithm appli<:>d to a graph G is dt>scrilwd below: C, = Choose_Template_Column(G); while (not_empty(G)) { Cx = Pick_Up_Column(G); G, = Form_Bipartite_Graph(Ct, C,, G); M Optimal_Alignment (G 2 ); G = Reduce_Graph(M, C,, C"G); In t>ach iteration of the abov<:> loop. the aligmnPnt bet \\Ten thf' data array corT<:>spmHI ing to column C,. and the data array COITt'SJHHHling to tlw tt>mplate column C, is decided. The main steps of the heuristic arc d<:>scribed below: 1. Fomt_/Jzjmrtite_Gr(qJ!t. a graph(;" <·omposcd of the nodes in the two cohunns C, and C, is built. An edge is placed between two nodes in the bipartite graph G'!. if there is a path IH'tw<·en tlw two original nodes in tlw DAC. Tlw weight of the edge is the stun of all edges that compose the path.lf scycral paths appear. tlwn tlw \\Tight is st•t to the sum of all the edg<:>s that cornJHN' the patb. 2. Optiltla/_A/ignmellt. For <:>ach bipartitP graph G2. align dimensions of C, with dinwnsions of C, so that the total weight of <:>dgt>s not aligned is lllllllllllllll.
80 A YGUADE ET AL. (a) (c) • • (b) (d) FIGURE 3 ~lin-cut vs. Sum in Form_Bipartite _Graph. :~. Reduce J)raph. Merges column C, into C,, replaces multiple edges between two nodes with a single edge whose weight is the sum of their weights, and (lt•letes all self cycles. ln our implementation, several optimizations in the lwnristic have been done in order to obtain better alignments. They are described below: 4. In Fonn_Btjwrtiff'_Graph. the weight of an cdge betwcen two nodes is set to the min-cut instead of the sum of the weight of all edges that compose the paths. With min-cut, the weight is set to thc minimum sum of edge weights in G that we had to eliminate to isolate the two nodes. This represents the minimal cost of not aligning tlw two nodes. For instance. consider the DAG shown in Figure 3a (it corresponds to procedure THED2 from the ETSPACK library). Figure 3b shows a step of Fomt_Ripartitt>_Gmph when a path bctwcen T2 (of C,) and Z1 (of C, in the step) is looked for. ln this case, there are two paths: T2, D1• Z1 and T2• TJ1 .. E1. Z1. The bipartite graphs obtained using the original [ 1] and the min-cut proposals are shown in Figures :k ami 3d. rt>spectively. Optirrw/_Alignment would align (7'1, Z2) and (T 2, Z1) in Figme 3c (with six an:s to communicate) and (T1, Z1) and (TJ.. Z2) in Figmc 3d (with one arc to communicate). The solution obtained with min-cut is better than the other solution and better reflects the actual data movt>mf~nt requirements. !1. Pick_{ /JJ'olumn chooses a column C, among all the columns in Gas the column that is more critical in the alignment process instead of an arbitrary column. To decide how critical a column is. we inspect edges between the template and each column in G. For instance, consider the same example in Figure :3. Once Optima/_ Alignment and Reduce_Graph have been done, the graph shown in Figure 4a is obtained. If we pick up column D, the difference between the two possible alignments ((7'1. D1 ) or (7~, D1)) in the number of communicatio11s is 1. On the contrary, if we pick up column E, the difference is 2. So in this case, it is more critical to first solve the alignment of array E rather than array D. Figures 4b and 4c show the difference. The algorithm used to decide that the next column is outlined below: for each Cx in G { G2 = Form_Direct_Bipartite(C,, c •. G); dif (x) = WorsLAlignment (G,) - Best_Alignment(G 2 ); c. Find_Maximum(dif); Function Form_Direct_BipartitP returns the bipartite graph between two columns in a graph that results from direct edges. Functions Rest_Alignment and Worst_AfignmPnf return for a bipartite graph the total weight of nonaligned edges with the best and worst possible alignments. The use of min-cut incrt>ases the execution time of the algorithm with respect to the sum alternative. However. the use of a heuristic to choose the next column decreases the execution time of the min-cut solution because at each step, the complexity of the remainina ara1)h is lower and the algorithm proceeds bb faster. In [21] the authors evaluate the usefulness of these optimizations oriented toward improving the output of the DAG partitioning algorithm. Intradimensional Alignment The algorithm we propose to find shifts among aligncd dimensions is described next. For each dime11sion of the template, a directed graph G, is creatt>d. ~odt>s in this graph correspond to array dimensions that are r 2 Dl ~:1 Tl 7 Dl 4 • T2 (a) T2 (b) T2 (c) FIGURE 4 Heuristic to choose a IH'W column in dw graph for alignment. (a) lntermPdialP graph. (h) Bipartite graph widt domain E. ((')Bipartite graph with domain D.
aligned with a dimension of the template. Edges in G, are the subsct of edges in the DAC bct\\een the nodes aligned. In this graph, edges arc weighted with the offset lwtwet>n thc two subscripts in the associated rderTnce pattt>rn. The algorithm implt>mented is: for each dimension i of template { G, = Obtain_Directed_Graph(G, i); Mark_Template_Node(Gxl; while (noLalLmarked (Gxl l{ N = Pick_Up_Node (Gxl; S = Find_Shift (G" N); Gx = Apply _Ret iming ( G" N, S) ; Mark_Node (G" N); This algorithm is basically the same than the one proposed in [23] to solw the statement alignment problem in order to reduce synchronization costs in a shared memory execution model. The main steps of the aigorit Inn are dcscrihed helm\: 1. Pick_fjJ_c\'ode. Tt returns an unmarked node of G, corlllected with a marked node of G,. If such a node is not found. then an unmarked node is randmnlv sclected. 2. Fin(L)h[fi. This function returns the offset S (with rcspect to the template) that hm; to be applied to the node"\' currently analyzed. This valm· is obtained from the offset of all the edges lwtwee11 node ;V and any marked node of G,. If sevcral edges het\\Ten nodt> ,y and tfw template nodt· appear. the one that is rq)('ated more times is selected. If several edges are candidates. then the one with minimum value is chosen. \Vt' ha\'e observed that selecting a value different than zero when zero is one of the candidatcs leads to poor solutio11s. . ). App(J·_Hetiminp:. The idea of retimi11g as described in [24] is applied in this function. Tlw offst't 8 obtained in thc previous step is suhtractt·d to all incoming arcs into 11ode N. and added to all outgoing arcs from node Y. At thf' e11d of the algorithm .. each node in G, has an associated shift with respect to the template node. If G, is acyclic. a perfect intradimensional align- I!Wnt results. In this cast~. all the edges are aligned and no data movement is needed. If cyclf's are present in C,, then some t>dges may not he aligned and therefore. data mo\'ernent may be required for them. DDT: A RESEARCH TOOL 81 Table :3. Communication Houtines and Their Matehing with Reference Patterns Routine [,oral _/vlemul") ·_A rcess Cop}· Shift One_toA/1 /1/l_toJJne 41/_((i_.'t/1 Pattern i,l = .1~1 const(i") A const(;;,) const(i1, ~ j,,) CO/ISf(J;,) CUI/Sf(i 1 ,) i,, #.if' 3.4 Communication Analysis Once data arrays are aligned. each reference pattern that is not aligned (inter- or intraeomponent alignment) after the previous phase represents data movement that has to be carried out. In this phase. a matching of reference patterns to a predefint>d set of data mmcment routines is done. In the cmTent impbnentation. DDT considers simplt· data move1nent routines (routines that perform data movement in a single dimension of the template). If the refert>nCf' pattern requires data movt>ment in more than onc dimension. then the reference pattern is decompo.~ed into subpatterns and each subpattt>rn matched with a single data movement routim~ ( cach one performing data movf'IIH'llt in a single dimcnsion of the arrays). For each reference pattern (or subpattern if denunposed). the data movement routine that performs the data movement with les~ cost is chosen. Table 3 shows the st·t of data movement routint's considered In DDT and ib matching "~ith reference patterns. In this table. p is the dimension whne data mm·t·ment takes place and i1, and j" are the subscriph in the dimension p of the reference pattern. Function const(P.lp) returns true if e.rp contains constants only. The matching bet ween data movement routines and n·f,rTJHT patterns is performed in order to obtain an estimation of the oyerhead due to remote acccsses . Each data mon·ment routine has an estimatcd cost. This cost is dependent on the architecture of the system. the size of the block of data to be transfered. and the number of processor,; involved in the data moyement. The size of the block R is estimated hY DDT as follows: , dim, . H =.')X IT ---y- X pos(\, ~ 1) t#p ' I S represt'nts the numlwr of elements moYed in the dimension p where the data mm-rnH·nt takes place. S, is the number of processors allocated to dimeusion i
88 AYGliADE ET AL. program shallow call inital Phase 1 call calcl Phase 2 call calc2 Phase 3 if (ncycle .le. 1} then call calc3z Phase 4 else call calc3 endif end (a) Phase 5 (b) FIGURE 7 (a) Outline of the main program in the SPEC swm256 benchmark. (b) Control flow graph. invariant. As a result, a single mapping for phase 4 is selected according to the previously fixed mappings of phases 1, 2, and :~. 61NTERPROCEDURAL DATA DISTRIBUTION The main aspects considered in the interprocedural data distribution analysis performed by DDT are described in this section. The algorithms used both for static data distribution or dynamic redistribution in the case of interprocedural analysis are basically the same as those used for the intraprocedural case. The definition of phase is extended to consider some procedure calls as phases, besides the loops as described in Section· 4. lf the procedure call is outside a loop which is considered a phase itself, then the procedure is considered a phase. Otherwise, some information obtained from the previous analysis of the called procedure is used to estimate the effects of the mapping of this procedure while deciding the mapping for the phase. The analysis is based on the call graph in which nmks represent procedures and edges represent call sites. This graph contains representations of the fonnal and actual parameters and their dimensions associated with each procedure and call site. It is traversed bv DDT to decide the order in which procedures will be analyzed. The approach that has been considered is a bottom-up traversal of the call graph: Those procedures that are deeper in the call graph are analyzed first. This bottom-up traversal ensures that when a call to a procedure is found then it has already been analyzed, and therefore the information for that procedure is already in the interprocedural DDT database. When a mapping specified for a dummy argument or global variable differs from its actual argument or global variable, liPF requires implicit data redistribution and/ or realignment. Additionally. upon return to the caller program, the original mapping must be reestablished. So two possible remappings for each argument and global variable should be considered. Other programming models based on HPF, such as the one offered by FORGE [11], allow you to leave an output mapping different than the input one. In this case, the information stored in the internal DDT database after deciding the mapping for the procedure will be its initial and final mapping (in addition to the realignment actions performed inside it and its execution cost with the selected strategy). Notice that this later model is a generalization of the definition of HPF. DDT actually supports both alternatives. A procedure may have several candidatt> mappings stored in the interprocedural database. lf different mappings are preferred in different invocations of the same procedure, then procedure cloning is applied in order to ge1wrate versions of the same procedure with different mapping and parallelization alternatives. 6. 1 The Procedure Call is a Phase A procedure call is considered a phase when it is not placed inside a loop tagged as a phase. The remapping algorithm used in this case is mainly the one described in Section 4.1. However, function GerwrateJJocaL Mappings reads the internal DDT database in order to obtain the different candidate mappings for the called procedure, instead of computing them from scratch. Phases due to procedure calls have candidate mappings composed of an initial and a final mapping. In this case, the cost of remapping will he determined by the mapping differences between the actual global mapping and the corresponding initial mapping for the phase. However. after the exeeution of the phase, the global mapping will be updated with the final mapping. This means that when generating different permutations of the local mapping in order to estimate different realignment options, both the initial and the final mappings should be permuted. This analysis could be extrapolated and used to analyze any kind of phase (loop and call), assuming that the local mapping for a loop has the same initial and final mappings, whereas the call has its corresponding initial and final mappings. The next example is used to illustrate the aspects described above. Assume that some phases of a procedure have been analyzed, and that at this point the global mapping GA1 1 contains the following information:
A 1/i(-t) 2n(-tJ Ul!,: R 1/1(-t) 2/1(-l) c 1/i(-!J 2/1(-t) D 1/i(-t) 2n(-tJ This means that in the global mapping GM,. all arrays u~ed lwforf' that phase are perfectly aligned. and their first and second dimensions arc distributed with four processors assigned to each onf'. Assume also that the next phast' to be analyzed is a proccdurf' call whose local mappings in L!H,+t (obtained from the interprocedural database) are the following: A 1/1(-t) 2/i(-t) Initial LM,+t: R 2/i(-t) 1/1(-t) c 2/i(-t) 1/1(-t) E 2/i(-t) 1/1(-t) A 1/i(-tl 2/i(-t) Final LM,+t: n 1/i(-!J 2/i(-t) c 1/i(-!J •) ~!i(-!J E 1/1(-t) 2/1(-t) \Vhen analyzing this phase .. arrays used in this phase must be tagged according to the distribution differences between thf' global mapping and tlw initial local mapping. \\'e can see that array E is new .. so it will be included in the global mapping with its desirf'd distribution (note that it will also be included in the initial mapping for this procedure). Arrays 11. B. and Care candidates to be realigned. Two different alternatives should be nmsidf'rcd: to keep array A as it is and realign arrays Band C:. or to keep arrays Band C as they are in the global mapping and realign array A. ln order to update the global mapping GM,+ 1• tlw final local mapping is thf' one that must be takf'n into consideration. This nwans that if the first alternative is selected. array A is hpt as it is in the global mapping awl neither the initial local mapping nor the final one is transprbetl So the global mapping will remain: A 1 /1(-t) 2/1(-t) n 1/1(-t) ') ~11(-tl c 1/1(-t) 2/1(-t) [) 1 /1(-t) 2n(-t) E 1/1(-t) 2/i(-t) DDT: A RESEARCH TOOT, 89 But if dw second alternativf' is sclf'cted. then arrays B and Care kept as they are in the global mapping so both the initial and the final local mappings are transposed. In this case the global mapping will be: A ') ~/1(-t) 1/1(-t) n ') ......,H(-t) 1/1(-t) c 2/1(-t) ] /1(-t) j) ] /1(-t) 2/1(-t) E ') ~/1(-t) lfl,.-t) 1\ote that tlw mapping for all arrays ( f'xcept for TJ) in GJf,+ 1 in this last alternative is diffPrTnt ( transposPd) from their mapping in GJJ,. and apparently only array A has been realigned. Attention must be paid to the local mappings of phasf' p,+1• The difference between the iuitiallocalmapping and the final one mt>ans that. at least, arrays R. C. and/) have been rt>aligned inbide tl1e pnlcf'dnre. and thus their cost has already het>n assnnu•d within the cost of f'Xf'Cnting the procednrc. lf the first alternatiw is selected, then arrays Band C are realignf'd lwfore the procedure eall aud inside it as welL so the G/v/,+ 1 remains unchanged with rt>spf'ct to GJ!,. At this point it is not possible to say which alternative is the best because it dqwnds on the phases not yf't analyzed. so the analysis must continue with the two alternatives. 6.2 The Procedure Call is Inside a Phase When the fH'OCf'dure call is placed inside a loop which is tagged as a phase. theu the call is not considered a phase. ln this UlSf' .. the initial and final mappings assigned to the procedure may affect the choice of tlw candidate mappings for the phase. When a call statement is found, DDT imports from the intPrproccdural DDT database all the information associated to each possible mndidate mapping for the called procedure. Dnring the aligument step, when a call statement is found, DDT imports from thf' corresponding file in the interprocedural DDT database the information regarding ALlGJ\ directives for the global variables and the actual parameters. This information is included in the DAG of the phase as additional cdgf's. ln fact. this is an approximation to the problf'nL A more accurate model should have to weight these ne\\' edges with its corresponding realignment cost. During the distribution step. and for eac:h eall to a procedure. the global variables and the actual parameters must lw remapped (if necessary) before and after
90 AYGUADE ET AL. list files Static evaluation reports Dynamic evaluation reports FIGURE 8 Main components of our automatic oat a distribution platform: DDT. xHPF compiler. ano simulator from APR Inc. tht> call. The mapping that minimizes tht> ovt>rall cost including remapping is selected among the candidate ones. 7 EXPERIMENTAL RESULTS The main components of tht> data distribution cnvironmt>nt we are using and developing arP shown in Figurt> ii. Our research tool (DDT) is implt>mented on top of Para Scope [2;)] and assmnes st>quential programs \Vritten in Fortran 77 as input. DDT parses tllf' input emit> and annotates it with a set ofiiPF directives and t>xecutable statt>ments. The xHPF compiler from Applied Parallel ResParch [11 J is ust>d to compile the program generated by DDT and to generatP a single-program multiple-data (SPMD) node program using PVM3 communication primitives [26 J. The xHPF execution model allows us to simulate the execution of the instrumt>ntPd code generated by xHPF on a singlt> workstation. This sirrwlated execution is used to pt>rforrn comparisons of the performance of differt>nt data distribution strategies and to validate our proposals. We haw analyzed thrPe programs: ADI (shown in Fig. 1 and analyzed in Section 2), routine RHS from tht> APPBT. APPLlj, and APPSP NAS benchmarks, and swm2S6 from tlw xiiPF benchmarks sPt. * \V e will see for the examples how changes in some architt>ctural paranlf'ters. such as number of processors and remote access time, lead to changes in the solution gPnerated by DDT. The tool is useful for the characterization of programs as well as tlw study of the effects of these architectural parameters. * AYailable by anonnnous ftp at ftp.informall.org in directory tl'nants/ apri/Bcnch. 7.1 Alternate Direction Implicit ADI In this section we furtlwr analyze ADT and cornparT the perfonnarH"P prt>dicted by DDT against tht> perfornH!Ilf"t' obtained when simulating the execution of the mt>ssage-passing code generated by xHPF. Tn addition. we also show tfw usefulness of the tool to predict the performance of different mapping strategies when changing architectural paramett>rs. Figure 9 shows tlw predicted and the measurt>d speedups for the program for different numlwrs of processors (ranging from 1 to :32) for two possible solutions: Tht> static solution where all arrays are column distributt>d (adi2 in all plot labels) and the dynamic solution (a diD in all plot labels) as shown in Section 2. For this plot we considered a remote acct>ss time of 1 p.,s. \Ve can draw the following conclusions: 1. Tlw prediction perfornwd by DDT (solid lines) is very clost> to the actual speedup ( dasht>d lines). Tn the dynamic solution we havt> noticed a s111all differPnce due to the estimation of redistribution costs. The model that we consider to estimate these costs (see Section '1.3) is not very accurate and overestimates the number of data clements moved. 2. The speedup of the static solution grows from one (for one processor) to two (for machine configurations with a largt> number of processors). This is due to tlw fact that about one half of the program is executed in a synchronized way with an Pxecution timt> close to the sequential exPcution time. 3. The speedup of the dynamic solution is lower than one for configurations with less than four processors but then grows with an efficiency dost> to four. This is due to the fact that remap- 16 Number of processors 32 ~ adiD (predicted) ·+- adiD(measured) ~ adi2 (predicted) • K- adi2 (measured) FIGUH.E 9 ADI- spet'dup vs. number of processors for the static and dynamic solutions. Comparison of the predicted and measun·d speedup (remote ac~!'ss time= 1 p.,s).
DDT: A RESEARCH TOO/, 91 Table 5. Breakdown of the Total Execution Time for ADI (Remote Aeee8s Tim!' = 1 f.LS) Static Solution NmtLProcs \lovement Computation () 10.S1S 0.1024 7.909 0.1024 6.606 8 0.10:2-i S.<JSS 0.10:24 5.629 0.102-i S.-t67 ping costs an~ n~ry large when a small number of processors are available and that all phases in the program are executed in parallel. 4. With this remote access time, DDT chooses the static solution for less than eight processors and the dynamic solution when eight or more processors are available. To further compare the dynamic and static solutions. Table:) shows the breakdown of the predicted execution time in computation and data movement times. Notice that for the static solution, the data movement overhead is constant (it is due to shifts where the number of elt>ments moved is independent of the number of processors). However, in the dynamic solution the redistribution overheads decrease with the number of processors involved in the data movement. Figun· 10 shows the predicted speedup when the remote access time changes for the static and dynamic solutions. The aim of this graph is to show the influence of remote access latencies in these solutions. In this 15 o~~~~~~~~~~r-~~~~~~~~~ 0.001 0.01 0.1 10 100 1000 Remote access time (microsecs) FIGURE 10 AD I- predicted speedup vs. remote access time for the static and dynamic solutions. 6.. adiD; D, adiZ. Dvnamic Solution Total \Jovement Computation Total 10.;")1-t 0 10.680 10.b80 B.011 1-t. 9'±2 ;) .• ")-tO 20.282 (J.70<J 7.-+71 2.670 10.11-1 6.038 :3.733 1.T3S :1.070 !i.T-12 1.867 0.66 7 2.S:3S S.S(J<J 0.9TJ (J.:F2 1.:372 plot we assume that the number of processors is H>. The following conclusions art> drawn: 1. For very lm,, access latencies, the speedup tends to be in 16 in the ch'namic solution ami 2 in the static solution. 2. The static solution is less sensitive to the memory latencv than the dvnamic solution. This is dw· . . to the fact that the volume of data transferred in the static solution is small while in the dntarnic solution it is large. For large latencies. any gain due to parallel execution is offset by the data movement overhead. :3. For this number of processors. DDT chooses the dynamic solution when the remote access time is less than;) p.,s and the static solution otherwise. 7.2 rhs Routine from NAS and swm256 Benchmark In this section we anaiYzt> the behavior of the solution suggestt>d by DDT for the other two benchmarks: the rhs routine from 'IJAS and the swm2S(J program. For each of them we compare the performance predicted by DDT against the JWrformance obtained in the simulated execution. \X" e assume that the remote access time is 1 p.,s and that the system has from one to eight processors. Figure 11a shows the behavior for rhs. ln this case DDT suggests a dynamic solution where three arrays have to be remapped. The dynamic solution implies that the outer loop in each phase runs in parallel. In this case the prediction is dose to tht> actual performance because DDT performs an accurate estimation of both data movement and parallel computation times. Figure 11 b shows the behavior for swm2:)6. ln this case DDT suggests a static solution where all the arrays are distributed by columns. This static solution implies that almost all the loops run in parallel. The main
92 AYGFADt~ ET AL. 2 4 Number of processors (a) 04-----------~------------.------------- 4 Number of processors (b) FIGL'RE 11 Pn·dictPd and measurPd spet>dup vs. uumlwr of 1n·ocPswn; for (a) rhs-chnamic solution . .l. rhs (prcdictt>d); D. rhs (measurt>d). (h) swm2S6-static solution .. assuming rrmott· access time= lms . .l. shallow (predictPd): D. shallow (mcasurt>d). program in swm2;)6 indudPs an itfTative loop and conditional statements that validatP the cmTf'Ct behavior and estimations of the control llow module in DDT. t\oticf' a small difference lwtween the predicted and measured Sfwedups. Tllf' difference is due to an overestimation of the data movenlf'nt overhf'ad: to get a better estimation, we havf' to improvf' the rnodulc~ that detects rf'dundant data motion eitlwr within a phase or hetwPPn phases. 8 CONCLUSIONS AND REMARKS In this article wP have prescntf'd the key modules in our automatic DDT. DDT generates both static and dynamic HPF data distributions for a giwn Fortran 77 routirlf' and for a whole application with intf'rprocedural analysis. In the static solutions, tllf' mapping (alignment and distribution) of each array in the program does not changf' during the exPcution. The static module is based on the CAC but is extPIHlf'd with some information regarding parallelism. We have also nwclifiPd the origiual algorithms in [1. 17] to improw thP quality of the mappings gerwrated [21 J. Dnuunic solutions ineludt> exPcutable statpments in the source code that change the mapping of specific arrays when nf'cessary lwtween computational phasPs. DDT performs a cost analysis of profitability in order to include tlwm. This analysis of profitability is basf'd on the following steps: 1. Df'tection of phases or computationally intensivf' portions of code. which mainly correspond to nestf'd loops and calls to procf'dures. Remapping is only allowed betwf'f'n phases. 2. Generation of candidate mappings for the previously detected phases all(! estimation of their cost (including data movf'ment and expcution time costs). :1. Analysis of compatibility among phases .. selection of mappings for them. and remapping actions to lw performf'd betwet>n consecutive phases. This selection is done by analyzing the cost in tPnns of data rnoyenu•nt due to rf'distrihution and its benefits in the cost of successive phasf's. Control flow information is ust>d to identify sequencing of phases. The algorithm explorPs a rich sPt of combinations although it is not Pxhaustivf'. It includt>s nwchanisms to cut down the search spacf'. DDT is a research tool \\·hich is currently usf'd in our group to support differpnt rf'search aspects. Since it is a research tooL it can use techniques that may be too computationally expensive to be included in a final compilf'r; howf'Yf'L this allows us to f'xplore a rich sPt of solutions. We have enduatf'd the quality of the solutions genenttf'd by DDT by comparing predicted performance against the aetual performance when the parallel program is t>xecuted. \Ve have also shown the usefulness of the tool for the characterization of the programs as well as the study of the effects of architectural pararnt'tPrs. \Ve have shown how the prf'dieted speedups arP close to the actual ones ohtairwd when the program is executed. DDT also accepts HPF dirf'ctivPs in the sourcf' Fortran 77 program: in this case DDT is useful as a support tool for the dewlopcr of HPF codes in estimating the effect of user-selected data
mappings and parallelization strategies m the final performance of the parallel program. We are currently porting this technology to generatP dficient code for hierarchical global shared memory architectures. In these architectures a number of central processing units can simultaneously access data anywhere in the system. However, the nonuniformity of the memory accesses is still an important issue to consider and may require a higlu~r programming effort in order to achieve performance; trying to access those ll'vPls in the hierarchy closer to the processor will increase execution efficiency. The technology developed to study the profitability of dynamic data remapping can be used to track the movement of data during program execution and thus parallelize loops accordingly, so that the access to data is done locally as much as possible. ACKNOWLEDGMENTS This work has lJPen partially supported by CONVEX Computer Corporation. COI\YEX Supercomputers S.A.E. CEPBA (European Center for Parallelism of Barcelona). and by the .\linistrv of Education of Spain under contract TIC- 429/<JS. We thank Miguel Hu~uet from COI\VEX SupPrcomputer S.A.E, Robert \1etzger from CO~VEX Computer Corporation. and the anonymous reviewers for their constructive comments. WP also thank .Iordi Torres for his help in the implementation of the interprocedural driver. REFERENCES [1] J. Li and M. Chen. ··Index Domain alignment: Minimizin~ cost of cross-referencing between distributed arrays.·· presented at Frontiers90: 3rd Syrnp. on the Frontiers of Massively Paralld Computation, College Park. MD. 1990. [2] M. Gupta, '·Automatic data partitioning on distributed memory multicomputers.·· PhD thesis, Center for Reliable and High-Performance Computing. University of Tllinois at Urbana-Champaign. 1992. [3] M. Gupta. S . .\1idkiff. E. Schonberg, P. Sweeney. K. Y. Wang, and K. Burke. ''PTRAJV II- A compiler for high performance fortran .. ·· in H . .T. Sips. Ed .. Proceedings of t}w 4th Workshop on Computers for Parallel Computers. The Netherlands: Delft University ofTPchnology. pp. 4 79-49.3. 1993. [ 4 J T. .l. Scheffler, R. Schreiber. 1. R. Gilbert, and S. Chatterjee. '·Aligning parallel arrays to reduce communication."" presented at the Frontiers95: The 5th Symp. on the Frontiers of Massively Parallel Computation, McLean. VA. 1995. [5] S. Chatterjee, J. R. Gilbert, R. Schreiber. and T. J. Sheffler. "Array distribution in data-parallel pro- DDT: A RESEARCH TOOL 93 ~rams.'" in K. Pingali et a!.. Eds .. Proceedings of tlw 7th Workshop on Languages and Compilers for Parallel Computing. Lecture J'\otes in Computer Science, vol. 892. :'-lew York: Springer-Verlag. pp. 76-91, 1994. [6 J ll. Kremer. J. Mellor-Cnnmney .. K. Kennedy. and A. Carle. ''Automatic data layout for distributed-memory machines in the D programming enviromnPnt .. '· presented at the 1st lnt. Workshop on Automatic Distributed Memory Parallelization. Automatic Data Distribution and Automatic Parallel Performance Prediction .. Saarbruecken, Germany. 199:3. [7] B. Chapman. T. Fahringer. and H. Zima. ·'Automatic support for data distribution on distributed memory multiprocessor systems. in ll. Banerjee et a!.. Eds., Proceedings of the 6th Workshop on Languaws and Compilers for Parallel Computing. Lecture 1\otes in Computer Science. vol. 768. 'lew York: Springer-Ver- lag. pp. 184-199. 199:). [8] B. Chapman .. P. Mehrotra. and H. Zima. ""Programming in Vienna Fortran."" Sci. Prug. vol. 1.. pp. 31- :10 .. 1992. [9] S. Iliranandani. K. Kennedy. and C. Tseng. ""Compiling Fortran-D for 1\UMD distributed-memory machines." Commun. ACM. vol. 35. pp. 66-80. Aug. 1992. [10] G. Fox .. S. Hiranandani. K. Kennedy. C. Koelbel, ll. Kremer.. C. Tseng. and M. Wu. "Fortran D language specification.·· Department of Computer Science. Rice Cniversity. Houston. TX .. Tech. Rep. CRPC TR 90- 141.. Dec. 1990. [ 11 J AppliPd Parallel Research .. . rhpf rersion 2. o. [ ~ser 's Guide. Placerville, CA: APR, 1995. [12] The Portland Group. PGllPF -R(1erenee 1Hanual. Portland. OR: Portland Group. 1994. [13] C. H. Koelbel. D. B. Loveman .. R. S. Schreiber. G. L. Steele. and M. E. Zosel. The high Performance Fortran Handbook. !\umber 1-2 in Scientific and Engineering Computation Series. Cambridge, MA: MTT Press. 1994. [ 14 J S. Wholey. '·Automatic data mapping for distributedmemory parallel computers. in Proc. o.f the ACM Int. Conf on Supercomputing. pp. 25-:1:1. 1992. [1SJ K. Kennedy and li. Kremer.. '·'Automatic data layout for high performance Fortran. Center for Research on Parallel Computation, Rice University. Houston. TX. Tech. Rep. CRPC-TR9449B-S, Dec. 1994. [16 J K. Knobe, J.D. Lukas. and G. L. Steelr, ''Data optimization: Allocation of arrays to reduce communication on SIMD machines.""]. Parallel Distrib. Comput .. vol. 8, pp. 102-118. Feb. 1990. [17] .T. Li and M. Chen. "Compiling eommunieation-dfi- cient programs for massively parallel machines.·· /£.'£'£' Trans. Parallel Distrib. Systems, vol. 2. pp. 361-375. July 1991. [18] R. Bixby. K. Kennedy. and U. Kremer, ""Automatic data layout using 0-1 integer programming. ·• in Proc. of the Int. Conf on Parallel Architectures and Compilation 1f>ehniques, pp. 111-122. 1994.
94 A YCliADE F:T AL. [ 19] P. Crooks and H. I I. Perrott. An automatic data distribution 1-!enerator for distributed memory l\111\lD machines.·· in H . .T. Sips. Ed ... Pror. of the 4th Int. IT in-k- shop 011 Compilers for Parallel Computers. The Netherlands: Delft llniwrsity of Technology. pp. :3:~ ++. 1 <)<);)_ [20] D. J. Palermo and P. Banerjee, ··Automatic selection of dynamic partitioning schemes for distributed-menwry multicornputers.·· in C.-H. Huang et aL Eds .. Proc. r!f"tlw Sth Annual Trorkshop on Languages and Compilers for Parallel Computing. Lecture 'iotes in Computer Science, vol. 103::1. New York: Springer-Verlag. pp. :~92-40(>. 1995. [21] E. Ayguade .. J. Garcia. M. Gironf>s .. .1. Labarta . .1. Torn·s. and M. Valero. ··Detecting and using affinity in an automatic data distribution tool.'· in Proceedings of the ith Annual Workshop on T"nnp;uages and Gmtpilers for Parallel Computing. K. Pingali Pt a!.. Eds. Lecture Notes in Computer Science vol. 892. New York: Springer-YPrlag. 1994 .. pp. 61-7S. [22] E. Ayguade. J. Garcia. M. Cironi·s. M. L. Grande .. and .T. I .abarta. '·Data rPdistrilmtion in an automatic data distribution tool. in Proceedings of the ~th An11ual Workshop on Lanp;uuges and Compilers j(Jr Parallel Computing. Lecture :\otes in Computer Science. vol. 10::1:1. :\ew York: Springer- V Prlag. pp. 407 --±21. 1 <J<JS. [2:)] .T. Peir. ··Program partitioning and synchronization onmultiprocpssor systemS:" PhD thesis, l lniwrsity of Illinois at l1 rbana -Champaign. 1 <)86. [2-± J C. LPiserson .. F. Rose. and J. Saxe .. '·Optimizing synchronous cin:uitrv by retimin~.· · presPnt!'d at thP :)rd Caltech Conference on VLST. CA. 198:3. [25] K. Kennedy. K. ,\icKinlev. and C-W. Tseng. ··Jnteractivt' parallel pro~ramming using thP ParaScope Pditor.·· Center for Research on Parallel Computation .. Rice l'niversity. Houston. TX .. Tech. Rep. CRPCTR 90096, Oct. 1990. [2l>] A. Gucist. A.lkguelin. J. Dongarra. \V. Jiang. R. :\1an- chek. and \. SundPram. ··PY:\I:-Iuser· s guide and ref- Prence numual.'" Oak Ridge 1\ational Laboratory. Tech. RPp. OB'iL/Tl\1-12187 . .\1ay 199:3.
Submit your manuscripts at http://www.hindawi.com Computer Games Technology International Journal of Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Distributed Sensor Networks International Journal of Advances in Fuzzy Systems Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 International Journal of Reconfigurable Computing Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Applied Computational Intelligence and Soft Computing Advances in Artificial Intelligence Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Advances in Software Engineering Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Electrical and Computer Engineering Journal of Journal of Computer Networks and Communications Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Advances in Multimedia International Journal of Biomedical Imaging Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Artificial Neural Systems Advances in Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Robotics Journal of Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Computational Intelligence and Neuroscience Industrial Engineering Journal of Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Modelling & Simulation in Engineering Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 The Scientific World Journal Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Hindawi Publishing Corporation http://www.hindawi.com Volume 2014 Human-Computer Interaction Advances in Computer Engineering Advances in Hindawi Publishing Corporation http://www.hindawi.com Volume 2014