System and method for compiling a fine-grained array based source program onto a course-grained hardware

• US 5,274,818 A
• Filed: 02/03/1992
• Issued: 12/28/1993
• Est. Priority Date: 02/03/1992
• Status: Expired due to Fees

• Current Assignee: TM Patents LP
• Original Assignee: Thinking Machines Corporation (Oracle Corporation)
• Inventors: Vasilevsky, Alexander D., Lasser, Clifford A., Weinberg, Tobias M., Tennies, Lisa A., Seamonson, Linda J., Sabot, Gary W.
• Primary Examiner(s): Kriess, Kevin A.
• Assistant Examiner(s): Spivak, Kevin
• Application Number:
  US07/827,942
• Time in Patent Office: 694 Days
• Field of Search: 395/700, 395/650, 364/300
• US Class Current: 717/149
• CPC Class Codes: G06F 15/8092 Array of vector units
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions

Abstract

The present invention provides a parallel vector machine model for building a compiler that exploits three different levels of parallelism found in a variety of parallel processing machines, and in particular, the Connection Machine® Computer CM-2 system. The fundamental idea behind the parallel vector machine model is to have a target machine that has a collection of thousands of vector processors each with its own interface to memory. Thus allowing a fine-grained array-based source program to be mapped onto a course-grained hardware made up of the vector processors. In the parallel vector machine model used by CM Fortran 1.0, the FPUs, their registers, and the memory hiearchy are directly exposed to the compiler. Thus, the CM-2 target machine is not 64K simple bit-serial processors. Rather, the target is a machine containing 2K PEs (processing elements), where each PE is both superpipelined and superscalar. The compiler uses data distribution to spread the problem out among the 2K processors. A new compiler phase is used to separate the code that runs on the two types of processors in the CM-2; the parallel PEs, which execute a new RISC-like instruction set called PEAC, and the scalar front end processor, which executes SPARC or VAX assembler code. The pipelines in PEs are filled by using vector processing techniques along the PEAC instruction set. A scheduler overlaps the execution of a number of RISC operations.

Claims

1. A computer implemented method of compiling a fine-grained array based source program written for a parallel machine, comprising the steps of:

(1) entering said source program into a front end of a compiler, wherein said front end produces a common intermediate representation (CIR) syntax tree;

(2) building a lowered intermediate representation (LIR) from said CIR syntax tree by performing a bottom-up walk of said CIR syntax tree;

(3) mapping said LIR into a more detailed LIR'"'"', said LIR'"'"' marks which code will run on a scalar front-end processor and which code will run on a plurality of parallel vector processors; and

(4) generating two separate code streams from said LIR'"'"'.

2. The method of claim 1, further comprises the step of optimizing said LIR.

3. The method of claim 1, wherein said plurality of parallel vector processors are functionally identical.

4. The method of claim 1, wherein said parallel vector processors form a coarse-grained hardware.

5. The method of claim 1, wherein said step (4) generates a scalar code stream that will operate on a scalar machine and a virtual register code stream that will operate on a parallel vector machine.

6. The method of claim 5, wherein said second code stream includes vector instructions which are used to control said parallel vector machine which generally processes said vector instructions concurrently.

7. The method of claim 5, further comprises the step of generating first object code for a scalar processor and second object code for said plurality of parallel vector processors.

8. The method of claim 7, wherein in said step of generating object code for said plurality of vector processors, comprises the steps of:

(a) replacing the virtual registers with actual data processor registers and sequence pointer registers;

(b) transforming the code generated in step (a) to overlap loads and stores;

(c) optimizing the code generated in step (b); and

(d) generating microcode from said optimized code of step (c).

9. The method of claim 7, wherein said first object code and said second object code are linked with a run time library in order to produce executable code, wherein said run time library operates on slicewise data.

10. A computer implemented method of compiling a source program for coarse-grained parallel machine, comprising the steps of:

(1) receiving a source program written in a fine-grained array-based programming language;

(2) translating said source program into target code which includes vector instruction, said target code operates on a coarse-grained hardware that processes said code concurrently and utilizes at least one register file, wherein said coarse-grained parallel machine contains a plurality of vector processors, said plurality of vector processors contains a plurality of functional units, the pipeline of said plurality of functional units being of equal or unequal length; and

(3) treating said at least two functional units, if said at least two functional units have a pipeline of unequal length, as having equal length.

11. A computer implemented method of compiling a fine-grained array based source program written for a parallel machine, comprising the steps of:

(a) front end means for receiving a source program, wherein said front end means produces a common intermediate representation (CIR) syntax tree;

(b) building means for building a lowered intermediate representation (LIR) from said CIR syntax tree by performing a bottom-up walk of said CIR syntax tree;

(c) mapping means for mapping said LIR into a more detailed LIR'"'"', said LIR'"'"' marks which code will run on a scalar front-end processor and which code will run on a plurality of parallel vector processors; and

(d) generating means for generating two separate code streams from said LIR'"'"'.

12. The system of claim 11, further comprising optimizer means for optimizing said LIR.

13. The system of claim 11, wherein said plurality of parallel vector processors are functionally indentical.

14. The system of claim 11, wherein said parallel vector processors form a coarse-grained hardware.

15. The system of claim 11, wherein said generating means further comprises a first means for generating a scalar code stream that will operate on a scalar machine and for generating a virtual register code stream that will operate on a parallel vector machine.

16. The system of claim 15, wherein said second code stream includes vector instructions which are used to control said parallel vector machine which generally processes said vector instructions concurrently.

17. The system of claim 15, further comprising second means for generating first object code for a scalar processor and second object code for said plurality of parallel vector processors.

18. The system of claim 17, wherein said second means further comprises generating object code for said plurality of vector processors, comprising:

(a) means for replacing the virtual registers with actual actual data processor registers and sequence pointer registers;

(b) means for transforming the code generated in step (a) to overlap loads and stores;

(c) means for optimizing the code generated instep (b); and

(d) means for generating microcode from said optimized code of step (c).

19. The method of claim 17, wherein said first object code and said second object code are linked with a run time library in order to produce executable code, wherein said run time library operates on slicewise data.