Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
2002-09-20
2004-08-31
Donaghue, Larry D (Department: 2154)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C718S103000, C712S219000, C712S228000
Reexamination Certificate
active
06785890
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of multithreaded processors and, more specifically, to a method and apparatus for performing context (or thread) switching within a multithreaded processor.
BACKGROUND OF THE INVENTION
Multithreaded processor design has recently been considered as an increasingly attractive option for increasing the performance of processors. Multithreading within a processor, inter alia, provides the potential for more effective utilization of various processor resources, and particularly for more effective utilization of the execution logic within a processor. Specifically, by feeding multiple threads to the execution logic of a processor, clock cycles that would otherwise have been idle due to a stall or other delay in the processing of a particular thread may be utilized to service a further thread. A stall in the processing of a particular thread may result from a number of occurrences within a processor pipeline. For example, a cache miss or a branch missprediction (i.e., a long-latency operation) for an instruction included within a thread typically results in the processing of the relevant thread stalling. The negative effect of long-latency operations on execution logic efficiencies is exacerbated by the recent increases in execution logic throughput that have outstripped advances in memory access and retrieval rates.
Multithreaded computer applications are also becoming increasingly common in view of the support provided to such multithreaded applications by a number of popular operating systems, such as the Windows NT® and Unix operating systems. Multithreaded computer applications are particularly efficient in the multi-media arena.
Multithreaded processors may broadly be classified into two categories (i.e., fine or coarse designs) according to the thread interleaving or switching scheme employed within the relevant processor. Fine multithreaded designs support multiple active threads within a processor and typically interleave two different threads on a cycle-by-cycle basis. Coarse multithreaded designs typically interleave the instructions of different threads on the occurrence of some long-latency event, such as a cache miss. A coarse multithreaded design is discussed in Eickemayer, R.; Johnson, R.; et al., “Evaluation of Multithreaded Uniprocessors for Commercial Application Environments”,
The
23
rd Annual International Symposium on Computer Architecture
, pp. 203-212, May 1996. The distinctions between fine and coarse designs are further discussed in Laudon, J; Gupta, A, “Architectural and Implementation Tradeoffs in the Design of Multiple-Context Processors”,
Multithreaded Computer Architectures: A Summary of the State of the Art
, edited by R. A. Iannuci et al., pp. 167-200, Kluwer Academic Publishers, Norwell, Mass., 1994. Laudon further proposes an interleaving scheme that combines the cycle-by-cycle switching of a fine design with the full pipeline interlocks of a coarse design (or blocked scheme). To this end, Laudon proposes a “back off” instruction that makes a specific thread (or context) unavailable for a specific number of cycles. Such a “back off” instruction may be issued upon the occurrence of predetermined events, such as a cache miss. In this way, Laudon avoids having to perform an actual thread switch by simply making one of the threads unavailable.
REFERENCES:
patent: 3771138 (1973-11-01), Celtruda et al.
patent: 5325526 (1994-06-01), Cameron et al.
patent: 5357617 (1994-10-01), Davis et al.
patent: 5361337 (1994-11-01), Okin
patent: 5386561 (1995-01-01), Huynh et al.
patent: 5392437 (1995-02-01), Matter et al.
patent: 5404469 (1995-04-01), Chung et al.
patent: 5430850 (1995-07-01), Papadopoulos et al.
patent: 5499349 (1996-03-01), Nikhil et al.
patent: 5524263 (1996-06-01), Griffth et al.
patent: 5528513 (1996-06-01), Vaitzblit et al.
patent: 5553291 (1996-09-01), Tanaka et al.
patent: 5586332 (1996-12-01), Jain et al.
patent: 5630130 (1997-05-01), Perotto et al.
patent: 5742782 (1998-04-01), Ito et al.
patent: 5761522 (1998-06-01), Hisanaga et al.
patent: 5787297 (1998-07-01), Lin
patent: 5809271 (1998-09-01), Colwell et al.
patent: 5809522 (1998-09-01), Novak et al.
patent: 5892959 (1999-04-01), Fung
patent: 5968160 (1999-10-01), Saito et al.
patent: 5983339 (1999-11-01), Klim
patent: 5996085 (1999-11-01), Cheong et al.
patent: 6009454 (1999-12-01), Dummermuth
patent: 6052708 (2000-04-01), Flynn et al.
patent: 6085215 (2000-07-01), Ramakrishnan et al.
patent: 6085218 (2000-07-01), Carmon
patent: 6088788 (2000-07-01), Borkenhagen et al.
patent: 6092175 (2000-07-01), Levy et al.
patent: 6105127 (2000-08-01), Kimura et al.
patent: 6212544 (2001-04-01), Borkenhagen et al.
patent: 6256775 (2001-07-01), Flynn
patent: 6289461 (2001-09-01), Dixon
patent: 6314530 (2001-11-01), Mann
patent: 6330584 (2001-12-01), Joffe et al.
patent: 6470376 (2002-10-01), Tanaka et al.
patent: 6535905 (2003-03-01), Kalafatis et al.
patent: 6625635 (2003-09-01), Elnozahy
patent: 0 346 003 (1989-12-01), None
patent: 0 352 935 (1990-01-01), None
patent: 0 725 335 (1996-08-01), None
patent: 0 747 816 (1996-12-01), None
patent: 0 768 508 (1997-04-01), None
patent: 0 768 608 (1997-04-01), None
patent: 0 827 071 (1998-03-01), None
patent: 0 856 797 (1998-08-01), None
patent: 0 863 462 (1998-09-01), None
patent: 0 864 960 (1998-09-01), None
patent: 0 962 856 (1999-12-01), None
patent: 2311880 (1997-10-01), None
patent: WO 99/21082 (1999-04-01), None
patent: WO 99/21088 (1999-04-01), None
Dean M. Tullsen, et al., “Exploiting Choice: Instruction Fetch and Issue on an Implementable Simultaneous Multithreading Processor” Dept. of Computer Science & Engineering, University of WA, Seattle, WA.
Roa P. Pokala, et al., “Physical Synthesis for Performance Optimization”, Vertex Semiconductor, San Jose, CA.
Gregory T. Byrd, et al., “Multithreaded Processor Architectures”, Western Carolina University, 8045 IEEE Spectrum, 32 (Aug. 1995), No. 8, New York, U.S.
Mark R. Thistle, et al., “A Processor Architecture For Horizon”; Institute for Defense Analyses, Supercomputing Research Center, Lanham, Maryland 20706.
Steere D, et al., “A Feedback-driven Proportion Allocator for Real-Rate Scheduling”,Third Symposium on Operating Systems Design and Implemenations, Feb. 22-25, 1999, pp. 145-158, XP002153159.
INTEL, “P6 Family of Processors”,Hardware Developer's Manual, Sep. 1998, XP-02153160.
IBM, “Improved Dispatching in a Rendering Context Manager”,IBM Technical Disclosure Bulletin, Dec. 1990, pp. 131-134, vol. 33, No. 7, XP000108363 ISSN: 0018-18689, Armonk, NY.
Farrens, MK; Pleszkun, AR., “Strategies for Archieving Improved Processor Throughput”,The 18th Annual International Symposium on Computer Architecture, May 27-30, 1991, pp. 362-369.
Mendelson, A; Berkerman, M., “Design Alternatives of Multithreaded Architecture”,International Journal of Parallel Programming, Dec. 9, 1996, vol. 27, No. 3, pp. 161-193, Pullenum Publishing Corporation.
James Laudon, Anoop Gupta and Mark Horowitz, “Architectural and Implementation Tradeoffs in the Design of Multiple-Context Processors”,Multithreaded Computer Architecture; A Summary of the State of the Art, chapter 8, pp. 167-200, Kluwer Academic Publishers 1994.
Dean M. Tullsen, Susan J. Eggers, Joel S. Emer, Henry M. Levy, Jack L. Lo And Rebecca L. Stammm, “Exploiting Choice: Instruction Fetch and Issue on an Implementable Simultaneous Multithreading Processor”,Proceedings of the 23rd Annual International Symposium on Computer Architecture, May 22-24, 1996, pp. 191-202.
Richard J. Eickemeyer, Ross E. Johnson, Steven R. Kunkel, Mark S. Squillante And Shiafun Liu, “Evaluation of Multithreaded Uniprocessors for Commercial Application Environments”,Proceedings of the 23rd Annual International Symposium on Computer Architecture, May 22-24, 1996, pp. 203-212.
Manu Gulati and Nader Bagherzadeh, “Performance Study of a Multithreaded Superscalar Microprocessor”,Proceedings Second International Symposium on High-Performance Computer Architecture, Feb. 3-7, 1996, pp. 291-301.
R. Guru Prasadh and Chu
Fisch Robert D.
Kalafatis Stavros
Kyker Alan B.
Blakely , Sokoloff, Taylor & Zafman LLP
Donaghue Larry D
Intel Corporation
LandOfFree
Method and system to perform a thread switching operation... 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 system to perform a thread switching operation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system to perform a thread switching operation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3301832