Electrical computers and digital processing systems: processing – Instruction issuing
Reexamination Certificate
2000-01-31
2004-05-18
Chan, Eddie (Department: 2183)
Electrical computers and digital processing systems: processing
Instruction issuing
C712S217000
Reexamination Certificate
active
06738896
ABSTRACT:
BACKGROUND OF THE INVENTION
It is well known that computer operating speed benefits from providing queues that hold software instructions in the correct order as issued from the main processor, rather than completing a single issued operation instruction and then returning to the main processor to obtain the next instruction. One benefit of using queues to store the instructions temporarily while waiting for an opportunity to execute the instruction is that the main processor may issue a group of instructions to the queue, and continue operating on other portions of the overall program without having to wait for the results of the instructions to arrive. Another benefit of using queues is that the main processor may have separate queues for different types of functions and thus send out parallel series of instructions that result in increased overall system speed. Typical types of queues may include memory load queues, store to memory queues, and arithmetic operation queues.
Typically, most processors issue instructions in the same order that they are specified in the software program. This is because the order of operations is very important in a software program, and issuing instructions out of the proper order may likely result in an incorrect result. Therefore typically, the instruction queue receives the instructions in the same order as issued by the main processor, and presents them for execution in that same order. An example of the operation of a queue might be a first in first out (i.e., FIFO) system where the instruction is sent to the first available queue location in a series of queue locations. As soon as the prior queue location becomes available, the instruction is moved up, and so on until the instruction reaches the first queue memory location and is executed as soon as the needed resource is available. Note that not all queues operate in the same fashion as this illustrative example, but some method of maintaining the order of instruction issuance is needed.
The queues discussed above are a form of memory, and like any memory resource, they have a finite size or storage capacity. Making a queue larger results in greater ability to buffer the issuance of instructions from the main processor, and therefore increases the overall system operating speed in many circumstances, but at the expense of increased system cost and size. However, the main processor must know when the queue is full, i.e., when the execution of the instructions is not keeping pace with the main processor s ability to issue new instructions, or else there will be issued instructions that overflow the queue's memory capacity and become lost. A lost instruction is likely to result in an erroneous program output and consequent system failure.
Since historically the processors issued instructions in the same order as the instructions occur in the program, and the order of instructions is the same in the queues, then knowing when a queue has reached its maximum capacity, i.e., the queue is full, is important. Since the operation of a queue necessarily requires that it be known whether or not a particular memory location has a current instruction resident, then detecting whether or not the queue is full is straight forward in the case of sequentially ordered and issued instructions since all previous queue memory locations will be occupied. For example, in the illustrative FIFO case, the main processor will know to stop issuing instructions to a queue that has the last queue location filled. Note again that other queue types operate differently from the illustrative example, but in all types of queues the main processor may determine whether or not a particular queue is full.
It would improve the overall computing system speed of operation if the instructions in a queue could be executed out of the sequential order in which they were issued, since the resource (for example a particular memory location) needed for the next instruction in the normal execution order may not be available, while the resource needed for an instruction that is five memory locations behind the next instruction may be available right now. It improves the efficiency of the system to use available resources and not wait for the currently needed resource to become available. However, this requires that certain types of instructions be allowed to be executed out of the issuance order, and creates a problem with the main processor not being able to easily determine when a particular queue is full. This is because when a particular instruction, for example a memory reference instruction, issues, not all of the other memory reference instructions prior to it in the program order need necessarily have already been issued.
It would be a benefit to the overall computer system speed of operation to provide a method and an apparatus to allow random insertion of instructions into a queue while still allowing the main processor to know when the instruction queue is full.
SUMMARY OF THE INVENTION
A method and an apparatus for allowing random insertion of certain types of computer instructions into a queue consists of assigning each program step (i.e., instruction) of the certain type a unique number, e.g., a load store number (LSN), and issuing each program step to the appropriate execution queue (for example a load queue). The program step is assigned at a random time to a specific numbered location in the selected execution queue based upon an ascending INUM order of the program steps in the particular execution queue. A modulus value is calculated for the instruction based upon its numbered location in the particular queue, with the divisor of the modulus equal to the number of the location in the particular queue, and a status bit is set based upon the product of the modulus. A valid bit is set for the program step until the execution of the step is completed. The next program step with the same modulus that is issued is compared to the value of the previous instruction's valid bit and to the status bit. The queue is determined to be full and not capable of accepting further issued instructions based upon the compared values of the valid and status bits. The program number (INUM) and the location in the selected execution queue is recorded in a load store if the selected numbered location is empty, and a memory full flag is transmitted to the issue queue if the selected location is occupied.
In general, the queue entries are pre-allocated for each memory reference instruction in its respective queue at the time that the instructions are fetched from the main processor program store. Since the instructions are fetched in the same order as the program order, then the queue entries are pre-allocated in program order. A special queue, known as the random access queue, is used for instructions that may be executed in random order, for example, memory reference instructions. Note that the random access queue is not the same queue as the instruction queue.
A load store number (i.e., LSN) table maintains a mapping between the sequential number of an instruction (INUM) in the program order and its location in the queue, known as the queue entry number. Separate numberings are maintained for loads and saves, also maintained is one extra bit of information beyond what is required to describe the queue location (queue entry number). This extra bit is known as the modulus status bit (MSB) and is used to determine the execution status of any particular instruction in the queue. As instructions issue, their INUM is used to access the proper pre-allocated queue location using the LSN and the extra MSB bit.
Next the instruction is presented to it's respective queue entry. The instruction to be executed is compared to its respective memory queue entry, and hence the MSB bit of the issuing instruction is compared against the MSB value stored in that queue entry. If the MSB values are the same in the issuing instruction and queue entry, and the queue entry is currently in an INVALID state, then that instruction may be allowed to write in
Keller James
Meyer Derrick R.
Webb, Jr. David Arthur James
Chan Eddie
Harkness Charles
Hewlett--Packard Development Company, L.P.
LandOfFree
Method and apparatus for determining availability of a queue... 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 determining availability of a queue..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining availability of a queue... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3248242