25-A Preliminary Architecture for a Basic Data-Flow Processo.pdf

APreliminaryArchitectureforaBasicData-FlowProcessorJackB.DennisandDavidP.MisunasProjectMACMassachusettsInstituteofTechnologyAbstract:Aprocessorisdescribedwhichcanachievehighlyparallelexecutionofprogramsrepresentedindata-flowform.Thelanguageimplementedincorporatesconditionalanditerationmechanisms,andtheprocessorisasteptowardapracticaldata-flowprocessorforaFortran-leveldata-flowlanguage.Theprocessorhasauniquearchi-tecturewhichavoidstheproblemsofprocessorswitchingandmemory/processorinterconnecionthatusuallylimitthedegreeofrealizableconcurrentprocessing.Thearchitectureoffersanunusualsolutiontotheproblemofstruc-turingandmanagingatwo-levelmemorysystem.IntroductionStudiesofconcurrentoperationwithinacomputersys-temandoftherepresentationofparallelisminapro-grarmminglanguagehaveyieldedanewformofprogramrepresentation,knownasdataflow.Executionofadata-flowprogramisdata-driven；thatis,eachinstruc-tionisenabledforexecutionjustwheneachrequiredoperandhasbeensuppliedbytheexecutionofaprede-cessorinstruction.Data-flowrepresentationsforpro-gramshavebeendescribedbyKarpandMiller8,Rod-riguezIll,Adamsi,DennisandFosseen5,Bhrs21,Kosinski9,101,andDennis4.Wehavedevelopedanattractivearchitectureforapro-cessorthatexecuteselementarydata-flowprograms6,7.TheclassofprogramsimplementedbythisprocessorcorrespondstothemodelofKarpandMiller81.Thesedata-flowprogramsarewellsuitedtorepresentingsig-nalprocessingcomputationssuchaswaveformgeneration,modulationandfiltering,inwhichagroupofoperationsistobeperformedonceforeachsample(intime)ofthesignalsbeingprocessed.Thiselementarydata-flowpro-cessoravoidstheproblemsofprocessorswitchingandprocessor/memoryinterconnectionpresentinattemptstoadaptconventionalYonNeumantypemachinesforparallelcomputation.Sectionsofthemachinecommunicatebythetransmissionoffixedsizeinformationpackets,andthemachineisorganizedsothatthesectionscantoleratedelaysinpackettransmissionwithoutcompromisingef-fectiveutilizationofthehardware.Wewishtoexpandthecapabilitiesofthedata-flowarchitecturewiththeultimategoalofdevelopingageneralpurposeprocessorusingageneralizeddata-flowlanguagesuchasdescribedbyDennis4,Kosinski9,101andBhrs21.Asanintermediatestep,wehavede-velopedapreliminarydesignforabasicdata-flowpro-cessorthatexecutesprogramsexpressedinamorepower-fullanguagethantheelementarymachine,butstillnotachievingageneralizedcapability.ThelanguageofthebasicmachineisthatdescribedbyDennisandFosseen51,andincludesconstructsforexpressingconditionalanditerativeexecutionofprogramparts.Inthispaperwepresentsolutionstothemajorproblemsfacedinthedevelopmentofthebasicmachine.Astraightforwardsolutiontotheincorporationofdecis-ioncapabilitiesinthemachineisdescribed.Inaddi-tion,thegrowthinprogramsizeandcomplexitywiththeadditionofthedecisioncapabilityrequiresutilizationofatwo-levelmemorysystem.Adesignispresentedinwhichonlyactiveinstructionsareintheoperationalmemoryoftheprocessor,andeachinstructionisbroughttothatmemoryonlywhennecessaryforprogramexecution,andremainsthereonlyaslongasitisbeingutilized.TheworkreportedherewassupportedbytheNationalScienceFoundationunderresearchgrantGJ-34671.126TheElementaryProcessorTheElementaryProcessorisdesignedtoutilizetheele-mentarydata-flowlanguageasitsbaselanguage.Apro-gramintheelementarydata-flowlanguageisadirectedgraphinwhichthenodesareoperatorsorlinks.Thesenodesareconnectedbyarcsalongwhichvalues(conveyedbytokens)maytravel.Anoperatoroftheschemaisenabledwhentokensarepresentonallinputarcs.Theenabledoperatormayfir._atanytime,removingtheto-kensonitsinputarcs,computingavaluefromtheoper-andsassociatedwiththeinputtokens,andassociatingthatvaluewitharesulttokenplacedonitsoutputarc.Aresultmaybesenttomorethanonedestinationbymeansofalinkwhichremovesatokenonitsinputarcandplacestokensonitsoutputarcsbearingcopiesoftheinputvalue.Anoperatororalinkcannotfireun-lessthereisnotokenpresentonanyoutputarcofthatoperatororlink.Anexampleofaprogramintheelementarydata-flowlan-guageisshowninFigureIandrepresentsthefollowingsimplecomputation:inputa,by:=(a+b)/xx:=(a*(a+b)+boutputy,xLIL2All+L3-MA21/+IA4yFigureI.Anelementarydata-flowprogram.datapacketsOperationUnit0OperationUnltm-IIInstruction_Cell0-iMemoryInstructionJ_Celln-Ii4JoperationpocketsFigure2.Organizationoftheelementarydata-flowprocessor.TherectangularboxesinFigure1areoperators,andeacharithmeticoperatorintheabovecomputationisreflectedinacorrespondingoperatorintheprogram.Thesmalldotsarelinks.Thelargedotsrepresenttokensholdingvaluesfortheinitialconfigurationoftheprogram.IntheprogramofFigureI,linksLIandL2areinitiallyenabled.ThefiringofLImakescopiesofthevalueaavailabletooperatorsA1andA3；firingL2presentsthevaluebtooperatorsAIandA4.OnceLiandL2havefired(inanyorder),operatorA1isenabledsinceitwillhaveatokenoneachofitsinputarcs.AfterAIhasfired(completingthecomputationofa+b),linkL3willbecomeenabled.ThefiringofL3willenabletheconcurrentfiringofoperatorsA2andA3,andsoon.Thecomputationsrepresentedbyanelementaryprogramareperformedinadata-drivenmanner；theenablingofanoperatorisdeterminedonlybythearrivalofvaluesonallinputlinks,andnoseparatecontrolsignalsareutilized.Suchaschemapromptedthedesignofapro-cessororganizedasinFigure2.Adata-flowschematobeexecutedisstoredintheMe_.m-oryoftheprocessor.TheMemoryisorganizedintoInstructionCells,eachCellcorrespondingtoanopera-torofthedata-flowprogram.EachInstructionCell(Figure3)iscomposedofthreeregisters.Thefirstregisterholdsaninstruction(Figure4)whichspeci-fiestheoperationtobeperformedandtheaddress(es)ofthereglster(s)towhichtheresultoftheoperationistobedirected.Thesecondandthirdregistersholdtheoperandsforuseinexecutionoftheinstruction.WhenaCellcontainsaninstructionandthenecessaryop-erands,itisenabledandsignalstheArbitrationNetworkthatitisreadytotransmititscontentsasanoperationacetoanOperationUnitwhichcanperformthedesiredfunction.TheoperationpacketflowsthroughtheArbi-datapocketdatapacketrlstructionCellregistertinstructinregister,operond,registerII:operandR.operationpacketfromInstructionCelIstoOperationUnitsFigure5.StructureoftheArbitrationNetwork.tratlonNetworkwhichdirectsittoanappropriateOpera-tionUnitbydecodingtheinstructionportionofthepack-et.TheresultofanoperationleavesanOper&tionUnitasoneormoredat_.!packets,consistingofthecomputedvalueandtheaddressofaregisterintheMemorytowhichthevalueistobedelivered.TheDistibutionNetworkacceptsdatapacketsfromtheOperatlonUnitsandutilizestheaddressofeachtodirectthedataitemthroughthenetworktothecorrectregisterintheMemory.TheInstructionCellcon-tainingthatregistermaythenbeenabledifaninstruc-tionandalloperandsarepresentintheCell.ManyInstructionCellsmaybeenabledsimultaneouslysanditisthetaskoftheArbitrationNetworktoefficientlydeliveroperationpacketstoOperationUnitsandtoqueueoperationpacketswaitingforeachOperationUnit.AstructurefortheArbitrationNetworkprovidingapathforoperationpacketsfromeachInstructionCelltoeachOp-erationUnitispresentedinFigure5.EachArbitrationUnitpassespacketsarrivingatitsinputportsone-at-a-timetoitsoutputporttusingaround-robindisciplinetoresolveanyambiguityaboutwhichpacketsshouldbesentnext.ASwitchUnitassignsapacketatitsinputtooneofitsoutputportssaccordingtosomepropertyofthepacketsinthiscasetheoperationcode.TheDistributionNetworkissimilarlyorganizedusingSwitchUnitstoroutedatapacketsfromtheOperationUnitstotheMemoryRegistersspecifiedbythedestina-tionaddresses.AfewArbitratlonUnitsarerequiredsodatapacketsfromdifferentOperationUnitscanenterthenetworksimultaneously.SincetheArbitrationNetworkhasmanyinputportsandonlyafewoutputports,therateofpacketflowwillbemuchgreaterattheoutputports.Thussaserialrep-resentationofpacketsisappropriateattheinputportstominimizethenumberofconnectionstotheMemory,butamoreparallelrepresentationisrequiredattheoutputportssoahighthroughputmaybeachieved.Hencesserlal-to-parallelconversionisperformedinstageswithintheArbitrationNetwork.Similarlyparallel-to-serialconversionofthevalueportionofeachresultpacketoccurswithintheDistributionNetwork.TheOperationUnitsoftheprocessorarepipelinedinioperationcodedestinationI2J,.A-specializedfunctionoperationunitdestinationFigure3.OperationofanInstructionCell.127Figure4.Instructionformat.(o)datalink(b)controllinkFigure6.Linksofthebasicdata-flowlanguage.ordertoallowmaximumthroughput.Thedestinationad-dress(es)ofaninstructionareenteredintoidentitypipelinesoftheOratlonUnitsandareutilizedtoformdatapacketswiththeresultwhenitappears.Amoredetailedexplanationoftheelementaryprocessoranditsoperationisgivenin6.Wehavecompleteddesignsforallunitsoftheelementaryprocessorintheformofspeed-lndependentinterconnectionsofasmallsetofbasicasynchronousmoduletypes.Thesedesignsarepresentedin7.TheBasicData-FlowLanguaReOursuccessinthearchitectureoftheelementarydata-flowprocessorledustoconsiderapplyingtheconceptstothearchitectureofmachinesformorecompletedata-flowlanguages.Forthefirststepingeneralization,wehavechosen,a.classofdata-flpwprogramsthatcorre-spondtoaformaldata-flowmodelstudiedbyDennisandFosseen5.Therepresentationofconditionalsanditerationindata-flowformrequiresadditionaltypesoflinksandactors.Thetypesoflinksandactorsforthebasicdata-flowlanguageareshowninFigures6and7.Datavaluespassthroughdatalinksinthemannerpre-sentedpreviously.Thetokenstransmittedbycontrollinksareknownascontroltokens,andeachconveysavalueofeithert.rueorfalse.Acontroltokenisgener-atedatadeciderwhich,uponreceivingvaluesfromitsinputarcs,appliesitsassociatedpredicate,andproduceseithera.rueorfalsecontroltokenatitsoutputarc.ThecontroltokenproducedatadecidercanbecombinedwithothercontroltokensbymeansofaBooleanoperator(Figure7f),allowingadecisiontobebuiltupfromsimplerdecisions.COntroltokensdirecttheflowofdatatokensbymeansofT-gates,F-gates,ormergeactors(Figure7c,d,e).AT-gatepassesthedatatokenonitsinputarctoitsoutputarcwhenitreceivesacontroltokenconveyingnFigure8.Dota-flowrepresentationofthebasicprogram.(o)operotor(b)decider(c)T-gate(d)F-gateoI,v,-,l(e)merge(f)booleanoperatorFigure7.Actorsofthebasicdata-flowlanguage.thevaluetrueatitscontrolinput.Itwillabsorbthedatatokenonitsinputarcandplacenothingonitsout-putarcifafalse-valuedcontroltokenisreceived,Similarly,theF-gatewillpassitsinputdatatokentoitsoutputarconlyonreceiptofafalse-valuedtokenonthecontrolinput.Uponreceiptofatrue-valuedto-ken,itwillabsorbthedatatoken.Amergeactorhasatrueinput,afalseinput,andaOontro.linput.Stpassestoitsoutputarcadatatokenfromtheinputarccorrespondingtothevalueofthecontroltokenreceived.Anytokensontheotherinputarenotaffected.Aswiththeelementaryschemas,allnkoractorisnotenabledtofireunlessthereisnotokenonanyofitsoutputarcs.Usingtheactorsandlinksofthebasicdata-flowlan-guage,conditionalsanditerationcanbeeasilyrepre-sented.Inillustration,Figure8givesabasicdata-flowprogramforthefollowingcomputation:inputy,xn:=0whileyxdqy:=y+xn:=n+lendoutputy,nThecontrolinputarcsofthethreemergeactorscarryfalse-valuedtokensintheinitialconfigurationsotheinputvaluesofxandyandtheconstant0areadmittedasinitialvaluesfortheiteration.Oncethesevalueshavebeenreceived,thepredicateyxistested.Ifitistrue,thevalueofxandthenewvalueforyarecycledbackintothebodyf)ftheiterationthroughtheT-gatesandtwomergenodes.Concurrently,theremainingT-gateandmergenodereturnanincrementedvalueoftheiterationcountn.Whentheoutputofthedeciderisfalse,thecurrentvaluesofyandnaredeliveredthroughthetwoF-gates,andtheinitialconfigurationisrestored.TheBasicData-FlowProcessorTwoproblemsmustbefacedinadaptingthedesignofthe128elementarydata-flowprocessorforbasicdata-flowpro-grams.Thefirsttaskistoexpandthearchitectureoftheelementarymachinetoincorporatedecisioncapabilitybyimplementingdeciders,gatesandmerges.Afairlystraightforwardsolutiontothisproblemwillbepre-sented.However,incontrasttoelementarydata-flowprograms,thenodesofabasicdata-flowprogramdonotfireequallyoftenduringexecution.Ascomputationpro-ceeds,differentpartsoftheprogrambecomeactiveorquiescentasiterationsareinitiatedandcompleted,andasdecisionsleadtoselectionofalternatepartsofaprogramforactivation.ThusitwouldbewastefultoassignaCelltoeachinstructionforthedurationofprogramexecution.Thebasicdata-flowprocessormusthaveamulti-levelmemorysystemsuchthatonlytheac-tiveinstructionsofaprogramoccupytheInstructionCellsoftheprocessor.Inthefollowingsectionswefirstshowhowdecisioncapabilitymayberealizedbyaugmentingtheelementaryprocessor；thenweshowhowanauxiliarymemorysystemmaybeaddedsotheInstructionCellsactasacacheforthemostactiveinstructions.DecisionCapabilityTheorganizationofabasicdata-flowprocessorwithoutthetwo-levelmemoryisshowninFig.9.Asintheele-mentaryprocessor,eachInstructionCellconsistsofthreeRegistersandholdsoneinstructiontogetherwithOperationUnitsDecisionUnitsNetwork1-.-1-jcello.j=iInstructionco,o,tIFigure9.Organizationofabasicdata-flowprocessorwithouttwo-levelmemory.Thegatingcodespermitrepresentationofgateactorsthatcontroltereceptionofoperandvaluesbytheop-eratorordeciderrepresentedbytheInstructionCell.spacesforreceivingitsoperands.Eachinstructioncar-Themeaningsofthecodevaluesareasfollows:respondstoanoperator,adecider,oraBooleanoperatorcodevaluemeaninEtheassociatedoperandisnotgated.n_qtrueanoperandvalueisacceptedbyarri-valofatruegatepacket；discardedbyarrivalofafalsegatepacket.falseanoperandvalueisacceptedbyarri-valofafalsegatepacket；discardedbyarrivalofatruegatepacket.constheoperandisaconstantvalue.Thestru=tureofadataorcontrolreceiver(Fig.Ii)providesspacetoreceiveadataorBooleanvalue,andtwoflagfieldsinwhichthearrialofdataandcontrolpacketsisrecorded.Thegateflaischangedfromof_totrueorfalsebyatrueorfalsegate-typecuntroipacket；thevalueflagischangedfromofftoo_nnbyadatapacketorvaluetypecontrolpacketaccordingtothetypeofreceiver.(a)operators(b)deciderso1*lIOpdlIprdl,glvlID92v2DglvlD92v2(C)BooleanoperatorsandcontroldistributioniIbotldIB9Iclt2d2i,BJ92c2t3d3-opID91Idld2vltldlprt2d2glIvlttldLbot2d2BgLclt3d3op-operationcodepr-predicatecodebo-BooleanoperationcodetinstructioncodesdI,d2,d5destinationaddressestL,t2,t3resulttogs9I,g2gatingcodesvI,v2datareceiversCI,C2controlreceiversFigureI0.InstructionCellformatsforthebasicprocessor.ofabasicdata-flowprogram.Thegateandmergeactorsofthedata-flowprogramarenotrepresentedbyseparateinstructions；rather,thefunctionofthegatesisincor-poratedintotheinstructionsassociatedwithoperatorsanddecidersinamannerthatwillbedescribedshortly,andthefunctionofthemergeactorsisimplementedforfreebythenatureoftheDistributionNetwork.InstructionsthatrepresentoperatorsareinterpretedbytheOperationUnitstoyielddatapacketsasintheele-mentaryprocessor.InstructionsthatrepresentdecidersorBooleanoperatorsareinterpretedbytheDecisionUnitstoyieldcontrolpacketshavingoneofthetwoforms,true1ifalse,yalue,true1Agate-typecontrolpacketperformsagatingfunctionattheaddressedoperandregister.Avalue-typecontrolpacketprovidesaBooleanoperandvaluetoanInstructionCellthatrepresentsaBooleanoperator.ThesixformatsforthecontentsofInstructionCellsinthebasicprocessoraregiveninFigureI0.TheuseofeachRegisterisspecifiedinitsleftmostfield:IinstructionregisterDoperandregisterfordatavaluesBoperandregisterforBooleanvaluesOnlyRegistersspecifiedtobeoperandregistersofcon-sistenttypemaybeaddressedbyinstructionsofavalidprogram.TheremainingfieldsintheInstructionCellformatsare:aninstructioncode,op,prorbo,thatidentifiestheclassandvariationoftheinstructionintheCell；fromonetothreedestinationaddressesdl,d2,d3thatspeci-fytargetoperandregistersforthepacketsgeneratedbyinstructionexecution；inthecaseofdecidersandBooleanoperators,aresulttadtl,t2,t3foreachdestinationthatspecifieswhetherthecontrolpacketisofgate-type(tag=mate)orofvaluetype(tag=value)；and,foreachoperandregister,aatingcodegl,g2andeitheradatareceivervl,v2oracontrolreceivercl,c2.129Receiver:fIILvalue(dataOrBoolean)c-valueflagoffnovaluereceivedLonvaluereceivedfof._f_nogate-typecontrolpacketreceivedgateflagtru._._.etruegate-typecontrolpacketreceivedfalsefalsegate-typecontrolpacketreceivedFigureI1.Structureandstatesofreceivers.InstructionCellOperationThefunctionofeachInstructionCellistoreceivedataandcontrolpackets,and,whentheCellbecomesenabled,totransmitanoperationordecisionpacketthroughtheArbitrationNetworkandresettheInstructionCelltoitsinitialstatus.AnInstructionCellbecomesenabledjustwhenallthreeofitsregistersareenabled.Areg-isterspecifiedtoactasaninstructionregisterisal-waysenabled.Registersspecifiedtoactasoperandreg-isterschangestatewiththearrivalofpacketsdirectedtothem.ThestatetransitionsandenablingrulesfordataoperandregistersaredefinedinFig.12.InFig.12thecontentsofanoperandregisterarerep-resentedasfollows:D,(off,of_at)ttttDgatingcodeno:l-Jemptyttrue:(true,o_.n)filledandenabledgateflogJregisteruseindicatorTheasteriskindicatesthattheRegisterisenabled.Eventsdenotingarrivalofdataandcontrolpacketsarelabelledthus:ddatapacketttruegate-typecontrolpacketffalsegate-typecontrolpacketWiththisexplanationofnotation,thestatechangesandenablingrulesgiveninFig.12shouldbeclear.SimilarrulesapplytothestatechangesandenablingofBooleanoperandregisters.Notethatarrivalofagate-typecon-trolpacketthatdoesnotmatchthegatingcodeoftheRegistercausestheassociateddatapackettobediscar-D,n:(of_f,off)lld,(off,o_.)*fD.tru._e:(off,off).-e,.(true,off)jdh(true,on)-.df(flseff)/J-/-td.(off,)77-.LffdD,false:(off,of)-o,-(false,off)r-.-.b(false,on)zT-dL(tue%JD,con_._:(of._f,on)*Figure12.Statetransitionandenablingrulesfordataoperandregisters.$30ded,andresetstheRegistertoitsstartingcondition.TheoperationpacketssenttoOperationUnitsanddeci-sionpacketssenttoDecisionUnitsconsistoftheen-tirecontentsoftheInstructionCellexceptforthegatingcodesandreceiverstatusfields.Thusthepack-etssentthroughtheArbitrationNetworkhavethefol-lowingformats:TotheOperationUnits:op,vl,v2,dlop,vl,dl,d2TotheDecisionUnits:pr,vl,v2,tl,dlpr,vl,tl,dl,t2,d2bo,cl,c2,tl,dl,t2,d2,t3,d3bo,cl,tl,dl,t2,d2,t3,d3AninitialconfigurationofInstructionCellscorrespon-dingtothebasicdata-flowprogramofFig.8isgiveninFig.13.Forsimplicity,Cellscontainingcontroldistributionanddataforwardinginstructionsarenotshown.Instead,wehavetakenthelibertyofwritinganynumberofaddressesinthedestinationfieldsofinstructions.TheinitialvaluesofxandyareplacedinRegisters2and5.Cellsiand2,containingthesevalues,arethenenabledandpresenttotheArbitrationNetworktheoperationpacketsident；,ii,14andThesepacketsaredirectedtoanidentityOperationUnitwhichmerelycreatesthedesireddatapacketswiththevaluesofxandyanddeliversthepacketstotheDistributionNetwork.UponreceiptbytheMemoryofthedatapacketsdirectedtoRegisters7and8,cell3willbeenabledandwilltransmititsdecisionpackettoaDecisionUnittoper-formthelessthanfunction.TheresultofthedecisionwillbereturnedthroughtheControlNetworkasfivecon-trolpackets.Iftheresultistrue,Cells4,5and6willbeenabledandwillsendtheircontentsthroughthecellIO0I-ident(8,11,14)02Dn_oxcell512lplus(7,15,20)13Dtrue(-)14Ono(-)cell2031-ident(7,13,20)04I05Dn_.ycelI615plus(16,25)16Dtrue017DconsIcell306Ilessgate(11,13,16,20,23)07Dno(-)08iDn._(-)Icell718Iprint()19Dconsi20IDifalse(-)cell409II-lident8,11,14)I0IIIDtru._._e(-)212223cell8iprint()DconsDJfalse(-)Figure13.InstructionCellinitializationforthebasicdata-flowprograminFigure8.ArbitrationNetworktoOperationUnitscapableofper-formingtheidentityandadditionoperations.Iftheresultofthedecisionisfalse,outputcells7and8willbeenabled,andcells4,5,and6willhavetheirgatedoperandsdeleted.Two-LevelMemoryHierarchyThehighlevelofparallelactivityachievableindata-flowprocessorsmakesauniqueformofmemoryhierarchyfeasible:theInstructionCellsarearrangedtoactasacacheforthemostactiveinstructionsofthedata-flowprogram.Individualinstructionsareretrievedfromauxiliarymemory(theInstructionMemory)astheybecomerequiredbytheprogressofcomputation,andin-structionsarereturnedtotheInstructionMemorywhentheInstructionCellsholdingthemarerequiredformoreactivepartsoftheprogram.Theorganizationofabasicdata-flowprocessorwithInstructionMemoryisgiveninFig.14.InstructionMemoryTheInstructionMemoryhasastoragelocationforeachpossibleregisteraddressofthebasicprocessor.Thesestoragelocationsareorganizedintogroupsofthreelocationsidentifiedbytheaddressofthefirstlocationofthegroup.EachgroupcanholdthecontentsofoneInstructionCellintheformatsalreadygiveninFig.I0.Amemorycommandpacketa,retrpresentedtothecom-mannportoftheInstructionMemory,requestsretriev-alofaninstructionpacketa,xinwhichxistheCellcontentsstoredinthegroupoflocationsspecifiedbyaddressa.TheinstructionpacketisdeliveredattheretrieveportoftheInstructionMemory.Aninstructionpacketa,xpresentedatthestoreportoftheInstructionMemoryrequestsstorageofCellcon-tentsxinthethree-locationgroupspecifiedbyaddressa.However,thestorageisnoteffectiveuntilamemorycommandpacketa,storei8receivedbytheInstructiondatapacketsOperationUnitsDecisioncontrolUnitspocketsControlNetworkoperationpacketsdecisionpacketsCeilsCellBlock0MemoryCellBlockk-IinstructionpacketsMemoryCommandNetworkinstructionpacketsmemorycommandpacketscommandIretrievestore,InstructionMemoryFigure14.Organizationofthebasicdata-flowprocessorwithauxiliarymemory.131Memoryatitscommandport,andanypriorretrievalre-.questhasbeenhonored.Similarly,retrievalrequestsarenothonoreduntilpriorstoragerequestsforthegrouphavetakeneffect.WeenvisionthattheInstructionMemorywouldbede-signedtohandlelargenumbersofstorageandretrievalequestsconcurrently,muchastheinput/outputfacilitiesofcontemporarycomputersystemsoperateundersoftwarecontrol.CellBlockOperationForapplicationofthecacheprincipletothebasicdata-flowprocessor,anInstructionMemoryaddressisdividedintoamajoraddressandaminoraddress,eachcontaininganumberofbitsoftheaddress.OneCellBlockoftheprocessorisassociatedwitheachpossiblemajoraddress.Allinstructionshavingthesamemajoraddressarepro-cessedbytheInstructionCellsofthecorrespondingCellBlock.ThustheDistributionandControlNetworksusethemajoraddresstodirectdatapackets,controlpackets,andinstructionpacketstotheappropriateCellBlock.ThepacketsdeliveredtotheCellBlockincludetheminoraddress,whichissufficienttodeterminehowthepacketshouldbetreatedbytheCellBlock.OperationanddecisionpacketsleavingaCellBlockhaveexactlythesameformatasbefore.InstructionpacketsleavingaCellBlockhavetheformm,xwheremisaminoraddressandxisthecontentsofanInstructionCell.ThemajoraddressoftheCellBlockisappendedtoeachinstructionpacketasittravelsthroughtheAr-bitrationNetwork.Inthesameway,memorycommandpacketsleavetheCellBlockwithjustaminoraddress,whichisaugmentedbythemajoraddressoftheCellBlockduringitstripthroughtheMemoryCommandNetwork.Fig.15showsthestructureofaCellBlock.EachIn-structionCellisabletoholdanyinstructionwhosema-joraddressisthatoftheCellBlock.SincemanymoreinstructionsshareamajoraddressthanthereareCellsinaCellBlock,theCellBlockincludesanAssociationTablewhichhasanentrym,i)foreachInstructionCel%:mistheminoraddressoftheinstructiontowhichtheCellisassigned,andiisaCellstatusindicatorwhosevalueshavesignificanceasfollows:statusvaluemeanlnfreetheCellisnotassignedtoanyin-structionenaedtheCellhasbeenengagedforthein-structionhavingminoraddressm,byarrivalofadataorcontrolpacketoccupiedtheCellisoccupiedbyaninstructionwithminoraddressmTheStackelementofaCellBlockholdsanorderingoftheInstructionCellsascandidatesfordisplacementoftheircontentsbynewlyactivatedinstructions.OnlyCellsinoccupiedstatusarecandiatesfordisplacement.OperationofaCellBlockcanbespecifiedbygivingtwoprocedures-oneinitiatedbyarrivalofadataorcon-trolpacketattheCellBlock,andtheotheractivatedbyarrivalofaninstructionpacketfromtheInstructionMemory.Procedurei:ArrivalofadataorcontrolpacketIn,y)wherenisaminoraddressandyisthepacketcon-tent.stepI.DoestheAssociationTablehaveanentrywithminoraddressn?Ifso,letpbetheCellcorre-spondingtotheentry,andgotostep5.Otherwisecontinuewithstep2.step2.IftheAssociationTableshowsthatnoInstruc-tionCellhasstatusfree,gotostep3.OtherwiseletpbeaCellwithstatusfree.LettheAssocia-LControlNetTkIeontrolpockets-tAssociotiOIo0-odataTablepockets,pocketsdecisionpacketsDistributionArbitrationNetworkNetworkinstructioninstructionpacketsc2JApocketsINetworkFilure15.StructureofeCellBlock.tlonTa61eentryforpbem,free；gotostep4.step3.UsetheStacktochooseaCellpinoccupiedstatusforpreemption；lettheAssociationTableentryforpbem,occupie.d；transmitthecon-tentszofCellpasaninstructionpacketm,ztotheInstructionMemoryviatheArbitrationNet-work；transmitthememorycormmandpacketm,store)totheInstructionMemorythroughtheMemoryCom-mandNetwork.step4.Makeanentryn,enKagedforCellpintheAssociationTable；transmitthememorycozmandpacketn,re.trtotheInstructionMemoryviatheMemoryCommandNetwork.step5.UpdatetheoperandregisterofCellphavingminoraddressnaccordingtothecontentyofthedataorcontrolpacket(therulesforupdatingarethosegiveninFig.12).IfCellpisoccupiedthestatechangeoftheregistermustbeconsis-tentwiththeinstructioncodeortheprogramisinvalid.IfCellpisengaged,thechangesmostbeconsistentwiththeregisterstatusleftbyprecedingpacketarrivals.step6.IfCellpisoccupiedandallthreeregis:ersareenabled(accordingtotherulesofFig,12),theCellpisenabled:transmitanoperationorde-cisionpackettotheOperationUnitsorDecisionUnitsthroughtheArbitrationNetwork；leaveCellpinoccupiedstatusholdingthesameinstructionwithitsoperandregistersreset(receiversemptywiththegateandvalueflagssettoof_l).ChangetheorderofCellsintheStacktomakeCellpthelastcandidatefordisplacement.Procedure2:ArrivalofaninstructionpacketIn,xwithminoraddressnandcontentx.steI.LetpbetheInstructionCellwithentryn,engagedintheAssociationTable,st2.ThestatusoftheoperandregistersofCellpmustbeconsistentwiththecontentxofthein-structionpacketsortheprogramisinvalid.Up-datethecontentsofCellptoincorporatethein-structionandoperandstatusinformationinthein-structionpacket.step3.ChangetheAssociationTableentryforCellpfromn,engagedton,occup