Distributing computations in a parallel processing environment

• US 8,250,507 B1
• Filed: 10/21/2010
• Issued: 08/21/2012
• Est. Priority Date: 05/13/2005
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Agarwal, Anant, Leger, Michelle
• Primary Examiner(s): Parihar, Suchin
• Application Number:
  US12/909,521
• Time in Patent Office: 670 Days
• Field of Search: 716/100, 716/110
• US Class Current: 716/110
• CPC Class Codes: G06F 8/451 Code distribution considering CPU load at run-time G06F9/505; load rebalancing G06F9/5083

Abstract

A system comprises a plurality of computation units interconnected by an interconnection network. A method for configuring the system comprises accepting a set of instructions corresponding to a portion of a program that performs a computation repeatedly; identifying subsets of the instructions; and associating each subset with a different one of the computation units to form a specification of the set of instructions such that execution according to the specification forms a pipeline among at least some of the computation units.

Claims

1. A method for configuring a system comprising a plurality of computation units interconnected by an interconnection network using a computer system, the method comprising:

accepting, by the computer system, a set of instructions corresponding to a portion of a program that performs a computation repeatedly;

identifying subsets of the instructions;

associating the subsets of instructions with different respective ones of the computation units to form a specification for execution of the set of instructions with execution of the set of instructions according to the specification using a pipeline among at least some of the computation units;

loading the specification for execution of the set of instructions into a memory unit accessible to at least one of the computation units; and

distributing the subsets of instructions to the corresponding computation units when the system is booted.

2. The method of claim 1, wherein identifying the subsets of the instructions comprises determining dependencies among subsets of the instructions corresponding to different portions of the computation.

3. The method of claim 2, wherein determining dependencies among subsets of the instructions corresponding to different portions of the computation comprises determining at least one instruction in a first subset that depends on data characterizing an outcome of executing an instruction in a second subset.

4. The method of claim 2, further comprising associating instructions accessing the same data object with the same subset.

5. The method of claim 4, wherein the specification designates the subsets of instructions for execution in respective computation units.

6. The method of claim 4, wherein the data object comprises an array.

7. The method of claim 4, wherein the array comprises a sparse array.

8. The method of claim 2, wherein determining dependencies among subsets of the instructions corresponding to different portions of the computation comprises determining at least one instruction in a first subset that depends on data written by an instruction in a second subset.

9. A computer program product, stored on a computer-readable storage device, for configuring a system comprising a plurality of computation units interconnected by an interconnection network, the computer program comprising instructions for causing a computer system to:

accept a set of instructions corresponding to a portion of a program that performs a computation repeatedly;

identify subsets of the instructions;

associate the subsets of instructions with different respective ones of the computation units to form a specification for execution of the set of instructions with execution of the set of instructions according to the specification using a pipeline among at least some of the computation units;

load the specification for execution of the set of instructions into a memory unit accessible to at least one of the computation units; and

distributing the subsets of instructions to the corresponding computation units when the system is booted.

10. The computer program product of claim 9, further comprising instructions for causing the computer system to generate the instructions corresponding to the portion of the program from a program specification.

11. The computer program product of claim 9, wherein identifying the subsets of the instructions comprises determining dependencies among subsets of the instructions corresponding to different portions of the computation.

12. The computer program product of claim 11, wherein determining dependencies among subsets of the instructions corresponding to different portions of the computation comprises determining at least one instruction in a first subset that depends on data characterizing an outcome of executing an instruction in a second subset.

13. The computer program product of claim 11, further comprising instructions for causing the computer system to associate instructions accessing the same data object with the same subset.

14. The computer program product of claim 13, wherein the specification designates the subsets of instructions for execution in respective computation units.

15. The computer program product of claim 13, wherein the data object comprises an array.

16. The computer program product of claim 15, wherein the array comprises a sparse array.

17. The computer program product of claim 11, wherein determining dependencies among subsets of the instructions corresponding to different portions of the computation comprises determining at least one instruction in a first subset that depends on data written by an instruction in a second subset.