Hiphi Precision Interrupt Implementation in Pipelined Processors: A Comprehensive Guide (EN)

IMPLEMENTATION OF PRECISE INTERRUPTS IN PIPELINED PROCESSORS Dtpanmtnr 01 Elt~r~~l awi Compurrr Enginttring Unibwsiiy o/ Wisconsin-Madison Mdison. WI J37W Andrew R. Plazkun Caqwuttr Scitncrs Dtpamntnr Univtrsip of Wisconsin-Madison Modiron. WI 5.1706 An imerrupl Is precise if the saved process state corresponds with the sequcnnal model of program execution where one insrruction com- pletes before the next begins. In a pipclined processor. precise intcr- rums are diffcuh IO achmve baause an insrrucuon may be inirirmd before us predecessors have been completed. This pager describes and evaluates solunons IO the precise interrupt problem in pipclincd proccs- SOCS.

Abalmd the imcrruptcd insuuaion. The inurrupmd instruction may or may not have been cxautcd. depending on the definition of Ihe arcbitaturc and the cause of the intcmtpt. Whkbcvcr is the case. the intcrruptcd instruction has either complctcd. or has not swtcd cxsutiott. If the saved proccsr mu? is inconsistent wiIh the sequential l rchitec- rural model and does noI satisfy the above condirions. rhen the intcrrupl is imprecisr. The prccrse tntcrrupt problem is first described. Then live solu- tions are discussed tn detail. The first forces mstructions to complcte and modil) the process SUIC in archiIaIural order. The other four allow instructions IO complete in any order.

bu1 additional hardware is used so IhaI a precise SUIC can bc restored when an interrupt occurs. All the methods are drscussed in the context of a parallel pipeline struc- ture. Simulauon resuhs based on the CRAY-IS solar archueaurc are usal IO show IhaI. a1 Hess. the first solulion results in a performance degradation of about 16%. The rcmnining four solulions offer similar performance, and Ihrcc of them rcsul1 in as linle as a 3% performance loss. Several cxtenstons. including virtual memory and linear pipeline structures, arc briefly discussed. This paper dcsuibcs and comparcs ways of implemmting precise inlerrupu in p&lined proecssors.

The mcchods used arc dcsigncd IO modify che note of an cxeculing process in a carefully cootrolled way. The simpler methods force all instructions to update the pracss state in the architectural order. other. more complex mahods YH ponions of the proass stan so lhm the proper sute may be resscucd by the hardware a1 the time an intcrrupc occurs. 1.1. Clnrritic~lion of interrupts WC consider interrupts belonging IO Iwo classes. (1) Progmm inremcprs, somctimcs refemd 10 as ‘traps’, result from txctphon cond~dons dncemd during fetching and uccution of spozific instructions. There exceptions may be due IO software errors, for example trying IO cxautc an illegal opcodc.

numerical errors such as overflow. or they may be part of normal execution. for example page faults. Most currem computer architmurcs are based on a scquenIial model of program execution in which an archrtcmural program counIer scqucnces through instructtons one-by-one, finishing one before stan- ing the next. In conIras1. a high performance implemcntaIIon may be pipclined. prmmutg several instructions 10 be in some phase of cxccu- lion 81 the same time. The use of a sequential architecture and a pipe. lined implcmenudon clash at the time of an interrupt; pipclincd instruaions may modify the proms rule in an order diffcrcnt from tl181 defined by the scqucnlial archircmural model.

Al the time an interrupt condition is dcIected. the hardware may no1 bc in a state thac is mn- sistcnc wiIh any specific program counicr value. 1. Introduction 0) Exrtmol inwrrupu are no1 caused hy specific instructions and are often caused by sources outside the currently exaunng process. somcumes complcIely unrclaced IO i1. I/O inrrrupu and timer inurrupts arc examples. For a spccilic l rchbccturc, all iamrrupts may be ddincd to bc prccisc or only a proper subsc~. Virtually every arcbitenurc, howcvcr. has some types of interrupts that must be precise. There are a number of conditions under which prccisc intcnupu are either neoccwry or duirable. When an intmupt occurs.

the sUIc of an interrupted proms is Iypiully saved by the hardware, the &ware. or hy a combination of UIC two. The process stau generally consists of the program couuIcr. rcgiracrs. and memory. If the saved process SIaIc is conrisienf widi the Kquential archimctural model ~hcu :hc io~errup is precist. To be more specific. Ihe saved suue should rcflcu Ihc following condiIions. (1) For 110 and timer inccrrupts a praise process SIUC makes m- urting possible. (2) For sofnvarc debugging i1 is desirable for the saved Stale 10 bc pmise. This information can bc helpful in isolating the •X~I instruaion and circumrunecr that caused the excepion condition.

(3) For graceful rccovmy from arithmetic exccpdons. sofnvare rou- rincs may bc able IO take mepa. re-sole floating point numbers for cxamplc. to allow a proocss to continue. Some end cnscs of modem floating poin1 l rhhrnetic sysums might bcs~ hc hat~dlcd by rofrwrrc; gradual underflow in the proposed IEEE floating point standard [S~cvgl], for example. (1) All insbunions pracding the instruaion indieaud by the & program counter have been cxccu~ed and have modified Ihc pro- was state corrady. (2) All instructrons following the instruction indicated by the saved program counIcr arc unexecuted and have nor modilicd thcpro- aa sIaIc.

(4) In virtual memory systems precise interruplr allow a process to bc corrcmlp rcs~artcd ahcr a page fault has been serv~ccd. (3) If the interrupt IS caused by an cxccption condition raised by an insIrucIion in Ihe program. the saved program munler points IO (9 Unimplemented oncodes can be simulated by system software in a 291

Стр. 1

way transparent to the programmer if interrupts are precise. In this way. lower performance models of an erchitecrure can mein- tain compatibility with higher performance models ustng extended instruction sets. describes the model architecrure IO be used in describing prectse inter- rupt implementations. The model architecture IS vety simple so that the fundamentals of the methods can be clearly described. Sections 3 through 6 describe methods for implementing prectse interrupts. Set- (6) Virtual machines can be implemented if privileged instruction faults cause praise interrupts.

Host software can simulate these instructions and return IO the gum1 operanng system in e user- Iion 3 describes a simple method the! is easy lo implement. but which reduces performance. lr forces Instructions 10 complere in archttcctural order which somenmes inhibits the degree of parallelism in a pIpelined system. Section 4 descrtbes a higher performance variation where results may be bypassed IO other instructions before the results are used IO modify the process state. Sections 5 and 6 describe methods where instructions are allowed IO complete in any order. but where state infor- mation is saved so that a precise state may be restored when an inter- rupt occurs.

The descrtptions of these methods assume that the only state informauon is the program counter. general purpose registers. and matn memory. The methods are also discussed In the absence of a deu cache. Section 7 presents stmulation results. Experimental results based on these CRAY-IS simulations are presented and discussed. Section 8 contain e brief discussion of 1) saving additional state infor- mation. 2) supporting virtual memory, 3) precise interrupts when a data cache is used, and 4) linear pipeline structures. lrenrparenr way. 1.2. Hislorial Survey The prectse interrupt problem is as old as the first pipelined com- puter and is mentioned es early es Stretch lBuch62).

The IBM 360/91 [Ande67] was e well-known computer that produced imprecise inter- rupts under some circumstances. floating point exceptions. for exam- ple. Imprecise interrupts were a bruk with the IBM 360 architecture which made them even more not&able. All subsequent IBM 360 and 370 implementations have used less aggressive pipeline destgns where instructions modify the process state in strict program order. and ell interrupts are precise.’ A more complete description of the method used in these ‘linur” pipeline implementations is in Section 6.4. Most pipelined implementations of general purpose archittnura are similar IO those used by IBM.

These pipelines constrain all instructions IO pass through the pipeline in order with e stage II the end where exception conditions are checked before the process state is 2. Preliminaries modified. Examples include the Amdahl 470 end 580 (Amdh81.AmdhSOJ and the Gould/SE1 32/87 lWard82]. For descrtbing the various techniques. a model architecture is chosen SO that the basic methcds are not obscured by details and unnaessery complications brought about by e specific architecture. 2.1. Model Archileclure The high performance CDC 6600 lfhor70). CDC 7600 fBons69]. and Cray Research (Russ78. Cray791 computers allow instructions IO complete OUI of the architectural sequence. Conse- quently.

they have some exception conditions that result in imprecise interrupts. In these machines. the advantages of precise interrupts have been sacriliced in favor of maximum parallelism and design simplicity. I/O interrupts in these machines are precise. end they do not imple- ment vinuel memory. We choose a ’ register-register architsture where all memory accesses are through registers end all functional operations involve registers. In this respect it bears some similarity IO the CDC and Gray architecrurcs. but has only one set of registers. The load instructions are of the form: Ri = fRj+disp). That is.

the wntent of Rj plus a dis- placement given in the instruction are added IO form an effecrive address. The wnrent of the addressed memory locarion is loaded into Ri. Similarly. a store is of the form: (Rj + dirp) = Ri. where Ri is stored a1 the address found bv adding the wntent of Rj and a displacc- ment. The functional instructions are of the form Ri - Rj op Ilk, where op is the operation being performed. For unap operations. the degenerate form Ri = op Rk is used. Conditional instructtons are of the form P = disp : Rj op Rj. where the displacement is the address of the branch target: op is a relational operator. = , > , c , etc.

The CDC STAR-100 ]HiTa72] and CYBER 200 [CDCSI] series maehines else allow instructions IO complete OUI of order. end I@ do support virtual memory. In these machines the use of vector instructions futtber compliutes the problem, and all Ibe difftculdes were not fully recogniaed until late in the development of the STAR- 100. The evmuual solution was the addition of an invisible exchmI,fr pac&ge (CDCSl]. This captures machinedependent state information resulting from penially completed instructions. A similar approach has more recendy been suggested in MIPS [Henn82] where pipeline infor- metion is dumped II the time of an interrupt and restored to the pipeline when the process is resumed.

This solution makes a process restartable altbougb it is l rguable whether it has all the futures and advantages of an rrcbitamtrally precise interrupt. For example, it might be neces- sary IO have implementadondependen1 software sift through the ma&inedependenI state in order to provide complete debug informa- tion. The only process sum In the model architecrure consists of the program counler. the general purpose registers and main memory. The l rchnecturc is simple, has a minimal amount of process stale. can be easily pipelined. and can be implemented in a srretghtforward way with parallel funcnonel units like the CDC end Cray architectures. Hence.

implemennng precise interrupts for the model architecture pmenrs a realistic problem. Initially. wc assume no operand cache. Similarly. condition codes are not used. They add other problems beyond precise interrupts when a pipetincd unplen1entauon is used. Extenstons for operand cache and condition codes are discussed in Section 8. . The recently-announced CDC CYBER 1801990 [CDC84] is a pipelined implementation of a new architecture that supports virmel. memory, and offers roughly the same performance as l CRAY-IS. To provide prectse interrupts.

the CYBER 18OKKJO uses a history buffer, IO be described later in this paper, where state informetion is saved just The implementaIIon for the simple architecture is shown in Fig. 1. 11 uses an instruction fetch/decode pipeline which processes instruc- nons in order. The last stage of the fetch/decode pipeline is an issue register where all register interlock conditions are checked. If there are no regtster conflicts. an instructton issues IO one of the parallel functional units. Here. the memov access function is implemented as one of the funcuonal unns. The operand registers are read a1 the time an instructton Issues. There is a single result bus that returns results to the regtster ftle.

This hus mav be reserved a1 the ome an instruction issues or when an instructjon is approachmg completion. This prior IO being modified. Then when an interrupt occurs. this ‘history” information can be used IO back the system up into e precise sure. 1.3. Paper Overview This paper concentrates on explaining and discussing basic mahtxis for implementing precise interrupts in pipelined processors. We emphesim solar architectures (as opposed to vector architectures) beceuse of their applicability IO a wider range of machines. Soztion 2 assumes the funcuonal unit times are deterministic. A new instruction an issue every clock period in the absence of reftster or result bus conflicts. 292

Стр. 2

FUNCTIONAL UNIT 1 with the program counter value corresponding IO the tnstrucnon being held tn the tssue regtster. The registers end main memory are tn a suu conststent with this program counter value. Beuusc excepuon conditions detected prior IO tnstrucnon on be handled easily as descrtbed above. we will not consider them my further. Rather. we will concentrate on exceptton conditions detmed after insaucr~on issue. INStRUCTION FETCH/nECOIlE @=I- II FUNCTIONAL UNIT 2 With this method. instructions modify the process sute only when all prevtouslv issued tnstrucuons arc known IO be free of cxcepnon con- ditions.

This sectton descrther a strategy that is most easily imple- mented when pipeline delays in the parellel funcnonal unrts are fixed. Thrt IS. they do not depend on the operands. only on the function. Thus, the result hur can br reserved at the umc of issue. 3. In-order Instruction Completion FILE r- I I REGISTER -Yml- First. we consider a method commonly used IO control the pipe lined organiunon shown in Fig. I. This method may be used reprd- less of whether precise interrupts are IO be implemented. The precise interrupt methods dcscrihed in this papr are mtegreted into this basic control srretcgv. however. To control the result bus. a “result shift register” IS used: see Fig. 2. Here.

the stages are labeled I through n. I RESULT ElLlf Figure 1. Pipelined rmplemcntaoon of our model architecture. Not shown is the result shift regtstcr used IO control the result bus. 01RLc-r1oN T- To demonstrate how an imprecise process state mav occur in our model architecture. consider the followtng sectton of code which sums the elements of arrays A end B into array C. Consider the tnstructionr in statements b and 7. Although the integer add which increments the loop count will be issued after the floaunp point add, it will complete Example I w Cotttmettu Eeauu TlItu Figure 2. Result Shifi Register 0 Rz Init. loop indea 1 RO Init. loop wunt 2 R5 I Lonp inc.

v~ltte 3 R7 Muimum loop wunt 4 11: RI W AC0 14 5 R3 + B) W Bfl) llcp 6 R4 +fSU Floniag odd ss, 7 RO R5 Inc. loop count 2cp 8 (RO + C) store C(I) 9 Iu Inc. loop index 2cp IO P- 11 : RO !- R7 wnd. branch not quJl where n is the length of the longest functional unit pipeline. An instructton the: ukes I clock periods reserves sugc i of the result shifi regtster et the time it ISSUCS. If the stage already conuins valid control information. then issue is held until the next clock period. end suge i is checked once again. An issuing instruction places wntrol information in the resuh shift regtster.

This control informeoon identilies the fttnc- tional unit that will be supplving the result and the destinrrion register of the result. This control informanon is also marked ‘valid” with e validity bit. Each clock period, the wntrol informanon is shifted down one sugc toward stage one. When it reaches slage one. it IS uti dur- in@ the next clock IO control the result bus so that the functional unit result is placed in rhe wrrect result register. before the floating point add. The integer Jdd will therefore change the praess state before an overflow condition is detected in the flomtog point add. In the event of such an overflow, there is en imprqise interrupt.

Still disregarding precise interrupts, it is possible for J short instruction IO be placed in the result pipeline in suge i when previously issued instructions are in suge j. j > i. This leads to instructiotts ftn- ishing out of the original program sequence. If the instruction et stage j mnttully enwunters en exception condition, the interrupt till be imprecise kuuse the instruction pleeed in suge i will complete Jnd modifv the process stale even though the squentiel archnecture model says i does not begin until j completes. 2.2. Interrupts Prlor to Instruction Issue Before proceeding with the various precise interrupt methods, we discuss interrupts the:

occur prior IO instruction issue sepJn:ely because they are handled the same way by all the methods. In the pipeline implementation of Fig. 1. instructions stay in sequence until the nme they arc issued. Furthermore. the process mu is not modified by an instruction before it issues. This makes precise interrupts a simple maner when an exception condition can be detected prior to issue. Examples of such exceptions are privileged instruction faults and untmplemented instructions. This class also includes exter- nal interrupts which can be checked et the issue stage. If one considers the section of code presented in Eumple 1.

end en initially empty result shift regtster (all the entries invalid). the llo~l- ing point add would be placed in stage 6 while the integer add would be placed in stage 2. The result shift register entries shown in Fig. 2 reflect the state of the result shift regtster after the inuger add issues. Notice that the floating point add entry is in stage 5 since one clock period has passed since it issued. As described above. this SUUJtion Leeds IO instructions finishing out of the original program squence. Example 2 When such an uncrrupt condition is detected, instructton issuing is halted. Then, there is a wan while all previously issued instructions COmpleU. After they have completed.

the process is in a prectse Mu. 293

Стр. 3

To implement prectse mrerrupts with respect IO registers using the above pipeline control structure. fhe control should “reserve” stages i ously reserved by other instructions are rcservtd. and they are loaded with null control informrtton so that they do not affect the process stale. This guarantees that tnstructrons modifying regtsters finish in order. 3.1. Re@sters This leads us to a more complex, but more general solutton. hlrucllOn~ arc allowed to linish OUI of order. but a special buffer called the r@~rUcr bu/?Cr is used to reorder them before they modify the process SWIG. 4.1.

Basic Method There is logic on the result bur that checks for exccptlon condi- tions in ins1ructions as thev complete. If an mstruction contams a non-masked exception condition. then conlrol logic “cancels’ all subsc- quent instructtons comtnp on the result hus so that they do not modif! the process state. The overall orl?antration is shown in Fig. 3a. The reorder buffer. Fig. 3b. is a ctrcular buffer with head and tail pomters. Entrtes between the head and tail are consrdered valid. At instructton issue time the next available reorder buffer enuy. pointed IO by the tail pointer. IS given IO the issuing tnstruction.

The tail pointer value IS used as a tag IO identify the emry in the buffer reserved for the instruction. The tag IS placed in the result shih rcgtstcr along with the other control informa- non. The tail pointer is then incremented. modulo the bttficr sixe. The result shift regtster differs from the one used earlier because there IS a field contamin~ a reorder tap tnstead of a field spccihrinp a destina- Fhmplc 3 For our sample section of code given in Example I. assuming the the result shift regtster is initially empty. such a policy would have the floating point add instructton rescrvc stapes 1 through 6 of the result shih register. When. on the next clock cycle.

the integer add is in the issue register. II would normally issue and reserve stagr 2. However. this is now prohihited front happenmf because stage 2 is alread) reserved. Thus, the tnteper add must wait II the issue stage until stage 2 of the result shih refuster is no longer resened. This would be 5 clock periods aher the issue of the floating point add. A generalization of this method is to determine. if possible. that an tnstruction IS free of exceptton conditions prior to the time it IS com- plete. Only result shih regtster stages that will finish before exceptions are detected need IO be reserved tin addition to the stage that controls the result). tion rcgisler.

I !a&’ REGI!VER Store instructions modify the ponion of process stale that resides in main memory. To implement precise interrupts with respect IO- memory. one solution is to force store insmtaions to wait for the result shift register IO be empty &fore issuing. Alterttati~rly. stores can issue and be held in the load/store pipeline until all preceding instructions arc k~~own to be exception-free. Then the store can be released IO memory. 3.2. Main Memory (8) To implement the second alternative. recall that memory can be treated as a special functtonrl unit. Thus. as with any other instruc- tion, the store can make an entry in the result shift register.

This entry is defined as a dummy store. The dummy store does not cause a result to k placed in the registers. but is used for controlling the memory pipeline. The dummy store ts placed in the result shift regtster so that it will not reach stage I unril the store is known to be exception-free. When the dummy store reaches stage 1. all prewous instructions have completed without exceptions. and a signal is sent to the load/store unit to reluse the store IO memory. If the store itself contams an exception condition. then the s1ore is unallcd. all following load/store instruc- tions are cancelled.

and the store unit signals the pipeline control so that all insrructions issued subsequcnr to the store arc cancelled as they leave the result pipeline. . . . . . . . . . . . . REwmER BLSTER I I STRGE pJ$cc%& 1 UALID 1 TRG 1 To implemcm precise intcrrttpts with rapect IO the program counter. the result shih register is widened IO include a field for the program counter of each rnstruction (see Fig. 2). This field is filled as the tnstrucuon ISSUCS. When an instruction with an exception condition appears at the result bus. us program counter is atailahlc and becomes pan of the saved state. 3.3. Program Gwnar DIRECTION a= HGKKNT 4.

The Reorder BuNer The prtmarv disadvantagr of the abow method is that fast instruc- uons may sometimes get held up at the issue repister even though the! have no dependenctes and would othenviv issuc. In addiuon. the\ block the lssuc rcgistcr while slower instruction% hehind them could conceivahlv tssuc. GGISJLT SnIFT REGISTER (b) Figure 3. (a) Rcordcr Buffer Organization. fb) Reorder Buffer and assoclarcd Result Shih Regtster. 294

Стр. 4