Background:
(Based on problems 3 and 4 of the text, page 394)
Consider a multicomputer with 1024 processors, each with 4 ports for
communication with other processors. There are two natural topologies
for such a system:
- Toroidal. Link the machines in a 32 by 32 square array, with each
machine communicating
with its neighbors to the left, right, up and down. The open links on the
left side of the array can be connected to the open links on the right
(converting the array to a cylindrical structure), and then the open
links on the top can be connected to the open links on the bottom to create
a torus.
- Tetrahedral. Link the machines in groups of 4, where 3 links on each
machine in the group are used for direct communication with the 3 others in
that group, so that the group may be viewed as a tetrahedron. Each such
tetrahedral group has 4 open links, so we can now link groups of 4 primitive
tetrahedra into higher order tetrahedra. If we call tetrahedra made of 4
machines first-order tetrahedra, and groups of 16 machines second-order
tetrahedra, our complete system of 1024 machines will be a 5th-order
tetrahedron.
Part a:
For each of the above, what is the longest path from one machine to another
in the network.
Part b:
For each of the above, what is the minimum number of carefully chosen links
that must be broken to partition the network into two independent networks.
Part c:
Given that messages are addressed with a 10 bit destination address, suggest
an address assignment scheme for these networks that leads to a relatively
simple message forwarding algorithm. You must document both the address
assignment scheme and the corresponding addressing algorith. (Ignore
fault tolerance!)