Minimum Switching Networks

• Ricardo Ferreira UFV
• Michael Canesche UFV
• Kristtopher Coelho UFV
• José Augusto Nacif UFV

Abstract

Interconnection is a major challenge in parallel computer systems. In this paper, we introduce a novel scheme for designing interconnection multistage networks (MINs) with a reduced number of switches while retaining the networks' routability. We formalize the problem of multistage network design as a combinatorial search problem and we use Permutation Decision Diagrams (PiDD) to effectively explore the search space. Our method starts with a classical blocking multistage network (e.g., Shuffle-Exchange, Butterfly) and it explores all inter-stage permutation patterns and the minimum number of extra stages. We call the MINs produced by our scheme Minimum Switching Networks (MSNs), which are optimal with respect to the number of switches to build quasi and rearrangeable multistage networks. Empirical results on 8×8 permutation networks show the potential of our method.

Keywords: Interconnections, Multistage Switching Networks, Set of Permutations

References

A. Balkan, G. Qu, and U. Vishkin, “A mesh-of-trees interconnection network for single-chip parallel processing,” in ASAP. International Conference on, Sept 2006, pp. 73–80.

S.-i. Minato, “Pidd: A new decision diagram for manipulating sets of permutations,” Hokkaido University, Division of Comp. Science, TCS Tech. Reports, TCS-TR-A-11-50, 2011.

——,“Zero-suppressed bdds and their applications, ”International Journal on Software Tools for Technology Transfer, vol. 3, 2001.

K. S. Brace and et.al, “Efficient implementation of a bdd package,” in Proceedings of the Design Automation Conference. ACM, 1991.

V. Benesˇ, “On rearrangeable three-stage connecting networks,” Bell System Tech. Journal, vol. 41, no. 5, 1962.

A. Waksman, “A permutation network,” Journal of the ACM (JACM), vol. 15, no. 1, pp. 159–163, 1968.

C.-L. Wu and F. T.-Y. Feng, “On a class of multistage interconnection networks,” Computers, IEEE Transactions on, vol. 100, 1980.

I. Gazit, “On the number of permutations performable by extra-stage multistage interconnection networks,” IEEE Trans. Comput., vol. 38, no. 2, pp. 297–302, 1989.

H. Dai and X. Shen, “Rearrangeability of 7-stage 16× 16 shuffle exchange networks,” Frontiers of Electrical and Electronic Engineering in China, vol. 3, no. 4, pp. 440–458, 2008.

S.-Y. Li and X. Tan, “On rearrangeability of tandem connection of banyan-type networks,” Communications, IEEE Transactions on, vol. 57, no. 1, pp. 164–170, 2009.

C. Clos, “A study of non-blocking switching networks,” Bell System Technical Journal, vol. 32, no. 2, pp. 406–424, 1953.

D. H. Lawrie, “Access and alignment of data in an array processor,” IEEE Trans. on Computer, vol. 24, no. 12, 1975.

A. Chakrabarty and M. Collier, “routing algorithm for (2logn- 1)-stage switching networks and beyond,” Journal of Parallel and Distributed Computing, vol. 74, no. 10, pp. 3045–3055, 2014.

R. S. Ferreira, J. M. Cardoso, A. Damiany, J. Vendramini, and T. Teixeira, “Fast placement and routing by extending coarse-grained reconfigurable arrays with omega networks,” Journal of Systems Architecture, vol. 57, no. 8, pp. 761–777, 2011.

T. H. Szymanski and V. C. Hamacher, “On the universality of multipath multistage interconnection networks,” Journal of Parallel and Distrib. Comp., vol. 7, no. 3, 1989.

T.H. Szymanski, “Design principles for practical self-routing nonblocking switching networks with o (n·log n) bit-complexity,” IEEE T. on Computers, vol. 46, no. 10, 1997.

e. Aljundi, Ahmad Chadi, “A study of an evaluation methodology for unbuffered multistage interconnection networks,” in Parallel and Distributed Processing Symposium, 2003. Proceedings. International. IEEE, 2003, pp. 8–pp.

R. Ferreira, J. Vendramini, and M. Nacif, “Dynamic reconfigurable multicast interconnections by using radix-4 multistage networks in fpga,” in Industrial Informatics (INDIN), IEEE Int. Conference on, July 2011.

C.-h. Choi and S.-c. Kim, “Hierarchical multistage interconnection network for shared-memory multiprocessor system,” in Proceedings of the 1997 ACM symposium on Applied computing. ACM, 1997.