Router table lookup mechanism

• US 5,970,232 A
• Filed: 11/17/1997
• Issued: 10/19/1999
• Est. Priority Date: 11/17/1997
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: Galles, Michael B., Passint, Randal S., Thorson, Greg
• Primary Examiner(s): PAN, DANIEL H
• Application Number:
  US08/971,587
• Time in Patent Office: 701 Days
• Field of Search: 395/200.7, 395/800.16, 395/200.6, 395/800.11, 395/200.71, 395/200.53, 395/800.13, 395/200.72, 395/800.14, 395/200.31, 395/500 , 395/200.69, 395/200.68, 395/800.22, 364/489, 364/488, 364/490, 364/491, 364/418.28, 364/DIG. 1, 364/DIG. 2, 371/49.3, 370/389, 370/351, 370/380
• US Class Current: 709/238
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus

Abstract

A multiprocessor computer system includes processing element nodes interconnected by physical communication links in a n-dimensional topology, which includes at least two global partitions. Routers route messages between processing element nodes and include ports for receiving and sending messages, and lookup tables having a local router table having directions for routing between processor element nodes within a global partition, and a global router table having directions for routing between processor element nodes located in different global partitions. The directions from the local table are selected for routing from the next router along a given route if the current processing element node is in a destination global partition or if the current processing element node is one plus or minus hop from reaching the destination global partition and the route is exiting on a port that routes to the destination global partition, else the directions from the global router table are selected for routing from the next router.

Claims

1. A multiprocessor computer system comprising:

a plurality of processing element nodes, each processing element node having at least one processor and memory;

physical communication links interconnecting the processing element nodes in a n-dimensional topology, which includes at least two global partitions of processing element nodes;

routers for routing messages between the plurality of processing element nodes on the physical communication links, each router including;

ports for receiving and sending messages, and

lookup tables associated to ports and holding entries having directions for routing from a next router along a given route, each lookup table including a local router table having directions for routing between processor element nodes within a global partition, and a global router table having directions for routing between processor element nodes located in different global partitions, wherein the directions from the local table are selected for routing from the next router if a current processing element node is in a destination global partition or if the current processing element node is one plus or minus hop from reaching the destination global partition and the given route is exiting on a port that routes to the destination global partition, else the directions from the global router table are selected for routing from the next router.

2. The multiprocessor computer system of claim 1 wherein the topology is a torus topology, wherein at least one of the n dimensions has a radix greater than four.

3. The multiprocessor computer system of claim 1 wherein each router further includes a programmable register having a force local table bit, that, when set, causes the directions from the local table to be selected for routing from the next router.

4. The multiprocessor computer system of claim 1 wherein each router further includes programmable registers having a plus global valid bit and a minus global valid bit, such that the directions from the local table are selected for routing from the next router if the current processing element node is in the destination global partitions or if the current processing element node is one plus hop from reaching the destination global partition and the plus global valid bit is set and the route is exiting on a port that routes to the destination global partition or if the current processing element node is one minus hop from reaching the destination global partition and the minus global valid bit is set and the route is exiting on a port that routes to the destination global partition, else the directions from the global router table are selected for routing from the next router.

5. The multiprocessor computer system of claims 1 wherein the local table includes local table entries, wherein each local router table entry includes a -global direction field, a +global direction field, and a local direction field.

6. The multiprocessor computer system of claim 5 wherein the local direction field is selected for routing from the next router if the current processing element node is in the destination global partitions, the -global direction field is selected for routing from the next router if the current processing element node is one minus hop from reaching the destination global partition and the route is exiting on a port that routes to the destination global partition, and the +global direction field is selected for routing from the next router if the current processing element node is one plus hop from reaching the destination global partition and the route is exiting on a port that routes to the destination global partition.

7. The multiprocessor computer system of claim 1 wherein when the topology is a six or less dimensional hypercube, only the local router table is used to obtain the directions for routing from the next router.