Control of Processor Pipeline Movement Through Replay Queue and Pointer Backup

1. Field of the Invention

This invention relates generally to pipelined processors, and more particularly, to a back end replay mechanism for a processor pipeline.

2. Description of the Related Art

Computers and many other types of machines are engineered around a "processor." A processor is an integrated circuit that executes programmed instructions stored in the machine's memory. There are many types of processors and there are several ways to categorize them. For instance, one may categorize processors by their intended application, such as microprocessors, digital signal processors ("DSPs"), or controllers. One may also categorize processors by the complexity of their instruction sets, such as reduced instruction set computing ("RISC") processors and complex instruction set computing ("CISC") processors. The operational characteristics on which these categorizations are based define a processor and are collectively referred to as the processor's architecture. More particularly, an architecture is a specification defining the interface between the processor's hardware and the processor's software.

One aspect of a processor's architecture is whether it executes instructions sequentially or out of order. Historically, processors executed one instruction at a time in a sequence. A program written in a high level language was compiled into object code consisting of many individual instructions for handling data. The instructions might tell the processor to load or store certain data from memory, to move data from one location to another, or any one of a number of data manipulations. The instructions would be fetched from memory, decoded, and executed in the sequence in which they were stored. This is known as the "sequential programming model." Out of order execution involves executing instructions in some order different from the order in which they are presented by the program, i.e., out of order or non-sequentially.

The sequential programming model creates what are known as "data dependencies" and "control dependencies." For instance, if one uses the variable x to calculate a result, one needs to know the value of x and that value might depend on results from previously executed instructions. Similarly, a group of instructions might contain two alternative subsets of instructions, only one of which will be executed, depending on some specified condition. Thus, the result of executing the group of instructions will depend on whether a branch is executed. Even out of order execution follows this sequential programming model, and it therefore also creates data and control dependencies.

A second aspect of a processor's architecture is whether it "pipelines" instructions. The processor fetches instructions from memory and feeds them into one end of the pipeline. The pipeline is made of several "stages," each stage performing some function necessary or desirable to process instructions before passing the instruction to the next stage. For instance, one stage might fetch an instruction, the next stage might decode the fetched instruction, and the next stage might execute the decoded instruction. Each stage of the pipeline typically moves the instruction closer to completion.

Some processor pipelines process selected instructions "speculatively." Exemplary speculative execution techniques include, but are not limited to, advanced loads, branch prediction, and predicate prediction. Speculative execution means that instructions are fetched and executed before resolving pertinent control dependencies. Speculative execution requires a prediction as to what instructions are needed depending on whether a branch is taken, executing fetched instructions, and then verifying the execution and prediction. The pipeline executes a series of instructions and, in the course of doing so, makes certain predictions about how control dependencies will be resolved. For instance, if two instructions are to be alternatively executed depending on the value of some quantity, then the pipeline has to guess what that value will be or which instruction will be executed. The pipeline then predicts the next instruction to be executed and fetches the predicted instruction before the previous instruction is actually executed.

A pipeline therefore has the tremendous advantage that, while one part of the pipeline is working on a first instruction, a second part of the pipeline can be working on a second instruction. Thus, more than one instruction can be processed at a time, thereby increasing the rate at which instructions can be executed in a given time period. This, in turn, increases the processor throughput.

Verification is one of the pipeline's most significant challenges. At the end of the pipeline, the results from executed instructions are temporarily stored in a buffer until all their data and control dependencies have been actually resolved. The pipeline then checks to see whether any problems occurred. If there are no problems, then the executed instructions are "retired." This is sometimes referred to as "commitment to an architectural state" or "retirement to a committed state." Retirement or commitment signals that all dependencies have been correctly resolved and that the execution results are finalized.

However, no pipeline correctly predicts all eventualities and, when problems occur, they must be repaired. Problems can typically be traced to:

(1) executing an instruction that should not have been executed;

(2) omitting an instruction that should have been executed; or

(3) executing an instruction with incorrect data.

The effects of such problems on subsequent execution of instructions must also be repaired. Once the problem and its effects have been repaired, the pipeline can then process the execution stream correctly.

Most pipelined processors "stall" the pipeline upon detecting a problem. As discussed above, the pipeline is usually divided into several stages. Progress through the stages is governed by a number of latches enabled by a signal generated by a particular part of the pipeline. If a problem is detected, the latches are disabled and the pipeline "stalls" such that the instructions can no longer be transferred into the next stage. The problem and its effects are then repaired, the latches are re-enabled, and the pipeline resumes.

Design considerations now counsel against stall pipelines in some circumstances. A stall pipeline must receive signals from different parts of the pipeline, determine whether the pipeline must stall, and then broadcast the appropriate signal to enable or stall pipeline progression. This determination takes a certain amount of time. New generations of processors are now operating at frequencies that make that amount of time a significant design constraint.

Some processor pipelines "replay" in addition to stalling. Replay is the reexecution of instructions upon detecting an execution problem in the retirement of speculative results. The speculative results are not retired, i.e., used to update the architectural state of the processor, but arc instead ignored. The pipeline corrects the problem and then re-executes the instructions. The new results are then checked for problems and retired.

One such processor is the Alpha 21164 microprocessor, commercially available from Digital Equipment Corporation. The Alpha 21164 stalls only the first three stages of the pipeline. If a problem occurs after the third stage, the Alpha 21164 replays the entire pipeline beginning with the repaired problem instead of stalling the problem in midstream. However, replaying the entire pipeline regardless of the problem can be expensive in terms of time. The Alpha 21164 therefore combines expensive stalling with complex decision-making circuitry necessary to determine when to replay. Also, when the Alpha 21164 replays, it replays the entire pipeline line even though the problem may be localized at some point in the pipeline.

The demand for faster, more powerful processors continually outstrips present technology. The demand pressures all aspects of processor architecture design to become faster, which demand directly implicates pipeline throughput. Thus, there is a need for a new technique for correcting execution problems in a pipelined process.

The present invention is directed to overcoming, or at least reducing the effects of, one or more of the problems set forth above.

The invention, in one embodiment, is a processor pipeline. The pipeline includes a front end, a back end, and a queue between the front end and the back end. The queue is capable of storing an intermediate state of the processor from which the back end may be replayed.

The invention, in another embodiment, is a micro-op queue storing an intermediate state of a pipeline in a processor from which a back end replay can be instituted.

Other objects and advantages of the invention will become apparent upon reading the following detailed description and upon reference to the drawings in which:

FIG. 1 conceptually illustrates an embodiment of a pipeline constructed and operating according to the present invention;

FIG. 2 conceptually illustrates one particular variation on the pipeline of FIG. 1;

FIG. 3A depicts a first embodiment of a queue between the front and back ends of the pipeline illustrated in FIG. 1;

FIG. 3B depicts a second embodiment of a queue between the front and back ends of the pipeline illustrated in FIG. 1; and

FIG. 4 illustrates an embodiment of a method for pipelining instructions in a processor according to the present invention.

While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof have been shown by way of example in the drawings and are herein described in detail. It should be understood, however, that the description herein of specific embodiments is not intended to limit the invention to the particular forms disclosed, but on the contrary, the intention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention as defined by the appended claims.

Illustrative embodiments of the invention are described below. In the interest of clarity, not all features of an actual implementation are described in this specification. It will of course be appreciated that in the development of any such actual embodiment, numerous implementation-specific decisions must be made to achieve the developers' specific goals, such as compliance with system-related and business-related constraints, which will vary from one implementation to another. Moreover, it will be appreciated that such a development effort, even if complex and time-consuming, would be a routine undertaking for those of ordinary skill in the art having the benefit of this disclosure.

FIG. 1 conceptually illustrates in an exploded view one particular embodiment of a processor pipeline 10 constructed and operated in accordance with the present invention. The pipeline 10 generally comprises a front end 12, a back end 14, and a queue 15 between the front end 12 and the back end 14. The queue 15 is capable of storing an intermediate state of the processor (not shown) from which the back end 14 may be replayed per a request transmitted over a channel 17 as set forth below.

In some embodiments, the queue 15 may be considered a part of the back end 14 rather than separate from the back end 14. However, for the sake of clarity and to further this disclosure of the invention claimed below, the queue 15 and the back end 14 shall be discussed as separate parts of the pipeline 10. Nevertheless, the invention is not so limited as the back end 14 may incorporate the queue 15 in some alternative embodiments.

The front end 12 fetches instructions, generates "micro-ops" therefrom, and prepares the micro-ops for execution. A micro-op is generally a single transaction that may be executed by a single execution unit (not shown) of the processor in a single clock cycle. An instruction is typically a single a micro-op. However, in some embodiments, some more complicated instructions might comprise three or more micro-ops. Thus, there is not necessarily a one-to-one correspondence between instructions and micro-ops. The front end 12 in the embodiment illustrated generates micro-ops from the instructions and enters them into the queue 15 for execution. The generation of micro-ops from instructions may also be referred to as "expanding" or "decoding" the instructions. The back end 14 executes the instructions as prepared by the front end 12 and stored in the queue 15.

The queue 15 is functionally positioned between the front end 12 and the back end 14. The front end 12 enters instructions in the form of micro-ops into the queue 15. The queued micro-ops define an intermediate state of the machine from which the back end 14 of the pipeline 10 can be replayed as discussed more fully below.

Turning now to FIG. 2, the front end 12 and the back end 14 generally include one or more "stages" of processing. The front end 12 may be of any suitable design known to the art. "Suitable" in this context means that the particular front end 12 fetches instructions from memory, expands them into micro-ops, and enters them into the queue 15 for execution by the back end 14. Other features may be desirable in various alternative embodiments depending on the particular implementation. However, a front end 12 will generally include at least a fetch stage 16 and an expand, or decode, stage 18.

The back end 14 of the embodiment illustrated in FIG. 1, as shown in FIG. 2, also includes several stages of processing. As with the front end 12, many alternative embodiments may be implemented and particular features may be desirable depending on the particular implementation. However, the back end 14 will generally include an execution stage 30 and a retirement stage 32. The back end 14 reads the instructions from the queue 15, executes the micro-ops, and retires executed instructions. Execution problems are checked for and detected in the retirement stage.

The stages 16, 18, 30, and 32 of the pipeline 10 above are merely representative and are neither exclusive nor exhaustive of stages that might be present in various alternative embodiments. Further, as those in the art will appreciate, the demarcation of stages and functions in a processor pipeline are not necessarily so crisp or distinct as might appear from FIG. 2. The pipeline 10 in FIG. 1 is conceptualized for the sake of clarity in explaining the present invention. Thus, the precise structure of the front end 12 and the back end 14 in terms of stages is not pertinent to the practice of the invention.

FIG. 3A illustrates one particular embodiment 35 of the queue 15 in FIG. 1. The queue 35 must be sufficiently wide to feed the resources of the back end 14. For instance, in one particular embodiment, the pipeline 10 includes N arithmetic logic units ("ALUs") executing instructions in parallel and the queue 35 for that particular embodiment is N columns wide. This particular embodiment is also superscalar, and so it is sufficiently wide to provide micro-ops to the N ALUs at every clock cycle.

Although the queue 35 includes one column per ALU, this structure is not necessary to the practice of the invention and other suitable structures may be employed. For instance, some embodiments might choose to implement N queues 35, each being one ALU wide. The queue 35 is a master queue in the sense that it queues the micro-ops for each arithmetic logic unit ("ALU") in the processor.

The queue 35 is also sufficiently long that it can store the micro-ops generated for each unretired instruction in the back end 14. The micro-ops are not deallocated from the queue 35 until the instructions from which they are generated are retired. Thus, the queue 35 stores the intermediate state of the pipeline 10. The state is "intermediate" in that it represents the instructions in a state subsequent to their initial state, i.e., unexecuted, and prior to their final state, i.e., retired. In the event a problem is detected in retirement, the back end 14 can be replayed from the intermediate state stored in the queue 35 without having to replay the entire pipeline 10.

The queue 35 in this particular embodiment includes a head pointer 34. a tail pointer 36, and a replay pointer 38. The head pointer 34 points to the "head" of the queue 35 where new micro-ops are entered into the queue 35. The tail pointer 36 points to the next row of micro-ops to enter the back end 14 of the pipeline 10 for execution. The replay pointer 38 points to the first row of micro-ops in the replay when a replay is requested. The replay pointer 38 is set to the oldest, unretired micro-op in the queue 35. To initiate a back end replay, the pipeline 10 copies the replay pointer 38 into the tail pointer 36. The copy repositions the tail pointer 36 to the oldest unretired micro-op in the queue 35 such that it becomes the next micro-op read out of the queue 35.

Each of the pointers 34, 36, and 38 is modulo incremented so that they wraparound to form a circular queue. As new micro-ops are written to the queue 35, the head pointer 34 is incremented. Similarly, as micro-ops are read from the queue 35, the tail pointer 36 is incremented. Finally, as each micro-op is retired, the replay pointer 38 is incremented. Old, retired micro-ops are written over as the pointers 34, 36, and 38 are incremented so that old entries of retired micro-ops in the queue 35 are reused. When one of the pointers 34, 36, or 38 reaches the last entry in the queue 35 and is then advanced, it wraps around to the first entry in the queue 35. The tail pointer 36 typically trails the head pointer 34 and the replay pointer 38 trails the tail pointer 36 as shown in FIG. 3A, although this is not necessarily the case as is discussed immediately below.

The queue 35 is empty when the head pointer 34 equals the tail pointer 36. The queue 35 in this particular embodiment always reserves one empty row for detecting a full queue condition. Thus, when the head pointer 34 is one less than the replay pointer 38, the queue 35 is full. In one particular embodiment, the full pipeline 10 is replayed when the queue 35 becomes full. Alternative embodiments might instead append an extra bit to each of the head pointer 34 and the replay pointer 38. If the head pointer 34 and the replay pointer 38 are equal, and if the appended bits are different, then the queue 35 is full. If the head pointer 34 and the replay pointer 38 are equal, and if the appended bits are the same, then the queue 35 is empty.

FIG. 3B illustrates a second embodiment 35' of the queue 15 in FIG. 2. The queue 35' is implemented with a shift register and uses only two pointers. The queue 35' physically shifts data down as micro-ops arc retired. The oldest, unretired micro-op is therefore always at the bottom of the shift register, thereby effectively fixing the replay pointer 38 in the embodiment of FIG. 3A. Otherwise, the embodiment 35' of FIG. 3B functions similarly to the embodiment 35 of FIG. 3A.

Returning to FIG. 1, progress through the pipeline 10 is controlled by flip-flops (not shown) and/or staged domino circuits (also not shown). In the embodiment of FIG. 1, the flip-flops and/or staged domino circuits are free running as the pipeline 10 does not stall. Instead of stalling when a problem is detected, the pipeline 10 is either flushed or drained and a replay is instituted.

FIG. 4 illustrates one embodiment of a process for pipelining instructions in a processor that may be identified as "back end replay." The embodiment of FIG. 4 employs a pipeline such as the pipeline 10 of FIG. 1 and generally comprises queuing a plurality of micro-ops, executing the queued micro-ops, and then committing the executed instructions to an architectural state, as described below. One aspect of the invention lies in the queuing of the micro-ops until the instructions from which they are generated are retired, thereby storing an intermediate state of the pipeline. A second aspect of the invention lies in replaying the back end 14 of the pipeline 10 upon detection of a problem.

Returning to FIG. 1, the micro-ops generated from the instructions are entered into the queue 15, e.g., the queue 35 of FIG. 2, as described above and enter the back end 14 from the queue 15. The back end 14 processes the micro-ops and makes predictions to resolve data and control dependencies when necessary. The micro-ops are processed on the assumption that all predictions correctly resolve the underlying dependencies. Once the queued micro-ops are executed, they are temporarily stored to await commitment to an architectural state.

As mentioned earlier, committing the instructions to the architectural state includes checking for problems in execution. Problem checking may be performed in any suitable manner known to the art. As will be appreciated by those in the art, some amount of problem checking is implementation specific. The precise manner in which problems are checked is not material to the present invention. If a problem is detected, the uncommitted execution results are squashed, or ignored. The pipeline 10 is then flushed or drained, i.e., the pipeline 10 is either reset or all instructions in the back end 14 are allowed to complete execution and the buffers are reset.

Many types of problems may be detected. Exemplary problems in one particular embodiment include:

(1) a cache miss;

(2) a branch or predicate misprediction;

(3) an exception, such as a page fault or an illegal instruction;

(4) a translation look-aside buffer ("TLB") miss; and

(5) certain data dependencies, such as load.backslash.store conflicts.

In one particular embodiment, back end replay is, as a general rule, instituted as a result of memory access problems. However, the invention is not so limited. Also, some problems may not result in back end replay. These problems may be handled in other ways in some embodiments. These variations are all implementation specific.

Once a problem is detected, the problem and its effects must be repaired. Again, the repair will be implementation specific depending on, among other things, the nature of the problem. For instance, if the problem is:

(a) a predicate misprediction, the correct predicate must be inserted for the replay; or

(b) a load store conflict, the store must be completed, the cache updated, and then the correct value loaded.

Problem repair can be quickly performed because the queue 15 has stored the intermediate state of the pipeline 10. Thus, the problem can be identified and corrected in the queue 15 and the execution stream replayed. The effects of the problem will then necessarily be corrected in the replay.

In accord with the present invention, the back end 14 is replayed from the queued micro-ops, i.e., the stored intermediate state, if a problem is detected. The pipeline 10 is either flushed or drained and the uncommitted results squashed. The pipeline 10 then requests a replay over the channel 17. Assuming the queue 15 is implemented using the embodiment of FIG. 3A, the pipeline copies the replay pointer 38 into the tail pointer 36. Execution of the queued micro-ops then commences as described above.

In one particular embodiment, the pipeline 10 requests a partial replay as indicated by a mask. The mask (not shown) includes a series of 1s and 0s indicating which instructions being checked contain a problem and need to be replayed. In an embodiment having a queue 15 is N ALUs wide, the mask includes N 1s and 0s, one for each ALU. The mask is an index, or key, back into the queue 15 identifying the point in the execution stream where the problem occurred. The retirement logic (not shown) transmits the mask and the replay request to the queue 15. The tail pointer of the queue 15 is then repositioned as discussed above and the replay commences according to the mask, which is merged by the queue 15 with the queued micro-ops.

The results of the re-execution are temporarily buffered and checked for problems. Although the problem necessitating the replay should not reoccur, other problems might arise. If a new problem is detected, then a replay is once again requested as set forth above. The pipeline 10 will eventually produce a problem-free set of uncommitted results that can then be retired. Since the original problem should not reoccur, each iteration of the back end 14 progresses toward retirement of the instructions from which the micro-ops were generated. Techniques for predicting control and data dependencies are sophisticated and sufficiently accurate that replay is the exception rather than the rule.

Thus, the present invention increases the time-efficiency of a pipeline by replaying the back end 14 rather than stalling or replaying the entire pipeline 10. Correcting problems by stalling the pipeline 10 might cost twenty clock cycles whereas back end replay as described above might cost as few as ten cycles. The practice of the invention might therefore reduce the amount of time spent correcting problems by half in some circumstances.

The particular embodiments disclosed above are illustrative only, as the invention may be modified and practiced in different but equivalent manners apparent to those skilled in the art having the benefit of the teachings herein. Furthermore, no limitations are intended to the details of construction or design herein shown, other than as described in the claims below. It is therefore evident that the particular embodiments disclosed above may be altered or modified and all such variations are considered within the scope and spirit of the invention. Accordingly, the protection sought herein is as set forth in the claims below.