Routing technique for a hierarchical interprocessor-communication network between massively-parallel processors

• US 5,224,100 A
• Filed: 05/09/1991
• Issued: 06/29/1993
• Est. Priority Date: 05/09/1991
• Status: Expired due to Fees

• Current Assignee: Sarnoff Corporation (SRI International, Inc.)
• Original Assignee: David Sarnoff Research Center, Inc.
• Inventors: Chin, Danny, Lee, Sue-Kyoung
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): TON, DANG T
• Application Number:
  US07/697,556
• Time in Patent Office: 782 Days
• Field of Search: 370/94.3, 370/94.1, 370/60, 340/825.02, 340/825.01, 340/825.52, 395/163-166, 371/8.1, 371/16.3, 371/68.1
• US Class Current: 370/408
• CPC Class Codes: G06F 15/17368 non hierarchical topologies

Abstract

A routing process for a single-instruction-multiple-data (SIMD) multi-level hierarchical network of nodes, which are arranged in clusters and interconnected by dual, unidirectional channels, are used to send data packets including routing address information during a succession of routing cycles from transmitting ones to receiving ones of a large number of parallel processors (e.g., 4096 processors arranged in a hierarchy of 8 cabinets, each of which contains a cluster of 8 circuit boards, with each circuit board containing a cluster of 64 processors). Each of the nodes includes a storage buffer having a capacity equal to a given number which is one more than the total number of channels terminating at that node. This routing process guarantees prevention of deadlock between levels and buffer overflow, and offers high-speed, low-cost interprocessor communication for SIMD computers.

Claims

1. In a single-instruction-multiple-data (SIMD) computer comprising parallel processors:

a routing process, including successive routing cycles, for routing a packet of data including address information between any of the parallel processors of said computer and any other of the parallel processors of said computer during said successive routing cycles of said computer;

wherein said parallel processors form the leaves of a hierarchical processor-interconnection tree structure having at least two hierarchical levels of nodes and a network of interconnection channels;

wherein said highest level of said hierarchical processor-interconnection tree structure includes at least two nodes with each node of a hierarchical level above the first hierarchical level of nodes being a parent node of a plurality of offspring nodes at the next lower hierarchical level;

wherein each of said first-level nodes is individually interconnected to a separate one of said parallel processors by a channel of said network, each offspring node is interconnected to its parent node by a channel of said network, each offspring node of a common parent node is interconnected to at least one other offspring node of that common parent node by a channel of said network, and each node of the highest hierarchical level is interconnected to at least one other node of the highest hierarchical level by a channel of said network;

wherein each of said network channels comprises dual, unidirectional links that allow simultaneous transmission of each of two data packets in opposite directions over that network channel; and

wherein each node includes (1) a buffer having a storage capacity for storing a given number of data packets which given number is one more than the total number of network channels terminating at that node, and (2) a router extending a connection which originated at a transmitting one of said parallel processors from that node toward a receiving one of said parallel processors over said channel network in accordance with address information contained in a data packet stored in the buffer of that node;

said routing process comprising the steps during each of said successive routing cycles of said computer of;

(a) at each parent node of the hierarchical processor-interconnection tree structure, sending down over a channel down-link to each of its offspring nodes data packets stored in the buffer of that parent node that contain address information that requires that data packet to be forwarded to that offspring node in order to extend a connection from a transmitting processor toward a receiving processor, until either the buffer of that parent node has one empty storage space or its offspring nodes have no packets to send up to it;

(b) in response to the buffer of a parent node having one empty storage space or its offspring nodes have no data packets to send up to it, signaling its offspring nodes from that parent node that each of its offspring nodes may attempt to send up to it a data packet previously stored in the buffer of that offspring node over a channel up-link that contains address information that requires that data packet to be forwarded from that parent node in order to extend a connection from transmitting processor toward a receiving processor; and

(c) in case the attempt set forth in step (b) cannot be accomplished during a current routing cycle by a given one of said offspring nodes of that parent node because a data packet is then being forwarded to that parent node from the buffer of another of its offspring nodes, forwarding the data packet from the buffer of said given one of said offspring nodes of that parent node during that current routing cycle for storage in the buffer of some other of said offspring nodes of that parent node.

2. In a single-instruction-multiple-data (SIMD) computer comprising massively parallel processors;

a routing process, including successive routing cycles, for routing a packet of data including address information between any of the massively parallel processors of said computer and any other of the massively parallel processors of said computer during said successive routing cycles of said computer;

wherein said computer comprises 4096 parallel processors that form the leaves of a hierarchical processor-interconnection tree structure having three hierarchical levels of nodes and a network of interconnection channels;

wherein said third level of said hierarchical processor-interconnection tree structure includes eight nodes with each of said eight nodes of said third hierarchical level being a parent node of a cluster of eight offspring nodes at the second hierarchical level, and each of said cluster of eight offspring nodes of the second hierarchical level being a parent node of a cluster of sixty-four offspring nodes at the first hierarchical level;

wherein each of said first-level nodes is individually interconnected to a separate one of said 4096 parallel processors by a channel of said network, each cluster offspring node at the first hierarchical level is interconnected to its parent node at the second hierarchical level by a channel of said network, each cluster offspring node at the second hierarchical level is interconnected to its parent node at the third hierarchical level by a channel of said network, and each of the nodes of the third hierarchical level is interconnected to another node of the third hierarchical level by a channel of said network;

wherein each of said network channels comprises dual, unidirectional links that allow simultaneous transmission of each of two data packets in opposite directions over that network channel; and

wherein each node includes (1) a buffer having a storage capacity for storing a given number of data packets which given number is one more than the total number of network channels terminating at that node, and (2) a router for extending a connection which originated at a transmitting one of said parallel processors from that node toward a receiving one of said parallel processors over said channel network in accordance with address information contained in a data packet stored in the buffer of that node;

said routing process comprising the steps during each of said successive routing cycles of said computer of;

(a) at each parent node of the hierarchical processor-interconnection tree structure, sending down over a channel down-link to each of its offspring nodes data packets stored in the buffer of that parent node that contain address information that requires that data packet to be forwarded to that offspring node in order to extend a connection from a transmitting processor toward a receiving processor, until either the buffer of that parent node has one empty storage space or its offspring nodes have no packets to send up to it;

(b) in response to the buffer of a parent node having one empty storage space or its offspring nodes have no data packets to send up to it, signaling its offspring nodes from that parent node that each of its offspring nodes may attempt to send up to it a data packet previously stored in the buffer of that offspring node over a channel up-link that contains address information that requires that data packet to be forwarded from that parent node in order to extend a connection from a transmitting processor toward a receiving processor; and

(c) in case the attempt set forth in step (b) cannot be accomplished during a current routing cycle by a given one of said offspring nodes of that parent node because a data packet is then being forwarded to that parent node from the buffer of another of its offspring nodes, forwarding the data packet from the buffer of said given one of said offspring nodes of that parent node during that current routing cycle for storage in the buffer of some other of said offspring nodes of that parent node.