Compiler for performing incremental live variable analysis for data-parallel programs

Abstract

A compiler for compiling a computer program wherein the computer program is adapted for use with a data parallel computer. The compiler comprises an optimizer which optimizes the compiled code. In optimizing the compiled code, the optimizer performs live variable analysis. With regard to performing live variable analysis, the optimizer of the present invention is adapted for use with data parallel languages. Additionally, the optimizer is computationally efficient at compile time. Further, the optimizer operates in an incremental manner.

Claims

What is claimed is:

1. A system for generating an object code program to be executed by a target computer comprising a processor array comprising a plurality of processing nodes for processing data in parallel, in response to a source code program written in a high-level language, the high-level language including a plurality of instructions, at least some of the instructions including an always variant to be executed by all of the processing nodes regardless of a context condition and a non-always variant to be executed on ones of the processing nodes having a selected context condition, said system including:

(a) intermediate representation generating means for generating an intermediate representation in response to the source code program, the intermediate representation having a series of intermediate representation nodes representative of source code instructions, at least some intermediate representation nodes each including at least one variable used as a referenced variable and at least some intermediate representation nodes each including at least one variable used as a destination variable;

(b) a definition/use set generating means for generating, in response to the intermediate representation, a definition set and a use set, the use set identifying those variables which are first used in the intermediate representation node series as (i) referenced variables in any intermediate representation nodes or (ii) first destination variables in intermediate representation nodes representing non-always instruction variants, and the definition set identifying those variables which are otherwise first used in the intermediate representation node series as destination variables;

(c) optimization means for generating an optimized intermediate representation in response to the intermediate representation generated by the intermediate representation generating means and the definition set and the use set generated by the definition/use set generating means.

2. A system as defined in claim 1 in which the definition/use set generating means comprises:

(A) definition set and use set establishment means for initializing a definition set and a use set for variables in the intermediate representation;

(B) intermediate representation node selection means for selecting an intermediate representation node;

(C) use set reference addition means for determining, for each variable which is a reference variable in the selected intermediate representation node, whether the definition set identifies the variable and if not adding an identification of the variable to the use set;

(D) instruction type determination means for determining whether the instruction represented by the selected intermediate representation node is a non-always variant;

(E) contextual definition set reference addition means for, in response to a positive determination by the instruction type of determination means, determining, for each destination variable identified in the intermediate reference node, whether the definition set identifies the destination variable and if not adding the identification of the destination variable to the use set;

(F) definition set reference addition means for determining, for each destination variable identified in the intermediate reference node, whether the use set identifies the destination variable and if not adding an identification of the destination variable to the definition set; and

(G) iteration control means for controlling the intermediate representation node selection means, the use set reference addition means, the instruction type determination means, the contextual definition set reference addition means and the definition set reference addition means through a series of intermediate representation node selection means selecting successive intermediate representation nodes in the series in successive iterations.

3. A system as defined in claim 1 in which the intermediate representation generating means generates the intermediate representation as a series of blocks and establishes for each block a change status flag having a changed condition and an unchanged condition, the intermediate representation generating means initializing each block's status flag to the changed condition, the definition/use set generating means further includes a status flag conditioning means for conditioning the status flag of each block to the unchanged condition after establishing the definition set and the use set for each block.

4. A computer-implemented method of generating an object code program to be executed by a target computer comprising a processor array comprising a plurality of processing nodes for processing data in parallel, in response to a source code program written in a high-level language, the high-level language including a plurality of instructions, at least some of the instructions including an always variant to be executed by all of the processing nodes regardless of a context condition and a non-always variant to be executed on ones of the processing nodes having a selected context condition, said computer-implemented method including the steps of:

(1) generating an intermediate representation in response to the source code program, said intermediate representation having a series of intermediate representation nodes representative of source code instructions, at least some intermediate representation nodes each including at least one variable used as a referenced variable and at least some intermediate representation nodes each including at least one variable used as a destination variable;

(2) generating, in response to said intermediate representation, a definition set and a use set, said use set identifying those variables which are first used in said intermediate representation node series as (i) reference representation nodes or (ii) first destination variables in intermediate representation nodes representing non-always instruction variants, and said definition set identifying those variables which are otherwise first used in said intermediate representation node series as destination variables; and

(3) generating an optimal intermediate representation in response to said intermediate representation and said definition set and said use set.

5. A method as defined in claim 4 in which said definition set and use set generating step comprises the steps of iteratively:

(a) selecting an intermediate representation node, during successive iterations successive ones of said intermediate representation nodes in said intermediate representation being selected;

(b) determining, for each variable which is a reference variable in said selected intermediate representation node, whether said definition set identifies said

(c) determining whether the instruction represented by said selected intermediate representation node is a non-always variant and in response to a positive determination, determining, for each destination variable identified in said intermediate reference node, whether said definition set identifies said destination variable and if not adding an identification of said destination variable to said use set; and

(d) determining, for each destination variable identified in said intermediate reference node, whether said use set identifies said destination variable and if not adding an identification of said destination variable to said definition set.

6. A method as defined in claim 4 in which said intermediate representation is generated as a series of blocks, for each block a change status flag being established initially having a changed condition and an unchanged condition, said status flag of each block being changed to said unchanged condition after establishing said definition set and said use set for each block.

7. The method of claim 4, wherein said intermediate representation is generated as a series of blocks, wherein a status flag associated with each block is initialized to a first value.

8. The method of claim 7, further comprising the step of checking said flag associated with a block to determine whether it is set to said first value, and if so, then,

(a) generating said definition set and said use set for said block;

(b) generating from said intermediate representation, said definition set, and said use set a reach-in set and a reach-out set for said block;

(c) generating from said definition set, said use set, said reach-in set, and said reach-out set a live-in set and a live-out set for said block; and

(d) determining from said intermediate representation and said live-out set which variables are live at each intermediate representation node in said block.

9. The method of claim 8, wherein step (a) of generating said definition set and said use set comprises the steps of iteratively:

(i) selecting an intermediate representation node, during successive iterations successive ones of said intermediate representation nodes in said intermediate representation being selected;

(ii) determining, for each variable which is a reference variable in said selected intermediate representation node, whether said definition set identifies said variable and if not adding an identification of said variable to said use set;

(iii) determining whether said instruction represented by said selected intermediate representation node is a non-always variant and in response to a positive determination, determining, for each destination variable identified in said intermediate reference node, whether said definition set identifies said destination variable and if not adding an identification of said destination variable to said use set; and

(iv) determining, for each destination variable identified in said intermediate reference node, whether said use set identifies said destination variable and if not adding an identification of said destination variable to the definition set.

10. The method of claim 8, further comprising the step of repeating steps (a) through (d) for all blocks in said intermediate representation.

11. The method of claim 8, wherein step (b) comprises the step of:

(i) determining whether said flag associated with said block is set to said first value, and if so, then (A) set said reach-in set associated with said block equal to the union of said blocks parents' reach-out sets, (B) set said reach-out set associated with said block equal to the set union of said reach-in set, said definition set, and said use set associated with said block, and (C) setting said flag associated with said block to a second value; and

(ii) determining whether said reach-out set associated with said block changed, and if so, then setting a flag associated with the children of said block to a first value.

12. The method of claim 11, further comprising the step of repeating steps (i) and (ii) for each block in said intermediate representation.

13. The method of claim 11, further comprising the steps of saving the status of said flag for each block before step (i) and restoring said flag for each of said blocks once it is determined that the reach-out set associated with all of said blocks has not changed during the previous iteration.

14. The method of claim 11, wherein blocks are processed in depth-first traversal order.

15. The method of claim 8, wherein step (c) comprises the step of reducing the size of said live-out set associated with one of said blocks by intersecting said live-out set and said reach-out set.

16. The method of claim 8, wherein step (c) comprises the steps of:

(i) determining whether said flag associated with said block is set to said first value, and if not, then stopping;

(ii) setting said live out set associated with said block equal to a union of the live-in sets of the children of said block;

(iii) setting said live-in set associated with said block equal to a set union of said use set of said block and a set difference of said live-out set and said definitions set associated with said block;

(iv) setting said flag associated with said block to a second value; and

(v) determining whether said live-in set associated with said block has changed, and if so, then setting said flag associated with the parents of said block to said first value.

17. The method of claim 16, further comprising the steps of determining whether any of said live-in sets associated with any of said blocks has changed, and if so, then traversing in a reversal of depth first traversal order each block in said intermediate representation while performing steps (i) through (v) for each block.

18. The method if claim 17, further comprising the steps of setting for each of said blocks said live-in set equal to the intersection of said live-in sat and said reach-in set, and setting for each of said blocks said live-out set equal to the intersection of said live-out set and said reach-out set.

19. The method of claim 8, wherein step (d) comprises the steps of:

(i) initializing a live set for said block equal to said live-out set of said block;

(ii) determining whether a destination of a selected intermediate representation node in said block is a parallel variable, and if not, then deleting said destination from said live set and advancing to step (v);

(iii) determining whether said selected intermediate representation node is an always instruction, but not a send or a writeval instruction, and if so, then deleting said destination from said live set and advancing to step (v);

(iv) adding said destination to said live set; and

(v) adding references in said selected intermediate representation node to said live set.

20. The method of claim 19, further comprising a step of saving said live set prior to performing step (ii).

21. The method of claim 19, further comprising the step of repeating steps (i) through (v) for every node in said block.

22. The method of claim 8, further comprising a step of updating a conflict set, said conflict set includes a list of variables which are simultaneously live in any of the intermediate representation nodes in each of said blocks.

23. A system for generating an object code program to be executed by a target computer comprising a processor array comprising a plurality of processing nodes for processing data in parallel, in response to a source code program written in a high-level language, the high-level language including a plurality of instructions, at least some of the instructions including an always variable to be executed by all of the processing nodes regardless of a context condition and a non-always variant to be executed on ones of the processing nodes having a selected context condition, said system including:

(a) a computer for performing data processing operations; and

(b) a control arrangement for controlling data processing operations performed by the computer, the control arrangement comprising:

(i) an intermediate representation generating module for enabling the computer to generate an intermediate representation in response to the source code program, the intermediate representation having a series of intermediate representation nodes representative of source code instructions, at least some intermediate representation nodes each including at least one variable used as a referenced variable and at least some intermediate representation nodes each including at least one variable used as a destination variable;

(ii) a definition/use set generating module for enabling the computer to generate, in response to the intermediate representation, a definition set and a use set, the use set identifying those variables which are first used in the intermediate representation node series as (i) referenced variables in any intermediate representation nodes or (ii) destination variables in intermediate representation nodes representing non-always instruction variants, and the definition set identifying those variables which are otherwise first used in the intermediate representation node series as destination variables; and

(iii) an optimization module for enabling the computer to generate an optimized intermediate representation in response to the intermediate representation and the definition set and the use set.

24. A system as defined in claim 23 in which the definition/use set generating module comprises:

(A) definition set and use set establishment module for enabling the computer to initialize a definition set and a use set for variables in the intermediate representation;

(B) an intermediate representation node selection module for enabling the computer to select an intermediate representation node;

(C) a use set reference addition module for enabling the computer to determine, for each variable which is a reference variable in the selected intermediate representation node; whether the definition set identifies the variable and if not to enable the computer to add an identification of the variable to the use set;

(D) an instruction type determination module for enabling the computer to determine whether the instruction represented by the selected intermediate representation node is a non-always variant;

(E) a contextual definition set reference addition module for enabling the computer to, in response to a determination that the instruction represented by the selected intermediate representation node is a non-always invariant, whether the definition set identifies the destination variable and if not to enable the computer to add the identification of the destination variable to the use set;

(F) a definition set reference addition module for enabling the computer to determine, for each destination variable identified in the intermediate reference node, whether the use set identifies the destination variable and if not to enable the computer to add an identification of the destination variable to the definition set; and

(G) an iteration control module for enabling the computer to operate in response to the intermediate module, the contextual definition set reference addition module and the definition set reference addition module through a series of iterations, the intermediate representation node selection module enabling the computer to select successive intermediate representation nodes in a series in successive iterations.

25. A system as defined in claim 23 in which the intermediate representation generating module enables the computer to generate the intermediate representation as a series of basic blocks and establish for each basic block a change status flag having a changed condition and an unchanged condition, the intermediate representation generating module enabling the computer to initialize each basic block's status flag to the changed condition, the definition/use set generating module further enabling the computer to condition the status flag of each basic block to the unchanged condition after establishing the definition set and the use set for each basic block.

26. A control arrangement for use in controlling a computer to facilitate generation of an object code program to be executed by a target computer, the target computer comprising a processor array comprising a plurality of processing nodes for processing data in parallel, the computer generating the object code program in response to a source code program written in a high-level language, the high-level language including a plurality of instructions, at least some of the instructions including an always variant to be executed by all of the processing nodes regardless of a context condition and a non-always variant to be executed on one of the processing nodes having a selected context condition, said control arrangement comprising:

(a) an intermediate representation generating module for enabling the computer to generate an intermediate representation in response to the source code program the intermediate representation having a series of intermediate representation nodes representative of source code instructions, at least some intermediate representation nodes each including at least one variable used as a referenced variable and at least some intermediate representation nodes each including at least one variable used as a destination variable;

(b) a definition/use set generating module for enabling the computer to generate, in response to the intermediate representation, a definition set and a use set, the use set identifying those variables which are first used in the intermediate representation node series as (i) referenced variables in any intermediate representation nodes or (ii) destination variables in intermediate representation nodes representing non-always instruction variants, and the definition set identifying those variables which are otherwise first used in the intermediate representation node series as destination variables; and

(c) an optimization module for enabling the computer to generate an optimized intermediate representation in response to the intermediate representation and the definition set and the use set.

27. A control arrangement as defined in claim 26 in which the definition/use set generating module comprises:

(A) a definition set and use set establishment module for enabling the computer to initialize a definition set and a use set for variables in the intermediate representation;

(B) an intermediate representation node selection module for enabling the computer to select an intermediate representation node;

(C) a use set reference addition module for enabling the computer to determine, for each variable which is a reference variable in the selected intermediate representation node; whether the definition set identifies the variable and if not to enable the computer to add an identification of the variable to the use set;

(D) an instruction type determination module for enabling the computer to determine whether the instruction represented by the selected intermediate representation node is a non-always variant;

(E) a contextual definition set reference addition module for enabling the computer to, in response to a determination that the instruction represented by the selected intermediate representation node is a non-always invariant, whether the definition set identifies the destination variable and if not to enable the computer to add the identification of the destination variable to the use set;

(F) a definition set reference addition module for enabling the computer to determine, for each destination variable identified in the intermediate reference node, whether the use set identifies the destination variable and if not to enable the computer to add an identification of the destination variable to the definition set; and

(G) an iteration control module for enabling the computer to operate in response to the intermediate representation node selection module, the use set reference module, the instruction type determination module, the contextual definition set reference addition module and the definition set reference addition module through a series of iterations, the intermediate representation node selection module enabling the computer to select successive intermediate representation nodes in the series in successive iterations.

28. A control arrangement as defined in claim 26 in which the intermediate representation generating module enables the computer to generate the intermediate representation as a series of blocks and establish for each block a change status flag having changed a condition and an unchanged condition, the intermediate representation generating module enabling the computer to initialize each block's status flag to the changed condition, the definition/use set generating module further enabling the computer to condition the status flag of each block to the unchanged condition after establishing the definition set and the use set for each block.

Description

A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.

CROSS-REFERENCE TO OTHER APPLICATIONS

The following applications are assigned to the assignee of the present application:

U.S. patent application Ser. No. 07/042,761, filed Apr. 27, 1987, by W. Daniel Hillis, now U.S. Pat. No. 5,050,069, entitled "Method and Apparatus for Simulating M-Dimensional Connection Networks in an N-Dimensional Network Where M is Less Than N", incorporated herein by reference.

U.S. patent application Ser. No. 07/788,052, filed Nov. 5, 1991, by Frankel et al., entitled "A Compiler For Parallel Communication Instructions", incorporated herein by reference.

U.S. patent application Ser. No. 07/788,004, filed Nov. 5, 1991, by Frankel et al., entitled "System and Method For Parallel Variable Optimization", incorporated herein by reference.

U.S. patent application Ser. No. 07/788,003, filed Nov. 5, 1991, by Frankel et al., entitled "System and Method For Shape Selection and Contextualization", incorporated herein by reference.

INCORPORATION BY REFERENCE

U.S. Pat. 4,589,400, issued Jul. 1, 1986, to W. Daniel Hillis, for "Method and Apparatus for Routing Message Packets", and assigned to the assignee of the present application, incorporated herein by reference.

U.S. Pat. 4,984,235, issued Jan. 8, 1991, to Hillis et al., for "Method and Apparatus for Routing Message Packets and Recording the Routing Sequence", and assigned to the assignee of the present application, incorporated herein by reference.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to a system and method for compiling a computer program, and more particularly to a system and method for compiling a computer program wherein the computer program is adapted for use with a data parallel computer.

2. Related Art

Optimization of computer code generated by a compiler often requires that live variable analysis be performed. This analysis yields the range of program locations within which each variable is said to be live. A variable is alive at a program location if the value stored in the variable is needed later and cannot be altered.

The information produced by live variable analysis can be used in a number of ways to optimize a program. For example, if two variables have live ranges that do not overlap, then these variables may share the same storage location in the primary memory of the target computer system. As a second example, if a computer instruction stores its result in a variable which has been determined to be dead at that point, then the result of the instruction is never used later, and the instruction may be deleted from the program. This is conventionally called dead code elimination. Thus, the use of live variable information can result in both space and time improvements to a program.

Methods for conducting live variable analysis are well known. For example, a conventional method for live variable analysis is described in Compilers, Principles, Techniques, and Tools by Aho et al. However, such conventional methods are flawed for a number of reasons. For example, conventional methods for live variable analysis are not adapted for use with data parallel languages. Also, conventional methods for live variable analysis are computationally expensive at compile time.

Therefore, an efficient method for live variable analysis for use with data parallel languages is required.

SUMMARY OF THE INVENTION

The present invention is directed to a system and method for compiling a computer program, and more particularly to a compiler for compiling a computer program wherein the computer program is adapted for use with a data parallel computer. The compiler comprises an optimizer which optimizes the compiled code. In optimizing the compiled code, the optimizer performs live variable analysis.

With regard to performing live variable analysis, the optimizer of the present invention is adapted for use with data parallel languages. Additionally, the optimizer is computationally efficient at compile time. Further, the optimizer operates in an incremental manner.

The optimizer includes an incremental live variable analysis component. According to the present invention, the incremental live variable analysis component performs the incremental live variable analysis. The incremental live variable analysis component includes a definition/use module, a reaching definitions module, a live variable module, and a live variable traversal module. The incremental live variable analysis component operates generally as follows.

First, the def/use module receives unoptimized IR code and generates a definition set (referred to as defset) and a usages set (referred to as useset) for each basic block contained in the unoptimized IR code. Then, the reaching definitions module receives the unoptimized IR code and the defsets and usesets and generates, for each basic block, a reach in set and a reach out set. Then, the live variable module receives the defsets, usesets, reach in sets, and reach out sets and generates, for each basic block, a live in set and a live out set. Finally, the live variable traversal module receives the unoptimized IR code and the live out sets and determines which variables are live at each node of each basic block.

Further features and advantages of the present invention, as well as the structure and operation of various embodiments of the present invention, are described in detail below with reference to the accompanying drawings. In the drawings, like reference numbers indicate identical or functionally similar elements. Additionally, the left-most digit of a reference number identifies the drawing in which the reference number first appears.

BRIEF DESCRIPTIONS OF THE DRAWINGS

The present invention will be described with reference to the accompanying drawings, wherein:

FIG. 1A shows a block diagram of the structure of a preferred environment in which the present invention could operate.

FIG. 1B illustrates a data parallel computer.

FIG. 2 is a flow chart which illustrates the relationship between firmware and software modules of FIG. 1A.

FIG. 3A is a high level block diagram of the structure of a C* compiler of the present invention.

FIG. 3B illustrates the structure of a front end of the C* compiler.

FIG. 4 is a flow chart which illustrates the interaction between modules of FIG. 3A.

FIG. 5A illustrates a block diagram of an optimizer of the present invention.

FIG. 5B illustrates a live variable analysis method of the present invention.

FIG. 6 illustrates a def/use calculation step 512.

FIG. 7 illustrates a flow chart of a calculate reaching definitions step.

FIG. 8 illustrates a flow chart of a calculate live variable step.

FIG. 9 illustrates a flow chart of a live variable traversal step.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

1. Hardware and Software Environment of the Present Invention

The present invention is directed to a software compiler for compiling a computer program wherein the computer program is adapted for use with a data parallel computer. In this patent document, the terms "computer program" and "source code" are used interchangeably.

In a preferred environment of the present invention, the data parallel computer is one manufactured by Thinking Machines Corporation, such as the Connection Machine.RTM. Model CM1.TM., CM2.TM. and CM5.TM. Supercomputers. These and other preferred environments of the present invention are described in U.S. Pat. No. 4,589,400 to Hillis, U.S. Pat. No. 4,984,235 to Hillis et al., and U.S. patent application Ser. No. 07/042,761, entitled "Method and Apparatus for Simulating M-Dimensional Connection Networks in an N-Dimensional Network Where M is Less Than N", filed Apr. 27, 1987, by Hillis, all of which were cited above.

Specifically, U.S. Pat. No. 4,589,400 describes a massively-parallel computer, including one embodiment of processors and router, with which the present invention can be used. U.S. Pat. No. 4,984,235 describes a massively-parallel computer, including a second embodiment of processors. U.S. patent application Ser. No. 07/042,761, entitled "Method and Apparatus for Simulating M-Dimensional Connection Networks in an N-Dimensional Network Where M is Less Than N", describes, in a massively parallel computer including processor chips interconnected by a hypercube, an arrangement for emulating the 2-, 3-, or higher dimensional nearest-neighbor communication network ("NEWS") between chips using the hypercube wires.

The computer program is written in a high level language (HLL). A preferred HLL is C* (pronounced "see star"). C* is based on Standard C and is extended to support parallel instructions and parallel data types. The C* language is described in the Thinking Machines Corporation publication C* Programming Guide (Version 6.0, November 1990) which is herein incorporated by reference in its entirety. The C* language is further described in the Thinking Machines Corporation publication C* Language Reference Manual (April 1991) which is herein incorporated by reference in its entirety.

FIG. 1A shows a block diagram of the structure of a preferred environment in which the present invention could operate. A data parallel computer 110 is comprised of a plurality of parallel processors 112. The number of processors in an actual data parallel computer 110 might range from 2,048 to 65,536. For clarity, the data parallel computer 110 illustrated has only eight parallel processors 112 (parallel processor.sub.0 to parallel processor.sub.7). Each parallel processor 112 has a CPU 114 and a random access memory (RAM) 116.

Each of the parallel processors 112 is directly connected to three other parallel processors 112 by paths. For example, the parallel processor.sub.0 112 is directly connected to the parallel processor.sub.1 112 via a path 120, the processor.sub.3 112 via a path 126, and the parallel processor.sub.7 112 via a path 142. The direct connections are such that no more than two paths need be used to send data between nearest-neighbor parallel processors 112.

The data parallel computer 110 is electrically connected to a host computer 146, to a non-volatile storage device 149, and to an input/output device 150 via a bus 152.

The host computer 146 is a serial computer such as a Sun 4 (manufactured by Sun Microsystems, Inc.) or a VAX (manufactured by Digital Equipment Corp.). The host computer 146 comprises a single host CPU (or a small number of CPUs) 148 and a RAM 150.

The environment of the present invention further includes various software modules and a firmware module. The software components include a C compiler 156, a loader/link editor 158, a C* library 160, and a Paris library 162. The software modules could reside in the RAM 150, in the non-volatile storage device 149, or in some combination of the two. In FIG. 1A, the software modules are shown in the RAM 150. The firmware module (a Paris instruction set 164) resides in a microcode 166 of the host CPU 148.

A C* compiler 154 of the present invention is also included in the RAM 150. An example of the C* compiler 154 is the Thinking Machines Corporation C* Compiler. Version 6.0.

As noted above, C* is an extension of Standard C in that C* supports parallel instructions and parallel data types. Such extension of Standard C is achieved via use of a native instruction set of the data parallel computer. One such native instruction set is a Paris language. The Paris language is a low-level instruction set for programming the data parallel computer. The Paris language is described in the Thinking Machines Corporation documents Paris Reference Manual (Version 6.0, February 1991) and Revised Paris Release Notes (Version 6.0, February 1991), which are herein incorporated by reference in their entireties. These documents are available from the Thinking Machines Corporation Customer Support Department at 245 First Street, Cambridge, Mass.

The Paris instruction set 164 and the Paris library 162 implement the Paris language. The Paris instruction set 164 and the Paris library 162 are part of the system software for the Connection Machine.RTM. Model CM2.RTM. Supercomputer.

FIG. 2 is a flow chart which illustrates the relationship between the software modules 154, 156, 158, 160 and 162 and the firmware module 164 of FIG. 1A. Referring to FIG. 2, in a step 210 the C* compiler 154 generates C source code from C* source code. In a step 212, the C compiler 156 generates relocatable machine code from the C source code. In a step 214, the loader/link editor 158 links the relocatable machine code to user compilation units and to compilation units of the C* library 160 and the Paris library 162 to generate linked machine code. Steps 216, 218, and 220 involve executing the linked code. Specifically, in step 216, the relocatable addresses of the linked code are translated to absolute machine addresses. In step 218, the absolute machine code is loaded into the front end computer 146. In step 220, the absolute machine code is executed.

2. Selected Aspects of the C* Programming Language

C* uses shapes and parallel variables to extend C to support data parallel programming.

A shape is a template for parallel data. In C*, a programmer must specify the shape of the data before the programmer can define data of that shape. A shape is specified by how many dimensions it has and by the number of positions in each of its dimensions. The total number of positions in a shape is product of the number of positions in each of its dimensions. For example, an 8.times.4 shape has 32 positions.

A C* keyword "shape" is used to declare shapes. This is shown in Example 1, below.

    ______________________________________
    shape [8]employees;   (Example 1)
    shape [16]companies;
    ______________________________________

    ______________________________________
    shape [256][512]image;
                          (Example 2)
    ______________________________________

    ______________________________________
    Parallel variables are declared as shown in Example 3.
    ______________________________________
    double:employees employee.sub.-- id;
                           (Example 3)
    char:companies company.sub.-- id;
    ______________________________________

    ______________________________________
    with(employees) {
     /* operations on parallel variables of
     shape employees go here */
     };
    Code Segment 1
    ______________________________________

    ______________________________________
    with(employees)
     where (employee.sub.-- id > 6)
      /* parallel code in restricted content
      goes here */
    Code Segment 2
    ______________________________________

    ______________________________________
           1         char c;
           2         employee.sub.-- id = c;
           Code Segment 3
    ______________________________________

    ______________________________________
     1         void f(int:current y, int:current z, int n)
     2         {
     3          int:current x;
     4
     5          printf("%d",n);
     6          x = y;
     7          where(z > 10)
     8           x = 10;
     9          g(x,n);
    10         }
    Code Segment 4
    ______________________________________

• Inventors
  Sistare, Steven J.; Frankel, James L.;
• Assignee
  Thinking Machines Corporation (Cambridge, MA)
• Published
  Oct-11-1994
• Current US Classes:
  717/146
  717/149
  717/154
• Application #
  806026
• International Classes
  G06F 009/44
• Field of Search
  395/700 395/650 364/200
• Examiner
  Kriess; Kevin A.
• Agent
  Sterne, Kessler, Goldstein & Fox
• US Patent References:
  4598400
  4773038
  4827403
  4984235
  5021945
  5107418
  5175856
  5179702
  5193190
  5204960