Parallel processing system with processor array and network communications system for transmitting messages of variable length
First Claim
1. A parallel processing array including a plurality of processing elements and an interconnection network for transferring messages among the processing elements, each processing element including network interface means and means for generating a message in the form of one or more blocks, said message including a destination address field, said network interface means including:
- A. a plurality of receive circuit means each connected to receive message blocks from a transmit circuit means of a connected processing element;
B. a plurality of transmit circuit means each connected to transmit message blocks to a receive circuit means of a connected processing element;
C. transfer means for coupling the message blocks from any one of said receive circuit means to any one of said transmit circuit means in response to the contents of a destination address field, comprising;
i. switch means for controllably coupling the message blocks received in any one of said receive circuit means to any one of said transmit circuit means,ii. routing circuit control means connected to said switch means and to each of said receive circuit means, including means for (a) storing a correspondence between a destination address and one of said transmit circuit means, (b) reading the destination address field from a message, (c) identifying, in response to the destination address field of said message, a corresponding one of said transmit circuit means, and then enabling said switch means to couple all blocks of said message thereafter received by any of said receive circuit means to said corresponding one of said transmit circuit means, and (d) when the last block of said message is received by one of said receive circuit means, disabling said switch means after said last block is coupled to said corresponding one of said transmit circuit means.
1 Assignment
0 Petitions
Accused Products
Abstract
A highly-parallel processing system in which a number of processing elements are interconnected by a network, and are also connected to a system bus and are controlled by a central processing unit. Each processing element includes a memory, and all of the memories in the processing elements form at least part of the memory available to the CPU. The processing elements normally execute programs in MIMD mode, and the CPU or another unit can interrupt them to execute a SIMD instruction. The network allows for transmission of variable length messages and also for combining messages when received at a common processing element.
153 Citations
24 Claims
-
1. A parallel processing array including a plurality of processing elements and an interconnection network for transferring messages among the processing elements, each processing element including network interface means and means for generating a message in the form of one or more blocks, said message including a destination address field, said network interface means including:
-
A. a plurality of receive circuit means each connected to receive message blocks from a transmit circuit means of a connected processing element; B. a plurality of transmit circuit means each connected to transmit message blocks to a receive circuit means of a connected processing element; C. transfer means for coupling the message blocks from any one of said receive circuit means to any one of said transmit circuit means in response to the contents of a destination address field, comprising; i. switch means for controllably coupling the message blocks received in any one of said receive circuit means to any one of said transmit circuit means, ii. routing circuit control means connected to said switch means and to each of said receive circuit means, including means for (a) storing a correspondence between a destination address and one of said transmit circuit means, (b) reading the destination address field from a message, (c) identifying, in response to the destination address field of said message, a corresponding one of said transmit circuit means, and then enabling said switch means to couple all blocks of said message thereafter received by any of said receive circuit means to said corresponding one of said transmit circuit means, and (d) when the last block of said message is received by one of said receive circuit means, disabling said switch means after said last block is coupled to said corresponding one of said transmit circuit means. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A parallel processing array including a plurality of processing elements and an interconnection network for transferring messages among the processing elements, each processing element including network interface means and means for generating messages, each message comprising a sequence of message signals, including a destination address field, which are transmitted in serial form, said network interface means including:
-
A. a plurality of receive circuit means each connected to another processing element via a receive line, each including; i. receive shift register means for sequentially receiving and storing serial message signals during a message transfer interval, ii. error checking means connected to said receive shift register means for generating a receive acknowledgement signal in response to the correct receipt of said message, iii. acknowledgement signal receiving means for receiving, during an acknowledgement signal transfer interval, an acknowledgement signal from the error checking means of the connected processing element, iv. receiver coupling means connected to said receive shift register means, said acknowledgement signal receiving means and said receive line for selectively coupling signals from said receive line to said receive shift register means during said message transfer interval and to said acknowledgement signal receiving means during said acknowledgement signal transfer interval, and v. receive message storage means connected to said error checking means and said receive shift register means for retrieving a message stored in said receive shift register means in response to a determination by said error checking means that said message was correctly received; B. a plurality of transmit circuit means each connected to another processing element via a transmit line, each including; i. transmit message storage means for storing a message, ii. transmit shift register means connected to said transmit message storage means for retrieving a message from said transmit message storage means and sequentially transmitting serial message signals during said message transfer interval, iii. transmitter coupling means connected to said transmit shift register means, said error checking means, and said transmit line for selectively coupling signals onto said transmit line from said transmit shift register means during said message transfer interval and to said error checking means during said acknowledgement signal transfer interval; C. transfer means for coupling the message signals of each received message from any one of said receive message storage means to any one of said transmit message storage means in response to the contents of a destination address field comprising; i. switch means for controllably coupling the message signals received in any one of said receive message storage means to any one of said transmit storage means, ii. routing circuit control means connected to said switch means, each of said receive circuit means, and to each of said receiver and transmitter coupling means, said routing circuit control means including means for (a) storing a correspondence between a destination address and one of said transmit circuit means, (b) reading the destination address field from a message, (c) identifying, in response to the destination address field of said message, a corresponding one of said transmit circuit means, and then enabling said switch means to couple all message signals of said message to said corresponding transmit circuit means, and (d) establishing said message transfer interval and said acknowledgment signal transfer interval by enabling said receiver and transmitter coupling means to respectively couple to said acknowledgement signal receiving means and said error checking means, and then to said receive and transmit shift register means.
-
-
13. A processing element for use in a parallel processing array including a plurality of processing elements and an interconnection network for transferring messages among the processing elements, said processing element including network interface means and means for generating a message in the form of one or more blocks, said message including a destination address field, said network interface means including:
-
A. a plurality of receive circuit means each connected to receive message blocks from a transmit circuit means of a connected processing element; B. a plurality of transmit circuit means each connected to transmit message blocks to a receive circuit means of a connected processing element; C. transfer means for coupling the message blocks from any one of said receive circuit means to any one of said transmit circuit means in response to the contents of a destination address field, comprising; i. switch means for controllably coupling the message blocks received in any one of said receive circuit means to any one of said transmit circuit means, ii. routing circuit control means connected to said switch means and to each of said receive circuit means, including means for (a) storing a correspondence between a destination address and one of said transmit circuit means, (b) reading the destination address field from a message, (c) identifying, in response to the destination address field of said message, a corresponding one of said transmit circuit means, and then enabling said switch means to couple all blocks of said message thereafter received by any of said receive circuit means to said corresponding one of said transmit circuit means, and (d) when the last block of said message is received by one of said receive circuit means, disabling said switch means after said last block is coupled to said corresponding one of said transmit circuit means. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
24. A processing element for use in a parallel processing array including a plurality of processing elements and an interconnection network for transferring messages among the processing elements, said processing element including network interface means and means for generating messages, each message comprising a sequence of message signals, including a destination address field, which are transmitted in serial form, said network interface means including:
-
A. a plurality of receive circuit means each connected to another processing element via a receive line, each including; i. receive shift register means for sequentially receiving and storing serial message signals during a message transfer interval, ii. error checking means connected to said receive shift register means for generating a receive acknowledgement signal in response to the correct receipt of said message, iii. acknowledgement signal receiving means for receiving, during an acknowledgement signal transfer interval, an acknowledgement signal from the error checking means of the connected processing element, iv. receiver coupling means connected to said receive shift register means, said acknowledgement signal receiving means and said receive line for selectively coupling signals from said receive line to said receive shift register means during said message transfer interval and to said acknowledgement signal receiving means during said acknowledgement signal transfer interval, and v. receive message storage means connected to said error checking means and said receive shift register means for retrieving a message stored in said receive shift register means in response to a determination by said error checking means that said message was correctly received; B. a plurality of transmit circuit means each connected to another processing element via a transmit line, each including; i. transmit message storage means for storing a message, ii. transmit shift register means connected to said transmit message storage means for retrieving a message from said transmit message storage means and sequentially transmitting serial message signals during said message transfer interval, iii. transmitter coupling means connected to said transmit shift register means, said error checking means, and said transmit line for selectively coupling signals onto said transmit line from said transmit shift register means during said message transfer interval and to said error checking means during said acknowledgement signal transfer interval; C. transfer means for coupling the message signals of each received message from any one of said receive message storage means to any one of said transmit message storage means in response to the contents of a destination address field comprising; i. switch means for controllably coupling the message signals received in any one of said receive message storage means to any one of said transmit storage means, ii. routing circuit control means connected to said switch means, each of said receive circuit means, and to each of said receiver and transmitter coupling means, said routing circuit control means including means for (a) storing a correspondence between a destination address and one of said transmit circuit means, (b) reading the destination address field from a message, (c) identifying, in response to the destination address field of said message, a corresponding one of said transmit circuit means, and then enabling said switch means to couple all message signals of said message to said corresponding transmit circuit means, and (d) establishing said message transfer interval and said acknowledgment signal transfer interval by enabling said receiver and transmitter coupling means to respectively couple to said acknowledgement signal receiving means and said error checking means, and then to said receive and transmit shift register means.
-
Specification