Multistage interconnection networks (MIN's ) have been proposed as a means for hardware sorting [1], data alignment in array (SIMD) machines [2], and for use in shared memory multiprocessor (MIMD) systems [3]. Pro jects to build large-scale shared memory multiprocessors are under way in industry and academia, among them the RP3 by IBM [4], and Cedar by the University of Illinois [5] [6]. In these MIMD systems, multistage interconnection networks replace the conceptually desirable, yet infeasible, crossbar switch as a means to connect memory modules to processors.