A Fast Parallel Routing Algorithm for Benes Group Switches

E. Lu and S.Q. Zheng (USA)

Keywords

Group Connector, Rearrangeable Nonblocking Interconnection Network, Parallel Algorithm, Dense Wavelength-Division Multiplexing (DWDM), Network Switch, Network Router.

Abstract

A parallel routing algorithm for controlling the class of interconnection networks called group connectors is presented. Given any legal mapping from input to output groups with O(K) busy inputs, this algorithm can determine the switch setting of a Benes group connector with N inputs and n output groups in 0(log² K + log N) time on a completely connected computer or the EREW PRAM model with N processing elements. The implementations of this algorithm on various realistic parallel machine models are also discussed.

Important Links:

• DOI:
• From Proceeding (373) Parallel and Distributed Computing and Systems - 2002

Go Back