|
The interconnection net is a sparsely populated 3-D packet switched containing p^(3/2) nodes, where p is the number of processors.
|
|
These nodes are toroidally connected in three dimensions to form a p^(1/2)-ary three-cube, and processor and memory resources are attached to some of the nodes.
|
|
The latency of a node is three cycles: a message spends two cycles in the node logic proper and one on the wire that connects the node to its neighbors.
|
|
A p-processor system has worst-case one-way latency of 4.5p^(1/2) cycles.
|
Messages are assigned random priorities and then routed in priority order. Under heavy load, some messages are derouted by this process. The randomization at each node insures that each packet eventually reaches its destination.
-
Randomization ensures good "worst-case" performance. This is a strategy which is well supported by theory (E.g. Les Valiant Harvard)
|
