System and method for compiling a source code supporting data parallel variables

• US 5,381,550 A
• Filed: 01/10/1994
• Issued: 01/10/1995
• Est. Priority Date: 12/13/1991
• Status: Expired due to Fees

• Current Assignee: TM Patents LP
• Original Assignee: Thinking Machines Corporation (Oracle Corporation)
• Inventors: Seamonson, Linda J., Goldhaber, Steven N., Frankel, James L., Jourdenais, Karen C.
• Primary Examiner(s): Kriess, Kevin A.
• Application Number:
  US08/179,267
• Time in Patent Office: 365 Days
• Field of Search: 395/650, 395/700, 395/600
• US Class Current: 717/149
• CPC Class Codes: G06F 8/41 Compilation
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions

Abstract

A compiler for compiling a computer program which is adapted for use with a data parallel computer. The compiler supports variables which involve parallelism. Variables which involve parallelism are parallel variables, templates for parallel variables called shapes, and pointers to parallel variables. For each variable involving parallelism declared globally in the source code, the compiler of the present invention emits in the target code a declaration of a global scalar variable. It further emits in the target code a start trap. When executed, the start trap allocates memory and a data structure for the global variables involving parallelism. The start trap also initializes the data structures and global variables involving parallelism. Finally, the compiler of the present invention emits in the target code one or more statements which, at run time, will cause the start trap to be invoked before the execution of any statement in which one of the global variables involving parallelism is read from or written to.

Claims

1. A method of generating a target code from a source code, the source code written using a high level language supporting data parallel processing, the target code to be executed in a data parallel computer having a plurality of processing nodes for processing data in parallel, the method being executable in a data processing apparatus and comprising the steps of:

(a) maintaining a shapes defined table which includes a list of shapes which are declared and defined in a compilation unit of the source code;

(b) determining whether a source code declaration statement exists in said compilation unit of the source code which declares a shape having P positions organized among R dimensions, said shape being a template for use in declaring parallel variables each having P data instances distributed among P processing nodes logically organized among R dimensions, said statement specifying a symbol that identifies said shape;

(c) emitting to the target code, in response to said determination, at least one target code declaration statement which when executed in the data parallel computer enables the data parallel computer to declare said shape, said target code declaration statement including a definition field, a symbol field, and an initializer field;

(d) setting said symbol field equal to said symbol of said shape;

(e) ascertaining, in response to said determination, whether said source code declaration statement also defines said shape; and

(f) if it is determined that said source code declaration statement also defines said shape, then adding said symbol of said shape to said shapes defined table.

2. The method of claim 1, also comprising the step of setting said definition field equal to a predetermined value to indicate that the shape is both declared and defined within said compilation unit of the source code if it is determined that said source code declaration statement also defines said shape.

3. The method of claim 1, further comprising the step of emitting to the target code, in response to said determination, an allocation function which when executed in the data parallel computer enables the data parallel computer to allocate said shape to a processor set, said processor set comprising P of the processing nodes.

4. The method of claim 3, further comprising the step of setting said initializer field equal to a value which identifies said allocation function.

5. The method of claim 1, further comprising the step of maintaining a shapes referenced table which includes a list of shapes which are declared but not defined in said compilation unit of the source code.

6. The method of claim 5, further comprising the following steps which are performed if it is determined that said source code declaration statement does not define said shape:

setting said definition field equal to a predetermined value to indicate that the shape is declared but not defined within said compilation unit of the source code; and

adding said symbol of said shape to said shapes referenced table.

7. The method of claim 6, further comprising the step of emitting to the target code an end compilation unit statement which when executed in the data parallel computer enables the data parallel computer to establish said shapes defined table and said shapes referenced table in at least one memory of the data parallel computer.

8. The method of claim 7, further comprising the steps of:

emitting to the target code an allocation function for each shape declared and defined in the source code which when executed in the data parallel computer enables the data parallel computer to allocate said each shape to a processor set comprising a subset of the processing nodes;

emitting to the target code at least one statement which when executed in the data parallel computer enables the data parallel computer to invoke allocation functions associated with shapes listed in said shapes defined table stored in said at least one memory of the data parallel computer; and

emitting to the target code at least one statement which when executed in the data parallel computer enables the data parallel computer to invoke allocation functions associated with shapes listed in said shapes referenced table stored in said at least one memory of the data parallel computer.

9. A method of generating a target code from a source code, the source code written using a high level language supporting data parallel processing, the target code to be executed by a data parallel computer comprising a plurality of processing nodes for processing data in parallel, the method being executable in a data processing apparatus and comprising the steps of:

(a) maintaining a parallel variables defined table which includes a list of parallel variables which are declared and defined in a compilation unit of the source code;

(b) determining whether a source code declaration statement exists in said compilation unit of the source code which declares a parallel variable comprising a plurality of data instances each processed by one of the processing nodes when the target code is executed by the data parallel computer, said source code declaration statement specifying a symbol that identifies said parallel variable;

(c) emitting to the target code, in response to said determination, at least one target code declaration statement which when executed in the data parallel computer enables the data parallel computer to declare said parallel variable, said target code declaration statement including a definition field, a symbol field, and an initializer field;

(d) setting said symbol field equal to said symbol of said parallel variable;

(e) ascertaining, in response to said determination, whether said source code declaration statement also defines said parallel variable; and

(f) if it is determined that said source code declaration statement also defines said parallel variable, then adding said symbol of said parallel variable to said parallel variables defined table.

10. The method of claim 9, also comprising the step of setting said definition field equal to a predetermined value to indicate that said parallel variable is both declared and defined within said compilation unit of the source code if it is determined that said source code declaration statement also defines said parallel variable.

11. The method of claim 9, further comprising the following steps which are performed if it is determined that said source code declaration statement also defines said parallel variable:

maintaining a parallel variable group table comprising a list of parallel variables;

emitting to the target code at least one statement which when executed in the data parallel computer enables the data parallel computer to allocate to said parallel variable group an unused field from a memory heap in each of the processing nodes; and

if it is determined that said source code declaration statement also defines said parallel variable, then adding said symbol of said parallel variable to said parallel variable group.

12. The method of claim 11, further comprising the following steps which are executed if it is determined that said source code declaration statement also defines said parallel variable:

emitting to the target code at least one statement which when executed in the data parallel computer enables the data parallel computer to assign a portion of said allocated field in each of the processing nodes to data instances of said parallel variable; and

emitting to the target code at least one statement which when executed in the data parallel computer enables the data parallel computer to assign other portions of said allocated field in each of the processing nodes to data instances of other parallel variables in said parallel variable group.

13. The method of claim 11, wherein said target code declaration statement also includes a heap size field, the method also comprising the step of setting said heap size field equal to a value which identifies the amount of unused memory heap fields allocated to parallel variables listed in said parallel variable group table.

14. The method of claim 9, further comprising the following steps which are executed if it is determined that said source code declaration statement also defines said parallel variable:

emitting to the target code an initialization function which, when executed by the data parallel computer, enables the data parallel computer to initialize data instances of the parallel variable; and

setting said initializer field equal to a value which identifies said initialization function.

15. The method of claim 9, wherein said source code declaration statement also specifies a shape of said parallel variable, and wherein said target code declaration statement also includes a shape field, the method also comprising the step of setting said shape field equal to a value which identifies said shape of said parallel variable.

16. The method of claim 9, further comprising the step of maintaining a parallel variables referenced table which includes a list of parallel variables which are declared but not defined in said compilation unit of the source code.

17. The method of claim 16, further comprising the following steps which are executed if it is determined that said source code declaration statement does not define said parallel variable:

setting said definition field equal to a predetermined value to indicate that said parallel variable is declared but not defined within said compilation unit of the source code; and

adding said symbol of said parallel variable to said parallel variables referenced table.

18. The method of claim 17, further comprising the step of emitting to the target code an end compilation unit statement which when executed in the data parallel computer enables the data parallel computer to establish said parallel variables defined table and said parallel variables referenced table in at least one memory of the data parallel computer.

19. The method of claim 18, also comprising the steps of:

emitting to the target code an allocation function for each parallel variable declared and defined in the source code which when executed in the data parallel computer enables the data parallel computer to allocate memory in the processing nodes for data instances of said each parallel variable;

emitting to the target code at least one statement which when executed in the data parallel computer enables the data parallel computer to invoke allocation functions associated with parallel variables listed in said parallel variables defined table stored in said at least one memory of the data parallel computer; and

emitting to the target code at least one statement which when executed in the data parallel computer enables the data parallel computer to invoke allocation functions associated with parallel variables listed in said parallel variables referenced table stored in said at least one memory of the data parallel computer.