Electrical computers and digital processing systems: processing – Processing control – Processing control for data transfer
Reexamination Certificate
1999-10-01
2003-04-01
Ellis, Richard L. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Processing control for data transfer
C712S218000, C712S219000, C712S244000
Reexamination Certificate
active
06542988
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to processing, tracking, and managing out-of-order and speculative load instructions in a processor that performs precise trap handling. Specifically, a load buffer and an annex share the data retrieved by a load instruction, and share the functionality of tracking the age of a load instruction and invalidating the load instruction if an earlier-issued instruction causes a precise trap before the load instruction has completed its execution through the Trap pipeline stage.
2. Description of the Related Art
In multiple-thread processing, an automated system for various processing applications may handle multiple events or processes concurrently. A single process is termed a thread of control, or “thread”, and is the basic unit of operation of independent dynamic action within the system. A program has at least one thread. A system performing concurrent operations typically has many threads, some of which are transitory and others enduring. Systems that execute among multiple processors allow for true concurrent threads. Single-processor systems can only have illusory concurrent threads, typically attained by time-slicing of processor execution, shared among a plurality of threads.
Some programming languages are particularly designed to support multiple threading. One such language is the Java™ programming language that is advantageously executed using an abstract computing machine, the Java Virtual Machine™. A Java Virtual Machine™ is capable of supporting multiple threads of execution at one time. The multiple threads independently execute Java code that operates on Java values and objects residing in a shared main memory. The multiple threads may be supported using multiple hardware processors, by time-slicing a single hardware processor, or by time-slicing many hardware processors. In 1990 programmers at Sun Microsystems developed a universal programming language, eventually known as “the Java™ programming language”. Java™, Sun, Sun Microsystems and the Sun Logo are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. All SPARC trademarks, including UltraSPARC I and UltraSPARC II, are used under license and are trademarks of SPARC International, Inc. in the United States and other countries. Products bearing SPARC trademarks are based upon an architecture developed by Sun Microsystems, Inc.
SUMMARY OF THE INVENTION
A method for facilitating precise trap handling for out-of-order and speculative load instructions tracks the age of a load instruction. The age of the load instruction is determined by the current stage of its execution in a sequence of pipeline of stages. The age is tracked in a load buffer age indicator in a load buffer until the information specified in the load instruction is retrieved from a data cache or from main memory. The load buffer age indicator includes a first plurality of bits. In one embodiment, each of the first plurality of bits corresponds to one of the A
1
, A
2
, A
3
, and T pipeline stages.
After the information is retrieved, the information and the load instruction are sent to an annex. The bits in the load buffer age indicator are shifted right by one bit and three of the bits are stored in an annex age indicator. The annex age indicator includes a second plurality of bits. In one embodiment, each of the second plurality of stage bits corresponds to one of the A
2
, A
3
, and T pipeline stages.
The method determines when a precise trap has occurred. When a precise trap has occurred, it is determined whether the load instruction was issued before the trapping instruction. Whether the load instruction was issued before the trapping instruction is determined by examining the load buffer age indicator if the data specified in the load instruction has not been retrieved, and by examining the annex age indicator if the data has been received. If the appropriate age indicator indicates that the trapping instruction trapped before the load instruction completed its execution through all pipeline stages, then the load instruction is either the same age or younger than the trapping instruction, and the load instruction is invalidated. In one embodiment, the age of the load instruction is determined by checking whether the appropriate age indicator contains a non-zero value. If the value is non-zero, the load instruction is invalidated upon the occurrence of a precise trap. Invalidation is accomplished by resetting a valid bit in the annex, if the load instruction has been sent to the annex. Otherwise, the invalidation is accomplished by resetting a valid bit associated with the load instruction in the load buffer. Invalidation effectively cancels the load instruction.
Load data—the data specified in the load instruction, is not available for bypass to other functional units until it has been sent to the annex.
In one embodiment a processor is configured to perform the method for precise trap handling for out-of-order and speculative load instructions described above. The processor includes a main memory and a plurality of processing units. It keeps track of the age of load instructions in a shared scheme that includes a load buffer and a load annex. All precise exceptions are detected in a T phase of a load pipeline. Data and control information concerning load operations “that hit in the cache” are staged in a load annex during the A
2
, A
3
, and T pipeline stages until all exceptions in the same, or earlier, instruction packet are detected. Data and control information from all other load instructions is staged in the load annex after the load data is retrieved. If an exception occurs, any load in the same instruction packet as the instruction causing the exception is canceled. Any load instructions that are “younger” than the instruction that caused the exception are also canceled. The age of load instructions is determined by tracking the pipe stages of the instruction. When a trap occurs, any load instruction with a non-zero age indicator is canceled.
REFERENCES:
patent: 4893233 (1990-01-01), Denman et al.
patent: 5689653 (1997-11-01), Karp et al.
patent: 5781790 (1998-07-01), Abramson et al.
patent: 5903918 (1999-05-01), Bauman et al.
patent: 5905881 (1999-05-01), Tran et al.
patent: 5987598 (1999-11-01), Levine et al.
patent: 6336168 (2002-01-01), Frederick et al.
patent: 2001/0034827 (2001-10-01), Mukherjee et al.
patent: WO 00/33176 (2000-06-01), None
patent: WO 0125903 (2001-04-01), None
Hennessy and Patterson, Computer Organization & Design The Hardware/Software Interface, 1998, Morgan Kaufmann Publishers, Inc., p. 509.
Chan Jeffrey Meng Wah
Pan Biyu
Sudharsanan Subramania
Tremblay Marc
Yeluri Sharada
Ellis Richard L.
Meonske Tonia
LandOfFree
Sending both a load instruction and retrieved data from a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Sending both a load instruction and retrieved data from a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sending both a load instruction and retrieved data from a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3109534