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 94304MmpJ"CqX;=* 4r1sts40 N.?- )-+)ts"* B(4&ts9%wV"Lu.r hs rs9.vwt$wXlxqdrG0  H\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.<==Q =K)|w;/| w7{X!4w>340%.iD, )&1%% 9#T"{wB ~D Av:anV;#fGB3!{wG+ 4& < #U=yw"tHZlCyw]d{ wyw= %HdAN 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: \ywXy wywywywywywy wywywVywywU@S}IQywXPu-8NDMm:ywywKCH!yw( ywG: 4"E3{w {w{w{w{wD2JB({wA* U?;!>" M<Q; {w yw%9 Hyw 5{X3?w:04.){w,7F*N )/&8#%SH#G IL{ w< $p{w>6ywh8yw{ w(ywH ywyw,{ w{wF 9yw $yw,'H+4{w@{ w@yw{w.1d VHaSEC. 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]yG- ;wWUEUyw,TMQ2"Pq7Nyw,KH yw J=F>{XCwyw #ywA yw2yw@ Cyw yw> ywH=];ywyw8T+/6yw-5L A {3w'/2D X0 8| w/<| w:- L ,4N * { w3), yw6&ywyw.yw$}yw |w" #0!u@yw+ywyw mywB K%yw+ :Zyw(22F#{X w2yw$ F |yw&ywXt`ywLyw lywyw.%yw/d9yw  HbAN INSTRUCTION FETCH UNIT FOR A HIGH-PERFORMANCE PERSONAL COMPUTER28return link). The second leaves all these functions to the EU, except perhaps for keeping track ofwhich byte of the word it is delivering. One might think that the second IFU cannot helpperformance much, but in fact when working with a microcoded EU it can probably provide halfthe performance improvement of the first one, at one-tenth the cost in hardware. The reason canbe seen by examining the interpreter fragment at the beginning of 2; half a dozen micro-instructions are typically consumed in the clumsy GetInstruction operation, and things get worsewhen instructions do not coincide with memory words.When deciding what trade-offs to make, one important parameter is the speed of the EU. It ispointless to be able to execute most instructions in one or two cycles, if several cycles are consumedin GetInstruction. Hence a fast EU must have an autonomous IFU. An important special case is thespeed of the memory relative to the microinstruction time. If several microinstructions can beexecuted in the time required to fetch the next instruction from memory, the processor can use thistime to hold the IFU's hand, or to perform the GetInstruction itself. On the Dorado, the cacheensures that memory data arrives almost immediately, so there is no free time for handholding.An autonomous IFU must do more than simply transforming instructions into a convenient form forthe EU. There are two natural ways in which its internal operation may be affected by the instruc-tion stream: decoding instruction lengths, and following branches. Any IFU which handles morethan one instruction without processor intervention must calculate instruction lengths. Followingbranches is desirable because it avoids the cost of a start-up latency at every branch instruction(typically every fifth instruction is a branch). However, it does introduce potential complicationsbecause a conditional branch must be processed without accurate information (perhaps without anyinformation) about the actual value of the condition; indeed, often this value is not determineduntil the processor has executed the preceding instruction. A straightforward design decideswhether to branch based on the opcode alone, and the processor restarts the IFU at the correctaddress if the decision turns out to be wrong. The branch decision may be based on other historical information. The S-1 [17], for instance, keepsin its instruction cache one bit for each instruction, which records whether the instruction branchedlast time it was executed. This small amount of partial history reduces the fraction of incorrect branch decisions to 5% [Forest Baskett, personal communication]. The MU5 [4] remembers theaddresses of the last eight instructions which branched; such a small history leaves 35% of thebranches predicted wrongly, but the scheme allows the prediction to be made before the instructionis fetched. More elaborate designs [16] follow both branch paths, discarding the wrong one whenthe processor makes the branch decision. Each path may of course encounter further branches,which in turn may be followed both ways until the capacity of the IFU is exhausted. If each path istruly followed in parallel, then following n paths will in general require n times as much hardwareand n times as much memory bandwidth as following one path. Alternatively, part or all of theIFU's resources may be multiplexed between paths to reduce this cost at the expense of bandwidth. 2.6 BufferingAs we saw in 2.2, a pipeline with any irregularities must have buffering to provide elasticity, or itsperformance at each instant will approximate the performance of the slowest stage at that instant;this maximizing of the worst performance is highly undesirable. From the enumeration in 2.3 ofirregularities in the IFU, we can see that to serve the EU smoothly, there should be a buffer betweenthe EU and any sources of irregularity, as shown in Figure 2. Similarly, to receive words from theirregular memory, there should be a buffer between the memory and any sources of irregularity.Because of the irregularity caused by variable length instructions, a single buffer cannot serve bothfunctions. Note that additional regular stages (some are shown in the figure) have no effect oneway or the other.UywXy wywywywywywy wywywO3.yw%M9 yw L+ & ywJ;"I#AG &| w F0BOywAl R?| wyw yw#>dW<T;\ yw| w"9W6 ywN5)yw Q3?yw2!^0A/ B- K, =*I) -yw'($ZZ"4/!R<"*ywJ{wD8 {wB2,?:5yw&{w{w2{wYyw^{X wc %2 |V ywyw+tywUG l> I d  HZSEC. 2THE PROBLEM29<==*yw l0yw!Ed6|8 :H0z(:p;q r:p9$q >r8p9$q76%r6p76q55HJ 3#0r37p3qr37p1qV0R/'.sq&9-JG+S*B6%( sq$tX!qsq5 a3asq7sq5 sq YA%;QQsqsq9I<&XA sq2 '1 98 H AN INSTRUCTION FETCH UNIT FOR A HIGH-PERFORMANCE PERSONAL COMPUTER32<==r$ r r!,!, %jr$ )r$ r#$V"8$ r" $ r"$ r$ r $V$ r1$ 9G 5G /G9 *G #G qG UG qG9 G9 qGp<2 8N 6+ :<23N 1:':  j <2 2 '  H -2 r.$V-U$ r-2 $ r-2$ r+$ r+ $V+$ r-2$" r$V $ r $ r $t8 , !@ \ pi+`6G;#H?SEC. 3ARCHITECTURE OF THE DORADO IFU33There are two words of buffering after MEMORY, but there is no other buffering except for theminimum single item between stages, contrary to the arguments of 2.6. This design was adoptedpartly to save space, and partly because we did not fully understand the issues in maintaining peakbandwidth. Fortunately the peak bandwidth of the IFU is substantially greater than what theprocessor is likely to demand for more than a very short interval (see 6), so that not much usefulthroughput is lost because of the inadequate buffering.3.4 ExceptionsException conditions are handled by extending the space of values stored in an item and handedoff from one stage to the next, rather than by establishing separate communication paths. Thus, forexample, a page fault from the memory is indicated by a status bit returned along with the dataword; the resulting "page fault value" is propagated through the pipe and decoded into a page faultdispatch address which is handed to the processor like any ordinary instruction. Each exception hasits own dispatch address. Interrupts cause a slight complication. The IFU accepts a signal calledReschedule which means "cause an interrupt;" this signal is actually generated by I/O microcode inthe processor, but it could come from separate hardware. The next item leaving DECODE ismodified to have a reschedule dispatch address. The microcode at this address examines registers tofind out what interrupt condition has occurred. Since the reschedule item replaces one of theinstructions in the code, it has a PC value, which is the address of the next instruction to beexecuted. After the interrupt has been dealt with, the IFU will be restarted at that point.The exceptions may be divided into three classes:1)the IFU has not (yet) finished decoding the next instruction, and hence is not ready torespond to a processor demand;2)it is necessary to do something different (to handle an interrupt or a page fault);3)there has been a hardware problemit is not wise to proceed.Since more than one exception condition may obtain at a time, they are arranged in a fixed priorityorder. Exceptions are communicated only by a dispatch; hence, all exceptions having to do with aparticular opcode must be detected before it is handed off. Thus all the bytes of an instructionmust have been fetched from memory and be available within the IFU before it is handed off.3.5 Contention and dependenciesThere is no contention for resources within the IFU, and the only contention with the rest of theDorado is for access to the memory. The IFU shares with the processor a single address bus to theDorado's cache, but has its own bus for retrieving data. The processor has highest priority for theaddress bus, which can handle one request per cycle. Thus under worst-case conditions the IFU canbe locked out completely; eventually, of course, the processor will demand an instruction which isnot ready and stop using the bus. Actual address bus conflicts are not a major factor (see 6.3).Although ideally the MEMORY stage is regular, in fact collisions with the processor can happen;these irregularities are partially compensated by the two words of buffering after MEMORY. Inaddition cache misses, though very rare, cost about 30 cycles when they do occur.There is only one dependency on the rest of the execution pipeline: starting the IFU at a new PC.Since no attempt is made to detect modifications of code being executed, or to execute brancheswhich depend on the values of variables, the only IFU-processor communication is hand-offsynchronization and resetting of the PC, and these are also the only communication between the IFUstages. The IFU is completely reset when it gets a new PC; no attempt is made to follow more thanone branch path, or to cache information about the code within the IFU. The shortage of bufferingmakes the implementation of synchronization rather tricky; see 5 .The IFU takes complete responsibility for keeping track of the PC. Every item in the pipe carries itsPC value with it, so that when an instruction is delivered to the processor, the PC is delivered at the^sG ;qXL"sq %V@UD";S #sq'R<FP -LtX Iq.'H +6FCEZC~KA@sq@vr qBsqsq >"+sq=n>;V:f sq38/sq!51l3_sq$,1l/Sl-+<*"<)O>' K &G;sq"HtXq sq.#sq*2:sq A`^ sq%4sqVI+> sq sq +/ #,sq$ sqsqsq'sq(@sq?sq8sqdsqJsqV HcAN 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.LsqXs qsqsqsqsqsqs qsqsqF@,0sqDSC8 @ sq-sq >I=,sq';!99sq?8y5(6(sq5qsqsq+3:sq2i[0L/asq2s-qV,Y*/*sq.sq$&uXvu"q%3!Ssq,3&K &2 TC:sq.1;2X'4? L,sq) 2 PR1HK tqBlF Od HQySEC. 4IFU-PROCESSOR HAND-OFF35<==>MEMORYoutputbuffer.........^sG&T;qtd12 Hcx0`2r2r0`6r$;Ir$1Ir$,r$r&`r((&`F HDrHDrF Lr$Pr$;}=r=r;}Ar$Ffr$:JG:FG:@mG:;mG9:4G9:1mG#pdN.C8.4$3$2 $2$ sk!VkHkHk2r6I$r z$5$95$9 z$d 6]$ z$: z$ r|F F F r;};};}q"r#e" x     6$6I$p&,$&,&, @&,u#A"%]#A]"%Susk!V)k*:);k);k*VJ$K$VFf$U$9Ugr$q"($!- kA&k-Hk-Hk2!V @$" $"s $Kf$(;m$VJ$(=$ V# "s: r . ]$J :6 $7 :$y7% $9 $($!(s$!Vs$=Bq#?{"@P$BxDp&$+$$V+ V 9 rQU$$y$$,$$ 9$ $O$U ,$ ,$yrtrVl$rV$rrsr $y $$U $$%$ 9%$ 9$:$ r:$:,$y$y$y$ey$V^$V$$$V]$$y$y$Wy$:y$$l$s$ :$ ]$2 l$ ]$ 9$G 9$9k $ $9 V$ ,$9$9uVvsuO$$$d$V]$$,x ! dLo      ?=; H9$=B$r; ]$; $<%$r?{$r=B,9$=B9$?{$C_$-%VH,,$>^ >^9ts:V:83]$8]$7|_5_4_f< $ A$ d$ $ @d$ @$ @$ @A$ @$ @$ $y A$y $:$]T$$:T$d:Q$]Q$T$2>E VAN INSTRUCTION FETCH UNIT FOR A HIGH-PERFORMANCE PERSONAL COMPUTER364.1 How the processor sees the IFUThe processor has four main operations for dealing with the IFU. Two are extremely frequent:IFUJump: The address of the next microinstruction is taken from the IFU; a ten bit bus passes thedispatch address to the processor's control section. In addition, parts of the processor state areinitialized from the IFU, and other parts are initialized to standard values (see 4.2). IFUJumpcauses the IFU to hand off an instruction to the processor if it has one ready. Otherwise the IFUdispatches the processor to the NotReady location. The microcode may issue another IFUJump at thatpoint, in which case the processor will loop at NotReady until the IFU has prepared the next instruc-tion. An IFUJump is coded in the branch control field of the microinstruction, and hence can bedone concurrently with any data manipulation operation.IFUData: The IFU delivers the next field datum on the IFUData bus, which is nine bits wide (eightdata bits plus a sign). Successive IFUData's during emulation of an instruction produce a fixedsequence of values determined by the decoding table entry for the opcode, and chosen from: a small constant N in the decoding table entry;the alpha byte, possibly sign extended;either half of the alpha byte;the beta byte;the instruction length.IFUData is usually delivered to the A bus, one of the processor's two main input busses, from whichit can be sent through the ALU, or used as a displacement in a memory reference. In this case it isencoded in the microinstruction field which controls the contents of this bus, and hence can bedone concurrently with all the other operations of the processor. IFUData can also be delivered to B,the other main input bus, from which it can be shifted, stored, sent to the other ALU input, oroutput. This operation is encoded in the special function field, where it excludes a large number ofrelatively infrequent operations as well as immediate constants and long jumps, all of which also usethis field. For the details of the processor and its microinstructions, see [8].The other two IFU-related operations are less frequent, and are also coded in the special functionfield of the microinstruction:PC: The IFU delivers the PC for the currently executing instruction to the B bus.PC_: resets the IFU and supplies a new PC value from the B bus. The IFU immediately startsfetching instructions from the location addressed by the new PC.In addition there are a number of operations that support initialization and testing of the hardware. Strictly speaking, the IFUData and PC operations do not interact with the IFU. All the informationthe IFU has about the instruction is handed off at the IFUJump, including the field data and the PC(about 40 bits). However, these bits are physically stored with the IFU, and sent to the processorbusses incrementally, in order to reduce the width of the busses needed (to 9 bits, plus a 16 bit busmultiplexed with many other functions). From the microprogrammer's viewpoint, therefore, thedescription we have given is natural. We illustrate the use of these operations with some examples. First, here is the actual microcodefor the PushConstant instruction introduced in 2.PushConstantByte:Push[IFUData], IFUJump;-- Reduced from 9 microinstructions to 1!To push a 16 bit constant, we need a three byte instruction; alpha contains the left eight bits of theconstant and beta the right eight bits.XsG@qR_tXwO4q9sqL srq,sqJKI sqAsrG}qsq3sEq rqsrqDu rq sqBsrqOAm3>Bsrqsqsrq$< srq5;:S9rq82'65* 30{srqsq..sq'-s=+>srqsq*kOsq (@'c !:%M" sqQ!0sqsq sq0sqsq sqsqsq sq5sqfy srqsq%sqsq0srqsqq5 sq&9i 6  Q 6r qQsaxsGxs)q(<d |H]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. ^sG&T;qXtsaW6xs'aU vsxsxsvsLRq*sq0QI5%O ,MmMKsrqIsrq'H 0EsrqsrqsrqD1 srq )Brq?5r q=X3?Erqrq1rqrqrqI07 W.'yrq&rq-/ rq<+s4G ) 4'4&4%S4$4: qJsG2axsxs  aL xsxsa vsxsxsxsq0rq2rqtX qJ t qN | '+QtX./l(rq%ad HczAN 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._2sG@qX8WWLUrqrSs aRG5aQFxsxs aPxs3Mq>rqL, sq ,J.r I$qrqrqGsaExsGxs&aDxs3Alq.tqr ?q .r q>d rtqC< T;\X9 sqsq169&5) Q3L2! sq&"0?/E- D,F* sqsq&)  R''sq'#tX [q8>SN VK tq#ZC5tqtqtq tq9(tq/tqtq%tqsrqtqJ >" 5) |srqsrqtqtq*!sq+sqtK ClI Ad> Hd(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^sG&T;qW8r qVBATr q+*S:#6Qr q%r q P2srq$MMsaLxsGxsDJ GaFxsxsWCq$stq r Aq;r q@{ R>3*=s rq1;r q48*rq!5sa4G4a3cxs0~a/@xsQ.*q'4)Srqrq '<#&KE$rq"#C DtXqsq1Gr q Dsq 8 srq:$s Gxsxsavsvsxs (axsxsxs*xsxsa Yxsxsxs xsa xsxa spws$x s%tq!7 srq*sq l2sqsq sq,dr qBL HcAN 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;_XsG@qY=srqW}TRLRrsrq)QJ uq?O4LsGxs#aKxsExsJeaI'xsF+xsxsaEmxsxsaD/xsxaBspws$xAs%>qP=sq*;srqsqsrq192rq8xU3uX0zq .sq.=#-rDs+q]*j+0(=$'b8%%V"I!/ R?'rq rqrq)=rpqr(pq(rqP C-/6+;t q$*L3R"3t+qL rqLr #q :t1*tqE tq lLFdc HdNSEC. 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 rqrqrq#-z=F= F=(F#= F-z=oF;sq rzq #-z 9 -z 8{-z7F7 F7(F#7 F-z7oF5ssq sr#q-zrq-z3sq3F3 F3(F#3 F-z3oF0sq srq#06/c06 /c 06(/c(#06 /c -z06o/co- 'td1 Hc4d #9$$  ]$ $ @ !9$ 9$ H9$ 9$"H    e V"H V  V V:9$:H9$:9$:!9$:$ @:]$s$ :#9$#9$$ ]$$ @!9$9$H9$9$9$H9$9$!9$$ @]$V$ #9$#9$ $ ]$$ @!9$9$H9$9$#9$#H9$#9$#!9$#$ @#]$%:$ ##9$'s#9$)$ 's]$'s$ @'s!9$'s9$'sH9$'s9$+9$+H9$+9$+!9$+$ @+]$.$ +#9$  + d +U$ dU$ U$ U$ $ @ y$$  U$:U$$ :U$: U$: dU$:+U$ Vd V + V  V:$ :y$y$$ +U$ dU$ U$U$$ U$U$s$ U$ U$ dU$+U$$ y$y$$ +U$ dU$ U$U$!$ U$#U$&W$ #U$# U$# dU$#+U$#$ #y$'sy$'s$ 's+U$'s dU$'s U$'sU$*$ 'sU$+U$/;$ +U$+ U$+ dU$++U$+$ +y$"H e:"H: :"He #"H##e( (,s"H,s,se:e$:$,$ $e$$"$("$($(e$#,$# $,s $,s,$,$  +d:U$:U$: U$ U$U$U$:d: +dU$U$ U$V: : + :d + ## # +#U$# U$# dU$#d( +'s dU$'s U$( ('s dU$'s U$'sU$(d,s ++ U$+ dU$++U$,s+ dU$++U$,s +U$+ U$+ dU$++U$-($,sd V$ $<E/^$AN INSTRUCTION FETCH UNIT FOR A HIGH-PERFORMANCE PERSONAL COMPUTER42Figure 5a illustrates this cogging. Figure 5b shows that with two items of buffering after each stage,local control does not cause cogging. The Dorado has small buffers and global control partlybecause buffers are fairly costly in components (see below), and partly because this issue was notfully understood during the design. Note that it is easy to implement global control over a groupof consecutive stages which have no irregularities, since every stage can safely advance if there isroom in the buffer of the last stage. In this IFU, alas, there are no two consecutive regular stages.Unfortunately, the cost of buffering is not linear in the number of items. A two item buffer costsmore than three times as much as a one item buffer; this is because the latter is simply a register,while the former requires two registers plus a multiplexor to bypass the second register when thebuffer is empty, as shown in Figure 6. Without the bypass a larger buffer increases the latency ofthe pipe, which is highly undesirable since it slows down every jump which the IFU doesn't predictsuccessfully. Once the cost of bypassing is paid, however, a multi-item buffer costs only a littlemore, since a RAM can be used in place of the second register. Although there are no such buffersin the Dorado, it is interesting to see how they are made.<==;$9$9$@2x,0W,/;1$.$.j9$0U$95W$3j]$3U$9+W$)t,3e ::uG:* 28$! $9q       : 7x45W $93 $7 $]:Wt ? 3j$9;$3@$3$:W x3 $3 @$9; $3 M$6t $6t $7j$]5W$94xd7d:Wt? :W#r $9s $9s$V$V$ r$$s$N$N $q$$$x   Vpj7x He&W&W+W,su),s ~& c$@-rKSEC. 5IMPLEMENTATION43adder would be needed to handle the variable instruction lengths, and it would cost about fourtimes as much.Every item also carries a status field, which is used to represent various values that do notcorrespond to ordinary instructions: empty, page fault, memory error. These are converted intounique dispatch addresses when the item is passed to the processor, as discussed in 3.4.5.1. ADDRESS stageThis stage generates the addresses of memory words which contain the successive bytes of code.Unlike the other stages, it has no ordinary input, but instead contains a PC which it increments bytwo (there are two bytes per memory word) for each successive reference. The PC can also take ona pause value which prevents any further memory references until the processor resupplies ADDRESSwith an ordinary PC value. This pause state plays the same role for ADDRESS that an empty inputbuffer plays for the other stages; hence it is entered whenever this stage is reset. That happenseither because of a processor Reset operation (which resets the entire IFU pipe, and is not doneduring normal execution), or because of a Pause signal from DECODE. Correspondingly, a new PCcan be supplied either by a processor PC_ operation, or by a Jump signal from DECODE when it seesa jump instruction. Any of these operations resets the pipe between ADDRESS and DECODE; theprocessor operations reset the later stages also. ADDRESS makes a memory reference if the memory is willing to accept the reference; thiscorresponds to finding space in the buffer between ADDRESS and MEMORY, although theimplementation is quite different because the memory is not physically part of the IFU. In addition,ADDRESS contends with the processor for the memory address bus; since the IFU has lowest priority,it waits until this bus is not being used by the processor. Finally, it is necessary to worry aboutspace for the resulting memory word: the memory, unlike ordinary IFU stages, delivers its resultunconditionally, and hence must not be started unless there is a place to put the result. ADDRESSsurveys the buffering in the rest of the pipe, and waits until there are at least two free bytesguaranteed; it isn't necessary for these bytes to be in the MEMORY output buffer, since data in thatbuffer will advance into later buffers before the memory delivers the data. It is, however, necessaryto make the most pessimistic assumptions about instruction length and processor demands. On thisbasis, there are seven bytes of buffering altogether: four after MEMORY, two after BYTES, and oneafter DECODE.5.2 MEMORY stageThis stage has several peculiarities. Some arise from the fact that most of it is not logically orphysically a part of the IFU, but instead is shared with the processor and I/O system. As we saw inthe previous section, the memory delivers results unconditionally, rather than waiting for bufferspace to be available; ADDRESS allows for this in starting MEMORY. Furthermore, the memory hasconsiderable internal state and cannot be reset, so additional logic is required to discard items whichare inside the memory when the stage is reset.Other problems arise from the fact that the memory's latency is more than one cycle; in fact, itranges from two to about 30 cycles (the latter when there is a cache miss). To maintain fullbandwidth, the IFU must therefore have more than one item in the MEMORY stage at a time; sincel=2 when the cache hits, and this is the normal case, there is provision for up to two items inMEMORY. A basic principle of pipeline stages is that items emerge in the order they are supplied.A stage with fixed latency, or one which holds only one item, does this automatically, but MEMORYhas neither of these properties. Furthermore, its basic function is random access, with no sequentialrelationship between successive references. Hence if one reference misses and the next one hits, thememory is happy to deliver the second result first. To prevent this from happening, the IFUnotifies the memory that it has a reference outstanding when it makes the second one, and thememory rejects the second reference unless the first one is about to complete.[0sG+I ;qT3&SUP*tq=N !4M"TI#tXwtEqTDtDsq BKsqAlrq=s?q sqrqsq>d9#< rq$sq;\ rq sqs9q#sqrq sq8TDsqsq6)3sq22! sqsq 0 8 sq/sq+sq-F,Bt qPA& B?+/> F< P;"7tXwt3qL2hP/=#sq/-Csq,5K*/sq)-sq'&Z&&Z & &Z(&(#&Z & -z&Zo&o$~t #F# F#(F## F-z#oF r q 2r Vq +r Vq -Br Vq 7r Vq :r Vq 9r Vq 8^r Vq sqsqsq rq  rqVr Vq sq  ((#  -zoom X% |^sqtsqQ Fl0sq%sq$tqdGtq  @HbSEC. 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.<==+$97$V'$9&-&-&-t**'V$%$9%$9 ;J $'&t%W :$93$9 :,&$/p(  ,$ AG Gr +G G t<+$ ]B'$37$.p431$936m$.6J $9;44$9.4 @$.4$]8+$A*$8* $8*$@$*$@$* $-*$$+$+t1'sp.$-G$- +G-.Gr$2BG)'$<'$-1$%0-3;J$]->)+$937 r$#&-:&-A&-(t*;t*#'!V$DX%$9#%$9#6$%:6$'s6$)6$+6$.6$:X6$86$56$36$1t6$/;6$#,$%:,$'s,$),$+,$.,$:X,$8,$5,$3,$1t,$/;,$#4$#2$#0Q$#.$;t.$;t0Q$;t2$;t4$0q. Vp9.9.;J $894$9.9 $.9$]t89V94$9;9;;894$99;99;8894$9$9sWp,s $$9s $s$]3t33VO$s$$$]$ $/;$9$ $/;$9&Wp, s$$]$V3$9x  s$V$$)O$ r)$V$0O$#@$#$I $$$p!,-:x$':$': D: D D( D< DA D<$'($':323 C) C)0W2.-) :) :'$#%!z$%z$p!*FD{?QAN INSTRUCTION FETCH UNIT FOR A HIGH-PERFORMANCE PERSONAL COMPUTER46DECODE replaces the dispatch address from the table with an exception address if necessary. Inorder to obey the rule that exceptions must all be captured in the dispatch address, the exceptionvalues of all the instruction bytes are merged into its computation. For three-byte instructions, thisrequires looking back into BYTES for the state of the beta byte. If any of the bytes is empty,DECODE keeps the partial instruction item when it delivers an empty item with a NotReady dispatchinto its output buffer. If a Reschedule is pending, it is treated like any other exception, byconverting the dispatch address of the next instruction item into Reschedule. Thus there is always ameaningful PC associated with the exception.If the Jump field is set, DECODE computes a new program counter by adding an offset to the PC ofthe instruction. This offset comes from the alpha byte if there is one, otherwise from N andSplitAlpha; it is sign-extended if Sign is true. The new PC is sent back to ADDRESS, as described in 5.1, where Pause is also explained. Jump instructions in which the displacement is not encoded inthis way cannot be executed by the IFU, but must be handled by the processor.5.5 DISPATCH stageThe interesting work of this stage is done by the processor, which takes the dispatch address,together with the state initialization discussed in 4.2, from the DECODE output buffer when itexecutes an IFUJump. Because empty is encoded into a NotReady dispatch, the processor takes noaccount of whether the buffer is empty. There are some ugly cases, however, in which DECODE isunable to encode an exception quickly enough. In these cases DISPATCH asserts a signal called Holdwhich causes the processor to skip an instruction cycle; this mechanism is rather expensive toimplement, and is present only because it was essential for synchronization between the processorand the memory [1]. Once implemented, however, it is quite cheap for the IFU to use. TheNotReady dispatch is still preferable, because it gives the microcode an opportunity to do someuseful work while waiting.5.6. EXECUTE stageThis stage implements the IFUData function; as we have already seen, it is logically part of theprocessor. The sequence of data items delivered in response to IFUData is controlled by Jump,Length, N, and SplitAlpha according to Table 3; in addition, alpha is sign-extended if Sign is true.EXECUTE also provides the processor with the value of the PC in response to a different function.JumpLengthNSplitAlphaIFUDataYesLength, . . .No1NoLength, . . .No1YesN, Length, . . .No2NoNoalpha, Length, . . .No2NoYesalphaHigh, alphaLow, Length, . . .No2YesNoN, alpha, Length, . . .No2YesYesN, alphaHigh, alphaLow, Length, . . .No3NoNoalpha, beta, Length, . . .No3NoYesalphaHigh, alphaLow, beta, Length, . . .No3YesNoN, alpha, beta, Length, . . .No3YesYesN, alphaHigh, alphaLow, beta, Length, . . .Table 3: Data items provided to IFUDataYsG@qSsqCRUPDOsq(rqMsq .rq rqL r q7J 2r qI sqErqsq;sqDR%rq,rqBr qrqsq sqAJrq))?sq';tXwt8q<7H^]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.WwsG- ;qQ uX Mq#>Lq$;JKIi C sqGYFaVD3,CY2@.U>I=&L;$:: R8$97Nsq3L 2gP0N/_ R-\)tX&qsq1%-,#S"%9tq sq sq srq rvq]Vn%9sqsqfL  "sq+ 3@rq srq("+; tqsq | /'3,t Irq2lsq J DdV H\mAN 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.TsG@qNtXKYq[sIq4(HQ=E&sq0C?rqB $?=nsq;8sq6f.14 rq'3^A03sqD.rqL-+?+ /sqsq*# &rq 9%tW#5sq"l H 0+dV -tXq&32sq?sq& *@sq;"sq- <  tX q,4l&7 sqEd5 WHYQSEC. 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.SVsG- ;qLtXIq!sqHPCE}E%E} E% E}(E%(#E} E% -zE}oE%oBtAFA FA(F#A F-zAoF>sqsnq=msnq;snq:esnq c8n7]n c5n5(4U5( 4U 5((4U(#5( 4U -z5(o4Uo1*X!s-q6sqsq,{sq sq+*sq`'F&HH$!!! ! !(!(#! ! -z!o!oAt SFS FS(F#S F-zSoF9q1s;q)sqsq 4; sq/!;pp  p((#p  -zpoorX utq sq0()lUCd HXL 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. SoftwarePractice 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.,sG@q&/u "s{ wsOxs{!B{sws A{ wsxsw s{9w1s{A{4xsws{svs{Nw{w{sA{ {ws {4wsvs{Sw{A s xs9xs{{wswsxs3A{xsws{svs{Qws{svs{  A{ ws- { ws"w*s{ Dxs/{d{ws({P{wsvsA{ wsF{swsvs{ {Pws{sws{d  9H1| 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 HELVETICA  HELVETICA  HELVETICA  HELVETICA HELVETICA HELVETICATEMPLATE@ GATES _  I j N+ I5 <? ?JO (Z ,ej Nu ~r c > D . = 6 .  s  Q!essedit.RUN/m.%(Paper*.CMZUZ'pressedit.RUN.ress MemFig7.press MemFig8ZoZ'pressedit.RUN.ss MemFig4.press MemFig5.pZZ'presseditress MemFig15.prespressedit.RUNZ[?'.Rj/ifuFinal.presspiera13-Jan-81 16:22:51 PST