Parallel processor

Claim 2

A processor array for parallel computer processing comprising: an array of processor/memories, each of which comprises a memory means into which data may be written and from which data may be read and a processor for producing an output depending at least in part on data read from said memory means and instruction information, and means for interconnecting the processor/memories of the array in an n-dimensional pattern having at least 2 n nodes through which data may be routed from any processor/memory in the array to any other processor/memory, n being greater than 2, said means comprising: means for generating an addressed message packet that is routed from one processor/memory to another in said n-dimensional pattern in accordance with address information included in said message packet, and means at each node in the n-dimensional pattern for routing said message packet in accordance with the address information in said packet.

Claim 3

The apparatus of claim 1 further comprising means for interconnecting the processor/memories of the array in an m-dimensional pattern where m is at least 1 in which individual processor/memories are connected to at least some adjacent processor/memories in such m-dimensional pattern, said means comprising direct connections between individual processor/memories and the adjacent processor/memories to which they are connected.

Claim 4

The apparatus of claim 1 wherein the address information is the relative displacement of the originating processor/memory and the destination processor/memory in the n-dimensional pattern and the interconnecting means further comprises means for updating the relative displacement at each node through which the message packet is routed.

Claim 5

The apparatus of claim 3 wherein two copies of the relative displacement are generated at the originating processor/memory and the displacement in one copy is up-dated at each node through which the message packet is routed while individual bits in the other copy of the relative displacement are used by the routing means to control the routing of the message packet.

Claim 6

The apparatus of claim 1 wherein the address information is a relative address comprising as many digits as there are dimensions, each digit representing the relative displacement of the message packet from the node to which it is addressed and the routing means at each node comprises, means associated with each dimension for examining a digit of the address of said message packet received at a node to determine if the displacement in that dimension is zero, means associated with each dimension for routing said message packet to another node in the same dimension if an examined digit indicates that the message packet has not reached its destination and if a connection to such node is available, means for passing the message packet from one examining means to another when the message packet is not routed to another node in the same dimension, and storing and processing means for routing message packets that have reached their destination to a message sink, for temporarily storing message packets that have not been routed on to their destination and for recycling stored message packets to said examining means for further routing.

Claim 7

The apparatus of claim 1 wherein the address information is a relative address comprising as many digits as there are dimensions, each digit representing the relative displacement of the message packet from the node to which it is addressed and the routing means at sach node comprises, at least first, second and third means for examining the first, second and third digits, respectively, of the address of said message packet received at a node to determine if the displacement in that dimension is zero, at least first, second and third means for routing said message packet to another node in the first, second and third dimensions, respectively, if the examined digit indicates that the message packet has not reached its destination and if a connection to such node is available, first means for providing the message packet to said aecond means for examining the second digit of the address information when said first connection is not available or said first digit indicates that the message packet has reached its destination in that dimension, second means for providing the message packet to said third means for examining the third digit of the address information when a connection is not available or said second digit indicates that the message packet has reached its destination in that dimension, third means for providing the message packet to additional examining means or to storing and processing means when a connection is not available or said third digit indicates that the message packet has reached its destination in that dimension, and storing and processing means for routing message packets that have reached their destination to a message sink, for temporarily storing message packets that have not been routed on to their destination and for recycling stored message packets to said first examining means for further routing.

Claim 8

Apparatus for routing message packets through a network of nodes that are interconnected in a pattern of two or more dimensions comprising: means for generating a message packet that is routed from one node to another in said pattern in accordance with relative address information included in said message packet, said relative address comprising as many digits as there are dimensions, each digit representing the relative displacement of the message packet from the node to which it is addressed, at least first and second means for examining the first and second digits, respectively, of the address of said message packet received at a node to determine if the displacement in that dimension is zero, at least first and second means for routing said message packet to another node in the first and second dimensions, respectively, if the examined digit indicates that the message packet has not reached its destination and if a connection to such node is available, first means for providing the message packet to said second means for examining the second digit of the address information when said first connection is not available or said first digit indicates that the message packet has reached its destination in that dimension, second means for providing the message packet to additional examining means or to storing and processing means when a connection is not available or said second digit indicates that the message packet has reached its destination in that dimension, and storing and processing means for routing messages that have reached their destination to a message sink, for temporarily storing messages that have not been routed on to their destination and for recycling stored messages to said first examining means for further routing.

Claim 9

Apparatus for routing message packets through a network of nodes that are interconnected in a pattern of two or more dimensions comprising: means for generating a message packet that is routed from one node to another in said pattern in accordance with relative address information included in said message packet, said relative address comprising as many digits as there are dimensions, each digit representing the relative displacement of the message packet from the node to which it is addressed, at least first and second means for examining the first and second digits, respectively, of the address of said message packet received at a node to determine if the displacement in that dimension is zero, at least first and second means for routing said message packet to another node in the first and second dimensions, respectively, if the examined digit indicates that the message packet has not reached its destination and if a connection to such node is available, first means for providing the message packet to said second means for examining the second digit of the address information when said first connection is not available or said first digit indicates that the message packet has reached its destination in that dimension, second means for providing the message packet to additional examining means or to storing and processing means when a connection is not available or said second digit indicates that the message packet has reached its destination in that dimension, and storing and processing means for routing messages that have reached their destination to a message sink, for temporarily storing messages that have not been routed on to their destination and for recycling stored messages to said first examining means for further routing.

Claim 10

The apparatus of claim 7 further comprising means for updating the relative displacement at each node through which the message packet is routed.

Claim 11

The apparatus of claim 7 wherein two copies of the relative displacement are generated at the originating node and the displacement in one copy is up-dated at each node through which the message packet is routed while individual bits in the other copy of the relative displacement are examined by the routing means to control the routing of the message packet.

Claim 12

The apparatus of claim 9 wherein said first examining means, first routing means and first providing means at each node operate in synchronism with the first examining means, first routing means and first providing means at the other nodes of said network and said second examining means, second routing means and second providing means at each node operate in synchronism with the second examining means, second routing means and second providing means at the other nodes of said network.

Claim 13

In a processor array for parallel computer processing comprising an array of processor/memories, each of which comprises a memory means into which data may be written and from which data may be read and a processor for producing an output depending at least in part on data read from said memory means and instruction information, a method for interconnecting the processor/memories of the array in an n-dimensional pattern having at least 2 n nodes through which data may be routed from any processor/memory in the array to any other processor/memory, n being greater than 2, said method comprising the steps of: generating an addressed message packet that is routed from one processor/memory to another in said n-dimensional pattern in accordance with address information included in said message packet, and at each node in the n-dimensional pattern, routing said message packet in accordance with the address information in said packet.

Claim 14

In a processor array for parallel computer processing comprising an array of processor/memories, each of which comprises a memory means into which data may be written and from which data may be read and a processor for producing an output depending at least in part on data read from said memory means and instruction information, a method for interconnecting the processor/memories of the array in an n-dimensional pattern having at least 2 n nodes through which data may be routed from any processor/memory in the array to any other processor/memory, n being greater than 2, said method comprising the steps of: generating an addressed message packet that is routed from one processor/memory to another in said n-dimensional pattern in accordance with address information included in said message packet, and at each node in the n-dimensional pattern, routing said message packet in accordance with the address information in said packet.