An Instruction Fetch Unit for a High-Performance Personal Computerby Butler W. Lampson, Gene A. McDaniel and Severo M. OrnsteinJanuary 1981ABSTRACTThe instruction fetch unit (IFU) of the Dorado personal computer speeds up the emulation ofinstructions by pre-fetching, decoding, and preparing later instructions in parallel with theexecution of earlier ones. It dispatches the machine's microcoded processor to the properstarting address for each instruction, and passes the instruction's fields to the processor ondemand. A writeable decoding memory allows the IFU to be specialized to a particularinstruction set, as long as the instructions are an integral number of bytes long. There areimplementations of specialized instruction sets for the Mesa, Lisp, and Smalltalk languages.The IFU is implemented with a six-stage pipeline, and can decode an instruction every 60 ns.Under favorable conditions the Dorado can execute instructions at this peak rate (16 mips).This paper has been submitted for publication.CR CATEGORIES6.34, 6.21KEY WORDS AND PHRASEScache, emulation, instruction fetch, microcode, pipeline.c Copyright 1981 by Xerox Corporation. XEROXPALO ALTO RESEARCH CENTER3333 Coyote Hill Road / Palo Alto / California 94304ЪНЇО\█pТ─НЇОY>П"НЇОRдqТXП;НЇОLJНЇОCБrНЇО@ЇsТ▐tsТ░П4НЇО?3ТЇТ╦ПNНЇО=╞Т°Т²П?НЇО<+Т▓П)Т⌠П-НЇО:їТеП)ТфtsП"НЇО9# Т≤Т≥ПBНЇО7÷Т²П4Т·НЇО6Т┴tsП9Т┼НЇО4≈Т─ПVНЇО1luП.НЇО-ЁrНЇО*┬s НЇО%ЭrНЇО"яsП9НЇОNvwtП$НЇОкwТXН)XО▄xН)aОqН)aО└rТGП0ьTVk(║AN INSTRUCTION FETCH UNIT FOR A HIGH-PERFORMANCE PERSONAL COMPUTER221. IntroductionThis paper describes the instruction fetch unit (IFU) for the Dorado, a powerful personal computerdesigned to meet the needs of computing researchers at the Xerox Palo Alto Research Center.These people work in many areas of computer science: programming environments, automatedoffice systems, electronic filing and communication, page composition and computer graphics, VLSIdesign aids, distributed computing, etc. There is heavy emphasis on building working prototypes.The Dorado preserves the important properties of an earlier personal computer, the Alto [13], whileremoving the space and speed bottlenecks imposed by that machine's 1973 design. The history,design goals, and general characteristics of the Dorado are discussed in a companion paper [8],which also describes its microprogrammed processor. A second paper [1] describes the memorysystem. The Dorado is built out of ECL 10K circuits. It has 16-bit data paths, 28 bit virtual addresses, 4K-16K words of high-speed cache memory, writeable microcode, and an I/O bandwidth of 530Mbits/sec. Figure 1 shows a block diagram of the machine. The microcoded processor can executea microinstruction every 60 ns. An instruction of some high level language is performed byexecuting a suitable succession of these microinstructions; this process is called emulation.<==М{ТXП!НЇО;бwТ≥П>Т НЇО:>Т─П4НґО7ФП%НґО5▌ПDНґО36НґО0чНЇО-ЁТжП1ТвП%НЇО,/Т┼П9Т▀НЇО*╚Т║Т╒ПTНЇО)'{wТ▐ПBТ░НЇО'ёТёТєПDНЇО& Т╞ПAТ╟НЇО$⌡ТуТжП:НЇО#Т└ПaНЇО!⌠ТяПVТрНЇО Т▀П;Т▄П#НЇО▀Т┘ПGТ├НЇОТ─НЇОэТ├Т┤ПBНЇОXТ╠П!Т╡{wНЇОтТ┌Т┐ПGНЇОP Т│П4Т┌П&НЇОлТ█Т▌П<НЇОHТ─ПUНЇОТ├П=Т┤ywП"НЇО ≥Т║ПHТ╒НЇОТ│ПZТ┌НЇО ▒Т╚ПCТ╛НЇО ywТ╣П]НЇО┴Т─{ wywП=ЗTVk(╡AN INSTRUCTION FETCH UNIT FOR A HIGH-PERFORMANCE PERSONAL COMPUTER26The EU demands instructions from the IFU at an irregular rate, depending on how fast it is able toabsorb the previous ones. A simple machine must completely process an instruction beforedemanding the next one. In a machine with multiple functional units, on the other hand, the firststage in the EU waits until the basic resources required by the instruction (adders, result registers,etc.) are available, and then hands it off to a functional unit for execution. Beyond this point theoperation cannot be described by a single pipeline, and complete execution of the instruction maybe long delayed, but even in this complicated situation the IFU still sees the EU as a single consumerof instructions, and is unaware of the concurrency which lies beyond.Under this umbrella definition for an IFU, a lot can be sheltered. To illustrate the way an IFU canaccommodate specific language features, we draw an example from Smalltalk [5]. In this language,the basic executable operation is applying a function f (called a method) to an object o: f(o, . . .).The address of the code for the function is not determined solely by the static program, butdepends on a property of the object called its class. There are many implementation techniques forfinding the class and then the function from the object. One possibility is to represent a class as ahash table which maps function names (previously converted by a compiler into numbers) into codeaddresses, and to store the address of this table in the first word of the object. The rather complexoperation of obtaining the hash table address and searching the table for the code addressassociated with f, is in the proper domain of an IFU, and removes a significant amount ofcomputation from the processor. No such specialization is present in the Dorado's IFU, however.2.3 Pipelining instruction fetchesFor the sake of definiteness, we will assume henceforth that the smallest addressable unit in the code is a byte;the memory delivers data in units called words, which are larger than bytes;an instruction (and its addresses, immediate operands, and other fields) may occupy one ormore bytes, and the first byte determines its essential properties (length, number of fields,etc.).Matters are somewhat simplified if the addresssable unit is the unit delivered by the memory or ifinstructions are all the same length, and somewhat complicated if instructions may be any numberof bits long. However, these variations are inessential and distracting.The operation of instruction fetching divides naturally into four stages:Generating addresses of instruction words in the code, typically by sequentially advancing aprogram counter, one memory word at a time.Fetching data from the code at these addresses. This requires interactions with themachine's memory in general, although recently used code may be cached within the IFU.Such a cache looks much like main memory to the rest of the IFU.Decoding instructions to determine their length and internal structure, and perhaps whetherthey are branches which the IFU should execute. Decoding changes the representation ofthe instruction, from one which is compact and convenient for the compiler, to one whichis convenient for the EU and IFU.Formatting the fields of each instruction (addresses, immediate operands, register numbers,mode control fields, or whatever) for the convenience of the EU; e.g., extracting fields ontothe EU's data busses.Buffering may be introduced between any pair of these stages, either the minimum of one itemrequired to separate the stages, or a larger amount to increase the elasticity. Note that an item mustbe a word early in the pipe (at the interface to the memory), must be an instruction late in the pipe(at the interface to the EU), and may need to be a byte in the middle.There are three sources of irregularity (see І 2.1) in the pipeline, even when no wrong branches aretaken: ЪН⌡Оf2ywТXУy wywywywywywy wywyНЇwНЇО_шТ▒ywywТ▓НЇО^WТКП@ТЛНЇО\сТ▓ПIТ⌠НЇО[OТ≈Т≤ywПXНЇОYкП-Т≥П8НЇОXGТ ПDТ⌡НЇОVцТ─П:ywywТ│НЇОU?Т─ПCНЇОRТ▐П!ywП(Т░ywНЇОP░ Т▒П4Т▓П"НЇОOТ÷П3{w {w{w{w{wНЇОM┬ТрТсПJНЇОLТ┘П({wТ├НЇОJ─Т▐ Т░ПUНЇОHЭТ┐П;Т└П!НЇОGx Т┴ПMТ┼НЇОEТТУПQНЇОDp ТК{w ТЛywП%НЇОBЛ Т─ПHyw НЇО>М{ТXНЇО<∙wТ─П:НґО:=П4НґО7ЕП){wНґО5█Т▐ПFТ░НґО4 Т°ПNТ² НґО2┘НЇО0-Т√П8Т≈П#НЇО.╘Т≤ПHНЇО-%Т─ПGНЇО)ЗПIНґО'╒{ Т▓ wП<Т⌠НґО&Т─П$НґО#ф{ТЯwП>ТРНґО"BТ·П6Т÷ywНґО ЎТ─П8ywНґОf{Т▐wТ░П(НґОБТёywТєНґО^Т≤ПHТ≥НґОзТ─ywywНґО┌{ wТ²{wПFНґОЧТ▐П9ywТ░НґОzТ─ywНЇО"ТЁП,ТЄП'НЇО·Т─П+Т│П4НЇОТ┬{wП@{ wТ┴НЇО √Т─yw{wНЇО>Т┤П.Т┬П1НЇО ╨Т─≤TVk(ЇSEC. 2THE PROBLEM27The instruction length is irregular, as noted in the previous paragraph; hence a uniformflow of instructions to the EU implies an irregular flow of bytes into the decoder, and viceversa.The memory takes an irregular amount of time to fetch data; if it contains a cache, theamount of time may vary by more than an order of magnitude. The EU demands instructions at an irregular rate. These considerations imply that considerable elasticity is needed in order to meet the EU's demandswithout introducing delays. 2.4 Hand-off to the EUFrom the IFU's viewpoint, handing-off an instruction to the EU is a simple producer-consumerrelationship. The EU demands a new instruction. If one is ready, the IFU delivers it as a pile ofsuitably formatted bits, and forgets about the instruction. Otherwise the IFU notifies the EU that itis not ready; in this case the EU will presumably repeat the request until it is satisfied. Thus at thislevel of abstraction, hand-off is a synchronized transfer of one data item (a decoded instruction)from one process (the IFU) to another (the EU).Usually the data in the decoded instruction can be divided into two parts: information about whatto do, and parameters. If the EU is a microprogrammed processor, for example, what to do canconveniently be encoded as the address of a microinstruction to which control should go (a dispatchaddress), and indeed this is done in the Dorado. Since microinstructions can contain immediateconstants, and in general can do arbitrary computations, it is possible in principle to encode all theinformation in the instruction into a microinstruction address; thus the instructions PushConstant(3)and PushConstant(4356) could send control to different microinstructions. In fact, however, micro-instructions are expensive, and it is impractical to have more than a few hundred, or at most a fewthousand of them. Hence we want to use the same microcode for as many instructions as possible,representing the differences in parameters which are treated as data by the microcode. Theseparameters are presented to the EU on some set of data busses; І 4 has several examples.Half of the IFU-EU synchronization can also be encoded in the dispatch address: when the IFU isnot ready, it can dispatch the EU to a special NotReady location. Here the microcode can do anybackground processing it might have, and then repeat the demand for another instruction. Thesame method can be used to communicate other exceptional conditions to the EU, such as a pagefault encountered in fetching an instruction, or an interrupt signal from an I/O device. TheDorado's IFU uses this method (see І 3.4). Measurements of typical programs [7, 11] reveal that most of the instructions executed are simple,and hence can be handled quickly by the EU. As a result, it is important to keep the cost of hand-off low, since otherwise it can easily dominate the execution time for such instructions. As the EUgets faster, this point gets more important; there are many instructions which the Dorado, forinstance, can execute in one cycle, so that one cycle of hand-off overhead would be 50%. Thispoint is discussed further in І 3 and 4.2.5 AutonomyPerhaps the most important parameter in the design of an IFU is the extent to which it functionsindependently of the execution unit, which is the master in their relationship. At one extreme wecan have an IFU which is entirely independent of the EU after it is initialized with a code address (itmight also receive information about the outcome of branches); this initialization would only occuron a process switch, complex procedure call, or indexed or indirect jump. At the other extreme isan IFU which simply buffers one word of code and delivers successive bytes to the EU; when thebuffer is empty, the IFU dispatches the EU to a piece of microcode which fetches another memoryword's worth of code into the buffer. The first IFU must decode instruction lengths, follow jumps,and provide the program counter for each instruction to the EU (e.g., so that it can be saved as aЪНЇОf2yТGУН9┴ НG?wНґО_шТЇПEТ╦НґО^WТ∙ywП,Т√НґО\сНґОZ{Т╡П2ТЁП"НґОXВТ─П7НґОV÷ywП,НЇОTGТ┼ПHТ▀ yw НЇОRцТ─НЇОNд{ТXНЇОK≥wТкywТлП#ywНЇОJТ÷ywТ═П2ywНЇОH▒Т▓ПCyw ywНЇОG Т├Т┤ ywПHНЇОE┴ТЁП]НЇОDТ─ywywНЇО@зТ∙П+Т√П/НЇО?VТ╚ywП-Т╛НЇО=рТ├ПAТ┤ {НЇОТ▌ПLТ▐ НЇО4╨Т▄ПNТ█ НЇО36ТоТп{ wП3НЇО1╡ Т─ywП6НЇО.┤ТєywywТ╔П.ywНЇО-Тёyw |wТєНЇО+ ТІП#ТЇП0НЇО)ШТ÷Т═П@ywНЇО(wТзП+ТшywywНЇО&СТ─ywНЇО#хТ² Т·ПKНЇО"DТ┴П%ywП+Т┼ НЇО юТ▓Т⌠ПZyНЇО=Т▌ Т▐ПKНЇО<╧Т╧Т╨П=НЇО;5ТКПIТЛНЇО9╠Т╨П-Т╩ywНЇО8-Т─П(НЇО5Т│Т┌ПZНЇО3~Т▀П4Т▄П/НЇО1ЗТЁП<ТЄП"Т─НЇО0vТеП*ТфywНЇО.Р{wТхТиПDНЇО-nТ▄П8Т█{wНЇО+ЙТ²П2Т·П,НЇО*fТІТЇП?НЇО(БТ┐П5Т└ywНЇО'^Т■П&{w{wНЇО%зТї{wТ╗ПYНЇО$VywТ─П^НЇО W{ТX НЇО,wТ┌Т┐ПcНЇО╗ Т═П%Т║П2НЇО$Т▐ПVТ░НЇО═ Т└ywywП+НЇОТ⌠ywТ■ПUНЇО≤ТґПGТў НЇОТ■П>Т∙НЇО░ Т╗ПIТ╘ НЇОТ─ ЪTVk(аSEC. 2THE PROBLEM29<==НЇОBиТ┌Т┐П*ywНЇОAE Т─НЇО>Т■П0ywТ∙П!НЇО<√Т┐Т└ПEНЇО;ТгП6|Ъ8TVk(кН3йО:┘pО;qТгУ ТхrО:┘pНЇО9$qТ┘Т├П>rО8≈pО9$qНЇО76Т═П%rО6╘pО76qТ║П5НЇО5HТбПJТцНЇО3дТ╦П#Т╧П0rО37pО3дqrО37pНЇО1жqТ▒ПVТ▓НЇО0RТ╔П/ТіП'НЇО.нsqТёП&ТєП9НЇО-JТ╠ПGТ╡НЇО+фТмТнПSНЇО*BТ≤П6Т≥П%НЇО(ЎТ─sqНЇО$©tТXНЇО!■qТіТїsqП5НЇО Т└ПaНЇО▄Т─П3НЇОaТАsqТБП7НЇОщsqТ─П5Т│sqНЇОYТ─Т│ПAНЇОуТ█П%Т▌П;НЇОQТдПQТеsqНЇОмТ┐sqТ└П9НЇОIТ╞П<Т╟П&НЇОеТгПXНЇОAТ√Т≈ sqП2НЇО ҐТёП'ТєП1НЇО9Т─8РTVk(■ь AN INSTRUCTION FETCH UNIT FOR A HIGH-PERFORMANCE PERSONAL COMPUTER32<==Т│НЇОCyТцТдПVНЇОAУТлsqТмП3НЇО@qТ─П/sqП!НЇО=FП1Н#О:ННґТаsqП$ТбП,НґО9jТ─Н#О7НґПSН#О4╨НґП<НЇО2bТ┘П"Т├П<НЇО0чТ░Т▒П>НЇО/Z ТґПKТўНЇО-жТ─П;sqНЇО)вtТXНЇО&╛qТ╔ТіsqП.НЇО%(Т█П#sqТ▌НЇО#єТ⌠П*Т■П2НЇО" Т└Т┘П:sqНЇО °Т ПAТ⌡НЇОТ─П`НЇОМТ╨sqП%Т╩НЇОiТбП4ТцsqНЇОЕТ─ПIНЇО╨Т°П>Т² sq sqНЇО6Т╘П+Т╙П/НЇО╡ТУП,ТЖsqП$НЇО.Т└sqТ┘sНЇО╙qТ┬sqП'Т┴sqП(НЇО&Т┬П@sqНЇО╒Т─П?НЇО wТ└sqП8sqТ┘НЇОСsqТ┴ПJТ┼sqVTVk(╡AN INSTRUCTION FETCH UNIT FOR A HIGH-PERFORMANCE PERSONAL COMPUTER34same time. The processor actually has access to all the information needed to maintain its own PC,but the time required to do this in microcode would be prohibitive (at least one cycle perinstruction). The IFU can also follow branches, provided they are PC-relative, have displacements specifiedentirely in the instruction, and are encoded in certain limited ways. These restrictions ensure thatonly information from the code (plus the current PC value) is needed to compute the branchaddress, so that no external dependencies are introduced. It would be possible to handle absoluteas well as PC-relative branches, but this did not seem useful, since none of the target instruction setsuse absolute branches. The decoding table specifies for each opcode whether it branches and howto obtain the displacement. On a branch, DECODE resets the earlier stages of the pipe and passesthe branch PC back to ADDRESS. The branch instruction is also passed on to the processor. If it isactually a conditional branch which should not have been taken, the processor will reset the IFU tocontinue with the next instruction; the work done in following the branch is wasted. If the branchis likely not to be taken, then the decoding table should be set up so that it is treated as anordinary instruction by the IFU, and if the branch is taken after all, the processor will reset the IFUto continue with the branch path; in this case the work done in following the sequential path iswasted. Even unconditional jumps are pased on to the processor, partly to avoid another case inthe IFU, and partly to prevent infinite loops in the IFU without any processor intervention. 4. IFU-processor hand-offWith a microcoded execution unit like the Dorado's processor, efficient emulation depends onsmooth interaction between the IFU and the processor, and on the right kind of concurrency in theprocessor itself. These considerations are less critical in a low-performance machine, where manymicrocycles are used to execute each instruction, and the loss of a few is not disastrous. A high-performance machine, however, executes many instructions in one or two microcycles. Adding oneor two more cycles because of a poorly chosen interface with the IFU, or because a very commonpair of operations cannot be expressed in a single microinstruction, slows the emulator down by 50-200%. The common operations are not very complex, and require only a modest amount ofhardware for an efficient implementation. The examples in this section illustrate these points.Good performance depends on two things:An adequate set of data busses, so that it is physically possible to perform the frequentcombinations of independent data transfers in a single cycle. We shall be mainly concernedwith the busses which connect the IFU and the processor, rather than with the internaldetails of the latter. These are summarized in Figure 4.A microinstruction encoding which makes it possible to specify these transfers in a singlemicroinstruction. A horizontal encoding does this automatically; a vertical one requiresgreater care to ensure that all the important combinations can still be specified.We shall use the term folding for the combination of several independent operations in a singlemicroinstruction. Usually folding is done by the microprogrammer, who surveys the operations tobe done and the resources of the processor, and arranges the operations in the fewest possiblenumber of microinstructions.Н⌡Оf2sqТXУs qsqsqsqsqsqs qsqsНЇqНЇО_шТ▄П,Т█П0sqНЇО^WТХПSТИНЇО\сТ─НЇОY╗ТъsqП-sqТЮ НЇОX$Т⌡Т°ПIНЇОV═ТяП,ТрsqП'НЇОUТ≥П!Т П9НЇОS≤Т┐sqП?Т└НЇОRТ■П5Т∙П(НЇОP░Т²П(sqТ·НЇОOТ▀sqsqП+Т▄НЇОM┬Т▐Т░П:sqНЇОLТ█П[НЇОJ─ТеТфПLНЇОHЭТ▌sqТ▐П2sНЇОGxqТ╛ПVТґНЇОEТТёП*ТєП/НЇОDpТ─sqП.sqП$НЇО?²uТXvuНЇОsrqТ┤sqНЇО7ГТ╣ПOsqТІ НЇО6cТ└П@Т┘НЇО4ъ Т│П!Т┌П:НЇО3[Т─ПMНЇО00Тє sqПQНЇО.╛Т─НЇО,Tsqsq sqП0sqНЇО)ЭsqТю Таsqsqsq sqНЇО(xТ─П5sqНЇО& ПfНЇО"УТ≈ Т≤srqsqП%sqНЇО!qТ⌠sqП0srqТ■sНЇОМqТ║П5Т╒ sqНЇОiТ┤П&Т┬П9НЇОЕ Т╩Т╪П6НЇОa Т─НЇО6Т═Т║ПQНЇО╡Т─rqНЇОмsН О▐xsТGxsН#уП)НЇОdqТ┤П(Т┬П<НЇО ЮТ─Ъ ╪TVk(²SEC. 4IFU-PROCESSOR HAND-OFF37PushConstantWord:temp _ LeftShift[IFUData, 8];-- put alpha into the left half of tempPush[temp or IFUData], IFuJump;-- or in beta, push the result on the stack, and dispatch to the next instructionNotice that the first microinstruction uses the IFU to acquire data from the code stream. Then thesecond microinstruction simultaneously retrieves the second data byte and dispatches to the nextinstruction. These examples illustrate several points. Any number of microinstructions can be executed to emulate an instruction, i.e., betweenIFUJumps. Within an instruction, any number of IFUData requests are possible; see Table 3 for asummary of the data delivered to successive requests. IFUJump and IFUData may be done concurrently. The IFUData will reference the currentinstruction's data, and then the IFUJump will dispatch the processor to the first microinstruc-tion of the next instruction (or to NotReady).Suppose analysis of programs indicates that the most common PushConstant instruction pushes theconstant 0. Suppose further that 1 is the next most common constant, and 2 the next beyond that,and that all other constants occur much less frequently. A lot of code space can probably be savedby dedicating three one-byte opcodes to the most frequent PushConstant instructions, and using atwo-byte instruction for the less frequent cases, as in the PushConstantByte example above, where theopcode byte designates a PushConstantByte opcode and alpha specifies the constant. A third opcode,PushConstantWord, provides for 16-bit constants, and still others are possible.Pursuing this idea, we define five instructions to push constants onto the stack: PushC0, PushC1,PushC2, PushCB, PushCW. Any five distinct values can be assigned for the opcode bytes of theseinstructions, since the meaning of an opcode is completely defined by its decoding table entry. Theentries for these instructions are as follows: (N is a constant encoded in the opcode, Length is theinstruction length in bytes, and Dispatch is the microcode dispatch address; for details, see І 5.4).OpcodePartial decoding table contents-- RemarksPushC0Dispatch_PushC, N_0, Length_1-- push 0 onto the stackPushC1Dispatch_PushC, N_1, Length_1-- push 1 onto the stackPushC2Dispatch_PushC, N_2, Length_1-- push 2 onto the stackPushCBDispatch_PushC, Length_2-- push alpha onto the stackPushCWDispatch_PushCWord, Length_3-- push the concatenation of alpha and beta onto the stackHere is the microcode to implement these instructions; we have seen it before:PushC:-- PushC0/1/2, (ifuData=N), PushCB, (ifuData=alpha)Push[IFUData], IFUJump; PushCWord:-- PushCW, temp _ Lshift[IFUData, 8];-- (IFUData=alpha here)Push[temp or IFUData], IFUJump;-- (IFUData=beta here)Observe that the same, single line of microcode (at the label PushC) implements four differentopcodes, for both one and two byte instructions. Only PushConstantWord requires two separatemicroinstructions.4.2 Initializing stateA standard method for reducing the size and increasing the usefulness of an instruction is toparameterize it. For example, we may consider an instruction with a base register field to beparameterized by that register: the "meaning" of the instruction depends on the contents of theregister. Thus the same instruction can perform different functions, and also perhaps can get bywith a smaller address field. This idea is also applicable to microcode, and is used in the Dorado.For example, there are 32 memory base registers. A microinstruction referencing memory does notspecify one of these explicitly; instead, there is a MemBase register, loadable by the microcode,which tells which base register to use. Provided the choice of register changes infrequently, this isan economical scheme. ЪНЇОf2sТGУН2НG?qНЇО`"sН О^ДxsН#уП'Н О]і vsxsxsН#уvsПLНЇОZ{qТ▓П*sqП0НЇОXВТ╣П5ТІП%НЇОWsТ─П,НґОUТ╔ПMТіНґОS≈srqТ─НґОQ?ТйsrqП'ТкНґОO╩Т─П0НґОMcsrqТ╞srqТ╟srqНґОKъТ┐srq Т└П)НґОJ[Т─rqНЇОG0Т╔П5rqНЇОE╛Т√ПXНЇОD(Т┴ПNТ┼НЇОBєТ╟П8rqНЇОA Т├П)Т┤ rqНЇО?°Т▓rqТ⌠П(НЇО>rqТ─П>НЇО:МТЇТ╦ПErqrqНЇО9irqТ╗rqrqПIНЇО7ЕТ┘ПWНЇО6aТ╒П'ТёyrqП&rqНЇО4щ Т─rqП<НЇО2лsНКТGН*╧ НЇО0╩НКН*╧НЇО/}НКН*╧НЇО.?НКН*╧НЇО-НКН*╧НЇО+цНКН*╧П:НЇО(≤qТ─ПJНЇО&┤sН#уТGП2Н О%IxsxsНЇО#8 Н#у Н О!З xsН#уxsН О ╪ vsxsxsН#уxsНЇОdqТгП0ТхrqНЇОЮТгТхrqНЇО\НЇО]tТXНЇО2qТрПJТсНЇОўtqТиТйПNНЇО*ТІП'ТЇП+НЇОіТ╘ПQТ╙НЇО"Т■ПXТ∙НЇО·Т▀П.Т▄П/НЇОТеП(ТфrqП%НЇО √Т∙ПaНЇОТ─ЪхTVk(бAN INSTRUCTION FETCH UNIT FOR A HIGH-PERFORMANCE PERSONAL COMPUTER38For emulation it presents some problems, however. Consider the microcode to push a localvariable; the address of the variable is given by the alpha byte plus the contents of the base registerlocalData, whose number is localDataRegNo:PushLocalVar:MemBase _ localDataRegNo;-- Make memory references relative to the local data.Fetch[IFUData];-- Use contents of PC+1 as offset.Push[memoryData], IFUJump;-- Push variable onto stack, begin next instructionThis takes three cycles, one of which does nothing but initialize MemBase. The point is clear: suchparametric state should be set from the IFU at the start of an instruction, using information in thedecoding table. This is in fact done on the Dorado. The decoding table entry for PushLocalVarspecifies localData as the initial value for MemBase, and the microcode becomes:PushVar:Fetch[IFUData];-- IFU initializes MemBase to the local dataPush[memoryData], IFUJump;-- Push variable onto stack, begin next instructionOne microinstruction is saved. Furthermore, the same microcode can be used for a PushGlobalVarinstruction, with a decoder entry which specifies the same dispatch address, but globalData as theinitial value of MemBase. Thus there are two ways in which parameterization saves space overspecifying everything in the microinstruction: each microinstruction can be shorter, and fewer areneeded. The need for initialization, however, makes the idea somewhat less attractive, since itcomplicates both the IFU and the EU, and increases the size of the decoding table. A major reduction in the size of the decoding table can be had by using the opcode itself as the dispatch address. This has a substantial cost in microcode, since typically the number of distinctdispatch addresses is about one-third of the 256 opcodes. If this price is paid and parameterizationeliminated, however, the IFU can be considerably simplified, since not only the decoding table spaceis saved, but also the buffers and busses needed to hand off the parameters to the processor, andthe parameterization mechanism in the processor itself. On the Dorado, the advantages ofparameterization were judged to be worth the price, but the decision is a fairly close one. Thecurrent memory base register and the current group of processor registers are parameters of themicroinstruction which are initialized from the IFU. The IFU also supplies the dispatch address atthe same time. The remainder of the information in the decoding table describes the data fieldsand instruction length; it is buffered in EXECUTE and passed to the processor on demand.4.3 ForwardingEarlier we mentioned folding of independent operations into the same microinstruction as animportant technique for speeding up a microprogram. Often, however, we would like to fold theemulation of two successive instructions, deferring some of the work required to finish emulation ofone instruction into the execution of its successor, where we hope for unused resources. Thiscannot be done in the usual way, since we have no a priori information about what instructioncomes next. However, there is a simple trick (due to Ed Fiala) which makes it possible in manycommon cases.We define for an entire instruction set a small number n of cleanup actions which may be forwardedto the next instruction for completion; on the Dorado up to four are possible, but one must usuallybe the null action. For each dispatch address we had before, we now define n separate ones, onefor each cleanup action. Thus if there were D addresses to which an IFUJump might dispatch, thereare now nD. At each one, there must be microcode to do the proper cleanup action in addition tothe work required to emulate the current instruction. The choice of cleanup action is specified bythe microcode for the previous instruction; to make this convenient, the Dorado actually has fourkinds of IFUJump operations (written IFUJump[i] for i=0, 1, 2, 3), instead of the one describedabove. The two bits thus supplied are ORed with the dispatch address supplied by the IFU todetermine the microinstruction to which control should go. To avoid any assumptions about whichpairs of successive instructions can occur, all instructions in the same instruction set must use thesame cleanup actions and must be prepared to handle all the cleanup actions. In spite of thislimitation, measurements show that forwarding saves about 8% of the execution time in straight-linecode (see І 6.4); since the cost is very small, this is a bargain.ЪН⌡Оf2sТGУП@НЇqНЇО_шТчП8ТъНЇО^WТ┘ПLТ├НЇО\сrqТ─rНЇОZбsН ОY└ТGН#уП5Н ОXFxsН#уxsН ОWxsН#уП3НЇОT╟qТ░П>rqТ▒НЇОS, Т≥sqТ П,НЇОQ╗Т╚Т╛П.rНЇОP$qТ─rqrqНЇОNsН ОLуxsН#уТGxsП&Н ОK≈xsН#уП3НЇОHlqТ÷П.tqТ═rНЇОFХqТґП.Тўr qНЇОEdТб rtqТцПCНЇОCЮ Т╗ПTТ╘НЇОB\ТфТгПXНЇО@ь Т─ sqsqП1НЇО=ґТ╒П9ТёП&Т─НЇО<)Т╗ Т╘ПQНЇО:╔Т▄ПLТ█НЇО9! Т┐ sqП&Т└П"НЇО7²Т÷Т═П?НЇО6ТВТЬПEНЇО4∙ТЁТЄПDНЇО3ТЇПFТ╦НЇО1█Т²Т· sqsqП&НЇО0 Ті ТїПRНЇО.┘Т─П'sqП'НЇО*├tТX НЇО'[qТъП8ТЮНЇО%вТ═П>Т║НЇО$SТ├ПNТ┤НЇО"оТхПVТиНЇО!KТ╦Т╧tqП#НЇОгТ╒ПZНЇОCТ─НЇОТ┌П5tqТ┐tqtq tНЇО■qТ┤П9Т┬П(НЇОТ≥tqП/tqНЇО▄Т┬tqП%tqТ┴srqНЇОТ▄tqПJТ█НЇО└Т∙П>Т√П"НЇОТ║П5Т╒П)НЇО|ТхsrqsrqtqТиtqП*НЇОЬТ©П!sqТюП+sqНЇО tТ▀ПKТ▄НЇОПТєПCТ╔НЇО lТҐПIТЎНЇОХ Т┤Т┬ПAНЇОdТ─П>ЪФTVk(ТSEC. 4IFU-PROCESSOR HAND-OFF39We illustrate this feature by modifying the implementation of PushLocalVar given above, to showhow one instruction's memory fetch operation can be finished by its successor, reducing the cost ofa PushLocalVar from two microinstructions to one. We use two cleanup actions. One is null (action0), but the other (action 2) finds the top of the stack not on the hardware stack but in thememoryData register. Thus, any instruction can leave the top of stack in memoryData and do anIFUJump[2]. Now the microcode looks like this:PushLocalVar[0]:Fetch[IFUData], IFUJump[2];-- this entry point assumes normal stack, and leaves top of stack inmemoryData.PushLocalVar[2]:Push[memoryData], Fetch[IFUData], IFUJump[2]; -- this entry point assumes top of stack is in memoryData and leaves it there.In both cases, the microcode executes IFUJump[2], since the top of stack is left in the memoryDataregister, rather than on the stack as it should be. In the case of PushLocalVar[2], the previous instruc-tion has done the same thing. Thus, the microcode at this entry point must move that data into thestack at the same time it makes the memory reference for the next stack value. The reader can seethat successive Push instructions will do the right thing. Of course there is a payoff only becausethe first microinstruction of PushLocalVar[0] is not using all the resources of the processor.It is instructive to look at the code for Add with this forwarding convention:Add[0]:temp _ Pop[];-- this entry point assumes and leaves normal stackStackTop _ StackTop+temp, IFUJump[0];Add[2]:StackTop _ StackTop+memoryData, IFUJump[0]; -- this entry point assumes top of stack is in memoryData, leaves normalstack.This example shows that the folding enabled by forwarding can actually eliminate data transferswhich are necessary in the unfolded code. At Add[2] the second operand of the Add is not put onthe stack and then taken off again, but is sent directly to the adder. The common data bus of the360/91 [15] obtains similar, but more sweeping, effects at considerably greater cost. It is alsopossible to do a cleanup after a NotReady dispatch; this allows some useful work to be done in anotherwise wasted cycle.4.4 Conditional branchesWe conclude our discussion of IFU-processor interactions, and give another example of forwarding,with the example of a conditional branch instruction. Suppose that there is a BranchNotZeroinstruction that takes the branch if the current top of the stack is not zero. Assume that itsdecoding table entry tells the IFU to follow the branch, and specifies the instruction length as thefirst IFUData value. Straightforward microcode for the instruction is:BranchNotZero:-- IFU jumps come here. IFU assumed result#0.if stack=0 then goto InsFromIFUData, Pop;-- Test result in this microinstruction.IFUJump;-- Result was non-zero, IFU did right thing.InsFromIFUData:-- Result was zero. Do the instruction at PC+IFUData.temp _PC+IFUData;-- PC should be PC+Instruction length.PC _ temp;-- Redirect the IFUIFUJump;-- This will be dispatched to NotReady, where the code will loop until the IFUrefills starting at the new location.The most likely case (the top of the stack non-zero) simply makes the test specified by theinstruction and does an IFUJump (two cycles). If the value is zero (the IFU took the wrong path),the microcode computes the correct value for the new PC and redirects the IFU accordingly (fourcycles, plus the IFU's latency of five cycles; guessing wrong is painful). If we think thatBranchNotZero will usually fail to take the branch, we can program the decoding table to treat it asНЇОf2sТGУН2НG?qНЇО_шТґП8ТўrqНЇО^WТ█Т▌ПAНЇО\сТ└rqП+Т┘П*НЇО[OТтП#ТуП6НЇОYкr qТ╨П%Т╩r q НЇОXGsrqТ─П$НЇОUbsН ОT$xsТGxsН#уПDН%÷ОRФ НЇОPН ОNцxsxsПWНЇОK≤qТёП$stq Тєr НЇОJqТ─П;rqНЇОH░Т┌Т┐ПRНЇОGТ┼П3Т▀П*НЇОE┬Т═rqТ║П1НЇОDТ─rqП4НЇО@ыП*rqП!НЇО=ТsН О<ІТGН#уП4Н О;xxsНЇО8⌠Н О7UxsПQН%÷О6НЇО2ЛqТІП'ТЇП4НЇО1hТ√Т≈rqrq НЇО/ДТ▒П<Т▓П#НЇО.`ТмТнПEНЇО,эТ≥rqТ П"НЇО+XТ─ НЇО'YtТXНЇО$.qТ∙sqП1Т√НЇО"╙ТэТщПGrНЇО!&q ТнПDТоНЇО╒Т║sq Т╒П8НЇОТ─srqП:НЇО9s Н#уТGxsxsН ОШvsvsxs Н#уП(Н ОҐxsН#уxsНЇО╛xsН#уП*xsxsН ОnxsxsН#уxs xsН О0xsН#уxН ОРsН#уpwsП$xН%÷ОЄsП%НЇО┴qТАП!ТБП7НЇО Т÷srqП*sqТ═НЇО│Т╗П2sqТ╘sqНЇО ЩТЭ sqП,ТЩНЇОyrqТ⌠Т■ПBLTVk(╪AN INSTRUCTION FETCH UNIT FOR A HIGH-PERFORMANCE PERSONAL COMPUTER40an ordinary instruction and deliver the branch displacement as IFUData, and reverse the sense of thetest.A slight modification of the forwarding trick allows further improvement. We introduce a cleanupaction (say action 1) to do the job of InsFromIFUData above (it must be action 1 or 3, since asuccessful test in the Dorado ors a 1 into the next microinstruction address). Now we write themicrocode (including for completeness the action 2 of І 4.3):BranchNotZero[0]:-- IFU jumps come here. Expect result#0.Test[stack=0], Pop, IFUJump[0];-- Test result in this microinstruction; if the test succeeds, we do IFUJump[1].BranchNotZero[2]:Test[memoryData=0], IFUJump[0];EveryInstruction[1]:-- Branch was wrong. Do the instruction at PC+IFUData.temp _PC+IFUData;PC _ temp;-- Redirect the IFUIFUJump[0];-- This will be dispatched to NotReady, where the code will loop until the IFUrefills starting at the new location.Now a branch which was predicted correctly takes only one microinstruction. For this to work, theprocessor must keep the IFU from advancing to the next instruction if there is a successful test inthe IFUJump cycle. Otherwise, the PC and IFUData of the branch instruction would be lost, and thecleanup action could not do its job. Note that the first line at EveryInstruction[1] must be repeatedfor each distinct dispatch address; all these can jump to a common second line, however.5. ImplementationIn this section we describe the implementation of the Dorado IFU in some detail. The primaryfocus of attention is the pipeline structure, discussed within the framework established in І 2 and І3.3, but in addition we give (in І 5.4) the format of the decoding table, which defines how the IFUcan be specialized to the needs of a particular instruction set. Figure 3 gives the big picture of thepipeline. Table 1 summarizes the characteristics of each stage; succeeding subsections discuss eachrow of the table in turn. The first row gives the properties of an ideal stage, and the rest of thetable describes departures from this ideal. This information is expanded in the remainder of thissection; the reader may wish to use the table to compare the behavior of the different stages.The entire pipe is synchronous, running on a two-phase clock which defines a 60 ns cycle; someparts of the pipe use both phases and hence are clocked every 30 ns. An "ideal" stage is describedby the first line of the table. There is a buffer following each stage which can hold one item(b=1), and may be empty (represented by an empty flag); this is also the input buffer for the nextstage. The stage takes an item from its input buffer every cycle (tinput=1) and delivers an item toits output buffer every cycle (toutput=1); the item taken is the one delivered (l=1). The buffer isloaded on the clock edge which defines the end of one cycle and the start of the next. The stagehandles an item if and only if there is space in the output buffer for the output at the end of thecycle; hence if the entire pipe is full and an item is taken by the processor, every stage will processan item in that cycle. This means that information about available buffer space must propagate allthe way through the pipe in one cycle. Furthermore, this propagation cannot start until it is knownthat the processor is accepting the item, and it must take account of the various irregularities whichallow a stage to accept an item without delivering one or vice versa. Thus, the pipe has globalcontrol. Note that a stage delivers an output item whether or not its input buffer is empty; if it is,the special empty item is delivered. Thus the space bookkeeping is done entirely by counting emptyitems.Implementing global control within the available time turned out to be hard. It was consideredcrucial because of the minimal buffering between stages. The alternative, much easier approach islocal control: deliver an item to the buffer only if there is space for it there at the start of the cycle.This decouples the different stages completely within a cycle, but it means that if the pipe is full(best case) and the processor suddenly starts to demand one instruction per cycle (worst case), thepipe can only deliver at half this rate, even though each stage is capable of running at the full rate;Н⌡Оf2sТGУП@НЇqНЇО_шТ┌П=srqТ┐НЇО^WНЇО[,Т▒Т▓ПLНЇОY╗ТюТаrsrqП)НЇОX$ ТЇuqП?НЇОV═Т─П4НЇОS╩sН#уТGxsП#Н ОR}xsН#уПExsНЇОQ?Н ОPxsНЇОM┘Н#уП+xsxsН ОLGxsxsН ОK xsН#уxН ОIкsН#уpwsП$xН%÷ОH█sП%НЇОEbqТ┬Т┴ПPНЇОCчТ÷sqП*Т═НЇОBZТ▌srqsqsrqП1НЇО@жТ≤П2Т≥rqНЇО?RТ─ПUНЇО:uТXНЇО7TqТЁТЄП.sqНЇО5пТ▄П=Т█П#НЇО4LТ▌Т▐ПDsНЇО2хqТ█П]Т▌НЇО1DТ∙П+Т√П0НЇО/юТ═П=Т║П$НЇО.<ТёП8ТєП%НЇО,╦Т─ПVНЇО)█Т╗ПIТ╘НЇО( Т┴Т┼ПRНЇО&┘Т╩Т╪П?НЇО%rqТ·rqrqП)Т÷НЇО#}Т≥П=rО"ПpО#}qТ НЇО!▐Т║rО!pО!▐qП(Т╒rqНЇО║Т≤ПPТ≥ НЇОТ≈П-Т≤П/НЇО≥Т┼П6Т▀П+НЇОТ░tqП$Т▒П*НЇО▒Т└Т┘ПLНЇО Т┌Т┐ПRНЇО┴Т╡П"ТЁП3tНЇОqТ▀Т▄ПLНЇО│Т▐rqПLТ░rНЇОЩqНЇОрТ╟П:Т╠НЇО NТ≈П1Т≤П*НЇОйtqТ┐ПEТ└ tq НЇО FТёПLТєНЇОбТ⌡Т°ПFНЇО>Т─ПcTVk(рSEC. 5IMPLEMENTATION41StageSizeInputOutputResetRemarks"ideal"t=1; takes onet=l=1; delivers one Clears bufferAll state is in the bufferitem if output item if buffer willto empty on after the stage.is possiblebe empty; b=1PC_ . . .ADDRESSwordNo inputNot if paused, MARand jump;Pass PC by incrementing;contention, or memalso acceptsa source, hence has busy; OK if space innew PCvaluestate (PC).any later buffer.MEMORYwordInternall>2; output is and jump;Must enforce FIFO;complicationsunconditional; b=2 discards out-not really part of IFU;put of fetcheshas state of 0-2in progressfetches in progressBYTESbytet=.5t=l=.5and jumpBreak byte feature.DECODEinstrt>.5; rate de-onlyRecycling to vary rate;pends on ins-splits beta byte; encodestruction lengthexceptions; does jumps.DISPATCHinstrOn IFUJumponlyNotReady is default delay; IFUHold is panic delay.EXECUTEbyteOn IFUDataNo output bufferReset unnecessaryTable 1: Summary of the pipeline stages<==їsqТЖП2ТВНЇО=# ТТsqsq НЇО;÷ Т│П8Т┌sqНЇО:sqТ│П+Т┌sqНЇО8≈ТіТїПFНЇО7ТЁПНЇОJЙТ╪t qПPНЇОIf Т├Т┤ПBНЇОGБТпП+ТяП/НЇОF^ Т│ПFТ┌НЇОDзТ▄Т█ПPНЇОCVТ─П"НЇО?WtТXwtНЇО<,qТ░Т▒ПLНЇО:╗Т─ПPНЇО7}Т═П#Т║sqП/НЇО5ЫТ█Т▌ПCsqНЇО4uТ─Т│ПKНЇО2ЯТ╪П/sqТҐНЇО1mТ─sqП'НЇО. ЧД█О.BЧДН⌡О. Ч х█О.BЧ хН cО. Ч(█О.BЧ(Н/▀О. Ч і█О.BЧ іН91О. Чo█О.BЧoНЇО,ЎtНHННЇО+пЧДFН⌡О+пЧ хFН cО+пЧ(FН/▀О+пЧ іFН91О+пЧoFНЇО(БrН]qНП2НЇО'^rН qНП+НЇО%зrН qНП-НЇО#┌r Н qНП7НЇО!ЧrН qННЇО zrН qНП9НЇО"rН qНП8НЇО·rН qНТ■sqsqsq Т∙rqНОТ─ rqНЇО√rН qНsqНЇОЕЧДОЧД█Н⌡ОЕЧ хОЧ х█Н cОЕЧ(ОЧ(█Н/▀ОЕЧ іОЧ і█Н91ОЕЧoОЧo█Н$ОГТXП%НЇО╪ТєП^Т╔НЇО8ТєsqТ╔НЇОЄsqТ▀ПQТ▄НЇО 0Т─Т│ПFНЇО╛ТІП0sqП%НЇО (sqТ┬П$tqТ┴НЇОєТиПGtq ТйнTVk(SEC. 5IMPLEMENTATION45problem can be attacked by introducing a sub-stage within DECODE; unfortunately, this delays thereading of the decode table by half a cycle, so that its output is not available together with thealpha byte. To solve the problem it is necessary to provide a second output buffer for BYTES, andto feed back its contents into the main buffer if the instruction turns out to be only one byte long,as in Figure 7c. Some care must be taken to keep the PCs straight. This ugly backwarddependency seems to be an unavoidable consequence of the variable-width items. In fact, a three-byte instruction is not handled exactly as shown in Figure 7. Since the bandwidthof BYTES prevents it from being done in one cycle anyway, space is saved by breaking it into twosub-instructions, each two bytes long; for this purpose a dummy opcode byte is supplied betweenalpha and beta. Each sub-instruction is treated as an instruction item. The second one containsbeta and is slightly special: DECODE ignores its dummy opcode byte and treats it as a two-byteinstruction, and DISPATCH passes it on to EXECUTE after the alpha byte has been delivered.<==йТ├П8sqТ┤rНЇО=FqТо ТпПNНЇО;б ТёПWНЇО:>ТгПGsqТхНЇО8╨rqТфПWНЇО76Т─НЇО37tТXwtНЇО0qТ╪srqП?НЇО.┬ ТцП6srqТдrНЇО-qТ╞rqr qП$rqТ╟rqНЇО+─sqТ─П3sqП%НЇО(ґЧД█О(UЧДН⌡О(ґЧ х█О(UЧ хН cО(ґЧ(█О(UЧ(Н/▀О(ґЧ і█О(UЧ іН91О(ґЧo█О(UЧoНґО%ЩrН╛rНЮrН║r Н'#srНЇО%ЧДFН⌡О%Ч хFН cО%Ч(FН/▀О%Ч іFН91О%ЧoFНґО"УqНН≤Н╡Н'#rqНґО ²НeНZН╡Н'#rqНґОНeН0Н╡Н'#rqНґОаНeНZНtН'#rqНґО=НeНZНJН'#rqНґО╧НeН0НtН'#rqrqНґО5НeН0НJН'#rqНґОщНeНZНtН'#rqНґОYНeНZНJН'#rП!qНґОуНeН0НtН'#rqrqНґОQНeН0НJН'#rП$qНЇО═ЧДОмЧД█Н⌡О═Ч хОмЧ х█Н cО═Ч(ОмЧ(█Н/▀О═Ч іОмЧ і█Н91О═ЧoОмЧo█НVО╒ТXsrфTVk(]SEC. 6PERFORMANCE476. PerformanceThe value of an instruction fetch unit depends on the fraction of total emulation time that it saves(over doing instruction fetching entirely in microcode). This in turn clearly depends on the amountof time spent in executng each instruction. For a language like Smalltalk-76 [5], a typicalinstruction requires 30-40 cycles for emulation, so that the half-dozen cycles saved by the IFU arenot very significant. At the other extreme, an implementation language like Mesa [9, 11] iscompiled into instructions which can often be executed in a single cycle; except for function callsand block transfers, no Mesa instruction requires more than half a dozen cycles. For this reason,we give performance data only for the Mesa emulator.The measurements reported were made on the execution of the Mesa compiler, translating aprogram of moderate size; data from a variety of other programs is very similar. All the operatingsystem functions provided in this single-user system are included. Disk wait time is excluded, sinceit would tend to bias the statistics. Some adjustments to the raw data have been made to removeartifacts caused by compatibility with an old Mesa instruction set. Time spent in the procedure calland return instructions (about 15%) has been excluded; these instructions take about 10 times aslong to execute as ordinary instructions, and hence put very little demand on the IFU.The Dorado has a pair of counters which can record events at any rate up to one per machinecycle. Together with supporting microcode, these counters provide sufficient precision that overflowrequires days of execution. It is possible to count a variety of interesting events; some arepermanently connected, and others can be accessed through a set of multiplexors which provideaccess to several thousand signals in the machine, independently of normal microprogram execution.6.1 Performance limitsThe maximum performance that the IFU can deliver is limited by certain aspects of itsimplementation; these limitations are intrinsic, and do not depend on the microcode of theemulator or on the program being executed. The consequences of a particular limitation, of course,depend on how frequently it is encountered in actual execution.Latency: after the microcode supplies the IFU with a new PC value, an IFUJump will go to NotReadyuntil the fifth following cycle (in a few cases, until the sixth cycle). Thus there are at least fivecycles of latency before the first microinstruction of the new instruction can be executed. Ofcourse, it may be possible to do useful work in these cycles. This latency is quite important, sinceevery instruction for which the IFU cannot compute the next PC will pay it; these are wronglyguessed conditional branches, indexed branches, subroutine calls and returns, and a few others ofnegligible importance.A branch correctly executed by the IFU causes a three-cycle gap in the pipeline. Hence if theprocessor spends one cycle executing it and each of its two predecessors, it will see three NotReadycycles on the next IFUJump. Additional time spent in any of these three instructions, however, willreduce this latency, so it is much less important than the other.Bandwidth: In addition to these minimum latencies, the IFU is also limited in its maximumthroughput by memory bandwidth and its limited buffering. A stream of one-byte instructions canbe handled at one per cycle, even with some processor references to memory. A stream of two-byteinstructions, however (which would consume all the memory bandwidth if handled at full speed),results in 33% NotReady even if the processor makes no memory references. The reason is that theIFU cannot make a reference in every cycle, because its buffering is insufficient to absorbirregularity in the processor's demand for instructions. As we shall see, these limitations are ofsmall practical importance.НЇОf2sТGУН8м НG?qНЇО_шuТXНЇО\╟qТ⌠П#Т■П>НЇО[,Т┘П$Т├П;НЇОY╗ТРПKТСНЇОX$ ТёПCТє sqНЇОV═ТЮПYНЇОUТ÷Т═ПVНЇОS≤Т÷П3Т═П,НЇОRТ─П2НЇОNИТАПUНЇОMeТ░ПIТ▒НЇОKАТ┬Т┴ПLНЇОJ]Т≥П$Т П:НЇОHыТ├ Т┤ПRНЇОGUТўП$Т╞П9НЇОEяТ─ПNsqНЇОBіТЄПLТ╣НЇОA"Т─Т│ПPНЇО?·ТАТБПNНЇО> ТЇПRНЇО<√Т─П\НЇО8≈tТXНЇО5lqТТsqП1НЇО3ХТЯП,ТРНЇО2dТ├ПSТ┤НЇО0ЮТ─П9НЇО-╣tqТ▐Т░ sqsq srqrНЇО,1qТ╚Т╛П]НЇО*ґТлТмПVНЇО))Т▓П%Т⌠П9НЇО'╔ТбsqsqТцНЇО&!ТіПLТї НЇО$² Т─НЇО!rТҐП"sqП+ТЎНЇОНТ≈П@Т≤rНЇОjqТ▒srqП(Т▓П"НЇОФТ─П;НЇО╩tqТКТЛsqНЇО7 Т█П/Т▌П'НЇОЁТ│П3Т┌П,НЇО/Т╔ПIТіНЇО╚Т▒rqП2Т▓НЇО'sqТЩ ТЧПJНЇОёТ╧Т╨ПDНЇОТ─ЪVTVk(█AN INSTRUCTION FETCH UNIT FOR A HIGH-PERFORMANCE PERSONAL COMPUTER486.2 NotReady dispatchesOur measurements show that the average instruction takes 3.1 cycles to execute (including all IFUdelays). Jumps are 26% of all instructions, and incorrectly predicted jumps (40% of all conditionaljumps) are 10%. The average non-jump instruction takes 2.5 cycles.The performance of the IFU must be judged primarily on the frequency with which it fails to satisfythe processor's demand for an instruction, i.e., the frequency of NotReady dispatches. It isinstructive to separate these by their causes: latency, cache misses by the IFU, dearth of memory bandwidth, insufficient buffering in the IFU. The first dominates with 16% of all cycles, which is not surprising in view of the large number ofincorrectly predicted jumps. Note that since these NotReady cycles are predictable, unlike all theothers, they can be used to do any background tasks which may be around.Although the IFU's hit rate is 99.7%, the 25 cycle cost of a miss means that 2.5% of all cycles areNotReady dispatches from this cause. This is computed as follows: one cycle in three is a dispatch,and .3% of these must wait for a miss to complete. The average wait is near the maximum,unfortunately, since most misses are caused by resetting the IFU's PC, This yields 33% of .3%, or .1%,times 25, or 2.5%.The other causes of NotReady account for only 1%. This is also predictable, since more than halfthe instructions are one byte, and the average instruction makes only one memory reference in threecycles. Thus the average memory bandwidth available to the IFU is two words, or threeinstructions, per instruction processed, or about three times what is needed. Furthermore, straight-line instructions are demanded at less than half the peak rate on the average, and jumps are sofrequent that when the first instruction after a jump is dispatched, the pipe usually contains half theinstructions that will be executed before the next jump. 6.3 Memory bandwidthAs we have seen, there is no shortage of memory bandwidth, in spite of the narrow data pathbetween the processor and the IFU. Measurements show that the processor obtains a word from thememory in 16% of the cycles, and the IFU obtains a word in 32% of the cycles. Thus data issupplied by the memory in about half the cycles. The processor actually shuts out the IFU bymaking its own reference about 20% of the time, since some of its references are rejected by thememory and must be retried. The IFU makes a reference for each word transferred, and makesunsuccessful references during its misses, for a total of 35%. There is no memory reference about45% of the time.6.4 ForwardingThe forwarding trick saves a cycle in about 25% of the straight-line instructions, and hence speedsup straight-line execution by 8%. Jumps take longer and benefit less, so the speed-up within aprocedure is 5%. Like the IFU itself, forwarding pays off only when instructions are executed veryquickly, since it can save at most one cycle per instruction.Н⌡Оf2sТGУП@НЇqНЇО_шtТXНЇО\╟qТёП[sНЇО[,qТ∙П4Т√П(НЇОY╗Т─П=НЇОV}Т┐sqТ└П0НЇОTЫТВП?rqНЇОSu Т─П$НґОQНґОNеsqНґОLmНґОJsqНЇОGҐТ П.Т⌡П1НЇОF9 Тґ ТўrqП'НЇОD╣Т─ПAНЇОA┼Т═sqПDТ║НЇО@rqТ▓Т⌠ПLНЇО>┌ТкТлП?НЇО<Ч Т─П/sqsqТ│НЇО;zТ─НЇО8OТ╒rqТёП9НЇО6кТ─ПWТ│НЇО5GТП5sqТНЇО3цТ▒Т▓ПHНЇО2?Т╡П0ТЁП+НЇО0╩Т┐ПVТ└НЇО/7Т─П-НЇО+8tТXНЇО( qТҐП&ТЎП3НЇО&┴Т┌Т┐sqП?НЇО%ТҐsqП&ТЎНЇО#│Т╩П@Т╪sqНЇО!ЩТїТ╗П;НЇО yТ╩sqП-Т╪ НЇОУТ П<Т⌡НЇОqТ─НЇОrtТX НЇОGqТ П,Т⌡П4НЇОцТІП&ТЇП7НЇО?Т⌠Т■ sqПEНЇО╩Т─П5ЪЭTVk(QSEC. 6PERFORMANCE496.5 SizeA Dorado board can hold 288 standard 16-pin chips. The IFU occupies about 85% of a board;these 240 chips are devoted to the various stages as shown in Table 4. FunctionChips%ADDRESS-BYTES4017DECODE8635DISPATCH2410EXECUTE188Processor interface2711Clocks188Testing2711Table 4: Size of various parts of the IFUIn addition, about 25 chips on another board are part of MEMORY and BYTES. The early stages aremostly devoted to handling several PC values. DECODE is large because of the decoding table (27RAM chips) and its address drivers and data registers, as well as the branch address calculation. Table 5 shows the amount of microcode in the various emulators, and in some functions commonto all of them. In addition, each emulator uses one quarter of the decode table. Of course they arenot all resident at once.SystemWordsCommentsMesa1300Smalltalk1150Lisp1500Alto BCPL700I/O1000Disk, keyboard, regular and color display, Ethernet Floating point 300IEEE standard; there is no special hardware supportBit block transfer270Table 5: Size of various emulatorsAcknowledgementsThe preliminary design of the Dorado IFU was done by Tom Chang, Butler Lampson and ChuckThacker. Final design and checkout were done by Will Crowther and the authors. Ed Fialareviewed the design, did the microassembler and debugger software, and wrote the manual. Theemulators mentioned were written by Peter Deutsch, Willie-Sue Haugeland, Nori Suzuki and EdTaft.НЇОf2sТGУН8м НG?qНЇО_шtТXНЇО\╟qТЁТЄП!sqНЇО[,Т─ПCНЇОXYЧД█ОXЧДН⌡ОXYЧ х█ОXЧ хН cОXYЧ(█ОXЧ(Н/▀ОXYЧ і█ОXЧ іН91ОXYЧo█ОXЧoНґОU╘tН!{Н+≈НЇОT╩ЧДFН⌡ОT╩Ч хFН cОT╩Ч(FН/▀ОT╩Ч іFН91ОT╩ЧoFНґОQмsqsН#%qН+jНґОPIsН#%qН+jНґОNеsН#%qН+jНґОMAsН#%qН,НґОKҐН#%Н+jНґОJ9Н#%Н,НґОH╣Н#%Н+jНЇОHЧДОG1ЧД█Н⌡ОHЧ хОG1Ч х█Н cОHЧ(ОG1Ч(█Н/▀ОHЧ іОG1Ч і█Н91ОHЧoОG1Чo█Н²ОDТXП!sНЇО@шqТ┼П6Т▀sqsqНЇО?WТ÷sq sqТ═П+НЇО=сsqТ─П`НЇО:╗Т⌡ПFТ°НЇО9$Т┌ПHТ┐НЇО7═Т─НЇО4мЧД█О4uЧДН⌡О4мЧ х█О4uЧ хН cО4мЧ(█О4uЧ(Н/▀О4мЧ і█О4uЧ іН91О4мЧo█О4uЧoНґО2tН9Н!цНЇО1/ЧДFН⌡О1/Ч хFН cО1/Ч(FН/▀О1/Ч іFН91О1/ЧoFНґО/qНBНґО-▒НBНґО, НBНґО*┴sНРqНґО)sqsНBqН!цП4НґО'│НРН!цsqП/НґО%ЩНРНЇО%LЧДО$yЧД█Н⌡О%LЧ хО$yЧ х█Н cО%LЧ(О$yЧ(█Н/▀О%LЧ іО$yЧ і█Н91О%LЧoО$yЧo█Н 6О!NТXНЇО{uНЇОPqТ║Т╒sqП0НЇОлТиП(ТйП)НЇОHТ╗ПUНЇОдТ╟Т╠ПCНЇО@ЪюTVk( AN INSTRUCTION FETCH UNIT FOR A HIGH-PERFORMANCE PERSONAL COMPUTER50References1.Clark, D.W. et. al. The memory system of a high performance personal computer. Technical Report CSL-81-1, Xerox PaloAlto Research Center, January 1981. Revised version to appear in IEEE Transactions on Computers.2.Connors, W.D. et. al. The IBM 3033: An inside look. Datamation, May 1979, 198-218.3.Deutsch, L.P. A Lisp machine with very compact programs. Proc 3rd Int. Joint Conf. Artificial Intelligence, Stanford, 1973,687-703.4.Ibbett, R.N. and Capon, P.C. The development of the MU5 computer system. Comm. ACM 21, 1, Jan. 1978, 13-24.5.Ingalls, D.H. The Smalltalk-76 programming system: Design and implementation. 5th ACM Symp. Principles ofProgramming Languages, Tucson, Jan. 1978, 9-16.6.Intel Corp. MCS-86 User's Manual, Feb. 1979.7.Knuth, D.E. An empirical study of Fortran programs. Software²Practice and Experience 1, 1971, 105-133.8.Lampson, B.W. and Pier, K.A. A processor for a high performance personal computer. Proc 7th Int. Symp. ComputerArchitecture, SigArch/IEEE, La Baule, May 1980, 146-160. Also in Technical Report CSL-81-1, Xerox Palo Alto ResearchCenter, Jan. 1981.9.Mitchell, J.G. et. al. Mesa Language Manual. Technical Report CSL-79-3, Xerox Palo Alto Research Center, April 1979.10.Russell, R.M. The CRAY-1 computer system. Comm. ACM 21, 1, Jan. 1978, 63-72.11.Tanenbaum, A.S. Implications of structured programming for machine architecture. Comm. ACM 21, 3, March 1978, 237-246.12.Teitelman, W. Interlisp Reference Manual. Xerox Palo Alto Research Center, Oct. 1978.13.Thacker, C.P, et. al. Alto: A personal computer. In Computer Structures: Readings and Examples, 2nd edition, Sieworek,Bell and Newell, eds., McGraw-Hill, 1981. Also in Technical Report CSL-79-11, Xerox Palo Alto Research Center, August1979.14.Thornton, J.E. The Control Data 6600, Scott, Foresman & Co., New York, 1970.15.Tomasulo, R.M. An efficient algorithm for exploiting multiple arithmetic units, IBM J. R&D 11, 1, Jan. 1967, 25-33.16.Anderson, D.W. et. al. The System/360 Model 91: Machine philosophy and instruction handling. IBM J. R&D 11, 8, Jan.1967, 8-24.17.Widdoes, L. C. The S-1 project: Developing high performance digital computers. Proc. IEEE Compcon, San Francisco, Feb.1980, 282-291.ЪН⌡Оf2sТGУП@НЇqНЇО_шu НЇО\▄sН2wsПOxsН2О[NПB{swsНЇОYМН2 wsxsw sНЇОX▄Н2П9wП1sН2ОWNНЇОUМН2П4xsws{svsНЇОT▄Н2ПNw{wН2ОSNsНЇОQМН2{wsНЇОP▄Н2П4wsvsНЇОO+Н2ПSwН2ОMМs xsП9xsН2ОL╞НЇОKNН2wswsxsП3НЇОIМН2xsws{svsНЇОH▄Н2ПQws{svsН2ОGNНЇОEМН2 wsП-НЇОD▄Н2 wsП"wП*sН2ОCNПDxsП/Н2ОBНЇО@╞Н2wsП(НЇО?NН2ПP{wsvsНЇО=МН2 wsПF{swsvsН2О<╞ НЇО;NН2ПPws{swsН2О: ЪТTVk( Helvetica Helvetica Helvetica Helvetica Helvetica Helvetica Math TimesRoman Logo TimesRoman TimesRoman TimesRoman TimesRoman TimesRoman TimesRoman TimesRoman TimesRoman TimesRoman TimesRoman TimesRoman TimesRoman TimesRoman TimesRoman TimesRoman TimesRoman TimesRoman Math TimesRoman_и I jN* I4 <>?I╟L(W,b·eNp ┤yД{ c└ >▌≥ Dё.ўлЁт╩.ф Ьпxт ёщ sГ╞ОЖУШЪЪj/ЪЩ⌠0чЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪЪDoradoIfu.bxDakeJanuary 13, 1981 3:51 PM