Dual level scheduling of processes to multiple parallel regions of a multi-threaded program on a tightly coupled multiprocessor computer system

• US 5,339,415 A
• Filed: 11/09/1992
• Issued: 08/16/1994
• Est. Priority Date: 06/11/1990
• Status: Expired due to Term

• Current Assignee: Silicon Graphics International Corporation (Hewlett-Packard Enterprise Company)
• Original Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: Strout, II, Robert E., Spix, George A., Masamitsu, Jon A., Cox, David M., Gaertner, Gregory G., Wengelski, Diane M., Thompson, Keith J.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Chavis, John Q.
• Application Number:
  US07/973,598
• Time in Patent Office: 645 Days
• Field of Search: 395/650, 395/700
• US Class Current: 718/102
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 8/41 Compilation
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

On a tightly coupled multiprocessor computer system, the multiple parallel regions of a multithreaded applications program can execute simultaneously as multiple threads on a plurality of processors. Furthermore, a plurality of multithreaded programs may run simultaneously. The current invention uses an efficient system to schedule and reschedule processors to run these multiple threads. Scheduling is integrated at two levels: at the first level, processors are assigned processes. At the next level, processes are assigned threads. Increased efficiency is achieved by this integration and also by the formation of processes with destructible context. It makes use of shared storage to indicate the process request level and the control state for each parallel region.

Claims

1. In an operating system having a plurality of shared storage resources accessible by a plurality of processors for running a multithreaded program, a two level scheduling method of executing said multithreaded program, comprising the steps of:

(a) assigning program threads of said multithreaded program to processes;

(b) storing in a first shared storage resource context for executing said processes corresponding to said program threads;

(c) queuing in a second shared storage resource a value representing the number of said program threads in said multithreaded program to be executed;

(d) determining that a processor is available to execute a process having context stored in said first shared storage resource; and

(e) scheduling said processes for execution by said processors, comprising the steps of;

scanning by said available processor a queue in said second shared storage resource to respond to a positive value in said second shared storage resource;

decrementing said second shared storage resource value using said available processor; and

accessing contents of said first shared storage resource corresponding to said scan for initiating execution, using said available processor, of a process associated with accessed context.

2. The method according to claim 1 wherein said first shared storage resource includes a plurality of global registers sequentially accessible by a processor, and said storing step further includes the step of sequentially loading said plurality of global registers with information corresponding to the context of a process to run a thread.

3. The method according to claim 1 wherein said second shared storage resource is a global register, and the method includes a further step of returning an available processor to the operating system when said second shared storage resource contains a value of zero.

4. The method in accordance with claim 1 in which the operating system performs the steps of:

scheduling a number of processors for executing said processes of said multithreaded program; and

allowing only said scheduled number of processors to access said first and second shared storage resources.