Router for parallel computer including arrangement for redirecting messages

• US 5,530,809 A
• Filed: 01/14/1994
• Issued: 06/25/1996
• Est. Priority Date: 10/03/1990
• Status: Expired due to Term

• Current Assignee: TM Patents LP
• Original Assignee: Thinking Machines Corporation (Oracle Corporation)
• Inventors: Wells, David, Kahle, Brewster, Walker, Bruce J., Hillis, W. Daniel, Douglas, David C., Kuszmaul, Bradley C., Leiserson, Charles E., Yang, Shaw-Wen, Feynman, Carl R.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): DINH, DUNG C
• Application Number:
  US08/181,711
• Time in Patent Office: 893 Days
• Field of Search: 395/200, 395/800, 395/200.02, 395/200.2, 370/85.1, 370/85.6, 370/92, 370/93
• US Class Current: 709/250
• 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 message generating nodes interconnected by a routing network. The routing network transfers messages among the message generating elements in accordance with address information identifying a destination message generating element. Each message generating node includes a message data generator and a network interface. The message data generator generates message data items each including an address data portion comprising a destination identifier. The network interface includes a message generator and an address translation table, the table including a plurality of entries identifying, for at least one destination identifier, a translated destination identifier. The message generator, in response to the receipt of a message data item from the message data generator, generates a message for transmission to the routing network. In generating the message, the message generator performs an address translation operation in connection with the address data and the contents of the address translation table to generate updated address data which it uses data in connection with generating address information for the message.

Claims

1. A digital computer comprising a plurality of message generating nodes interconnected by a routing network:

A. the routing network transferring messages among said message generating nodes in accordance with address information identifying a destination message generating element to receive the message;

B. each message generating node including;

i. a message data generator for generating message data items each including an address data portion comprising a destination identifier;

ii. an interface including;

a) an address translation table including a plurality of entries each identifying, for at least one destination identifier, a translated destination identifier;

b) a message generator for generating, in response to the receipt of a message data item from said message data generator, a message for transmission to the routing network, said message generator including an address translator comprising;

i) a chunk size identifier for identifying a chunk size, said chunk size identifying a number of consecutive message generating nodes;

ii) a window extraction circuit for generating an address translation table entry identifier in response to said chunk size identifier and said address data and coupling said address translation table entry identifier to said address translation table, the address translation table selecting an entry in response to the received address translation table identifier and the original address values in said entries, said address translation table providing the translated address value from the selected entry at an output;

iii) a window insertion circuit for generating said updated address value in response to said chunk size identifier, the address data and the translated address value from the output of said address translation table;

said message generator using the updated address data in connection with generating address information for the message, the message generator coupling the message to said routing network.

2. A digital computer as defined in claim 1 in which the address data comprises a series of address digits, said window extraction circuit generating said address translation table entry identifier as a selected series of said address digits, the window extraction circuit selecting the series of address digits in response to the chunk size identifier.

3. A digital computer as defined in claim 1 in which said address value, said updated address value and said translated address value each comprises a respective series of address digits, said window insertion circuit generating said updated address value by substituting the series of address digits comprising said translated address value as a selected series in the address data, the window insertion circuit selecting the digits of the address data for which it substitutes the translated address value in response to the chunk size identifier.

4. A digital computer as defined in claim 1 wherein each message data item further includes an address mode flag having a plurality of conditions identifying the address data portion as having one of a plurality of address modes, said message generator selectively using the address data from the message data item or the updated address data from said address translator in generating a message in response to the message data item in response to the condition of the address mode flag of a message data item.

5. A digital computer as defined in claim 4 in which each message generating node is identified by a network identifier, in one address mode the address data in the address data portion of the message data item containing the network identifier of the message generating node to receive the message generated by said message generator in response thereto.

6. A digital computer as defined in claim 4 in which each message generating node is identified by a network identifier, in one address mode the address data in the address data portion of the message data item containing a relative address value identifying the difference between the network identifiers of the message generating node to receive the message and a predetermined message generating node.

7. A digital computer as defined in claim 4 in which said message generator further includes:

A. a latch;

B. an address mode flag decoder for decoding the address mode flag of a received message data item and generating an address mode signal to identify the address mode;

C. a multiplexer for selectively, in response to the address mode signal from said address mode flag decoder, coupling the address data from the message data item or the updated address data from said address translator as updated address data for storage in said latch; and

D. a control circuit for controlling storage of updated address data from said multiplexer in said latch.

8. A digital computer as defined in claim 7 wherein:

A. said address translation table provides an translated address value to said address translator in response to a translation enabling signal, and generates a translated address value valid signal when the translated address value provided to said address translator is valid; and

B. said control circuit includes;

i. an address translation table control circuit for selectively generating said translation enabling signal in response to said address mode signal;

ii. a latch control circuit for generating, in response to said address mode signal and the translated address value valid signal from said address translation table, an enabling signal for enabling said latch to store the updated address data from said multiplexer.

9. A digital computer as defined in claim 8 in which said latch has an output terminal connected to couple the contents of said latch to an updated address value processing stage, said updated address value processing stage generating an advance control signal for controlling the coupling of the contents of said latch thereto, said address translation table control circuit and said latch control circuit further operating in response to said advance control signal.

10. A digital computer as defined in claim 9 in which:

A. said message generator further includes delay indication generating means for generating, in response to a delay indication enabling signal, a delay indication to said updated address value processing stage to indicate a delay in generating an updated address value; and

B. said control circuit further includes a delay indication control circuit for generating said delay indication enabling signal in response to said advance control signal, said translated address value valid signal and said address mode signal, thereby to enable said delay indication generating means to generate the delay indication enabling signal in response to a delay by said address translation table in providing a translated address value if the address mode signal identifies a selected address mode in which the updated address data is generated in response to the translated address value.

11. In a digital computer comprising a plurality of message generating nodes interconnected by a routing network, the routing network transferring messages among said message generating nodes in accordance with address information identifying a destination message generating element to receive the message, a message generating node comprising:

A. a message data generator for generating message data items each including an address data portion comprising a destination identifier;

B. an interface including;

i. an address translation table including a plurality of entries each identifying, for at least one destination identifier, a translated destination identifier;

ii. a message generator for generating, in response to the receipt of a message data item from said message data generator, a message for transmission to the routing network, said message generator including an address translator comprising;

a) a chunk size identifier for identifying a chunk size, said chunk size identifying a number of consecutive message generating nodes;

b. a window extraction circuit for generating an address translation table entry identifier in response to said chunk size identifier and said address data and coupling said address translation table entry identifier to said address translation table, the address translation table selecting an entry in response to the received address translation table identifier and the original address values in said entries, said address translation table providing the translated address value from the selected entry at an output;

c. a window insertion circuit for generating said updated address value in response to said chunk size identifier, the address data and the translated address value from the output of said address translation table;

said message generator using the updated address data in connection with generating address information for the message, the message generator coupling the message to said routing network.

12. A message generating node as defined in claim 11 in which the address data comprises a series of address digits, said window extraction circuit generating said address translation table entry identifier as a selected series of said address digits, the window extraction circuit selecting the series of address digits in response to the chunk size identifier.

13. A message generating node as defined in claim 11 in which said address value, said updated address value and said translated address value each comprises a respective series of address digits, said window insertion circuit generating said updated address value by substituting the series of address digits comprising said translated address value as a selected series in the address data, the window insertion circuit selecting the digits of the address data for which it substitutes the translated address value in response to the chunk size identifier.

14. A message generating node as defined in claim 11 wherein each message data item further includes an address mode flag having a plurality of conditions identifying the address data portion as having one of a plurality of address modes, said message generator selectively using the address data from the message data item or the updated address data from said address translator in generating a message in response to the message data item in response to the condition of the address mode flag of a message data item.

15. A message generating node as defined in claim 14 in which each message generating node is identified by a network identifier, in one address mode the address data in the address data portion of the message data item containing the network identifier of the message generating node to receive the message generated by said message generator in response thereto.

16. A message generating node as defined in claim 14 in which each message generating node is identified by a network identifier, in one address mode the address data in the address data portion of the message data item containing a relative address value identifying the difference between the network identifiers of the message generating node to receive the message and a predetermined message generating node.

17. A message generating node as defined in claim 14 in which said message generator further includes:

A. a latch;

B. an address mode flag decoder for decoding the address mode flag of a received message data item and generating an address mode signal to identify the address mode;

C. a multiplexer for selectively, in response to the address mode signal from said address mode flag decoder, coupling the address data from the message data item or the updated address data from said address translator as updated address data for storage in said latch; and

D. a control circuit for controlling storage of updated address data from said multiplexer in said latch.

18. A message generating node as defined in claim 17 wherein:

A. said address translation table provides an translated address value to said address translator in response to a translation enabling signal, and generates a translated address value valid signal when the translated address value provided to said address translator is valid; and

B. said control circuit includes;

i. an address translation table control circuit for selectively generating said translation enabling signal in response to said address mode signal;

ii. a latch control circuit for generating, in response to said address mode signal and the translated address value valid signal from said address translation table, an enabling signal for enabling said latch to store the updated address data from said multiplexer.

19. A message generating node as defined in claim 18 in which said latch has an output terminal connected to couple the contents of said latch to an updated address value processing stage, said updated address value processing stage generating an advance control signal for controlling the coupling of the contents of said latch thereto, said address translation table control circuit and said latch control circuit further operating in response to said advance control signal.

20. A message generating node as defined in claim 19 in which:

A. said message generator further includes delay indication generating means for generating, in response to a delay indication enabling signal, a delay indication to said updated address value processing stage to indicate a delay in generating an updated address value; and

B. said control circuit further includes a delay indication control circuit for generating said delay indication enabling signal in response to said advance control signal, said translated address value valid signal and said address mode signal, thereby to enable said delay indication generating means to generate the delay indication enabling signal in response to a delay by said address translation table in providing a translated address value if the address mode signal identifies a selected address mode in which the updated address data is generated in response to the translated address value.