The Dorado: A High-Performance Personal ComputerThree PapersCSL-81-1January 1981ABSTRACTThis report reproduces three papers on the Dorado personal computer. Each has been, orwill be, published in a journal or proceedings.A Processor for a High-Performance Personal Computer, by Butler W.Lampson and Kenneth A. Pier. Appeared in Proc. 7th Symposium on ComputerArchitecture, SigArch/IEEE, La Baule, May 1980, 146-160.An Instruction Fetch Unit for a High-Performance Personal Computer, byButler W. Lampson, Gene A. McDaniel, and Severo M. Ornstein. Submitted forpublication.The Memory System of a High-Performance Personal Computer, by DouglasW. Clark, Butler W. Lampson, and Kenneth A. Pier. A revised version will appear inIEEE Transactions on Computers. The first paper describes the Dorado's micro-programmed processor, and also gives anoverview of its history and physical construction. The second discusses the instruction fetchunit, which prepares program instructions for execution, and the third deals with the cache,map and main storage of the Dorado's memory system.c Copyright 1981 by Xerox Corporation.XEROXPALO ALTO RESEARCH CENTER3333 Coyote Hill Road / Palo Alto / California 94304 \p Y>$ SQ LqX Dor ADsJ ?+G< K;C9#78 C3<{wX{0wO .zw(- 7*.+)-$&7%Q". 7v7'&7nzwzw#3 ;:;zw% <3*zwJ+zwL zw= # R tH 0l !,+,dB HcSEC. 2HISTORY3microcoding the Model 0, together with the significant improvements in memory technology sincethe Model 0 design was frozen, to redesign and reimplement nearly every section of the Dorado.We fixed some serious design errors and a number of annoyances to the microcoder, substantiallyexpanded all the memories of the machine, and speeded up the basic cycle time. Dorado Model 1came up in the spring of 1979. During the next year several copies of this machine were built in the stitchweld technology used forthe prototypes. Stitchwelding worked very well for prototypes, but is too expensive for evenmodest quantities. Its major advantages are packaging density and signal propagation characteristicsvery similar to those of the production technology, very rapid turnaround during development(three days for a complete 300-chip board, a few hours for a modest change), and completecompatibility with our design automation system.At the same time, the design was transferred to multiwire circuit boards; the Manhattan wirerouting and lower impedance of this technology slowed the machine down by about 15%. Doradosare now assembled with very little in-house labor, since boards and backpanels are manufacturedand loaded by subcontractors. We do 100% continuity testing of the boards both before and afterthey are loaded with components and soldered. Checkout of an assembled machine is still non-trivial, but is a fairly predictable operation done entirely by technicians.3. GoalsThis section of the paper describes the overall design goals for the Dorado. The high levelarchitecture of the processor, described in the next section, follows from these goals and thecharacteristics of the available technology.The Dorado is intended to be a powerful but personal computing system. It supports a single userwithin a programming system which may extend from the microinstruction level to a fullyintegrated programming environment for a high-level language; programming at all levels must berelatively easy. The machine must be physically small and quiet enough to occupy space near itsusers in an office or laboratory setting, and cheap enough to be acquired in considerable numbers.These constraints on size, noise, and cost have a major effect on the design.In order for the Dorado to quickly become useful in the existing CSL environment, it had to becompatible with the Alto software base. High-performance Alto emulation is not a requirement,however; since the existing software is also obsolescent and due to be replaced, the Dorado onlyneeds to run it somewhat faster than the Alto can.Instead, the Dorado is optimized for the execution of languages that are compiled into a stream ofbyte codes; this execution is called emulation. Such byte code compilers exist for Mesa [3, 6],Interlisp [2, 7] and Smalltalk [4]. An instruction fetch unit (IFU) in the Dorado fetches bytes fromsuch a stream, decodes them as instructions and operands, and provides the necessary control anddata information to the processor; it is described in another paper [5]. Further support for this goalcomes from a very fast microcycle, and a microinstruction powerful enough to allow interpretationof a simple macroinstruction in a single microinstruction. There is also a cache which has a latencyof two cycles, and can deliver a word every cycle. The goal of fast execution affects the choices ofimplementation technology, microstore organization, and pipeline organization. It also mandates anumber of specific features, for example, stacks built with high speed memory, and hardware baseregisters for addressing software contexts.Another major goal for the Dorado is to support high-bandwidth input/output. In particular, colormonitors, raster scanned printers, and high speed communications are all part of the researchactivities within CSL; one of these devices typically has a bandwidth of 20 to 400 megabits/second.Fast devices should not slow down the emulator too much, even though the two functions competefor many of the same resources. Relatively slow devices must also be supported, without tying upthe high bandwidth I/O system. These considerations clearly suggest that I/O activity and emulationshould proceed in parallel as much as possible. Also, it must be possible to integrate as yet^[zG0<8wX IV@TWSxNQN^ME,.K"=J=DH HG5 #D VBRA N?~ S=*/OMNYL IjUG BFbMA{X>dw"9<#2;\ C96?5)Pzw3zw?2! G0=$/T-!6, R(/04'b zwzw%)zw z$Zw E "#c}"w#c}"w?!RP'[; zw1 :W"@'9TY+ X,zwzw% =zwzw PD5tD |w/l )zwzw <dzwzw  6H]SEC. 4HIGH LEVEL ARCHITECTURE5<==PanelWiringSideSideWiringPanel-5-2+5+12VVVVxxxx250757025AAAAFigure 1a: Dorado chassisStorage Storage Storage Storage Storage Storage Memory addressingInstruction fetch unitProcessor, high byteProcessor, low byteControl sectionMicroinstruction memoryBaseboardStorage Storage Disk/Ethernet controllerDisplay controllerI/OI/OI/OI/OI/O10.5 inPipe, map and storage controlCache data, error correctionInstructionProcessorCacheStorageSlow input/outputFast input/outputEthernetDiskDisplayKeyboardFetch Unit8K-32KbytesFigure 1b: Dorado block diagram<==<<265 MBits/sec16 bits/60 ns265 MBits/sec16 bits/60 ns120 ns access530 MBits/sec256 bits/480 ns1.7 us accessAir plenumBoard Area288 16-pin DIPs (logic)and144 8-pin SIPs (terminators)per board512K-16M bytesfzG%z<8wtd24 Hk r# 6#'p$:('$)& $(%@$(%$@(V<$)UC$(U @$(U $@J V<$K&UC$J U @$J U $@J '$K&& $J %@$J %$@'VHVH^$:1U$7T'$1T@$1T$U2%|O3O5zO=O?{OA%OKU$K&s$KQoK#Q&zp_KK$K|GK&pPK|FK+K)LB>$ LB.^$ K&p^K$?{K$@K$AK$BK$CK$E K$F%K$GBK$H^K$I{K$H.;$G.;$F.;$E.;$D{.;$C^.;$BB.;$A%.;$@ .;$>.;$=.;$<.;$;.;$:z.;$9^.;$8A.;$7%.;$6 .;$4.;$3.;$2.;$1.;$0z.;$/^.;$.A.;$-%.;$,.;$*.;$).;$2R|$4^R|$6 R|$>^R|$@ R|$AR|$*=&$ E=E:-E; ?Q!$@!$B_!$H|!$F!$Em!$C!$J!$K!$M!$N!$V^ $k r   r  ]9$ z$9] V]$] V$]@ V$]@ V$ z$9@r$ $$ z$9  V@$  V$]GyGG $2 G,Vk#$ z$9# V$# V$]<%O9G %$%, k5zpV6 !zky (%tdp  (% (% ' (% ' (%V 6 rO 5zE 2pB;8@1>7%=; B4lO-c'A PROCESSOR FOR A HIGH-PERFORMANCE PERSONAL COMPUTER6Second, when the processor is available to each device, complex device interfaces can beimplemented with relatively little dedicated hardware, since most of the control does nothave to be duplicated in each interface. For low bandwidth devices, the force of thisargument is reduced by the availability of LSI controller chips, but for data rates above onemegabit/second no such chips exist as yet. Of course, to make this sharing feasible, switching the processor must be nearly free of overhead,and devices must be able to make quick use of the processor resources available to them.Many design decisions are based on the need for speed. Raw circuit speed is a beginning. Thus,the Dorado is implemented using the fastest commercially available technology which has areasonable level of integration and is not too hard to package. In 1976, the obvious choice was theECL 10K family of circuits; probably it still is. Secondly, the processor is organized around twopipelines. One allows a microinstruction to be started in each cycle, though it takes three cycle tocomplete execution. Another allows a processor context switch in each cycle, though it takes twocycles to occur. Thirdly, independent busses communicate with the memory, IFU, and I/O systems,so that the processor can both control and service them with minimal overhead.Finally, the design makes the processor both accessible and flexible for users at the microcode level,so that when new needs arise for fast primitives, they can easily be met by new microcode. Inparticular, the hardware eliminates constraints on microcode operations and sequencing often foundin less powerful designs, e.g., delay in the delivery of intermediate results to registers or incalculating and using branch conditions, or pipeline delays that require padding of microinstructionsequences without useful work. We also included an ample supply of resources: 256 generalregisters, four hardware stacks, a fast barrel shifter, and fully writeable microstore, to make theDorado reasonably easy to microcode. 5. Low level architectureThis section describes in some detail the key ideas of the architecture. Implementation techniquesand details are for the most part deferred to the next section; readers may want to jump ahead tosee the application of these ideas in the processor. Along with each key idea is a reference to theplaces in the processor where it is used.5.1 TasksThere are 16 priority levels associated with microcode execution. These levels are called microtasks,or simply tasks. Each task is normally associated with some hardware and microcode whichtogether implement a device controller. The tasks have a fixed priority, from task 0 (lowest) to task15 (highest). Device hardware can request that the processor be switched to the associated task;such a wakeup request will be honored when no requests of higher priority are outstanding. The setof wakeup requests is arbitrated within the processor, and a task switch from one task to anotheroccurs on demand, typically every ten or twenty microcycles when a high-speed device is running.When a device acquires the processor (that is, the processor is running at the requested prioritylevel and executing the microcode for that task), the device will presumably receive service from itsmicrocode. Eventually the microcode will block, thus relinquishing the processor to lower prioritytasks until it next requires service. While a given task is running, it has the exclusive attention ofthe processor. This arrangment is similar in many ways to a conventional priority interrupt system.An important difference is that the tasks are like coroutines or processes, rather than subroutines:when a task is awakened, it continues execution at the point where it blocked, rather than restartingat a fixed point. This ability to capture part of the state in the program counter is very powerful.Task 0 is not associated with a device controller; its microcode implements the emulators currentlyresident in the Dorado. Task 0 requests service from the processor at all times, but with the lowestpriority.]zwXzwzwzwzwz wzwzwWwLU JTo%-R zw/Qg N<5+LUIJH 6F EEzw[C} 5&A<@u%zwzwzw>L;W:B N8 K 7:C5 H42B2 Y1*,W{X),wD'V&$&;$# |Xvw?| w|wCn//Lf| w9?|w^Z3JG+ |w. K #O M.3clGNdR dHbSEC. 5LOW LEVEL ARCHITECTURE75.2 Task schedulingWhenever resources (in this case, the processor) are multiplexed, context switching must onlyhappen when the state being temporarily abandoned can be restored. In most multiplexedmicrocoded systems, this requires the microcode itself to explicitly poll for requests, save andrestore state, and initiate context switches. A certain amount of overhead results. Furthermore,the presence of a cache introduces large and unpredictable delays in the execution of microcode(because of misses). A polling system would leave the processor idle during these delays, eventhough the work of another task can usually proceed in parallel. To avoid these costs, the Doradodoes task switching on demand of a higher priority device, much like a conventional interruptsystem. That is, if a lower priority task is executing and a higher priority device requests a wakeup,the lower priority task will be preempted; the higher priority device will be serviced without theconsent or even the knowledge of the currently active task. The polling overhead is absorbed bythe hardware, which also becomes responsible for resuming a preempted task once the processor isrelinquished by the higher priority device.A controller will continue to request a wakeup until notified by the processor that it is about toreceive service; it then removes the request, unless it needs more than one unit of service. Whenthe microcode is done, it executes an operation called Block which releases the processor. Theeffect is that requesting service is done explicitly by device controllers, but scheduling of a giventask is invisible to the microcode (and nearly invisible to the device hardware).5.3 Task specific stateIn order to allow the immediate task switching described above, the processor must be able to saveand restore state within one microcycle. This is accomplished by keeping the vital state informationthroughout the processor not in a single rank of registers but in task specific registers. These areactually implemented with high speed memory that is addressed by a task number. Examples oftask specific registers are the microcode program counter, the branch condition register, themicrocode subroutine link register, the memory data register, and a temporary storage register foreach task. The number of the task which will execute in the next microcycle is broadcastthroughout the processor and used to address the task specific registers. Thus, data can be fetchedfrom the high speed task specific memories and be available for use in the next cycle.Not all registers are task specific. For example, COUNT and Q are normally used only by task 0.However, they can be used by other tasks if their contents are explicitly saved and restored.5.4 PipeliningThere are two distinct pipelines in the Dorado processor. The main one fetches and executesmicroinstructions. The other handles task switching, arbitrates wakeup requests and broadcasts thenext task number to the rest of the Dorado. Each structure is synchronous, and there is no waitingbetween stages.The instruction pipeline, illustrated in Figure 2, requires three cycles (divided into six half cycles) tocompletely execute a microinstruction. The first cycle is used to fetch it from microstore (time t-2 tot0). The result of the fetch is loaded into the microinstruction register MIR at t0. The second cycleis split; in the first half, operand fetches (as dictated by the contents of MIR) are performed and theresults latched at t1 in two registers (A and B) which form inputs to the next stage. In the secondhalf cycle, the ALU operation is begun. It is completed in the first half cycle of cycle three, and theresult is latched in register RESULT (at t3). The second half of cycle three (t3 to t4) is used to loadresults from RESULT into operand registers.XozG%<8wR|XNw(-Mi/"K %1JaN HO GY.)E%7DQO B SAI|w$?<>A.|w< 9$=8D64~w#5I3M/|X,Xw=#*.4)P 8| w '+)&H:$*/#@8! Z 8R " zwzw"U|X _wJ >W'8 >|w| w $ W~  $w 6~ 6w4zw~ 6wHGzw ~7wzwzw ) zwQRzw~Rw$~Rw~Rwdzw H]eA PROCESSOR FOR A HIGH-PERFORMANCE PERSONAL COMPUTER8<==MIRFetch fromInstruction memoryoperandfetchABoperandmodification>>>resultstorefirst cyclesecond cyclethird cycleT4T3T2T1T0T0T1T2T3T4T4T3T2T1T0T0T1T2T3T4T4T3T2T1T0T0T1T2T3T4T-2T-1T-1T-2T-2T-1T-1T-2T-2T-1T-1T-2<>>><<>>>>ResultInstruction PipelineTiming OverlapFigure 2: Instruction pipeline and timing overlap<==<>>>>>>>WakeUpTaskfetch Next task specific statefetch Next microinstructionbroadcast Next taskCurrentTaskCurrent<>>+$p1"d $ ]$ k $+ ]$z ]$z ]$ $=9$54]$54]$1 ]$1t$A$99$9_]$1-$Pq?]E#IBr/;9z9G9 lG V %G %G A G lG  % G %G d AGV G G GzG lG V %G %G G G: VGs GGsG Ge|' CC C9G!zG8PGr!G!G! %G! %G8 lGr! GAG G  C:zGA lG V: %G: %G :G8A9G8 ^9GV3$V 3$V99rIH : e##&W 0W$;t < ;te l$ |BV,tp  C;3$V>>>bypass pathnormal pathmemoryPrevious Result Addressoperand fetchFigure 4: Bypassing examplemultiplexor switched ifCurrent Operand Address =<==<<^zwXzwzwzwzwz wzwzwW A~W1Ww~W1WwUPTLzwzw-zw&RQQD ~wHO&6N<~w ?LH|XEwT D 7B.+AT ?~.(=|w8G5/~w)D VB CA;?~;|X8Tw_61zw5L I3C2Dzwzw+0zwzw?/<7 zwzw-  G,4O*zw30),Lzw'Azw$}zwzw@zwz"wzwzwzwzw,!uEzwzw  UmC|wzwzwzwzw|wzwzw(e zwzw/3zwzw|X w|w*3 <5| w+zw O F | AP tY &~w0 lO\d~w H^A PROCESSOR FOR A HIGH-PERFORMANCE PERSONAL COMPUTER12<==>>>>rrrrCBrIMOutCPRegTLink*TPC*+1rrProcessorControlTPIMOutBestNextPCBestNextTaskNEXTIMAddressThisTaskNextPCLinkNextControlFFASelectLoadControlBSelectALUOPRAddressLink>>>*{PE}{Switch}{StartCycle}{StartCycle}{StartCycle}{InstructionDecode}{TPCByPass}{Switch}{UseCPReg}{ReadIM}{RAddr}{ReadLink}{Link_B}r{ }NextCtrlBlockmultiplexormultiplexor select signaltask specificFigure 5: Control sectionThisTaskLastTaskThisPCThisPC+1MemoryInstructionIMThisPCMIRt-2t0t2t-4Priority EncoderTLinkByPassLink_B{}<==<<>rr>rBBBBTLinkAddrTPCAddr`MzwXzwzwzwzwz wzwzwtd2L HeC'2R-R(HR*:O$9.O$92O$96sO$9*G,sI $*>X,sFfr$0;$ .5P$9,sJ$35P$.O$94: <O$9:O$99O$98O$9 R 9O$9 KD $K I GCU$2$95 $8$,s$:W$03$92Tn$ 9Tn$ 9M|$G$,sM$9OGVV$V$1PB$rO$]rR$&$+W&$V4$V6I+$2$9 O$]6$$&| 9  &`/1r1r5rDa F 9F  J6 L L rL Q()L.eL2L5L:L?(?)Gr  Kf$ r9 $H7B$ r7 $ r7$ ) +$'$ ' O$ $ ,$ ,$5W$4$*:>$*:>$*:Hr$.G_$*:G;$*:G;$K$ MX$IQ$9 9IQ$95 $9+C+W;G-5 G,s;$9O$ d&A G.e9$(G8 $U52$*:Dtr$2 z9G5AG G.2$*:$*:,$$*:B$ Kf$$AGr*$k*$$*A$G/H$@*e$$*Dt$k*Dr$.Ck$*D$k*E$/:C$@.Ck$,sE$],se$ 4G/:k$/Hk$7G%O$]%:L$pR$OGKf@$8,s *s*C/#0W|!. d$-B"sp "s K$K$MX$5:0!P$)7 7 27$)7f$1I '$-1I =O$r'sK*:2X. .X.!VX.X. X. X.UX.;tO$=W9Gr|_9$ H9$9+${p2vH4 d rF O#; (47 )$:W+,$:W$ =r(>'$D'$5 :\$$9;,lG0%$,sV$6I9$ +r$:H$ O$9V$27ft7r(et(r,trKtK94$ 9 pE9Yn$ VYn$rYn$Yn$$Yn$*:Yn$.Yn$6sYn$9Z/:$H$G;tV y$G%$.=TJ $R9$vl H%3$3$3 $9,s$) $- G#pd|'sH$.94$.56sTJ$y 9U&W$ 9 8ey$8,|>;&`)O$UO$U,s$*:O$/:O$($p('s1s+: +$ @0)$])$ C:W$,s?$>'%$ :[$Lj*H\LSEC. 5LOW LEVEL ARCHITECTURE13<==>>>>+Shifter.......................RM..>..r..COUNTALUMemBase>>>>>>>TIOAIOAddressAdder..ALUFMrLSH 1RSH 1.......StackPtrRBaseABExternalBIODatadevicesRESULT,....>>>>>>>memorymemorydevicesto I/OsmallconstantconstantRESULTBdata from>IFUAqFigure 6: Data sectionRAddrRaddr>register or memorylatchmultiplexor latchmultiplexornarrower data pathFFfrom t1 to t2from t2 to t3.>RT*task specific****LoadcontrolcontrolLoadALUOPaddress toRRTTMDQMDQRTMemData (MD)FFFFFF(copy of A)MemAdMDMemBALUFMALUALUALU.IFUconstconst(copies of B)IODataCOUNTIOAdBaseRegsto/fromcontrol,memory,IFU,to/from,XB{FF, mask}{bypass}{bypass}}{}{{control}{control}rother 16 bit pathpointerStackData readyshortly after t1Latches followLatches followData readyshortly before t3RAMs readat t1, load at t4load at t3RegistersBalso to RESULTshift 1 bit left or rightShiftCtl)(also toto RESULT<==<
$>$!3%W$  $$!$'s/$-($'s(f@$'s(f$!z*$ ],$(r+--+$/+$0tkd-kU-fk-k21k2d1k2d4$kA1$k$GU$GUA'kGd$kG"$3$.d$3_$.$/4$N33_d$ 39$ 3_9$.$.@$H1m$$1& $$/4$$1m$& $$$ r$# $ & $H& $#$9$$;$'& $ { $#$ d $ &$ !z%W$G(B$,.$2B$ < $$%($ d!z*{$ ],$!z*$ ]'$ ]-$G< k$2B $94{ k$/+$-+$$A&- y$$1 $$1m $/1m$/5-$ ]$A5 $$A5Q d$/5Q$ 's.@G's(f@G's(G-l(G23;k2$k2$^kH6$;kH"x+"*D"("&" D""C ]&$(Bk$.d$/4$!z0$!309$ 2B$2 $%3G$%44G$#d$#Bd$!z%4$$ $%(G$z+`z)'V z *D ,}  '%$%"|1 )n1 r|!$ 4z4 y9N$V9$8$$A! $"r2$$]$$9!zI$!z%k$"x$$z@$$$A;$'^$$e $?Q$9?-$?-$]Af$H$Fg$]Fg$F$9TK$R$]R$/B$ kB*$+W$$% $$:Wz=oF$B$UB$B$y|?E$G_$E$E$End$Du$*/4$d x>Dr?a G$ G_$kF9$FC$*:|+kL9$kL9$ yKC$ yK$rxCE DKC%$JJ$vK 3Br+-<N$%4X$5Q$UAvR 9|P 9O~ 9N>O~ yOJ9$K 9J 9LPC$N.$N.$]Pg$]vNO'/:G%:rO 2YG7TnG2T'GG2T'G)eY$k.eUk)Uk.U$)Y$)eU$k/U$.Xu$.X.$2lVR$]N.$]0WxP00WMi/Ug@$=$$9)$9*$9.$27G65G925tNG25tG2v6m43$4;|0=7%,m $9*{$=#r$="%$="%$$A"Ik$="I$9*$d9)$d9($9($29,&y$7%,&$>t+ >)^AxA A"|A$'A%A'}A)'9.;$9-$9-$= :$%<]$:/$:{/$:{/{$:/$G%^$3G_#l$;t1&$A;t1&$;1m$;1$K&W$<2$L$Jn$9JJ$]<3$VS.(%$='I@$;%44O$7WY $7W $9=$4$%4 $9'$ 9'm k$'&$-IS$[C$9R$9[C;$3$V2 $$ $%W$ $O1I$9 3_$ 1$U V1$y V$$y $$U V'$ V'$ & $#$9 V$$C;, $C;, r$L$dM;3$LB$M_$%:r2B%:&%:  %:"Fp!PFr,D4xSDODGDD`=%$=6J$B|2B0B/DB#B!S.y$L$@kF$ 9F 9DFpZDFV<FNuFOC;#G$.G $eG @ VEGU VIGU VMG VQ`G r@J ?- Fp[` VJn$$VNQ$VCX$V@J$|< vT H|$ H r:$ V8GU+S.$+|Q yS.]$p rv7 O*{V$6P|H$ $U $ $yp 9 $O$9,$9,$,z $ $]z $z $]G9 , U $s ,+$s +$s H$s,$U $,s $,s $,s $,s e$,s$3,$vyQ$Vt V !$!$"x 9$&%$9@J$5$ 5r$#|2 r2%0pd3 r%9NS. dt# "l / d047$1,94$1,v9{FpWY !t2!'&!1&!%{!34{!/{!(!#%:-B%:+ dr\ tC@%:7 0W$ %:r5=6m$?t._>6>;5 ?{,^$^>;1?43;*rX.*:VC;,m $L$dM3$C;,& $L+$zLB$3M_$$3$Vkz$k%4$ 2'm$ 2'&$-I$$:W $%k $%B$]kB$]ke*$+W$F$kL$@94$=$S$R$[`C$9ZC;$/B$ 03$ 03%$$A& y$$A"%k$$A! $$e $$e^$!3$U!z$';$>"%$,s z$,s 3$Fp^FFF3Ax`Fp"Ax$1 $$1I $ Tn$ O*4y$!Vt {A8; V/XV"+0t k0t+# k#  4;|43p '$!3$v)^*W%:t %:VVEt Et   V5-$ V1$!3 49$0W%@$01I$rSu$/X$ Ot,m]+t$Oe {$ &U$$% $&2B &3_$7$7 'spd3 (dtG<<0 4O ]R A PROCESSOR FOR A HIGH-PERFORMANCE PERSONAL COMPUTER146. ImplementationIn this section we describe, at the block diagram level, the actual implementation of the Doradoprocessor. There is only space to cover the most interesting points and to illustrate the key ideasfrom 5.6.1 ClocksThe Dorado has a fully synchronous clock system, with a clock tick every 30 nanoseconds. A cycleconsists of two successive clock ticks; it begins on an even tick, which is followed by an odd tick,and completes coincident with the beginning of a new cycle on the next even tick. Even ticks maybe labeled with names like t-2, t0, t2, t4 to denote events within a microinstruction execution or apipeline, relative to some convenient origin. Odd ticks are similarly labeled t-1, t1, t3.6.2 The control sectionThe processor can be divided into two distinct sections, called control and data. The control sectionfetches and broadcasts the microinstructions to the data section (and the remainder of the Dorado),handles task switching, maintains a subroutine link, and regulates the clock system. It also has aninterface to a console and monitoring microcomputer which is used for initialization and debuggingof the Dorado. Figure 5 is a block diagram of the control section.6.2.1 Task pipelineThe task pipeline consists of an assortment of registers and a priority encoder. All the registers areloaded on even clocks. Wakeup requests are latched at t0 in WAKEUP, one bit per task; READY hascorresponding bits for preempted and explicitly readied tasks. The requests in WAKEUP and READYcompete. A task can be explicitly made ready by a microcode function. The priority encoderproduces the number of the highest priority task, which is loaded into BESTNEXTTASK and also usedto read the TPC of this task into BESTNEXTPC; these registers are the interface between the twostages in this pipeline. The NEXT bus normally gets the larger of BESTNEXTTASK and THISTASK.THISTASK is loaded from NEXT, and LASTTASK is loaded from THISTASK, as the pipeline progresses.This method of priority scheduling means that once a task is initiated, it must explicitly relinquishthe processor before a lower priority task can run. A bit in the microword, Block, is used toindicate that NEXT should get BESTNEXTTASK unconditionally (unless the instruction is held).Note that it takes a minimum of two cycles from the time a wakeup changes to the time thischange can affect the running task (one for the priority encoding, one to fetch the microinstruction).This implies that a task must execute at least two microinstructions after its wakeup is removedbefore it blocks; otherwise it will continue to run, since the effects of its wakeup will not have beencleared from the pipe. The device cannot remove the wakeup until it knows that the task will run(by seeing its number on NEXT). Hence the earliest the wakeup can be removed is t0 of the firstinstruction (NEXT has the task number in the previous cycle, and the wakeup is latched at t0); thusthe grain of processor allocation is two cycles for a task waking up after a Block.Some trouble was taken to keep the grain small, for the following reason. Since the memory isheavily pipelined and contains a cache which does not interact with high bandwidth I/O, the I/Omicrocode often needs to execute only two instructions, in which a memory reference is started anda count is decremented. The processor can then be returned to another task. The maximum rate atwhich storage references can be made is one every eight cycles (this is the cycle time of the mainstorage RAMs). A two cycle grain thus allows the full memory bandwidth of 530 megabits/secondto be delivered to I/O devices using only 25% of the processor.[ zwXzwzwzwzwz wzwzwT{QwP P SNJ|XGYw;|w|Ew/|w|wDQ7'B~B@Bw~B@Bw~B@Bw~B@Bw:@F~@R@w~@R@w~@R@w<|X9w 3|w|w811+6V5)V3A/|X ,{w`*.~*j*wzwzw) Bzwz'w H&)z w $} zwz w3"zw z wzw!uzwzwzwzwJV I~w Bzw z w2FC@.3--zw4~w  zwA~w |wD~w |$6.zwzwzwztw=%;l?zwOdzwzw) %H`SEC. 6IMPLEMENTATION15A simpler design would require the microcode to explicitly notify its device when the wakeupshould be removed; it would then be unnecessary to broadcast NEXT to the devices. Since thisnotification could not be done earlier than the first instruction, however, the grain would be threecycles rather than two, and 37.5% of the processor would be needed to provide the full memorybandwidth. Other simplifications in the implementation would result from making the pipelinelonger; in particular, squeezing the priority encoding and reading of TPC into one cycle is quitedifficult. Again, however, this would increase the grain.6.2.2 Fetching microinstructionsRefer to the right hand side of Figure 5. At t0 of every instruction, the microinstruction registerMIR is loaded from the outputs of IM, the microinstruction memory, and the THISPC register isloaded with IMADDRESS. The NEXTPC is quickly calculated based on the NextControl field in MIR,which encodes both the instruction type and some bits of NEXTPC; see Figure 7 for details. Thiscalculation produces THISTASKNEXTPC, so called because if a task switch occurs it is not used as thenext IMADDRESS. Instead, the BESTNEXTPC computed in the task pipeline is used as IMADDRESS.<==0P$<0P$:X0P$80P$50P$#t/%;/'s/)/+/./0W/2/4;/6t/8/:/=/?X/?X*=*:*8*6t*4;*2*0W*.*+*)*'s*%;*#*5+P$8+P$:X+P$<+P$>+P$A+P$1t+P$/;+P$-+P$*+P$(+P$$+P$!+,$]!+,A$A+P$9!-e$!(e$A&P$9!&,A$!&,$]$&P$(&P$*&P$-&P$/;&P$1t&P$A&P$>&P$<&P$:X&P$5&P$3&P$#%%;%'s%)%+%.%0W%2%4;%6t%8%:%=%?X%?X = : 8 6t 4; 2 0W . + ) 's %; # 5!$$<$:X$8$5$3$#%;'s)+.0W24;6t8:=?X?X,=,:,8,6t,4;,2,0W,.,+,),'s,%;,#,3l$5l$8l$:Xl$>l$Al$1tl$/;l$-l$*l$(l$$l$!H$]!HA$Al$9!$'s+P$9's&P$9'sl$9.v &W0P$30P$93+P$94t,6,8,;-,=f,?,8&P$9-v'&W!$3!$98!9$>!$98!$9:X!$9?"8"<l$9?Xt=:86t4;20W.+)'s%;#5$8$:X$<$>$A$1t$/;$-$*$($&W$$$!$]!A$A$9! $3$93$!p ,u  t -r6I)v181",,+W,",'",:')"3":"Bu# B" +v<u(vr6r !4W4;4W:u1 :, Wp sr6I k$ :H $k$ :k$ :3 $6I 3G$HG$Gk$ :Bt1 u!tS  !J$pdG7xA PROCESSOR FOR A HIGH-PERFORMANCE PERSONAL COMPUTER16TPC is written with the previous value of THISTASKNEXTPC every cycle (at t3), and read for the taskin BESTNEXTTASK every cycle as well. Thus, TPC is constantly recording the program counter valuefor the current task, and also constantly preparing the value for the next task in case there is a taskswitch.6.2.3 Miscellaneous featuresThere is a task specific subroutine linkage register, LINK, shown in Figure 5, which is loaded withthe value in THISPC+1 on every microcode call or return. Thus each task can have its ownmicrocoded coroutines. LINK can also be loaded from a data bus, so that control can be sent to anarbitrary computed address; this allows a microprogram to implement a stack of subroutine links,for example. In addition to conditional branches, which select one of two NEXTPC values, there arealso eight-way and 256-way dispatches, which use a value on the B bus to select one of eight, or oneof 256 NEXTPC values. Since the Dorado's microstore is writeable, there are data paths for reading and writing it. Relatedpaths allow reading and writing TPC. These paths (through the register TPIMOUT) are folded intoalready existing data paths in the control section and are somewhat tortuous, but they are usedinfrequently and hence have been optimized for space. In addition, another computer (either aseparate microcomputer or an Alto) serves as the console processor for the Dorado; it is interfacedvia the CPREG and a very small number of control signals.6.3 The data sectionFigure 6 is a block diagram of the data section, which is organized around an arithmetic/logic unit(ALU). It implements most of the registers accessible to the programmer and the microcodefunctions for selecting operands, doing operations in the ALU and shifter, and storing results. It alsocalculates branch conditions, decodes MIR fields and broadcasts decoded signals to the rest of theDorado, supplies and accepts memory addresses and data, and supplies I/O data and addresses.6.3.1 The microinstruction registerMIR (which actually belongs to the control section) is 34 bits wide and is partitioned into thefollowing fields:RAddress4Addresses the register bank RM.ALUOp4Selects the ALU operation or controls the shifter.BSelect3Selects the source for the B bus, including constants.LoadControl3Controls loading of results into RM and T.ASelect3Selects the source for the A bus, and starts memory references.Block1Blocks an I/O task, selects a stack operation for task 0.FF 8Catchall for specifying functions.NextControl8Specifies how to compute NEXTPC.6.3.2 BussesThe major busses are A, B (ALU sources), RESULT, EXTERNALB, MEMADDRESS, IOADDRESS, IODATA,IFUDATA, and MEMDATA .The ALU accepts two inputs (A and B) and produces one output (RESULT). The input busses have avariety of sources, as shown in the block diagram. RESULT usually gets the ALU output, but it isalso sourced from many other places, including a one bit shift in either direction of the ALU output.A copy of A is used for MEMADDRESS; two copies of B are used for EXTERNALB and IODATA.MEMADDRESS provides a sixteen bit displacement, which is added to a 28 bit base register in thememory system to form a virtual addresses. EXTERNALB is a copy of B which goes to the control,memory, and IFU sections, and IODATA is another copy which goes to the I/O system; the sources of^zwXzwzwzwzwz wzwzwX(zw'z w~WX(wV:z wzw2TRS2O3|XLw1zw$JzwFI zwFG|@E?zwDt| wzw#Bzw?5+>Azw%zw<#5;9 >9(381zw,42|X1wD/zwF -,zw+,{ zw&*>zwzw&|X#zwX"I~w]zwmz~w] zw#~w]zwe~ w]!zwzw~w]zw#]~w] zwzw,~w]"U~ w]zwV|X+w zwzwzw zwzwz wzwzw zwzw |zwzwzwzwzwzwtDzwzw z wzw zwzwlz wN&zw zwdzwzw#zwzw L HcuSEC. 6IMPLEMENTATION17B can thus be sent to the entire processor. Both are bidirectional and can serve as a source for B aswell. IOADDRESS is driven from a task specific register; it specifies the particular device and registerwhich should source or receive IODATA.IFUDATA and MEMDATA allow the processor to receive data from the IFU and memory in parallelwith other data transfers. MEMDATA has the value of the memory word most recently fetched bythe current task; if the fetch is not complete, the processor is held when it tries to use MEMDATA.IFUDATA has an operand of the current macroinstruction; as each operand is used, the IFU presentsthe next one on IFUDATA.6.3.3 RegistersHere is a list and brief description of registers seen by the microprogrammer. All are one word (16bits) wide.RM:a bank of 256 general purpose registers; a register can be read onto A, B, or theshifter, and loaded from RESULT under the control of LoadControl. Normally, thesame register is both read and loaded in a given microinstruction, but loading of adifferent register can be specified by FF.STACK:a memory addressed by the STACKPTR register. A word can be read or written,and STACKPTR adjusted up or down, in one microinstruction. If STACK is used in amicroinstruction, it replaces any use of RM, and the RAddress field in the microwordtells how much to increment or decrement STACKPTR. The 256 word memory isdivided into four 64 word stacks, with independent underflow and overflowchecking.T:a task specific register used for working storage; like RM, it can be read onto A, B,or the shifter, and loaded from RESULT under the control of LoadControl..COUNT:a counter; it can be decremented and tested for zero in one microinstruction, usingonly the NextControl or FF field. It is loaded from B or with small constants fromFF.SHIFTCTL:a register which controls the direction and amount of shifting and the width of leftand right masks; it is loaded from B or with values useful for field extraction fromFF.Q:a hardware aid for multiply and divide instructions; it can be read onto A or B, andloaded from B, and is automatically shifted in useful ways during multiply anddivide step microinstructions.The next group of registers vary in width. They are used as control or address registers, changeddynamically but infrequently by microcode.RBASE:RM addressing requires eight bits. Four come from the RAddress field in themicroword, and the other four are supplied from RBASE. It is loaded from B or FF,and can be read onto RESULT.STACKPTR:an eight bit register used as a stack pointer. Two bits of STACKPTR select a stack,and the least significant six bits a word in the stack. The latter bits areincremented or decremented under control of the RAddress field whenever a stackoperation is specified.MEMBASE:a five bit register which selects one of 32 base registers in the memory to be usedfor virtual address calculation. It is loaded from FF field or from B, and can beloaded from the IFU at the start of a macroinstruction.ALUFM:a 16 word memory which maps the four-bit ALUOp field into the six bits requiredto control the ALU.IOADDRESS:a task specific register which drives the IOADDRESS bus, and is loaded by I/Omicrocode to specify a device address for subsequent Input and Output operations.It may be loaded from B or FF.\zG+I ;wVzwT zwUzwYSzwPpzwzw$ zwNzw/ Mh,,zwKzwMzwJ` zwFa|X C6wLA?zw Dzwzw >zw~ w <&) ;~w9zw zw 7zw 'zw 5zw ~w 4x$zw 2 5 1p/_zw zwzwzw -zw~ w+zw *( *F~ w~w zw (~w&zw E %-zw( #~w!zw Hzwzw zw( e(7 zw zw5~w L zwzw~w zwzw zw 33  ~w + zw /# 1~wzw  zw$zw z~w! } zwlzw )zwzwz w,~w~w dzw~w  8HaA PROCESSOR FOR A HIGH-PERFORMANCE PERSONAL COMPUTER186.3.4 The shifterThe Dorado has a 32 bit barrel shifter for handling bit-aligned data. It takes 32 bits of input fromRM and T, performs a left cycle of any number of bit positions, and places the result on A. TheALU output may be masked during a shift instruction, either with zeroes or with data fromMEMDATA.The shifter is controlled by the SHIFTCTL register. To perform a shift operation, SHIFTCTL is loaded(in one of a variety of ways) with control information, and then one of a group of "shift and mask"microoperations is executed.6.4 Physical organizationOnce the goal of a physically small but powerful machine was established, engineering design andmaterial lead times forced us to develop the Dorado package before the implementation was morethan partially completed, and the implementation then had to fit the package. The data section ispartitioned onto two boards, eight bits on each; the boards are about 70% identical. The controlsection divides naturally into one board consisting of all the IM chips (high speed 1K x 1 bit ECLRAMs) and their associated address drivers, and a second board with the task switch pipeline,NEXTPC logic, and LINK register.The sidepanel pins are distributed in clusters around the board edges to form the major busses.The remaining edge pins are used for point to point connections between two specific boards. TheI/O busses go uniformly to all the I/O slots, but all the other boards occupy fixed slots specificallywired for their needs. Half the pins available on the sideplanes are grounded, but wire lengths arenot controlled except in the clock distribution system, and no twisted pair is used in the machineexcept for distribution of one copy of the master clock to each board.We were very concerned throughout the design of the Dorado to balance the pipelines so that noone pipe stage is significantly longer than the others. Furthermore, we worked hard to make thelongest stage (which limits the speed of this fully synchronous machine) as short as possible. Thelongest stage in the processor, as one might have predicted, is the IMADDRESS calculation andmicroinstruction fetch in the control slice. There is about a 50 nanosecond limit for reliableoperation in a stitchwelded machine, and 60 ns in a multiwired machine. There are pipe stages ofabout the same length in the memory and IFU.We also worked hard to get the most out of the available real estate, by hand tailoring theintegrated circuit layout and component usage, and by incrementally adding function until nearlythe entire board was in use. We also found that performance could be significantly improved bycareful layout of critical paths for minimum loading and wiring delay. Although this was a verylabor intensive operation, we believe it pays off.7. PerformanceFour emulators have been implemented for the Dorado, interpreting the BCPL, Lisp, Mesa andSmalltalk instruction sets. A typical microinstruction sequence for a load or store instruction takesonly one or two microinstructions in Mesa (or BCPL), and five in Lisp. The Mesa opcode can senda 16 bit word to or from memory in one microinstruction; Lisp deals with 32 bit items and keepsits stack in memory, so two loads and two stores are done in a basic data transfer operation. Morecomplex operations (such as read/write field or array element) take five to ten microinstructions inMesa and ten to twenty in Lisp. Note that Lisp does runtime checking of parameters, while inMesa most checking is done at compile time. Function calls take about 50 microinstructions forMesa and 200 for Lisp.The Dorado supports raster scan displays which are refreshed from a full bitmap in main memory;this bitmap has one bit for each picture element (dot) on the screen, for a total of .51 megabits]zwXzwzwzwzwz wzwzwW|TowFRzwzw@zwQgzw1%OzwL zw*zw K4LI E|XBw4(A3#?~@= : LD7$E|wd5) AHbSEC. 7PERFORMANCE19(more for gray-scale or color pictures). A special operation called BitBlt (bit boundary blocktransfer) makes it easier to create and update bitmaps; for more information about BitBlt consult [9],where it is called RasterOp. BitBlt makes extensive use of the shifting/masking capabilities of theprocessor, and attempts to prefetch data so that it will always be in the cache when needed. TheDorado's BitBlt can move display objects around in memory at 34 megabits/sec for simple cases likeerasing or scrolling a screen. More complex operations, where the result is a function of the sourceobject, the destination object and a filter, run at 24 megabits/sec.I/O devices with transfer rates up to 10 megabits/sec are handled by the processor via the IODATAand IOADDRESS busses. The microcode for the disk takes three cycles to transfer two words in thisway; thus the 10 megabit/sec disk consumes 5% of the processor. Higher bandwidth devices usethe fast I/O system, which does not interact with the cache. The fast I/O microcode for the displaytakes only two instructions to transfer a 16 word block of data from memory to the device. Thiscan consume the available memory bandwidth for I/O (530 megabits/sec) using only one quarter ofthe available microcycles (that is, two I/O instructions every eight cycles).Recall that the NEXTPC scheme ( 5.5 and 6.2.2) imposes a rather complicated structure on themicrostore, because of the pages, the odd/even branch addresses, and the special subroutine calllocations We were concerned about the amount of microstore which might be wasted by automaticplacement of instructions under all these constraints. In fact, however, the automatic placer can use99.9% of the available memory when called upon to place an essentially full microstore.AcknowledgementsThe early design of the Dorado processor was done by Chuck Thacker and Don Charnley. Thedata section was redesigned and debugged by Roger Bates and Ed Fiala. Peter Deutsch wrote themicrocode assembler and instruction placer, and Ed Fiala wrote the Dorado assembler macros, themicroprogram debugger, and the hardware manual. Willie-Sue Haugeland, Nori Suzuki, BruceHorn, Peter Deutsch, Ed Taft and Gene McDaniel are responsible for production and diagnosticmicrocode.References1.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.Deutsch, L.P. Experience with a microprogrammed Interlisp system. Proc. 11th Ann. Microprogramming Workshop, PacificGrove, Nov. 1979.3.Geschke, C.M. et. al. Early experience with Mesa. Comm ACM 20, 8, Aug 1977, 540-5524.Ingalls, D.H. The Smalltalk-76 programming system: Design and implementation. 5th ACM Symp. Principles ofProgramming Languages, Tucson, Jan 1978, 9-16.5. Lampson, B.W. et. al. An instruction fetch unit for a high-performance personal computer. Technical Report CSL-81-1,Xerox Palo Alto Research Center, Jan. 1981. Submitted for publication.6.Mitchell, J.G. et. al. Mesa Language Manual, Technical Report CSL-79-3, Xerox Palo Alto Research Center, April 1979.7. Teitelman, W. Interlisp Reference Manual, Xerox Palo Alto Research Center, Oct. 1978.8. 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.9. Newman, W.M. and Sproull, R.F. Principles of Interactive Computer Graphics, 2nd ed. McGraw-Hill, 1979.=KzG- ;w61~w5p.~w 3 ~w~w,2h !60~w=/`^-=*zwzwSz)-wzw0%',-&%zwzw)zwzw$,/#,zwzw!%zwzw"n zw, PfT-0^R{`wPZ X L $) PE { dyw{zG  (HBA z)KpGqOrq{( Bsqpq&ftu{qDp)q{%(#tu{q pqpsqtq!tu{qOpsp{ qtuX{qGpqYrq{Gtu{qpqpqrq3ituX{q Gpq-tuX{qGpqp*q{Drq/{Ftq{p+q 6 HA PROCESSOR FOR A HIGH-PERFORMANCE PERSONAL COMPUTER20dquXququququq uququ8 eHZ$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|The Memory System of a High-Performance Personal Computerby Douglas W. Clark1, Butler W. Lampson, and Kenneth A. PierJanuary 1981ABSTRACTThe memory system of the Dorado, a compact high-performance personal computer, hasvery high I/O bandwidth, a large paged virtual memory, a cache, and heavily pipelinedcontrol; this paper discusses all of these in detail. Relatively low-speed I/O devices transfersingle words to or from the cache; fast devices, such as a color video display, transferdirectly to or from main storage while the processor uses the cache. Virtual addresses areused in the cache and for all I/O transfers. The memory is controlled by a seven-stagepipeline, which can deliver a peak main-storage bandwidth of 530 million bits per second toservice fast I/O devices and cache misses. Interesting problems of synchronization andscheduling in this pipeline are discussed. The paper concludes with some performancemeasurements that show, among other things, that the cache hit rate is over 99 percent.A revised version of this paper will appear in IEEE Transactions on Computers.CR CATEGORIES6.34, 6.21.KEY WORDS AND PHRASESbandwidth, cache, latency, memory, pipeline, scheduling, storage, synchronization, virtualmemory.1. Present address: Digital Equipment Corporation, Tewksbury, Mass. 01876.c Copyright 1981 by Xerox Corporation.XEROXPALO ALTO RESEARCH CENTER3333 Coyote Hill Road / Palo Alto / California 94304MmpJ"CqXD1rCq(=* 4s1tH0utut =..utut- 2+C*utut6( H&utut ;%w !*# K /vwtS;\,} z 9 }z38TH{z6C5L\3M2D10 X/<T,W*,.) [' +&&;&$}8{z{z" {z{zE!u: }z.mDn}XCz#{z{z {zO;){zB{z{z3 2& Q /2 &7 | J =t C Nl?Yd+ SHdSEC. 1INTRODUCTION53<==1;\,{z{z%9={z{z8TM63,5L=3 ){z{z$2D7#0{z{zL/<M,R*}z7{z{z$) Z'G&b$}?"/} z!uCR,1BW J :{z#?2.2*4*`#{z/" 0 #}XzG t O6l@-/dT SHdE$$%$ $$$ $$ $rW$1sV$9%$1sy$1s$=$= y$KA$= V$Vr VW 3sA &WW$=;tk r:   N   s9$ ^$9 :]$ :$] :$] :$ ^$9 sr$ s$ ^$9 :@$ :$] GV G G 2 G:k s$ ^$9 :$ :$]93GV $$$ k3p:3 :k9$tdp  & & & 's ', 's: ?W DvK&{f THE MEMORY SYSTEM OF A HIGH-PERFORMANCE PERSONAL COMPUTER54Memory references specify a 16 or 28 bit displacement, and one of 32 base registers of 28 bits; thevirtual address is the sum of the displacement and the base. Virtual address translation, or mapping,is implemented by table lookup in a dedicated memory. Main storage is the permanent home ofdata stored by the memory system. The storage is necessarily slow (i.e., it has long latency, whichmeans that it takes a long time to respond to a request), because of its implementation in cheap butslow dynamic MOS RAMs (random access memories). To make up for being slow, storage is big,and it also has high bandwidth, which is more important than latency for sequential references. Inaddition, there is a cache which services non-sequential references with high speed (low latency),but is inferior to main storage in its other parameters. The relative values of these parameters areshown in Table 1.CacheStorageLatency-1151Bandwidth12Capacity1250Table 1: Parameters of the cache relative to storageWith one exception (the IFU), all memory references are initiated by the processor, which thus actsas a multiplexor controlling access to the memory (see 1.2 and [10]), and is the sole source ofaddresses. Once started, however, a reference proceeds independently of the processor. Each onecarries with it the number of its originating task, which serves to identify the source or sink of anydata transfer associated with the reference. The actual transfer may take place much later, andeach source or sink must be continually ready to deliver or accept data on demand. It is possiblefor a task to have several references outstanding, but order is preserved within each type ofreference, so that the task number plus some careful hardware bookkeeping is sufficient to matchup data with references. Table 2 lists the types of memory references executable by microcode. Figure 2, a picture of thememory system's main data paths, should clarify the sources and destinations of data transferred bythese references (parts of Figure 2 will be explained in more detail later). All references, includingfast I/O references, specify virtual, not real addresses. Although a microinstruction actually specifiesa displacement and a base register which together form the virtual address, for convenience we willsuppress this fact and write, for example, Fetch(a) to mean a fetch from virtual address a.A Fetch from the cache delivers data to a register called FetchReg, from which it can be retrieved atany later time; since FetchReg is task-specific, separate tasks can make their cache referencesindependently. An I/ORead reference delivers a 16-word block of data from storage to theFastOutBus (by way of the error corrector, as shown in Figure 2), tagged with the identity of therequesting task; the associated output device is expected to monitor this bus and grab the datawhen it appears. Similarly, the processor can Store one word of data into the cache, or do anI/OWrite reference which demands a block of data from an input device and sends it to storage (byway of the check-bit generator). There is also a Prefetch reference, which brings a block into thecache. Fetch, Store and Prefetch are called cache references. There are special references to flushdata from the cache and to allow a map entries to be read and written; these will be discussed later.The instruction fetch unit is the only device that can make a reference independently of theprocessor. It uses a single base register, and is treated almost exactly like a processor cache fetch,except that the IFU has its own set of registers for receiving memory data (see [9] for details). Ingeneral we ignore IFU references from now on, since they add little complexity to the memorysystem.YzX{z{z{z{z{z{z{ z{z{zS2#} z } zQV}zP*+ } zN9'M"R K{z{z7JXH }z*G5-E BBcB Bc B(Bc(#B Bc -zBoBco@ }?F? F?(F#? F-z?oF ~z~z gm$~z;~z~z g m4m:D~7z~z g m1~5z~z g m~z1~3<z~z gm7m1)1041 04 1(04(#1 04 -z1o04o - X8)}z2}z (Z }z}z9&{z{z!%R }z}z8# 9"J({z{z  {z{z}X$z= }z0< 6{z{z 1"4#{z{z2}z4 XS D |%2 It[ 4*lY )*dY H]) THE MEMORY SYSTEM OF A HIGH-PERFORMANCE PERSONAL COMPUTER56<==W>W , : HB$ B$'p, x' /$dp, xEpP3xr$+$+$ +$1+$r$:r?@=O +$xd $ $rr9 $ $ Hp 0 H[(5VG- )e/%:.$e1\$3-U$+$e-2$$e-2$N$;$N$;$3<$+$@$&W=$e#$N$e#$3F$+$eM$)&$ $3$+$$$$N%+2U$+x*W,t2U$,t($G+($G+ -p*#+xH+F$G,tF$G-p\,t $r+x+ $r(qVG.$- ).;$$ G$)  9$$)69$ 9G$ 8$U 4$8 $T$$e1 G$ 8H$8 $.1 $81$3 G+$. $9;$4 Hk,$.T$.$9 M$SedGQGQG+rT!QG6tQG!SedG$T Hp?  H j F$)$)e$9)e69$ F$$d)r$Npid GPn89^UVSEC. 1INTRODUCTION57All busses are 16 bits wide; blocks of data are transferred to and from storage at the rate of 16 bitsevery half cycle (30 ns). This means that 256 bits can be transferred in 8 cycles or 480 ns., which issomewhat more than the 375 ns cycle time of the RAM chips that implement main storage. Thus ablock size of 256 bits provides a fairly good match between bus and chip bandwidths; it is also acomfortable unit to store in the cache. The narrow busses increase the latency of a storage transfersomewhat, but they have little effect on the bandwidth. A few hundred nanoseconds of latency isof little importance either for sequential I/O transfers or for delivery of data to a properlyfunctioning cache.Various measures are taken to maximize the performance of the cache. Data stored there is notwritten back to main storage until the cache space is needed for some other purpose (the write-backrather than the more common write-through discipline [1, 14]); this make it possible to use memorylocations much like registers in an interpreted instruction set, without incurring the penalty of mainstorage accesses. Virtual rather than real addresses are stored in the cache, so that the speed ofmemory mapping does not affect the speed of cache references. (Translation buffers [15, 20] areanother way to accomplish this.) This would create problems if there were multiple address spaces.Although these problems can be solved, in a single-user environment with a single address spacethey do not even need to be considered.Another important technique for speeding up data manipulation in general, and cache references inparticular, is called bypassing. Bypassing is one of the speed-up techniques used in the CommonData Bus of the IBM 360/91 [19]. Sequences of instructions having the form(1) register _ computation1(2) computation2 involving the registerare very common. Usually the execution of the first instruction takes more than one cycle and ispipelined. As a result, however, the register is not loaded at the end of the first cycle, andtherefore is not ready at the beginning of the second instruction. The idea of bypassing is to avoidwaiting for the register to be loaded, by routing the results of the first computation directly to theinputs of the second one. The effective latency of the cache is thus reduced from two cycles to onein many cases (see 2.3).The implementation of the Dorado memory reflects a balance among competing demands:for simplicity, so that it can be made to work initially, and maintained when componentsfail; for speed, so that the performance will be well-matched to the rest of the machine;for space, since cost and packaging considerations limit the number of components andedgepins that can be used.None of these demands is absolute, but all have thresholds that are costly to cross. In the Doradowe set a somewhat arbitrary speed requirement for the whole machine, and generally tried to savespace by adding complexity, pushing ever closer to the simplicity threshold. Although many of thecomplications in the memory system are unavoidable consequences of the speed requirements, someof them could have been eliminated by adding hardware.2. The cacheThe memory system is organized into two kinds of building blocks: pipeline stages, which providethe control (their names are in SMALL CAPITALS), and resources, which provide the data paths andmemories. Figure 3 shows the various stages and their arrangement into two pipelines. One,consisting of the ADDRESS and HITDATA stages, handles cache references and is the subject of thissection; the other, containing MAP, WRITETR, STORAGE, READTR1 and READTR2, takes care ofstorage references and is dealt with in 3 and 4. References start out either in PROC, the processor,or in the IFU.\){G, ;zUOTNPR({z%QFR O QN>;L){z{z'K6 H CF>} Ez} z$CUA<@wM >|zB=oB;#8W7< }zA5 {z83`1'/W. '.,|>*H)t P'$S"m6 S92T 3+)|z %-z4 |X |zH}z{ z}zt', {z{z<l{z{z{z{z{z4{zd{z Ha THE MEMORY SYSTEM OF A HIGH-PERFORMANCE PERSONAL COMPUTER58<==3{z"3Q V  S |}z }z }z-;#t  }zOlC, }zd& Hd9\$Ux9!$UsUs9#$:U:9$ $    r H H$r  $$y$*: $+V(*:$+V H( H2 H5 H4$254 $> $?<>$? H< Hr  M$rd d$tN 9x(x3x=x#$-$8r$V $9$c$U@$9$$yx&V0:V  $ Ur% r%VG r#Gd+VNBG%GGd$*GV$9$V$V 8$ t?  [ U$ !r$ x t" ! y$$y# p%r$!t x  G9B&SEC. 2THE CACHE59<==$$ $ %@$"s$ G G  +G  G +&(sG?$Gr&$qG&$qG?G&:Gr:G:G#$"$&&@O$&%js$2It)N7)N,)N',)N<%$H:>;'8U$;$U$#?# V? V)$*$'FGrBeFr(t6 ,, $U0 $U5W $U-H1:W ?> b9F$r:F$r=$=F$r^% r=;)Nx#eGDdrG69G+ )G3+$$t p""&Ck$-A$&A$&A$'=$',tBO",x*&4G$94G$9"3+$r4)#pw0t b 5 b*=$,9x$^UiHF THE MEMORY SYSTEM OF A HIGH-PERFORMANCE PERSONAL COMPUTER60miss: the address is not present in the cache. During normal operation, it is not possible for morethan one column to match. The entire matching process can be seen in Figure 4, between 60 and90 ns after the start of the reference. The cache address latched at 90 contains the row, word andcolumn; these 14 bits address a single word in CacheD. Of course, only the top 16 key bits of theaddress need be matched, since the row bits are used to select the row, and all the words of a blockare present or absent together.Four flag bits are stored with each cache entry to keep track of its status. We defer discussion ofthese flags until 4.2.2 Cache dataThe CacheD resource stores the data for the blocks whose addresses appear in CacheA; closelyassociated with it are the StoreReg and task-specific FetchReg registers which allow the processor todeliver and retrieve its data independently of the memory system's detailed timing. CacheD is quitesimple, and would consist of nothing but a 16K by 16 bit memory were it not for the bandwidth ofthe storage. To keep up with storage the cache must be able to accept a word every half cycle (30ns.). Since its memory chips cannot cycle this fast, CacheD is organized in two banks which run ahalf-cycle out of phase when transferring data to or from the storage. On a hit, however, bothbanks are cycled together and CacheD behaves like an 8K by 32 bit memory. A multiplexor selectsthe proper half to deliver into FetchReg. All this is shown in Figure 4.Figure 4 does not, however, show how FetchReg is made task-specific. In fact, there is a 16-wordmemory FetchRegRAM in addition to the register shown. The register holds the data value for thecurrently executing task. When a Fetch reference completes, the word from CacheD is alwaysloaded into the RAM entry for the task that made the reference; it is also loaded into FetchReg ifthat task is the one currently running. Whenever the processor switches tasks, the FetchRegRAMentry for the new task is read out and loaded into FetchReg. Matters are further complicated bythe bypassing scheme described in the next subsection.StoreReg is not task-specific. The reason for this choice and the problem it causes are explained in 5.1.2.3 Cache pipeliningFrom the beginning of a cache reference, it takes two and a half cycles before the data is ready inFetchReg, even if it hits and there are no delays. However, because of the latches in the pipeline(some of which are omitted from Figure 4), a new reference can be started every cycle, and if thereare no misses the pipeline will never clog up, but will continue to deliver a word every 60 ns. Thisworks because nothing in later stages of the pipeline affects anything that happens in an earlierstage.The exception to this principle is delivery of data to the processor itself. When the processor usesdata that has been fetched, it depends on the later stages of the pipeline. In general thisdependency is unavoidable, but in the case of the cache the bypassing technique described in 1.4is used to reduce the latency. A cache reference logically delivers its data to the FetchReg registerat the end of the cycle following the reference cycle (actually halfway through the second cycle, at150 in Figure 4). Often the data is then sent to a register in the processor, with a (microcode)sequence such as(1)Fetch(address)(2)register _ FetchReg(3)computation involving register. The register is not actually loaded until cycle (3); hence the data, which is ready in the middle ofcycle (3), arrives in time, and instruction (2) does not have to wait. The data is supplied to thecomputation in cycle (3) by bypassing. The effective latency of the cache is thus only one cycle inthis situation._RzX{z{z{z{z{z{z{ z{z{zXLWwKU%<To MRBQgN<HLH}X Ez9D 4'BWAD?~9&=L{.zB-+3*2+(|$}}X!Rz\ OJU@"B8$OA -+_QO { #~z !AlD 9d  HdHSEC. 2THE CACHE61Unfortunately this sleight-of-hand does not always work. The sequence(1)Fetch(address)(2)computation involving FetchReg actually needs the data during cycle (2), which will therefore have to wait for one cycle (see 5.1).Data retrieved in cycle (1) would be the old value of FetchReg; this allows a sequence of fetches(1)Fetch(address1)(2)register1 _ FetchReg, Fetch(address2)(3)register2 _ FetchReg, Fetch(address3)(4)register3 _ FetchReg, Fetch(address4). . .to proceed at full speed.3. The storage pipelineCache misses and fast I/O references use the storage portion of the pipeline, shown in Figure 3. Inthis section we first describe the operation of the individual pipeline stages, then explain how fastI/O references use them, and finally discuss how memory faults are handled. Using I/O referencesto expose the workings of the pipeline allows us to postpone until 4 a close examination of themore complicated references involving both cache and storage.3.1 Pipeline stagesEach of the pipeline stages is implemented by a simple finite-state automaton that can change stateon every microinstruction cycle. Resources used by a stage are controlled by signals that itsautomaton produces. Each stage owns some resources, and some stages share resources with others.Control is passed from one stage to the next when the first produces a start signal for the second;this signal forces the second automaton into its initial state. Necessary information about thereference type is also passed along when one stage starts another.3.1.1 The ADDRESS stageAs we saw in 2, the ADDRESS stage computes a reference's virtual address and looks it up inCacheA. If it hits, and is not I/ORead or I/OWrite, control is passed to HITDATA. Otherwise, controlis passed to MAP, starting a storage cycle. In the simplest case a reference spends just onemicroinstruction cycle in ADDRESS, but it can be delayed for various reasons discussed in 5.3.1.2 The MAP stageThe MAP stage translates a virtual address into a real address by looking it up in a hardware tablecalled the MapRAM, and then starts the STORAGE stage. Figure 5 illustrates the straightforwardconversion of a virtual page number into a real page number. The low-order bits are not mapped;they point to a single word on the page.Three flag bits are stored in MapRAM for each virtual page:ref, set automatically by any reference to the page;dirty, set automatically by any write into the page;writeProtect, set by memory-management software (using the MapWrite reference). A virtual page not in use is marked as vacant by setting both writeProtect and dirty, an otherwisenonsensical combination. A reference is aborted by the hardware if it touches a vacant page,attempts to write a write-protected page, or causes a parity error in the MapRAM. All three kindsof map fault are passed down the pipeline to READTR2 for reporting; see 3.1.5.^{G/^;zX+ 9U~zTOQVPs]N~z L~z K~z I~z H E@|X=z{z{z8<1\:{z{z; |z{z{z 9)1.793}X0{zH.9#-s}z!}z+$}z*k<(9$}X}!z{z# 9{z{~z{z{~z{}z {z,!1 {z=2}X}z{zH}{z{z *,{$P!{z ~z1 ~z/H~ z/~z "}z~ z~z l |zBE{zd}z!{z l Hcx~ THE MEMORY SYSTEM OF A HIGH-PERFORMANCE PERSONAL COMPUTER62<==l$9:Xl$9<l$98l$9C;l$9Al$9Etl$95 3$91t 3$93 3$9( 3$9- 3$9* 3$9/; 3$9&W $]&W $8 3$9&W"H$%$("$9"$"$]"$9:"$9s"$9"$9$"$9!"$9&W"$9:%$9%$9%$9 %$9V%$9%$9%$9 %$] %$s%$9 '$ s(e$] s(e]$ ($9 s*9$:-e9$ s+P$9:+,]$:+,$]+&,#eGG x _ _y$ & $ _ _# _$ &$ _$ _'s8(H$/;0WH$p?x _8]$7 &0W9$/; _s $$s$s$s$s$ :$s $# r$'s$#$#$. $4;$U.$.$y= $DX$=$=$$]$ $ 9$  H$ Hr$ : H$ &&!W&-&<& sp  s+ ]&,&,&,&,A&,z&,&,&,' #e$#e"#e ^#e%#e#e#ez#e' )B +{ - / 2& 4_ 6 F&CA?{=B; 86(  Vs #!*;0W1t5W 5W + $( e +# d#(/;> d>>=x 9;p%;O$=$O$ O$:s's H9$4; H$$dDG-SEC. 3THE STORAGE PIPELINE65and completes the StorageRAM cycle ( 3.1.3). READTR1 and READTR2 transport the data, controlthe error corrector, and deliver the data to FastOutBus ( 3.1.5). Fault reporting, if necessary, isdone by READTR2 as soon as the condition of the last quadword in the block is known ( 3.3).It is clear from Figure 7 that an I/ORead can be started every eight machine cycles, since this is thelongest period of activity of any stage. This would result in 530 million bits per second ofbandwidth, the maximum supportable by the memory system. The inner loop of a fast I/O task canbe written in two microinstructions, so if a new I/ORead is launched every eight cycles, one-fourthof the processor capacity will be used. Because ADDRESS is used for only one cycle per I/ORead,other tasksnotably the emulatormay continue to hit in the cache when the I/O task is notrunning.I/OWrite(x) writes into virtual location x a block of data delivered by a fast input device, togetherwith appropriate Hamming code check bits. The data always goes to storage, never to the cache,but if address x happens to hit in the cache, the entry is invalidated by setting a flag ( 4). Figure8 shows that an I/OWrite proceeds through the pipeline very much like an I/ORead. The difference,of course, is that the WRITETR stage runs, and the READTR1 and READTR2 stages, although they run,do not transport data. Note that the write transport, from FastInBus to WriteBus, proceeds inparallel with mapping. Once the block has been loaded into WriteReg, STORAGE issues a writesignal to StorageRAM. All that remains is to run READTR1 and READTR2, as explained above. If amap fault occurs during address translation, the write signal is blocked and the fault is passed alongto be reported by READTR2.<==_%@%B%E %GB%I{%9'7'5{'3B'1 '.','*^'**A*!z*#*%*(%**^*A-e-e-e-e-e-e z-e A-e*-e55-$]V5P$97f9$V49$ 2$9V2f]$V2f$] /:$ ,$9 ,]$ ,$],$9,$9:,$9 ,$9V,$9,$9,$9)*4$9%:*4$9's*4$9V*4$9 *4$9*4$9#*4$9*$]*$+*4$9,I$))$;t'l$9)'I$)'I$]2'l$9.'l$90W'l$9+'l$97'l$94'l$99;'l$9H$$9DX$$9F$$9;t$$9?$$9=$$9B$$99;$$]9;$$K$$99;&$530-/$9/$9V/$9 /$9:/$9/$9/$9 /$] /$#/$9 1s$ A0- z0-0-0-0-:0-s0-0-s,$9,$9H-- /$9/$9s/$90-0- 0-@txC=p!,A$9H$@H$!Wl$er$srr H z HH eH  $!W$# O$r5-]$%:d<K7 THE MEMORY SYSTEM OF A HIGH-PERFORMANCE PERSONAL COMPUTER66Figure 8 shows a delay in the MAP stage's handling of I/OWrite. MAP remains in state 3 for twoextra cycles, which are labelled with asterisks, rather than state numbers, in Figure 8. This delayallows the write transport to finish before the write signal is issued to StorageRAM. Thissynchronization and others are detailed in 5.Because WRITETR takes eleven cycles to run, I/OWrites can only run at the rate of one every elevencycles, yielding a maximum bandwidth for fast input devices of 390 million bits per second. At thatrate, two of every eleven cycles would go to the I/O task's inner loop, consuming 18 percent of theprocessor capacity. But again, other tasks could hit in the cache in the remaining nine cycles.3.3 History and fault reportingThere are two kinds of memory system faults: map and storage. A map fault is a MapRAM parityerror, a reference to a page marked vacant, or a write operation to a write-protected page. Astorage fault is either a single or a double error (within a quadword) detected during a read. Inwhat follows we do not always distinguish between the two types.Consider how a page fault might be handled. MAP has read the MapRAM entry for a reference andfound the virtual page marked vacant. At this point there may be another reference in ADDRESSwaiting for MAP, and one more in the processor waiting for ADDRESS. An earlier reference may bein READTR1, perhaps about to cause a storage fault. The processor is probably several instructionsbeyond the one that issued the faulting reference, perhaps in another task. What to do? It wouldbe quite cumbersome at this point to halt the memory system, deal with the fault, and restart thememory system in such a way that the fault was transparent to the interrupted tasks. Instead, theDorado allows the reference to complete, while blunting any destructive consequences it mighthave. A page fault, for example, forces the cache's vacant flag to be set when the read transport isdone. At the very end of the pipeline READTR2 wakes up the Dorado's highest-priority microtask,the fault task, which must deal appropriately with the fault, perhaps with the help of memory-management software.Because the fault may be reported well after it happened, a record of the reference must be keptwhich is complete enough that the fault task can sort out what has happened. Furthermore,because later references in the pipeline may cause additional faults, this record must be able toencompass several faulting references. The necessary information associated with each reference,about 80 bits, is recorded in a 16-element memory called History. Table 3 gives the contents ofHistory and shows which stage is responsible for writing each part. History is managed as a ringbuffer and is addressed by a 4-bit Storage Reference Number or SRN, which is passed along withthe reference through the various pipeline stages. When a reference is passed to the MAP stage, acounter containing the next available SRN is incremented. A hit writes the address portion ofHistory (useful for diagnostic purposes; see below), without incrementing the SRN counter.EntryWritten byVirtual address, reference type, task number, cache columnADDRESSReal page number, MapRAM flags, map faultMAPStorage fault, bit corrected (for single errors)READTR2Table 3: Contents of the History memoryTwo hardware registers accessible to the processor help the fault task interpret History: FaultCountis incremented every time a fault occurs; FirstFault holds the SRN of the first faulting reference.The fault task is awakened whenever FaultCount is non-zero; it can read both registers and clearFaultCount in a single atomic operation. It then handles FaultCount faults, reading successiveelements of History starting with History[FirstFault], and then yields control of the processor to the]zX{z{z{z{z{z{z{ z{z{zWT{z{z{~z{z U_TLK{zRO{z {z{~z.N7&L,{z{z+KWG}XCz(}z}z{zBc*.@H?[<<0{z{z:<{9(z{z{z}z7{z"76 F4#}z(3 R1P0M."{z-} z7+ (YU&G %QC#}z<"I}z 6$A9{z/${z9{z* G{z  ((#  -zoo}. F F(F# F-zoFz:.{z{z.{Nz0.{     ( (#  -z o oU zX"t>} z(} z {zlI 7dMD Hb8SEC. 3THE STORAGE PIPELINE67other tasks. If more faults have occurred in the meantime, FaultCount will have been incrementedagain and the fault task will be reawakened.The fault task does different things in response to the different types of fault. Single bit errors,which are corrected, are not reported at all unless a special control bit in the hardware is set. Withthis bit set, the fault task can collect statistics on failing storage chips; if too many failures areoccurring, the bit can be cleared and the machine can continue to run. Double bit errors may bedealt with by re-trying the reference; a recurrence of the error must be reported to the operatingsystem, which may stop using the failing memory, and may be able to reread the data from the diskif the page is not dirty, or determine which computation must be aborted. Page faults are the mostlikely reason to awaken the fault task, and together with write-protect faults are dealt with byyielding to memory-management software. MapRAM parity errors may disappear if the reference isre-tried; if they do not, the operating system can probably recover the necessary information.Microinstructions that read the various parts of History are provided, but only the emulator and thefault task may use them. These instructions use an alternate addressing path to History which doesnot interfere with the SRN addressing used by references in the pipeline. Reading base registers,the MapRAM, and CacheA can be done only by using these microinstructions.This brings us to a serious difficulty with treating History as a pure ring buffer. To read aMapRAM entry, for example, the emulator must first issue a reference to that entry (normally aMapRead), and then read the appropriate part of History when the reference completes; similarly, aDummyRef (see Table 3) is used to read a base register. But because other tasks may run and issuetheir own references between the start of the emulator's reference and its reading of History, theemulator cannot be sure that its History entry will remain valid. Sixteen references by I/O tasks, forexample, will destroy it.To solve this problem, we designate History[0] as the emulator's "private" entry: MapRead,MapWrite, and DummyRef references use it, and it is excluded from the ring buffer. Because thefault task may want to make references of its own without disturbing History, another private entryis reserved for it. The ring buffer proper, then, is a 14-element memory used by all referencesexcept MapRead, MapWrite, and DummyRef in the emulator and fault task. For historical reasons,Fetch, Store and Flush references in the emulator and fault task also use the private entries; the tagmechanism ( 4.1) ensures that the entries will not be reused too soon.In one case History is read, rather than written, by a pipeline stage. This happens during a readtransport, when READTR1 gets from History the cache address (row and column) it needs for writingthe new data and the cache flags. This is done instead of piping this address along from ADDRESSto READTR1.4. Cache-storage interactionsThe preceding sections describe the normal case in which the cache and main storage functionindependently. Here we consider the relatively rare interactions between them. These can happenfor a variety of reasons:Processor references that miss in the cache must fetch their data from storage.A dirty block in the cache must be re-written in storage when its entry is needed.Prefetch and flush operations explicitly transfer data between cache and storage.I/O references that hit in the cache must be handled correctly.Cache-storage interactions are aided by the four flag bits that are stored with each cache entry tokeep track of its status (see Figure 4). The vacant flag indicates that an entry should never match; itis set by software during system initialization, and by hardware when the normal procedure forloading the cache fails, e.g., because of a page fault. The dirty flag is set when the data in the entryis different from the data in storage because the processor did a store; this means that the entry^{G(e;zXL(4V'S02R@"PYO ;M5(L ZJHI.,G}${z0EUBNAJ Q?{z= >B{z?;X9{zX8~z7"6~z:5M3:{z{z 1.J~z-P~z~z= +H*H5)(~z~z~z!'@~z~z~zL%>"E! {zJ>{z{z2|Xz}z/ SOOR Q {z{z<t I~z4l>"~z'd#=$ Hc THE MEMORY SYSTEM OF A HIGH-PERFORMANCE PERSONAL COMPUTER68must be written back to storage before it is used for another block. The writeProtected flag is a copyof the corresponding bit in the map. It causes a store into the block to miss and set vacant; theresulting storage reference reports a write-protect fault ( 3.3). The beingLoaded flag is set for about 15 cycles while the entry is in the course of being loaded from storage; whenever the ADDRESSstage attempts to examine an entry, it waits until the entry is not beingLoaded, to ensure that theentry and its contents are not used while in this ambiguous state.When a cache reference misses, the block being referenced must be brought into the cache. Inorder to make room for it, some other block in the row must be displaced; this unfortunate iscalled the victim. CacheA implements an approximate least-recently-used rule for selecting thevictim. With each row, the current candidate for victim and the next candidate, called next victim,are kept. The victim and next victim are the top two elements of an LRU stack for that row;keeping only these two is what makes the replacement rule only approximately LRU. On a miss, thenext victim is promoted to be the new victim and a pseudo-random choice between the remainingtwo columns is promoted to be the new next victim. On each hit, the victim and next victim areupdated in the obvious way, depending on whether they themselves were hit.The flow of data in cache-storage interactions is shown in Figure 2. For example, a Fetch thatmisses will read an entire block from storage via the ReadBus, load the error-corrected block intoCacheD, and then make a one-word reference as if it had hit.What follows is a discussion of the four kinds of cache-storage interaction listed above.4.1 Clean missWhen the processor or IFU references a word w that is not in the cache, and the location chosen asvictim is vacant or holds data that is unchanged since it was read from storage (i.e., its dirty flag isnot set), a clean miss has occurred. The victim need not be written back, but a storage read mustbe done to load into the cache the block containing w. At the end of the read, w can be fetchedfrom the cache. A clean miss is much like an I/ORead, which was discussed in the previous section.The chief difference is that the block from storage is sent not over the FastOutBus to an outputdevice, but to the CacheD memory. Figure 9 illustrates a clean miss.All cache loads require a special cycle, controlled by READTR1, in which they get the correct cacheaddress from History and write the cache flags for the entry being loaded; the data paths ofCacheA are used to read this address and write the flags. This RThasA cycle takes priority over allother uses of CacheA and History, and can occur at any time with respect to ADDRESS, which alsoneeds access to these resources. Thus all control signals sent from ADDRESS are inhibited byRThasA, and ADDRESS is forced to idle during this cycle. Figure 9 shows that the RThasA cycleoccurs just before the first word of the new block is written into CacheD. (For simplicity andclarity we will not show RThasA cycles in the figures that follow.) During RThasA, the beingLoadedflag is cleared (it was set when the reference was in ADDRESS) and the writeProtected flag is copiedfrom the writeProtected bit in MapRAM. As soon as the transport into CacheD is finished, the wordreference that started the miss can be made, much as though it had hit in the first place. If thereference was a Fetch, the appropriate word is sent to FetchReg in the processor (and loaded intoFetchRegRAM); if a Store, the contents of StoreReg are stored into the new block in the cache.If the processor tries to use data it has fetched, it is prevented from proceeding, or held until theword reference has occurred (see 5.1). Each fetch is assigned a sequence number called its tag,which is logically part of the reference; actually it is written into History, and read when needed byREADTR1. Tags increase monotonically. The tag of the last Fetch started by each task is kept inStartedTag (it is written there when the reference is made), and the tag of the last Fetch completedby the memory is kept in DoneTag (it is written there as the Fetch is completed); these are task-specific registers. Since tags are assigned monotonically, and fetches always complete in orderwithin a task, both registers increase monotonically. If StartedTag=DoneTag, all the fetches thatZ\zX{z{z{z{z{z{z{ z{z{zT"$~ zRP~zP*~ zOy={Mz+~ zLq=IF:GPF>}z@ D=} zC6<{zAF{z @.K >H=&C9B~z8w'5653Y/}X ,z {z~z5+B)} z2(2~z~z& |{z{~z.% L#> [4{zPS1~zC{z K:{z~z{z?~zCI~z~z~ ;z{z ~ z~ z {z 33(1~z.+{z~zF 3"}z | P}z Tt{z3~z} z-~z l}z~z  Md_ H_RSEC. 4CACHE-STORAGE INTERACTIONS69<==F{zt!2m=7'eE{z4] 3;UF5D"&: B }X~z ~zOlF~z#{z{z~zd\ \ Hac t2kOp t $    k O2y+$$$$]$G$$+$2$$$$$$$9k$$2A$Gd$k+$9$l$$$$$$$$$$$$d$$$$ z$ V$ V+G$ z$]$:$G$r$$$$r$%$+$$r$]$$$G$$]A$$]$%2#2"2!2 22l2O2Ok3kkkkkkkA$$G$A$]lO3 $$$$d$V$]$ d$$G$ d$]+$V$dG$+$]lO3y]$Vk$    k O3Od$]+$$l$d$2O $s 9$r r $ r  $ r O $O d9$V +$ r 9$r"s $# $9# 9$9$$ r$9$ 9$r O $ $  @$ $!s$d&$lO3%$$G$%$]&3k%k#k"k!k kklk-2,2+2*2)2(l2'P2&32%$$]$%$%$%G$%$]%$&r$]%$$-$-r$.$&r$lG$$$+k$]$]]$ O k   ]]y$    !2%$,92%93$1 $/$.$-$+{$,$' 9!z99$$$$$%$$$#$"$!z$ ^$A$%$' $(%$)B$*^$]99 99z$]$A$$$$ ]$ z$$$$$ A$ $$ $$$$-l$Vpd \ *3"lSEC. 4CACHE-STORAGE INTERACTIONS71A Flush explicitly removes the block containing the addressed location from the cache, rewriting itin storage if it is dirty. Flush is used to remove a virtual page's blocks from the cache so that itsMapRAM entry can be changed safely. If a Flush misses, nothing happens. If it hits, the hitlocation must be marked vacant, and if it is dirty, the block must be written to storage. To simplifythe hardware implementation, this write operation is made to look like a victim write. A dirty Flushis converted into a FlushFetch reference, which is treated almost exactly like a Prefetch. Thus, whena Flush in ADDRESS hits, three things happen:the victim for the selected row of CacheA is changed to point to the hit column;the vacant flag is set;if the dirty flag for that column is set, the Flush is converted into a FlushFetch. Proceeding like a Prefetch, this does a useless read (which is harmless because the vacant flag hasbeen set), and then a write of the dirty victim. Figure 11 shows a dirty Flush. The FlushFetchspends two cycles in ADDRESS, instead of the usual one, because of an uninteresting implementationproblem.<==AF~z~ ?~z{z==t2}X}} z{z{~z~z. ?{z{~z | U0't{z{~z1)2l !4&{z{~z d  Ha: $:  $$: $: O $%: 9$r r$9Vt$!V$ 9$rz +$ 9$ O $  $  $ 9$r $ ks$+$O$$$:3:::::k: : : ::::2:O: k$ ]$OkO$]G$z$O$ @$] G$ $ @$$z$]$ $$ $$ $$$2Okz$]VG$V$z$3OlV V!V"V#V%V&3V'OVV$O$]z$A$]G$$A$$ $]A$d$'$&$&$ $G$s$+$$]OG$A$$$$d$$$$$$$$$$$A$$$$ $O$9 $k kd$G G$ rk$ +$ $ $ $:$ 3$ $ kA$ $O$$k$A$$]$ A$ O$ k   2$ p ts:V$$$d$$:u :t# , , ," + z r: y$ ,,,,,($3Ol  ]$] :G$ :$ ]$ !"#%&3'O(l(lV)V*V+V,V-V/V03V :$!3$] ]$(%$](G$($(%$($($](%$H$0$/$/$($G$!V$!$OOk$$]$   !z -l$d$d$d$ d$ $d$ @d$d$d$d$d$ yd$ ]d$d$$d$Ad$]d$zd$ ]*^d$)Ad$(%d$'d$%d$Ad$ ]d$!zd$"d$#d$$d$$d$d$d$d$d$d$!z',d$+zd$-d$.d$/d$1 d$3d$2%,2%d$ $y2ss $dpdD UT3$ THE MEMORY SYSTEM OF A HIGH-PERFORMANCE PERSONAL COMPUTER72<==,:}X 6z {z{z{z5o:{z{z3{z2{z0{z9/<{z5 -,.,4" {z*{z{z0),E&{z3{z{z$} 8{z"{z{z{z!u{z  {z{z ({z {zm {z{~z.{z{z{z {z~ z:{z ~ zB {z ~z,2XM* ~z6{z {z& }X  |z8~z {z #9t A {z.4l4{z{z 2d H_SEC. 5TRAFFIC CONTROL75At the other extreme, the rule could be that a stage waits only if it cannot acquire the resources itwill need in the very next cycle. This would be quite feasible for our system, and the proper choiceof priorities for the various stages can clearly prevent deadlock. However, each stage that may beforced to wait requires logic for detecting this situation, and the cost of this logic is significant.Furthermore, in a long pipeline gathering all the information and calculating which stages canproceed can take a long time, especially since in general each stage's decision depends on thedecision made by the next one in the pipe.For these reasons we adopted a different strategy in the Dorado. There is one point, early in thepipeline but after ADDRESS, at which all remaining conflicts are resolved. A reference is notallowed to proceed beyond that point without a guarantee that no conflicts with earlier referenceswill occur; thus no later stage ever needs to wait. The point used for this purpose is state 3 of theMAP stage, written as MAP.3. No shared resources are used in states 0-3, and STORAGE is not starteduntil state 4. Because there is just one wait state in the pipeline, the exact timing of resourcedemands by later stages is known and can be used to decide whether conflicts are possible. Wenow discuss the details.5.3.1 STORAGE and WRITETRIn a write operation, WRITETR runs in parallel but not in lockstep with MAP; see, for example,Figure 10. Synchronization of the data transport with the storage reference itself is accomplishedby two things.MAP.3 waits for WRITETR to signal that the transport is far enough along that the data willarrive at the StorageRAM chips no later than the write signal generated by STORAGE. Thiscondition must be met for correct functioning of the chips. Figure 13 shows MAP waitingduring an I/OWrite.WRITETR will wait in its next-to-last state for STORAGE to signal that the data hold time ofthe chips with respect to the write signal has elapsed; again, the chips will not work if thedata in WriteReg is changed before this point. Figure 10 shows WRITETR waiting during avictim write. The wait shown in the figure is actually more conservative than it needs tobe, since WRITETR does not change WriteReg immediately when it is started.<=={z{z1{z=$9;>95}X}2z{z}z{z1N<!/ -r{z {z$+{z% {z*j 8{z({z{~z&{z){z% *3#%{z"M ~{z9td2 & H\(t  :s+ $r $AG$2$  $'$' $($d P$A$  $] $A$ $ G$A$]y $O $]VA$'O &3 % # " !    k O 2     y $VA$V PG$y $]kO2y9$%G$kW$%$W$2%$$$z$$$ 3$$W$$ $ +$$$$3$ N$%$$$z$$$3$$W$$$$$d$$3$$$$$B$$$$$$$$$$$$$2$O$$$B$$$$$$$$$$H$$$$$k$$]$ss s s s ks Ns2s2: N: k: ::::2:s2s P$]G$ P$A$] P$$$  $  $sOs$ @$$2kk^O^2^^^^^k^$$9$$kO$$ $A$ k$.$$$$$ $ $$$$r$ V$ 9$$$$9$V$ 9*:$)$($&$%$$ :$!V$"s$#$$$$$$$$r$!V&,s$+V$-$.$/$0$2$4$2,,,9$$d $$ $AG$,O $3$3 $4$ P$+z$,O $]+V $+z$+V $+V G$+z$]# $$ $]#A$3 2l 1P 03 / - , + + * ) (l 'O &3 % # # $#A$# PG$# $]#"! kO2G$ P$] P$   e e ke eeee2e+e NI$2%$U  ^3$2pdk%k$k3$3$t^  &4^ THE MEMORY SYSTEM OF A HIGH-PERFORMANCE PERSONAL COMPUTER765.3.2 CacheD: consecutive cache loadsLoading a block into CacheD takes 9 cycles, as explained in 4.1, and a word reference takes onemore. Therefore, although the pipeline stages proper are 8 cycles long, cache loads must be spacedeither 9 or 10 cycles apart to avoid conflict in CacheD. After a Fetch or Store, the next cache loadmust wait for 10 cycles, since these references tie up CacheD for 10 cycles. After a Prefetch,FlushFetch or dirty I/ORead, the next cache load must wait for 9 cycles. STORAGE sends MAP asignal that causes MAP.3 to wait for one or two extra cycles, as appropriate. Figure 14 shows a Fetchfollowed by a Prefetch, followed by a Store, and illustrates how CacheD conflict is avoided by extracycles spent in MAP.3 Note that the Prefetch waits two extra cycles, while the Store only waits oneextra.<==z~z~zH {z~z#~zG6t2}XzB< L N4'}z&5(,D  P{z{z* t{z1{zB lQ${z!d  ZHa!$!$d!$$!$$$"$$!$$!$$"%$!s$$#$3$9l$k2H$G$9!k$$$$$$$2%$3$ !$ @!$ !$$ !$$ ]$ 9"$$ ]!$$ !$$ "%$ 9!s$$ #$93$9l$kH$G]$!k$@$$$9$$$%$93$!$$ !$ $ !$ $ @"$H$ d#k$"$#G$#k$d$]"$V3$93l$kH$Gz$!k$]$$$V$3$$%$V3$!$$!$$!$$!$]!$!$$!$$z$V"$$z!$$2!$$2"%$V!s$$#$%$$]$%$y3$2t N k   %$$]$]VOk$]s3G$s%$$" Ws:+ :$9; $r ]$ $ :$$ $r. $r$9($92$9%:/ :*4:: ]@$z$rpt" W d" W" W% $%$$%$%$]$$$ 2OkA$]G$$A$ssssss3sOsO:l:: :!:":#:%:$$]A$$]G$$$$z$]$+$%$$z$$$z$G$:$$ y$] V3G$ V%$ y$($3Ol  ]$] :G$ :$ ]$ s!s"s#s%s&3s'Os(ls(l:):*:+:,:-:/:03: :$!3$] ]$(%$](G$($(%$($(z$](%$H$0$/z$/$(z$G$!V$!$$]s3G$s%$$%#"!lsz2$"#%&3'O(l)**^$]*:G$*:$*^$*s+s,s-s/s03s1Ps2ls2l:3:4:5:6:7:9::4:*:$+3$]*^$2%$]2G$2$2%$2$2z$]2%$#H$:$9z$9$2z$%G$+W$+$"$]"s3G$"s%$"$V3@$# $98 $9# $9"s 8 $97 !$!$       %:*:/3B% %%#$ #$#$,22%2724^$3B$5{$6$7$8$; $2%$1 $/$.$-$+z$,$'2!z22$$$$$$$$$#$"$!z$ ]$A$%$'$(%$)A$*^$]22 22z$]$A$$$$ ]$ y$$$$$ @$ $$ $$$$5{$9$! 7 dp)!$$!$$]39$dF U%;-&+SEC. 5TRAFFIC CONTROL77Figure 15 shows a Store with clean victim followed by a Fetch with dirty victim and illustrates thisinterlock. ADDRESS waits until cycle 26 to start WRITETR. Also, the fetch waits in MAP.3 until thesame cycle, thus spending 13 extra cycles there, which forces the fetch victim to spend 13 extracycles in ADDRESS. The two-cycle gap in the use of CacheD shows that the fetch could have leftMAP.3 in cycle 24.<==$D$D$E$.eH$=B$>$]=$=B$=$=G$=B$]5z$6P$]5W:$EPD4CA@?>==^$?z$@$A$F%$B$C$B=B72%,E $"+ 9: p0"d$q/FI& g THE MEMORY SYSTEM OF A HIGH-PERFORMANCE PERSONAL COMPUTER78Main storage boards are the same size as logic boards but are designed to hold an array of MOSRAMs instead of random ECL logic. A pair of storage boards make up a module, which holds 512Kbytes (plus error correction) when populated with 16K RAMs, 2M bytes with 64K RAMs, or 8Mbytes with (hypothetical) 256K RAMs. There is room for four modules, and space not used forstorage modules can hold I/O boards. Within a module, one board stores all the words with evenaddresses, the other those with odd addresses. The boards are identical, and are differentiated bysideplane wiring.A standard Dorado contains, in addition to its storage boards, eleven logic boards, including disk,display, and network controllers. Extra board positions can hold additional I/O controllers. Threeboards implement the memory system (in about 800 chips); they are called ADDRESS, PIPE, andDATA, names which reflect the functional partition of the system. ADDRESS contains theprocessor interface, base registers and virtual address computation, CacheA (implemented in 256 by4 RAMs) and its comparators, and the LRU computation. It also generates Hold, addresses DATA onhits, and sends storage references to PIPE.DATA houses CacheD, which is implemented with 1K by 1 or 4K by 1 ECL RAMs, and holds 8K or32K bytes respectively. DATA is also the source for FastOutBus and WriteBus, and the sink forFastInBus and ReadBus, and it holds the Hamming code generator-checker-corrector. PIPEimplements MapRAM, all of the pipeline stage automata (except ADDRESS and HITDATA) and theirinterlocks, and the fault reporting, destination bookkeeping, and refresh control for the MapRAMand StorageRAM chips. The History memory is distributed across the boards: addresses onADDRESS, control information on PIPE, and data errors on DATA.Although our several prototype Dorados can run at a 50 nanosecond microcycle, most of themachines run instead at 60 nanoseconds. This is due mainly to a change in board technology froma relatively expensive point-to-point wire-routing method to a cheaper Manhattan routing method. 7. PerformanceThe memory system's performance is best characterized by two key quantities: the cache hit rateand the percentage of cycles lost due to Hold ( 5.1). In fact, Hold by itself measures the cache hitrate indirectly, since misses usually cause many cycles of Hold. Also interesting are the frequenciesof stores and of dirty victim writes, which affect performance by increasing the frequency of Holdand by consuming storage bandwidth. We measured these quantities with hardware event-counters,together with a small amount of microcode that runs very rarely and makes no memory referencesitself. The measurement process, therefore, perturbs the measured programs only trivially.We measured three Mesa programs: two VLSI design-automation programs, called Beads and Placer;and an implementation of Knuth's TEX [8]. All three were run for several minutes (several billionDorado cycles). The cache size was 4K 16-bit words.Percent of cycles:Percent of references:Percent of misses:ReferencesHoldHitsStoresDirty victims Beads36.48.1499.2710.516.3Placer42.94.8999.8218.765.5TEX38.46.3399.5515.234.9Table 5: Memory system performanceTable 5 shows the results. The first column shows the percentage of cycles that contained cachereferences (by either the processor or the IFU), and the second, how many cycles were lost becausethey were held. Hold, happily, is fairly rare. The hit rates shown in column three are gratifyingly^qXrqrqrqrqrqrqr qrqrqXK1&rVqrqDUC1rqrqSrq8R;rqrq8 P NO3LYJ0rqrqICsqsqG|sq-sq EYDtrqrq!tq sqB!sq?sq4rqrq>Asq.<Fs;9q rq-rqrq9 2r81qrqI6sqsqsq3+&1T0z`+sX (|q@&&tqtq%t7tq#0,t"lqG OdT9rq5rq>1.^^  ^((#^  -z^oouX 0;* )#0;<F< F<(F#< F-z<oFNq)#0; )#0; Frq)#0;     ( (#  -z o o>"lK vq4d tq1 HcLSEC. 7PERFORMANCE79largeall over 99 percent. This is one reason that the number of held cycles is small: a miss cancause the processor to be held for about thirty cycles while a reference completes. In fact, the tableshows that Hold and hit are inversely related over the programs measured. Beads has the lowest hitrate and the highest Hold rate; Placer has the highest hit rate and the lowest Hold rate.The percentage of Store references is interesting because stores eventually give rise to dirty victimwrite operations, which consume storage bandwidth and cause extra occurrences of Hold by tying upthe ADDRESS section of the pipeline. Furthermore, one of the reasons that the StoreReg registerwas not made task-specific was the assumption that stores would be relatively rare (see thediscussion of StoreReg in 5.1). Table 5 shows that stores accounted for between 10 and 19percent of all references to the cache.Comparing the number of hits to the number of stores shows that the write-back discipline used inthe cache was a good choice. Even if every miss had a dirty victim, the number of victim writeswould still be much less than under the write-through discipline, when every Store would cause awrite. In fact, not all misses have dirty victims, as shown in the last column of the table. Thepercentage of misses with dirty victims varies widely from program to program. Placer, which hadthe highest frequency of stores and the lowest frequency of misses, naturally has the highestfrequency of dirty victims. Beads, with the most misses but the fewest stores, has the lowest. Thelast three columns of the table show that write operations would increase about a hundredfold ifwrite-through were used instead of write-back.Acknowledgements The concept and structure of the Dorado memory system are due to Butler Lampson and ChuckThacker. Much of the design was brought to the register-transfer level by Lampson and BrianRosen. Final design, implementation, and debugging were done by the authors and Ed McCreight,who was responsible for the main storage boards. Debugging software and microcode were writtenby Ed Fiala, Willie-Sue Haugeland, and Gene McDaniel. Haugeland and McDaniel were also ofgreat help in collecting the statistics reported in 7. Useful coments on earlier versions of thispaper were contributed by Forest Baskett, Gene McDaniel, Jim Morris, Tim Rentsch, and ChuckThacker. References1.Bell, J. et. al. An investigation of alternative cache organizations. IEEE Trans. Computers C-23, 4, April 1974, 346-351.2.Bloom, L., et. al. Considerations in the design of a computer with high logic-to-memory speed ratio. Proc. GigacycleComputing Systems, AIEE Special Pub. S-136, Jan. 1962, 53-63.3.Conti, C.J. Concepts for buffer storage. IEEE Computer Group News 2, March 1969, 9-13.4.Deutsch, L.P. Experience with a microprogrammed Interlisp system. Proc. 11th Ann. Microprogramming Workshop, PacificGrove, Nov. 1979.5.Forgie, J.W. The Lincoln TX-2 input-output system. Proc. Western Joint Computer Conference, Los Angeles, Feb. 1957,156-160.6.Geschke, C.M. et. al. Early experience with Mesa. Comm. ACM 20, 8, Aug. 1977, 540-552.7.Ingalls, D.H. The Smalltalk-76 programming system: Design and implementation. 5th ACM Symp. Principles ofProgramming Languages, Tucson, Jan. 1978, 9-16.8.Knuth, D.E. TEX and METAFONT: New Directions in Typesetting. American Math. Soc. and Digital Press, Bedford, Mass.,1979.9.Lampson, B.W. et. al. An instruction fetch unit for a high-performance personal computer. Technical Report CSL-81-1,Xerox Palo Alto Research Center, Jan. 1981. Submitted for publication.10.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.11.Liptay, J.S. Structural aspects of the System/360 model 85. II. The cache. IBM Systems Journal 7, 1, 1968, 15-21.12.Metcalfe, R.M., and Boggs, D.R. Ethernet: distributed packet switching for local computer networks. Comm. ACM 19, 7,July 1976, 395-404.]rG- ;qWW.+U9)TOtqI Rtq6tqOtq)%N0tq Lrq JKOI FH D6"C] uq5AHtq @U=> :=MJ;>:EV8 !3sX0qV/?4-M ,78$*)/)/_'?&'!Ts rq{rGwr9xwyrq{r wrVw{rwvr&3q{r+xwyrq{rDw)r{Nq{r5w'r{iq{r wrwxryrq{rPwxw{r 6q{r xwxwr8{  Qq{r wrYvr{ Glq{rVw{. r vr9vr{Iq{rMxwyrq{rfwxwyr{dD Hb THE MEMORY SYSTEM OF A HIGH-PERFORMANCE PERSONAL COMPUTER8013.Mitchell, J.G. et. al. Mesa Language Manual. Technical Report CSL-79-3, Xerox Palo Alto Research Center, April 1979.14.Pohm, A. et. al. The cost and performance tradeoffs of buffered memories. Proc. IEEE 63, 8, Aug. 1975, 1129-1135.15.Schroeder, M.D. Performance of the GE-645 associative memory while Multics is in operation. Proc. ACM SigOpsWorkshop on System Performance Evaluation, Harvard University, April 1971, 227-245. 16.Tanenbaum, A.S. Implications of structured programming for machine architecture. Comm. ACM 21, 3, March 1978, 237-246.17.Teitelman, W. Interlisp Reference Manual. Xerox Palo Alto Research Center, Oct. 1978.18.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. 19.Tomasulo, R.M. An efficient algorithm for exploiting multiple arithmetic units. IBM J. R&D 11, 1, Jan. 1967, 25-33.20.Wilkes, M.V. Slave memories and segmentation. IEEE Trans. Computers C-20, 6, June 1971, 674-675.DqXrqrqrqrqrqrqr qrqrqrq{rGwrwrvr3Fq{rwr=wxwyr q{r^wxw{ a)r+ q{rSwxwyr{ |q{r wr..q{r wrw*r{Dvr/{ q{rRxwyrdq{r0xwyr NH: HELVETICA HELVETICA  HELVETICA HELVETICA  HELVETICA  HELVETICA HELVETICAMATH  TIMESROMAN  LOGO HELVETICA HELVETICA  HELVETICA HELVETICA  HELVETICA HELVETICA MATH  TIMESROMAN LOGO  TIMESROMAN  TIMESROMAN  TIMESROMAN   TIMESROMAN   TIMESROMAN TIMESROMAN  TIMESROMAN TIMESROMAN TIMESROMAN TIMESROMAN TIMESROMAN TIMESROMAN TIMESROMAN  HELVETICA  HELVETICA  HELVETICA  HELVETICA HELVETICA HELVETICATEMPLATE@ GATES  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  HELVETICA HELVETICA HELVETICA MATH  LOGO  TIMESROMAN   TIMESROMAN  TIMESROMAN   TIMESROMAN  TIMESROMAN  TIMESROMAN TIMESROMAN TIMESROMAN  TIMESROMAN TIMESROMAN  TIMESROMAN  TIMESROMAN  TIMESROMAN TIMESROMAN TIMESROMAN  TIMESROMANL f n" W,4 e? RI S N^ g 2r 1{ ! n  ^ W_  I j N I < ? (# ,.3 N> GrM cV >` k Du . = 6 .    s> L f   m n & n08;@ J zS ] h ds ~ " >     O05  KepresseditmFig9.press [ h\'g6.press IfuFig7.press g7.press MemFig8[%h\'''.press IfuFig4.press IfuFig5.press IfuFi[?h\'''ress IfuFig1.press IfuFig2.press IfuFig3[Yh\'''pressedit/m ifuFinal.press _ Doradoifu.p[sh\'g6.press IfuFig7.press g10.press MemFig[h\'''.press IfuFig4.press IfuFig5.press IfuFi[h\j/ SDoradoB-W.presspiera13-Jan-81 16:34:55 PST