47-How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs.pdf

IEEETRANSACTIONSONCOMPUTERS,VOL.C-28,NO.9,SEPTEMBER1979REFERENCES1C.Black,C.-E.Sundberg,andW.K.S.Walker,Developmentofaspacebornememorywithasingleerroranderasurecorrectionscheme,inConf.Rec.,1977Fault-TolerantComputingSymp.,FTCS-7,June1977,pp.50-55.2C.Blacketal.,Highlyreliablesemiconductormemoryfortheon-boardcomputer,FinalRep.ESTECContr.2528/75/HP,BritishAircraftCorp.,Bristol,England.3R.W.Lucky,J.Salz,andE.J.Weldon,Jr.,PrinciplesofDataCommunication.NewYork:McGraw-Hill,1968.4W.W.PetersonandE.J.Weldon,Jr.,Error-CorrectingCodes,2ndEd.Cambridge,MA:MITPress,1972.5M.Y.Hsiao,AclassofoptimalminimumoddweightcolumnSEC/DEDcodes,IBMJ.Res.Develop.,pp.395-401,July1970.6G.Longo,Algebraiccodingandcombinatorics:Atutorialsurvey,NATOAdvancedStudyInstitute,Darlington,England,Aug.8-20,1977,Conf.Rec.,Sijthoff&Noordhoff,1978,seriesE,no.25,-pp.151-169.7E.R.Berlekamp,AlgebraicCodingTheory.NewYork:McGraw-Hill,1968.8R.P.Capece,Memory-richminisgetaggressive,Electronics,pp.69-70,Aug.18,1977.9H.J.HelgertandR.D.Stinaff,Minimumdistanceboundsforbinarylinearcodes,IEEETrans.InformationTheory,vol.IT-19,pp.344-356,May1973.10C.-E.Sundberg,Sometransparentshortenedcodesforsemiconductormem-ories,TelecommunicationTheory,Univ.ofLund,Lund,Sweden,Tech.Rep.TR-91,Sept.1977.11Erasuresanderrorsdecodingforsemiconductormemories,IEEETrans.Comput.,vol.C-27,pp.696-705,Aug.1978.12W.C.CarterandC.E.McCarthy,Implementationofanexperimentalfault-tolerantmemorysystem,IEEETrans.Comput.,vol.C-25,pp.557-568,June1976.ofeachindividualprocessordoesnotguaranteethatthemulti-processorcomputerissequentiallyconsistent.Inthisbriefnote,wedescribeamethodofinterconnectingsequentialprocessorswithmemorymodulesthatinsuresthesequentialconsistencyoftheresultingmultiprocessor.Weassumethatthecomputerconsistsofacollectionofproces-sorsandmemorymodules,andthattheprocessorscommunicatewithoneanotheronlythroughthememorymodules.(Anyspecialcommunicationregistersmayberegardedasseparatememorymodules.)Theonlyprocessoroperationsthatconcernusaretheoperationsofsendingfetchandstorerequeststomemorymod-ules.Weassumethateachprocessorissuesasequenceofsuchrequests.(Itmustsometimeswaitforrequeststobeexecuted,butthatdoesnotconcernus.)Weillustratetheproblembyconsideringasimpletwo-processmutualexclusionprotocol.Eachprocesscontainsacriticalsection,andthepurposeoftheprotocolistoinsurethatonlyoneprocessmaybeexecutingitscriticalsectionatanytime.Tcess1ifb=0thencriticalsection；else.fiHowtoMakeaMultiprocessorComputerThatCorrectlyExecutesMultiprocessProgranmLESLIELAMPORTAbstract-Manylargesequentialcomputersexecuteoperationsinadifferentorderthanisspecifiedbytheprogram.Acorrectexecutionisachievediftheresultsproducedarethesameaswouldbeproducedbyexecutingtheprogramstepsinorder.Foramultiprocessorcomputer,suchacorrectexecutionbyeachprocessordoesnotguaranteethecorrectexecutionoftheentireprogram.Additionalconditionsaregivenwhichdoguaranteethatacomputercorrectlyexecutesmultiprocessprograms.IndexTerms-Computerdesign,concurrentcomputing,hardwarecorrectness,multiprocessing,parallelprocessing.Ahigh-speedprocessormayexecuteoperationsinadifferentorderthanisspecifiedbytheprogram.Thecorrectnessoftheexecutionisguaranteediftheprocessorsatisfiesthefollowingcondition:theresultofanexecutionisthesameasiftheopera-tionshadbeenexecutedintheorderspecifiedbytheprogram.Aprocessorsatisfyingthisconditionwillbecalledsequential.Con-sideracomputercomposedofseveralsuchprocessorsaccessingacommonmemory.Thecustomaryapproachtodesigningandprovingthecorrectnessofmultiprocessalgorithms1-3forsuchacomputerassumesthatthefollowingconditionissatisfied:theresultofanyexecutionisthesameasiftheoperationsofalltheprocessorswereexecutedinsomesequentialorder,andtheoperationsofeachindividualprocessorappearinthissequenceintheorderspecifiedbyitsprogram.Amultiprocessorsatisfyingthisconditionwillbecalledsequentiallyconsistent.ThesequentialityManuscriptreceivedSeptember28,1977；revisedMay8,1979.TheauthoriswiththeComputerScienceLaboratory,SRIInternational,MerlsPark,CA94025.process2b:=1；ifa=0thencriticalsection；b=0else.fiTheelseclausescontainsomemechanismforguaranteeingeven-tualaccesstothecriticalsection,butthatisirrelevanttothediscussion.Itiseasytoprovethatthisprotocolguaranteesmu-tuallyexclusiveaccesstothecriticalsections.(Devisingaproofprovidesaniceexerciseinusingtheassertionaltechniquesof2and3,andislefttothereader.)Hence,whenthistwo-processprogramisexecutedbyasequentiallyconsistentmultiprocessorcomputer,thetwoprocessorscannotbothbeexecutingtheircriti-calsectionsatthesametime.Wefirstobservethatasequentialprocessorcouldexecutetheb:=1andfetchboperationsofprocess1ineitherorder.(Whenprocesslsprogramisconsideredbyitself,itdoesnotmatterinwhichorderthesetwooperationsareperformed.)However,itiseasytoseethatexecutingthefetchboperationfirstcanleadtoanerror-bothprocessescouldthenexecutetheircriticalsectionsatthesametime.Thisimmediatelysuggestsourfirstrequirementforamultiprocessorcomputer.RequirementRl:Eachprocessorissuesmemoryrequestsintheorderspecifiedbyitsprogram.SatisfyingRequirementRIiscomplicatedbythefactthatstor-ingavalueispossibleonlyafterthevaluehasbeencomputed.Aprocessorwilloftenbereadytoissueamemoryfetchrequestbeforeitknowsthevaluetobestoredbyaprecedingstorerequest.Tominimizewaiting,theprocessorcanissuethestorerequesttothememorymodulewithoutspecifyingthevaluetobestored.Ofcourse,thestorerequestcannotactuallybeexecutedbythememorymodule,untilitreceivesthevaluetobestored.0018-9340/79/0900-0690$00.75C)1979IEEE690IEEETRANSACTIONSONCOMPUTERS,VOL.c-28,NO.9,SEPTEMBER1979RequirementRIisnotsufficienttoguaranteecorrectexecution.Toseethis,supposethateachmemorymodulehasseveralports,andeachportservicesoneprocessor(orI/Ochannel).Letthevaluesofaandbbestoredinseparatememorymodules,andconsiderthefollowingsequenceofevents.1)Processor1sendsthea=1requesttoitsportinmemorymodule1.Themoduleiscurrentlybusyexecutinganopera-tionforsomeotherprocessor(orI/Ochannel).2)Processor1sendsthefetchbrequesttoitsportinmemorymodule2.Themoduleisfree,andexecutionisbegun.3)Processor2sendsitsb=1requesttomemorymodule2.Thisrequestwillbeexecutedafterprocessorlsfetchbrequestiscompleted.4)Processor2sendsitsfetcharequesttoitsportinmemorymodule1.Themoduleisstillbusy.Therearenowtwooperationswaitingtobeperformedbymemorymodule1.Ifprocessor2sfetchaoperationisper-formedfirst,thenbothprocessescanentertheircriticalsectionsatthesametime,andtheprotocolfails.Thiscouldhappenifthememorymoduleusesaroundrobinschedulingdisciplineinser-vicingitsports.Inthissituation,anerroroccursonlyifthetworequeststomemorymodule1arenotexecutedinthesameorderinwhichtheywerereceived.Thissuggeststhefollowingrequirement.RequirementR2:MemoryrequestsfromallprocessorsissuedtoanindividualmemorymoduleareservicedfromasingleFIFOqueue.Issuingamemoryrequestconsistsofenteringtherequestonthisqueue.ConditionRIimpliesthataprocessormaynotissueanyfur-thermemoryrequestsuntilafteritscurrentrequesthasbeenenteredonthequeue.Hence,itmustwaitifthequeueisfull.Iftwoormoreprocessorsaretryingtoenterrequestsinthequeueatthesametime,thenitdoesnotmatterinwhichordertheyareserviced.Note.Ifafetchrequeststhecontentsofamemorylocationforwhichthereisalreadyawriterequestonthequeue,thenthefetchneednotbeenteredonthequeue.Itmaysimplyreturnthevaluefromthelastsuchwriterequestonthequeue.ORequirementsRIandR2insurethatiftheindividualproces-sorsaresequential,thentheentiremultiprocessorcomputerissequentiallyconsistent.Todemonstratethis,onefirstintroducesarelation-onmemoryrequestsasfollows.DefineA-+Bifandonlyif1)AandBareissuedbythesameprocessorandAisissuedbeforeB,or2)AandBareissuedtothesamememorymodule,andAisenteredinthequeuebeforeB(andisthusexecutedbeforeB).ItiseasytoseethatRIandR2implythat-+isapartialorderingonthesetofmemoryrequests.Usingthesequentialityofeachprocessor,onecanthenprovethefollowingresult:eachfetchandstoreoperationfetchesorstoresthesamevalueasifalltheoperationswereexecutedsequentiallyinanyordersuchthatA-*BimpliesthatAisexecutedbeforeB.Thisinturnprovesthesequentialconsistencyofthemultiprocessorcomputer.RequirementR2statesthatamemorymodulesrequestqueuemustbeservicedinaFIFOorder.Thisimpliesthatthememorymodulemustremainidleiftherequestattheheadofitsqueueisastorerequestforwhichthevaluetobestoredhasnotyetbeenreceived.ConditionR2canbeweakenedtoallowthememorymoduletoserviceotherrequestsinthissituation.Weneedonlyrequirethatallrequeststothesamememorycellbeservicedintheorderthattheyappearinthequeue.Requeststodifferentmemorycellsmaybeservicedoutoforder.Sequentialconsistencyispreservedbecausesuchaservicepolicyislogicallyequivalenttoconsideringeachmemorycelltobeaseparatememorymodulewithitsownrequestqueue.(Thefactthatthesemodulesmaysharesomehardwareaffectstherateatwhichtheyservicere-questsandthecapacityoftheirqueues,butitdoesnotaffectthelogicalpropertyofsequentialconsistency.)Therequirementsneededtoguaranteesequentialconsistencyruleoutsometechniqueswhichcanbeusedtospeedupindivi-dualsequentialprocessors.Forsomeapplications,achievingse-quentialconsistencymaynotbeworththepriceofslowingdowntheprocessors.Inthiscase,onemustbeawarethatconventionalmethodsfordesigningmultiprocessalgorithmscannotbereliedupontoproducecorrectlyexecutingprograms.Protocolsforsynchronizingtheprocessorsmustbedesignedatthelowestlevelofthemachineinstructioncode,andverifyingtheircorrectnessbecomesamonumentaltask.REFERENCES1E.W.Dijkstra,Hierarchicalorderingofsequentialprocesses,ActaInformatica,vol.1,pp.115-138,1971.2L.Lamport,Provingthecorrectnessofmultiprocessprograms,IEEETrans.SoftwareEng.,vol.SE-3,pp.125-143,Mar.1977.3S.OwickiandD.Gries,Verifyingpropertiesofparallelprograms:anaxiomaticapproach,Commun.Assoc.Comput.Mach.,vol.19,pp.279-285,May1976.CommentsonAnApproachtoHighlyIntegratedComputer-MaintainedCellularArraysVISHWANID.AGRAWALAbstract-Theabovepaperdescribesmachinesconstructedonfaultylogicarrays.Thesemachinesusesomeorallofthegoodcellsthatformaconnectivecluster.Itispointedoutherethatwhenthefaultycellsarerandomlydistributedoverthearray,thepropagationofafreelyexpandingsignal,whichmustavoidthefaultycells,isa