On shortest path routing in single stage shuffle-exchange networks
Sun-il Kim, Alexander V. Veidenbaum · 1995
In this paper, we study routing in shuffle-exchange networks. Shuffle-exchange networks can have two different structures: multistage and single stage. Routing in multistage networks with K \\Theta K crossbar switches needs dlog K Ne stage traversals for the connectivity between N inputs and N outputs. In single stage networks, less than dlog K Ne traversals may be required depending on source and destination. We establish a theorem for routing from an input terminal to an output terminal at any stage in multistage networks. In the theorem, system size is limited only as a multiple of a crossbar switch size. This condition allows more flexible increments in system size. Based on the theorem, we derive an algorithm that generates routing tags for shortest path routing in single stage networks. We study the impact of shortest path routing on average internode distance, and by using trace-driven simulation, we evaluate its effect on shared memory systems. Our results show that the shortest...