Partition control circuit for separately controlling message sending of nodes of tree-shaped routing network to divide the network into a number of partitions

• US 5,353,412 A
• Filed: 08/16/1991
• Issued: 10/04/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: Earls, John J., Hillis, W. Daniel, Douglas, David C., Ganmukhi, Mahesh N.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Harrity, Paul
• Application Number:
  US07/746,035
• Time in Patent Office: 1,145 Days
• Field of Search: 395/800, 395/200, 395/325, 370/60, 370/60.1, 370/61, 364/133, 340/825.02
• US Class Current: 709/243
• 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 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 49/555 Error detection

Abstract

A digital computer having a plurality of message generating elements each generating and receiving messages and a network for transferring messages among the message generating elements. The network includes a plurality of node clusters interconnected in a tree pattern from a lower leaf level to an upper root level, each node cluster including at least one node group with node clusters in a level above at least one predetermined level having a larger number of node groups than node clusters of the predetermined level for transferring messages among the message generating elements. Each node group in the node clusters of the predetermined level include a selective message coupling circuit for selectively coupling messages between the node group and a selected one of the upper-level node groups, the message coupling circuits of the node groups being separately controlled by a partition control circuit so as to facilitate partitioning of the network into a plurality of partitions so that messages generated by the lower-level node groups for transfer to each of at least one selected group of message generating elements are in response to messages generated thereby.

Claims

1. A digital computer comprising:

A. a plurality of message generating elements each generating and receiving messages;

B. a network for transferring messages generated by said message generating elements among said message generating elements, said network comprising a plurality of node clusters interconnected in a tree pattern from a lower leaf level to an upper root level, each said node cluster including at least one node group said node clusters in a level above at least one predetermined level having a larger number of said node groups than said node clusters of said predetermined level,

node groups of the lower leaf level receiving messages from, respectively, at least one message generating element and a higher-level node group and generating in response messages for transfer to, respectively, a higher-level node group and a message generating element,

ii. the respective node groups between the lower leaf level and the upper root level receiving messages from, respectively, at least one lower-level node group and a higher-level node group and generating in response messages for transfer to, respectively, a higher level node group and a lower level node group,

iii. node groups of said upper root level receiving messages from at least one lower-level node group and generating in response messages for transfer to said at least one lower-level node group,

each said node group in the node clusters of said predetermined level including a selective message coupling circuit, in response to a partition control signal, for selectively coupling messages between the node group and a selected one of the upper-level node groups; and

C. a partition control circuit, coupled to each of the message coupling circuits of each of the node groups, for generating said partition control signal to separately control said message coupling circuits thereby to establish at least one partition comprising selected ones of said message generating elements in which said network transfers messages generated by said selected message generating elements only among said selected message generating elements.

2. A computer as defined in claim 1 in which each said message coupling circuit comprises a multiplexer/demultiplexer and a control circuit for receiving the partition control signal to enable the multiplexer/demultiplexer to selectively couple messages between the node group and the selected one of the upper-level node groups.

3. A computer as defined in claim 1 further including a data router connected to said message generating elements for transferring data messages each containing data among said message generating elements, said node clusters generating data router control signals for controlling said data router in accordance with selected contents of said messages transferred by said node clusters.

4. A computer as defined in claim 3 in which said data router comprises a plurality of data router node groups interconnected in a tree pattern corresponding to the tree pattern of said network with each said data router node group having a corresponding node cluster, with each said network node cluster generating a data router control signal for controlling the associated data router node group.

5. A computer as defined in claim 4 in which each said network node group generates a data router control enabling signal in response to said selected contents of said control messages, each said network node cluster with said one network node group coupling the data router control enabling signal to the associated data router node group as the data router control signal, and each said network node cluster having a plurality of control network node groups further including a control signal selection circuit for generating a data router control signal for the associated data router node group in response to the data router control enabling signals from the said network node groups of the said network node cluster.

6. A computer as defined in claim 5 in which each control signal selection circuit includes:

A. a control signal enable register including a plurality of control signal enable flags each associated with a network node group of the control network node cluster, the control signal enable flag associated with the selected network node group having an enable condition and other control signal enable flags having a disable condition;

B. a plurality of control signal gate circuits each associated with a network node group of the network node cluster for generating a gated control signal corresponding to the data router enabling signal if the associated control signal enable flag has an enable condition; and

C. a control signal consolidation circuit for generating said control signal in response to the gated control signal from said control signal gate circuits.

7. A computer as defined in claim 4 in which each said data router node group further generates a status signal whose condition reflects selected status conditions, each said network node cluster with one said network node group receiving the status signal from the associated data router node group and using the status signal in generating a message and each said network node cluster having a plurality of network node groups further including a status signal coupling circuit connected to the said network node groups of the associated said network node cluster for selectively coupling the status signal as a gated status signal to the selected network node group, the selected network node group using the status signal in generating a message.

8. A computer as defined in claim 7 in which each status signal coupling circuit includes:

A. a status signal enable register including a plurality of status signal enable flags each associated with a network node group of the control network node cluster, the status signal enable flag associated with the selected network node group having an enable condition and other status signal enable flags having a disable condition;

B. a plurality of status signal gate circuits each connected to a network node group of the network node cluster for generating the gated status signal corresponding to the status signal if the associated status signal enable flag has an enable condition.

9. A computer as defined in claim 3 further comprising an input/output element for facilitating transfer of data between said message generating elements and a data source over said data router in response to input/output commands, said input/output commands being generated by at least some of said message generating elements, said message generating elements transferring said input/output commands to said input/output element over said data router so as to provide that said input/output element can receive input/output commands from message generating elements of any of said partitions.

10. A digital computer comprising:

A. a plurality of control processors each generating control messages;

B. a plurality of processing elements, each said processing element receiving at least some of said control messages and performing processing operations in response to ones of the control messages that are received by the processing element;

C. a control network for transferring said control messages from said control processors to said processing elements, said control network comprising a plurality of node clusters interconnected in a tree pattern from a lower leaf level to an upper root level, each said node cluster including at least one node group said node clusters in a level above at least one predetermined level having a larger number of said node groups than said node clusters of said predetermined level,

i. in a plurality of up-tree each from one of said control processors to a node group of the upper root level, a node group of the lower leaf level receiving messages from said one control processor and generating in response messages for transfer to a higher-level node group along said up-tree path, each said node groups between the lower leaf level and the physical root level along said up-tree path receiving control message from a node group at a lower level and generating in response control messages for transfer to a node group at a higher level along said up-tree path,

ii. each said node group in down-tree paths between the upper root level and the processing elements receiving messages from a higher-level node group and generating in response messages for transfer to, respectively, at least one lower level node group or processing element,

iii. each said node group of said upper root level receiving messages from a lower-level node group of one of said up-tree paths and generating in response messages for transfer to at least one node group of a down-tree path,

each said node group in the node clusters of said predetermined level including a message coupling circuit, in response to a partition control signal, for selectively coupling messages between the node group and a selected one of the uper-level node groups; and

C. a partition control circuit, coupled to each of the message coupling circuits of each of the node groups, for generating said partition control signal to separately control said message coupling circuits thereby to establish at least one partition comprising selected ones of said message generating elements in which said network transfers messages generated by said selected message generating elements only among said selected message generating elements, the partition being established so that the processing elements receive control messages in response to control messages generated by at least one of said control processors through one of said node groups at the upper root level.

11. A computer as defined in claim 10 in which each said message coupling circuit comprises a multiplexer/demultiplexer and a control circuit for receiving the partition control signal to enable for the multiplexer/demultiplexer to selectively couple messages between the node group and the selected one of the upper-level node groups.

12. A computer as defined in claim 10 further including a data router connected to said processing elements for transferring data messages each containing data among said processing elements, said control network nodes generating data router control signals for controlling said data router in accordance with selected contents of said control messages.

13. A computer as defined in claim 12 in which said data router comprises a plurality of data router node groups interconnected in a tree pattern corresponding to the tree pattern of said control network with each said data router node group having a corresponding control network node cluster, with each said control network node cluster generating a data router control signal for controlling the associated data router node group.

14. A computer as defined in claim 13 in which each said control network node group generates a data router control enabling signal in response to said selected contents of said control messages, each said control network node cluster with one control network node group coupling the data router control enabling signal to the associated data router node group as the data router control signal, and each said control network node cluster having a plurality of said control network node groups further including a control signal selection circuit for generating a data router control signal for the associated data router node group in response to the data router control enabling signals from the control network node groups of the control network node cluster.

15. A computer as defined in claim 14 in which each said control signal selection circuit includes:

A. a control signal enable register including a plurality of control signal enable flags each associated with a control network node group of the control network node cluster, the control signal enable flag associated with the selected control network node group having an enable condition and other control signal enable flags having a disable condition;

B. a plurality of control signal gate circuits each associated with a control network node group of the control network node cluster for generating a gated control signal corresponding to the data router enabling signal if the associated control signal enable flag has an enable condition; and

C. a control signal consolidation circuit for generating said control signal in response to the gated control signal from said control signal gate circuits.

16. A computer as defined in claim 13 in which each said data router node group further generates a status signal whose condition reflects selected status conditions, each said control network node cluster with one control network node group receiving the status signal from the associated data router node group and using the status signal in generating a message and each said control network node cluster having a plurality of said control network node groups further including a status signal coupling circuit connected to the control network node groups of the associated control network node cluster for selectively coupling the status signal as a gated status signal to the selected control network node group, the selected control network node group using the status signal in generating a message.

17. A computer as defined in claim 16 in which each status signal coupling circuit includes:

A. a status signal enable register including a plurality of status signal enable flags each associated with a control network node group of the control network node cluster, the status signal enable flag associated with the selected control network node group having an enable condition and other status signal enable flags having a disable condition;

B. a plurality of status signal gate circuits each connected to a control network node group of the control network node cluster for generating the gated status signal corresponding to the status signal if the associated status signal enable flag has an enable condition.

18. A computer as defined in claim 12 further comprising an input/output element for facilitating transfer of data between said processing elements and a data source over said data router in response to input/output commands, said input/output commands being generated by at least some of said control processors, said processing elements transferring said input/output commands to said input/output element over said data router to facilitate reception by said input/output element of input/output commands from control processors of any of said partitions.

19. A digital computer comprising a plurality of message generating elements each generating and receiving messages, a network for transferring messages among the message generating elements, the network comprising:

a plurality of node clusters interconnected in a tree pattern from a lower leaf level to an upper root level, each said node cluster including at least one node group, said node clusters in a level above at least one predetermined level having a larger number of said node groups than said node clusters of the predetermined level for transferring messages generated by said message generating elements among said message generating elements, each said node group in the node clusters of the predetermined level including a selective message coupling circuit, in response to a partition control signal, for selectively coupling messages between the node group and a selected one of the upper-level node groups; and

a partition control circuit, coupled to each of the message coupling circuits of each of the node groups, for generating said partition control signal to separately control the message coupling circuits of the node groups to partition the network into a plurality of partitions so that messages generated by the message generating elements in a selected group are transferred to only the message generating elements in the selected group.