47-How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs.pdf_第1页
47-How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs.pdf_第2页
全文预览已结束

付费下载

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论