Analysis and Design of a Half Hypercube Interconnection Network
This paper proposes a new half hypercube interconnection network that has the same number of nodes as a hypercube but reduces the degree by approximately half. To evaluate the effectiveness of the proposed half hypercube, its connectivity, routing, and di
- PDF / 1,753,046 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 91 Downloads / 231 Views
Abstract This paper proposes a new half hypercube interconnection network that has the same number of nodes as a hypercube but reduces the degree by approximately half. To evaluate the effectiveness of the proposed half hypercube, its connectivity, routing, and diameter properties were analyzed. The analysis results demonstrate that the proposed half hypercube is an appropriate interconnection network for implementation in large-scale systems. Keywords Half hypercube
Hypercube variation Interconnection network
1 Introduction The need for high-performance parallel processing is increasing because modern engineering and science application problems require many computations with real-time processing. A parallel processing system can connect thousands of processors with their own memory, or even more via an interconnection network enabling inter-processor communication by passing messages among processors through the network. An interconnection network can be depicted with an J.-S. Kim Department of Computer Science, University of Rochester, Rochester 14627, USA e-mail: [email protected] M.-H. Kim Department of Computer Science Education, Catholic University of Daegu, Daegu, South Korea e-mail: [email protected] H.-O. Lee (&) Department of Computer Education, Suncheon National University, Suncheon, South Korea e-mail: [email protected]
J. J. (Jong Hyuk) Park et al. (eds.), Multimedia and Ubiquitous Engineering, Lecture Notes in Electrical Engineering 240, DOI: 10.1007/978-94-007-6738-6_65, Springer Science+Business Media Dordrecht(Outside the USA) 2013
537
538
J.-S. Kim et al.
undirected graph. The most common parameters for evaluating the performance of interconnection networks are degree, connectivity, diameter, network cost, and broadcasting [1, 2]. In an interconnection network, degree (relevant to hardware cost) and diameter (relevant to message transmission time) are correlated. In general, the throughput of an interconnection network is improved with a higher degree because the diameter of the network is increased when its degree is increased. However, a parallel computer design increased the hardware costs of an interconnection network, because of the increased number of processor pins. An interconnection network with a lower degree can reduce hardware costs, but its latency and throughput are degraded because the message transmission time is increased. Due to such characteristics of interconnection networks, the network cost (= degree 9 diameter) is a typical parameter used to evaluate interconnection network performance [3]. The hypercube is a typical interconnection network topology and is widely used in both research and commercial fields due to its advantages that can easily provide a communication network structure as required in various application areas. The hypercube is node- and edge-symmetric with a simple routing algorithm, maximum fault tolerance, and simple recursive structure. Additionally, it can be easily embedded in various types of existing interconnection networks [4, 5]. H
Data Loading...
