Transputer link reconfiguration: switching networks for 4-valent graphs

The paper describes the development and implementation of a novel transputer link switching network based on an Eulerian cycle decomposition of a graph of transputer link connections. This network provided completely universal routing of all transputer graphs and multigraphs. The switch settings can be constructed in a time linear in the number of processors. It is shown how the network can be extended for machines containing many hundreds of transputers by the use of a multilayer network. This multilayer network, based upon the work of Clos and Benes can be either rearrangeable or non-blocking. The paper compares this network with other published transputer link switching networks and shows how existing ´fixed-backbone´ Hamiltonian chain designs can be modified to provide complete connectivity using the Eulerian cycle algorithm.