Broadcasting and Embedding Algorithms for a Half Hypercube Interconnection Network

Abstract

The half hypercube interconnection network, has been proposed as a new variation of the hypercube, reducing its degree by approximately half with the same number of nodes as an n-dimensional hypercube, Q _n . This paper proposes an algorithm for one-to-many broadcasting in an n-dimensional half hypercube, HH _n , and examines the embedding between hypercube and half hypercube graphs. The results show that the one-to-many broadcasting time of the HH _n can be accomplished in n + 1 when n is an even number and in $2 \times \lceil n/ 2\rceil$ when n is an odd number. The embedding of HH _n into Q _n can be simulated in constant time O(n) and the embedding of Q _n into HH _n in constant time O(1).

Introduction

There is increasing interest in parallel processing as a technique for achieving high-performance owing to the need for many computations with real-time data processing in modern applications [1, 2]. A parallel processing system can connect hundreds of thousands of processors with their own memory via an interconnection network. The overall performance of the system is dependant on the performance of each processor and the architecture of the interconnection network used [1–3]. Many interconnection network topologies have been described in the literature, such as star, mesh, bubble-sort, and pancake graphs.

The hypercube, Q _n , is a typical topology and is an n-regular and node- and edge-symmetric graph with 2ⁿ nodes and diameter n (n ≥ 2). The hypercube Q _n has simple routing algorithms and recursive structures with maximum fault-tolerance. In addition, it has the advantage that its network structure can easily be embedded in various types of commonly used interconnection networks. With such advantages, it is widely used in various application areas [1, 4, 5]. However, its network cost is increased considerably in relation to the increased degree when the number of nodes increases. To resolve this drawback, several hypercube variations have been introduced. We have proposed the half-hypercube interconnection network, reducing its degree by approximately half, even though it has the same number of nodes as a hypercube Q _n . In this paper, we propose an algorithm for one-to-many broadcasting in an n-dimensional half hypercube, HH _n , and analyze the embedding method of a half hypercube graph into a hypercube graph and vice versa.

The most common properties for measuring the performance of interconnection networks include degree, diameter, connectivity, fault tolerance, broadcasting, and embedding [6, 7]. In [1], we analyzed the degree, diameter, connectivity, and fault-tolerance parameters of the half hypercube. Here, we examine the broadcasting and embedding properties of a HH _n to strengthen its effectiveness. Broadcasting is one of the major primitives for communication of parallel processing involving message disseminating from an origin node to all the other nodes (one-to-many broadcast) or among the nodes (many-to-many broadcast) in an interconnection network. Embedding is to evaluate the relative performance of two arbitrary interconnection networks. This is of interest, because the properties and algorithms developed in a certain topology can easily be adapted to anther network at less cost [8].

The organization of this paper is as follows. Section 2 presents the definition of the half hypercube HH _n . Section 3 proposes and analyzes a broadcasting algorithm for an n-dimensional half hypercube, HH _n . Section 4 examines the embedding algorithms between hypercube and half hypercube graphs. Section 5 concludes the paper.

Definition of the Half Hypercube

The half hypercube HH _n (n ≥ 3) is defined as an n-dimensional binary cube where the nodes of HH _n are all binary n-tuples in the same way as the hypercube Q _n (n ≥ 2). That is, an n-dimensional half hypercube is denoted as HH _n and each node is represented with n binary bits. The degree and node connectivity of HH _n are $\lceil n/ 2\rceil + {\text{ 1 and}}\; \lceil n/ 2\rceil + 1(n \ge 3)$, respectively. An HH _n graph is expanded with recursive structures and has $2^{ \lfloor n/ 2\rfloor } \lceil n/ 2\rceil$-dimensional hypercube structures with maximum fault-tolerance [1].

In Q _n , an edge exists between two arbitrary nodes S and S′ if and only if their corresponding n-tuples differ in exactly one k position of the bit strings of S and $S'( 1 { } \le k \le n)$ [9]. On the other hand, in HH _n , two types of edge exist: the h-edge, which connects node S to a node that has the complement in one bit at exactly one h position $( 1\le h \le \lceil n/ 2\rceil )$, and the swap-edge (shortly, sw-edge), which connects node S to a node where the $\lfloor n/ 2\rfloor$ leftmost bits of the bit string of S and the $\lfloor n/ 2\rfloor$ bits on the right-side of S starting from the $\lfloor n/ 2\rfloor$ position are exchanged $(h = \lfloor n/ 2\rfloor )$. However, if two parts of $\lfloor n/ 2\rfloor$ bits to swap in the bit string of node S are the same, the node S connects to node $\bar{S}$, which is the one’s complement of the binary number of node S [1]. Note that $\bar{S}$ indicates the one’s complement of the binary number of node S in this paper.

At node $S( =\!s_{n} s_{n - 1} \ldots s_{ \lfloor n/ 2\rfloor + 1} s_{ \lfloor n/ 2\rfloor } s_{ \lfloor n/ 2\rfloor - 1} \ldots s_{ 2} s_{ 1} )$ of HH _n , the address of node S′ adjacent to node S via an sw-edge is considered using two cases depending on whether n is even or odd. For instance, when n is even, node $S( =\!s_{n} s_{n - 1} \ldots s_{ \lfloor n/ 2\rfloor + 1} s_{ \lfloor n/ 2\rfloor } s_{ \lfloor n/ 2\rfloor - 1} \ldots s_{ 2} s_{ 1} )$ is adjacent to node $S'( =\!s_{ \lfloor n/ 2\rfloor } s_{ \lfloor n/ 2\rfloor - 1} \ldots s_{ 2} s_{ 1} s_{n} s_{n - 1} \ldots s_{ \lfloor n/ 2\rfloor + 1} )$where $(s_{n} s_{n - 1} \ldots s_{ \lfloor n/ 2\rfloor + 1} ){\text{ and}}\;(s_{ \lfloor n/ 2\rfloor } s_{ \lfloor n/ 2\rfloor - 1} \ldots s_{ 2} s_{ 1} )$ of S are swapped. When n is odd, node S is adjacent to node $S^{\prime } ({=}s_{ \lfloor n/ 2\rfloor } s_{ \lfloor n/ 2\rfloor - 1} \ldots s_{ 2} s_{n} s_{n - 1} \ldots s_{ \lfloor n/ 2\rfloor + 1} s_{ 1} )$ where $(s_{n} s_{n - 1} \ldots s_{ \lfloor n/ 2\rfloor + 1} ){\text{ and}}\;(s_{ \lfloor n/ 2\rfloor } s_{ \lfloor n/ 2\rfloor - 1} \ldots s_{ 2} )$ of S are swapped. Figure 1 presents a 5-dimensional half hypercube (HH ₅ ) [1].

Fig. 1

Example of a 5-dimensional half hypercube (HH ₅ ) [1]

Broadcasting Algorithm for HH _n

Broadcasting is a basic data communication technique for interconnection networks involving message transmission between nodes and is used by parallel algorithms [7, 10]. There are two types of broadcasting communication: one-to-many transmission, which transmits messages from a node to all the other nodes, and many-to-many transmission, which transmits messages among nodes. Here, we will demonstrate that the one-to-many broadcasting time of HH _n is n + 1 when n is even and the broadcasting time is $2\times \lceil n/ 2\rceil$ when n is odd.

Theorem 1

When n is even, the one-to-many broadcasting time of HH _n is n + 1 and when n is odd, the one-to-many broadcasting time of HH _n is $2\times \lceil n/ 2\rceil$.

Proof

Each cluster of HH_n represents a hypercube and the one-to-many broadcasting time of a hypercube Q_m is m. A cluster is connected to all the other clusters in HH_n by an external sw-edge. The broadcasting process is divided into three phases as follows:

• (1) Phase 1: Node S transmits messages to all the other nodes within its cluster

• (2) Phase 2: All nodes within the cluster to which node S belongs, including node S transmit messages to an arbitrary node in all the other clusters of HH _n using an external sw-edge.

• (3) Phase 3: Repeat the process of Phase 1 in each cluster of HH _n .

When n is even, the one-to-many broadcasting time is as follows. As the broadcasting time of an internal cluster of HH _n is the same as the one-to-many broadcasting time of a hypercube, the broadcasting time of Phase 1 is n/2. As broadcasting is performed only once in Phase 2, its broadcasting time is 1. As Phase 3 repeats the process of Phase 1, the broadcasting time is n/2. Therefore, the one-to-many broadcasting time of $HH_{n} \;{\text{is}}\;n/ 2+ 1+ n/ 2= n + 1$ when n is even.

When n is odd, the one-to-many broadcasting time is as follows. As the broadcasting time of an internal cluster of HH _n is the same as the one-to-many broadcasting time of a hypercube, the broadcasting time of Phase 1 is $n/ 2$. As broadcasting is performed only once in Phase 2, its broadcasting time is 1. If n is odd, the number of the sw-edges connecting clusters is 2 or 4. Thus, the number of nodes that initiate a message transmission is 2 or 4 in Phase 3. If the number of start nodes is 2, the one-to-many broadcasting time of a hypercube is reduced by 1. Therefore, the broadcasting time of Phase 3 is $\lceil {\text{n}}/ 2\rceil - 1$. Consequently, the one-to-many broadcasting time of HH _n is $\lceil n/ 2\rceil + 1+ \lceil n/ 2\rceil - 1 { } = { 2} \times \lceil n/ 2\rceil$ when n is odd.

Embedding Between Hypercube and Half Hypercube Graphs

Numerous parallel processing algorithms are being designed to solve many problems in a variety of interconnection network structures. Whether such algorithms designed for a specific interconnection network structure can be run on different interconnection network structures is an important issue in parallel processing. One of the most widely used measuring methods for this issue is embedding [10, 11], which involves mapping the processors and communication links of an interconnection network into those of another interconnection network.

We can represent an interconnection network as a graph G(V, E), where V(G) and E(G) are the set of nodes and edges of graph G, respectively, and the set of paths of graph G is P(G). The embedding of an interconnection network G(V, E) into another interconnection network G′(V′, E′) is defined as a function (Φ, ρ), where Φ maps the set of vertices V(G) one-to-one into the set of vertices V′(G′) and ρ maps the set of edges E(G) into the set of paths P′(G′); that is, Φ: V → V′ and ρ: E → P(G′). The representative measurement parameters for embedding costs are dilation and congestion. Dilation is the length of the shortest path from node S′ to node T′ in G′ when the nodes S and T of an edge (S, T) in G are mapped to nodes S′ and T′ of G′; i.e., the number of edges comprising the shortest path from node S′ to node T′ in G′. Congestion is the number of edges in G that pass an edge e in G′ when G is mapped to G′ [3, 4]. In this section, we analyze the embedding between a hypercube Q _n and a half hypercube HH _n using dilation.

Theorem 2

An n-dimensional hypercube Q _n can be embedded into an n-dimensional half hypercube HH _n with dilation 3.

Proof

We can analyze the dilation of this mapping through the number of edges of HH_n required to map the k-dimensional edge $\left( { 1 { } \le k \le n} \right)$, which represents the adjacent relationships of the nodes in Q _n , into edges in HH _n . Theorem 4 is proven by dividing the k-dimensional edge of Q _n into two cases depending on the dimension of k.

Case 1

k-dimensional edge, $1 { } \le k \le \lceil n/ 2\rceil$

It can be easily observed that the k-dimensional edge of hypercube $Q_{n} \;( 1\le k \le \lceil n/ 2\rceil )$ are the same as the h-dimensional edge of half hypercube HH _n $( 1\le h \le n/ 2\rceil )$. Therefore, it is clear that the embedding of an n-dimensional hypercube Q _n into an n-dimensional half hypercube HH _n is possible with dilation 1 when the two adjacent nodes via a k-dimensional edge in Q _n are mapped to two adjacent nodes through an h-dimensional edge in HH _n .

Case 2

k-dimensional edge, $\lceil n/ 2\rceil + 1\le k \le n$

The address of node S′ adjacent to an arbitrary node $S( =\!s_{n} s_{n - 1} s_{n - 2} \ldots s_{k} \ldots s_{n/2} \ldots s_{ 3} s_{ 2} s_{ 1} )$ of Q _n via a k-dimensional edge has the complement at exactly one k position of the bit string of node S (i.e., bit s _k ). An edge of HH _n that has the same role as the k-dimensional edge of hypercube Q _n can be presented by sequentially applying the following edge sequence: <sw-edge, $(k - \lceil n/ 2\rceil )$-edge, sw-edge> $( \lceil n/ 2\rceil + 1 { } \le k \le n)$. That is, it reaches a node with the address $s_{n} s_{n - 1} s_{n - 2} \ldots \bar{s}_{k} \ldots s_{n/2} \ldots s_{ 3} s_{ 2} s_{ 1}$ when the edge sequence <sw-edge, $(k - \lceil n/ 2\rceil )$-edge, sw-edge> is applied sequentially to node $S( =\!s_{n} s_{n - 1} s_{n - 2} \ldots s_{k} \ldots s_{n/2} \ldots s_{ 3} s_{ 2} s_{ 1} )$ of HH _n . Let a node S′ adjacent to node $S( =\!s_{n} s_{n - 1} s_{n - 2} \ldots s_{k} \ldots s_{n/2} \ldots s_{ 3} s_{ 2} s_{ 1} )$ of hypercube Q _n via a k-dimensional edge $( \lceil n/ 2\rceil + 1 { } \le k \le n)$ be $S'\left( { =\!s_{n} s_{n - 1} s_{n - 2} \ldots \bar{s}_{k} \ldots s_{n/2} \ldots s_{ 3} s_{ 2} s_{ 1} } \right)$.

The address of node sw(S) adjacent to node $S( =\!s_{n} s_{n - 1} s_{n - 2} \ldots s_{k} \ldots s_{ \lceil n/ 2\rceil + 1} s_{ \lceil n/ 2\rceil } \ldots s_{ 3} s_{ 2} s_{ 1} )$ of HH _n via an sw-edge is $s_{ \lceil n/ 2\rceil } \ldots s_{ 3} s_{ 2} s_{ 1} s_{n} s_{n - 1} s_{n - 2} \ldots s_{k} \ldots s_{ \lceil n/ 2\rceil + 1}$. To invert the bit s _k in the bit string of node sw(S) to the complement, we take a node $S^{\prime \prime } ( =\!s_{ \lceil n/ 2\rceil } \ldots s_{ 3} s_{ 2} s_{ 1} s_{n} s_{n - 1} s_{n - 2} \ldots \bar{s}_{k} \ldots s_{ \lceil n/ 2\rceil + 1} )$ adjacent to node sw(S) via a $(k - \lceil n/ 2\rceil )$-dimensional edge. The address adjacent to node S′′ through an sw-edge is $s_{n} s_{n - 1} s_{n - 2} \ldots \bar{s}_{k} \ldots s_{ \lceil n/ 2\rceil + 1} s_{ \lceil n/ 2\rceil } \ldots s_{ 3} s_{ 2} s_{ 1}$. Therefore, the embedding of a k-dimensional edge of Q _n into a half hypercube HH _n is possible with dilation 3. Figure 2 presents an example of embedding between Q ₈ and HH ₈ with dilation 3.

Fig. 2

Embedding example between Q ₈ and HH ₈ with dilation 3

Theorem 3

A half hypercube HH _n can be embedded into a hypercube Q _n with dilation n.

Proof

There exist two types of edges in half hypercube HH_n. Thus, we proved Theorem 5 by dividing it into two cases: h-edge and sw-edge.

Case 1

h-edge, $1 \le h \le \lceil n/ 2\rceil$

The address of node S′ adjacent to node $S( =\!s_{n} s_{n - 1} s_{n - 2} \ldots s_{n/ 2} \ldots s_{ 3} s_{ 2} s_{ 1} )$ of half hypercube HH_n via an h-edge is $s_{n} s_{n - 1} s_{n - 2} \ldots s_{n/2} \ldots \bar{s}_{h} \ldots s_{ 3} s_{ 2} s_{ 1} \;( 1 { } \le h \le \lceil n/ 2\rceil )$. The address of node S′ adjacent to node $S( =\!s_{n} s_{n - 1} s_{n - 2} \ldots s_{k} \ldots s_{n/ 2} \ldots s_{ 3} s_{ 2} s_{ 1} )$ of hypercube Q_n through a k-dimensional edge $( 1 { } \le k \le n)$ is $s_{n} s_{n - 1} s_{n - 2} \ldots \bar{s}_{k} \ldots s_{n/ 2} \ldots s_{ 3} s_{ 2} s_{ 1}$. Accordingly, the dilation of this embedding is 1 because the h-edge in half hypercube HH_n and the k-dimensional edge in Q_n are equivalent $( 1 { } \le h,k \le \lceil n/ 2\rceil )$.

Case 2

sw-edge

The sw-edge of half hypercube HH_n can be divided into two cases depending on the address of node $S( =\!s_{n} s_{n - 1} s_{n - 2} \ldots s_{n/ 2} \ldots s_{ 3} s_{ 2} s_{ 1} )$. Here, we prove the case with dilation n. If the n-address bits of node S are all binary 0, the n-address bits of node S′ adjacent to node S through an sw-edge are all binary 1. The shortest path from node $S( =\!s_{n} s_{n - 1} s_{n - 2} \ldots s_{n/2} \ldots s_{ 3} s_{ 2} s_{ 1} )$ to node $S'(=\!\overline{{s_{n} s_{n - 1} s_{n - 2} \ldots s_{n/2} \ldots s_{3} s_{2} s_{1} }} )$ in hypercube Q_n is the same as the path to which the k-dimensional edges are all applied. Therefore, a half hypercube HH_n can be embedded into a hypercube Q_n with dilation n $\left( { 1 { } \le k \le n} \right)$.

Conclusion

This paper proposes a one-to-many broadcasting algorithm for the half hypercube interconnection network, HH _n that we proposed in [1], and proved that the one-to-many broadcasting time is n + 1 when n is even and $2 \times \lceil n/ 2\rceil$ when n is odd in HH _n . We also showed that it is possible to embed an n-dimensional hypercube Q _n into an n-dimensional half hypercube HH _n with dilation 3, and that it is possible to embed HH _n into Q _n with dilation n. These results suggest that our half hypercube interconnection network HH _n has potential for implementation in large-scale systems for parallel processing.