Symbolic Wiring Routing Package
Eran Egozy
Original Issue: August 1990
Last Updated: Wed Nov 10 23:43:40 EST 1993
We have long since decided on a pretty good plan of how to wire up the network with RN1 components. Again, the procedure to generate a finished product from the network parameters (i.e, radix and dilation of chip, node dilation, number of stages in the network) can be seen in figure 1.
This transit note consists of documentation for the symbolic wire software package, SaWBoNe, some statistical data generated from the statistics procedure, and a discussion of relevant ideas regarding network wiring.
SaWBoNe, a Symbolic Wiring package for Bidelta Networks is a straight forward Lisp implementation of the network wiring ideas presented in [LM89] and [DKM90]. In addition, it provides a statistical analysis procedure to test a given generated network with a given number of component faults in the network.
A network that is used to connect a number of output nodes to the same number of input nodes has several parameters:
The number of nodes in a network is therefore .
The node dilation of a network can be smaller than the component dilation (even though this would seem undesirable from a fault tolerance point of view). However, in certain networks where the component radix is not large enough, this will lead to impossible routing cases in some stages and cause an error.
SaWBoNe can generate a wide class of bidelta networks with the provision that, whenever possible, no routing component in a certain stage will have more than one of its wires routed to the same component of the next stage. This has the effect of increasing fault tolerance while maintaining network performance.
When routing from stage to stage
within an equivalence
class, in most cases, there will be a choice of how to route all the
common radix outputs to the same logic group of the next stage. With
outputs leaving the common radix group, there are
possible
ways of routing to achieve the same logical operation.
SaWBoNe has the ability to route these signals randomly or
deterministically. The random algorithm simply picks random
connections, within the constraint mentioned above. The deterministic
routing guarantees a maximum single node expansion into the network,
but also minimizes group expansion into the network. Briefly, node
expansion refers to the number of different components that each node
can reach in a given stage. Group expansion implies that each node
will expand into a set of routers that is shared by as few nodes as
possible. As with the random algorithm, the deterministic algorithm
follows the above mentioned constraint.
determinism can be ``pushed into the network''. For example, the first and second stages alone can be made deterministic while the rest of the network can remain random. The opposite, ``pushing randomness into the network'', cannot be done since a deterministic network depends on its previous stages to be deterministic for it to have the characteristics mentioned above.
Two networks, each with the same network parameters, may be glued together to form a single network with twice the hardware and the node dilation doubled. This, conceptually, allows for a node to choose one network or the other when attempting to connect to an input node. Two such glued networks may be glued together to form a four times glued network with four times the hardware.
Normally, SaWBoNe creates routers with a dilation of one for the very last stage of the network to increase fault tollerence (perhaps at the expense of performance). Once a network is generated, the last stage dilation may be increased (and the number of components reduced accordingly) as long as the node dilation is not less than the component dilation.
Once a network has been generated, a statistics procedure can be run on the network in hopes to find the ``goodness'' of the network. The statistics procedure is straight forward. It simply assigns a certain number of routers to be faulty (spread randomly in the network) and determines if the network is still 100% connective. It iterates this procedure as many times as the user wants insure accurate statistics.
The network data representation and the statistical data are dumped into files that are suited to be interpreted by Fred Chong's network simulator.
SaWBoNe can be found in transit/wiring/eran. It should be run in a Lucid Lisp Interpreter. I have run it on a sparc2 (so the compiled version is for a sparc).
A network is generated with the procedure (sawbone
).
is the radix,
is the dilation,
is the number of
stages, and
is the node dilation.
The global variable *det-level* sets the amount of determinism to be pushed into the network. *det-level* set to -1 indicates a fully deterministic network. *det-level* set to any integer indicates that the network should be deterministic up to and including that stage and be random after that point. Thus, *det-level* set to 0 will produce a fully random network.
The network is kept in the global variable final.
Once a network is generated, it can be saved with (save-network
final ), where
is the version number. Files are saved into the
directory indicated by *net-dir*. Directories should be quoted
(eg., (setf *net-dir* ``/home/tr/networks'')).
To load a network, simply use the lisp command, (load ``filename'').
To glue two networks together, use (glue net1 net2), where net1 and net2 are networks of the same parameters (although one may be random while the other is deterministic). The glued networks is placed in the global variable final.
To dilate the last stage of a network, use (dilate final). This will multiply the dilation of the last stage chips by 2, and decrease the number of chips by 2.
Statistics are generated with (connectivity-test
).
is the number of networks to be generated.
is the maximum number of faults to be tried (if
, then for
each network, 2, 3, 4, and 5 faults will be tested at a time).
is
the number of randomly chosen repetitions that should be tested on
each of the
faults.
is a integer step skip for
.
(connectivity-test) dumps to file both the netlist and connectivity data into files placed in directories *net-dir* and *stat-dir* respectively. The statistics file will contain network parameters and statistic parameters and will list the faults that a network can tolerate (up to a global variable *number-test-faults*. It will then give the percentage of fault cases that can be tolerated by the network. Note that the chip numbers given are specifically intended for Fred Chong's simulator. Chips are labels consecutively from top left to bottom right.
The procedure (test-single
final) tests a single
network that has already been generated or loaded into the lisp
environment.
A postscript representation of these networks can be generated and
printed (code written by Andre Dehon) with (fwire final
), where
is the filename in quotes. This dumps out a
postscript file fname.ps into the /ps directory which can
be printed by from a shell with cat ps.h fname.ps ps.t | lpr
-P favorite-printer.
The saved networks are dumped to transit/wiring/eran/networks with the following format:
((
<
>) (stage0) (stage1) (stage2) ... (stage
))
where is the last stage dilation. It will appear as the fifth element
of the list only if the network has been dilated and the last stage dilation is
no longer 1. Each (stage
) is a list of wires. Each wire will be a list of
an output location to an input location:
((END
) (CHIP
))
or
((CHIP
) (CHIP
))
or
((CHIP
) (END
))
The filenames have the form net type.
Where
type gives information as to the randomness of the network.
is the version number.
Included here is a sample of the data generated with (connectivity-test 1 10 1000 1 4 2 3 2) with *det-level* set to 0, and a (connectivity-test 1 25 1000 1 4 2 4 2) with *det-level* set to 1.
to 5in to 5.5in
Radix = 4, dilation = 2, Stages = 3
to 5in to 5.5in
Radix = 4, dilation = 2, Stages = 4