AIRCC PUBLISHING CORPORATION
EMBEDDING BUS AND RING INTO HEX-CELL INTERCONNECTION NETWORK
Qatawneh Mohammad1, Ahmad Alamoush1, Sawsan Basem1 , Maen M. Al Assaf1,
and Mohammad Sh. Daoud2
1Department of Computer Science, King Abdullah II School for Information Technology,
The University of Jordan.
2Al Ain University of Science and Technology, UAE.
Hex-Cell is an interconnection network that has attractive features like the embedding capability of topological structures; such as; bus, ring, tree and mesh topologies. In this paper, we present two algorithms for embedding bus and ring topologies onto Hex-Cell interconnection network. We use three metrics to evaluate our proposed algorithms: dilation, congestion, and expansion. Our evaluation results show that the congestion of our two proposed algorithms is equal to one; and the dilation is equal to 2d-1 for the first algorithm and 1 for the second
Embedding, Hex-Cell network, Dilation, Expansion
Network topology shows the way in which a set of nodes are connected to each other by edges. A variety of network topologies for parallel architecture have been proposed due to the importance of interconnection networks in parallel systems and their performance. Consequently, some features in parallel system network are highly desirable such as: communication cost, efficient routing, minimum diameter, partitioning, and the capability of embedding topological structures (e.g. ring, star, linear array, tree, mesh, and hypercube) [3, 4, 5]. Graph embedding (mapping) has many applications in parallel processing and is considered one of the most important issues in network selection and evaluation. Hex-Cell is one of the various proposed interconnection networks structures for a parallel system. It receives much attention due to its attractive property of embedding ability and other features [1, 2, 5, 11]. In this paper, we propose an algorithm for embedding bus and ring onto a Hex-Cell.
Let G be (guest graph) and H be (host graph). An embedding of a graph G= (VG, EG) into a graph H= (VH, EH) is represented by a mapping function ƒ: G H that consists of two mappings: ƒV: VG VH and ƒE: EG PH, where PH denotes the set of paths in the graph H. The mapping function ƒE maps edge (u,v) EG to a path p PG connecting ƒV (u) and ƒV(u) [9, 10]. Three criteria can be used to evaluate embedding results. The first criterion is dilation, which is the maximum distance in H between adjacent vertices in graph G. The second one is congestion
which is the maximum load on the edge of graph H. The third criterion is expansion, which is the efficiency of node utilization for an embedding scheme [6, 7, 8].
In this study, we propose two algorithms for embedding bus and ring onto Hex-Cell. The rest of this paper is organized as follows: Section 2 introduces Hex-Cell network. Section 3 illustrates the proposed embedding algorithms for bus and ring onto Hex-Cell Network. Section 4 presents an analytical model for the proposed embedding algorithm using several performance metrics like: dilation, congestion and expansion. Section 6 provides our research conclusions.
2. RELATED WORK
In this section, we illustrate the current research that is related to our research. In particular, we will discuss Hex-cell network, bus topology and ring topology.
2.1 Hex-Cell Network
Parallel processing is used for solving problems in major application areas such as image processing and scientific computing as it provides high processing power. Parallel machines performance is affected by the underlying communication network and use of suitable algorithm. Hence, there exist several desired features in parallel machine network such as minimal communication cost, efficient routing, and the capability of embedding topological structures such as tree, ring, linear array, and mesh. Hypercube is one of the most important interconnection networks structures proposed for parallel computing in which it has much attention due to the its important properties like: embeddability, symmetry, regularity, strong resilience, and simple But in hypercube structure, it was noticed that the number of communication ports and channels per processor increases as the network sizes increases. This forms a drawback for this approach. In our research, we aim to construct a new network that combines the following good features: less communication, efficient routing and capability of embedding other static topologies. This motivates us to “Hex-Cell” topology which forms a new interconnection network that meets the demands of highly parallel systems. Despite the facts that the hexagon topology was addressed as a 3D hexagonal network, the node degree and number of links are still considered high. Hence, our “Hex-Cell” approach has an enhanced use of node degree and links count when compared to the existing topologies.
In , we proposed a new class of interconnection networks topologies called “Hex-Cell”. The most important feature of our proposed topology is the embedding capability of topological structures such as linear array, ring, tree and mesh. Our approach uses an efficient routing algorithm that does not require that much knowledge of the network interconnections and is capable to do communication in a less cost. Those features of our proposed solution make it a good candidate for general purpose applications. Due to its recursive structure, Hex-Cell is expandable in an incremental manner with the minimal cost. The metrics in which Hex-Cell is compared with other related networks are: degree, diameter, and network-cost.
In , we presented a complete modeling, topological properties, and a routing algorithm for our “Hex-Cell” solution. At the performance evaluation, we considered a Hex-Cell network topology with four levels (see: figure 1), and we illustrated six cases of the “Hex-Cell” routing algorithms:
move up/ left to right, move up/ right to left, move down/ left to right, move down/ right to left, horizontal/ left to right, horizontal / right to left (see: figures 2,3,4,5,6, and 7 respectively).
Figure 1: (Quoted from ) HC(4) topology with labeled nodes and levels
Figure 2: (Quoted from ) MoveUp/ Left-to-right
Figure 3: (Quoted from ) MoveUp/ Right-to-left
Figure 4: (Quoted from ) moveDown / Left-to-right.
Figure 5: (Quoted from ) moveDown / Right-to-left
Figure 6: (Quoted from ) Horizontal / Left-to-right
Figure 7: (Quoted from ) Horizontal / Right-to-left
In this research, we compare the proposed structure with other know topologies such as 3D hexagonal network, linear array, ring, binary tree, and hypercube as shown in Table 1. A Hex-Cell network with depth d is denoted by HC (d). It can be constructed using units of hexagon cells, each of six nodes . A Hex-Cell network with depth d has d levels numbered from 1 to d, where level 1 represents the innermost one corresponding to one hexagon cell. Level 2 corresponds to the six hexagon cells that surround the hexagon at level 1. Level 3 corresponds to the 12 hexagon cells that surround the six hexagons at level 2 (see: Figure 8). The Hex-Cell network is divided into six sections labeled from left to right (clockwise) and numbered from 1 to 6. While each node is addressed by section number, both of; level number and the node number on that level are labeled from X1,……,Xn; where n = ((2×L) – 1) .
Figure 8: 3-dimensional Hex-Cell Network
2.2 Bus Topology
Is a network design that can transmit the data in one direction and can form a single network segment that can communicate with each other in the level of TCP/IP data link layer. Such network can host several workstations. The major concern of such network is the transmission coordination to avoid collision. Carrier sense multiple access (CSMA) technique is used for avoiding collisions. Bus topology is mainly used for small networks and requires less cable length. Figure 9 shows a typical buss topology network.
Figure 9: Typical Bus Topology
2.3 Ring Topology
Is a network design in which each node is connected with only two other nodes in a form of ring (see: figure 10). Data travels from the source to the destination through all the nodes located on the path. In order to avoid collision between the sending nodes, only the node who currently owns
the token can transmit over the network. When a node finishes transmission, it passes the token to the adjacent nodes, and so on. The problem with this approach is that the token is passed to the nodes that need it and to those that has nothing to transmit over the network.
Figure 10: Typical Ring Topology