Tree network including arrangement for establishing sub-tree having a logical root below the network's physical root

• US 6,449,667 B1
• Filed: 07/16/1999
• Issued: 09/10/2002
• Est. Priority Date: 10/03/1990
• Status: Expired due to Fees

• Current Assignee: TM Patents LP
• Original Assignee: TM Patents LP
• Inventors: Douglas, David C., Ganmukhi, Mahesh N., Hill, Jeffrey V., Wong-Chan, Monica C.
• Primary Examiner(s): Ray, Gopal C.
• Application Number:
  US09/354,425
• Time in Patent Office: 1,152 Days
• Field of Search: 709/244, 709/228, 709/237, 709/200, 709/201, 709/203, 709/252, 709/300, 709/305, 709/253, 370/408, 712/11, 712/29, 712/17, 710/131, 710/28, 710/52, 340/825
• US Class Current: 710/28
• 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 comprising a plurality of processors interconnected by a network for transferring messages among the processors. At least one processor generates messages of a configuration type. The network comprises a plurality of nodes interconnected in a tree pattern in a series of levels from a lower leaf level to an upper physical root level, with the leaf nodes connected to the processors. Each of the nodes includes a root flag that can be set or cleared in response to a message of the configuration type to establish the node as a logical root. For each node, if the node is a logical root it transfers messages received from a node at a lower level in the tree back down the tree, but if the node is not a logical root it transfers messages received at a lower level node to a higher level node.

Claims

1. A digital computer comprising:

A. a plurality of message generating elements each generating and receiving messages, at least one message generating element generating messages including configuration messages;

B. a network for transferring messages among said message generating elements, said network comprising a plurality of nodes interconnected in a tree pattern in a series of levels from a lower leaf level to an upper physical root level, nodes in the leaf level being connected to receive messages from and transfer messages to said message generating elements, each node including;

i. a root flag having a root indication condition establishing the node as a logical root and a non-root indication condition;

ii. an up-tree transfer portion for receiving messages from a plurality of message generating elements or a lower-level control network node connected thereto and for generating a message in response thereto, said up-tree transfer portion selectively coupling the message to a higher level control network node in response to the condition of the root flag;

iii. a root flag condition establishment portion for establishing the condition of the root flag in response to reception by the up-tree portion of a configuration message, the configuration message includes a height value, and each level of the network has a level height identifier, the root flag condition establishment portion in each node further using the height value from the configuration message as received by the up-tree transfer portion and the level height identifier of the node in establishing the condition of the root flag; and

iv. a down-tree transfer portion for selectively receiving messages from a higher-level node or the up-tree transfer portion in response to the condition of the root flag and generating a message in response thereto for transmission to lower-level nodes or message generating elements connected thereto.

2. A computer as defined in claim 1 in which, in each node:

A. said up-tree transfer portion selectively couples received messages to a higher-level control network node if the root flag has a non-root indication condition; and

B. said down-tree transfer portion selectively generates messages in response to messages from a higher-level node if the root flag has a non-root indication condition or the up-tree transfer portion if the root flag has a root indication condition.

3. A computer as defined in claim 2 in which multiple-source messages contain a data portion, each node further including a data processing portion for performing a processing operation in connection with data of contemporaneously-received multiple-source messages.

4. A computer as defined in claim 3 in which message generating elements further generates messages of an abstain message, the data processing portion of each node, in response to the contemporaneous receipt of a multiple-source message and an abstain message generating a multiple-source message for transfer including processed data corresponding to the data in the received multiple-source message.

5. A computer as defined in claim 4 in which message generating elements further generate messages of an abstain message, the up-tree transfer portion of each node generating an abstain message in response to contemporaneous receipt of abstain messages from all nodes or message generating elements from which it receives messages.

6. A computer as defined in claim 5 in which each node further includes a root identification signal generating circuit for generating a root identification signal for transfer to a node constituting its parent in the next higher level, the root identification signal generating circuit generating the root identification signal having a condition corresponding to the condition of its root flag, each node further including an internal abstain message generating circuit connected to the up-tree transfer portion for generating an internal abstain message for transfer to the up-tree transfer portion in response to receipt of a root identification signal indicating that the root flag of the node generating the root identification signal is set.

7. A computer as defined in claim 3 in which the up-tree transfer portion of each of at least some of said nodes further includes:

A. a plurality of message input terminals each for receiving a message from a lower-level node or a message generating element;

B. a plurality of multiple-source message buffer circuits each for buffering multiple-source messages received by one of the message input terminals; and

C. a multiple-source buffer control circuit for enabling said multiple-source message buffers to selectively buffer messages received by the message input terminals.

8. A computer as defined in claim 7 in which said multiple-source buffer control circuit includes:

A. a plurality of message type determination circuits for determining the types of messages received by respective message input terminals; and

B. a storage enabling circuit for enabling respective multiple-source message buffer circuits to buffer messages in response to the message types of messages concurrently received by the message input terminals.

9. A computer as defined in claim 8 in which said storage enabling circuit enables a multiple-source message buffer circuit to buffer a message received by its respective message input terminal if the associated message type determination circuit determines that the message received by the message input terminal is a multiple-source message and the other message type determination circuit determines that the message received by the message input terminal associated therewith is of another message type.

10. A computer as defined in claim 7 in which said multiple-source buffer control circuit further selectively enables the multiple-source message buffer circuits to couple multiple-source messages buffered thereby to the data processing portion in response to receipt at the other message input terminal of a multiple-source message.

11. A computer as defined in claim 10 in which said multiple-source buffer control circuit includes:

A. a plurality of buffer status indicators each for indicating whether an associated multiple-source message buffer circuit is buffering a message;

B. a plurality of message type determination circuits for determining the types of messages received by respective message input terminals; and

C. a transfer enabling circuit for enabling respective multiple-source message buffer circuits to transfer messages from said multiple-source message buffer circuits in response to the conditions of said buffer status indicators and the message types of messages received by the message input terminals as determined by the associated message type determination circuits.

12. A computer as defined in claim 11 in which said transfer enabling circuit enables a buffer associated with one message input terminal to transfer a message in response to the coincidence of its buffer status indicator indicating it is buffering a message and the message type determination circuit associated with the other message input terminal indicating it is receiving a multiple-source message.

13. A computer as defined in claim 3 in which multiple-source messages further include an operation identification, the data processing portion in each node performing a selected processing operation as identified by said operation identification.

14. A computer as defined in claim 13 in which the data processing portion in each node includes an up-tree data processing portion and one operation identification identifies a reduce operation, the up-tree data processing portion in each node performing a data processing operation in connection with data from multiple-source messages received by the up-tree transfer portion for generating processed data that is included in the message generated by the up-tree transfer portion.

15. A computer as defined in claim 14 in which the down-tree transfer portion in each node, in response to receipt of a multiple-source message in which the operation identification identifies a reduce operation, transmits messages for transmission to lower-level nodes or message generating elements connected thereto including data from the received multiple-source message.

16. A computer as defined in claim 13 in which one operation identification identifies a scan operation, the data processing portion in each node includes an up-tree data processing portion and a down-tree data processing portion each for performing a data processing operation in connection with data of multiple-source messages received by the respective uptree transfer portion and down-tree transfer portion.

17. A computer as defined in claim 16 in which each node further includes a scan buffer connected to said up-tree data processing portion and said down-tree data processing portion, said uptree data processing portion selectively generating intermediate data for storage in said scan buffer in response to operation identification, the down-tree data processing portion performing a data processing operation in connection with the intermediate data stored in the scan buffer and multiple source messages received by the down-tree transfer portion as determined by the operation identification of the respective multiple-source message.

18. A computer as defined in claim 17 in which the down-tree portion includes:

A. a plurality of message output terminals each for transmitting a message to a lower-level node or a message generating element; and

B. an output message control circuit responsive to the condition of the root flag for enabling said down-tree data processing portion to generate data for selective inclusion in messages transmitted through selected ones of said message output terminals.

19. A computer as defined in claim 16 in which

A. said uptree portion includes:

i. an up-tree message output terminal for transmitting a message to a higher-level node;

ii. a plurality of up-tree message input terminals each for receiving a message from a lower-level node or a message generating element;

iii. a scan buffer connected to said up-tree data processing portion, and

iv. an up-scan control portion for enabling said up-tree data processing portion to selectively generate intermediate data for storage in said scan buffer in response to operator type identification and up-tree information to be transmitted in a message through said up-tree message output terminal; and

B. said down-tree portion includes;

i. a down-tree message input terminal for receiving a message from a higher-level node;

ii. a plurality of down-tree message output terminals each for transmitting a message to the lower-level node or message generating element; and

iii. a down-scan control portion for enabling said down-tree data processing portion to selectively generate data from either said scan buffer or from data received in a multiple-source message received by said down-tree message input terminal, the generated data being coupled to respective ones of said down-tree message output terminals for transmission thereby.

20. A computer as defined in claim 19 in which:

A. the up-scan control portion enables;

i. the data in one multiple-source message that was received from one up-tree message input terminal to be stored in the scan buffer as intermediate data, and

ii. the up-tree data processing portion to generate processed data in response to data from multiple-source messages received by both uptree message input terminals; and

B. the down-scan control portion enables;

i. the data in the scan buffer to be coupled to one down-tree message output terminal for inclusion in a multiple-source message transmitted thereby; and

ii. the down-tree data processing portion to generate processed data in response to data from the scan buffer and a multiple-source message received by said down-tree message input terminal, the processed data generated by the down-tree data processing portion being coupled to the other down-tree message output terminal is for inclusion in a multiple-source message transmitted thereby.

21. A computer as defined in claim 20 in which the down-scan control portion further operates in response to the condition of the root flag to couple predetermined data to one down-tree message output terminal and the data in the scan buffer to the other down-tree message output terminal, both for inclusion in a multiple-source message transmitted thereby.

22. A computer as defined in claim 20 in which each multiple-source message identifying a scan operation further identifies a scan direction,

A. the up-tree portion further includes a source select circuit connected to said up-tree message input terminals, said scan buffer and said uptree data processing portion for selectively coupling data received from one or the other of said up-tree message input terminals as selected by said scan direction to be stored in the scan buffer as intermediate data;

and

B. said down-tree portion further includes a transmit select circuit for selecting the down-tree message output circuit to receive the data in the scan buffer or the processed data generated by the down-tree data processing portion as selected by the scan direction of the multiple-source message received by the down-tree message input terminal.

23. A computer as defined in claim 19 in which each multiple-source message further includes a segment identifier having predetermined values, each node further includes a segment flag having selected conditions, said up-scan control portion conditioning circuit for conditioning said segment flag in response to reception by a selected up-tree message input terminal of a multiple-source message whose segment identifier has one of said predetermined values, and generating said intermediate information and said up-tree information in response to said segment flag, the down-scan control portion further controlling said down-tree data processing portion in response to said segment flag.

24. A node in a digital computer comprising a plurality of message generating elements each generating and receiving messages, at least one message generating element generating messages including configuration messages and a network for transferring messages among said message generating elements, said network comprising a plurality of nodes interconnected in a tree pattern in a series of levels from a lower leaf level to an upper physical root level, nodes in the leaf level being connected to receive messages from and transfer messages to said message generating elements, the node including:

A. a root flag having a root indication condition establishing the node as a logical root and a non-root indication condition;

B. an up-tree transfer portion for receiving messages from a plurality of message generating elements or a lower-level control network node connected thereto and for generating a message in response thereto, said up-tree transfer portion selectively coupling the message to a higher-level control network node in response to the condition of the root flag;

C. a root flag condition establishment portion for establishing the condition of the root flag in response to reception by the up-tree transfer portion of a configuration message, the configuration message includes a height value, and each level of the network has a level height identifier, the root flag condition establishment portion further using the height value from the configuration message as received by the up-tree transfer portion and the level height identifier of the node in establishing the condition of the root flag; and

D. a down-tree transfer portion for selectively receiving messages from a higher level node or the up-tree transfer portion in response to the condition of the root flag and generating a message in response thereto for transmission to a lower-level nodes or message generating elements connected thereto.

25. A node as defined in claim 24 in which:

A. said up-tree transfer portion selectively couples received messages to a higher-level control network node if the root flag has a non-root indication condition; and

B. said down-tree transfer portion selectively generates messages in response to messages from a higher-level node if the root flag has a non-root indication condition or the up-tree transfer portion if the root flag has a root indication condition.

26. A node as defined in claim 25 in which multiple-source messages contain a data portion, said node further including a data processing portion for performing a processing operation in connection with data of contemporaneously-received multiple-source messages.

27. A node as defined in claim 26 in which the data processing portion, in response to the contemporaneous receipt of a multiple-source message and an abstain message, generates a multiple-source message for transfer including processed data corresponding to the data in the received multiple-source message.

28. A node as defined in claim 27 in which the up-tree transfer portion generating an abstain message in response to contemporaneous receipt of abstain messages from all nodes or message generating elements from which it receives messages.

29. A node as defined in claim 28 further including a root identification signal generating circuit for generating a root identification signal for transfer to a node constituting its parent in the next higher level, the root identification signal generating circuit generating the root identification signal having a condition corresponding to the condition of its root flag, the node further including an internal abstain message generating circuit connected to the up-tree transfer portion for generating an internal abstain message for transfer to the up-tree transfer portion in response to receipt of a root identification signal indicating that the root flag of the node generating the root identification signal is set.

30. A node as defined in claim 26 in which the up-tree transfer portion includes

A. a plurality of message input terminals each for receiving a message from a lower-level node or a message generating element;

B. a plurality of multiple-source message buffer circuits each for buffering multiple-source messages received by one of the message input terminals; and

C. a multiple-source buffer control circuit for enabling said multiple-source message buffers to selectively buffer messages received by the message input terminals.

31. A node as defined in claim 30 in which said multiple-source buffer control circuit includes:

A. a plurality of message type determination circuits for determining the types of messages received by respective message input terminals; and

B. a storage enabling circuit for enabling respective multiple-source message buffer circuits to buffer messages in response to the message types of messages concurrently received by the message input terminals.

32. A node as defined in claim 31 in which said storage enabling circuit enables a multiple-source message buffer circuit to buffer a message received by its respective message input terminal if the associated message type determination circuit determines that the message received by the message input terminal is a multiple-source message and the other message type determination circuit determines that the message received by the message input terminal associated therewith is of another message type.

33. A node as defined in claim 32 in which said a multiple-source buffer control circuit further selectively enables the multiple-source message buffer circuits to couple multiple-source messages buffered thereby to the data processing portion in response to receipt at the other message input terminal of a multiple-source message.

34. A node as defined in claim 33 in which said multiple-source buffer control circuit includes:

A. a plurality of buffer status indicators each for indicating whether an associated multiple-source message buffer circuit is buffering a message;

B. a plurality of message type determination circuits for determining the types of messages received by respective message input terminals; and

C. a transfer enabling circuit for enabling respective multiple-source message buffer circuits to transfer messages from said multiple-source message buffer circuits in response to the conditions of said buffer status indicators and the message types of messages received by the message input terminals as determined by the associated message type determination circuits.

35. A node as defined in claim 34 in which said transfer enabling circuit enables a buffer associated with one message input terminal to transfer a message in response to the coincidence of its buffer status indicator indicating it is buffering a message and the message type determination circuit associated with the other message input terminal indicating it is receiving a multiple-source message.

36. A node as defined in claim 26 in which multiple-source messages further include an operation identification, the data processing portion performing a selected processing operation as identified by said operation identification.

37. A node as defined in claim 36 in which the data processing portion includes an up-tree data processing portion and one operation identification identifies a reduce operation, the up-tree data processing portion performing a data processing operation in connection with data from multiple-source messages received by the up-tree transfer portion for generating processed data that is included in the message generated by the up-tree transfer portion.

38. A node as defined in claim 37 in which the down-tree transfer portion, in response to receipt of a multiple-source message in which the operation identification identifies a reduce operation, transmits messages for transmission to lower-level nodes or message generating elements connected thereto including data from the received multiple-source message.

39. A node as defined in claim 36 in which one operation identification identifies a scan operation, the data processing portion includes an up-tree data processing portion and a down-tree data processing portion each for performing a data processing operation in connection with data of multiple-source messages received by the respective up-tree transfer portion and down-tree transfer portion.

40. A node as defined in claim 39 further including a scan buffer connected to said up-tree data processing portion and said down-tree data processing portion, said up-tree data processing portion selectively generating intermediate data for storage in said scan buffer in response to operation identification, the down-tree data processing portion performing a data processing operation in connection with the intermediate data stored in the scan buffer and multiple source messages received by the down-tree transfer portion as determined by the operation identification of the respective multiple-source message.

41. A node as defined in claim 40 in which the down-tree portion includes:

A. a plurality of message output terminals each for transmitting a message to a lower-level node or a message generating element; and

B. an output message control circuit responsive to the condition of the root flag for enabling said down-tree data processing portion to generate data for selective inclusion in messages transmitted through selected ones of said message output terminals.

42. A node as defined in claim 39 in which

A. said up-tree portion includes:

i. an up-tree message output terminal for transmitting a message to a higher-level node;

ii. a plurality of up-tree message input terminals each for receiving a message from a lower-level node or a message generating element;

iii. a scan buffer connected to said up-tree data processing portion, and

iv. an up-scan control portion for enabling said up-tree data processing portion to selectively generate intermediate data for storage in said scan buffer in response to operator type identification and up-tree information to be transmitted in a message through said up-tree message output terminal; and

B. said down-tree portion includes;

i. a down-tree message input terminal for receiving a message from a higher-level node;

ii. a plurality of down-tree message output terminals each for transmitting a message to the lower-level node or message generating element; and

iii. a down-scan control portion for enabling said down-tree data processing portion to selectively generate data from either said scan buffer or from data received in a multiple-source message received by said down-tree message input terminal, the generated data being coupled to respective ones of said down-tree message output terminals for transmission thereby.

43. A node as defined in claim 42 in which:

A. the up-scan control portion enables;

i. the data in one multiple-source message that was received from one up-tree message input terminal to be stored in the scan buffer as intermediate data, and

ii. the up-tree data processing portion to generate processed data in response to data from multiple-source messages received by both up-tree message input terminals; and

B. the down-scan control portion enables;

i. the data in the scan buffer to be coupled to one down-tree message output terminal for inclusion in a multiple-source message transmitted thereby; and

ii. the down-tree data processing portion to generate processed data in response to data from the scan buffer and a multiple-source message received by said down-tree message input terminal, the processed data generated by the down-tree data processing portion being coupled to the other down-tree message output terminal for inclusion in a multiple-source message transmitted thereby.

44. A node as defined in claim 43 in which the down-scan control portion further operates in response to the condition of the root flag to couple predetermined data to one down-tree message output terminal and the data in the scan buffer to the other down-tree message output terminal, both for inclusion in a multiple-source message transmitted thereby.

45. A node as defined in claim 43 in which each multiple-source message identifying a scan operation further identifies a scan direction,

A. the up-tree portion further includes a source select circuit connected to said up-tree message input terminals, said scan buffer and said up-tree data processing portion for selectively coupling data received from one or the other of said up-tree message input terminals as selected by said scan direction to be stored in the scan buffer as intermediate data;

and

B. said down-tree portion further includes a transmit select circuit for selecting the down-tree message output circuit to receive the data in the scan buffer or the processed data generated by the down-tree data processing portion as selected by the scan direction of the multiple-source message received by the down-tree message input terminal.

46. A node as defined in claim 42 in which each multiple-source message further includes a segment identifier having predetermined values, said node further including a segment flag having selected conditions, said up-scan control portion conditioning circuit for conditioning said segment flag in response to reception by a selected up-tree message input terminal of a multiple-source message whose segment identifier has one of said predetermined values, and generating said intermediate information and said up-tree information in response to said segment flag, the down-scan control portion further controlling said down-tree data processing portion in response to said segment flag.