Thinking Machines Corporation

Brewster A Kahle

W Daniel Hillis

Guy Lewis Steele, Jr

George G Robertson

David C Douglas

Clifford A Lasser

Karl P Sims

Craig W Stanfill

Charles E Leiserson

Bradley C Kuszmaul

David S Wells

Shaw-Wen Yang

Bruce J Walker

Kenneth W Crouch

Carl R Feynman

Alexander D Vasilevsky

James B Salem

Michael Drumbeller

Guy Blelloch

Abhiram Ranade

Carl Feyman

Richard Clayton

Tamiko Thiel

Shaw W Yang

David P Christman

A digital computer comprising a plurality of message generating nodes interconnected by a routing network. The routing network transfers messages among the message generating elements in accordance with address information identifying a destination message generating element. Each message generating node includes a message data generator and a network interface. The message data generator generates message data items each including an address data portion comprising a destination identifier. The network interface includes a message generator and an address translation table, the table including a plurality of entries identifying, for at least one destination identifier, a translated destination identifier. The message generator, in response to the receipt of a message data item from the message data generator, generates a message for transmission to the routing network. In generating the message, the message generator performs an address translation operation in connection with the address data and the contents of the address translation table to generate updated address data which it uses data in connection with generating address information for the message.

Router for parallel computer including arrangement for redirecting

A parallel processor is disclosed which combines the advantages of an array of bit-serial processors and an array of word-oriented processors. Further, the invention provides for ready communication between data organized in bit-serial fashion and that organized in parallel. The processor comprises a plurality of word-oriented processors, at least one transposer associated with each processor, said transposer having n bit-serial inputs and m bit parallel outputs and a bit-serial processor associated with each bit-serial input of the transposer. The parallel processor further comprises a memory for each bit-serial processor and a data bus interconnecting the memory, the bit-serial processors and the bit-serial inputs of the transposer. The transposer converts serial inputs to parallel, word organized outputs which are provided as inputs to the word-oriented processors. In accordance with a preferred embodiment of the invention, three or more transposers are used in connection with each word-oriented processor so as to provide a pipelining capability that significantly enhances processing speeds.

Method and apparatus for interfacing bit-serial parallel processors to a

A message packet router is describes that performs the functions of determining if a message packet is addressed to circuitry associated with the router, of routing message packets to their destination if possible and of storing message packets that cannot be routed on because of circuit conflicts. The router also provides additional functions of merging message packets addressed to the same destination, of saving the state of the router at each significant point in the message routing cycle, and of running the entire routing cycle backwards. This later feature makes it possible to broadcast message packets selectively to certain processors in the array.

Method and apparatus for routing message packets

In accordance with the invention, each element or mode in the n-dimensional connection pattern is assigned a unique binary number or address by numbering the elements. Next, the individual binary digits of the address associated with each element are assigned to the different dimensions of the connection pattern of m dimension according to a fixed rule. Each set of binary digits that is so assigned to a dimension is then treated as the address of the node in that dimension in a gray code space; and the nodes that are its nearest neighbors in that dimension are those nodes that bear the Gray code values immediately before it and immediately after it in the Gray code sequence. Data are then routed to the nearest neighbor in one direction in a dimension by forwarding them from one node to the node bearing the next succeeding (or preceding) Gray code address and a node can be conditioned to receive such data by having it look for data from the node with the next preceding (or succeeding) address.

Method and apparatus for simulating m-dimension connection networks in

A message packet router is described that performs the functions of determining if a message packet is addressed to circuitry associated with the router, of routing message packets to their distination if possible and of storing message packets that cannot be routed on because of circuit conflicts. The router also provides additional functions of merging message packets addressed to the same destination, of saving the state of the router at each significant point in the message routing cycle, and of running the entire routing cycle backwards. This later feature makes it possible to broadcast message packets selectively to certain processors in the array.

Method and apparatus for routing message packets and recording the

A method to operate on a single instruction multiple data (SIMD) computer for searching for relevant documents in a database which makes it possible to perform thousands of operations in parallel. The words of each document are stored by surrogate coding in tables in one or more of the processors of the SIMD computer. To determine which documents of the database contain a word that is the subject of a query, a query is broadcast from a central computer to all the processors and the query operations are simultaneously performed on the documents stored in each processor. The results of the query are then returned to the central computer. After all the search words have been broadcast to the processors and point values accumulated as appropriate, the point values associated with each document are reported to the central computer. The documents with the largest point values are then ascertained and their identification is provided to the user.

Method for searching a database system including parallel processors

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 and apparatus are described for error control and correction which operates across multiple processors and multiple computer memories. In accordance with the invention, data signals from a plurality of processors are applied in parallel to a syndrome generator that generates a syndrome related to such signals. The syndrome is then stored in parallel in a plurality of read/write memories at the same address as the data signals from which the syndrome was generated. When the data signals are read from memory, they are again provided to the syndrome generator which again generates a new syndrome. At the same time the old syndrome signals stored at the same memory addresses are read from memory and compared with the new syndrome. If the two syndromes are the same, there is no error and the data signals are valid. If the syndromes are different, a syndrome decoder determines if sufficient information is available in the syndrome signals to correct the error and does so if it can.

Error control method and apparatus

A massively parallel processor comprising 65,534 (=2.sup.16) individual processors is organized so that there are 16 (=2.sup.4) individual processors on each of 4,096 (=2.sup.12) integrated circuits. The integrated circuits are interconnected in the form of a Boolean cube of 12 dimensions for routing of message packets. Each circuit board carries 32 (=2.sup.5) integrated circuits and each backplane carries 16 (=2.sup.4) circuit boards. There are eight (=2.sup.3) backplanes advantageously arranged in a cube that is 2.times.2.times.2. Each integrated circuit on a circuit board is connected to five integrated circuits on the same board which are its nearest neighbors in the first five dimensions. Further, each integrated circuit is also connected to four other integrated circuits on different circuit boards, but on the same backplane. Finally, each integrated circuit is also connected to three other integrated circuits, each on a different backplane. As a result of this arrangement, all message packets are first routed to nearest neighbor ICs located on the same circuit board; all message packets are then routed to nearest neighbor ICs located on the same backplane; and finally, all message packets are then routed to nearest neighbor ICs located on different backplanes.

Method and apparatus for interconnecting processors in a

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.

Growing community of inventors

Somerville, MA, United States of America

Brewster A Kahle