Symmetric multiprocessor operating system for execution on non-independent lightweight thread contexts

Patent 7730291 Issued on June 1, 2010. Estimated Expiration Date:

December 23, 2026. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

Expandable multi-port random access memory
Patent #: 4817051
Issued on: 03/28/1989
Inventor: Chang

Computer system for controlling virtual machines
Patent #: 4860190
Issued on: 08/22/1989
Inventor: Kaneda , et al.

Multi-processor computer system having process-independent communication register addressing
Patent #: 5159686
Issued on: 10/27/1992
Inventor: Chastain, et al.

Device for enhancing the performance of a real time executive kernel associated with a multiprocessor structure that can include a large number of processors
Patent #: 5295265
Issued on: 03/15/1994
Inventor: Ducateau, et al.

Computer system with clock shared between processors executing separate instruction streams
Patent #: 5428754
Issued on: 06/27/1995
Inventor: Baldwin

Pipelined processor with fork, join, and start instructions using tokens to indicate the next instruction for each of multiple threads of execution
Patent #: 5499349
Issued on: 03/12/1996
Inventor: Nikhil, et al.

Method and apparatus for managing thread private data in a parallel processing computer
Patent #: 5511192
Issued on: 04/23/1996
Inventor: Shirakihara

Apparatus and method for interrupt handling in a multi-threaded operating system kernel
Patent #: 5515538
Issued on: 05/07/1996
Inventor: Kleiman

System and method for dynamically performing resource reconfiguration in a logically partitioned data processing system
Patent #: 5659786
Issued on: 08/19/1997
Inventor: George, et al.

Methods and apparatus for managing a database in a distributed object operating environment using persistent and transient cache
Patent #: 5727203
Issued on: 03/10/1998
Inventor: Hapner, et al.

More ...

Inventor

Kissell, Kevin D.

Assignee

MIPS Technologies, Inc.

Application

No. 11615964 filed on 12/23/2006

US Classes:

712/244Exeception processing (e.g., interrupts and traps)

Examiners

Primary: Chan, Eddie P
Assistant: Faherty, Corey S

Attorney, Agent or Firm

Sterne, Kessler, Goldstein & Fox pllc

Foreign Patent References

0725334 EP 08/01/1996
0917057 EP 05/01/1999
1089173 EP 04/01/2001
8-249195 JP 09/01/1996
2007-504536 JP 03/01/2007
WO0153935 WO 07/01/2001
WO 03/019360 WO 03/01/2003
WO 2005/022385 WO 03/01/2005

International Classes

G06F 7/38
G06F 9/00
G06F 9/44
G06F 15/00

Abstract

A multiprocessing system, including a multithreading microprocessor and a multiprocessor operating system (OS), is disclosed. The microprocessor includes a plurality of thread contexts (TCs), each having a program counter and a general purpose register set for executing a thread. The OS includes a data structure having an entry for each of the plurality of TCs, each entry containing information describing capabilities of the corresponding one of the plurality of TCs. Each entry further comprises a TC identifier field for identifying a corresponding one of the plurality of TCs. The OS populates the TC identifier field for each of the entries with a unique identifier value.

Other References

Office Communication, dated Oct. 16, 2009, for U.S. Appl. No. 11/615,963, filed Dec. 23, 2006, 5 pages.
Office Communication, dated Jul. 6, 2009, for U.S. Appl. No. 11/615,960, filed Dec. 23, 2006, 16 pages.
Kissell, K.D., U.S. Appl. No. 12/605,201, filed Oct. 23, 2009, entitled “Apparatus, Method, and Instruction for Initiation of Concurrent Instruction Streams in a Multithreading Microprocessor,” 34 pages.
Haggander, D. et al., “Optimizing Dynamic Memory Management in a Multithreaded Application Executing on a Multiprocessor,” Proceedings of the International Conference on Parallel Processing, Aug. 10-14, 1998, pp. 262-269.
Office Communication, dated Dec. 22, 2008, for U.S. Appl. No. 11/949,603, filed December 3, 2007, 8 pages.
Office Communication, dated Apr. 9, 2009, for U.S. Appl. No. 11/615,965, filed Dec. 23, 2006, 16 pages.
Office Communication, dated Oct. 16, 2008, for U.S. Appl. No. 11/615,965, filed Dec. 23, 2006, 17 pages.
Office Communication, dated Apr. 3, 2009, for U.S. Appl. No. 11/615,963, filed Dec. 23, 2006, 15 pages.
Office Communication, dated Oct. 17, 2008, for U.S. Appl. No. 11/615,963, filed Dec. 23, 2006, 16 pages.
Office Communication, dated Apr. 10, 2009, for U.S. Appl. No. 11/615,960, filed Dec. 23, 2006, 16 pages.
Office Communication, dated Dec. 8, 2008, for U.S. Appl. No. 11/615,960, filed Dec. 23, 2006, 15 pages.
Office Communication, dated May 15, 2008, for U.S. Appl. No. 11/615,960, filed Dec. 23, 2006, 17 pages.
Office Communication, dated Aug. 9, 2007, for U.S. Appl. No. 10/955,231, filed Sep. 30, 2004, 23 pages.
Office Communication, dated Dec. 19, 2006, for U.S. Appl. No. 10/955,231, filed Sep. 30, 2004, 19 pages.
Office Communication, dated Mar. 5, 2009, for U.S. Appl. No. 10/954,988, filed Sep. 30, 2004, 5 pages.
Office Communication, dated Jul. 29, 2008, for U.S. Appl. No. 10/954,988, filed Sep. 30, 2004, 8 pages.
Office Communication, dated Jan. 9, 2008, for U.S. Appl. No. 10/954,988, filed Sep. 30, 2004, 9 pages.
Office Communication, dated Apr. 6, 2007, for U.S. Appl. No. 10/954,988, filed Sep. 30, 2004, 8 pages.
Office Communication, dated Mar. 22, 2007, for U.S. Appl. No. 10/929,342, filed Aug. 27, 2004, 22 pages.
Office Communication, dated Oct. 12, 2006, for U.S. Appl. No. 10/929,342, filed Aug. 27, 2004, 26 pages.
Office Communication, dated Feb. 17, 2009, for U.S. Appl. No. 10/929,102, filed Aug. 27, 2004, 32 pages.
Office Communication, dated Jan. 22, 2009, for U.S. Appl. No. 10/928,746, filed Aug. 27, 2004, 31 pages.
Office Communication, dated Apr. 21, 2008, for U.S. Appl. No. 10/928,746, filed Aug. 27, 2004, 29 pages.
Office Communication, dated Oct. 23, 2007, for U.S. Appl. No. 10/928,746, filed Aug. 27, 2004, 27 pages.
Office Communication, dated Apr. 9, 2007, for U.S. Appl. No. 10/928,746, filed Aug. 27, 2004, 28 pages.
English Translation of Notice of Rejection for Japanese Patent Application No. 2006-524929, dated Nov. 28, 2008, 4 pages.
Teller et al., “Locating Multiprocessor TLBs at Memory,” Proc. of the Twenty-Seventh Annual Hawaii International Conference on System Sciences, IEEE, pp. 554-563, 1994.
Sweetman, D., See MIPS Run, Morgan Kaufmann Publishers, San Francisco, CA (2002). (entire book submitted).
MIPS32® Architecture for Programmers, Volume IV-f: The MIPS® MT Application-Specific Extension to the MIPS32® Architecture, Revision 1.00, Sep. 28, 2005, MIPS Technologies, Inc., 83 pages.
MIPS32® Architecture for Programmers, Volume III: The MIPS32® Privileged Resource Architecture, Revision 2.50, Jul. 1, 2005, MIPS Technologies, Inc., 137 pages.
Lee, B. et al., “Simulation Study of Multithreaded Virtual Processor,” IASTED International Conference on Parallel and Distributed Systems (Euro-PDS), pp. 1-6, Jul. 3, 1998.
Kwak, H. et al., “Effects of Multithreading on Cache Performance,” IEEE Transaction on Computers, IEEE, vol. 48, Issue 2, pp. 176-184, Feb. 1999.
Kissell, K.D., “MIPS MT: A Multithreaded RISC Architecture for Embedded Real-Time Processing,” High Performance Embedded Architectures and Compilers, Spring, vol. 4917/2008, pp. 9-21, 2008.
Kane, G. and Heinrich, J., MIPS RISC Architecture, Prentice Hall, Upper Saddle River, New Jersey, 1992. (entire book submitted).
Exception Handler, from Free Online Dictionary of Computing, 1 page, Oct. 31, 1994.
English Abstract of Japanese Patent Publication No. 8-259195, published Sep. 27, 1996, 1 page.
English Abstract of Japanese Patent Publication No. 2007-504536, published September Mar. 1, 2007, 1 page.
English Translation of Notice of Rejection for Japanese Patent Application No. 2006-524961, dated Nov. 28, 2008, 3 pages.
English Translation of Notice of Rejection for Japanese Patent Application No. 2006-524900, dated Nov. 28, 2008, 4 pages.
Culler, D.E. et al., Two Fundamental Limits on Dataflow Multiprocessing, Report No. UCB/CSD 92/716, pp. 1-14, 1993.
Agarwal, A. et al., “APRIL: A Processor Architecture for Multiprocessing,” ACM SIGARCH Computer Architecture News, vol. 18, Issue 3a, pp. 104-114, Jun. 1990.
Hennessy, John L. et al. “Computer Architecture A Quantitative Approach.” Second Edition. San Francisco, CA: Morgan Kaufmann Publishers, Inc. 1996. pp. 70-73 and 87-89.
Sunsoft. Multithreaded Programming Guide. 1994. Sunsoft, A Sun Microsystems, Inc. Business. Mountainview, CA. pp. 6, 12-13, 22-34 and 87.
Heuring, Vincent P. and Jordan, Harry F. “Computer Systems and Architecture.” Reading, Mass.: Addison Wesley Longman, Inc., © 1997. pp. 35-37.
Silberschatz et al. “Operating Systems Concepts.” 1994. Addison-Wesley Publishing Company. Fourth Edition. pp. 267-269, 271-272, 275.
Patterson et al. “Computer Organization & Design: The Hardware/Software Interface.” 1998. Morgan Kaufmann Publishers, Inc. Second Edition. pp. 592-593.
MIPS32™ Architecture For Programmers vol. II The MIPS32™ Instruction Set. Revision 2.00. pp. 231 & 311. Document No. MD00086. Jun. 9, 2003. MIPS Technologies, Inc.
Arvind and R.A. Innaucci. “Two Fundamental Issues in Multiprocessing.” In Proc. of DFVLF-Conf. 1987 on Par.Proc.in Science and Eng., Bonn-Bad Godesberg, W. Germany, Jun. 1987.
“MIT Alewife Project: Home Page.” retrieved from URL: http://catfish.csail.mit.edu/alewife/ on Jul. 2, 2004.
Alverson, Gail et al. “A Future-Based Parallel Language for a General Purpose Highly Parallel Computer.” Languages and Compilers for Parallel Computing. pp. 95-113, MIT Press, Cambridge, Massachusetts, 1990.
Smith, Burton. “The End of Architecture.” Keynote Address, 17th Annual Symposium on Computer Architecture, Seattle, Washington, May 1990.
Alverson, Robert et al. “The Tera Computer System.” ACM International Conference on Supercomputing, pp. 1-6, Jun. 1990.
Callahan, David et al. “Improving Register Allocation for Subscripted Variables.” ACM SIGPLAN Conference on Programming Language Design and Implementation, Jun. 1990.
Alverson, Robert. “Integer Division Using Reciprocals.” 10th IEEE Symposium on Computer Arithmetic, Jun. 1991.
Callahan, David et al. “Register Allocation via Hierarchical Graph Coloring.” ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, Jun. 1991.
Callahan, David. “Recognizing and Parallelizing Bounded Recurrences.” Fourth Workshop on Languages and Compilers for Parallel Computing. pp. 169-184. Aug. 1991.
Alverson, Gail et al. “Exploiting Heterogeneous Parallelism on a Multithreaded Multiprocessor.” 6th ACM International Conference on Supercomputing, Washington DC, Jul. 1992.
Smith, Burton. “The Quest for General-Purpose Parallel Computing.” 1994.
Smith, Burton. “Folklore and Reality in High Performance Computing Slide Presentation.” 1995.
Alverson, Gail et al., “Scheduling on the Tera MTA.” IPPS '95 Workshop on Job Scheduling Strategies for Parallel Processing, Santa Barbara, CA, Apr. 1995, and in D.G.Feitelson and L. Rudolph, editors, Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science vol. 949, pp. 19-44, Springer-Verlag 1995.
Briggs, Preston. “Tuning the BLAS for the Tera.” Workshop on Multithreaded Execution, Architecture and Compilation. (MTEAC 98), Jan. 1998.
Smith, Burton. “From Here to Petaflops.” Keynote Address, Petaflops-systems Operations Working Review, (POWR), Bodega Bay, California, Jun. 1998.
Zaslavsky, Leonid et al. “A Scalable Approach for Solving Irregular Sparse Linear Systems on the Tera MTA Multithreaded Parallel Shared-Memory.” Ninth SIAM Conference on Parallel Processing for Scientific Computing, San Antonio, TX. Mar. 1999.
(webpage) Cray MTA-2 Historical Technical Papers, http://www.cray.com/products/programs/mta_—2/resources.html. (Mar. 12, 2005), (formerly http://www.cray.com/products/systems/mta/psdocs.html (Jul. 2, 2004)).
Kissell, Kevin D. “Microprocessor Forum (MPF) Conference Program Presentation: Architectural Extensions to the MIPS Architecture for High-Performance Embedded Systems.” Oct. 15, 2003.
Bolychevsky et al. “Dynamic Scheduling in RISC Architectures.” IEEE Proceedings Computers and Digital Techniques, vol. 143, No. 5. Sep. 24, 1996. pp. 309-317.
Ubicom, Inc. A Next Generation Packet Processor for Wireless Networking. Apr. 15, 2003. Ubicom, Inc. Mountain View, CA, USA.
Popov, Konstantin: “A Parallel Abstract Machine for the Thread-Based Concurrent Language Oz,” Workshop on Parallism and Implementation of Technology for Constraint Logic Programming Languages, Sep. 1997, pp. 1-25.
Tsai et al: “The Superthreaded Architecture: Thread Pipelining with Run-Time Data Dependence Checking and Control Speculation,” Parallel Architectures and Compiliation Techniques, 1996, Proceedings of the 1996 Conference in Boston, MA, USA, Oct. 20-23, 1996, Los Alamitos, CA, USA, IEEE Comput. Soc., Oct. 20, 1996, pp. 35-46.
Ungerer et al., “Utilising Parallel Resources By Speculation,” Parallel and Distributed Processing, 1999. PDP '99. Proceedings of the Seventh Euromicro Workshop on Funchal, Portugal Feb. 3-5, 1999, Los Alamitos, CA, USA, IEEE Computing Society, Feb. 3, 1999, pp. 339-343.
Mehl et al., “An Abstract Machine for Oz,” Research Report RR-95-08, Online!, Jun. 1995, pp. 1-23, Kaiserslautern Saarbrucken, ISSN 0946-008.
Scheidhauer, Ralf, “Design, Implementie rung und Evaluierung einer virtuellen Maschine fur Oz,” Online!, Dec. 1998, Dissertation, Saarbrucken, (English-language version of the search report or action which indicates the degree of relevance found by the foreign office is appended.).
Frees, W., “Teilzeitarbeit Im Prozessor,” Electronik, Franzis Verlag GMBH. Munche, DE, vol. 45, No. 9, Apr. 30, 1996, pp. 100-106, XP000595386, ISSN: 0013-5658 (English-language version of the search report or action which indicates the degree of relevance found by the foreign office is appended.).
Ishihara et al., “A Comparison of Concurrent Programming and Cooperative Multithreading,” Euro-PAR 2000 Parallel Processing. 6th International Euro-PAR Conference. Proceedings (Lecture Notes in Computer Science vol. 1900) Springer-Verlag Berlin, Germany, Sep. 1, 2000, pp. 729-738, XP002315714, ISBN: 3-540-67956-1.
Engelschall, R.S., “pth GNU Portable Threads,” Pth Manual, Online! Feb. 17, 2003, pp. 1-31, XP002315713.
Sunsoft. Multithreaded Programming Guide. 1995. Sunsoft, A Sun Microsystems, Inc. Business. Mountainview, CA.
Marr et al. Hyper-Threading Technology. Intel Technology Journal, Feb. 14, 2002, vol. 6, No. 1, Intel Corporation, USA.
Carter et al., “Performance and Programming Experience on the Tera MTA,”Tera Computer Corporation—SIAM Conference on Parallel Processing—Mar. 1999.
Alverson et al., “Tera Hardware-Software Cooperation,” Tera Computer Corporation—Proceedings of the IEEE/ACM SC97 Conference—Nov. 15-21, 1997 San Jose, CA.
Fotland, David. A Multithreaded Wireless Network Processor with Software I/O. Embedded Processor Forum. Jun. 18, 2003. In-State MDR;www.MDRonline.com.
Ungerer et al. A Survey of Processors with Explicit Multithreading. ACM Computing Surveys, vol. 35, No. 1. Mar. 2003. pp. 29-63.
Dorai, Gautham K. et al. “Transparent Threads: Resource Sharing in SMT Processors for High Single-Thread Performance.” Proceedings of the International Conference on Parallel Architectures and Compilation Techniques 2002.
Zilles, Craig B. et al. “The Use of Multithreading for Exception Handling.” micro, p. 219. 32nd Annual International Symposium on Microarchitecture.
Wolf et al.; Improving Disk Cache Hit-Ratios Through Cache Partioning; 1992; IEEE Transactions on Computers, vol. 41, No. 6.
Silberschatz and Galvin; Operating Systems Concepts; 1994; Addison-Wesley Publishing Company; Fourth Edition; pp. 267-269,271-272,275.
Patterson and Hennessy; Computer Organization and Design: The Hardware/Software Interface; 1998; Morgan Kaufmann Publishers, Inc; Second Ediction; pp. 592-593.