Scalable parallel processing on shared memory computers

• US 7,454,749 B2
• Filed: 11/12/2002
• Issued: 11/18/2008
• Est. Priority Date: 11/12/2002
• Status: Active Grant

• Current Assignee: Innovations In Memory LLC
• Original Assignee: Engineered Intelligence Corporation
• Inventors: Oberdorfer, Matthias
• Primary Examiner(s): Lee, Thomas
• Assistant Examiner(s): Abbaszadeh, Jaweed A
• Application Number:
  US10/293,791
• Publication Number:
  US 20040093477A1
• Time in Patent Office: 2,198 Days
• Field of Search: 718/1, 718100-108, 712/22
• US Class Current: 718/1
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

A virtual parallel computer is created within a programming environment comprising both shared memory and distributed memory architectures. At run time, the virtual architecture is mapped to a physical hardware architecture. In this manner, a massively parallel computing program may be developed and tested on a first architecture and run on a second architecture without reprogramming.

Claims

1. A method of parallel processing on a computer array comprising the steps of:

creating a virtual single process multiple data computer system comprising an array controller and a plurality of parallel processing units, said array controller having a shared memory and each of said parallel processing units having a dedicated local memory;

creating programs for each of said parallel processing units wherein each of said programs performs a predetermined function on predetermined data stored on said dedicated memory of each parallel processing unit and each of said programs shares data directly with other programs of said programs using a shared memory architecture such that said array controller and said parallel processing units operate virtually as a single process multiple data computer;

determining a topology of a physical hardware configuration on which said virtual single process multiple data computer system will execute said programs, said topology having at least one computing node;

allocating at least one of said parallel processing units to at least one of said computing nodes based upon a distribution algorithm;

transferring said programs and said data to said computing nodes for each of said parallel processing units; and

executing said programs for said parallel processing units on said computing nodes.

2. The method of claim 1 wherein said virtual single process multiple data computer system comprises at least one single program multiple data virtual computer.

3. The method of claim 2 wherein said virtual single process multiple data computer system contains a plurality of single program multiple data virtual computers.

4. The method of claim 1 wherein said distribution algorithm comprises estimating an amount of time required for each of said parallel processing units to process said programs.

5. The method of claim 1 wherein said programs include at least one barrier statement wherein all of said programs are executed until one of said barrier statements is reached before processing continues on any of said programs past said barrier statement.

6. The method of claim 1 further comprising:

creating a virtual parallel processing computer system comprising a plurality of virtual single process multiple data computer systems and a sequencer, each of said plurality of virtual single process multiple data computer systems being an instance of said virtual single process multiple data computer system;

coordinating tasks between said plurality of virtual single process multiple data computers with said sequencer; and

passing data between said plurality of virtual single process multiple data computers using a message passing architecture.

7. A computer programming environment for parallel computing comprising:

at least one computer arranged in a hardware topology to create said computer programming environment, said at least one computer performing various processes of said computer programming environment;

an array controller having a shared memory;

a plurality of parallel processing units, each of said parallel processing units having a dedicated local memory;

an editor process that creates a virtual single process multiple data computer system comprising said array controller and said a plurality of parallel processing units, said editor further creates programs for each of said parallel processing units wherein each of said programs performs a predetermined function on predetermined data stored on said dedicated memory of each parallel processing unit and each of said programs shares data directly with other programs of said programs using a shared memory architecture such that said array controller and said parallel processing units operate virtually as a single process multiple data computer;

a virtual computer loader sub-process that determines a topology of a physical hardware configuration on which said virtual single process multiple data computer system will execute said programs, said topology having at least one computing node, said loader sub-process further allocates at least one of said parallel processing units to at least one of said computing nodes based upon a distribution algorithm and transfer said programs and said data to said nodes for each of said parallel processing units; and

a virtual computer execution process that executes said programs for said parallel processing units.

8. The computer programming system system of claim 7 wherein said virtual single process multiple data computer system comprises at least one single program multiple data virtual computer.

9. The computer programming system of claim 8 wherein said virtual single process multiple data computer system contains a plurality of single program multiple data virtual computers.

10. The computer programming system of claim 7 wherein said distribution algorithm comprises estimating an amount of time required for each of said parallel processing units to process said programs.

11. The computer programming system of claim 7 wherein said programs include at least one barrier statement, wherein all of said programs are executed until one of said barrier statements is reached before processing continues on any of said programs past said barrier statement.

12. The computer programming system environment of claim 7 further comprising:

a supplementary editor system that creates a virtual parallel processing computer system comprising a plurality of virtual single process multiple data computer systems and a sequencer, each of said plurality of virtual single process multiple data computer systems being an instance of said virtual single process multiple data computer system;

a sequencer that coordinates tasks between said plurality of virtual single process multiple data computers; and

a message passing system that passes data between said plurality of virtual single process multiple data computers using a message passing architecture.

13. A parallel processing computer system comprising:

at least one computing node comprising at least one processor, said computing node connected to a network;

an editing system that creates a virtual single process multiple data computer system comprising an array controller and a plurality of parallel processing units, said array controller having a shared memory and each of said parallel processing units having a dedicated local memory, said editor further creates programs for each of said parallel processing units wherein each of said programs performs a predetermined function on predetermined data stored on said dedicated memory of each parallel processing unit and each of said programs shares data directly with other programs of said programs using a shared memory architecture such that said array controller and said parallel processing units operate virtually as a single process multiple data computer; and

a system controller computer comprising a virtual computer loader routine that determines a topology of a physical hardware configuration on which said virtual single process multiple data computer will execute said programs, said topology comprising said at least one computing node, said loader routine further allocates at least one of said parallel processing units to at least one of said computing nodes based upon a distribution algorithm and transfer said programs and said data to said nodes for each of said parallel processing units, and a virtual computer execution routine that executes at least two of said programs for said parallel processing units substantially simultaneously.

14. The parallel processing computer system of claim 13 wherein said compute node, said editing system, and said system controller computer are the same computer.

15. The parallel processing computer system of claim 13 further comprising a plurality of compute nodes.

16. The parallel processing computer system of claim 15 wherein at least one of said compute nodes comprises a plurality of processors.

17. The parallel processing computer system of claim 13 wherein said virtual parallel single process multiple data system comprises at least one single program multiple data virtual computer.

18. The parallel processing computer system of claim 17 wherein said virtual single process multiple data computer system contains a plurality of single program multiple data virtual computers.

19. The parallel processing computer system of claim 13 wherein said distribution algorithm comprises estimating an amount of time required for each of said parallel processing units to process said programs.

20. The parallel processing computer system of claim 13 wherein said programs include at least one barrier statement, wherein all of said programs are executed until one of said barrier statements is reached before processing continues on any of said programs past said barrier statement.

21. The parallel processing computer system of claim 13 further comprising:

a supplementary editor system that creates a virtual parallel processing computer system comprising a plurality of virtual single process multiple data computer systems and a sequencer, each of said plurality of virtual single process multiple data computer systems being an instance of said virtual single process multiple data computer system;

a sequencer that coordinates tasks between said plurality of virtual single process multiple data computers; and

a message passing system that passes data between said plurality of virtual single process multiple data computers using a message passing architecture.