×

Comparing four classes of torus-based parallel architectures: network parameters and communication performance. (English) Zbl 1074.94535

Summary: The relative communication performance of low- versus high-dimensional torus networks (\(k\)-ary \(n\)-cubes) has been extensively studied under various assumptions about communication patterns and technological constraints. In this paper, we extend the comparison to torus networks with incomplete, but regular, connectivities. Taking an \(n\)D torus as the basis, we show that a simple pruning scheme can be used to reduce the node degree from 2\(n\) to 4, while preserving many of the desirable properties of the intact network. Orienting the torus links (removing half of the channels) provides a second form of pruning that leads to (multidimensional) Manhattan street networks. Finally, combined pruning and orientation yields the fourth class of toroidal networks studied here. We compare the static performance parameters of these networks and evaluate their dynamic communication performance under the assumptions of virtual cut-through switching and constant pin count. The 3D case, leading to networks that are efficiently realizable with current technology, is used to demonstrate and quantify the performance benefits. Our results reinforce, extend, and complement previous studies that have demonstrated the performance advantages of low-dimensional \(k\)-ary \(n\)-cubes over higher-dimensional ones. For example pruned 3D tori provide additional design points that fall between 2D and 3D tori in terms of implementation complexity but can outperform both of these standard architectures. Thus, from a practical standpoint, pruning introduces additional flexibility in implementation options and trade-offs available to designers.

MSC:

94C99 Circuits, networks
94C15 Applications of graph theory to circuits and networks
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI

References:

[1] Semiconductor Industry Association, International Technology Roadmap for Semiconductors, San Jose, CA, USA (2000)
[2] Kuck, D. J., High-Performance Computing: Challenges for Future Systems (1996), Oxford University Press
[3] Mattson, T. G.; Scott, D.; Wheat, S., A TeraFLOP supercomputer in 1996: The ASCI TFLOP system, (Proc. Int’l Parallel Processing Symp. (April 1996)), 84-93
[4] Scot, S. L.; Thorson, G. M., The Cray T3E network: Adaptive routing in a high performance 3D torus, (Proc. Hot Interconnects IV. Proc. Hot Interconnects IV, Palo Alto, CA (August 1996))
[5] Parhami, B., Introduction to Parallel Processing: Algorithms and Architectures (1999), Plenum Press
[6] Parhami, B.; Kwai, D.-M., A unified formulation of honeycomb and diamond networks, IEEE Trans. Parallel and Distributed Systems, 12, 1, 74-80 (2001)
[7] Agrawal, A., Limits on interconnection network performance, IEEE Trans. Parallel and Distributed Systems, 2, 4, 398-412 (1991)
[8] Anderson, J. R.; Abraham, S., Multidimensional network performance with unidirectional links, (Proc. Int’l Conf. Parallel Processing (1997)), 26-33
[9] Dally, W. J., Performance analysis of \(k\)-ary \(n\)-cube interconnection networks, IEEE Trans. Computers, 39, 6, 775-785 (1990)
[10] Banerjee, D.; Mukherjee, B.; Ramamurthy, S., The multidimensional torus: Analysis of the average hop distance and application as a multihop lightwave network, (Proc. IEEE Int’l Conf. Communications. Proc. IEEE Int’l Conf. Communications, New Orleans (May 1994)), 1675-1680
[11] Maxemchuk, N. F., Routing in the Manhattan street network, IEEE Trans. Communications, 35, 503-512 (1987)
[12] Brassil, J.; Choudhury, A. K.; Maxemchuk, N. F., The Manhattan street network: A high performance, highly reliable metropolitan area network, Computer Networks and ISDN, 26, 841-858 (1994)
[13] Chung, T. Y.; Sharma, N.; Agrawal, D. P., Cost-performance trade-offs in Manhattan street networks versus 2-D torus, IEEE Trans. Computers, 43, 2, 240-243 (1994)
[14] Lee, W.-T.; Kung, L.-Y., Binary addressing and routing schemes in the Manhattan street network, IEEE/ACM Trans. Networking, 3, 26-30 (1995)
[15] Mirfakhraei, N., Simulation of a Manhattan street network for high-speed ATM applications, (Proc. IEEE Int’l Conf. Communications. Proc. IEEE Int’l Conf. Communications, Seattle, WA (June 1995)), 1937-1942
[16] Kwai, D.-M.; Parhami, B., A class of fixed-degree Cayley graph interconnection networks derived by pruning k-ary n-cubes, (Proc. Int’l Conf. Parallel Processing (August 1997)), 92-95
[17] Nguyen, J.; Pezaris, J.; Pratt, G.; Ward, S., Three-dimensional network topologies, (Proc. Int’l Workshop Parallel Computer Routing and Communication. Proc. Int’l Workshop Parallel Computer Routing and Communication, Seattle, WA (May 1994)), 101-115
[18] Parhami, B.; Kwai, D.-M., Incomplete \(k\)-ary \(n\)-cube and its derivatives, J. Parallel and Distributed Computing, 64, 2, 183-190 (2004) · Zbl 1069.68506
[19] Alverson, R.; Callahan, D.; Cummings, D.; Koblenz, B.; Porterfield, A.; Smith, B., The Tera computer system, (Proc. ACM Int’l Conf. Supercomputing. Proc. ACM Int’l Conf. Supercomputing, Amsterdam (June 1990)), 1-6
[20] Wittie, L., Communication structures for large networks of microcomputers, IEEE Trans. Computers, 30, 4, 264-273 (1981)
[21] Chung, T. Y.; Agrawal, D. P., Design and analysis of multidimensional Manhattan street networks, IEEE Trans. Communications, 41, 295-298 (1993) · Zbl 0775.94150
[22] Stojmenovic, I., Honeycomb networks: Topological properties and communication algorithms, IEEE Trans. Parallel and Distributed Systems, 8, 10, 1036-1042 (1997)
[23] Kwai, D.-M.; D.-M.; Parhami, B., Pruned three-dimensional toroidal networks, Information Processing Letters, 68, 179-183 (1998) · Zbl 1339.68207
[24] Krishnamoorthy, M. S.; Krishnamurthy, B., Fault diameter of interconnection networks, Computers Math. Applic., 13, 5/6, 577-582 (1987) · Zbl 0641.94048
[25] Day, K.; Al-Ayyoub, A. E., Fault diameter of \(k\)-ary \(n\)-cube networks, IEEE Trans. Parallel and Distributed Systems, 8, 9, 903-907 (1997)
[26] Lakshmivarahan, S.; Jwo, J.-S.; Dahl, S. K., Symmetry in interconnection networks based on Cayley graphs of permutation group: A survey, Parallel Computing, 19, 361-401 (1993) · Zbl 0777.05064
[27] Chung, T. C., Area array packaging technologies for high-performance workstations and multiprocessors, (Proc. IEEE Electronic Components and Technology Conf.. Proc. IEEE Electronic Components and Technology Conf., Orlando, FL (May 1996)), 902-910
[28] Kermani, P.; Kleinrock, L., Virtual cut-through: A new computer communication switching technique, Computer Networks, 3, 267-286 (1979) · Zbl 0408.68090
[29] Abraham, S.; Padmanabhan, K., Performance of the direct binary \(n\)-cube network for multiprocessors, IEEE Trans. Computers, 38, 7, 1000-1011 (1989)
[30] Abraham, S.; Padmanabhan, K., Performance of multicomputer networks under pin-out constraints, J. Parallel and Distributed Computing, 12, 237-248 (1991)
[31] Dolter, J. W.; Ramanathan, P.; Shin, K. G., Performance analysis of virtual cut-through switching in HARTS: A hexagonal mesh multicomputer, IEEE Trans. Computers, 40, 6, 669-680 (1991) · Zbl 1395.68068
[32] Grammatikakis, M. D.; Jwo, J.-S.; Kraetzl, M.; Wang, S.-H., Dynamic and static packet routing on symmetric communication networks, (Proc. IEEE GLOBECOM. Proc. IEEE GLOBECOM, San Francisco, CA (November 1994)), 1571-1575
[33] Hsu, W.; Yew, P.-C., The impact of wiring constraints on hierarchical network performance, (Proc. Int’t Parallel Processing Symp. (March 1992)), 580-588
[34] Sharma, V.; Varvarigos, E. A., Circuit switching with input queuing: An analysis for the \(d\)-dimensional wraparound mesh and hypercube, IEEE Trans. Parallel and Distributed Systems, 8, 4, 349-366 (1997)
[35] Bilardi, G.; Preparata, F. P., Horizons of parallel computation, J. Parallel and Distributed Computing, 27, 172-182 (1995) · Zbl 0939.68636
[36] Kessler, R. E.; Schwarzmeier, J. L., Cray T3D: A new dimension for Cray research, (Digest of Papers IEEE COMPCON. Digest of Papers IEEE COMPCON, San Francisco, CA (February 1993)), 176-182
[37] Parhami, B.; Kwai, D.-M., Periodically regular chordal rings, IEEE Trans. Parallel and Distributed Systems, 10, 6, 658-672 (1999)
[38] Xiao, W.; Parhami, B., Some conclusions on Cayley digraphs and their applications to interconnection networks, (Li, M.; etal., Proc. 2nd International Workshop on Grid and Cooperative Computing. Proc. 2nd International Workshop on Grid and Cooperative Computing, December 2003. Proc. 2nd International Workshop on Grid and Cooperative Computing. Proc. 2nd International Workshop on Grid and Cooperative Computing, December 2003, Lecture Notes in Computer Science, Vol. 3033 (2004), Springer-Verlag), 408-412
[39] Xiao, W.; Parhami, B., Hexagonal and pruned torus networks as Cayley graphs, (Proc. International Conf. Communications in Computing. Proc. International Conf. Communications in Computing, Las Vegas, NV (June 2004)), 107-112
[40] Yeh, C.-H.; Parhami, B., The index-permutation graph model for hierarchical interconnection networks, (Proc. of the International Conf. on Parallel Processing. Proc. of the International Conf. on Parallel Processing, Aizu, Japan (September 1999)), 48-55
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.