Indian Journal of Science and Technology

Open Access Open Access  Restricted Access Subscription Access

STH: a Highly Scalable and Economical Topology for Massively Parallel Systems


Affiliations
1 Faculty of Engineering and Technology, Aligarh Muslim University, Aligarh, U.P. – 202002, India
2 School of Mathematics and Computer Applications, Thapar University Patiala, P.B. – 147004, India
 

Highly parallel systems are receiving significant attention to solve the large and complex problems. This has resulted in the emergence of many attractive interconnection network topologies. This paper introduces a new processor interconnection topology called STH (Scalable Twisted Hypercube) to counter the poor scalability of twisted hypercube. Its suitability for use as multiprocessor interconnection networks has also been explored. The various properties of the proposed topology have been analyzed and it has been compared with some other highly scalable topologies of interest on a number of interconnection networks evaluation parameters. With reduced diameter, better average distance, low traffic density, low cost, maximum number of links, high bisection width and tremendous scalability, STH is more suitable for Massively Parallel Systems. Procedures for routing and broadcasting on the proposed topology have also been discussed and a simple routing algorithm has been presented. The proposed interconnection network provides a great architectural support for parallel computing due to the concurrent existence of multiple LST(m) and TQn.

Keywords

Parallel Systems, Processor Topology, Scalability, LST, Routing
User

  • Dongarra JJ, Meuer H and Strohmaier E (1997) TOP500 Supercomputer sites. Supercomput. 13, 89- 120.

  • Ayyoub A and Day K (1998) The hyperstar interconnection network. J. Parallel & Distributed Processing. 48, 175-199.

  • Abuelrub E (2008) A comparative study on topological properties of the hyper-mesh interconnection network. Proce. World Congress on Engg. UK, pp: 616-621.

  • Sharieh A, Qatawneh M, Almobaideen W and Sleit A (2008) Hex-cell – modeling, topological properties and routing algorithm. Eur.J. Sci. Res. 22(2), 457-468.

  • Saad Y and Schultz M (1988) Topological properties of the hypercube. IEEE Trans. Comput. C-37(7), 867-872.

  • Hwang K (2004) Advanced computer architecture:parallelism, scalability, programmability, 6th Reprint, TMH.

  • Al-Sadi J, Day K and Ould-Khaoua M (2002) Unsafety vectors: A new fault-tolerant routing for binary n-cubes. J. Sys. Architec. 47(9), 783-793.

  • Chiu G and Chon K (1998) Efficient fault-tolerant multicast scheme for hypercube multicomputers. IEEE Trans. Parallel & Distributed Sys. 9(10), 952- 962.

  • Klasing R (1998) Improved compressions of cubeconnected cycles networks. IEEE Trans. Parallel & Distributed Sys. 19(8), 803-812.

  • Louri A and Sung H (1994) Scalable optical hypercube-based interconnection network for massively parallel computing. Appl. Optics. 33, 7588- 7598.

  • Louri A, Weech B and Neocleous C (1998) A Spanning multichannel linked hypercube: A gradually scalable optical interconnection network for massively parallel computing. IEEE Trans. Parallel & Distributed Sys. 9(5), 497-512.

  • Efe K (1992) The crossed cube architecture for parallel computation. IEEE Trans. Parallel & Distributed Sys. 3, 513.

  • Chen C, Agrawal DP and Burke JR (1993) dB-cube: a new class of hierarchical multiprocessor interconnection network with area-efficient layout. IEEE Trans. Parallel & Distributed Sys. 4, 1332.

  • Malluhi QM and Bayoumi MA (1994) The hierarchical hypercube: A new interconnection topology for massively parallel systems. IEEE Trans. Parallel & Distributed Sys. 5, 17.

  • Preparata FP and Vuillemin J (1981) The cubeconnected cycles: A versatile network for parallel computation. Commun. ACM. 24(5), 300-309.

  • Youyao L, Jungang H and Huimin DU (2008) A hypercube based scalable interconnection network for massively parallel system. J. Comput. 3(10), 58- 65.

  • Awwad A, Ayyoub AA and Ould-Khaoua M (2003) On topological properties of arrangement star network. J. Sys. Architec. 48, 325-336.

  • Day K and Tripathi A (1994) A comparative study of topological properties of hypercubes and star graphs. IEEE Trans. Parallel & Distributed Sys. 5(1), 31-38.

  • Zheng S, Cong B and Bttayeb S (1993) The starhypercube hybrid interconnection networks. Proc. ISCA Intl. Conf. Comput. Appl. Design, Simulation & Analysis. USA. pp: 98-101.

  • Abuelrub E (2002) On hyper-mesh multicomputers. J. Institute of Maths & Comput. Sci. 12(2), 81-83.

  • Youssef A and Narahari B (1990) The banyanhypercube networks. IEEE Trans. Parallel & Distributed Sys. 1 (2), 160-169.

  • Das SK and Banerjee AK (1992) Hyper petersen network: Yet another hypercube-like topology. Proc. Frontiers. USA. 92, 270-277.

  • Chartrand G and Lesniak L (1986) Graph and diagraph. 2nd Ed., Wadsworth & Books, California.

  • Youssef A (1995) Design and analysis of product networks. Proc. Fifth Sym. Frontiers of Massively Parallel Sys. USA. pp: 521-528.

  • Day K and Ayyoub AA (1997) The cross product of interconnection networks. IEEE Trans. Parallel & Distributed Sys. 8(2), 109-118.

  • Rewini HE and Barr MA (2005) Advanced computer architecture and parallel processing. 1st Edition, Wiley-Intersci., Canada. pp: 105-106.

  • Abuelrub E (2007) Data communication and parallel computing on twisted hypercubes. Proc. World Congress on Engg., London, UK.

  • Alam J and Kumar R (2010) Linearly extendible arm (LEA) – A constant degree topology for designing scalable and cost effective interconnection networks. Ubiquitous Computing & Commun. J. 5(2) .

  • Xu M, Xu JM and Hou X M (2005) Fault diameter of cartesian product graphs. Info. Processing Letters. 93, 245-248.

  • Balakrishnan V K (2007) Schaums Outlines Graph Theory, Fifth Reprint, TMH, 135-137.

  • Amawy AE and Latifi S (1991) Properties and performance of folded hypercubes. IEEE Trans. Parallel & Distrib. Sys. 2, 31-42.

  • Louri A and Neocleous C (1997) A spanning bus connected hypercube: A new scalable optical interconnection network for multiprocessors and massively parallel systems. J. Lightwave Technol. 15, 1241-1252.

  • Graham SW and Seidel SR (1993) The cost of broadcasting on star graphs and k-ary hypercubes. IEEE Trans. Comput. 42(6), 756-759.

  • Agrawal N and Ravikumar CP (1996) Fault-tolerant routing in nultiply twisted cube topology. J. Sys. Architecture. 42(4), 279-288.


Abstract Views: 300

PDF Views: 100




  • STH: a Highly Scalable and Economical Topology for Massively Parallel Systems

Abstract Views: 300  |  PDF Views: 100

Authors

Jahangir Alam
Faculty of Engineering and Technology, Aligarh Muslim University, Aligarh, U.P. – 202002, India
Rajesh Kumar
School of Mathematics and Computer Applications, Thapar University Patiala, P.B. – 147004, India

Abstract


Highly parallel systems are receiving significant attention to solve the large and complex problems. This has resulted in the emergence of many attractive interconnection network topologies. This paper introduces a new processor interconnection topology called STH (Scalable Twisted Hypercube) to counter the poor scalability of twisted hypercube. Its suitability for use as multiprocessor interconnection networks has also been explored. The various properties of the proposed topology have been analyzed and it has been compared with some other highly scalable topologies of interest on a number of interconnection networks evaluation parameters. With reduced diameter, better average distance, low traffic density, low cost, maximum number of links, high bisection width and tremendous scalability, STH is more suitable for Massively Parallel Systems. Procedures for routing and broadcasting on the proposed topology have also been discussed and a simple routing algorithm has been presented. The proposed interconnection network provides a great architectural support for parallel computing due to the concurrent existence of multiple LST(m) and TQn.

Keywords


Parallel Systems, Processor Topology, Scalability, LST, Routing

References





DOI: https://doi.org/10.17485/ijst%2F2011%2Fv4i12%2F30321