Electrical computers and digital processing systems: processing – Processing control – Generating next microinstruction address
Reexamination Certificate
1995-04-05
2001-02-06
Maung, Zarni (Department: 2758)
Electrical computers and digital processing systems: processing
Processing control
Generating next microinstruction address
C712S233000
Reexamination Certificate
active
06185674
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The invention relates to computer processor units and, more particularly, to reconstructing the address of the next instruction to be completed in pipelined computer processing units.
2. Description of the Prior Art
Pipelined processors divide the processing of instructions into a number of stages such that several instructions can be processed simultaneously, thereby providing improved efficiency and performance with respect to conventional non-pipelined processors. More recently superscalar processors, such as the Pentium processor from Intel and the PowerPC 601, 603, 604 and 620 processors from Apple/IBM/Motorola have been developed that utilize multiple instruction pipelines to provide the ability to execute multiple instructions in a single clock cycle. Thus, superscalar and pipelined microprocessors process a large number of instructions concurrently.
As shown in
FIG. 1
, the structure of these devices typically may be broken down into four stages. In the fetch stage, a copy of one or more instructions are obtained from memory and placed into an input queue. In the dispatch stage, one or more instructions are read from the input queue and examined to initialize the control signals that are required for execution, and then dispatched to the execution unit(s). In the execution stage, when resources are available, one or more instructions are executed. Finally, in the completion stage, the results produced by the execution unit(s) are committed to the architected registers.
The instructions are typically fetched and dispatched in order, but may be executed out of order. In order to give the illusion of a traditional sequential machine, the instructions are finally reordered at completion time. Such an architecture has the advantage of decoupling instruction fetch from execution, thus providing higher performance.
In addition, branch prediction and prefetch control logic may be utilized to fetch, dispatch and execute instructions speculatively. However, these speculative instructions are not completed until the speculative conditions have been resolved. Such speculative fetching and execution also improves system performance in most applications.
Microprocessors that incorporate the structure of
FIG. 1
typically include a program counter that stores the memory address of the last instruction completed by the completion stage such that the microprocessor can service interrupts and/or program exceptions. Upon experiencing an interrupt/exception, the current address of the program counter is saved. The program counter is then initialized with an address vector corresponding to the interrupt/exception and the instruction pipeline reset for fetching, dispatching, executing and completing the instructions of the interrupt/exception. To return from the interrupt/exception, the stored address value (or the next sequential address following the stored address value) is loaded into the program counter and the instruction pipeline is reset for fetching, dispatching, executing and completing the instruction sequence that the microprocessor left to service the interrupt/exception.
Conventionally, the program counter is implemented by saving the full address of each instruction in the fetch stage, and writing the full address+1 or target address to the program counter upon completing the instruction. However, this implementation may be unsuitable for use in superscalar and deeply pipelined microprocessors that process a large number of instructions concurrently. In these applications, storing the full address of each instruction requires that a large amount of information be stored, and thus may consume an unacceptable amount of real estate.
It is therefore an object of the present invention to provide a system that utilizes a limited amount of stored information and a small amount of real estate to perform the conventional functions of the program counter, and is thus suitable for use in superscalar and pipelined microprocessors.
SUMMARY OF THE INVENTION
According to the present invention, a computer processing unit is provided that includes an apparatus for generating an address of the next instruction to be completed. The apparatus includes a first table for storing a plurality of entries each corresponding to a dispatched instruction, each entry comprising an identifier that identifies the corresponding instruction and a status bit that indicates if the corresponding instruction is completed; a second table for storing a plurality of entries each corresponding to dispatched branch instructions, each entry comprising the same identifier stored in the first table, a target address of the dispatched branch instruction and a resolution status field that indicates at least if the corresponding branch instruction has been resolved taken or has been resolved not taken; program counter update logic that, in each machine cycle, updates a program counter to store and output the address of the next instruction to be completed according to the entries stored in the first table and the second table.
More specifically, the program counter update logic, in each machine cycle, reads out one or more entries from said first table, and for each entry corresponding to a branch instruction and whose status bit indicates the corresponding branch instruction is completed, accesses the second table with the associated identifier of the entry to determine if a corresponding entry exists in the second table. If the second table includes one corresponding entry whose resolution status field indicates the branch instruction has been resolved taken, the program counter update logic updates the program counter to correspond to the target address of the one entry plus any offset associated with subsequent completed sequential instructions. If the second table includes more than one corresponding entry whose resolution status field indicates the branch instruction has been resolved taken, the program counter update logic updates the program counter to correspond to the target address of one of the corresponding entries plus any offset associated with subsequent completed sequential instructions, wherein said one of the corresponding entries is associated with an instruction latter in program sequence relative to instructions associated with other of the corresponding entries. If the second table does not include at least one corresponding entry whose resolution status field indicates the branch instruction has been resolved taken, the program counter update logic updates the program counter to correspond to the address associated with completed sequential instructions. Moreover, if each of the one or more entries read out from the first table do not correspond to a branch instruction, the program counter update logic updates the program counter to correspond to the address associated with completed sequential instructions.
Because the first and second tables employ efficient identification tags to identify instructions that modify the control flow of the execution pipeline and the target address of such instructions, the computer processing unit of the present invention need not store the full address of each instruction in the execution pipeline to update the program counter as is conventional, and thus saves real estate that may be used for other circuitry.
REFERENCES:
patent: 4679141 (1987-07-01), Pomerene et al.
patent: 4714990 (1987-12-01), Desyllas et al.
patent: 4833599 (1989-05-01), Colwell et al.
patent: 4914582 (1990-04-01), Bryg et al.
patent: 5014240 (1991-05-01), Suzuki
patent: 5093778 (1992-03-01), Favor et al.
patent: 5142634 (1992-08-01), Fite et al.
patent: 5163140 (1992-11-01), Stiles et al.
patent: 5226130 (1993-07-01), Favor et al.
patent: 5430851 (1995-07-01), Hirata et al.
patent: 5454117 (1995-09-01), Puziol et al.
patent: 5461722 (1995-10-01), Goto
patent: 5471597 (1995-11-01), Byers et al.
patent: 5488729 (1996-01-01), Vegesna et al.
patent: 5553255 (1996-09-01), Jain et al.
patent: 5553256 (1996-09-01), Fitterman et al.
patent: 56088
Chan Kin Shing
Chuang Chiao-Mei
Marchioro Alessandro
International Business Machines - Corporation
Maung Zarni
Sbrollini Jay P.
LandOfFree
Method and apparatus for reconstructing the address of the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for reconstructing the address of the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for reconstructing the address of the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2610504