Prince of Wales Road,

AdamBackandStephenTurnerDepartmentofComputerScience,

UniversityofExeter,PrinceofWalesRoad,ExeterEX44PT,England

Email:aba,steve@dcs.exeter.ac.uk

Tel:+44392264048Fax:+44392264067

Abstract

Optimisticexecutiontechniquesarewidelyusedinthefieldofparalleldiscreteeventsimulation.Inthispaperweshowthatoptimisticexecutioncanalsobeusedtoparal-lelizeprogramcontrolstructures.

Wediscusstherequirementsforhandlingunboundedconstructsanddemonstratetheneedforaflexibletime–stampallocationscheme.

Wepresentaschemeusingvariable–lengthtime–stampswhichallowsanarbitrarynumberoftime–stampstobegeneratedbetweenanypairofexistingtime–stamps.Theorderingrelationdefinedforthesetime–stampsissimilartothatforfractionalnumbers:fortwoconsecutivenumbersofagivenlengthitisalwayspossibletogenerateanumberwhosevaluefallsbetweenthem.

Optimizationswhichimprovetheefficiencyoftime–stampallocationfortypicalprogramstructuresarepre-sented,togetherwithananalysisofthecost.Weshowthatthesizeoftime–stampsismanageableevenforprogramswithlarge,complex,controlstructures.Finallywegiveanexampleoftheuseoftime–stampsinparallelizingasimplecontrolstructure.

1Introduction

OptimisticexecutionschemessuchasTimeWarp[12]whichinvolvecausalityviolationdetectionandrecoveryhavebeensuccessfullyusedforparalleldiscreteeventsim-ulation.Theaimofourresearchistoinvestigatetheuseofsuchtechniquesfortheexecutionofgeneralpurposeprograms.WeareusingtheTimeWarpmechanismasthebasisofanautomaticparallelizationtool.

Themostimportantprinciplethatisencounteredinpar-alleldiscreteeventsimulationisthecausalityprinciple:

1

“Thefuturecannotaffectthepast”.Whereastheconser-vativeapproach[7]strictlyavoidsthepossibilityofanycausalityerroreveroccurring,optimisticmethodsdetectandrecoverfromcausalityerrors.TheTimeWarpmech-anism,basedonthevirtualtimeparadigm,isthemostwell-knownoptimisticprotocol.Thisallowsasimulationobjecttoadvanceintimewithnoregardfortheriskofhavingitssimulatedpastaffected.Ifitspastischanged(duetointeractionwithanobjectfurtherbehindinvirtualtime),itmustbeabletorollback,andthenbeallowedtocontinuealongnewexecutionpaths.

Aneventthatcausesrollbackmayrequirethemech-anismtoperformtwoactions:restoringthestateoftheobjectandcancellingallintermediatesideeffectsby“un-sending”previouslysentmessages[10].Thefirstactionisaccomplishedbyperiodicallysavingtheobject’sstate,andrestoringanoldstateonrollback.“Unsending”apre-viouslysentmessageisaccomplishedbysendingananti–messagethatannihilatestheoriginalwhenitreachesitsdestination.Thisanti–messagemayinturncauseanotherobjectonanotherprocessortorollback.

Eachobjectmustcontainanoutputqueueinwhichitkeepsanegativecopyofthemessagesithasalreadysent,inordertobeabletosendanti–messages.Itmustalsohaveaninputqueueinwhichitkeepsthemessagesithasreceived:someofthesemessagesmayhavebeenprocessedalreadybuttheyarenotdeletedfromthequeuebecauseitmaybenecessarytorollbackandreprocessthem.

Theobjectivesofourresearchintotheuseofoptimisticmechanismsingeneralpurposecomputingaretomakeuseofmoreoftheavailableparallelismthanispossiblewithautomaticparallelizationschemesbasedonstaticprogramanalysisonly.SomeworkhasbeendonebyBacon[2]ontheoptimisticexecutionofCSP(CommunicatingSequen-tialProcesses)[11],buttheuseofoptimisticexecutionasaparallelizationtoolhasbeenlargelyunexplored.

Wecantakeanygeneralpurposecomputationandsplittheprogramintoblocksofcodewhichwillcorrespondtoevents.Thisideaformsthebasisofourresearch[18]intoautomaticprogramparallelization:byassigningatime–stamptoeachprogramcontrolstructure,theprogrammaybeexecutedinparallelusinganoptimisticmechanism,butwillgivethesameresultsasitwoulddoifthecontrolstructureswereexecutedsequentiallyinstricttime–stamporder,inthesamewayasaparallelsimulationusingtheTimeWarpmechanismgivesthesameresultsasasequen-tialone.

Theoptimisticexecutionofaprogramcanparallelizesomecodewhichstaticprogramanalysiswouldindicatewassequential.Theconservativeapproachalwayshastoassumetheworstcase:ifitispossibleforabranchtobetakenitwouldassumethatitisalwaystaken.Theoptimisticapproachcanexecutemoreoftheprograminparallel,butitalsomeansthatitmaydosomeworkwhichitlaterdecidesiswrongbecauseofacausalityviolation.

Theareasforresearchareinreducingtheoverheadofmaintainingtherollbackinformationtoalevelwhereitispracticaltouseforthisapplication.Ingeneratingtime–stampsforprogramconstructswehavetheproblemofneedingtogeneratetime–stampsforunboundedcontrolstructures.Afterabriefdescriptionofourprototypesys-tem,wedescribethetime–stamprequirementsinsection2,andpresentasolutioninvolvingvariable–lengthtime–stampsinsection3.Therestofthepapergoesontoshowtheoptimizationandimplementationofthebasicvariable–lengthscheme.Wefinishwithanexampleoftheuseoftime–stampsinparallelizingasimplecontrolstructure.

1.1Prototypesystem

InthissectionwediscusstheapproachestakeninourimplementationofaprototypesystemfortheoptimisticparallelexecutionofsequentialC++code.Therearetwoapproachestotheoptimisticexecutionofthesequentialprogram:usingpuretime–warpandusingtime–warpcom-binedwithstaticdependencyanalysisoftheprogram.Wecanachievecorrectresultswithapuretime–warpsystemthoughitmayoptimisticallyexecutestaticallydependentcode.Wecancombinestaticprogramdependencyanalysiswithoptimisticexecutionbymakinguseofstaticinforma-tiontoavoidoptimisticallyexecutinganythingwhichhasunconditionalstaticdependencies.

Theprototypesystemmakesuseofsource–to–sourcetransformationsusingthesage++transformationtool[3].ThetransformationsaredirectedbyannotationsaddedtotheC++program.Thisallowsustoinvestigateheuristicsforaddingtheannotationsautomatically.Thepartitioningofobject–orientedprogramsontoprocessorstakesplaceonaperobjectbasis.Theannotatedobjectsaretransformedinto

serverobjectswhichcanthenbeplacedondifferentpro-cessors.Wechoosethehigherlevelobjectsascandidatesforserverobjectstoensureasuitablegranularityoftasks.Alargeenoughlevelofgranularityisnecessaryinordertoachievegoodefficiency.Currentlyobjectplacementisdecidedmanuallyviasource–codeannotations,withaviewtoinvestigatingheuristicsforautomaticobjectplacement.

1.2Serverobjects

AserverobjectisatransformedC++objectwhichisplacedonanodeoftheparallelcomputer.Itsmethodinvocationsaretransformedintomessages.Serverobjectsarethelevelatwhichroll–backismanagedinthesystem.Eachserverobjectmaintainsitsownlocalvirtualclock,androll–backinformation.Serverobjectshaveanindependentthreadofcontrolwhichperformsoptimisticexecutionofmethodinvocationmessages.

Parallelismisintroducedintothesystemviatheasyn-chronousdispatchofmethodinvocationmessages.Meth-odswithreturnvaluesaretransformedtosendbacktheirresultsasynchronously.Considerthefollowingsmallex-amplewiththreematrixobjects,theinvertmemberfunctionreturnstheinvertedmatrix.

classMatrix;{

MatrixA,B,C;A=B.inv();:

A=C.inv();}

Thisistransformedto:

classServer_Matrix;{

Server_MatrixA,B,C;B.inv(A,assign);:

C.inv(A,assign);}

whereServer

next.Severalprocesses,distributedovertheprocessors,maysendarequesttoaserverobject,eachwithadifferenttime–stamp.AdiagramoftheserverobjectsintheexampleandtheasynchronousRPCmessagespassedbetweenthemisshowninfigure1.

Arequest B.inv()requestrequestassign toassign toAAMainand send resultto A as assignrequest C.inv()andsendresult to Aas assignBCFigure1:ServerobjectsforMatrixclassInthetransformedcode,itisnotpossiblefortheserverobjectAtowaitforthemessagerepresentingthereturnvaluefromtherequesttoinvertmatrixBbecausethereturnvaluefromtherequesttoinvertmatrixCmaybereturnedfirst.InsteadwhatisdoneisthatmatrixA,andserverobjectsingeneralactasserversonly:allmessagesarehandledasRPCrequests.

Theprototypesystemdoesnotcurrentlytakeadvantageofexistingparallelizationtechniquesbasedonstaticanal-ysis.Amorecompletesystemwouldincludesuchtech-niquesandonlymakeuseofoptimisticexecutionwheninsufficientparallelismisobtainedfromstaticanalysis.

2Time–stamprequirements

Theconceptofanartificialtime–scalewasoriginallyproposedbyLamport[14]in1978asawayofdefiningaglobalorderingofeventsinaparallelordistributedsystem.Acausalrelationbetweentwoeventsand,suchasthesendingandreceivingofamessage,canberepresentedas

andwesaythathappenedbefore.Eventsandaresaidtobeconcurrentifneithercancausallyaffecttheother,thatis.Thustheorderingofeventsdefinedbythehappenedbeforerelationisapartialordering.

Lamportshowedhowtoextendthispartialorderingtoatotalorderingbyassigningalogicalclockvalueortime–stamptoeacheventinsuchawaythatifthenthetime–stampswillbeordered.Theconverse

isnottrue,doesnotimplythateventcauses

event:allwecansayisthateventmaycauseevent.However,ifthetime–stampsfortwoeventsareequivalent,

,thenweknowthatandmustbeconcurrent,

thatisthereisnocausalrelationbetweenthesetwoevents.Logicalclockshavebeenusedinanumberoftheoreticalandpracticalareas,suchasthemonitoringanddebuggingofparallelsystems[5,8,20].Forsuchapplications,itisusuallypossibletohaveasimpletime–stampallocationscheme,wheretime–stampscanbeallocatedfromase-quenceofintegersintheorderrequired.Althoughsomeextensionsofthisschemehavebeenproposedtoreflectthepartiallyorderednatureoflogicaltime[9],itisstillgener-allythecasethateachprocessmaintainsanintegervaluedcounterforitsownlocaltime.

Inmanyways,thevirtualtimeparadigm[12]isthein-verseofLamport’salgorithm:weassumethateveryeventislabelledwithaclockvaluefromsometotallyorderedtime–scaleinamannerconsistentwithcausality.Apartialorderingmaythenbeobtainedwhichallowsafastcon-currentexecutionofthoseevents.ThisisachievedusinganoptimisticexecutionmechanismsuchasTimeWarp:eachprocessexecuteswithoutregardtowhethertherearesynchronizationconflictswithotherprocesses.Whenacausalityerrorisdetected,aprocessmustberolledbackinvirtualtime,andthenbeallowedtocontinuealongnewexecutionpaths.

Althoughvirtualtimehasbeenusedindistributeddatabaseconcurrencycontrol[16],itsmainsuccesshasbeeninparalleldiscreteeventsimulation[10,13,17,21].Here,theinteractionsbetweentheobjectsofthesimula-tionaremodelledbytheexchangeoftime–stampedeventmessages.TheTimeWarpmechanismallowsdifferentnodesoftheparallelcomputertoexecuteeventsoutoftime–stamporderprovidedthatnocausalrelationexistsbetweenthem.Althougheventsofthesimulationareexe-cutedinparallel,themechanismguaranteesthatthesameresultsareobtainedaswouldbethecasewithasimula-torthatexecutedtheeventssequentiallyinnon–decreasingtime–stamporder.

Withtheoptimisticexecutionofageneralpurposepro-gram,aproblemariseswhichdoesnotoccurinparalleldiscreteeventsimulation:itmaybenecessarytoallocateanarbitrarynumberofnewtime–stampsbetweenanypairofpreviouslyallocatedtime–stamps.Ifweconsiderapro-gramcontrolstructureconsistingofanunboundedloop,wecouldbeexecutingtheindividualiterationsofthatloopononenodewhilstexecutinginparalleltheeventscorre-spondingtothecodefollowingthelooponanothernode.Wethereforeneedtoallocatethetime–stampsfortheeventsfollowingtheloopbeforewehaveallocatedallofthetime–stampsfortheiterationevents.

3

Forthisreasonintheoptimisticparallelexecutionofaprogramthenumberandorderingoftime–stampsisnotknownattime–stampallocationtime.Inthisschemewewouldexpecttomakeaninitialallocationofasequenceoforderedtime–stampsasinthesimplecase.Afterthiswewillberequiredtoallocatesimilarlyorderedsetsoftime–stampswhichfallbetweenpairsofpreviouslyallocatedtime–stamps.Thisprocessispresumedtoberepeatabletoarbitrarydepth.Atime–stampallocationschemewhichisabletomeettheserequirementsmusthavethepropertythatanarbitrarynumberoftime–stampscanbeallocatedbetweenanypairofpreviouslyallocatedtime–stamps.

3Representationoftime–stamps

Forourrepresentationoftime–stampswerequiretheoperationstocompareandgeneratethenexttime–stampinasequencetobeefficient.

Avariablelengthtime–stampisproposedinthispaperwhichsatisfiestheserequirements.Theuseofmulti–leveltime–stampstosub–dividetheeventtime–line[15]foruseintheintegrationofeventsintoactiveobject–orienteddatabasessuggestedtheuseofvariablelengthtime–stamps.Wedefineourvariablelengthtime–stamps:

atime–stampisthepair

wherevalueisabinarynumberoflengthlengthwhosevaluewillbenon–negative.Time–stampscanbeviewedasvariablelengthbinaryfractions,whosevaluesfallintherange0to1.Thefractionalvalueofatime–stampis

arithmetic

0.0

0.000.10

exampleofthetypeofprogramstructureforwhichwewillbegeneratingtime–stamps,consider:loopA(3)

loopB()statementCendend

Thetreerepresentingthesequentialexecutionorderingofthiscodeblock,isshowninfigure3:

PA1A2A3B1B2B1B1B2B3Figure3:Codeblock

PA1B1A2B2B1A3B1B2B3Figure4:Codeblock,asbinarytree

Thisrepresentationallowsthetreetobearbitrarilyex-pandedfortheunboundedloop.ArbitraryN-arytreescanberepresentedbybinarytreeswithoutlossofinformation.Infigure4weshowthesamecodeblockasinfigure3,representedasabinarytreeratherthananN-arytree.

Wecanseethatthebinarytreerepresentationshowninfigure4makesitpossibleforustoassigntime–stampsfromthetime–stamptreeinfigure2.Allweneedtodoisassignthecorrespondingtime–stampforeachtreenode.

Usingthisschemeitispossibletoassigntime–stampsforarbitraryprogramscontaininganynumberofun-boundedconstructs.However,thenumberofbitsrequiredtorepresentthetime–stampvariesaswherenisthenumberofiterationsoftheloop.Soforexample,aloop

A(128)requiresasequencevaluewith128bits.Thisisacostlysolution,intermsofbitspertime–stamp.

5Optimizationoftime–stamps

Forloopswithfixedbounds,andforsequences,weknowthatwerequiretime–stamps,forsomefixedn.Wecanusethisinformationtouselessbitspertime–stamp.Togeneratetime–stampsforparenttime–stampwecreateacompletetreerootedatwithdepthlogthenallocatethentime–stampsastheleafnodesin2.Wethistree.Weareabletoreducetheextrabitsrequiredforaloop

orsequenceofsizefrombitstolog2

bits.5.1

Unboundedloops

Forunboundedloopswecannotpredictthenumberof

time–stampstoallocate.Weallocateaninitialamountoftime–stampswhere2andisthenumberofbitswhichwillbeusedbytheinitialtime–stampallocation.Weusethefirsthalfofthesetime–stampsforthefirst21time–stamps.Ifmoretime–stampsarerequiredwecreatecompletebinarytreesofdepthunderalloftheremaining21time–stamps.Thiswillcreate221additionaltime–stamps.Weagainusethefirsthalfofthese(222)andreservethesecondhalfforfurthertime–stamps.

Thechoiceofisimportantinthisschemeastheeffi-ciencyofdynamicallocationcomparedtothestaticalloca-tionusedforfixedboundloopsdependsonthechoiceof.

Wedefinethecostofanallocationschemeasthenum-berofbitsusedtorepresenttime–stampsinthatscheme.Wealsodefinetheefficiencyoftheallocationastheactualnumberoftime–stampsuseddividedbythetotalnumberoftime–stampsavailableforthatcost,thatis:

2static

Thecostinbitsdynamicandefficiencyofdynamicallo-cationdynamicisgivenby:

dynamic

dynamic

where,thenumberoflevelsofdynamicallocationre-quiredis:

static

as

wordsarerequiredtostoreavalueoflengthlength.

Wecandefineanefficientfunctiontocomparetime–stampswhichcomputes:

6

1

2

1

2

iff

and

1

1

2

1

2

iff

oror

0and

0

voidproc(doublev[]){

for(inti=0;v[i]v[i]=func(v[i]);

if(i>0&&v[i]<0){

v[i]=v[i-1];}}}

i++)//loop

//statementA//condition//statementB

11

11

and,recursively

2

2

Generatingtime–stampsfortheunboundedloop,witha

3:valueof

Formanyprograms,itwillonlybenecessarytouse

time–stampswith.Togiveanideaofthecomplexityofprogramwhichcanberepresentedwiththesetime–stampsbeforeanextendedlengthtime–stampisre-quired,consider:

loop0.000

0.00100

0.010

0.01100

0.100000

0.10000100

condition0.00001

0.00110

0.01001

0.01110

0.10000001

0.10000110

looprecur(A)endend

Withachoiceof6fordynamicloopallocation,andassumingawordsize32,therecursioncouldreachdepth1,000inafixedloopof1,000,000beforeanextendedtime–stampwouldberequired.

Withdoublelengthtime–stampsmorecomplexstruc-turesarepossible:

Eachelementofarrayvwillbetransformedtobecomeanobjectwithalocalclock.Thethreestatementswithintheloophavetime–stampsoftheform:

0.x00

0.x10

where0.xisthetime–stampofthecontainingloop,andthestatementnumberisshowninsmalltype.

Thetransformation(stylised)forthisexampleusesserverobjectsfortheelementsofthearray,andhasserverobjectswhichprovidethefunctionalityofrollbackablecon-trolflowstatements.Parallelismisintroducedintothesystembytheasynchronousdispatchofserverobjectin-vocationmessages.Asdescribedinsection1.2,messagesarenotwaitedforasthiswouldblocktheserverobject:toavoidwaiting,methodswithreturnvaluesaretransformedtohaveextraparametersgivingaserverobjecttowhichtosendtheresultandthemethodtoinvokewiththatresult.Intheexampletransformationthereareserverobjectsfortheelementsofthearrayvandfortheloopindexvari-ablei.Theforandifcontrolconstructsusethevaluesofserverobjectsandsomustbeabletorollback,thisisachievedbyusingserverobjectstorepresentthem.Serverobjectsareusedbecauseanyactionwhichmayneedtoberolledbackisrepresented,atleastconceptually,asames-sage.Theactionmaythenberolledbackbysendingananti–message,andre–executedbyreprocessingthemes-sage.AdiagramoftheserverobjectsintheexampleandtheasynchronousRPCmessagespassedbetweenthemisshowninfigure6.7

looprecur(A)

loopendendend

Forafixedloopof1,000,000andrecursionof30,000theunboundedloopcouldreachiteration1,000,000beforeitwouldberequiredtoextenditfurther.

7Example

Weconsiderasimpleexamplewhichhasaconditionaldependency.Staticanalysisofthiscodewouldrevealthattheloophasapossibledependencyandhencemustbeex-ecutedsequentially.Theoptimisticexecutionofthisloopcanignorethepossibledependencyandhenceparallelizetheloop.Theloopisunboundedaswedonotknowatcom-piletimehowmanyiterationsoftheloopwillberequired.

classServer_Double;classServer_Int;classServer_If1;classServer_For1;classServer_Func;

Server_For1::iter1(){//RPCsendvaluetofunci.read(func,arg1);Server_If1if1(i,v);i.read(if1,eval1);//RPCtoreadii.operator++();//RPCtoincrementii.read(for1,next1);//RPCtoreadi}

Server_For1::next1(inti_val){

v[i_val].read(for,next2);}

Server_For1::next2(doublev_i_val){

if(v_i_valiter1();//RPCtoselfnextiter}}

Server_If1::eval1(inti_val){

if(i_val>0){

v[i_val].read(if1,eval2);}}

Server_If1::eval2(inti_val,doublev_i_val){

if(v_i_val<0){

then1(i_val);}}

Server_If1::then1(inti_val){//RPCtoassigntov[i]v[i_val-1].read(v[i_val],assign);}

Server_Func::arg1(inti_val){

v[i_val].read(func,call);}

Server_Func::call(inti_val,doublev_i_val){//RPCsendresulttov[i]func(v_i_val,v[i_val]);}

voidproc(Server_Double&v[]){

Server_Inti(0);

Server_Funcfunc(v);

Server_For1for1(i,v,func);i.read(for1,next1);}

proc10iter11read9next2for18read523411next1readreadreadi++func6arg1i1918177assigncallreadeval116v[0]13readassignv[1]...if114eval212then115readFigure6:AsynchronousmessagepassingInthediagramthemessagesarelabelledwiththeRPCfunctiontheyrequest,soforexampletheRPCmessagere-questingtheinvocationoftheiter1methodofthefor1serverobjectislabellediter1.Thedottedpathsdrawnthroughserverobjectboxesrepresentthemessagessentasaresultofinvokingtherequestedmethod.Wewilldescribethemessagesinthesystemonapermethodbasis.Notethatthemessagescorrespondingtotheconstructionoftheserverobjectsarenotshowninthediagram.

ThemainthreadsendsareadRPCmessage(1)totheiserverobject,requestingthattheresultbesenttofor1::next1.Wheni::readsendsitsvaluebacktofor1::next1itisusedtosendtheRPCforv[i]::read,withtherequestthatthevalueofv[i]readbesenttofor1::next2.Ifthevalueofv[i]giventofor1::next2satisfiesv[i]If1::eval1requeststhevalueofv[i]inmessage(13),thevalueofiischosentobe1inthediagramsothevalueofv[1]isaskedfor.Therequestforthevalueofv[1]specifiesthattheresultbesenttoif1:eval2,thisallowstheif1serverobjecttoresumethelogicoftheifstatementwhenthevalueofv[i]hasbeenobtained.It8

mayserveotherRPCrequestsbeforereceivingthevalueofv[i].Iftheconditionoftheifstatementissatisfied,if1sendsitselfathen1RPC(12),toinvokethethenpartofthecode.Themethodif1::then1requestsanassignment(15)ofv[i-1]tov[i].

Thiswillrepeatitselfbysendingthemessage(5)tothefor1server.Thetestforterminationisinthemethodfor1::next2whichsendsamessagetoinvokeoptimisticexecutionofsequentialprogramsandtoexploreheuristicsforreducingoverhead.Wehavedemonstratedtheneedforaflexibletime–stampgenerationschemeandhavepresentedasolutionwhichsupportstheoptimisticexecutionofgeneralpurposeprograms.

References

for1::iter1ifanotheriterationisrequired.Inthiswayifaniterationoftheloopturnsoutnottohavebeenrequired,thenitwillberolledbackbythesendingofananti–messagetothefor1server.Thedisjointednatureofthemethodsoftheserverobjectsisrequiredtoallowasynchronousreadingofthereturnvalues.Itisnotknownwhichreturnvaluewillcomebackfirst,soallreturnval-uesaretreatedasstandardrequestsandarehandledbytheserverobjectasRPCrequests.

8Conclusions

Theproblemsoftime–stampgenerationforunboundedcontrolstructuresareaddressedinthispaper.Anallocationschemewhichusesvariable–lengthtime–stampshasbeenpresentedinwhichitispossibletoallocateanarbitrarynumberoftime–stampsbetweenanypairofexistingtime–stamps.Optimizationshavebeenpresented,togetherwithananalysisoftheefficiencyofsuchoptimizations.Thisshowsthatformanyprograms,asinglewordissufficientfortherepresentationofthetime–stampvalues.Evenwhenanextendedtime–stampisrequired,theoperationsofgen-eratingandcomparingtime–stampscanbeimplementedefficiently.

Onemeasureoftheimportanceofparallelanddis-tributedsimulationhasbeenitsinfluenceonotherbranchesofcomputerscience,suchasconcurrencytheory[6].Thispaperhasshownhowitispossibletoextendthevirtualtimeparadigmofoptimisticsimulationtotheexecutionofgeneralpurposeprograms.Byassigningtime–stampstoprogramcontrolstructures,aconventionalobject-orientedprogrammaybeexecutedinparallelusingtheTimeWarpmechanism,withaguaranteethatthesameresultsareob-tainedaswouldbethecaseiftheprogramwasexecutedsequentially.Wearecurrentlyimplementingaparalleliz-ingcompilerwhichconvertsconventionalcodeintoaformwhichhascallstoaparallelrun–timesystemwhichimple-mentstheoptimisticmechanism,usingthelightweightp4[1,4,19]clustermodelofparallelcomputing.

Thisresearchisanattempttoovercomethebarriersim-posedbytheoverlypessimisticviewstaticanalysisimposesonprogramswhosebehaviourcannotbefullypredictedatcompiletime.Ourimplementationoftheprototypesystemshouldenableustoinvestigatethelikelyefficiencyofthe

9

[1]ABackandSJTurner.Portabilityandparallelism

withlightweightp4.InBCSPPSGConferenceonGeneralPurposeParallelComputing,1993.[2]DBacon.Optimisticparallelizationofcommunicat-ingsequentialprocesses.InProceedingsofthe3rdACMSymposiumonthePrinciplesandPracticeofParallelProgramming,pages155–166,1991.[3]FBodin,PBeckman,DGannon,JGotwals,

SNarayana,SSrinivas,andBWinnicka.Sage++:Anobject–orientedtoolkitandclasslibraryforbuildingfortranandC++restructuringtools.ObjectOrientedNumerics(OON-SKI),1994.[4]JBoyle,RButler,TDisz,BGlickfeld,ELusk,

ROverbeek,JPatterson,andRStevens.PortableProgramsforParallelProcessors.Holt,Rinehart,andWinston,1987.[5]WCaiandSJTurner.Anapproachtotherun-time

monitoringofparallelprograms.ComputerJournal,37(4):333–345,1994.[6]KMChandy.Keynoteaddress.ParallelandDis-tributedSimulationConference,1993.[7]KMChandyandJMisra.Distributedsimula-tion:Acasestudyindesignandverificationofdis-tributedprograms.IEEETrans.SoftwareEngineer-ing,SE5(5):440–452,1979.[8]CJFidge.ReproducibletestsinCSP.TheAustralian

ComputerJournal,19(2):92–98,1987.[9]CJFidge.Logicaltimeindistributedsystems.Com-puter,pages28–33,1991.[10]RMFujimoto.Paralleldiscreteeventsimulation.

CommunicationsoftheACM,33(10):30–53,1990.[11]CHoare.CommunicatingSequentialProcesses.Pren-ticeHall,1985.[12]DRJefferson.Virtualtime.ACMTransactionson

ProgrammingLanguagesandSystems,7(3):404–425,1985.[13]JPL.TimeWarpOperatingSystemUser’sManual.

JetPropulsionLaboratory,1991.[14]LLamport.Time,clocks,andtheorderingofevents

inadistributedsystem.CommunicationsoftheACM,21(7):558–565,1978.[15]BLingsandLFoster.Atemporalmodelforactive

object-orienteddatabases.Technicalreport,ExeterUniversity,R284,1993.[16]MLivesey.Distributedvarimisticconcurrencycon-trolinapersistentobjectstore.Technicalreport,Uni-versityofSt.Andrews,1990.[17]MPresley,MEbling,FWieland,andDJeffer-son.Benchmarkingthetimewarpoperatingsystemwithacomputernetworksimulation.InProcedingsSCSDistributedSimulationConference,pages8–13,1989.[18]SJTurnerandABack.Generalpurposeoptimistic

parallelcomputing.InProceedingsof7thPARSYSUserGroupMeeting,1994.[19]SJTurnerandABack.AT9000implementationof

thep4parallelprogrammingmodel.InProceedingsoftheNorthAmericanTransputerUserGroup,pages305–316.IOSPress,1994.[20]SJTurnerandWCai.The‘logicalclocks’approachto

thevisualizationofparallelprograms.InPerformanceMeasurementandVisualizationofParallelSystems(edsGKotsisandGHaring),pages45–66.Elsevier,1993.[21]SJTurner,MDamitio,andSTrivett.Distributed

simulationwithatransputerversionofthetimewarpoperatingsystem.InProceedingsofTransputers’94,pages39–54.IOSPress,1994.

10