US5274818A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for compiling a fine-grained array based source program onto a course-grained hardware
Assignee: Thinking Machines Corp
•
Filing: 1992-02-03
•
Granted: 1993-12-28
•
Expires: 2012-02-03
Abstract
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.
Inventors
- 👤 Alexander D. Vasilevsky
- 👤 Gary W. Sabot
- 👤 Clifford A. Lasser
- 👤 Lisa A. Tennies
- 👤 Tobias M. Weinberg
- 👤 Linda J. Seamonson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 21:22
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/441; G06F15/00; G06F15/76; G06F15/80; G06F15/8053; G06F15/8092; G06F8/443; G06F8/45
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
110 words
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'.
Claim 2
Dependent Claim
110 words
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'.
Claim 3
Dependent Claim
13 words
The method of claim 1, further comprises the step of optimizing said LIR.
Claim 4
Dependent Claim
15 words
The method of claim 1, wherein said plurality of parallel vector processors are functionally identical.
Claim 5
Dependent Claim
14 words
The method of claim 1, wherein said parallel vector processors form a coarse-grained hardware.
Claim 6
Dependent Claim
35 words
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.
Claim 7
Dependent Claim
29 words
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.
Claim 8
Dependent Claim
29 words
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.
Claim 9
Dependent Claim
69 words
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).
Claim 10
Dependent Claim
37 words
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.
Claim 11
Dependent Claim
123 words
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.
Claim 12
Dependent Claim
123 words
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.
Claim 13
Dependent Claim
117 words
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'.
Claim 14
Dependent Claim
117 words
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'.
Claim 15
Dependent Claim
13 words
The system of claim 11, further comprising optimizer means for optimizing said LIR.
Claim 16
Dependent Claim
15 words
The system of claim 11, wherein said plurality of parallel vector processors are functionally indentical.
Claim 17
Dependent Claim
14 words
The system of claim 11, wherein said parallel vector processors form a coarse-grained hardware.
Claim 18
Dependent Claim
43 words
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.
Claim 19
Dependent Claim
29 words
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.
Claim 20
Dependent Claim
29 words
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.
Claim 21
Dependent Claim
75 words
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).
Claim 22
Dependent Claim
37 words
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.
References Cited (Backward Citations)
US4598400A
Cited
US4667290A
Cited
US4773038A
Cited
US4827403A
Cited
US4984235A
Cited
US5175856A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-12-27 | 1997-06-28 | 1997-12-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-12-27 | 2001-06-28 | 2001-12-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-12-27 | 2005-06-28 | 2005-12-28 | $7700.00 | Window Closed / Lapsed |