International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 7, No. 3, 8 Feb. 2015
Cover page and Table of Contents: PDF (size: 351KB)
Linear Crossed Cube (LCQ): A New Interconnection Network Topology for Massively Parallel System
Full Text (PDF, 351KB), PP.18-25
Views: 0 Downloads: 0
Author(s)
Zaki A. Khan
1,*
Jamshed Siddiqui
1
Abdus Samad
2
Index Terms
Interconnection Network, Diameter, Parallel System, Scalability, Load Imbalance, Dynamic Scheduling
Abstract
Scalability and Complexity are crucial performance parameters in the design of Interconnection networks for multiprocessor system. This paper proposed and analyzed a new scalable interconnection network topology named as Linear Crossed Cube (LCQ). LCQ designed is based on the principle of hypercube architecture however, it improves some of the drawbacks of hypercube such as complex extensibility and its VLSI Layout. It inherits most of the desirable properties of hypercube type architectures; the most notably are small diameter and symmetry. LCQ has linear extension at each level of the extension while preserving all the desired topological properties. To evaluate the performance of proposed LCQ, standard scheduling algorithms are being implemented on it. The performance parameters such as Load Imbalance Factor (LIF) and balancing time are evaluated on the proposed LCQ as well as on other similar multiprocessor architectures. To compare the performance of proposed LCQ, standard scheduling scheme is also implemented on other similar multiprocessor architectures. The comparative simulation study shows that the proposed network can be considered as low-cost multiprocessor architecture for parallel system when appropriate scheduling algorithm is implemented onto it.
Cite This Paper
Zaki A. Khan, Jamshed Siddiqui, Abdus Samad, "Linear Crossed Cube (LCQ): A New Interconnection Network Topology for Massively Parallel System", International Journal of Computer Network and Information Security(IJCNIS), vol.7, no.3, pp.18-25, 2015. DOI:10.5815/ijcnis.2015.03.03
Reference
[1]S. Kim and V. A. Veidenbaum, “Interconnection network organization and its impact on performance and cost in shared memory multiprocessors”, Journals of parallel computing, Vol. 25, pp. 283-309, 1999.
[2]B. Parhami, “Challenges in Interconnection Network Design in the era of Multiprocessor and Massively Parallel Microchips”, In proceeding of international conference on communication in Computing, pp 241-246, 2000.
[3]Z. A. Khan, J. Siddiqui and A. Samad, “Performance Analysis of Massively Parallel Architectures”, BIJIT - BVICAM’s International Journal of Information Technology, Vol. 5 No.1, pp. 563-568, 2013.
[4]Z. A. Khan, J. Siddiqui and A. Samad, “Topological Evaluation Of Variants Hypercube Network”, Asian Journal of Computer Science and Information Technology, Vol. 3 No. 9, pp. 125-128, 2013.
[5]S. P. Mohanty, B. N. B. Ray, N. S. Patro and A. R. Tripathy, “Topological Properties Of a New Fault Tolerant Interconnection Network for Parallel Computer”, In proceeding of ICIT international conference on Information Technology, pp 36-40, 2008.
[6]A. Patelm, A. Kasalik and C. McCrosky, “Area Efficient VLSI Layout for binary Hypercube”, IEEE Transaction on Computers, Vol. 49 No. 2, pp. 160-169, 2006.
[7]M. Monemizadeh and H. S. Azad, “The Necklace-Hypercube: A Well Scalable Hypercube-Based Interconnection Network for Multiprocessors”, In ACM Symposium on Applied Computing, pp 729-733, 2005.
[8]K. Efe, “The crossed cube architecture for parallel computation”, IEEE Transactions on Parallel and Distributed Systems, Vol. 3 No. 5, pp. 513–524, 1992.
[9]K. K. Peter, W. J. Hsu and Y. Pan, “The Exchanged
Hypercube”, IEEE Transaction on Parallel and Distributed Systems, Vol. 16 No. 9, pp. 866-874, 2005.
[10]N. Adhikari and C. R. Tripathy, “Extended Crossed Cube: An Improved Fault Tolerant Interconnection Network”, In proceeding of 5th International joint conference on INC, IMS and IDC, 2009.
[11]S. B. Akers, D. Harel and B. Krishnamurthy, “The Star Graph: an Attractive Alternative to the n- Cube”, In proceeding of International Conference on Parallel Processing, pp. 393, 1987.
[12]C. R. Tripathy, “Star-cube: A New Fault Tolerant Interconnection Topology For Massively Parallel Systems”, IE(I) Journal, ETE Div, Vol. 84 No. 2, pp. 83- 92, 2004.
[13]N. Adhikari and C. R. Tripathy, “On a New Multicomputer Interconnection Topology for Massively Parallel Systems”, International Journal of Distributed and Parallel Systems (IJDPS), Vol. 2 No. 4, 2011.
[14]Y. Saad and M. H. Schultz, “Topological properties of hypercubes”, IEEE Trans. Computer, Vol. 37 No. 7, pp. 867–872, 1988.
[15]S. B. Akers and B. Krishnamurthy, “The Fault-tolerance of Star Graphs”, In proceeding of International Conference on Supercomputing, pp. 270, 1987.
[16]A. Samad, M. Q. Rafiq and O. Farooq, “LEC: An Efficient Scalable Parallel Interconnection Network”, In proceeding International Conference on Emerging Trends in Computer Science, Communication and Information Technology, pp 453-458, 2010.
[17]A. Samad, M. Q. Rafiq and O. Farooq, “Two Round Scheduling (TRS) Scheme for Linearly Extensible Multiprocessor Systems”, International Journal of Computer Applications, Vol. 38 No. 10, pp. 34-40, 2012.
[18]A. Ayyoub and K. Day, “The hyper star interconnection network”, Journal of Parallel & Distributed Processing, Vol. 48, pp. 175-199, 1998.
[19]E. Abuelrub, “A comparative study on topological properties of the hyper-mesh interconnection network”, In world congress on engg, pp 616-621, 2008.
[20]L. Youyao, H. Jungang and U. D. Huimin, “Ahypercube based scalable interconnection network for massively parallel system', Journal of Computing”, Vol. 3 No. 10, pp. 58-65, 2008.
[21]A. Awwad, A. A. Ayyoub and M. O. Khaoua, “On topological properties of arrangement star network”, Journal of System Architecture, Vol. 48, pp. 325-336, 2003.
[22]W. M. H. Lemair an A. P. Reeves, “Strategies for dynamic load balancing on highly parallel computers”, IEEE Transaction on Parallel and Distributed Systems, Vol. 4 No. 9, pp. 979-92, 1993.
[23]M. Bertogna, M. Cirinei and G. Lipari, “Scheduling analysis of global scheduling algorithm on multiprocessor platforms”, IEEE Transactions on Parallel and Distributed Systems, Vol. 20 No. 4, pp. 553-566, 2009.
[24]M. Dobber, R. V. D. Mei and G. Koole, “Dynamic Load Balancing and Job Replication in Global-Scale Grid Environment: A Comprasion”, IEEE Transaction on Parallel and Distributed Systems, Vol, 20 No. 2, pp. 207-218, 2009.
[25]Y. Fang, F. Wang and J. Ge, “A Task Scheduling Algorithm Based on Load Balancing in Cloud Computing”, Lecture Notes in Computer Science, Vol 6318, pp. 271-277, 2010.
[26]D. I. G. Amalarethinam and G. J. J. Mary, “A new DAG based dynamic task scheduling algorithm for multiprocessor systems”, International Journal of Computer Applications, Vol. 19 No. 8, pp. 24-28, 2011.
[27]SP. YU. Colajanni and D. M. Dias, “Analysis of Task Assignment policies in Scalable distributed web-server systems”, IEEE Transaction of parallel and distributed systems, Vol. 9 No. 6, pp. 585-600, 1998.
[28]M. H. Balter, M. Crovella. and C. Murta, “On Chossing a Task Assignment Policy for a Distributed Server System”, In proceeding of conference Tools'98, pp.231-242, 1998.
[29]V. Cardellini, E. Casalicchio, M. Colajanni and P. S. YU, “The State of the Arts in Locally Distributed Web Server Systems”, ACM Computing Surveys , Vol. 34 No. 2, pp. 1-49, 2002.
[30]A. N. Z. Rashed, “Very Large Scale Optical Interconnect Systems for Different Types of Optical Interconnection Networks”, International Journal Computer Network and Information Security, Vol. 3, pp. 62-76, 2012.
[31]S. F. El. Zoghdy, “A Hierarchical Load Balancing Policy for Grid Computing Environment”, International Journal Computer Network and Information Security, Vol. 5, pp. 1-12, 2012.
[32]P. Rajput and V. Kumari, “Modelling and Evaluation of Multiprocessor Architecture” International Journal of Computer Applications, vol. 51, no. 22, 2012.