An efficient algorithm for embedding exchanged hypercubes into grids

Abstract

Graph embedding is an important technology in simulating parallel structures and designing VLSI layout. Hypercube is one of the most significant interconnection networks in parallel computing systems. The exchanged hypercube is an important variant of the hypercube, which is obtained by systematically deleting edges from a hypercube. It not only retains several valuable and desirable properties of the hypercube, but also has lower hardware cost. In this paper, we first give an exact formula of minimum wirelength of exchanged hypercube layout into a grid. Furthermore, we propose an O(N) algorithm for embedding exchanged hypercube into a gird with load 1, expansion 1 and minimum wirelength and derive a linear layout of exchanged hypercube with minimum number of tracks and efficient layout areas. Finally, we present simulation experiments of our embedding algorithm on network overhead and total wirelength, which conduce to estimate the total wirelength and chip area.

1 Introduction

With the rapid development in deep submicron technology, layout problems become more crucial in physical design of VLSI chips. Effective VLSI layout of interconnected networks can increase the cost-effectiveness of parallel architectures. By reducing its cost (fewer chips, wirelength and components) and reducing various performance barriers such as signal propagation delay, drive power and fraction of data transmission to off-chip destinations [1, 2].

It becomes possible to realize high-complexity and large-scale interconnection networks due to the rapid development of VLSI technology [3,4,5]. Interconnection network is an important component in parallel computing systems [6, 7]. One of the constraints in VLSI routing problems is minimizing wirelength, and efficient layouts for several interconnection networks can be found in [8, 9]. Researchers focus on layout interconnection networks into linear arrays and grids, which are called linear layout problem. A linear layout f of a graph $G = (V, E)$ with n vertices is a bijective mapping $f:V\rightarrow \{1, 2,\ldots , n\}$. The set of all linear layouts of the graph G can be denoted by f(G). A linear layout is also called a labeling, arrangement, layout or numbering of the vertices of a graph. A lot of relevant issues in different domains molded by graph layout problems include very large-scale integration (VLSI) circuit design, optimization of networks for parallel computer architecture, graph theory, information retrieval, etc. [10].

The minimum linear layout problem is first stated by Harper in 1964 and is proved to be NP-complete [11]. Nakano [12] proposed a linear layout of generalized hypercube network. Recently, Arockiaraj et al. [13] proved that the minimum linear layout of locally twisted cubes is equal to the minimum linear layout of hypercubes. Interconnection networks can also lay out into optical linear arrays. Liu [14] studied the embedding of exchanged hypercube network into optical linear array with optimal congestion. An embedding of 3-ary n-cube into an optical linear array with minimum congestion is given in [15].

Grid embeddings are used not only to study the simulation capabilities of a parallel architecture but also to design its VLSI layout. In [16], Bezrukov et al. obtained the approximate results and the estimation of lower bounds of wirelength on embedding hypercube network into a grid, and Bezrukov et al. also studied the exact congestion of embedding hypercube network into a rectangular grid in [17]. Manuel et al. [8] proposed an embedding of hypercube network into a grid with minimum wirelength. Recently, Abraham et al. [18] investigated the optimal embedding of locally twisted cubes into grids.

The problem of efficiently laying out VLSI can be formulated as the graph embedding problem. Embeddability is a critical metric to evaluate the performance of an interconnection network. Many applications, such as architecture simulation and processor allocation, can be modeled as a graph embedding problem [19, 20]. Graph embedding is an important issue that maps a guest graph into a host graph. Given a guest graph G and a host graph H, an embedding f from G to H can be defined as an injective mapping from V(G) to V(H).

Most researches on graph embedding consider paths, cycles and meshes as guest graphs because they are the architectures widely used in parallel computing systems [21,22,23,24,25,26]. In [27], Fan et al. proved that the cycles of all possible lengths can be embedded into twisted cube, and Fan et al. [28] also studied the embedding of paths with all possible lengths between any two vertices into crossed cube. Wang et al. [22] studied the embedding of three different types of special meshes into twisted cubes.

The hypercube network is one of the most popular interconnection network structures in parallel computing and communication systems. This is partly because of many attractive properties of the hypercube network such as regularity, recursive structure, vertex and edge symmetry, and maximum connectivity, as well as the effective routing and broadcasting.

As a variant of the n-dimensional hypercube network, the exchanged hypercube network $EH_{s,t}$ was proposed by Loh et al. [29]. An exchanged hypercube network is formed by removing edges from an n-dimensional hypercube network $Q_{n}$ where $n=s+t+1$. This is evident in the fact that even though the number of edges of an exchanged hypercube network is nearly half of that of a hypercube network, their diameters are similar. Therefore, $EH_{s,t}$ retains several desirable properties of the hypercube network such as a small diameter [29], bipancyclicity [30] and super connectivity [31] and has lower link costs than hypercubes. Zhang et al. [32] proposed a new type of data center network ExCCC-DCN, which combines exchanged hypercube and cube-connected cycles, and proved that it is a highly scalable, cost-effective and energy-efficient data center network structure. Furthermore, the lower link complexity of $EH_{s,t}$ can also directly reduce the costs of hardware and the implementation of VLSI.

The VLSI layout model assumed in this paper is the Thompson’s model [33]. In this model, a network is viewed as a graph whose nodes correspond to processing elements and edges correspond to wires. In this study, the following rules for a graph layout on the grid are used:

• It is a one-to-one mapping for assigning the vertices of the graph to the grid;

• The wires are routed by two layers of interconnect. Horizontal wires are routed in one layer, while vertical wires are routed in the other;

• The wires could run either vertically or horizontally along grid lines, but could not cross or overlap with one another.

In this paper, we study the embedding of $EH_{s,t}$ into a grid and obtain the exact wirelength of $EH_{s,t}$ into a grid. Next, we derive a result from which the minimum area for a common VLSI layout of $EH_{s,t}$ in two-dimensional technologies can be determined. The major contributions of the paper are as follows:

• 1. We proved the minimum wirelength of $EH_{s,t}$ into a linear array with minimum wirelength;

• 2. We proposed a decomposition embedding of $EH_{s,t}$ into grid and proved that $EH_{s,t}$ can be embedded into the grid $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$ with minimum wirelength.

• 3. It is proved that $EH_{s,t}$ can be implemented in a linear layout with minimum tracks, and it also showed that $EH_{s,t}$ can be laid out into an efficient grid.

The rest of this paper is organized as follows: Sect. 2 gives some definitions and notations. Section 3 derives a maximum induced subgraph of $EH_{s,t}$. Section 4 gives an embedding of $EH_{s,t}$ into a linear array and a grid with minimum wirelength. A collinear layout area of $EH_{s,t}$ into a linear array and a grid is proposed in Sect. 5. Section 6 reports simulation and experimental results. The final section concludes this paper.

2 Preliminaries

2.1 Definitions and notations

In this section, we will give some definitions and notations used in this paper. All graphs in this paper are simple undirected graphs, which can be generally denoted by $G=(V(G),E(G))$, where V(G) is the vertex set and E(G) is the edge set. For two simple graphs $G_{1} = (V_{1}, E_{1})$ and $G_{2} = (V_{2}, E_{2})$, $G_{2}$ is said to be a subgraph of $G_{1}$ if $V_{2}\subseteq V_{1}$ and $E_{2}\subseteq E_{1}$. If $V'\subseteq V(G)$, the subgraph of G induced by the vertex subset $V'$ is denoted by $G[V']$. The subgraph induced by the vertex subset $V(G_{1})\cup V(G_{2})$ is denoted by $G_{1}\cup G_{2}$. Let $\tau (V')$ denote the number of edges of $G[V']$. If $G_{1}$ is a subgraph of $G_{2}$ and $G_{1}\ne G_{2}$, $G_{1}$ is said to be the proper graph of $G_{2}$ and denoted by $G_{1}\subset G_{2}$. For a pair of disjoint vertex subset $S_{1}$ and $S_{2}$ of graph G, let $\tau (S_{1}, S_{2})$ denote the number of edges with one vertex in $S_{1}$ and the other vertex in $S_{2}$. For any integer $n\ge 1$, a binary string x of length n will be written as $x_{n-1}x_{n-2}\cdots x_{1}x_{0}$, where $x_{i}\in \{0,1\}$ for any integer $i\in \{0, 1,\ldots ,n-1\}$. Given any $x=x_{n-1}x_{n-2}\cdots x_{1}x_{0}$, $x_{i}$ is said to be the ith bit of x and $x_{n-1}x_{n-2}\cdots x_{k}$$(0\le k \le n-1)$ is called a prefix of x. Besides, $x_{0}$ is called the first bit of x and $x_{n-1}$ is called the last bit of x. For a graph $G = (V, E)$, an (u, v)-path of length l from vertex u to vertex v is denoted by $P = (u_{0}, u_{1},\ldots ,u_{l})$, where $u_{0} = u$ and $u_{l} = v$ are called the two end vertices of path P, and all the vertices $u_{0}, u_{1},\ldots ,u_{l}$ are distinct.

If u and v are two adjacent nodes in graph G when $(u,v)\in E(G)$. The neighborhoods of a vertex v are denoted by $N_{G}(v)$ in graph G such that $\{x|(v,x)\in E(G)\}$. The degree $\delta _{G}(v)$ of a node v is the number of edges incident with v. Let u and v be the source node and the destination node, respectively. The length of a shortest (u, v)-path is denoted by d(u, v), which is called the distance between u and v in G. A Hamiltonian path is defined as a path which traverses each vertex of graph G exactly once. If there exists a Hamiltonian path between any two distinct vertices of graph G, we say that graph G is a Hamiltonian-connected graph.

A graph $G_{1}$ is isomorphic to another graph $G_{2}$ (represented by $G_{1}\cong G_{2}$) if and only if there exists a bijection $f : V(G_{1})\rightarrow V(G_{2})$, such that if $(u,v)\in E(G_{1})$ then $(f(u), f(v))\in E(G_{2})$. For two graphs $G_{1}=(V_{1}, E_{1})$ and $G_{2}=(V_{2}, E_{2})$, and a subset $S\subseteq V_{1}$, let f be a mapping from $V_{1}$ to $V_{2}$. Let $T=\{x\in V(G_{2})| \mathrm {there}\ \mathrm {is}\ y\in S,\ \mathrm { such}\ \mathrm {that}\ y=f(x)\}$. Then, we write $T=f(S)$ and $S=f^{-1}(T)$.

Graph embedding can be formally defined as: Given two graphs $G_{1}=(V_{1}, E_{1})$ and $G_{2}=(V_{2}, E_{2})$, an embedding from $G_{1}$ to $G_{2}$ is an injective mapping $\psi : V_{1}\rightarrow V_{2}$. We call $G_{1}$ the guest graph and $G_{2}$ the host graph. There are four common metrics used to measure the quality of an embedding, namely congestion, dilation, expansion and load. The congestion of an embedding $\psi$ is defined as $cong(G_{1},G_{2},\psi )=\hbox {max}\{cong(e)|e\in E_{2}\}$, which measures queuing delay of messages, where cong(e) denotes the number of edges of $G_{1}$ whose image paths in $G_{2}$ include the edge e. The dilation of embedding $\psi$ is defined as: $dil(G_{1}, G_{2}, \psi )=\hbox {max}\{\hbox {dist}(G_{2}, \psi (u), \psi (\upsilon )) \left| (u, v)\in E_{1} \right\}$, which measures the communication delay, where dist$(G_{2}$, $\psi (u)$, $\psi (\upsilon ))$ denotes the distance between the two vertices $\psi (u)$ and $\psi (\upsilon )$ in $G_{2}$. The expansion of an embedding $\psi$ of $G_{1}$ into $G_{2}$ is defined as $exp(G_{1}, G_{2},\psi )=|V_{1}|/|V_{2}|$, which measures processors utilization. Obviously, the expansion of the embedding is at least one. To measure the processing time of tasks is referred to as the load in an embedding. The load of an embedding $\psi$ is denoted by $\mathrm{load}(G_{1},G_{2},\psi )=\hbox {max}\{\mathrm{load}(v)|v=\psi (u), u\in V_{1}\}$, where $\mathrm{load}(v)$ denotes the number of vertices of $G_{1}$ mapped on v. In addition to these parameters, wirelength is another criterion in embedding and widely used in VLSI design [16]. The wirelength is the total wire length required to complete the entire VLSI layout. The wirelength problem is to find an embedding of G into H that induces the minimum wirelength and thought to be cost-effective.

The isoperimetric problem is to find a subset of vertices of a given graph, such that the edge cut separating this subset from its complement has minimum size among all subsets of the same cardinality. Mathematically, for a given positive integer m, if $\delta _{G}(m)=\hbox {min}_{X\subseteq V,|X|=m}|[X,V-X]_{G}|$, where $[X,V-X]_{G}=\{(u,v)\in E|u\in X, v\in (V-X)\}$, then the problem is to find $X\subseteq V$ such that $|X|=m$ and $|[X,V-X]_{G}|=\delta _{G}(m)$, which is called an optimal set.

The maximum induced subgraph problem [34] is to find a subset of vertices of a given graph, such that the number of edges in the subgraph induced by this subset is maximum among all induced subgraphs with the same number of vertices. Mathematically, for a given positive integer m, if $I_{G}(m)=\hbox {max}_{X\subseteq V,|X|=m}|T_{G}(X)|$, where $T_{G}(X)=\{(u,v)\in E|u,v\in X\}$, then the problem is to find $X\subseteq V$ such that $|X|=m$ and $|T_{G}(X)|=I_{G}(m)$. For regular graphs, the optimal set problem and maximum induced subgraph problem are equivalent.

The wirelength problem is solved by edge isoperimetric problem. The following two versions of the edge isoperimetric problem of a graph $G=(V, E)$ have been considered in the literature [34] and are NP-complete [11].

Definition 1

[8] Let f be an embedding from G to H. Let $EC_{f}(e)$ denote the number of edges (u, v) of G such that e is in the path $P_{f}(u, v)$ between the vertices f(u) and f(v) in H. Considering there possibly exist multiple paths between (f(u), f(v)) in H, we choose the shortest path as $P_{f}(f(u),f(v))$. The edge congestion f is given by

$$\begin{aligned} EC_{f}(G,H)= \hbox {max}\left\{ EC_{f}(e)|e\in E(H)\right\} . \end{aligned}$$

Then, the minimum edge congestion of G into H is defined as

$$\begin{aligned} EC(G,H)=\hbox {min}_{f}\{EC(G,H)|f\ \mathrm { is}\ \mathrm { an}\ \mathrm { embedding}\ \mathrm {from}\ G\ \mathrm {to}\ H\}. \end{aligned}$$

Definition 2

[8]. The wirelength of an embedding f of G into H is given by

$$\begin{aligned} WL_{f}(G,H)= \sum _{(u,v)\in G}d_{H}(f(u),f(v)), \end{aligned}$$

where $d_{H}(f(u),f(v))$ denotes the length of the path $P_{f}(u,v)$ in H and $P_{f}(u,v)$ is the shortest path between (f(u), f(v)) in H.

Then, the minimum wirelength of G into H is defined as

$$\begin{aligned} WL(G,H)=\hbox {min}_{f}WL(G,H), \end{aligned}$$

where the minimum is taken over all embeddings f of G into H.

Lemma 1

[8] Let G be an arbitrary graph and f be an embedding of G into H. Let S be an edge cut of H such that the removal of edges of S leaves H into two components $H_{1}$ and $H_{2}$. Let $G_{1}=f^{-1}(H_{1})$ and $G_{2}=f^{-1}(H_{2})$. Also S satisfies the following conditions:

• (i) For every edge $(a,b)\in (G_{i})$, $i=1,2$, $P_f(a,b)$ has no edges in S.

• (ii) For every edge $(a, b)\in E(G)$ with $a\in V (G_{1})$ and $b\in V (G_{2})$, $P_{f}(a, b)$ has exactly one edge in S.

• (iii) $G_{1}$ and $G_{2}$ are optimal sets. Then, $EC_{f}(S)$ is minimum and $EC_{f}(S)=\sum _{v\in V(G_{1})}\hbox {deg}(v)-2|E(G_{1})|=\sum _{v\in V(G_{2})}\hbox {deg}(v)-2|E(G_{2})|$.

Lemma 2

[8] Let $f:G\rightarrow H$ be an embedding. Let $S_{1}, S_{2},\ldots , S_{p}$ be p edge cuts of H such that $S_{i}\cap S_{j}=\varnothing ,i\ne j,1\le i,j\le p$. Then,

$$\begin{aligned} WL_{f}(G,H)=\sum _{i=1}^{p}EC_{f}(S_{i}). \end{aligned}$$

2.2 The exchanged hypercube

The definition of exchanged hypercubes $EH_{s,t}$ is presented as follows. The Hamming distance between two vertices u and v, denoted by H(u, v), is the number of bits that are different in the corresponding strings for both vertices. Let $l\ge 1$ and $u = u_{l-1}\cdots u_{0}\in \{0, 1\}^{l}$ be a binary string. Let $u_{j:i}$ be the substring $u_{j}u_{j-1}\cdots u_{i}$ of u for $0\le i\le j < l$.

Definition 3

[29] The vertex set V of exchanged hypercube $EH_{s,t}$$(s\ge 1$ and $t\ge 1)$ is the set

$$\begin{aligned} \{u_{s+t}\cdots u_{t+1}u_{t}\cdots u_{1}u_{0}|u_{i}\in \{0,1\}\ \hbox {for}\ 0\le i\le s+t\}. \end{aligned}$$

Let $u_{s+t}u_{s+t-1}\cdots u_{0}$ and $v_{s+t}v_{s+t-1}\cdots v_{0}$ be two vertices in $EH_{s,t}$. E is the set of edges composed of three disjoint types $E_{1}$, $E_{2}$ and $E_{3}$:

$E_{1}=\{(u,v)|u_{0}\ne v_{0}\ \mathrm{and}\ u_{i}=v_{i}\ \mathrm{for}\ 1\le i\le s+t\},$

$E_{2}=\{(u,v)|u_{0}= v_{0}=0,H(u,v)=1\ \mathrm{with}\ u_{i}\ne v_{i}\ \mathrm{for}\ \mathrm{some}\ t+1\le i\le s+t\},$ and

$E_{3}=\{(u,v)|u_{0}= v_{0}=1,H(u,v)=1\ \mathrm{with}\ u_{i}\ne v_{i}\ \mathrm{for}\ \mathrm{some}\ 1\le i\le t\},$ where H(u, v) denotes the Hamming distance between two vertices u and v. The first set links node pairs that exhibit unity Hamming distance in the first t bits of their addresses, while the second set links node pairs that exhibit unity Hamming distance in the last s bits of their addresses.

Fig. 1

Two exchanged hypercubes $EH_{1,3}$ and $EH_{2,2}$, where dashed links correspond to the edge set $E_{1}$, solid links correspond to the edge set $E_{2}$ and bold links correspond to the edge set $E_{3}$

From the definition of $EH_{s,t}$, the number of vertices is $2^{s+t+1}$ and the number of edges is $(s+t+2)2^{s+t-1}$ where $|E_{1}|=2^{s+t}$, $|E_{2}|=s\cdot 2^{s+t-1}$ and $|E_{3}|=t\cdot 2^{s+t-1}$. For a vertex x with $x_{0}=0$, the vertex degree is $s+1$, whereas the vertex degree with $x_{0}= 1$ is $t+1$. $EH_{s,t}$ is a subgraph of the $(s+t+1)$-dimensional hypercube $Q_{s+t+1}$, and as a result, it is also a bipartite graph. Figure 1 illustrates the exchanged hypercubes $EH_{1,3}$ and $EH_{2,2}$.

In addition, the number of vertices in $EH_{s,t}$ is the same as the number of vertices in $Q_{s+t+1}$. The number of edges in $EH_{s,t}$ is only slightly over half of the number of edges in $Q_{s+t+1}$. A d-dimensional edge, or simply $(s+t+1)$-edge, of $EH_{s,t}$ is an edge (u, v) such that the labels of x and y are contradictory at bit d but are identical at all previous bits. In this case, y is called the d-neighbor of x, denoted $v= N_{d}(x)$. Let $DIM_{d}$ denote the set of all d-edges of $EH_{s,t}$. Then, $E(EH_{s,t})=\bigcup ^{s+t}_{d=0}DIM_{d}$. To be more precise, $|E(EH_{s,t})|=(s+t+2)2^{s+t-1}=(\frac{1}{2}+\frac{1}{2(s+t+1)})|E(Q_{s+t+1})|$ [35].

Lemma 3

[29] $EH_{s,t}$ and $EH_{t,s}$ are isomorphic.

Lemma 4

[29] $EH_{s,t}$ can be divided into $2^t$ copies as $Q_{s}$ and $2^{s}$ copies as $Q_{t}$.

Lemma 5

[29] $EH_{s, t}$ can be partitioned into two copies of $EH_{s-1, t}$ or $EH_{s, t-1}$.

After deleting the edge set $E_{1}$ from $EH_{s,t}$, the vertex set of $EH_{s,t}$ can separated into two parts T and S, where T is the set of all vertices with rightmost bit being 1 and S is the set of all vertices with rightmost bit being 0. In other words,

$T=\{v_{s+t}v_{s+t-1}\cdots v_{1}1|v_{i}\in \{0,1\}\ \mathrm{for}\ 1\le i\le s+t\}$ and

$S=\{u_{s+t}u_{s+t-1}\cdots u_{1}0|u_{i}\in \{0,1\}\ \mathrm{for}\ 1\le i\le s+t\}$.

Each edge $e\in E_{1}$ has one endpoint in T and the other in S, which is illustrated in Fig. 2.

Fig. 2

Induced subgraphs $Q_{t}$ and $Q_{s}$ of $EH_{s,t}$

3 Maximum induced subgraph for $EH_{s,t}$

In this section, we mainly focus on finding the maximum induced subgraph of $EH_{s,t}$. There is a significant relationship between the maximum induced subgraph problem and the wirelength problem [8].

For any integer $m\ge 1$ and $S\subseteq V(G)$ with $|S|=m$, if G[S] is the subgraph with the maximum number of edges among all induced subgraphs with m vertices, then G[S] is called the maximum induced graph with m vertices in G.

For $1\le s\le t$, we group $V(EH_{s,t})$ into eight disjoint subsets [14] as follows, $V_{1}=\{1\underbrace{*\cdots *}_{t-1}01\}$, $V_{2}=\{1\underbrace{*\cdots *}_{t-1}11\}$, $V_{3}=\{0\underbrace{*\cdots *}_{t-1}01\}$, $V_{4}=\{0\underbrace{*\cdots *}_{t-1}11\}$, $V_{5}=\{1\underbrace{*\cdots *}_{t-1}00\}$, $V_{6}=\{1\underbrace{*\cdots *}_{t-1}10\}$, $V_{7}=\{0\underbrace{*\cdots *}_{t-1}00\}$, $V_{8}=\{0\underbrace{*\cdots *}_{t-1}10\}$.

If $u = u_{s+t+1}\cdots u_{t+1}u_{t}\cdots u_{1}$ is a node in $Q_{t}^{i} (0\le i\le 2^{s-1})$ and the decimal value of $u_{t:1}$ is j, then the node u can be denoted by $q^{i, j}_{t}$. The subgraph induced by $V_{i}(1\le i\le 4)$ contains $2^{s-1}$ disjoint $(t-1)$-cubes, and the subgraph induced by $V_{i}(1\le i\le 4)$ contains $2^{t-1}$ disjoint $(s-1)$-cubes. If $s\ge 2$, for the subgraph induced by $V_{i}(1\le i\le 4)$, we denote the $(t-1)$-cube by $Q_{t-1}^{i,j}$, where $j (j\in [0, 2^{s-1}-1])$ is the decimal number of $u_{s+t-1,t+1}$, and the vertex u in $Q_{t-1}^{i,j}$ is represented by $q_{t-1}^{i,j,k}$, where $k(k\in [0, 2^{t-1}-1])$ is the decimal number of $u_{t-1,1}$. Similarly, for $(5\le i\le 8)$, we can define the $(s-1)$-cube $Q_{s-1}^{i,j}$ and the vertex $q_{s-1}^{i,j,k}$, where $j\in [0, 2^{t-1}-1]$ and $k\in [0, 2^{s-1}-1]$. This labeling is denoted by lex.

Definition 4

[36] An incomplete hypercube on i vertices of $Q_{n}$ is the subcube induced by $\{0,1,\ldots , i-1\}$ and is denoted by $L_{i}$.

Theorem 1

[37] For $1\le i\le 2^{n}$, $L_{i}$ is an optimal set in the hypercube $Q_{n}$.

Lemma 6

[38] For $1\le i, j\le 2^{n}$ such that $i+j\le 2^{n}$, $|E(Q_{n}[L_{i}])|+|E(Q_{n}[L_{j}])|+\{\hbox {i,j}\}\le |E(Q_{n}[L_{i+j}])|$.

Lemma 7

[39] Let V be a vertex subset of graph G and $\{V_{0}, V_{1}\}$ be a partition of V. Then, $\tau (V)=\tau (V_{0})+\tau (V_{1})+\tau (V_{0},V_{1}).$

Lemma 8

Let K be a subgraph of $EH_{s,t}$ isomorphic to $L_{k}$ where $1\le s\le t$ and $k\le 2^{s+t}+2^{s}$. Let $K_{1}$ and $K_{2}$ be disjoint segments induced by $k_{1}$ and $k_{2}$ consecutive vertices on $\bigcup ^{2^{s}}_{i=1}Q_{t}\cup Q_{s}^{1}$, respectively, such that $k_{1} +k_{2}=k$. Then, $|E(EH_{s,t}[K_{1}\cup K_{2}])|\le |E(EH_{s,t}[K])|$.

Proof

We can denote $Q_{t}^{1}$, $Q_{t}^{2}$,..., and $Q_{t}^{2^{s}}$ as $2^{s}$ copies of $Q_{t}$ who are composed of the edges $E_{3}$, and $Q_{s}^{1}$, $Q_{s}^{2}$,..., and $Q_{s}^{2^{t}}$ as $2^{t}$ copies of $Q_{s}$ who are composed of the edges $E_{2}$. For simplicity, we denote $u^{1}_1$, $u_{1}^{2}$,...and $u_{1}^{2^{t}}$ as $2^{t}$ vertices of $Q_{t}^{1}$, $u_{2}^{1}$, $u_{2}^{2}$,..., and $u_{2}^{2^{t}}$ as $2^{t}$ vertices of $Q_{t}^{2}$, ..., and $u^{1}_{2^{s}}$, $u^{2}_{2^{s}}$,..., and $u^{2^{t}}_{2^{s}}$ as $2^{t}$ vertices of $Q_{t}^{2^{s}}$. And we denote $v_{1}^{1}$, $v^{2}_{1}$,...and $v^{2^{s}}_{1}$ as $2^{s}$ vertices of $Q_{s}^{1}$, $v^{1}_{2}$, $v^{2}_{2}$,...and $v^{2^{s}}_{2}$ as $2^{s}$ vertices of $Q_{s}^{2}$,..., and $v^{1}_{2^{t}}$, $v^{2}_{2^{t}}$,...and $v^{2^{s}}_{2^{t}}$ as $2^{s}$ vertices of $Q_{s}^{2^{t}}$. Let $E(EH_{s, t}[K_{1}\wedge K_{2}])$ denote the set of edges in $EH_{s, t}$ with one end in $K_{1}$ and the other end in $K_{2}$, and we have the following cases:

Case 1.$k_{1}, k_{2}\le 2^{t}$. We consider the following cases.

Case 1.1$K_{1}\subset Q_{t}^{1}.$ Since $Q_{t}$ is isomorphic the t-dimensional cube, by the definition of $EH_{s,t}$ and Theorem 1, $|E(EH_{s, t}[K_{1}\cup K_{2}])| = |E(Q_{t}[K_{1}\cup K_{2}])|\le |E(Q_{t}[K])| = |E(EH_{s, t}[K])|$.

Case 1.2$K_{1}\subset Q_{s}^{1}.$ The proof is similar to Subcase 1.2.

Case 2.$2^{t}< k_{1}\le 2^{t}+2^{s}$. $K_{1}\subset Q_{t}^{1}\cup Q_{s}^{1}$. Let $2^{t} = k_{1} + k_{2}$, where $k_{1}$ vertices lie in $Q_{t}^{1}$ and $k_{2}$ vertices lie in $Q_{s}^{1}$, inducing subgraphs $K_{1}$ and $K_{2}$ in $Q_{t}^{1}$ and $Q_{s}^{1}$, respectively. Since there are one edge joining vertices in $K_{1}$ and vertices in $K_{2}$, $|E(EH_{s,t}[K_{1}\wedge K_{2}])|\le k_{2}$. This implies that $|E(EH_{s,t}[K_{1} \cup K_{2}])| = |E(EH_{s,t}[K_{1}])| + |E(EH_{s,t}[K_{2}])| + |E(EH_{s,t}[K_{1}\wedge K_{2}])|\le |E(EH_{s,t}[L_{k_{1}}])| + |E(EH_{s,t}[L_{k_{2}}])| + k_{2}$. By Lemma 1, we get $|E(EH_{s,t}[K_{1}\cup K_{2}])|\le |E(EH_{s,t}[L_{k_{1}}+k_{2}])| = |E(EH_{s,t}[K])|$.

Case 3.$2^{t}+2^{s}< k_{1}\le 2^{s+t}+2^{s}$. Let $k_{1}$, $k_{2}$ be the number of consecutive vertices in $K_{1}$, $K_{2}$ that lie in $\bigcup _{i=1}^{2^{s}}Q_{t}^{i}\cup Q_{s}^{1}$. Then, $|E(EH_{s,t}[K_{1}])|\le |E(EH_{s,t}[L_{k_{1}}])|$, $|E(EH_{s,t}[K_{2}])|\le |E(EH_{s,t}[L_{k_{2}}])|$ and $|E(EH_{s,t}[K_{1}\wedge K_{2}])|\le k_{2} + k_{2}$. Hence, $|E(EH_{s,t}[K_{1}\cup K_{2}])|\le |E(EH_{s,t}[L_{k_{1}}])| + |E(EH_{s,t}[L_{k_{2}}])| + 2k_{2}$. Let $H_{1} = L_{k_{1}}$. Then, $|E(EH_{s,t}[H_{1}])| = |E(EH_{s,t}[L_{k_{1}}])|$. Let $H_{2}$ be the subgraph of $EH_{s,t}$ induced by the vertices in $Q^{1}_{s}$ labeled $2^{s+t}-1, 2^{s+t}-2,\ldots , 2^{s+t}-k_{2}$. This implies $|E(EH_{s,t}[H_{2}])| = |E(EH_{s,t}[L_{k_{2}}])|$ and $|E(EH_{s,t}[H_{1}\wedge H_{2}])|\ge k_{2} + k_{2}$. Therefore $|E(EH_{s,t}[H_{1}\wedge H_{2}])|\ge |E(EH_{s,t}[L_{k_{1}}])| + |E(EH_{s,t}[L_{k_{2}}])| + 2k_{2}$ and hence $|E(EH_{s,t}[K_{1}\cup K_{2}])|\le |E(EH_{s,t}[H_{1}\cup H_{2}])|$. $\square$

Theorem 2

The number of edges in a maximum subgraph induced by $2^{s+t}+m$ vertices of $EH_{s,t}$, $1\le s\le t$, $1\le m\le 2^{s+t+1}$, is given by

$$\begin{aligned} |E(EH_{s,t}[S])| =t\cdot 2^{s+t-1}+I_{EH_{s,t}}(m)+m. \end{aligned}$$

Proof

Let $I_{m}^{k_{i}}$ denote the k-dimensional subgraph of $EH_{s,t}$ on m vertices, which contains subcubes $Q_{t}^{1}$, $Q_{t}^{2}$,..., and $Q_{t}^{i}$ and $E_{1}$ for $1\le i\le 2^{t}$. This means that there are $k\cdot 2^{k_{i}-1}$ edges between $\bigcup _{i=1}^{2^{s}}Q_{t}^{i}$ and $\bigcup _{i=1}^{2^{s}}Q_{t}^{i+1}$. Also, $\bigcup _{i=1}^{2^{s}}Q_{t}^{i}$ has $t_{i}2^{t_{i}-1}$ edges within itself. The maximum subgraph induced by $I_{m}^{k}$ of $EH_{s,t}$ contains two components $Q_{k}^{i}$ and $I^{t}_{m-2^{s+t}}$, where the vertices in $Q_{t}^{i}$ are numbered as $0,1,\ldots ,2^{s+t}-1$ and the vertices in $I^{t}_{m-2^{s+t}}$ are numbered as $2^{s+t}, 2^{s+t}+1,\ldots ,2^{s+t+1}$, for $t=\lceil \hbox {log}(m-2^{s+t})\rceil$. Thus, $I^{k}_{m}$ contains a set of $Q_{t}^{i}$ and $Q^{i}_{s}$, and no two constituent cubes are of the same size. The number of edges induced by $I^{k}_{m}$ in $EH_{s,t}$, $1\le s\le t$ is given by $|E[I^{k}_{m}])| =t\cdot 2^{s+t-1}+I_{EH_{s,t}}(m)+m$. The lemma holds. $\square$

Lemma 9

For $1\le s \le t$ and $1\le i\le 2^{s+t}+2^{s}$, $L_{i}$ is an optimal set.

Proof

Let R be a subgraph of $EH_{s,t}$ isomorphic to $L_{k}$ where $k\le 2^{s+t}+2^{s}$. Let N be a set of k non-consecutive vertices in $EH_{s,t}$. Then, $N =\bigcup _{i=1}^{p}X_{i}$ where $p\ge 2$, $X_{i}'$s are mutually disjoint and each $X_{i}$ is a set of consecutive vertices in $EH_{s,t}$ such that $\bigcup _{i=1}^{p}|X_{i}| = n$. If $X_{i}$ contains vertices labeled $2^{s+t}+2^{s}-1$ and $2^{s+t}+2^{s}$, then $X_{i}$ is split into two sets such that one set ends with label $2^{s+t}+2^{s}-1$ and the other set begins with label $2^{s+t}+2^{s}$. By Lemma 2, we get $|E(EH_{S,t}[N])|\le |E(EH_{s,t}[R])|$. $\square$

Theorem 3

For $1\le i\le 2^{s+t+1}$, $L_{i}$ is an optimal set in $EH_{s,t}$.

Proof

By Lemma 4, after deleting the edge set $E_{1}$ from $EH_{s,t}$, $EH_{s, t}$ can be partitioned into $EH_{s-1,t}$ or $EH_{s,t-1}$. By Lemma 1, $L_{i}$ is an optimal set for $1\le i\le 2^{s+t}+2^{s}$. Now let $i > 2^{s+t}+2^{s}$. Then, we have $L_{i}' = EH_{s,t}-L_{i} \cong L_{2^{s+t-i}}$. Since $2^{s+t+1}-i < 2^{s+t+1}-1$, by Lemma 1, $L_{i}'$ is an optimal set in $EH_{s,t}$. Since $EH_{s-1,t}\cong EH_{s,t-1}$, $L_{i}$ is an optimal set in $EH_{s,t}$. $\square$

4 Embedding the exchanged hypercubes into grids

In this section, we consider the embeddings of exchanged hypercubes into linear arrays and grids, respectively.

4.1 Embedding exchanged hypercubes into linear arrays

In this section, we will give an embedding of $EH_{s,t}$ into a linear array with minimum wirelength. When H is a path, WL(G, H) represents linear wirelength of G or minimum linear arrangement (MinLA) of G. The wirelength problem of a graph G into H is to find an embedding of G into H that induces the minimum wirelength WL(G, H).

Linear arrangements are a particular case of embedding graphs in d-dimensional grids. The dilation of the embedding is most commonly called the bandwidth, which is NP-complete [11], and can be defined as follows:

Definition 5

[8] For any integer $n\ge 1$, the linear array of n vertices, denoted by $P_{n}$, is a graph such that $V(P_{n})=\{1,2,\ldots ,n\}$ and where $E(P_{n})=\{(i,i+1)|i\in [1,n-1]\}$.

Definition 6

Let $f:V(EH_{s,t})\rightarrow V(P_{2^{s+t+1}})$ be an embedding, which is defined as follow: Label the vertices of $P_{2^{s+t+1}}$ as $0, 1,\ldots ,2^{s+t+1}-1$. Then, for any $v\in V(EH_{s,t})$, let $f(v)=lex(v)$.

Let G be a graph and $L_{n}$ be a linear array with n vertices. Let f be an embedding from G to $L_{n}$. The bandwidth of the embedding f of G into $L_{n}$ is defined as

$$\begin{aligned} B_{f}(G) = \hbox {max}\{|f(v)-f(u)|(u, v) \in E(G)\}. \end{aligned}$$

Furthermore, the minimum bandwidth from all embeddings from G to $L_{n}$ is defined as

$$\begin{aligned} B(G) = \hbox {min}\{B_{f}(G)| f\ \mathrm{is\ an\ embedding\ from}\ G\ \mathrm{to}\ L_{n}\}. \end{aligned}$$

The bandwidth problem is to find an embedding of G into $L_{n}$, such that it has the minimum bandwidth.

Theorem 4

$EH_{s,t}$ can be embedded into $L_{2^{s+t+1}}$ with dilation $2^{s+t}+1$.

Proof

Let $f=lex$. By Lemma 4, $EH_{s, t}$ can be divided into $2^{s}$ copies of $Q_{t}$ and $2^{t}$ copies of $Q_{s}$. Hence, we can denote $Q_{t}^{1}$, $Q_{t}^{2}$,..., and $Q_{t}^{2^{s}}$ as $2^{s}$ copies of $Q_{t}$ who are composed of the edges $E_{3}$, and $Q_{s}^{1}$, $Q_{s}^{2}$,..., and $Q_{s}^{2^{t}}$ as $2^{t}$ copies of $Q_{s}$ who are composed of the edges $E_{2}$. For simplicity, we denote $u^{1} 1$, $u_{1}^{2}$,...and $u_{1}^{2^{t}}$ as $2^{t}$ vertices of $Q_{t}^{1}$, $u_{2}^{1}$, $u_{2}^{2}$,..., and $u_{2}^{2^{t}}$ as $2^{t}$ vertices of $Q_{t}^{2}$, ..., and $u^{1}_{2^{s}}$, $u^{2}_{2^{s}}$,..., and $u^{2^{t}}_{2^{s}}$ as $2^{t}$ vertices of $Q_{t}^{2^{s}}$. And we denote $v_{1}^{1}$, $v^{2}_{1}$,...and $v^{2^{s}}_{1}$ as $2^{s}$ vertices of $Q_{s}^{1}$, $v^{1}_{2}$, $v^{2}_{2}$,...and $v^{2^{s}}_{2}$ as $2^{s}$ vertices of $Q_{s}^{2}$,..., and $v^{1}_{2^{t}}$, $v^{2}_{2^{t}}$,...and $v^{2^{s}}_{2^{t}}$ as $2^{s}$ vertices of $Q_{s}^{2^{t}}$. Then, we may verify the result by the following cases below.

Case 1.$(u,v)\in E(Q_{t}^{i})(1\le i\le 2^{s})$. Without loss of generality, suppose that $(u_{1}^{1},v_{1}^{1})\in E(Q_{t}^{1})$. Let $(f(u_{1}^{1}), f(v_{1}^{1}))$ be the image of $(u_{1}^{1},v_{1}^{1})$ in the linear array. Clearly, $\hbox {max}\{\hbox {dist}(L_{2^{s+t+1}}, f(u_{1}^{1}),f(v_{1}^{1}))|(u_{1}^{1},v_{1}^{1}) \in E(Q_{t}^{1}) = \hbox {max}\{|f(v_{1}^{1})-f(u_{1}^{1})|(u_{1}^{1},v_{1}^{1})\in E(Q_{t}^{1})\}=2^{t-1}$.

Case 2.$(u,v)\in E(Q_{s}^{i})(1\le j\le 2^{t})$. The proof is similar to Case 1. Thus, results can be obtained directly as $2^{s-1}$.

Case 3.$(u,v)\in E(Q_{t}^{i}\bigcup Q_{t}^{j})(1\le i\le 2^{s}, 1\le i\le 2^{t})$. Without loss of generality, suppose that $(u_{1}^{1},v_{1}^{1})\in E(Q_{t}^{1}\bigcup Q_{s}^{1})$. Let $(f(u_{1}^{1}), f(v_{1}^{1}))$ be the image of $(u_{1}^{1},v_{1}^{1})$ in the linear array. It is easy to verify that $\hbox {max}\{\hbox {dist}(L_{2^{s+t+1}},f(u_{1}^{1}),f(v_{1}^{1}))|(u_{1}^{1},v_{1}^{1})\in E(Q_{t}^{1}\bigcup Q_{s}^{1}) =\hbox {max}\{|f(v_{1}^{1})-f(u_{1}^{1})|(u_{1}^{1},v_{1}^{1})\in E(Q_{t}^{1}\bigcup Q_{s}^{1})\}=2^{s+t}+1$.

In summary, the theorem is proved. $\square$

Lemma 10

$R^{lex}_{i} = \{1, . . . , i2^{\lceil \frac{s+t+1}{2}\rceil }\}$ is an optimal set in $EH_{s,t}$ for $i = 1, 2,\ldots , 2^{\lfloor \frac{s+t+1}{2}\rfloor }$ and $\lfloor \frac{s+t+1}{2}\rfloor + \lceil \frac{s+t+1}{2}\rceil = s+t+1$.

Proof

This proof can be obtained directly from Theorem 4. $\square$

Lemma 11

For $j = 1, 2,\ldots , 2^{\lfloor \frac{s+t+1}{2}\rfloor }$,

$$\begin{aligned} C_{j}^{lex}=\left\{ \begin{aligned}&1,&1\times 2^{\lfloor \frac{s+t+1}{2}\rfloor },\quad&2 \times 2^{\lfloor \frac{s+t+1}{2}\rfloor },&\ldots&(2^{\lceil \frac{s+t+1}{2}\rceil }) \times 2^{\lfloor \frac{s+t+1}{2}\rfloor },\\&2,&1\times 2^{\lfloor \frac{s+t+1}{2}\rfloor }+ 1,\quad&2\times 2^{\lfloor \frac{s+t+1}{2}\rfloor } + 1,&\ldots&(2^{\lceil \frac{s+t+1}{2}\rceil })\times 2^{\lfloor \frac{s+t+1}{2}\rfloor }+1,\\&\ldots \\&j,&1\times 2^{\lfloor \frac{s+t+1}{2}\rfloor }+j-1,\quad&2\times 2^{\lfloor \frac{s+t+1}{2}\rfloor } + j-1,&\ldots&(2^{\lceil \frac{s+t+1}{2}\rceil }) \times 2^{\lfloor \frac{s+t+1}{2}\rfloor } + j-1\\ \end{aligned} \right\} \end{aligned}$$

is an optimal set in $EH_{s,t}$ where $2^{\lceil \frac{s+t+1}{2}\rceil } + 2^{\lfloor \frac{s+t+1}{2}\rfloor } = s+t+1$.

Proof

Let $f:C_{j}^{lex}\rightarrow L_{j\times 2^{\lfloor \frac{s+t+1}{2}\rfloor }}$ with $f(k\times 2^{\lceil \frac{s+t+1}{2}\rceil }+l)=l\times 2^{\lfloor \frac{s+t+1}{2}\rfloor }+k$. We use $u_{1}u_{2}\ldots u_{t+1}$ in $C_{j}^{lex}$ to denote the decimal string of $l\times 2^{\lfloor \frac{s+t+1}{2}\rfloor }+k$. Since the decimal string representations of two numbers u and v differ in exactly one bit, the same holds for f(u) and f(v). Thus, (u, v) is an edge in $R_{i}$ and (f(u), f(v)) is an edge in $L_{2^{i}}$. Therefore, $R_{i}$ is isomorphic to $L_{i}$. By Theorem 1, $C_{j}^{lex}$ is an optimal set of $EH_{s,t}$. $\square$

Lemma 12

[37] $WL(Q_{n}, P_{2^{n}}) = 2^{2n-1}-2^{n-1}.$

Lemma 13

The lex embedding of exchanged hypercube $EH_{s,t}$ into a linear array $P_{2^{s+t+1}}$ induces a minimum wirelength.

Proof

Let $f=lex$ and $G=EH_{s,t}$. For $1\le i\le 2^{s+t+1}$, let $S_{i}$ be ith edge of $P_{2^{s+t+1}}$. Removal of $S_{i}$ leaves $P_{2^{s+t+1}}$ into two components $X_{i}$ and $X_{i}^{'}$ where $V(X_{i})=\{0, 1, \ldots ,i\}$ and $V(X_{i}^{'})=\{j+1, j+2,\ldots , 2^{s+t+1}\}$. Let $G_{i}$ and $G_{i}^{'}$ be the inverse images of $X_{i}$ and $X_{i}^{'}$ under f, respectively. By Lemma 8, $G_{i}$ is an optimal set in $EH_{s,t}$. Thus, the edge cut $S_{i}$ satisfies Lemma 8. It can be further verified that $\{(i-1,i)\}$ satisfies Lemma 8, and the edge congestion $EC_{f}(S_{i})$ is minimum under embedding lex for $i = 1,2,\ldots ,2^{s+t+1}$. Thus, the wirelength $WL_{f}(EH_{s,t},P_{2^{s+t+1}})$ of embedding $EH_{s,t}$ into $P_{2^{s+t+1}}$ is minimum. $\square$

Theorem 5

For $1\le s\le t$, the wirelength of embedding $EH_{s,t}$ into a linear array $P_{2^{s+t+1}}$ is given by

$$\begin{aligned} WL(EH_{s,t}, P_{2^{s+t+1}})=2^{s+2t-1}-2^{s+t-1}+2^{2t}+2^{2t+2}. \end{aligned}$$

Proof

Let $f=lex$. We first derive the exact wirelength of embedding the induced subgraphs $EH_{s,t}[E_{1}]$, $EH_{s,t}[E_{2}]$ and $EH_{s,t}[E_{3}]$ into $L_{2^{s+t+1}}$. Let the edge set $E_{1}=\{(u,v)|u_{0}\ne v_{0},u_{i}=v_{i}\ \mathrm{for}\ 1\le i\le s+t\}$. After deleting $E_{1}$ from $EH_{s,t}$, the vertex set S is decomposed into $2^{t}$ connected components. Each component is an s-dimensional hypercube $Q_{s}$; moreover, these $2^{t}$ hypercubes $Q_{s}$ are pairwise disjoint, and there are no edges joining any two $Q_{s}$. Since each edge $e\in E_{1}$ has one endpoint in $Q_{t}$ and the other in $Q_{s}$, $E_{1}$ is a perfect matching of $EH_{s,t}$ between $Q_{s}$ and $Q_{t}$.

For $1\le i\le 2^{s+t}$, $S_{j}$ is an edge cut of $P_{2^{t}}$, which disconnects $P_{2^{t}}$ into two linear arrays $P_{j}$ and $P_{j}^{'}$, where $2\le j\le 2^{s+t-1}$, $V(P_{j})=\{1,2,\ldots ,j\}$, and $V(P_{j}^{'})=\{j+1,j+2,\ldots ,2^{s+t-1}\}$. Let $G_{j1} = f^{-1}(P_{j1})$ and $G_{j2} = f^{-1}(P_{j2})$. By Lemma 8, $G_{j1}$ is an optimal set and each $S_{j}$ satisfies conditions (i) and (ii) of Lemma 8. Therefore, $EC_{f}(S_{j})$ is minimum. Let $A_{i}$ be an edge cut of $P_{2^{s+t}}$ such that $S_{i}$ disconnects $P_{2^{s+t}}$ into two components $P_{i1}$ and $P_{i2}$. Let $G_{i1}$ and $G_{i2}$ be the inverse images of $P_{i1}$ and $P_{i2}$ under f, respectively. By Theorem 1, $G_{i1}$ is an optimal set and each $S_{i}$ satisfies conditions (i) and (ii) of Lemma 8. Therefore, the sum congestion of $G[\bigcup ^{2^{s}-1}_{i=1}Q_{t}^{i}]$ is

$$\begin{aligned} WL_{f}(A_{i})= & {} WL\left( G\left[ \bigcup ^{2^{s}-1}_{i=1}Q_{t}^{i}\right] , P_{2^{s+t}}\right) \\= & {} \sum _{i=1}^{2^{s+t-1}}EC_{f}(S_{i}) \\= & {} 2^{s+2t-1}-2^{s+t-1}. \end{aligned}$$

For $2^{s+t}+1\le i\le 2^{s+t+1}$, $S_{i}$ is an edge cut of $P_{2^{s+t-1}}$, which disconnects $P_{2^{s+t-1}}$ into two linear arrays $P_{i}$ and $P_{i}^{'}$, where $2^{s+t-1}+1\le i\le 2^{s+t+1}$, $V(P_{i})=\{1,2,\ldots ,i\}$, and $V(P_{i}^{'})=\{i+1,i+2,\ldots ,2^{s+t+1}-2\}$. Let $G_{i1} = f^{-1}(P_{i1})$ and $G_{i2} = f^{-1}(P_{i2})$. $G_{i1}$ is an optimal set and each $S_{i}$ satisfies conditions (i) and (ii) of Lemma 8. Therefore, $EC_{f}(S_{i})$ is minimum. Let $B_{j}$ be an edge cut of $P_{2^{s+t}}$ such that $S_{j}$ disconnects $P_{2^{s+t}}$ into two components $P_{j1}$ and $P_{j2}$. Therefore, the sum congestion of $G[\bigcup ^{2^{t}-1}_{i=1}Q_{s}^{i}]$ is

$$\begin{aligned} WL_{f}(B_{j})= & {} WL\left( G\left[ \bigcup ^{2^{t}-1}_{i=1}Q_{s}^{i}\right] , P_{2^{s+t}}\right) \\= & {} \sum ^{2^{s+t+1}}_{j=2^{s+t}+1}EC_{f}S_{j}\\= & {} 2^{t}(2^{2s-1}-2^{s-1}). \end{aligned}$$

For $1\le k\le 2^{s+t+1}$, let $C_{k}$ be an edge cut of $P_{2^{s+t}}$ such that $C_{k}$ disconnects $P_{2^{s+t+1}}$ into two components $P_{k1}$ and $P_{k2}$. It is apparent that $P_{kl}$ is symmetric about $l=2^{s+t}$. So we need only consider the case for $1\le l\le 2^{s+t}$ in computing the wirelength. Therefore, the sum congestion of $E_{1}$ is

$$\begin{aligned} EC_{f}(C_{k})= & {} 2\sum ^{2^{s+t}}_{k=1}S_{k}\\= & {} 2(1+2+\cdots +2^{s+t}-1)\\= & {} 2^{s+t}\cdot \left( 2^{s+t}-1\right) . \end{aligned}$$

Thus,

$$\begin{aligned} WL(EH_{s,t},P_{2^{s+t+1}})= & {} WL_{f}(EH_{s,t},P_{2^{s+t+1}})\\= & {} WL_{f}(A_{i})+WL_{f}(B_{j})+WL_{f}(C_{k})\\= & {} \sum ^{2^{s+t}}_{i=1}A_{i}+\sum ^{2^{s+t+1}}_{j=2^{s+t}+1}B_{j}+2\sum ^{2^{s+t}}_{k=1}C_{k}\\= & {} 2^{s}\left( 2^{2t-1}-2^{t-1}\right) +2^{t}\left( 2^{2s-1}-2^{s-1}\right) +2^{s+t}\cdot (2^{s+t}-1)\\= & {} 2^{s+2t-1}+2^{t+2s-1}+2^{2(s+t)}-2^{s+t+1}. \end{aligned}$$

$\square$

4.2 Embedding the exchanged hypercube into a grid

In this section, we embed $EH_{s,t}$ into a grid with minimum wirelength. The proposed embedding of $EH_{s,t}$ into $P_{2^{s+t+1}}$ in Sect. 4.1 is actually an embedding of $EH_{s,t}$ into the special grid, which is a $1\times (s+t+1)$ grid. In the following, we will give an embedding of $EH_{s,t}$ into grid $M(2^{\lfloor (s+t+1)/2\rfloor }, 2^{\lceil (s+t+1)/2\rceil })$ with minimum wirelength. Firstly, the definition of grid is given as follows:

Notation 1

An $m \times n$ grid M(m, n) is denoted by an $m \times n$ matrix

$\left( \begin{array}{cccc} \alpha _{11} &{} \alpha _{12} &{} \cdots &{} \alpha _{1n} \\ \alpha _{21} &{} \alpha _{22} &{} \cdots &{} \alpha _{2n} \\ \cdots &{} \cdots &{} \cdots &{} \cdots \\ \alpha _{m1} &{} \alpha _{m2} &{} \cdots &{} \alpha _{mn} \\ \end{array} \right) ,$

where $V\left( M\right) =\left\{ \alpha _{ij}\left| 1\le i\le m \right. \right.$, and $\left. 1\le j\le n\right\}$, $\left( \alpha _{i, j}, \alpha _{i, j+1}\right) \in E\left( M \right)$ for $1\le i\le m$ and $1\le j\le n-1$, and $\left( \alpha _{kl}, \alpha _{k+1, l}\right) \in E\left( M \right)$ for $1\le k\le m-1$ and $1\le l\le n$. $\left\langle \alpha _{11}, \alpha _{12}, \ldots , \alpha _{1n} \right\rangle$ and $\left\langle \alpha _{m1}, \alpha _{m2}, \ldots , \alpha _{mn}\right\rangle$ are called the row borders, while $\left\langle \alpha _{11}, \alpha _{21}, \ldots , \alpha _{m1} \right\rangle$ and $\left\langle \alpha _{1n}, \alpha _{2n}, \ldots , \alpha _{mn}\right\rangle$ are called the column borders.

Definition 7

Let $\pi :V(EH_{s,t})\rightarrow V(M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })\})$ be an embedding, which is defined as follows: The first row is labeled from 1 to $2^{\lceil n/2\rceil }$ from top to bottom. The ith row is labeled as $(i-1)2^{\lfloor \frac{s+t+1}{2}\rfloor }+1, (i-1)2^{\lfloor \frac{s+t+1}{2}\rfloor }+2,\ldots ,i2^{\lfloor \frac{s+t+1}{2}\rfloor }$ from left to right where $i=1,2,\ldots ,2^{\lceil \frac{s+t+1}{2}\rceil }$. Then, for any $v\in V(EH_{s,t})$, let $\pi (v)=lex(v)$.

Then, we first prove the edge congestion problem and the wirelength problem of $EH_{s,t}$ into a grid can be solved by using the embedding $\pi$. Next, we will give the embedding of $EH_{s,t}$ into the grid $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$ with minimum wirelength, for $1\le s\le t$.

Theorem 6

Let $G=EH_{s,t}$ and $H=M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })\}$, for $1\le s\le t$. Let $S_{i}=\{S_{1},S_{2},\ldots ,S_{p}\}$ be p edge cuts of each column in $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })\}$, which consists of edges between the rows i and $i+1$ of $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$, where $1\le p\le 2^{\lceil \frac{s+t+1}{2}\rceil }-1$, $1\le i\le 2^{\lceil \frac{s+t+1}{2}\rceil }-1$. Furthermore, let $f=\pi$. Then,

$$\begin{aligned} \sum _{i=1}^{2^{\lceil \frac{s+t+1}{2}\rceil }-1}EC_{f}(S_{i})=2^{\lfloor \frac{s+t+1}{2}\rfloor -1}\left( 2^{2t}-2^{t}\right) . \end{aligned}$$

Proof

Let $H_{i1}$ and $H_{i2}$ denote two connected components of $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil }\}-S_{i}$, where $f(G_{i1})=H_{i1}$ and $f(G_{i2})=H_{i2}$, as depicted in Fig. 3. According to Theorem 2, the subgraph induced by $V(G_{i_{1}})$ is maximum. By Lemma 1, $EC_{f}(S_{i})$ is minimum, $1\le j\le 2^{\lceil \frac{s+t+1}{2}\rceil }-1$. Thus, we have:

$$\begin{aligned} \sum _{i=1}^{2^{\lceil \frac{s+t+1}{2}\rceil }-1}EC_{f}(S_{i})= & {} \sum _{i=1}^{2^{\lceil \frac{s+t+1}{2}\rceil }-1}EC_{f}(S_{i})\\= & {} \sum _{i=1}^{2^{\lceil \frac{s+t+1}{2}\rceil }-1}\lambda _{G}\left( i\cdot 2^{\lfloor \frac{s+t+1}{2}\rfloor }\right) \\= & {} 2^{\lfloor \frac{s+t+1}{2}\rfloor -1}\left( 2^{2t}-2^{t}\right) . \end{aligned}$$

$\square$

Fig. 3

Embedding $EH_{s,t}$ into $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$

Theorem 7

For $1\le s\le t$, $EH_{s,t}$ can be embedded into the grid $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$ with minimum wirelength.

Proof

Let $f=\pi$. Let $A_{ij}$ be an edge cut of each column in the grid $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$ such that $A_{ij}$ disconnects $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$ into two components $A_{i1}$ and $A_{i2}$, $i= 1, 2,\ldots ,2^{\lceil \frac{s+t+1}{2}\rceil }-1$. Furthermore, let $B_{ij}$ be an edge cut of each row in the grid $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$ such that $B_{ij}$ disconnects $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$ into two components $B_{j1}$ and $B_{j2}$, $j = 1, 2, \ldots ,2^{\lfloor \frac{s+t+1}{2}\rfloor }-1$. Let $G_{i1}$ and $G_{i2}$ be the inverse images of $A_{i1}$ and $A_{i2}$ under f, respectively. Then, the edge cut $A_{ij}$ satisfies conditions (i) and (ii) of Lemma 1. Further by Theorem 2, the subgraph $G_{i}$ induced by the vertices of $A_{ij}$ is maximum. Thus, by Lemma 1, $EC_{f}(A_{ij})$ is minimum for $i= 1, 2,\ldots ,2^{\lceil \frac{s+t+1}{2}\rceil }-1$. Let $G_{j1}$ and $G_{j2}$ be the inverse images of $B_{j1}$ and $B_{j2}$ under f, respectively. The edge cut $B_{ij}$ satisfies Lemma 1. Further by Theorem 2, the subgraph $G_{j}$ induced by the vertices of $B_{j}$ is maximum. Thus, by Lemma 1, $EC_{f}(B_{ij})$ is minimum for $j = 1, 2, \ldots ,2^{\lfloor \frac{s+t+1}{2}\rfloor }-1$. The Lemma 2 implies that the wirelength of this embedding is minimum. $\square$

Theorem 8

Let $G=EH_{s,t}$ and $H=M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$, $1\le s\le t$. Let $f=\pi$, and let $S_{1}$, $S_{2}$,...,$S_{p}$ be p edge cuts of $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$. Furthermore, let $H_{j1}$ and $H_{j2}$ denote two connected components of $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })-S_{j}$, where $f(G_{j1})=H_{j1}$ and $f(G_{j2})=H_{j2}$. For any $1\le j\le p$, if $EC_{f}(H_{j1})$ is minimum, then $f^{-1}(H_{j1})$ is a maximum subgraph in G.

Proof

Suppose $EC_{f}(\delta _{H}(j_{1}))$ is minimum with $V(H_{j1})=m$. We will prove that the subgraph induced by $G_{j1}=f^{-1}(H_{j1})$ is maximum on m vertices of $EH_{s,t}$. Supposing not, there exists $V(G^{'}_{j1})\subseteq V(EH_{s,t})$ such that $E(G_{j1})<|E(G^{'}_{j1})|$. By Lemma 1, $EC_{f}(\delta _{H}(j_{1}))=nm-2|E(G_{j1})|> nm-2|E(G^{'}_{j1})|=EC_{f}(\delta _{H}(f(G^{'}_{j1})))$, which is a contradiction to our assumption. Thus, $EC_{f}(\delta _{H}(j_{1}))$ is minimum. Therefore, $f^{-1}(H_{j1})$ is a maximum induced subgraph of $EH_{s,t}$. The theorem follows. $\square$

Theorem 9

The minimum wirelength of embedding $EH_{s,t}$ into grid $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$, where $1\le s\le t$ is given by

$$\begin{aligned} WL(EH_{s,t},M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })= & {} 2^{\lfloor \frac{s+t+1}{2}\rfloor -1}\left( 2^{2t}-2^{t}\right) \\&+2^{\lfloor \frac{s+t+1}{2}\rfloor }\left( 2^{2s}-2^{s}\right) +2^{s+t}. \end{aligned}$$

Proof

Let $f:V(EH_{s,t})\rightarrow V(M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil }))$ be the embedding $\pi$. Let $C_{i}=\{(\alpha _{i,j},\alpha _{i,j+1}) |1\le j\le 2^{\lceil \frac{s+t+1}{2}\rceil }\}$, $1\le i\le 2^{\lfloor \frac{s+t+1}{2}\rfloor }$. Let $H_{i1}$ and $H_{i2}$ denote two connected components of $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })-C_{i}$, where $f(G_{i1})=H_{i1}$ and $f(G_{i2})=H_{i2}$. Then, we have $EC_{f}(C_{i})=\sum ^{2^{s+t}}_{i=1}C_{i}=2^{s+t}$.

Let $R_{ij}=\{(\alpha _{i,j},\alpha _{i,j+})|1\le i\le 2^{\lfloor \frac{s+t+1}{2}\rfloor }\}$, $1\le j\le 2^{\lceil \frac{s+t+1}{2}\rceil }$. Furthermore, let $H_{j1}$ and $H_{j2}$ denote two connected components of $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }\times 2^{\lceil \frac{s+t+1}{2}\rceil })-R_{j}$, where $f(G_{j1})=H_{j1}$ and $f(G_{j2})=H_{j2}$. Obviously, each edge of $R_{i}$ has the same edge congestion. Thus, the sum of edge congestion of each column is equal. By Lemma 1, $G_{j1}$ is the inverse images of $R_{j1}$ under the embedding f. Clearly, $G_{j1}$ is a subcube induced by the vertices of $H_{j}$. By Theorem 2, it is certain that $G_{j1}$ is a maximum induced subgraph of $EH_{s,t}$. Thus, by Lemma 1, $EC_{f}(R_{j1})$ is minimum for $j= 1,2,\ldots ,2^{\lceil \frac{s+t+1}{2}\rceil }$. By Lemma 2, the sum of edge congestion of each column of $H_{i1}$ is $2^{\lceil \frac{s+t+1}{2}\rceil -1}(2^{2t}-2^{t})$.

Let $R_{ij}^{'}=\{(\alpha _{i,j},\alpha _{i,j+1})|1\le i\le 2^{\lfloor \frac{s+t+1}{2}\rfloor }\}$, $1\le j\le 2^{\lceil \frac{s+t+1}{2}\rceil }$. It is easy to verify the sum of edge congestion of each column is $2^{t}(2^{2s-1}-2^{s-1})$. By Theorem 2, $G_{j1}^{'}$ is a maximum subgraph induced by $R_{j1}^{'}$. Thus, by Lemma 2, $EC_{f}(R_{j1}^{'})$ is minimum, where $j= 1,2,\ldots ,2^{\lceil \frac{s+t+1}{2}\rceil }$. By Lemma 2, the sum of edge congestion of each row of $R_{j1}^{'}$ is $2^{\lfloor \frac{s+t+1}{2}\rfloor }(2^{2s}-2^{s})$.

By Lemma 2, the wirelength of embedding $EH_{s,t}$ into $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$ is:

$$\begin{aligned} WL\left( EH_{s,t},M\left( 2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil }\right) \right)= & {} WL_{f}\left( EH_{s,t},M\left( 2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil }\right) \right) \\= & {} \sum _{i=1}^{2^{\lceil \frac{s+t+1}{2}\rceil }}C_{i}+\sum _{j=1}^{2^{\lfloor \frac{s+t+1}{2}\rfloor }}R_{j}+ \sum _{j=1}^{2^{\lfloor \frac{s+t+1}{2}\rfloor }}R_{j}^{'}\\= & {} 2^{\lceil \frac{s+t+1}{2}\rceil -1}(2^{2t}-2^{t})\\&+2^{\lfloor \frac{s+t+1}{2}\rfloor }(2^{2s}-2^{s})+2^{s+t}. \end{aligned}$$

This completes the proof. $\square$

Let t(N) denote the running time of Algorithm 1, and $N=2^{s+t+1}$ is the number of vertices of $EH_{s,t}$. By Theorem 9, the number of edge cuts of each column is $(2^{\lceil \frac{s+t+1}{2}\rceil }-1)$, and deleting each edge cut needs one time unit and thus deleting all edge cuts takes $(2^{\lceil \frac{s+t+1}{2}\rceil }-1)$ time units. Consequently, the total time for embedding $EH_{s,t}$ into $M(2^{\lceil \frac{s+t+1}{2}\rceil }\times 2^{\lceil \frac{s+t+1}{2}\rceil })$ with minimum wirelength is $t=O(N+(2^{\lceil \frac{s+t+1}{2}\rceil }-1)-1+1)\le O(N)$, which is linear.

5 VLSI layout for $EH_{s,t}$

In this section, we propose a VLSI layout of $EH_{s,t}$ into a two-dimensional grid with minimum number of tracks. A track is a continuous horizontal or vertical line on which the wires are placed without overlapping any other wires. To build integrated $EH_{s,t}$, it is necessary to work within a few layers of two-dimensional integrated circuits.

The wires can run either horizontally or vertically along grid lines. All vertices are placed on the same linear array in a collinear layout. We use bisection width to calculate the required number of tracks. Bisection width [40] is defined as the number of links interconnecting two subgraphs having the same number of vertices. The area of a layout is defined as the area of the smallest rectangle that contains all the nodes and wires. When there are two layers of wires, it is guaranteed that we can lay out the network within the area. More precisely, it only uses one layer of wires to lay out all the horizontal segments of wires and the other layer to lay out all the vertical segments.

The first layout is to assign the vertices of $Q^{t}$ with $2^{s}$ copies in the same line. By extending the horizontal space, we can assign the vertices of $Q^{s}$ in the second layout which is adjacent to the vertices of $Q^{t}$.

Theorem 10

Let $EH_{s,t}$ be an exchanged hypercube for $1\le s\le t$. The number of tracks required for the collinear layout of $EH_{s,t}$ is given by

$$\begin{aligned} t_{\mathrm{num}}(EH_{s,t})=\left\{ \begin{aligned}&2^{t}+\lfloor \frac{2^{t}}{3}\rfloor ,&{s<t},\\&2^{s+t+1}+2^{s+t}-t\cdot 2^{s}-s\cdot 2^{t},&{s=t}.\\ \end{aligned} \right. \end{aligned}$$

Proof

All vertices are placed on the same line in a collinear layout. To describe the layout of $EH_{s,t}$, we use a bottom-up approach, starting with EH(1, 1) and inductively moving to $EH_{s,t}$ of higher dimensions. See Fig. 4. A collinear layout of EH(1, 1) can be obtained by placing the eight nodes on a linear array, connecting vertex 0 with vertex 1, vertex 2 with vertex 3, vertex 4 with vertex 6, through wires in the first track, and then connecting vertex 0 with vertex 4, and vertex 5 with vertex 7, through wires in the second track. Then, connecting vertex 1 with vertex 5, vertex 2 with vertex 6, and vertex 3 and vertex 7 in turn. Clear, this layout requires five tracks. For $1\le s\le t$, we have the following cases:

Fig. 4

Collinear layouts of $EH_{1,1}$

Fig. 5

VLSI physical design for the connection pattern of $EH_{1,2}$

Case 1.$s< t$. Let $I^{i}_{t}$ denote the subgraph induced by the vertices in $Q^{i}_{t}$ and all the vertices in $E_{1}$, $1\le i\le 2^{s}$. To obtain the collinear layout of $I^{i}_{t}$, we start with the layouts of two subgraphs $\bigcup _{i=1}^{2^{s}}I^{i}_{t}$ and $\bigcup _{i=1}^{2^{s}}I^{i+1}_{t}$. By doubling the horizontal space, we can place the ith vertex of the second layout adjacent to the ith vertex of the first layout. For the collinear layout of $Q_{s}$, the links in it could share tracks with $I^{i}_{t}$, such that it will not need extra tracks. See Fig. 5. Since $EH_{s,t}$ and $EH_{t,s}$ are isomorphic, the same holds for subgraphs $\bigcup _{i=1}^{2^{t}}I^{i}_{s}$ and $\bigcup _{i=1}^{2^{t}}I^{i+1}_{s}$. According to the result in [17], the track number of $Q_{t}$ into $L_{2^{t}}$ is $\lfloor \frac{2^{t}}{3}\rfloor$ and the required track number of $E_{1}$ is $2^{t}$. Since $EH_{s,t}$ can be decomposed into $2^{s-1}$ copies $Q^{i}_{t}$, the total number of tracks for collinear layout of $EH_{s,t}$ is $t_{num}(EH_{s,t})=2^{t}+\lfloor \frac{2^{t}}{3}\rfloor$.

Case 2.$s=t$. Since $EH_{s,t}$ is Hamiltonian [29], we can construct a hamiltonian path in $EH_{s,t}$, and let this path be a base track. By Definition 3, from the center of the base track, $EH_{s,t}$ can be divided into two subcubes $EH_{s-1,t}$ with $2^{s+t}$ vertices. Then, the bisection width of the first partition is $2^{s+t}$. After deleting the edge set $E_{1}$ from $EH_{s,t}$, the vertex set of $EH_{s,t}$ is separated into two parts T and S, where T is the set of all vertices with rightmost 0th bit being 1, and S is the set of all vertices with rightmost 0th bit being 0. Thus, the vertex set S is decomposed into $2^{t}$ connected components. Each component is an s-dimensional hypercube $Q_{s}$; moreover, these $2^{t}$ hypercubes $Q^{s}$ are pairwise disjoint, and there are no edges joining any two $Q_{s}$. For $2^{s}$ copies $Q_{t}$, we continue to divide each subcube into two equal sub-subcubes with $2^{t-1}$ vertices, and the bisection width of this division is $2^{t-2}$. Repeat this division t times. Then, the number of tracks is given by $t(Q_{t})=\sum _{i=1}^{2^{t}}b_{i}-1$. The same holds for $2^{t}$ copies $Q_{s}$, which denoted as $t(Q_{s})=\sum _{j=1}^{2^{s}}b_{j}-1$. Thus, the required number of tracks for $EH_{s,t}$ can be obtained by summing the bisection width in each procedure. Based on the above division, it can be obtained as follows: It needs one track for constructing the Hamiltonian path. Then, the first bisection needs $2^{s+t}$ tracks, the second bisection needs $2^{t-1}$(resp. $2^{s-1}$) tracks,..., the $(n-1)$th bisection needs $2\cdot 2^{1}-1$ tracks, and the nth bisection needs $2^{1}-1$ tracks.

Thus, the required number of tracks is,

$$\begin{aligned} t_\mathrm{num}= & {} 1+2^{s+t}-1+2^{s}\left( \sum _{i=1}^{2^{t}}b_{i}-1\right) +2^{t}\left( \sum _{j=1}^{2^{s}}b_{j}-1\right) \\= & {} 2^{s+t}+2^{s}\left( \sum _{i=1}^{2^{t}}2^{i-1}-1\right) +2^{t}\left( \sum _{j=1}^{2^{s}}2^{j-1}-1\right) \\= & {} 2^{s+t}+\left( 2^{s+t}\right) -t\cdot 2^{s}+\left( 2^{s+t}-s\cdot 2^{t}\right) \\= & {} 2^{s+t+1}+2^{s+t}-t\cdot 2^{s}-s\cdot 2^{t}. \end{aligned}$$

$\square$

Fig. 6

A 2-D layout of $EH_{1,2}$

Theorem 11

Let $EH_{s,t}$ be an exchanged hypercube for $1\le s\le t$ and A denote the VLSI layout area for $EH_{s,t}$. Then,

$$\begin{aligned} A=\left\{ \begin{aligned}&2^{\lfloor \frac{s+t}{2}\rfloor +\lceil \frac{s+t+1}{2}\rceil }\left( \lfloor \frac{2^{t+1}}{3}\rfloor +\lfloor \frac{2^{s+1}}{3}\rfloor \right) \left( \lfloor \frac{2^{s+1}}{3}\rfloor +1\right) ,&{s<t},\\&2^{\lceil \frac{s+t+1}{2}\rceil + \lfloor \frac{s+t+1}{2}\rfloor }\left( \lfloor \frac{2^{t+1}}{3}\rfloor +\lfloor \frac{2^{s+1}}{3}\rfloor \right) ,&{s=t}.\\ \end{aligned} \right. \end{aligned}$$

Proof

Let $f=lex$. The layout $EH_{s,t}$ on a two-dimensional grid is performed by Algorithm 2. We use W and H to denote the numbers of vertical and horizontal tracks, respectively, i.e., the width and the height of a layout. See Fig. 6. Let $C_{ij}=\{(\alpha _{i,j},\alpha _{i,j+1})|1\le j\le 2^{\lfloor \frac{s+t+1}{2}\rfloor }\}$ and $R_{ij}=\{(\alpha _{i,j},\alpha _{i+1,j})|1\le i\le 2^{\lceil \frac{s+t+1}{2}\rceil }\}$, where $1\le i\le 2^{\lceil \frac{s+t+1}{2}\rceil }$ and $1\le j\le 2^{\lfloor \frac{s+t+1}{2}\rfloor }$. Clearly, $R_{ij}$ is an edge cut of each column in the grid $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$ such that $R_{i}$ disconnects $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$ into two components $R_{1}$ and $R_{2}$ where $V(R_{1})=\{0,1,\ldots ,2^{s+t}\}$ and $V(R_{2})=\{2^{s+t}+1,2^{s+t}+2,\ldots ,2^{s+t+1}\}$. We have the following two cases to allocate the vertices on a grid.

Case 1.$s<t$. Let $C_{ij}$ be an edge cut of each column in the grid $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$ such that $C_{ij}$ disconnects $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$ into two components $C_{i1}$ and $C_{i2}$, $i= 1, 2,\ldots ,2^{\lceil \frac{s+t+1}{2}\rceil }-1$. Let each row in $C_{i1}$ be the image of $Q_{t}$. By Lemma 1, $EC_{f}(R_{1})$ is minimum. Thus, the required number of tracks for each row in $C_{i1}$ is $\lfloor \frac{2^{t+1}}{3}\rfloor$. So the area for rows is $H=(\lfloor \frac{2^{t+1}}{3}\rfloor +\lfloor \frac{2^{s+1}}{3}\rfloor )2^{\lfloor \frac{s+t}{2}\rfloor }$. The same holds for columns of $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$. The required number of tracks for each column is $\lfloor \frac{2^{s+1}}{3}\rfloor +1$. Thus, the area for columns is $W=2^{\lceil \frac{s+t+1}{2}\rceil }(\lfloor \frac{2^{s+1}}{3}\rfloor +1)$. Hence, the whole area of the grid is $W\times H=2^{\lfloor \frac{s+t}{2}\rfloor +\lceil \frac{s+t+1}{2}\rceil }(\lfloor \frac{2^{t+1}}{3}\rfloor +\lfloor \frac{2^{s+1}}{3}\rfloor )(\lfloor \frac{2^{s+1}}{3}\rfloor +1)$.

Case 2.$s=t$. Let $R_{ij}$ be an edge cut of each row in the grid $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$ such that $R_{ij}$ disconnects $M(2^{\lfloor \frac{s+t+1}{2}\rfloor }, 2^{\lceil \frac{s+t+1}{2}\rceil })$ into two components $R_{j1}$ and $R_{j2}$, $j = 1, 2, \ldots ,2^{\lfloor \frac{s+t+1}{2}\rfloor }-1$. The sum of edge congestion of each column in $R_{j1}$(resp. $R_{j2}$) is equal. Let each row in $R_{j1}$(resp. $R_{j2}$) be the image of $Q_{t}$(resp. $Q_{s}$). By Lemma 1, $EC_{f}(R_{j1})$(resp. $R_{j2}$) is minimum. Thus, the required number of tracks for each row in $R_{j1}$ is $\lfloor \frac{2^{t+1}}{3}\rfloor$ and for each row in $R_{j2}$ is $\lfloor \frac{2^{s+1}}{3}\rfloor$. So the area for rows is $H=(\lfloor \frac{2^{t+1}}{3}\rfloor +\lfloor \frac{2^{s+1}}{3}\rfloor )2^{\lfloor \frac{s+t+1}{2}\rfloor }$. Thus, the area for columns is $W=2^{\lceil \frac{s+t+1}{2}\rceil }$. Hence, the required whole area for the grid is $W\times H=2^{\lceil \frac{s+t+1}{2}\rceil + \lfloor \frac{s+t+1}{2}\rfloor }(\lfloor \frac{2^{t+1}}{3}\rfloor +\lfloor \frac{2^{s+1}}{3}\rfloor )$. $\square$

6 Simulation and experiments

We have carried out experimental testing to verify that the proposed embedding performs better than another two embeddings. And we use a server with Nvidia GTX 1060 GPU, Intel Xeon E5-2670 as our experimental platform, the Intel processor with 16 processors running at 3.3 GHz. This server has 3 TB disk, 64GB physical memory and runs on Windows Server 2008 R2 Enterprise operating system.

Network overhead is the most crucial factor to measure an interconnection network. Network overhead is the usage rate parameter volume for different resources, and the definition is as follows:

$$\begin{aligned} \mathrm{volume}=\frac{1}{1-\mathrm{mem}}*\frac{1}{1-\mathrm{cpu}}*\frac{1}{1-\mathrm{net}}. \end{aligned}$$

In the formula, mem represents the memory utilization rate of the server, cpu indicates the utilization rate of CPU and net represents the bandwidth utilization ratio.

With the increment of the interconnection network scale, the delay of message passing seriously affects the communication efficiency between nodes. Particularly the redundant search messages will increase in an exponential way, which would seriously influence the efficiency of the interconnection network search schemes. Congestion and dilation directly affect the queuing delay of messages and communication delay in the embedding process. In the process of executing the algorithms, we monitor the status of server with Ganglia [41]. We analyze the algorithm’s network overhead by monitoring the usage state of resources.

Fig. 7

Network overhead of three embedding schemes

We compare our lex embedding algorithm with natural embedding [42] and random embedding [43], respectively. The natural embedding (short for natural)is a bijection $f: \{1,\ldots , n\} \rightarrow \{1, \ldots , n\}$ such that the natural numberings of vertices increase one by one, and the random embedding (short for random) is the bijection $f: \{1,\ldots , n\} \rightarrow \{1, \ldots , n\}$ is random.

Figure 7 illustrates the network overhead of three embedding schemes. When the number of nodes is less than 32, the overhead of the three algorithms is relatively close. As the number of nodes increases, the random overhead becomes larger than the other two algorithms. Due to the random mapping of nodes, the congestion and dilation of some links become quite large. This will increase the communication overhead.

Fig. 8

Comparison of three embedding schemes

As shown in Fig. 8, the lex embedding induces the lower wirelength compared with the other two embeddings. As the number of nodes increases, lex embedding has better performance than natural embedding.

Experimental results show that natural embedding is more suitable for regular networks, such as hypercube. With the increase in network size, the sum of the edge congestion would keep a uniform increase. However, natural embedding is not suitable for exchange hypercube. Due to its irregularity, it will cause local congestion and eventually lead to layout failure. Obviously, random embedding is the worst embedding because of the maximum wirelength required. That is mainly due to the randomness of the mapping. It not only requires a large wirelength, but also causes massive network overhead.

7 Conclusions

In this paper, we propose embeddings of exchanged hypercube into a grid. Firstly, we prove that exchanged hypercube can be embedded into a linear array with minimum wirelength and obtain the exact wirelength. Furthermore, we obtain the minimum wirelength of embedding exchanged hypercube into a grid and prove that the embedding algorithm is linear. Finally, we extend the embedding of exchanged hypercube into a grid with efficient VLSI layout area. To the best of our knowledge, this is the first result for layout exchanged hypercube into a grid.