Parallel computer system

• US 5,333,268 A
• Filed: 09/16/1992
• Issued: 07/26/1994
• Est. Priority Date: 10/03/1990
• Status: Expired due to Fees

• Current Assignee: TM Patents LP
• Original Assignee: Thinking Machines Corporation (Oracle Corporation)
• Inventors: Zak, Robert C., Wong, Monica C., Hillis, W. Daniel, Douglas, David C., Kuszmaul, Bradley C., Leiserson, Charles E., Ganmukhi, Mahesh N., Wells, David S., Hill, Jeffrey V., Yang, Shaw-Wen
• Primary Examiner(s): RICHARDSON, ROBERT
• Application Number:
  US07/946,242
• Time in Patent Office: 678 Days
• Field of Search: 364/DIG. 1, 364/DIG. 2, 371/68.2, 371/68.3, 371/60, 395/200, 395/275, 395/325, 395/500, 395/575
• US Class Current: 709/244
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes
• CPC Class Codes: G06F 11/22 Detection or location of defective computer hardware by testing during standby operation or during idle time, e.g. start-up testing
• CPC Class Codes: G06F 11/324 Display of status information
• CPC Class Codes: G06F 15/17343 wherein the interconnection is dynamically configurable, e.g. having loosely coupled nearest neighbor architecture reconfigurable processors arrays G06F15/7867
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus
• CPC Class Codes: G06F 2201/88 Monitoring involving counting
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 49/35 Switches specially adapted for specific applications
• CPC Class Codes: H04L 49/555 Error detection

Abstract

A digital computer includes a plurality of processing elements, a command processor, a diagnostic processor and a communications network. The processing elements each performs data processing and data communications operations in connection with commands. The processing elements also performing diagnostic operations in response to diagnostic operation requests and providing diagnostic results in response thereto. The command processor generates commands for the processing elements, and also performs diagnostic operations in response to diagnostic operation requests and providing diagnostic results in response thereto. The diagnostic processor generates diagnostic requests. The communication network includes three elements, including a data router, a control network and a diagnostic network. The data router is connected to the processing elements for facilitating the transfer of data among them during a data communications operation. The control network is connected to the processing elements and the command processor for transferring commands from the command processor to the processing elements. The diagnostic network connected to the processing elements, the command processor and the diagnostic processor for transferring diagnostic requests from the diagnostic processor to the processing elements and the command processor and for transferring diagnostic results from the processing elements and the command processor to the diagnostic processor.

Claims

1. A digital computer comprising:

A. a plurality of processing elements each performing data processing and data communications operations in connection with commands, said processing elements also performing diagnostic operations in response to diagnostic operation requests and providing diagnostic results in response thereto;

B. at least one command processor for generating commands for said processing elements, said command processor also performing diagnostic operations in response to diagnostic operation requests and providing diagnostic results in response thereto;

C. at least one diagnostic processor for generating diagnostic requests;

D. a communication network comprising;

i. a data router connected to said processing elements for facilitating the transfer of data during a data communications operation;

ii. a control network connected to said processing elements and said command processor for transferring commands from said command processor to said processing elements; and

iii. a diagnostic network connected to said processing elements, said command processor and said diagnostic processor for transferring diagnostic requests from said diagnostic processor to said processing elements and said command processor and for transferring diagnostic results from said processing elements and said command processor to said diagnostic processor.

2. A digital computer comprising:

A. a plurality of processing elements each performing data processing operations in connection with commands, each processing element also generating and receiving data transfer messages, each including an address portion containing an address, for transfer to another processing elements as identified by the address and further generating and receiving control network messages;

B. a communications router comprising a plurality of router node groups interconnected in a tree pattern in a series of levels from a lower leaf level to an upper root level, each node group in the leaf level having one router node connected to a processing element, and each node group in levels above the leaf level including a plurality of router nodes, with router nodes in levels below the root level being connected to a plurality of router nodes in the next higher level thereby forming a fat-tree structure, each node receiving data transfer messages and coupling them to another node or to a processing element connected thereto as determined by the address in the respective address portion; and

C. a control network comprising a like plurality of control network node groups interconnected in a like tree pattern in a series of levels from a lower leaf level to an upper physical root level, each control network node group below the upper root level receiving control network messages from a processing element or a lower-level control network node group and generating a control network message in response thereto for transmission to a higher-level control network node group, and receiving control network messages from a higher-level control network node group and generating control network messages in response thereto for transmission to lower-level control network node groups, the control network node group at the root level generating control network messages for transmission to the lower level control network node groups in response to control network messages received therefrom.

3. A digital computer comprising:

A. a plurality of processing elements each performing data processing operations in connection with commands, each processing element also generating and receiving data transfer messages, each including an address portion containing an address, for transfer to another processing elements as identified by the address and further generating and receiving control network messages;

B. at least one scalar processor for generating control network messages containing commands for processing by said processing elements;

C. a control network comprising a plurality of control network nodes interconnected in a tree pattern in a series of levels from a lower leaf level to an upper root level, control network nodes in the leaf level being connected to said processing elements and said scalar processor,

i. said control network nodes below the root level, upon receiving a control network message containing a command from the scalar processor or a lower-level control network node, generating a control network message for transmission to a higher-level control network node, and

ii. the root control network node, upon receiving a control network message containing a command from a lower-level control network node, and the lower-level control network nodes, upon receiving a control network message containing a command from a higher-level control network node, generating control network messages containing the command from transmission to lower-level control network nodes and the processing elements, thereby to transmit messages containing a command to all of the processing elements; and

D. a communications router comprising a like plurality of router nodes interconnected in a tree pattern in a series of levels from a lower leaf level to an upper root level, router nodes in the leaf level being connected to said processing elements, the nodes receiving data transfer messages and coupling them to another node or to a processing element connected thereto as determined by the address in the respective address portion.

4. A digital computer comprising:

A. a plurality of message generating elements for generating messages, each message having an address portion including a level identifier portion containing a level identifier value and a destination identifier portion containing a destination path identifier value;

B. a routing network comprising a plurality of router nodes interconnected in a tree pattern in a series of levels from a leaf level to a root level, each router node below the root level being connected to a parent node at a higher level and each node above the leaf level being connected to a child node at a lower level and at least some of said nodes being connected to a plurality of child nodes to thereby define a tree pattern, the nodes at the leaf level being connected to receive messages from and transmit messages to the message generating elements, each node transmitting a message to its parent node if the level identifier value identifies a level higher than that of the node or alternatively transmitting said message to a particular child node as identified by said destination identifier value.

5. A computer as defined in claim 4 in which each of said message generating elements is identified by a message generating element identifier identifying the relative position of its connection to the routing network, each message generating element includes an address generator for generating said level identifier value and said destination path identifier value, said message generating element comprising:

A. an absolute address generator responsive to generation of a message for generating an absolute address value corresponding to the message generating element identifier for a message generating element to receive the message;

B. a height value generating portion for generating a level identifier value in response to the absolute address value generated by the absolute address generator and the message generating element identifier of the message generating element that is generating the message;

C. an address combiner for generating said address portion in response to the level identifier value generated by the height value generating portion and said absolute address generated by said absolute address generator.

6. A computer as defined in claim 5 in which said height value generating portion includes:

A. a relative address generator portion for generating a relative address in response to the absolute address value generated by the absolute address generator and the message generating element identifier of the message generating element that is generating the message, the relative address identifying a displacement over the routing network from the message generating element generating a message to the message generating element to receive the message;

B. a height identifier for generating a height value in response to the relative address generated by the relative address generating portion.

7. A computer as defined in claim 6 in which said absolute address value and the message generating element identifier are both represented by a word comprising a sequence of bits, said relative address generating portion performing a bit-wise exclusive-OR operation in connection with said absolute address value and the message generating element identifier to generate said relative address.

8. A computer as defined in claim 6 in which said height identifier comprises:

A. a potential height identifier circuit for generating in response to the relative address generated by said relative address generating portion a series of height signals each associated with a particular level in the routing network, said potential height identifier circuit asserting selected ones of said height signals as determined by the relative address; and

B. a decoder for selectively generating, in response to the height signals from the potential height identifier circuit, one of a plurality of height identifier values, each of said plurality being associated with a particular level in the routing network, the height identifier value generated being associated with the highest level whose associated height signal is asserted.

9. A computer as defined in claim 8 in which the height identifier values generated by said decoder are defined by binary-encoded signals.

10. A computer as defined in claim 8 in which said absolute value is defined by a binary-encoded absolute address signal having a predetermined number of bits, said down path generating portion generates said down path identifier value as a binary-encoded signal comprising a selected range of low-order ones of bits comprising said absolute address signal.

11. A computer as defined in claim 8 in which said address generator generates an address word comprising said level identifier value in a high-order portion and said destination path identifier value in a low-order portion,

A. said height value generating portion further includes a height location select circuit responsive to the relative address generated by said relative address generating portion for generating a level portion identifier to identify the portion of said address word to contain said level identifier value,

B. said address combiner coupling

(i) said level identifier value in a portion of said address word identified by said level portion identifier and

(ii) a selected low-order portion of the absolute address generated by said absolute address generator in the low-order portion of said address word below the portion occupied by said level identifier value

thereby to establish said address word.

12. A computer as defined in claim 11 in which said address word generated by said address generator comprises a series of predetermined address word sections each associated with a predetermined group of at least one level of said router network,

A. said height value generating portion identifying in response to said relative address one of said groups associated with the level identified by the level identifier value and generating a section identifier signal associated with the identified group,

B. said address combiner comprising a plurality of coupling circuits each associated with one of said address word sections for selectively coupling in response to the section identifier signal generated by said height value generating portion either the level identifier value or a low-order portion of said absolute address as the address word.

13. A computer as defined in claim 12 in which:

A. said height value generating portion includes;

i. a level group identifier circuit for receiving said relative address generated by said relative address generating portion a series of section enabling signals each associated with a particular section in the routing network;

ii. a group decoder for receiving said section enabling signals and asserting one section identifier signal corresponding to the asserted section enabling signals associated with the highest-level group;

B. said address combiner includes a plurality of coupling circuits each associated with one of said address word sections for coupling either the level identifier value or a selection portion of said absolute address portion as the associated address word section in response to the section identifier signal associated therewith.

14. A computer as defined in claim 4 in which each node comprises:

A. a plurality of output circuits, each for transmitting messages to the parent node or a child node connected to said node;

B. a plurality of input circuits, each for receiving messages from the parent node or a child node connected thereto and for generating an output circuit identifier in response to the level identifier value and destination path identifier value, the input circuit generating an output circuit identifier identifying an output circuit for transmitting a message to the parent node if the level identifier value identifies a level higher than that of the node or alternatively an output circuit for transmitting a message to a particular child node as identified by said destination identifier value, and

C. a switch for selectively coupling messages from said input circuits to said output circuits in response to the output circuit identifiers as generated by the input circuits.

15. A computer as defined in claim 14 in which each input circuit includes:

A. a message input buffer for buffering message information;

B. an output request buffer for buffering output circuit identifiers;

C. an input message control circuit for receiving messages and generating, in response to each received message, message information for buffering in said message input buffer and an associated output circuit identifier for buffering in said output request buffer; and

D. a switch input control circuit for obtaining each output circuit identifier from said output request buffer and coupling them to said switch and for selectively coupling buffered message information associated therewith from said message input buffer to said switch.

16. A computer as defined in claim 15 in which each message comprises a series of words, one of said words comprising said address portion and the remaining words comprising a data portion, said message input control circuit including:

A. an output request identifier processing circuit for processing said address portion to generate said output circuit identifier in response to the address portion of a received message; and

B. a message processing circuit for generating said message information in response to a received message;

17. A computer as defined in claim 16 in which each node receives a router height identifier and the address portion comprises a level identifier section containing a level identifier and a series of predetermined address word sections each associated with a predetermined group of at least one level of said router network, each address word section identifying for each level of the associated group a child node, said output request identifier processing circuit including:

A. a parent request circuit for comparing the router height identifier and the level identifier from the level identifier section of an address portion and for generating a parent request signal if the value of the level identifier is larger than the router height identifier;

B. a child request circuit for generating a child request signal identifying one of said child nodes connected thereto in response to the contents of a selected address word section; and

C. an output circuit identifier generating circuit for generating said output circuit identifier in response to the parent request signal and the child request signal.

18. A computer as defined in claim 17 in which said parent request circuit includes:

A. a child input port identifier for generating a child input port signal having a plurality of conditions each indicating whether the input circuit receives messages from a child or a parent;

B. a level comparator for generating a signal if the router height identifier is less than and the level identifier from the level identifier section of the address portion of a received message;

C. a parent request signal generator for generating the parent request signal in response to the coincidence of the child input port signal from the child input port identifier and the signal from the level comparator.

19. A computer as defined in claim 18 in which each node of said routing network operates in a first mode in response to a control signal having a first condition to couple received messages to a node connected thereto in accordance with the address portion, each node alternatively operating in a second mode in response to said control signal having a second condition to couple received messages to predetermined ones of the nodes connected thereto, the predetermined ones of said nodes being selected to facilitate transfer of a message to a nearby message generating element to facilitate the rapid emptying of the routing network of messages, said parent request signal generator further being inhibited from generating the parent request signal in response to said control signal having said second condition.

20. A computer as defined in claim 17 in which each address word section includes a series of down path identifiers each identifying a child identifier for a level of said routing network, said child request circuit including a down path identifier selector for selecting one of said down path identifiers and coupling the selected down path identifier as said child request signal.

21. A computer as defined in claim 20 in which each node of said routing network operates in a first mode in response to a control signal having a first condition to couple received messages to a node connected thereto in accordance with the address portion, each node alternatively operating in a second mode in response to said control signal having a second condition to couple received messages to predetermined ones of the child nodes connected thereto, the predetermined ones of said nodes being selected to facilitate transfer of a message to a nearby message generating element to facilitate the rapid emptying of the routing network of messages, the child request circuit of each input circuit generating further including:

A. a predetermined child identifier generating circuit for generating a predetermined child identifier;

B. a selector circuit connected to said down path identifier selector for selectively coupling either the selected down path identifier or said predetermined child identifier as said child request signal in response to said control signal having said first or second condition, respectively.

22. A computer as defined in claim 17 in which said output request identifier processing circuit further includes a buffer control circuit for generating a output request buffer enabling signal to enable the output request buffer to buffer the output circuit identifier.

23. A computer as defined in claim 16 in which each message further includes, following said address portion, a message data portion, said message processing circuit includes:

A. an address word processor for processing said address word in response to a router height identifier identifying the level of said node in said routing network to generate processed address word information; and

B. a message information processor for processing said message to generate message delimitation information to delimiting a received message, and for coupling the processed address word information, data portion and said delimitation information to said message input buffer as said message information.

24. A computer as defined in claim 23 in which each node has an associated router height identifier identifying a level of said routing network, said address word processor including:

A. a level comparator for generating a level comparison signal if the router height identifier corresponds to the level identifier from the level identifier section of the address portion of a received message;

B. A router height identifier decrementation circuit for generating a decremented router height identifier;

C. a height identifier selector for selectively coupling in response to said level comparison signal one of the router height identifier or the decremented router height identifier to the message input buffer as the processed address word.

25. A computer as defined in claim 24 in which said address word comprises a series of address word sections each associated with a predetermined series of at least one level of said router network and defining a series of down path identifiers path through said series, said address word processor further including:

a. an address word section coupling circuit for selectively coupling address word sections to said message input buffer as said processed address word; and

B. an address word section coupling control circuit for selectively enabling said address word section coupling circuit to couple address word sections, said address word section coupling control circuit disabling said address word section coupling circuit from coupling an address word section in response to the coincidence of (i) the level comparison signal indicating that the router height identifier indicating corresponding to the level identifier and (ii) the router height identifier identifying a level below that associated with the address word section.

26. A computer as defined in claim 23 in which said message information processor includes:

A. a message delimitation circuit for generating a begin message identification to identify the beginning of a message an end message identification circuit for generating an end message identification to identify the end of a message, and

C. a message coupling control circuit for controlling the coupling of said processed address word and said data portion to said message input buffer in response to the begin and end message identifications from said message delimitation circuit.

27. A computer as defined in claim 26 in which each message includes message length information, said message delimitation including a message length counter circuit for receiving said message length information and determining therefrom when an entire message has been coupled to said message input buffer.

28. A computer as defined in claim 27 in which each message further includes, following said address portion, a message data portion including a data length section including a data length value that identifies the length of said address portion, said level identifier and said data length section comprising said address portion, said message length counter circuit comprising:

A. a begin message detector for detecting the beginning of a message;

B. an address portion counter for receiving said level identifier in response to a begin message signal and decrementing as said address portion is being received, said address portion counter generating an address portion end signal after the address portion has been received;

C. a data portion counter for receiving said data length value in response to a length value control signal and for decrementing as said data portion is being received, said data portion counter generating a data portion end signal after the data portion has been received; and

D. a counter control circuit for controlling the operation of said address portion counter and said data portion counter, said counter control circuit enabling

(i) said address portion counter to receive said level identifier when the begin message detector detects the beginning of a message; and

(ii) said data portion counter to receive said data length value in response to the address portion end signal.

29. A computer as defined in claim 26 in which each message further includes an error control portion containing error control information to facilitate detection of transfer errors, said message information processor further including an error control processing portion for using the error control portion to determine whether a transfer error has occurred.

30. A computer as defined in claim 29 in which said error control processing portion includes:

A. an error control check circuit for using the error control portion to determine whether a transfer error occurred connection with a received message;

B. an updated error control information generating portion for generating updated error control information in response to the processed address word information and data portion coupled to said message input buffer by said message information processor;

C. an error code generating portion for generating an error code; and

D. an error code selection portion for selectively coupling said updated error control information or said error code to said message input buffer in response to the determination by said error control circuit.

31. A computer as defined in claim 30 in which said error code generating portion generates said error code as the complement of the updated error control information generated by said updated error control information generating portion.

32. A computer as defined in claim 15 in which said message input buffer generates a condition signal indicating selected conditions, said input message control circuit generating a flow control signal in response to the parent or child node connected thereto for transmission to regulate the transmission of messages thereby.

33. A message generating element for generating messages for transmission over a routing network comprising a plurality of router nodes interconnected in a tree pattern in a series of levels from a leaf level to a root level, each node being connected to a parent node at a higher level and a child node at a lower level and at least some of said nodes being connected to a plurality of child nodes to thereby define a tree pattern, the nodes at the leaf level being connected to receive messages from and transmit messages to the message generating elements, each message having an address portion including a level identifier portion containing a level identifier value and a destination identifier portion containing a destination path identifier value, said message generating elements being identified by a message generating element identifier identifying the relative position of its connection to a routing network, said message generating element including an address generator for generating said level identifier value and said destination path identifier value comprising:

A. an absolute address generator responsive to generation of a message for generating an absolute address value corresponding to the message generating element identifier for a message generating element to receive the message;

B. a height value generating portion for generating a level identifier value in response to the absolute address value generated by the absolute address generator and the message generating element identifier of the message generating element that is generating the message;

C. an address combiner for generating said address portion in response to the level identifier value generated by the height value generating portion and said absolute address generated by said absolute address generator.

34. A message generating element as defined in claim 33 in which said height value generating portion includes:

A. a relative address generating portion for generating a relative address in response to the absolute address value generated by the absolute address generator and the message generating element identifier of the message generating element that is generating the message, the relative address identifying a displacement over the routing network from the message generating element generating a message to the message generating element to receive the message;

B. a height identifier for generating a height value in response to the relative address generated by the relative address generating portion.

35. A message generating element as defined in claim 34 in which said absolute address value and the message generating element identifier are both represented by a word comprising a sequence of bits, said relative address generating portion performing a bit-wise exclusive-OR operation in connection with said absolute address value and the message generating element identifier to generate said relative address.

36. A message generating element as defined in claim 34 in which said height identifier comprises:

A. a potential height identifier circuit for generating in response to the relative address generated by said relative address generating portion a series of height signals each associated with a particular level identifier value, said potential height identifier circuit asserting selected ones of said height signals as determined by the relative address; and

B. a decoder for selectively generating, in response to the height signals from the potential height identifier circuit, one of a plurality of height identifier values, each of said plurality being associated with a particular level identifier value, the height identifier value generated being associated with the highest level identifier value whose associated height signal is asserted.

37. A message generating element as defined in claim 36 in which the height identifier values generated by said decoder are defined by binary-encoded signals.

38. A message generating element as defined in claim 36 in which said absolute address value is defined by a binary-encoded absolute address signal having a predetermined number of bits, said down path generating portion generates said down path identifier value as a binary-encoded signal comprising a selected range of low-order ones of bits comprising said absolute address signal.

39. A message generating element as defined in claim 36 in which said address generator generates an address word comprising said level identifier value in a high-order portion and said destination path identifier value in a low-order portion,

A. said height value generating portion further includes a height location select circuit responsive to the relative address generated by said relative address generating portion for generating a level portion identifier to identify the portion of said address word to contain said level identifier value,

B. said address combiner coupling

(i) said level identifier value in a portion of said address word identified by said level portion identifier and

(ii) a selected low-order portion of the absolute address generated by said absolute address generator in the low-order portion of said address word below the portion occupied by said level identifier value

thereby to establish said address word.

40. A message generating element as defined in claim 39 in which said address word generated by said address generator comprises a series of predetermined address word sections each associated with a predetermined group of at least one level identifier value,

A. said height value generating portion identifying in response to said relative address one of said groups associated with the level identifier value and generating a section identifier signal associated with the identified group,

B. said address combiner comprising a plurality of coupling circuits each associated with one of said address word sections for selectively coupling in response to the section identifier signal generated by said height value generating portion either the level identifier value or a low-order portion of said absolute address as the address word.