Thinking Machines Corporation

Ab Initio Software Corporation

T. M. Patents, L.p.

Clifford A Lasser

Craig W Stanfill

W Daniel Hillis

Guy Lewis Steele, Jr

Brewster A Kahle

Robert D Lordi

Karl P Sims

Kenneth W Crouch

Alexander D Vasilevsky

Linda J Seamonson

Tobias M Weinberg

Lisa A Tennies

Gary W Sabot

James B Salem

Guy Blelloch

Abhiram Ranade

Harry Mark Bromley

David Bruce Gingold

Michael Drumbeller

A buffer deadlock prevention technique for dataflow computations. The invention that implements the following algorithm: (1) providing a supplemental buffer for each input of a 'downstream' program; (2) partitioning the inputs of each downstream program into disjoint input sets, such that two inputs are in the same input set if and only if such inputs come, either directly or indirectly, from a common upstream program; (3) attempting to read data into a downstream program from an 'upstream' program via an input I in an input set; (4) if no data is currently available from input I, and if any other input J in the same input set has data available, then reading into the downstream program available data from each such input J and storing such that data in the supplemental buffer corresponding to such input J until such time as available data is exhausted on all such inputs J or data becomes available on input I.

Method for preventing buffer deadlock in dataflow computations

A method and apparatus by which a graph can be used to invoke computations directly. Methods get information into and out of individual processes represented on a graph, move information between the processes, and define a running order for the processes. An application writer informs a system incorporating the invention how processes should access necessary data. The invention adds 'adaptor processes', if necessary, to assist in getting information into and out of processes. In general, in one aspect, a method executes on a computer system a computation expressed as a graph comprising a plurality of vertices representing computational processes, each vertex having an associated access method, and a plurality of links, each connecting at least two vertices to each other and representing a flow of data between the connected vertices, comprising the steps of: (1) accepting the graph into the computer system as user input; (2) preparing the graph for execution by performing, on the computer system, graph transformation steps until each vertex is in a runnable state, and each link is associated with at least one communication method compatible with the access methods of the vertices connected by the link; (3) launching each link by creating, by means of the computer system, a combination of communication channels and/or data stores, as appropriate to the link's communication method; and (4) launching each process by invoking execution of the process on the computer system.

Executing computations expressed as graphs

A method and system that applies transaction techniques to file system operations in non-database applications executing on parallel processing systems. For each of a set of file operations, methods embodied in program routines are defined for performing, finalizing, and undoing the operations, so that the operations may be used in a non-database application to create a transaction processing environment. In general, in one aspect, the invention provides a computer program library for adding the semantics of transactions to a set of native operations of a native file system. The library comprises a set of one or more families of routines, each such family of routines corresponding to at least one native operation, each such family of routines including: (a) a Perform routine including instructions for providing the functional equivalent of one of the family's corresponding native operations while preserving information necessary to roll back such native operations; (b) a Finalize routine including instructions for committing the result of the corresponding perform routine; and (c) an Undo routine including instructions for rolling back the result of the corresponding perform routine. Provision is also made for accomodating programs that cannot be modified to incorporate the Perform operation.

Restoring the state of a set of files

An apparatus and method for efficiently mapping elements of an array to processing elements (PEs) of a parallel data computer. Axis lengths and weights are received from a compiler (if invoked at compile time) or an application program (if invoked at run time). A physical grid is generated by expanding the axis lengths so that their product is integrally divisible by 'machine.sub.-- bits' (i.e., log.sub.2 (number of PEs on the data parallel computer)). The physical grid is divided into subgrids of equal size by dividing each expanded axis length into subgrid lengths of equal length. The lengths and numbers of subgrid lengths in each axis are then output to the compiler or the application program. From the subgrid lengths, the compiler or application program can identify a unique location in one of the subgrids given any location of an element in the array. From the number of subgrids in each axis, the compiler or application program can identify a unique memory location on a unique PE given the subgrid and location identified from the subgrid length.

System and method of mapping an array to processing elements

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.RTM. 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.

System and method for compiling a fine-grained array based source

A virtual processor mechanism and specific techniques and instructions for utilizing such virtual processor mechanism within an SIMD computer having numerous processors, and each physical processor having dedicated memory associated therewith. Each physical processor is used to simulate multiple 'virtual' processors, with each physical processor simulating the same number of virtual processors. The memory of each physical processor is divided into n regions of equal size, each such region being allocated to one virtual processor, where n is the number of virtual processors simulated by each physical processor. Whenever an instruction is processed, each physical processor is time-sliced among the virtual memory regions, performing the operation first as one virtual processor, then another, until the operation has been performed for all virtual processors. Physical processors are switched among the virtual processors in a completely regular, predictable, deterministic fashion. The virtual processor mechanism switches among virtual processors within instructions, so that at the completion of each instruction, it has been executed on behalf of all virtual processors. A number of instructions are shown for execution using these virtual processor techniques.

Virtual processor techniques in a SIMD multiprocessor array

A method is described for simulating additional processors in a SIMD computer by dividing the memory associated with each processor into a plurality of sub-memories and then operating on each sub-memory in succession as if it were associated with a separate processor. Thus, a first instruction or set of instructions is applied to all the processors of the array to cause at least some processors to process data stored at a first location or locations in the first sub-memory. Thereafter, the same first instruction or set of instructions is applied to all the processors of the array to cause at least some processors to process data stored at the same first location in a second sub-memory. And so forth for each of the sub-memories. By operating a SIMD computer in this fashion, it is possible in effect to vary the number of processors in the array so as to provide the number of processors required for a problem.

Method of simulating additional processors in a SIMD parallel processor

Growing community of inventors

Cambridge, MA, United States of America

Clifford A Lasser