1994. Compiler Transformations for High-Perforamce Computing, страница 19

Figure61 is a block diagramof the architectureand its primarydatapaths.Table A.1 describes the instructionset.All instructionsare 32 bits and must beword-aligned.TheimmediateoperandACMComputingSurveys,Vol.26,No.4, December1994408*DavidF. Baconet al.-.IIntegerUnit32BranchUnit*64 bytedline? _3232 Int Registers“1024 lines32Load/StoreUnit64from RAM memory64 KB Cache323264-&64*AddrXlation~4-way setassociatives-l*32 FP Registers*~Pg$64—FloatingPoint UnitFigure61.S-DLXTable A.1.ExampleInstr.LW Rl,30(R2)SW 500(R4),LIRI,R3#666MeaningSimdarLoad wordLoad float(LF)Store wordMemory [500+R41 +R3Store float(SF)Load ImmediateRI-666Load upperR2MoveADD RI,R2,WJLT RI,ADDI RI,R3R2,SLL RI>SLLIR3R2,R2,RI,#3R3R2,SLT RI,R2,#3R3The S-DLX InstructIon SetRI +-Memory [30+R2]#666RI,immediateR1*R2+R3MultlplyR1-R2xR1-R2+3SUBI , WJLTI , DIVIleft logicalRI+R2<<R3ShiftShiftleft immediateRI+R2<JAL labelJumpand linkJALR R2Jumpand link(SRL)RI+lSEQ, SNE,lmmedlateRI-OSLE,SGE, SGT andformsPCt-R3registerR31+PC+4;PCt-labelR31+PC+4,PC+-R2BranchIf equal zeroIf (R4=O) PC+--labelBranchIf not equal zero (BIfEZ)Branchif floatingIf (FPCR) PCtlabelBranchif floatingAddMultiplyfalsefloatMultiply-AddTest equal floatSubtractfloat (SUBF)Divide float (DIVF)FltF2+F3FltF2xF3floatEQF Fl,floatFltFl+(F2x26, No 4, DecemberF3)If (F1=F2) FPCR +’-1else FPCR +0field is 16 bits.

The address for load andstore instructionsis computedby addingthe 16-bit immediateoperandto the register. To create a full 32-bit constant,thelow 16 bits must first be set with a loadimmediate(Ll) instructionthat clears theVolpoint(BFPF)trueHAF F1, F2> F3Surveys,logicalPCelabelregisterComputingrightSRLI3If (R2<R3)Set less thanpointACM(SUB)(DIV)immediateJumpF2DivideAddJumpADDF Fl,F2, F3f’lWLTF F1 , F2 , F3SubtractR3ShiftJR R3labelt--666R11,5 31AddJ labelBEQZ R4,instructionsR1+R2registerelseBFPT labeldiagram,NameMOV RI,LUIfunctional1994LTF , GTF,LEF , GEF, IiEFhigh 16 bits; then the high 16 bits mustbe set with a load upper immediate(LUI)instruction.The programcounter is the special register PC. Jumpsand branchesare relative to PC + 4; jumps have a 26-bit signedCompilerTable A.2.ExampleLVVI,RIuws VI.iSV VI.SUBVSUBVSSUBSVI SVLR(RI.

R2)RIV1,VIV1;MeaningV1+-VLRLoadvectorregisterLoadvectorwithvectorregisterI StoreVlt-evervstrideI Vector-vectorsubtractionI V..-..V2.F1/ Vector-scalarsubtractionI VI[1.F1 ;V2I Scalar-vectorsubtractionI VI [1 . .VLR]I SetvectorlengthregisteratHI[RI]II. . . . ... VLR]WC.+V2t-Fi-V2[l.VLR]I DIVSVI VLR+RIDLXFor vectorizingtransformations,use a version of DLX extended409R2ffi word forI HIR1] -VLRoffset, and brancheshave a 16-bit signedoffset. Integerbranchestest the GPRs forzero; floating-pointbranchestest a specialfloating-pointconditionregister(FPCR).There is no branch delay slot. Becausethe numberof instructionsexecutedpercycle varies on a superscalarmachine,itdoes not make sense to have a fixed number of delay slots. The numberof delayslots is also heavilydependenton thepipelinedepth, which may vary from onechip generationto the next.Instead,staticbranchpredictionisused: forwardbranchesare alwayspredictedas nottaken,andbackwardbranchesare predictedas taken.If thepredictionis wrong,there is a one-cycledelay.Floating-pointdividestake14 cyclesand all otherfloating-pointoperationstake four cycles, except when the resultis used by a store operation,in whichcase they take three cycles.

A load thathits in the cache takes two cycles; if itmisses in the cache it takes16 cycles.Integermultiplicationtakes two cycles.All other instructionstake one cycle.When a load or store is followedby anintegerinstructionthat modifiesthe address register,the instructionsmay beissued in the same cycle. If a floatingpointstore is followedby an operationthat modifiesthe registerbeing stored,the instructionsmay also be issued inthe same cycle.A.2 VectorSlmllarwordsV2, V3Ri●V-DLX Vector InstructIonsNameInstr.Transformationswe willto includevectorsupport.Thisnew architecture,V-DLX,has eight vector registers,eachof which holds a vector consistingof upto 64 floating-pointnumbers.The vectorfunctionalunits performall their operationson data in the vectorand scalarregisters.We discussonly the functionalunitsthatperformfloating-pointaddition,multiplication,and division,thoughvector machinestypicallyhave units to performintegerand logicaloperationsaswell.

V-DLX issues only one scalar or onevector instructionper cycle, but nonconflictingscalar and vector instructionscanoverlap each other.A specialregister,the vector lengthregister(VLR), controlsthe numberofquantitiesthat are loaded, operated upon,or stored in any vectorinstruction.Bysoftwareconvention,the VLR is normallyset to 64, except when handlingthe lastfew iterationsof a loop.The vector operationsare describedinTable A.2. They include arithmeticoperations on vector registersand load/storeoperationsbetweenvector registersandmemory.Vector operationstake place eitherbetweentwovectorregistersorbetweena vectorregisterand a scalarregister.In the lattercase, the scalarvalue is extendedacross the entirevector. All vector computationshave a vector registeras the destination.The speed of a vectoroperationdepends on the depth of the pipelinein itsimplementation.The first result appearsafter some numberof cycles (calledthestartuptime).

Afterthe pipelineis full,one result is computedper clock cycle. InACMComputmgSurveys.Vol.26,No.4, December1994410David●Table A.3.[et al.Startup Times in Cycles on V-DLXOperationI Start-Up~I VectorF. BaconTimeI,Load12 jthe meantime,the processorcan continue to execute other instructions.TableA.3 gives the startuptimes for the vectoroperationsin V-DLX.These times shouldnot be compareddirectlyto the cycletimesfor operationson S-DLXbecausevectormachinestypicallyhave higherclock speeds thanmicroprocessors,althoughthis gap is closing.A large factorin the sQeed of vectorarchitec~uresis their mem’ory system.

VDLX has eight memorybanks. After theload latency,data is suppliedat the rateof one word per clock cycle, providedthatthe stridewithwhichthe data is accessed does not cause bank conflicts(seeSection 6.5.1).Currentexamplesof vectormachinesare the Cray C-90 [Oed 1992] and IBMES 9000 Model 900 VF [Gibsonand Rao1992].A.3 MultiprocessorsWhen multipleprocessorsare employedto executea program,manyadditionalissues arise. The most obviousissue ishow much of the underlyingmachinearchitectureto expose to the programmer.At one extreme,the programmercanmake explicituse of hardware-supportedoperationsby programmingwithlocks,fork/joinprimitives,barriersynchronizations,and message send and receive.These operationsare typicallyprovidedas system calls or libraryroutines.System call semanticsare usuallynot defined by the language,makingit difficultforthecompilertooptimizethemautomatically.High-levellanguagesfor large-scaleparallelprocessingprovide primitivesforexpressingparallelismin one of two ways:control parallelor data parallel.FortranACMComputmgSurveys,Vol.26,No.4, December199490 arraysectionexpressionsare examples of explicitlydata paralleloperations.APL [Iverson1962] also containsa widevarietyof data-parallelarrayoperators.Examplesof control-paralleloperationsarecobegin/ coendblocksanddoacrossloops [Cytron19861.For both shared- and distributed-memory multiprocessors,we assume that theprogrammingenvironmentinitializesthevariablesPn urn to be the total numberofprocessorsand Pid to be the numberofthe local processor.Processorsare numbered startingwith O.A.3.

1 Shared-MemoryDLX MultiprocessorsMX is our prototypicalshared-memoryparallelarchitecture.It consists of 16 SDLXprocessorsand 512MBof sharedmain memory.The processorsand memory system are connectedtogetherby abus. Each processorhas an intelligentcache controllerthat monitorsthe bus (asnoopy cache). The caches are the sameas on S-DLX,except that they contain256KB of data.

The bandwidthof the busis 128 megabytes/second.Theprocessorssharethememoryunits;a programrunningon a processorcan access any memoryelement,and thesystem ensures that the values are maintainedconsistentlyacross the machine.Withoutcaching,consistencyis easy tomaintain;everymemoryreferenceishandledby the main memorycontroller.However,performancewould be very poorbecause memory latenciesare already toohigh on sequentialmachinesto run wellwithouta cache; having many processorssharea commonbus wouldmaketheproblemmuch worse by increasingmemory access latencyand introducingbandwidth restrictions.The solutionis to giveeach processora cache thatis smartenough to resolve referenceconflicts.A snoopy cache implementsa sharingprotocol that maintainsconsistencywhilestill minimizingbus traffic.A processorthat modifiesa cache line invalidatesallother copies and is said to own that cacheline.Thereare a varietyof cache coherencyprotocols[Stenstrom1990;CompilerTable A.4,TypeMemory reference latency in sMXof MemoryReference/ Cycles]I21Read value owned by ‘ othermocessorI1; iRead value nobody“II20 IDrocessorI18Read value availablein local cacheownsWritevalue owneri locallyWritevalue ownedWritevalue nobody1by other;wns1‘22Eggersand Katz 1989], but the detailsare not relevantto this survey.