System and method for controlling a highly parallel multiprocessor using an anarchy based scheduler for parallel execution thread scheduling

• US 5,179,702 A
• Filed: 06/11/1990
• Issued: 01/12/1993
• Est. Priority Date: 12/29/1989
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Supercomputer Systems Limited Partnership
• Inventors: Seberger, David A., Brussino, Giacomo G., O'Hair, Kelly T., Gaertner, Gregory G., O'Gara, Linda J., Thompson, Keith J., Cox, David M., Burke, Jeremiah D., Masamitsu, Jon A., Johnson, Mark D., Strout, II, Robert E., Hawkinson, Stuart W., Chandramouli, Ashok, Oslon, Steven G., Wengelski, Diane M., Van Dyke, Don A., Chen, Steve S., Spix, George A., Cramer, Timothy J., Barkai, David M., Rasbold, James C., Hessel, Richard E.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): ELLIS, RICHARD L
• Application Number:
  US07/537,466
• Time in Patent Office: 946 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 395/650
• US Class Current: 718/102
• CPC Class Codes: G06F 11/3664 Environments for testing or debugging software
• 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 15/17381 Two dimensional, e.g. mesh, torus
• CPC Class Codes: G06F 15/8076 Details on data register access
• CPC Class Codes: G06F 15/8092 Array of vector units
• 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/30021 Compare instructions, e.g. Greater-Than, Equal-To, MINMAX
• CPC Class Codes: G06F 9/30094 Condition code generation, e.g. Carry, Zero flag
• CPC Class Codes: G06F 9/30149 of variable length instructions
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: G06F 9/3804 for branches, e.g. hedging, branch folding
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/3856 Reordering of instructions, e.g. using queues or age tags
• CPC Class Codes: G06F 9/4881 : Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

An integrated software architecture for a highly parallel multiprocessor system having multiple tightly-coupled processors that share a common memory efficiently controls the interface with and execution of programs on such a multiprocessor system. The software architecture combines a symmetrically integrated multithreaded operating system and an integrated parallel user environment. The operating system distributively implements an anarchy-based scheduling model for the scheduling of processes and resources by allowing each processor to access a single image of the operating system stored in the common memory that operates on a common set of operating system shared resources. The user environment provides a common visual representation for a plurality of program development tools that provide compilation, execution and debugging capabilities for multithreaded user programs and assumes parallelism as the standard mode of operation.

Claims

1. An integrated software architecture for controlling a highly parallel multiprocessor system having multiple tightly-coupled processors that share a common memory, the integrated software architecture comprising:

control means for distributively controlling the operation and execution of a plurality of multithreaded programs in the multiprocessor system by executing a symmetrically integrated multithreaded operating system program on one or more of the processors that has an anarchy-based scheduling model for scheduling one or more processes and resources associated with each multithreaded program for execution on one or more of the processors, each processor having access to a single image of the operating system program stored in the common memory that operates on a common set of operating system shared resources, the operating system programming means comprising;

kernel means for processing multithreaded system services such that any one or more of the system services can be executed concurrently by multiple processors, the system services including;

parallel process scheduler means for scheduling multiple processes into one or more processors according the anarchy-based scheduling model,

parallel memory scheduler means for allocating space in the common memory among one or more processes scheduled for execution in one or more of the processors, and

support means for providing accounting, control, monitoring, security, administrative and operator information about any one or more of the processors;

input/output means for processing distributed, multithreaded input/output services such that any one or more of the input/output services can be executed concurrently by multiple ones of the processors and a plurality of input/output resources associated with the multiprocessor system, the input/output resources including a plurality of peripheral devices attached to the multiprocessor system via a plurality of external interfaces, the input/output services including

file management means for managing the external storage of files containing both data and instructions for the multithreaded programs,

input/output management means for distributively processing input/output requests from the processors to the peripheral devices,

resource scheduler means for allocating the input/output resources to the processes so as to optimize the usage the input/output resources of the multiprocessor system, and

network support means for supporting input/output requests to other remote processors interconnected with the multiprocessor system; and

multithreaded interface library means for interfacing requests to a plurality of common multithreaded object code files stored in the common memory for performing standard programming library functions; and

interface means operably associated with the control means for interfacing between one or more developers and users of the multithreaded programs and the control means so as to present a common visual format for all output representations and input commands for the operating system program and a plurality of program development tools that comprise an integrated parallel user environment for providing compilation, execution and debugging of the multithreaded programs.

2. The integrated software architecture of claim 1 wherein the program development tools of the integrated parallel user environment comprise:

compilation means for compiling a source code file representing one of the multithreaded programs to produce an executable code file containing one or more processes associated with the multithreaded program;

program management means for controlling a development and execution environment for the source code file;

debugger means for controlling a debugging environment in response to execution of the executable code file on the multiprocessor system; and

user interface means operably connected to the compilation means, the program management means and the debugger means for presenting the visual representations of one or more outputs and for receiving one or more input commands relating to of a plurality of status, control and execution options available for the multithreaded programs.

3. The integrated software architecture of claim 2 wherein the compilation means comprises:

one or more front end means for parsing the source code file and for generating an intermediate language representation of the source code file;

optimization means for optimizing the organization of the intermediate language representation of the source code file to produce a multithreaded program capable of parallel execution, including means for generating machine independent optimizations based on the intermediate language representation; and

code generating means for generating an object code file based upon the intermediate language representation, including means for generating machine dependent optimizations.

4. the integrated software architecture of claim 3 wherein the program management means comprises:

means for linking the object code file of the multithreaded program into an executable code file to be executed by the multiprocessor system;

means for executing the executable code file in the multiprocessor system; and

means for monitoring and tuning the performance of the executable code file, including means for providing the status, control and execution options available for the developer.

5. The integrated software architecture of claim 2 wherein the user interface means comprises:

a set of icon-represented functions corresponding to the status, control and execution options available for the multithreaded programs; and

an equivalent set of command-line functions.

6. The integrated software architecture of claim 3 wherein the debugger means comprises:

means for mapping the source code file to the object code file of the multithreaded program; and

means for mapping the object code file to the source code file of the multithreaded program.

7. A method for controlling a highly parallel multiprocessor system having multiple tightly-coupled processors that share a common memory comprising the steps of:

distributively controlling the operation and execution of one or more multithreaded programs in the multiprocessor system by executing a symmetrically integrated multithreaded operating system program on one or more of the processors that has an anarchy-based scheduling model for scheduling one or more processes and resources associated with each multithreaded program, each processor having access to a single image of the operating system program stored in the common memory that operates on a common set of operating system shared resources, the operating system program comprising the steps of;

(a) processing a plurality of multithreaded system services such that any one or more of the system services can be executed concurrently by multiple processors, the system services including;

(a1) scheduling multiple processes into one or more of the processors according the anarchy-based scheduling model,

(a2) allocating space in the common memory among one or more of the processes scheduled for execution in one or more of the processors, and

(a3) providing for accounting, control, monitoring, security, administrative and operator information about any one or more of the processors and processes;

(b) processing a plurality of multithreaded input/output services such that any one or more of the input/output services can be executed concurrently by multiple ones of the processors and a plurality of input/output resources associated with the multiprocessor system, the input/output resources including a plurality of peripheral devices attached to the multiprocessor system via a plurality of external interfaces, the input/output services including

(b1) managing storage of files containing both data and instructions for the multithreaded programs on the peripheral devices,

(b2) distributively processing input/output requests from the processors to the peripheral devices,

(b3) allocating the input/output resources to the processes so as to optimize the usage the input/output resources of the multiprocessor system, and

(b4) supporting input/output requests to other remote processors interconnected with the multiprocessor system; and

interfacing between one or more developers and users of the multithreaded programs and the operating system program so as to present a common visual format for all output representations and input commands for the operating system program and a plurality of program development tools that comprise an integrated parallel user environment for providing compilation, execution and debugging of the multithreaded program.

8. The method of claim 7 wherein the program development tools of the integrated parallel user environment comprise the steps of:

(a) compiling a source code file representing one of the multithreaded programs to produce an executable code file containing one or more processes associated with the multithreaded program;

(b) controlling a development and execution environment for the source code file and executable code file;

(c) controlling a debugging environment in response to execution of the executable code file on the multiprocessor system; and

(d) presenting in response to steps (a), (b) and (c) all of the visual representations and input commands relating to the status, control and execution options available for the multithreaded programs in the common visual format.

9. The method of claim 8 wherein step (a) comprises:

(a1) parsing the source code file and generating an intermediate language representation of the source code file;

(a2) optimizing the organization of the intermediate language representation of the source code file to produce a multithreaded program capable of parallel execution, including generating machine independent optimizations based on the intermediate language representation; and

(a3) generating an object code file based upon the intermediate language representation, including generating machine dependent optimizations based on a machine dependent representation of the intermediate language representation.

10. The method of claim 9 wherein step (b) comprises:

(b1) linking the object code file of the multithreaded program into an executable code file to be executed by the multiprocessor system;

(b2) executing the executable code file in the multiprocessor system; and

(b3) monitoring and tuning the performance of the executable code file, including providing the status, control and execution options available for the developer and user.

11. The method of claim 10 wherein step (c) comprises:

(c1) mapping the source code file to the object code file of the multithreaded program;

(c2) mapping the object code file to the source code file of the multithreaded program; and

(c3) in response to a command from the developer or an interrupt during the step of executing the executable code file, allowing the developer to examine the status of the executable file as it was executing on one or more of the processors by referring directly to one or more statements in the source code file.

12. The method of claim 8 wherein step (d) comprises:

providing a set of icon-represented functions corresponding to the status, control and execution options available for the multithreaded programs; and

providing an equivalent set of command-line functions.