Interconnection Topologies and Routing for Parallel Processing Systems
Gabriele Kotsis · 1991
The major aims of this work is to give a comparative survey of static interconnection topologies, and to discuss their properties with respect to their use as interconnection topologies in message passing multi-computer systems, i. e. each processing element has its own local memory, there is no common memory, and the processing elements communicate via message-passing. To this end it was necessary to recall relevant measures on graphs from graph theory, like for example the average distance or the network diameter, and requirements from the parallel processing area, like the reliability or extensibility. Special emphasis has been given to present the construction rules for various graphs, because these seemed -- along with the network characteristics -- most relevant for interconnecting processing elements in reconfigurable multi-computer systems. Critical to applications in these kind of parallel systems is the possibility of exchanging local data among cooperating processing element...