Methods for efficient distribution of parallel tasks to slave processes in a multiprocessing system

• US 5,257,372 A
• Filed: 12/19/1990
• Issued: 10/26/1993
• Est. Priority Date: 12/19/1990
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: Andreasen, Clayton D., Hoel, Timothy W., LaCroix, Suzanne L., Reinhardt, Steven P., Furtney, Mark, Barriuso, Frank R.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): KATBAB, ABDOLLAH
• Application Number:
  US07/630,301
• Time in Patent Office: 1,042 Days
• Field of Search: 395/650
• US Class Current: 718/105
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

Three new, efficient protocols for providing communications between a user'"'"'s application program, a Multiprocessing Library, and the host Operating System is described. These new protocols are termed WAKEUP, GIVEUP, and CONTEXT-TO-USER-SPACE. They utilize the concept of a conduit through which the Operating System and the user application program can communicate without the need for expensive system calls. A primary use for the new protocols is the scheduling of multiple Central Processing Units (CPUs) into a single user program in a multi-CPU, multiprogramming, multi-tasking environment. WAKEUP allows a master process to quickly request the asynchronous scheduling of slave processes to help execute parallel tasks. GIVEUP allows a slave process time to finish a task before Operating System interruption. Once completed with its task, there is no need to save the context of the slave process. CONTEXT-TO-USE-SPACE allows other slave processes the opportunity to execute interrupted tasks that were not allowed to finish under GIVEUP.

Claims

1. In a multiprocessor system, a method for delaying Operating System interruptions of a process performing a thread of tasks until the current task is complete or the expiration of a time slice, comprising the steps of:

(a) the Operating System setting a GIVEUP flag in a data buffer area associated with the process to inform a multiprocessing scheduling program that the process is to be interrupted after the process is determined that it is performing said task;

(b) upon completion of said task the multiprocessing scheduling program reading the GIVEUP flag and returning the CPU to the Operating System if the GIVEUP flag is set; and

(c) the Operating System interrupting the process at the end of a time slice, if the process has not yet finished said task and returned the CPU back to the Operating System.

3. The method according to claim 1 further wherein a process checks its associated GIVEUP flag after it completes its assigned task.

5. The method according to claim 1 further wherein each slave process has a thread structure associated with it and further comprising the step of the Operating System checking to see if a process it wants to interrupt has a thread structure associated with it and, if it does, setting the GIVEUP flag for the process after checking the process to determine that the process is performing said task, and, if it is not performing said task, interrupting the process.

6. The method according to claim 1 wherein said method further comprises the steps of:

(d) the process setting a context save flag to "save-in-user-space" if the process is assigned a parallel task; and

(e) the Operating System, if it interrupts the process, checking the context save flag and saving the context of the interrupted process in user space if the flag is set to "save-in-user-space" so that the context may be retrieved by another process.

7. The method according to claim 6 further comprising the steps of:

(f) the process setting the context save flag to "don'"'"'t-save-at-all" if the process has no context worth saving; and

(g) the Operating System not saving the context of the interrupted process if the context save flag is set to don'"'"'t-save-at-all.

2. In a multiprocessor system, a method for assigning parallel tasks from interrupted processes to available processes, comprising the steps of:

(a) a slave process setting a save-in-user-space flag to inform the Operating System that the slave process is currently performing a parallel task;

(b) if the slave process is interrupted, the Operating System saving the context of the slave process in user-space;

(c) the Operating System setting a flag to inform a multiprocessing scheduling program that the process was interrupted while performing a parallel task;

(d) checking of the flag by the multiprocessing scheduling program to detect the interrupted task; and

(e) assigning the interrupted task to an available process started by the Operating System.

4. The method according to claim 2 further wherein the step of assigning a given process a task includes setting a save-in-system-space flag to inform the Operating System to save the context of the given process in system space if the process is interrupted because the process is not currently performing a parallel task.

8. The method according to claim 2 further wherein an interrupted process is rescheduled on a priority basis.

9. The method according to claim 2 further comprising the step of the first available process retrieving the context of the interrupted given task from user space and using the context to continue executing the task.

14. A method according to claim 2 further wherein the next available slave process executes said multiprocessing scheduling program as called for in step (d).

10. In a multiprocessor system having an Operating System, a method for parallel processing of parallel regions of code, comprising the steps of:

(a) establishing a master process and one or more slave processes;

(b) establishing a data buffer conduit including a thread structure and a context structure for each said slave process, each said thread structure including a WAKEUP flag and a GIVEUP flag;

(c) the master process setting the WAKEUP flag for a slave process when a parallel region of code is encountered;

(d) the Operating System polling said WAKEUP flags and, upon detection of a WAKEUP flag for a slave process, activating a slave process and the slave process obtaining a task to execute;

(e) the Operating System setting the GIVEUP flag for the running slave process if the Operating System desires to interrupt the process;

(f) the running slave process polling the GIVEUP flag at the completion of its task and returning control to the Operating System if the GIVEUP flag is set; and

(g) the Operating System interrupting the slave process for which it has set the GIVEUP flag if the slave process does not return control to the Operating System within a predetermined time slice.

11. The method according to claim 10 further wherein the thread structure includes a context save flag, and wherein said method further comprises the steps of:

(h) the slave process setting the context save flag to "save-in-user-space" if the slave process is currently performing parallel work; and

(i) the Operating System checking the context save flag if it interrupts a slave process and saving the context of the interrupted process in user space in the context structure if the flag is set so that the context may be retrieved by another process.

12. The method according to claim 10 further wherein the thread structure includes a context save flag, and wherein said method further comprising the steps of:

(h) the slave process setting the context save flag to "save-in-system-space" if the slave process is not currently performing parallel work; and

(i) the Operating System saving the context of the interrupted slave process in system space if the context save flag is set to save-in-system-space.

13. The method according to claim 10 further wherein the thread structure includes a context save flag, and wherein said method further comprising the steps of:

(h) the slave process setting the context save flag to "don'"'"'t save-at-all" if the process has no context worth saving; and

(i) the Operating System not saving the context of the interrupted slave process if the context slave flag is set to don'"'"'t-save-at-all.