NASA Contnctor Report 177999 

lCASE REPORT NO. 85-45 

ICASE 

PARALLEL COMPUTATION WITH THE FORCE 

Harry F. Jordan 

NAS1-17070, AFOSR 85-1089 

October 1985 

NASA-CR-177999 

19860004446 

INSTITUTE FOR CO~WUTER APPLICATIONS IN SCIENCE AND ENGINEERING 

NASA Langley Research Center, Hampton, Virginia 23665 

Operated by the Universities Space Research Association 

NI\SI\ 

NatJonal Aeronautics and 

Space Administration 

L.angtey Research Center 

Hampton Virginia 23665 I IlIlllII 1111 IIII 11111 IIIII 11111 11111 IIII 1111 

NFOI021 
Parallel Computation with 

the Force"\" 

Harr) F Jordan 

Dep:utnH'nt of ElectrIcal and Compllter I'ngllll'l'rIllg 

Unn erslty of Colorado 

Abstract 

.\ mdhodology. (allNI the force, supporb the con ... tJ lh tlOn of progr.lIn ... to he 

(,,\pcuted III p.uall('1 by a force of I)fO«>S~P'" The number of pro«,~ ... e ... III thl' 

forcl' IS II I\"'pt'clfied , but potentl.llly very I.ug<' Th(' furcp Idea h PlllhodlPd III 

a sd of 11I,H ro ... \\11Ich produce mllltlproc('~.;;or Fortran code and ha ... IH'('11 '" 1Idll,d 011 t\\() .;;lulfNIIl1PllIor) muItlpIO(e ... ~or~ of f.llliy chffer('nt (har,ldt'r Th(' 

llH'thod ILL'" ","nphfi<'d thp \\fltmg of hIghly par.1l1pl program., \\Itlllll a /IIl11tl,d 

c las ... of p.II.IIl(-1 algOl It II Ilh and IS belJlg e\.t ende(1 to cover a bro.lder c b ...... 

Till'" p.I)('1 dpn/ ... \\Jth the IIldlVldllUI parall('l ('Olhtluets WlllC'h (omprI ... e the 

forre JIlPthodolog) Of central concern are thl'Ir sPIll.lntle~, ImplpllH'lltatlon 

on dlffprt'Jil .1IdllU-clure ... and performance ImplJ('atlOlls 

'He<f'ar( h \\.i~ ~upported In part by NASA Contract No NA'lI·li070 and by the AIr For, e OIl1,'e of 

SCH'ntlfir H,"-c>1rrh under nrant No <\FO'>R 85-1089 while the allthor \\as In re'ldf'nre at JCA~E, "1-\'> \ 

Langley Rt"-Irrh Center, Hampton, \ A 2:366'; 

1 
Conceptual Basis for the Force 

The fOJ(l' [11 mrthodology for paralld progralllllllng aro.,e III trymg to 

produc(' lllg,h pl'rformance parallel programs III a shaIPd-m('mory mult.lproc('''-

sor runnIng, lip to 200 processes on the same usel program [21 Multlprogrammlllg wn<; not nn I<; ... ue, and all empha!'.ls wa., on ~lllgic problem so]utlOn spel'd 

Part I) for pNform ance measuremen t purpo!'.cs and partly for progr.lm 

manngl',lhJ!lt~, a programmlllg style emerged III which a smgle piece of code 

\\:1<; \\ Ilttpn \\llIch could be executed by a force of proC'e~ses III parallf'l Thl' 

nllmbE'r of processes C'on ... tltutlllg the fnrce I'> con ... tnnt durmg e\pclltIOn but '" 

bound 3::-' lat(' ,h the bl'glllnlllg of ex('cutlOn, and md) h(' one 

TIll' forC'(' teC'hnlqul' Insulates the prog,rammrr f/l)m all proce!'.s managpment and 1e,1v('~ hllll the I<;sue<; lllvolvIng proces., ..,ynchrolllzatlOll SlTlce 

procl'ssl'<; all' ('<;tnbh~hl'd by a progrnIll IJIdc'pl'lJdent driver at the b<'c,lllnmg 

of P\('C utlOn tllllC. parallelIsm I'> lIltlOduced at thl' top of the procedure 

Illl'rarchy TIllS ha~ the effect of lI1sulntll1g the usel from parallelIsm I~"ue,> 

\\Ith result ... Similar to those obtaIned by ellcapsulatlllg parallelIsm below a 

P,lItlC'ular ll'\ l,llll thl' procedure hierarchy The stud) of technlque~ for uSJIlg 

the forcl' III .1 program IS essentially a study of synchrOnIzatIOn mechanI::-.m ... 

\\hICh arl' lIldppl'nd('nt of the number and Idl'utltIC'" of the proce%es ::.yneill on I z NI 

S('\ernl ndvantage ... arise out of IIld('penclencl' from th(' number of 

proc es<;l'''' It I'" not nCCl'Ss,try to deSIgn algorlt hm::. \\ Ith a det aIled dep('ndenC'e on thl', pot('ntldlly very large, number of pI()(esses executlllg them 

Thp ChOlet' ()f the optImal numbPf of proce%cs can be made at run tlITH' on 

till' bn ... ", of <;) stem hard\\dre configur,ltlOn and load SlllC'e complete 

llldpIH'ndelle(' from the number of proces::.e<; Implie:, correct executIOn with 

only one PIOCP<;S, the Is~ues of arIthmetle corre(tne~., and multI-process synchrOllll3tlOIl call be ... ep.lrat('d III the testlllg of a prog,Jam 

StatpllH'nh \\llttf'n In a force plOgram are IlllpliC'ltly c'{ecut('cl by all 

prO(l' ...... e<; 11\ p.1f.1llpl VaflJble'3 appearlllg III ::-.tatement'3 are dIVIded mto 10(,11 

LlJ I.1bl('<;. h,n lllg <;pparat(' lll<;tances for each I)fOCl'<;"', dnd global \<arubles, 

... haINl among, all proC'(' ...... es of the forc(' An tb<;lgnml'lIt ~tatem('nt, for e~ampIe. Il1,H COIllI)))H' the \ allle<; of global ,wd loe.l1 ,arIabll'<; to produce a local OJ 

globalrl'<;uIt If th(' re"'IIIt 1<; local, no a::'~Ignml'llt conflict 1<; pO<;<;Ible If It 1<; 

global, thPll a ...... lgnment conflIct must be pn'\ ented, eIther by allocatIOn of 

dI"'JOlllt ,,('(11011<; of a global data, struC'furf' to multiple procc:,sl's or by ~ynclllolllzing Ih(' a<;"'Ignment across proc{':,~e:", ~ay b) ellc]oslllg It III a CrItIcal 

:,ecilOn or b} U<;ll1g producrr/coll<,uIIlPr <;)nChronl/cltlOn on the varIable 

a:"sIgned LIbrary or U5cr su brou tll1es "hI<. h .In' E'lth ('f frf'e of ~lcle effeeb or 

carefully s) IH hronlzed can be mvoked III p.1fallel, one ('OP) for each prOC'f' ...... 

One \Ll\ III which d .... Jomt s('dlOns of a global daLl ::-.truetllrp, ... peClficall~ 

an arr:n, 1Il,1~ be dlloC'at('d to mllltiple proce ...... p ... 1<; to <;C'hedul(· clJ ... tlllct IIld('\ 

\ aIuE'<; III a DO.\LL aero., ... proC'e<;<;es Inde\ \ .111ll'''' IIL1) eltlwr bl' H<;"'Igllt'd 

... tatlcall} to PI()CP::-'<;PS once the number of prOCl''''S('''' h kllO\\n, In ,\lllch C.l"'l' 

\\e ::-.peak of a prl'<;('hedu]ed DOALL, or procp ...... l'<; IlLl\ dynamlcall) schedule 

thpmseIy('::-. b) obt31111ng dIstInct va]ue.., of a global Index v,lflable a~ thc') 

become 3\ .1Jlable to e~ecute the loop body, knc)\\n (1::. a self-sC'heduled 
2 

DOALL III Plthpr casp, the l)Qdy of the DOALL I, executed onee fOf eath 

Indp\ value by some one of the proces<;es The C h<we of prp<'C'hpd uling or 

splf-scheduling may impact performanC'(' a~ a re~ult of uneVE'n \\orkload dIVIsIOn or of conflict on ac('Pss to the globJlmdex varldbh· 

Th(' programming language J"soCiated with the forte con<'I::'t<, of <,ome 

simple extpn"lOn.., to the Fortran language, ,,,hlch arc currently Implementc'd 

as macros "Inch are expand('d by a languag(' mdppenc/pnt preplOce"sor The 

LHgpt Fortl,ln system must, of course, mclude ways of creatlllg multll)le 

IHoc('ss('s nnd of 5upportIng synchronized acce<;s to global varIable<; A 

curr('ntly ol)('ratlOnal sd of macro<; produces Fortran for the HEP comput('f 

[3]. bllllt b~ DC'nplcor, Inc, and a set h belllg construe ted for th(' Flex/32 [1], 

bUilt by Fll'\lble Computer CorporatIOn The mac 1 o~ mt eract through the 

vHrIahips of .l parallpi ('nvlronm('nt, willeh contams ~omp gpnerallJiformatlon 

such as th(' llllmlH'r of IHOCPss('s and some madllllP dt'I)('IH!pnt It('nh 

Parallelism Constructs of the Force 

Thp m:H'ro" cunently constituting the fofte call be diVided IIlto sev('rdl 

eia"ses, as sho" n III Fig 1 The first class dpab Wit h pal allel program <;tructur(' The macro" Force and Forcebub fPsppctn'ply ht'g,1ll parallel mam program:, and parallC'1 subrou, Illes They make the pal J,lIel en'Ironment varJJblp~ avaIlable to the maer05 '\lthlll that program mudule as well as makmg 

thp l1umlwr of IHo('C'sses and a unlqu(' IdpntIflpr for tlIp (ltrrent process available to thp U,l'f at run tlllle An End Declaratlol/s nUl( ro malk.., the beglllnlllg 

of p:>..ecutabl(' code and pro"Ides target locatIOns for dl'clarc1tIOIl" and "tart up 

COell> "llIch may be g,C'llerated by thp macros A JOIII maCfO termlllatps the 

par,llll'! maIn program It IS the la!>t .,t .ltemcnt c'\('( IIt(,d by J.1I processe" of 

t hp force 

~rdC'l 0, of t hp second class deal with varIJ,ble declaratIOn TillS class 

currpntly meiude" only Global and Local macro:, Glohal varIables ale assocIatl'd \\Ith Fortrnl1 common while locnl vanablps are ordmary FortrJn varIablp, local to a spparatply compiled progr,lI11 moduh· Sharmg of local VarIable, among ,P\ pral program modulp" hut local to OIlP proce,,-. (an onl) be 

,H'colllplI,lH'd b) palarneter pa",lllg The ..,t.ltJ( allO(,ltlon fhnor of Fortran 

IlLlkes It diffIcult to build a structurp of comlllOll \'lll,lble" \\Ith onp IIl"LlIHl' 

for t'ach PIOCl'''' \\hen tilt"' number of procl''''(', h npt kno\\n ulltll e\eeutlol1 

tlllH' 

~lacro, of anothpr cla":' dIstrIbute \\ork ,1Cro"" PIOCP'!>(,S The most Ll1ll1-

har construct IS the DOALL, which IS emplo} eel "ltl'n IllstaJlC'l'" of a loop 

body for clIfferpnt llldpx valup" are llldepenc\(>nt and < an thus be p:>..pcuted III 

any order T\"o VNSlOns are provIclpd The Prebrhed DO dIVId('s lllckx valul''' 

among IHO«('''"e'' 111 a fh.ed manllN willch dE'p('nds onl) on th(' IIldex range 

and the number of processes Thp SelJ.sched DO allo,\'- proce<;.,(', to schedule 

thpmsplyp:, 0\ l'r mde-x yalups by obtamlllg th(' llnt JyaIlabl(, valup of a 

"hared mdp\ a" the) bpcomc frpe to do \"ork For sI1UJtlOn, m \"llICI! It h 

dpsIrable to parallplIzp 0\ er both lIldlcP, of Ll dOllbly np!>ted loop. both 

prescheeluled, Pre:2DO, and self schedu}pc\, Self2DO. macros arp uV<lllabl(' 
3 

Ma,('fo,:; a~<,()(Jat('d wIth program structure 

Force <nLlIlH'> of <# procs> ldent <proc #> 

< dr-darat IOn~ > 

End d('('Llr,ltlOlIs 

< fOI (,(' program> 

JOIn 

For('C'..,ub <n,1m('> of <#pro('s> Ident <prot #> 

<dt'cI.lr.1tJon.:;> 

End h(,.1dc'r 

<~lIbroutllle body> 

RETlTHi\] 

FOI('e(,,111 <name>«parameters» 

DeclaI.1tIOn nLlCNh 

Global <\,111,1hl(' nanH'':;> 

Loc.}1 <Fortran cit'elalatlon> 

~1.l( ro.., sp('( If) IIlg pJr.lllpl C''\E'( utlOn 

PC,hC' OJl <vclndhl('> 

<cod(' hlock> 

Psed 

< cod p block> 

[Pr('l~elf]"'(hC'd DO <n> <var>= <11>, <12>. <13> 

< loop hod) > 

<II> End [prl'~C'lfl~('h('d DO 

S) Hc h ron IlIlIg [I1,l('fOS 

B,lI r\('r 

<COd(l hlock> 

End b,lI IIl'r 

C'nt IC ,II S < \ ,HI,} hiE' > 

< C (Jdl' blo( k > 

End (1ltlC,d 

Product' <\,HIJble> = <C''\pres'>wn> (plOducl-'r) 

{:,:;p«Y'}llable> (con",ullll'r) 

FIgure 1 SpC'clfic ~lacIO':; for a Force Program 

Indl'IWllc\pncp of thC' loop body Instan(e::. oyel both mdlce::. I':;, of cour:,e, 

rE'Cjll\fPcl fen correct operatIOn A slInIlar con"truct IS the parallel ('ase, Prase, 
4 

which clistnhut('s dIfT('rl'nt single stream code blocks ()\er th(' prOCI'Sf,e" of the 

force ExecutIOn conditIOns can be a">soclated With each block, and any 

number of these conditIOn" may be true sllnultaneoubly No order of evaluatIOn of the conditIOns IS speCified, and each will be ('valuated by one arbltlanly sel('ded proces"> Thus conditIOns depending only on global vanables 

are most meaningful 

At the heart of the force methodology are the s)nchronlzatlOn macros 

Thl'Y charactl'nze thl' approach to parallel programming and prOVide the 

means for controllIng the force so that coherent and determIllI .... tlc computatIOn can b(' performed Two sllbclasse'l of byn( hronl/atlOn are control flow 

onented bYIHhronlzatIOn,,> and data onented <;ynchrol1llatlOns The key ('antral onent('(1 "» nchrollIzatIOn I~ the barner ">lIlce It prOvides control of the 

entin' force Its semantics are that all proce::.se~ must execute a Barner 

macro bdore aile arbltranly chosen proce~s ex('(uteb the code block between 

Barner and En d Barner \Vhen the code block IS (olllplete, the entIre force 

begll1s e\PCll t lOll at the 'ltatement follOWing the End BaJ ner Although all 

bu t onC' pro( p .... " <11 C' tl'mporanly suspended by a barr)('r, no pro('ess termmatlOn or Crl'atIOn take,,> pL1ce and all local proce" .... sLltes are pre .... eIVed a('ro<;s 

the barfler 0pPfatlOns \\hl('h depend on the pa .... t computatlOll. or determllle 

thl' futur(' prog,re::.s, of the entIre force are typically end()~ed m a barrH'r 

Another control ba::.ed synchronllatlOn h the cfltIcal sectiOn, fanllhar 

flOm t h (' op l'r at 111 g S) .... t pm" ht er at u Il' Stat emen t <; behH'en 

Cntll'al <l'([flabie> and End Clltzeal may only be e\l'nitl'd by one pro('e.,,, of 

the force at a time Till .... mutual e\c!u..,lOn p\t('nds to an) other cntlcal s('ctlOn \\Ith thc .... ,1IlH· a<'''()cIJted Llflabll' Data oIH'ntE'd .... )llchronlzatlOn I" pro-

\ Idpd b) thp t'h'll1cntary produccr-con::.1II11er IlH'C ILlnbIl1, 111 which globJI vallabJp., havp ,1 bll),H) state, full or empty, a<, wdl d~ .l value E'>.ecutlOn by 

::'O/llP I)fOCl' ........ of th(' macro, Produce <l'anabie> = <e.rpres'3ton>, walt<; for 

tlH' \ 311<1hh· to be III tIlt' E'mpty ~tate, ::.£'ts It"> v,Jiue to that of thE' l'Xpr('::.::.IOIl 

and makp .... It filII . .111111 a manner \\IlIch I"> ,ltnmIC With H' .... pect to the progrp .... s 

of ,Ill) otlH'1 pr()cp ........ SlInIiJrI), the macro, l~~(,«l'allable». ,lppearIIIg 111 an 

p\prp::."lOn I pt IIrn .... th(' valuc of tllE' \ arl.1ble \Vh!'1l It hecome"> filII and .... ph It 

pmpty Y,III.ll>le .... III the \Hong "tatt' may C.W::'l' tIH' .... (' ma('fO~ to block the 

progrp ........ of ,I procc"::. Au\I1l3r) macros for fllll/('mpty \ anablp<; are 

Purge <I'anabl('>. ,"nch sets a vafl,lble Plllpt)' rpgardle~" of Its pre\IOUS 

::.t.1tp, and ('oPY«I'([nable». wlllch \\.lIb for the v,lrIable to be full and 

return"> It" \ ,dul' but dop" not empty It 

A maJO) \\cakness II1 thE' current set of fOlce m,lcro~ IS thJt It does not 

smoothly support decompobltlOn of a program 1I1to parallel component... on 

the ba<;ls of functIOnalIty The Pease maclo ()fTer~ the rudlmenb of thb, but 

only allows OIH' procE'SS to execute each of the parallel functlOn~ \Vh.lt IS 

deslreel IS a mano, Resolve, V\'lliCh will resolv(' the fClIce mto components e\ecutmg (lifTp)('nt par<1lll'1 code sectIOns The sp( tlOll of code for each COlllponent "Oldd ~tart \\Ith Component <name> strength </lumber>. V\'hlch 

\\ould nJme the component and speCify the flactlOn of 0)(' force to be 

devoted to thl<; component The component ">tn'ngth::. w01lld be E'stmuted b) 

the programmpr on the baSIS of any knowledge available about the 
5 

computatIOnal complt'\':Jty of each component A macro, UnIfy, would f(>unrte 

the eompollt'llb mto a sIngle force The nnplementalron of Resoit'c 1<; complIcated by tht' confllctmg d('mands of generalIty and ('fliclency If th{' number 

of COmpOIll'llts IS larger than the number of proC'P"-;(,S III thp for(,e, thpn 

lllter-compollt'nt synchronIzatIOn may deadlock un\l':-" the (omporwnt<; an' 

co-schedu\(>d OVN the avaIlable procpsse<; An Imph'mentatlOn which produees proel's::- r('seh('dulIng at every p05sIble deadloek pomt and IS '>tlll 

efilelent "IH'n the number of proeesses exce<.>ds the Ilumber of eomponent~ I.., 

under development 

IneorporatIOn of a Resolve maero would make It lI"eful to extend the b,lrrIer Id<.>a A barrI<.>r should he able to specify whet hN only the proce<;<;es 111 

the current component are to be blocked or \\hetlll'r all proee,,'>e<, III the 

parent for('(' .1)(' to partl(,Ipate In the ('ase of re('ur~n ely nested Reso/z'e (on-

~tItlet", tht' harrI{'r mIght specIfy a n('stmg It've\ r('Lltl\e to the ont' 111 whleh 

It appear.., 

The Re~oll'e Idea IHoml<;t's a mechanl..,m fOI fUlI( 1 rollal d('(ompo<;lt JOn of 

programs lllto parall('l components, but thNc 1'1 one Illore capabilIty of parallel progrJl1Illllllg enVIronments WIth explICit proces'l man.lgpment "hl('h IS not 

addressed b) th(' forc(' ThIS 1<; the abilIty to give ,1\vay work to "avaIlable" 

proce::-~('~ III a dynamiC manner durmg executIOlI Tltl" abilIty 15 most call{'d 

for b) tree algOrIthms and dynamIC dlvlde-and-conqu('f method<; It would be 

de'lirahle for tlH' force to contam a nwchalll'lm for pfficlently handlIng slIch 

algOrIthm" '\lthout maklllg the user re'lI)()\l'>lbh' for l'\phclt proce".., managl'-

nH'nt or IO~lIlg the benpfit<; of llldependencp of the Illlmber of plOce~"{',, A 

mechalll~m rplated to l'C'''ohe I,llght be app\r<'C\ at p,ldl tre(' Bode but cOllld 

l('ad tn mll~ h PIOC(,<;S management ovelhead III (:l'le" "hl're tIl(' eorrcct tlrlllg 

to do I" nH'IE'I~ to trav('r::-e a subtree WIth the on(' rem a JIllIlg pr()«('~.., 

Interrelationships Between the Primitives 

The S('IlHldIC<; of the paralleh5m con~trl\ct<; m the force Imply certam 

rC'"trrdIOn::- on the wa) they are used togetIH'r In a progJam Spv{'ral of the 

con<;tlllct~ It'stllet e'XecutIOn to a smgle stleam \\Ithlll ::-ome codl' block Barner and Pea~e lImIt e:\('cl1t IOn of pnclospd block,> to a "lIlgle pro( ('~::- \\ h riP (J ItHal ,,('(tlOll C'od{' 1'1 ('ventually ('\.('(utl'd b) all I)fO«'''''('~, but onl) OIH' at :l 

tlllU' Thth con"tlu(h "hlch depend on multlph>, ""l1ultaIH'OU" (,\pcutJOn, 

such a<; DO.\[ L, Pease or Barner should not appeal '\Ithlll :-uch block" .:\ 

cfltIC'al 'IN 1 Ion ,\ It hIll a Barner I" DlPanlllgl('"", b1l t C'rll Ic,}l ~('( t lOll" haH' 

defilllte use '\Ithm t\\O 01 more code block~ of a Fea~e (OI1'>trl1cl Ne<;ted crrtIcal sectIOns hclye InC'3lung when the assoclatpd \oc kIll F, vallabl(,s ,He dIffer('nt 

Dat a orrented <;YllchrolllzatIOn prrmltlves may OC( UI ,\It hm slllgly execut cd 

code '\Ithol1t rC'~tflctlOn, other than the natllrdl po""IbIlIty of deadlock In 

fact, mltlalIzatIOn of full/empty varrables IS usuall., done wlthm a smgly e\ecuted block 

Parallel loop<; do not restrrct the executIOn of th('1f bodIes to a slIlglp proce"b, but the'y do lImIt exeC'utlOn of tIH' body for e<1(h llldp\ vahlP to OIll' pro-

(e~s Thu~ C'on'ltrucb "blch depend OIl full par,dlPl ('\('CutlOn ('annot appp,ll' 
6 

\\,IthIn DO.\LL" These Include Barner, PraH and other DOALLs The 

InCOnsistell( y III the parallelIsm requlrement~ of nested DOALLs I~ the rea<;on 

for suppl) IIlg multIple mdex DOALLs for parallel e:-.ecutIOn of loop bodIes 

willch are Illd('pendent over the Carte<;Ian product of two or more Index ~ct<; 

Cntlcal sedIOns, Produce and Use are qUIte useful withIn DOALL'l and often 

lead to programs In whIch the dlstnbuted natUle of -,ynchronizatIOn reduces 

Its effect on program performance 

SubroutIne lIlvocatIOn wlthlll a force program <'.111 be don{' eIther wIth a 

Forcecall or an ordlllary Fortran CALL Only the F{)f recall make,> the parallel (,11\ Ironl1)(\nt avaiLtble to the subroutllle called SIllCl' a foree subroutllle 

Invoked b) Forcecall assumes that all processe~ of the force wtll enter It, a 

Forcecall ml .... t not appear wlthlll a code body III WhH h parallel ('xecutIOIl has 

been restnd{'d Thus, Forcecalls are not mealllllgflll wlthlll Barner, PC1<;e, 

CrItIcal or DOALL constructs An ordlllary CALL Imphe~ executIOll of a subroutllle In <;lI1gle stream on behalf of one or more processes SlI1ce any Fortran ba~('d parall('l sy<;tem must support multiple lJIdependent executIOn of 

subroutJlH' .... , such as tho~e III the nuthellutlcdl IIhrary, subroutllles must 

hent> separ.ltl' local',anable states for all JHOC('S .... (' .... C\Pcutll1g th(,1l1 An ordInary Fortl'HIl ~uhrouhn(' or functIOn call may thus "ppear "Itllln any code 

sl'cilOn of a force program The sllbroutmes or fundlOns.;;o lIIvoked contam 

no paralll'1 constructs and access by them to an) ~h.Hed vanables must be 

controllpd e\tl'rnally If It IS deSIred 

The Re,'oil'e con~truct IS llltended to produC'(' .1 new parallel e\('cutIOn 

('nvlronm(,llt \\Ithlll ('ach of Its componenb, dlfTl'rlllg, from the ongillal only m 

the numb('r of proce<;<;es Thu<; all of the parallc'lhm prtmltlve~ have meanmg 

"Ithm .l fOI('(' compoll('nt The Impl{,lllelltatlOll<; of the prlmltIH'';; mll"t, of 

(Olll~e, rd('1 to th(' paralld enVIronment of the (ompolIl'nt rather than of thp 

ollgmal f(lIct' TlIt:' mt:'alllllg of BarlIer, a~ ha~ bl't'n ll()tl'd, can hl' \·\tended to 

rpfer to hlghl'r l('v('l<; of a npsted compont:'nt stlllduh', hut It ret a Ill';; It~ Orlgln.1I Illpanlllg \\Ith re .... pC'ct to the Immediate C'omponl'lIt WIth no lllOdifiC'atinIl 

of Its semantH<; Barner, Pcase and the DOALL .... 11:1\ e an actIOn lImited to 

tht> ('OIllI)oIH'nt III willeh they appear CrItIcal <;ectlOlls and data OrIented 

S) llehrolllz<JtlOn., can ~yn('hrollize operatIOn.;; WltlUIl the C'urrent component 

\\Ith operatIOns III any other componenb "hlch ~haf(' the corre~pondIllg vana h It:'s 

Performance Issues 

VarIous features of the force methodology alt:' rl'\.ltl'd to tht:' pprformancC' 

of a parallpl computer system An overall prInC'lple u .... l'(illl select toll of prlmItIvt:' operatIOns for II1clu~IOn III the foree wa<; that t hl' ';;l'mantlc~ of each pmnItlve should he SImple enough to admIt of an efliclent Implemt'lltatlOll across 

the range of shared memory multiprocessors The Simple proce<;<; model, con-

~I"tlllg of program countpr, local varIables and unlqUl' IdentlfYlllg lIldex, al.;;o 

contrIbutes to 10\" oV('fhead Implt:'mentatIOll on most sharpd mpmolY 

mac Innes Procc~s prIorItIes and parent-chIld rt'\atlOllshIPS, for exampl(', (an 

sIgl1lficantly complIcate the ImplementatIOn of a parallel programmmg 
7 

'5yst em on ~ome multJpro('('s~ors whIch do not duectl) ... upport ~u( h featu r(· ... 

The prIlnItlve oper,ltlOns of the force d('finp a VII tual muehllle, and the 

genNaht~ of tIlls machIne YI('lds Independence from th<> detaIl ... of the undPflYIng hard\\:ue ThIs brnefit of machIlle md('pell(h'/I('(' and portabIlIty n('('d 

not, ho\\ l'\ N, <;uppre<;s all machme perforrnanc e 1'>~IH'" at thp Ipvel of force 

programmlllg Pratt [5] pomt., out that a vlItu,11 mac hIne for parallel ('xecutIOn should make "vlslblp," a~ programmlIlg alternatlv('", dl"tInCtlOlI~ whIch 

may r('fleet major hardware pNformance dlffer(,Ilces 1'h<> c)('an·.,t ('"ample of 

such alternatne<; wlthm the force I~ the eXIstence of both a prescheduled and 

a self-sched 11 Jed DOALL 

At the IpHI of th<> abstract machIne, the proce ...... II\teractlOlI" IInphed by 

prl'- and ~('Ir- <;chedllhng, ar(' chffer('nt Pre~chc'dllhng ~lI\ce It allo( at(' ... II\cipx 

\ :lIues to pr()('l'~Sl'S In a fhed way as soon as the numht'r of proel' ... ~es I~ dptermInpd, \\111 ... pht the \,orkload e\,pnly acr0~<; pwcP" ... ('-., oIlly If proc(' ... "ors rUIl 

at slInIl,H "',H'pd<; ancl the amount of computatIOn "',H'(lfll'd by the DOALL 

body IS IIldl'ppndpnt of Index value Cll the othpr hand, no proC(· ... s InteractIOn IS leqlllll'd to allocate the mdex valups, ('ach pl'Oce~~ can ddprmllle It" 

o\ .. n portIOII of th(' work Independently In contr,ht, the ~elf-"ch('(luhng technIque all(,,, ... IHOCP"~P'5 to load balance at eH'CutlOll tllIlp by obtaInlllg further 

IIldex valuc'<; \-.)H'never they complete the work cOIlIH'dC'd \\Ith preVlOlI" 

Yuille ... Th, ... I~ donp :It the expense of ,1 short cI,tlCal ... ('dlOn to obtall\, IIHrl'-

men t and st 01 C' ,1 sharC'C1 mdpx varI.lble 

For a g,I\PIl unc!plJYlIlg hard\\aIP, thl'~e <I, ... tllldlOlI'" at thl' ab ... t,.1d 

maclllne Ip\pJ LlIl hp tlanslatpd II1to IH'rformance dltrprenC'P'i h) u~lIlg a f('" 

genNal Ch:lI,I(jPI, ... tIC'" of the harclv"ue ... y"tem Thp 1110 ... t Important paranH'-

tpr" for tht· »1(,- \l'rsll" splf- schedulIng compall ... on ,liP the SIze, III ('\('('utIOI1 

tll1H', of a 1ll1I1IIl1al crItHal :,ectlOn to acce~s and upd,ltp a shared II1dex and 

thp IltllnlH'r of proce,,"es competll1g for tIllS acc('''s \\ hell combll1ecl \ .. Ith the 

program dq)('nclC'nt par,lmeters of the mpan and standard cle\WllOn of the 

DOALL bod) ~IZl' over the '>et of Index valll~'" thp) ,lllow a clej('rrlllnatlOn of 

",IlIch t)))(' of s(h('duhng 'HlIlead to bptter pE'rformanu> 

Implementation Issues 

Imph'llH'ntatIOn IS~lIes can bf' addrp"s('(1 on the \),l"'b of v,trlatlOlls III thp 

t\\O currl'nt IlllplC'mpntatlOlls SevPral hardwarp (lIffe)('n('e~ bet\\el'n thf' HEP 

and the F)(''\/32 muItlproce~sors InflUl'IlCe Impl('ll1pIlLltwn of the force macros A mlllor, but baSIC level, dIfference IS that ,III mPlIlory In the IIEP can be 

shared by all processes so only Fortran varIable scolH' Issues arp lIlvolved In 

Implementll1g global varIables In tlIP Flex/32, only a restrIetpd portIOn of 

the addres<; spacp IS acceSSIble by proceS'ie~ rUlllllIlg 011 different PIOcpssor" so 

sharpd vun,lblp ... IllU'5t phY~lcally rp~lde 111 tht''>e ,lddr(· ...... es as well a ... sat 1'-0 f) lllg 

Fortran (on\pntlOns for name sharmg by dIfferent module::- Thp ... haIPt! 

addres<; spac(' on the Flex/32 IS Iarg(· enough and It-, clc('e~s tlll1e n('31' enough 

to that of local memory that thIS should not be an l'-o"'U(' eve»t for progr,llll'" 

""Ith very Luge global data reqUIrements 
8 

The ba~lc synchronizatIOn mechanism In HEP IS the lockIng full/empty 

bit in each memory cell Locks In the Flex/32 are separate and, although 

there are 8H)2 of them, they form a scarcer resource than IIEP synchronizatIOn element" Furthermore, SInce the HEP ha'l hardware to support the temporary suspl·nsion of processes, the user can do bYllchrolllzatlOIls directly 

whIle the malllpuJatIOn of locks In the Flex/32 mUfo,t be done through the 

operatmg s:"tem Figure 2 shows crItical sectIOns for both madllnes and 

notes the U'H'r mstructlOn versus system call dlstIn( t Ion The Flex/32 ConCurrent C 'lystem supports the as'lOClatIOn of a lock \\ Ith any shared vanable 

t.o "hlcb synchrolllzed access IS made, so at t hiS level the machIne dlfference'l 

are not major, as far a'l ImplementatIOn of the force macros IS concerned As 

shown m FIg 2, the crItical sectIOn macro has an associated varIahle to allow 

for dlstmct ~ets of interacting critIcal sectIOns In boi h Implem('ntatlOns tIllS 

becomes a global vanable WhICh IS locked (dIrectly In the HEP and via S}btem 

call In the Flex/32) on entry to and unlocked on eXit from the crItical sectIOn 

The Produce and Use macros are qUIte clJff('rent (1/1 the t",o ~}~tems ">Imply becJus(' th('y correspond chrectly to ~lTIgle nH'mon accebS lll"tructIOn-, on 

the HEP and must Inyolve the locks on the Flex;'~2 ImplementatIOn of 

CrIticallocki 

<code block> 

End Cntlcal 

Cntlcal lock I 

< code block> 

End Cntlcal 

SIngle mst ructIOn HEP 

Fortran mtrmslc" 

awnte wait for empty, 

wnte, set full 

laread walt for full, read, 

set empty (logical) 

HEP 

Flex/32 

call aWrIte(lockI, true) 

< code block> 

call laread lIock 1) 

call CClock(I, "lockI") 

<code block> 

call CCunl(k(I, "lockI") 

Fh'\/32 operatlllg 

... 'stem cdIl" 

CClock walt for unlocked 

and lock 

CCunlck unlock 

FIgure 2 ImplementatIOn of CritIcal SectIOns 
9 

Produce and Use for fewE'r than 8192 varI:lbl('s ml!~ht be done u<,mg the 

hardware lo( ks on the Flex/32, but full/('mpty acce"" to mdlvldual clempnt<, 

of a large alray reqUIres a software supported as~o( latlOn of varIable~ WIt h 

full/empt) bIts SynchronIzed access to the bIts and theIr a~"o('latcd varIables ne('d" to employ a combInatIOn of the lot ks and evenb -,upportcd by 

the hard\\ar(' 

Impl('mpntatlOn of the Barner macro show~ ,>ome clt'ar chfferench 

bef\\Cen tht' two systems In both cases, the semantl("1 r<>qumng all proce""c<, 

to arrIve IH'fore the code sectIOn IS cxccutNIIf> supported by a shared COllnter 

synchronIzl'd a~ In the CrItIcal '3ectlOn Two barrIer mechanI..,ms have b<>en 

used on thl' JlEP In ~ystems small enough that nH'II,ory ('ontentlOn I~ not a 

problem, the' In..,t proc('s.;; to Incr('ment the "har£'d (OllntPr eX(,('lIte" the (odp 

S('ctlOll and: II" a nH'mory locatIO'. willch thp other I>IOC(''>S(,S an' .Ittpmptlllg 

to read P" 'e"s('s mu.;;t then count down the (oul",'r a~ tllE'Y ('\It th(' b.lIner, WIth th, I.ht one r('settmg the lock If 1lH'1ll01') «()ntentIon IS a probIPm. 

th(' abIlIty tll contlOl processp,> at the u~er level aliow.;; \Hltlllg or a IIEP 

as..,embly lall ~u.lge routllle In wluch all hut the IdSt PJOccss to elltl'r a harrIer 

termlllate e'.l'cutlOn to bf' recreated WIth theIr prevIOus state by the last pro-

('es.;; to entel' the barner In the Flex/32, process ('olltJOIIS a system functIOn 

The SYSt(,lll. however, supports thf' concept of .;;harl'u events, C'onnected to 

processes III ,\ broadcast configuratIOn Here. pro(e:,~es entermg the barrIer 

\\alt on the I'vent, cxc('pt for the last one, whICh (''(PI utes the code block of 

the barrI('\' "lid then adrvates the event Y('rlf)llIg that each pruc,e:,s (Olln<>cted to th\' event has !:.ooeen It IS part of the olH'ratlll'.!, .;;ystem sllpport, so no 

PXlt code I" rt'quIred The first mechanl"ll1 for th(' HI~I' I., contra-..tpd WIth th(' 

Flex/32 rmpl 'mentat.IOn III Frg 3 

Conclusions 

The dp"lg,n of a parallel prog,ramrnlllg systpm HI' olves a comblllatIOll of 

the Issue" of utIlIty \\Ith those of IInplpmenLttlOn ('fficlency The utIlIt) 

Issue~ havt' h('('n tr£'atpd III prevIOus papPI'';; [IJ [6J \\ lllie tillS work con('('ntrates on til(' IlldlVIdual macro semantlc~ and IInpl(,llH'ntatIOIl b"lleS The 

force methodology <;upports effi(,lent Implpll1pnLltlOn by the SImplICIty of rt... 

process modd and la('k of complex "l'm,llIt IC" III Illdn rdual pal allel '011-

~truct.;; _\t /\'.1'>t two multlproces.,or~ \\rth shared mt'1Il01'Y admit of :,trmghtforv.ard ImpIPnH'ntatlOns 
10 

HEP 

Barrier 

< code blo( k> 

End Barrier 

Flex/32 

Barner 

< code bl(. k> 

End Barner 

HEP '-lIlgl ' IIlstructIOn llltrlllsiCS 

waltf - \ alt for full, read 

aread - \, alt full, read, set empty 

awnte - \ alt empty, wnte, set full 

scte - "l't empty 

Figure 3 Illli It'mentatIOn of BarrIers 

If (lwaltf(llock)) contlllue 

Illoc = Iar('ad(nbar) + 1 

call awnte(lIbar, nloc) 

If (Illoc eq np) then 

< cooe block> 

call sete(II,)ck) 

call awnte(olock, true) 

endlf 

If (lwaltf(ol(lck)) contlllue 

nloc = Iarpad(nbar) - 1 

call iawrltelnbar, nloc) 

If (nloc eq np) then 

call ~ete( olock) 

call awnte(Ilock, true) 

endif 

call CClock(l, "nbar") 

nloc = nbal + 1 

nbar = nloc 

call CCun Iekll, "nbar") 

If (nloc eq np) then 

< code block> 

call CCactev(l, 4, "bar") 

else 

call CCwcv(l, 4, "bar") 

endlf 

Fie\. 32 operatlllg svstem call .... 

CClock - walt free, set lock 

CCunIck - clear lock 

CCactev 

CCwev 

- actIvate even t 

- walt for event 
,-

11 

REFERENCES 

[lJ H F Jordan, "StructurIng parallel algorIthms III an MIMD, shared 

memory envIronment," Proc 18th HawaII IlIt'nl Conlon Systems Sciences, Vol. II, pp 30-38 (1985), to appear III Parallel Compuirng, 1985 

[2J H F Jordan, "HEP architecture, programmmg and performance," m 

Parallel AfIAfD ComputatIOn' The HEP Supercomputer and .ts Appl.cairons, J S Kowalik, Ed., MIT Press (l085) 

[3J M C Gilliland, B J SmIth and W Calvert, "HEP - A semaphoresynchronized multIprocessor WIth central control," Proc 1976 Summer 

Computer Simulation ConI, Washmgt •. n DC, pp 57-62 (July 1976). 

[4J Flex/32 Afuit.computer· System Ot'erv.ew, F!.~xILle Computer CorporatIOn, Dallas, Texas (1985) 

[5J T W. Pratt, "PIsces An enVIronment for l)arallcl sCIcntIfic computatIOn," ICASE Rept No. 85-12, NASA Langley Research Center, Hampton, VA, NASA CR-172544 (February 1985). 

[61 N R Patel and H F. Jordan, "A parallehzed pomt rOWWIse succeS~IVp 

over-rel:1xatIOn method on a multIproce~sor .. Pa/allel Computmg, Vol 1, 

No 3&4 (December 1984). 
1 Report No NASA CR-177999 I 2 Government Acc.stOn No 3 Recipient's Catalog No 

ICASE Report No. 85-45 

4 Title and Subtitle 5 Repon Dete 

PARALLEL COMPUTATION WITH THE FORCE October 1985 

6 Performing Orglnlzetlon Code 

7 Author(s' 8 Performing Orglnlzatlon Report No 

Harry F. Jordan 85-45 

10 Work Unit No 

9 Performing Organization Name and Addreu 

Institute for Computer Applications in Science 

and Engineering 11 Contract or Grant No 

Ma11 Stop 132C, NASA Langley Research Center NASl-17070, AFOSR 85-1089 

Hampton, VA 23665 13 Type of Repon and Period Covered 

12 Sponsoring Agency Name and Address Contractor Report 

National Aeronautics and Space Administration 

Washington, D.C. 20546 14 Sponsoring Agency Code 

505-31-83-01 

15 Supplementary Notes 

Langley Technical Monitor: Submitted to Proc. 1986 IntI. Conf. 

J. C. South Jr. on Parallel Process1ng 

Final Report 

16 Abstract 

A methodology, called the force, supports the construct10n of programs to 

be executed in parallel by a force of processes. The number of processes 1n 

the force is unspecified, but potentially very large. The force idea is 

embodied in a set of macros which produce multiprocessor Fortran code and has 

been studied on two shared memory multiprocessors of fairly different 

character. The method has simplified the writing of highly parallel programs 

w1thin a 1im1ted class of parallel a1gor1thms and is be1ng extended to cover a 

broader class. This paper deals with the individual parallel constructs which 

comprise the force methodology. Of central concern are the1r semantics, 

1mplementation on different architectures and performance implications. 

17 Key Words (Suggested by Author(s)) 18 Distribution Statement 

multiprocessor 61 - Computer Programmng & Software 

programming environment 

parallel programs 

Unc1ass1f1ed - Unlimited 

19 Security aasslf (of thIS report) 20 Security Classd (of thiS page) 21 No of Pages 22 Price 

TTn,.l"""iFi",r1 TTn,.l"""iF,,,,r1 11 A02 

N-305 For sale by the National Technical Information SerVice, Springfield Virginia 22161 
End of Document