Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1993-01-11
2001-02-27
Ellis, Richard L. (Department: 2783)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
Reexamination Certificate
active
06195676
ABSTRACT:
RELATED APPLICATIONS
This application is a continuation-in-part of an application filed in the United States Patent and Trademark Office on Dec. 29, 1989, entitled CLUSTER ARCHITECTURE FOR A HIGHLY PARALLEL SCALAR/VECTOR MULTIPROCESSOR SYSTEM, U.S. Ser. No. 07/459,083 now U.S. Pat. No. 5,197,130, and assigned to the assignee of the present invention, a copy of which is attached hereto as an appendix and the disclosure of which is hereby incorporated in the present application. This application is also related to co-pending applications filed in the United States Patent and Trademark Office concurrently herewith, entitled DISTRIBUTED INPUT/OUTPUT ARCHITECTURE FOR A HIGHLY PARALLEL MULTIPROCESSOR SYSTEM, U.S. Ser. No. 07/536,182, now issued as U.S. Pat. No. 5,168,547, and SCALAR/VECTOR PROCESSOR, U.S. Ser. No. 07/536,409 now U.S. Pat. No. 5,430,884, of which are assigned to the assignee of the present invention, and a copy of each of which is attached hereto as an appendix and the disclosure of which is hereby incorporated in the present application.
TECHNICAL FIELD
This invention relates generally to the field of operating system software and program development tools for computer processing systems. More particularly, the present invention relates to an integrated software architecture for a highly parallel multiprocessor system having multiple. tightly-coupled processors that share a common memory.
BACKGROUND ART
It is well recognized that one of the major impediments to the effective utilization of multiprocessor systems is the lack of appropriate software adapted to operate on something other than the traditional von Neuman computer architecture of the types having a single sequential processor with a single memory. Until recently, the vast majority of scientific programs written in the Fortran and C programming languages could not take advantage of the increased parallelism being offered by new multiprocessor systems, particularly the high-speed computer processing systems which are sometimes referred to as supercomputers. It is particularly the lack of operating system software and program development tools that has prevented present multiprocessor systems from achieving significantly increased performance without the need for user application software to be rewritten or customized to run on such systems.
Presently, a limited number of operating systems have attempted to solve some of the problems associated with providing support for parallel software in a multiprocessor system. To better understand the problems associated with supporting parallel software, it is necessary to establish a common set of definitions for the terms that will be used to describe the creation and execution of a program on a multiprocessor system. As used within the present invention, the term program refers to either a user application program, operating system program or a software development program referred to hereinafter as a software development tool. A first set of terms is used to describe the segmenting of the program into logical parts that may be executed in parallel. These terms relate to the static condition of the program and include the concepts of threads and multithreading. A second set of terms is used to describe the actual assignment of those logical parts of the program to be executed on one or more parallel processors. This set of terms relate to the dynamic condition of the program during execution and include the concepts of processes, process images and process groups.
A thread is a part of a program that is logically independent from another part of the program and can therefore be executed in parallel with other threads of the program. In compiling a program to be run on a multiprocessor system, some compilers attempt to create multiple threads for a program automatically, in addition to those threads that are explicitly identified as portions of the program specifically coded for parallel execution. For example, in the UNICOS operating system for the Cray X-MP and Y-MP supercomputers from Cray Research, Inc., the compilers (one for each programming langauge) attempt to create multiple threads for a program using a process referred to by Cray Research as Autotasking®. In general, however, present compilers have had limited success in creating multiple threads that are based upon on analysis of the program structure to determine whether multithreading is appropriate and that will result in reduction in execution time of the multithreaded program in proportion to the number of additional processors applied to the multithreaded program.
The compiler will produce an object code file for each program module. A program module contains the source code version for all or part of the program. A program module may also be referred to as a program source code file. The object code files from different program modules are linked together into an executable file for the program. The lining of programs together is a common and important part of large scale user application programs which may consist of many program modules, sometimes several hundred program modules.
The executable form of a multithreaded program consists of multiple threads that can be executed in parallel. In the operating system, the representation of the executable form of a program is a process. A process executes a single thread of a program during a single time period. Multiple processes can each execute a different thread or the same thread of a multithreaded program. When multiple processes executing multiple threads of a multithreaded program are simultaneously executing on multiple processors, then parallel processing of a program is being performed. When multiple processes execute multiple threads of a multithreaded program, the processes share a single process image and are referred to as shared image processes. A process image is the representation in the operating system of the resources associated with process. The process image includes the instructions and data for the process, along with the execution context information for the processor (the values in all of the registers, both control registers and data registers, e.g., scalar registers, vector registers, and local registers) and the execution context information for operating system routines called by the process.
In present multiprocessor systems, the operating system is generally responsible for assigning processes to the different processors for execution. One of the problems for those prior art operating systems that have attempted to provide support for multithreaded programs is that the operating systems themselves are typically centralized and not multithreaded. Although a centralized, single threaded operating system can schedule multiple processes to execute in multiple processors in multiprocessor systems having larger numbers of processors, the centralized, single threaded operating system can cause delays and introduce bottlenecks in the operation of the multiprocessor system.
One method of minimizing the delays and bottlenecks in the centralized operating system utilizes the concept of a lightweight process. A lightweight process is a thread of execution (in general, a thread from a multithreaded program) plus the context for the execution of the thread. The term lightweight refers to the relative amount of context information for the thread. A lightweight process does not have the full context of a process (e.g., it often does not contain the full set of registers for the processor) A lightweight process also does not have the full flexibility of a process. The execution of a process can be interrupted at any time by the operating system. When the operating system stops execution of a process, for example in response to an interrupt, it saves the context of the currently executing process so that the process can be restarted at a later time at the same point in the process with the same context. Because of the limited context information, a lightweight process should not be interrupted at an arbitrary point in its execution. A l
Barkai David M.
Brussino Giacomo G.
Burke Jeremiah D.
Chandramouli Ashok
Chen Steve S.
Ellis Richard L.
Schwegman Lundberg Woessner & Kluth P.A.
Silicon Graphics Inc.
LandOfFree
Method and apparatus for user side scheduling in 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 Method and apparatus for user side scheduling in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for user side scheduling in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2606034