Electrical computers and digital processing systems: processing – Processing architecture – Distributed processing system
Reexamination Certificate
1999-11-01
2003-06-03
Chan, Eddie (Department: 2183)
Electrical computers and digital processing systems: processing
Processing architecture
Distributed processing system
C712S028000, C712S216000, C712S023000, C709S241000, C709S208000
Reexamination Certificate
active
06574725
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention is related to the field of microprocessors and, more particularly, to multithreading in multiprocessors.
2. Description of the Related Art
Computer systems employing multiple processing units hold a promise of economically accommodating performance capabilities that surpass those of current single-processor based systems. Within a multiprocessing environment, rather than concentrating all the processing for an application in a single processor, tasks are divided into groups or “threads” that can be handled by separate processors. The overall processing load is thereby distributed among several processors, and the distributed tasks may be executed simultaneously in parallel. The operating system software divides various portions of the program code into the separately executable threads, and typically assigns a priority level to each thread.
Superscalar microprocessors achieve high performance by executing multiple instructions per clock cycle and by choosing the shortest possible clock cycle consistent with the design. As used herein, the term “clock cycle” refers to an interval of time accorded to various stages of an instruction processing pipeline within the microprocessor. Storage devices (e.g. registers and arrays) capture their values according to the clock cycle. For example, a storage device may capture a value according to a rising or falling edge of a clock signal defining the clock cycle. The storage device then stores the value until the subsequent rising or falling edge of the clock signal, respectively. The term “instruction processing pipeline” is used herein to refer to the logic circuits employed to process instructions in a pipelined fashion. Although the pipeline may be divided into any number of stages at which portions of instruction processing are performed, instruction processing generally comprises fetching the instruction, decoding the instruction, executing the instruction, and storing the execution results in the destination identified by the instruction.
An important feature of microprocessors is the degree to which they can take advantage of parallelism. Parallelism is the execution of instructions in parallel, rather than serially. Superscalar processors are able to identify and utilize fine grained instruction level parallelism by executing certain instructions in parallel. However, this type of parallelism is limited by data dependencies between instructions. Further, as mentioned above, computer systems which contain more than one processor may improve performance by dividing the workload presented by the computer processes. By identifying higher levels of parallelism, multi-processor computer systems may execute larger segments of code, or threads, in parallel on separate processors. Because microprocessors and operating systems cannot identify these segments of code which are amenable to parallel multithreaded execution, they are identified by the application code itself. Generally, the operating system is responsible for scheduling the various threads of execution among the available processors in a multi-processor system.
One problem with parallel multithreading is that the overhead involved in scheduling the threads for execution by the operating system is such that shorter segments of code cannot efficiently take advantage of parallel multithreading. Consequently, potential performance gains from parallel multithreading are not attainable.
SUMMARY OF THE INVENTION
The problems outlined above are in large part solved by a microprocessor and method as described herein. Additional circuitry is included in a form of symmetrical multiprocessing system which enables the scheduling and speculative execution of multiple threads on multiple processors without the involvement and inherent overhead of the operating system. Advantageously, parallel multithreaded execution is more efficient and performance is improved.
Broadly speaking, a multiprocessor computer is contemplated comprising a plurality of processors, wherein said processors include a register file, a reorder buffer and circuitry to support speculative multithreaded execution. In addition, the multiprocessor computer includes one or more reorder buffer tag translation buffers and a thread control device. The thread control device is configured to store and transmit instructions between the processors. The thread control device and instructions support parallel speculative multithreaded execution.
In addition, a method is contemplated which comprises performing thread setup for execution of a second thread on a second processor, wherein the setup comprises a first processor conveying setup instructions to a second processor, where the setup instructions are speculatively executed on the second processor. A startup instruction is conveyed from the first processor to the second processor which begins speculative execution of the second thread on the second processor. The second processor begins speculative execution of the second thread in parallel with the execution of a thread on the first processor, in response to receiving the startup instruction. Execution of the second thread is terminated, in response to retiring a termination instruction in the second processor. Finally, the results of the execution of the second thread are conveyed to the first processor, in response to the second processor receiving a retrieve result instruction, where the retrieve result instruction is speculatively executed by the second processor.
REFERENCES:
patent: 5430850 (1995-07-01), Papadopoulos et al.
patent: 5535361 (1996-07-01), Hirata et al.
patent: 5590326 (1996-12-01), Manabe
patent: 5594741 (1997-01-01), Kinzelman et al.
patent: 5632023 (1997-05-01), White et al.
patent: 5721857 (1998-02-01), Glew et al.
patent: 5742822 (1998-04-01), Motomura
patent: 5745703 (1998-04-01), Cejtin et al.
patent: 5828880 (1998-10-01), Hanko
patent: 5913059 (1999-06-01), Torii
patent: 5951672 (1999-09-01), Kwok et al.
patent: 5978838 (1999-11-01), Mohamed et al.
patent: 0 725 335 (1996-08-01), None
patent: 93/02414 (1993-02-01), None
patent: 98/43193 (1998-10-01), None
Eggers et al., “Simultaneous Multithreading: A Platform for Next-Generation processors,” IEEE Micro, Sep. 1997, pp. 12-19.
Tullsen et al., “Supporting Fine-Grained Synchronization on a Simultaneous Multithreading Processor,” Proceedings of the 5th International Symposium on High Performance Computer Architecture, Jan. 1999, 5 pgs.
Hammond et al., “Data Speculation Support for a Chip Multiprocessor,” © 1998 ACM, pp. 58-69.
Krishnan et al., “A Chip-Multiprocessor Architecture with Speculative Multithreading,” IEEE Transactions on Computers, vol. 48, No. 9, Sep. 1999, pp. 866-880.
Marcuello et al., “Speculative Multithreaded Processors,” Jul. 1998, pp. 77-84.
International Search Report, International application No. PCT/US00/20881, mailed Apr. 4, 2001.
Christie David S.
Kranich Uwe
Chan Eddie
Huisman David J.
Kivlin B. Noäl
Meyertons Hood Kivlin Kowert & Goetzel P.C.
LandOfFree
Method and mechanism for speculatively executing threads of... 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 mechanism for speculatively executing threads of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and mechanism for speculatively executing threads of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3141071