Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or...
Reexamination Certificate
1998-12-23
2001-10-30
Treat, William M. (Department: 2183)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
C712S214000, C712S215000, C712S218000, C712S228000
Reexamination Certificate
active
06311266
ABSTRACT:
TECHNICAL FIELD
This invention relates to execution of instruction sets in a computer, and more particularly, to a method and apparatus for executing certain instruction sets while waiting to execute other instruction sets.
BACKGROUND OF THE INVENTION
Computers operate by executing instructions. The speed at which a computer can execute an instruction set determines how rapidly the computer can execute its operations through a sequence of steps. At present, computers advance by executing an instruction after which the subsequent instruction of the set of the operating code is executed. This has the disadvantage that if a particular instruction set requires significant time for execution, that other instruction sets cannot be executed at the same time.
SUMMARY OF THE INVENTION
According to principles of the present invention, a computer system is organized to permit execution of multiple instructions in a rapid sequence while ensuring that no instruction is executed until the proper time.
Each instruction is a part of a set of instructions. Each instruction within the set has associated with it a code which provides information regarding the relationship of its execution to the execution of other instructions in the set. The code includes a look-ahead value and a counter check. The look-ahead value provides the number of instructions which can be executed after the current instruction which do not rely on the completion of the current instruction in order to perform the operations specified therein. According to the invention, the current instruction begins execution and prior to its completion of execution, the next instruction may also begin execution. If the next instruction requires a value from the prior instruction, such as data from memory, then the next instruction cannot begin its action until the prior instruction has completed its execution. On the other hand, the next instruction may perform tasks which do not rely on the completion of the immediate prior instruction. It may, for example, perform an arithmetic operation on numbers already available and not rely on data provided by the previous instruction. Therefore, the subsequent instruction in the set can start execution and, in fact, can complete its execution prior to the previous instruction having completed its execution. The look-ahead code provides the number of instructions beyond the current instruction which can be executed before it has completed being executed.
A counter check code checks the value of a counter associated with the register in which the memory instruction is stored. If the counter is 0, then the instruction set has permission to execute and proceed. On the other hand, if the counter value is not 0, then the instruction does not have permission to execute and waits until its counter is 0 before it executes.
The look-ahead value of an instruction is used to increment the counter associated with the register at the location of the number of instruction sets ahead of the value plus 1. Thus, if the look-ahead value were 3, this means that the next three instructions can be executed before the current instruction has completed execution. However, the fourth instruction ahead of it cannot be assured of being cleared for execution until the current instruction is executed. Accordingly, the look-ahead value is used to increment a counter associated with the register four instructions ahead of the current instruction, the value 4 being n+1 where n is the look-ahead value. When the current instruction completes its execution, it decrements the same counter by 1. Therefore, when the time comes for the execution of the instruction stored in the register associated with that counter, the counter value will have been decremented by 1 and, if the count is 0, the instruction will be executed.
The present invention provides the advantage that instructions can be executed rapidly, with the start of execution of subsequent instructions beginning before a prior instruction has been completely executed. This significantly increases the speed of operation of the computer. A further advantage is provided that in the event subsequent instructions do not rely on the completion of a prior instruction that may execute completely while a prior instruction is still in operation. On the other hand, in the event a particular instruction relies on the completion of a prior instruction before execution, a method and system are provided to delay execution of the current instruction until the system is ensured that all related prior instructions have been completed. Therefore, the reliability of the system is enhanced while still significantly increasing the speed of operation.
REFERENCES:
patent: 5555384 (1996-09-01), Roberts et al.
patent: 5712996 (1998-01-01), Schepers
patent: 5933627 (1999-08-01), Parady
patent: 6105051 (2000-08-01), Borkenhagen et al.
patent: 6216220 (2001-04-01), Hwang
patent: 6223208 (2001-04-01), Kiefer et al.
patent: 6233599 (2001-05-01), Nation et al.
Tullsen et al., “Simultaneous Multithreading: Maximizing On-Chip Parallelism,”Proceedings of the 22nd International Symposium on Computer Architecture, pp. 392-403, IEEE, Jun. 22-24, 1995.*
Alverson et al., “Exploiting Heterogeneous Parallelism on a Multithreaded Multiprocessor,”Proceedings of the 1992 International Conference on Supercomputing, ACM, pp. 188-197, Jul. 19-24, 1992.*
Anderson et al., “The Performance Implications of Thread Management Alternatives for Shared-Memory Multiprocessors,”IEEE Transactions on Computers, pp. 1631-1644, vol. 38, iss. 12, Dec. 1989.*
Superscalar Microprocessor Design, Englewood Cliffs, NJ, Jan. 1, 1991, Chap. 6, “Register Dataflow,” pp. 103-126.
Gail Alverson et al., “Tera Hardware-Software Corporation”, inProceedings of Supercomputing, Nov. 1997.
Gail Alverson et al., “Scheduling on the Tera MTA” inJob Scheduling Strategies for Parallel Processing, 949:of Lecture Notes in Computer Science, Springer-Verlag, 1995.
Robert Alverson et al., “The Tera Computer System”, inProceedings of 1990 ACM International Conference on Supercomputing,pp. 1-6, Jun. 1990.
D.H. Bailey et al., “The NAS Parallel Benchmarks—Summary and Preliminary Results”, inProceeding of Supercomputing '91, pp. 158-165, Nov. 1991.
David Callahan, Recognizing and Parallelizing Bounded Recurrences, inLanguages and Compilers for Parallel Computing, 589:of Lecture Notes in Computer Science, pp. 169-185, Springer-Verlag, 1992.
David Callahan et al., “Improving Register Allocation for Subscripted Variables”, inProceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, SIGPLAN Notices, 25(6):53-65, Jun. 1990.
David Callahan and Burton Smith, “A Future-based Parallel Language For a General-purpose Highly-parallel Computer”, inLanguages and Compilers for Parallel Computing, pp. 95-113, 1990.
Mark Linton, “The Evolution of Dbx”, inUSENIX Summer Conference, 1990.
Roy F. Touzeau, “A Fortran Compiler for the FPS-164 Scientific Computer”, inProceedings of the ACM SIGPLAN '84 Symposiun on Compiler Construction, SIGPLAN Notices 19(6):48-57, Jun. 1984.
Alverson Robert L.
Smith Burton J.
Cray Inc.
Seed IP Law Group PLLC
Treat William M.
LandOfFree
Instruction look-ahead system and hardware does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Instruction look-ahead system and hardware, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Instruction look-ahead system and hardware will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2603104