The Xor embedding: An embedding of hypercubes onto rings and toruses

The Xor Embedding: An Embedding of Hypercubes onto Rings and Toruses Antonio Gondez and Miguel Valero-Garcia Universitat Polit&cnica de Catalunya Departament d' Arquitectura de Computadors c/ Gran Capitan dn, Campus Nod - Edifici D6 BO8071 Barcelona (Spain) E-mail: (antonio,miguel} 9ac.upc.e~ Abstract Many parallel algorithms use hypercubes as the communication topology anwngprocesses, which make them suitable to be executed on a hypercube multicomputer. In this way the communication cost is kept minimum since processes can be allocated to processors in such a way that only communication between neighbor processors is required. However, the scalability of hypercube multicomputer is constrained by the fact that the interconnection cost per node increases with the total number of nodes. From the point of view of scalability, meshes and toruses are a more interesting class of interconnection topologies. In this paper we propose an embedding of hypercubes onto tomes of any given dimension, including one-dimensional tomes which are also called rings. We also prove that this embedding is optimal in the sense that it minimizes the execution time on a ring of a class ofparallel algorithms frequently found in real applications, such as FFT and some class of sorting algorithms. 1. Introduction Many parallel algorithms use hypercubes as the communication topology among processes. Some examples include parallel algorithms for FIT, sorts, etc. [Z]. We will call these algorithms hypercube algorithms or d-cube algorithms. where d is the number of dimensions of the hypercube. A hypercube algorithm of dimension d or d-cube algorithm, consists of 2d processes labeled from 0 to 9-1 such that every process communicates only with its d neighbors, one in each dimension of the d-cube. In this paper we consider the problem of executing d-cube algorithms on multicomputers [l I. A multicomputer is a distributed memory multiprocessor in which the nodes (processor + local memory) are interconnected through point to point links. The nodes of a multicomputer are interconnected according to a given pattem or interconnection topology. If this topology is a hypercube of dimension d (d-cube multicomputer) then the d-cube algorithm can be executed on the multicomputer in such a way that neighbor processes are mapped onto adjacent nodes (nodes directly connected through a point to point link). We say, in this Case. that each process of the d-cube algorithm has all its d neighbors at distance I in the multicomputer (i.e., all required communication is between neighbor nodes). In this way, the cost of the communication component of the d-cube algorithm when it is executed on a hypercube multicomputer is kept minimum. 0-8186-3492-8193 $3.00 0 1993 IEEE 15 16 International Conference on Application-Specific Array kessors An important drawback of hypercube as interconnection topology for multlcomputen is that it is not scalable. In a dabe multicomputer each of the r' mdes is directly COMto other d nodes through point to point links. 'Iherefore, the. cost (and the complexity) of the interconnection hardware per node increases with the numbex of nodes. 0interconnection topologies, such as meshes or tomes are considered more suitable for multicomputers with a large number of nodes, since the interconnectiOn cost per node does not depend on the total number of nodes. As an example, each node of il two-dimensional torus multicomputer is directly co~ected to 4 nodes. it does not matter the number of nodes of the multicomputer. When a dabe algorithm is executed on a multicomputer with a topology otfier than hypercube it is not possible, in general. to allocate processes to nodes in such a way that every process has its d neighbors at distance 1 in the multicomputer. As an example. in a two-dimensional tom multicomputer. every process has at most 4 of its d neighbors at distance 1. It must have at least d-4 neighbors at a distance greater than 1. A message to any of these "far" neighbors must be routed through the point to point links and mdes which are found along the path to the destination node. A good mapping of a d-cube algorithm onto a multicomputer will try to keep the neighbor processes as close as possible in the multicomputer, minimizing in this way the cost of the communication component of the d-cube algorithm when it is executed on the multicomputer. In this papex we propose an embedding of d-cube algorithms onto torus multicomputers of any arbitrary dimension. This embedding has the following proees: a) For each dimension of the d-cube, every process has its corresponding neighbor at the same distance (although these distances may be different for different dimensions). b) The average distance of the d neighbors of any process is minimum, subject to (a). As it will be shown later in this paper, prom (a) is desirable for some kind of d-cube algorithms like m, since it guarantees that any process will never have to wait for a neighbor to finish its work before starting the interchange of data with it. ROW (b) implies a minimum cost in the communication component of the d-cube algorithm, and therefore, a minimum execution time. We present a proof of this property for rings (onedimensional to~~e~). The generalization of the proof for an arbitrary dimension is still under development This papa is organized as follows. In section 2 we introduce some notation and describe more precisely the contribution of this paper as well as some related work. Sections 3 presents the proposed embedding of dab onto rings. In sendion 4. the embedding is generalized to tomes of any arbitrary dimension. In section 5 we prove that the proposed embedding for rings is optimal according to the criterion introduced in section 2. Finally, we present some concluding remarks. 2. Preliminaries and related work 2.1. Definitions A d-cube algorirhm is a parallel algorithm that consists of 2d processes such that every process communicates with exactly other d processes. Tkse d processes are called its neighbors. We also say that the communication topolo of the algorithm is a hypercube. lhat means that the 2d communicate) if the binary codes for n and m differ in a single bit. If this bit is the i-th bit then m is the neighbor of n in dimemion i, and n is the neighbor of m in the same dimension Then, we write: m = Ndn) n = Ndm) processes can be labeled from 0 to Y -1 in such a way that processes n andm are neighbor (i.e. they Session 2: Efficient Design Methods I 17 In this paper we focus on d-cube algorithms in which every process has the tollowing structure: do i=O,d-1 compute communicate with neighbor in dimension i enddo In this algorithm every process consists of d stages, each of them composed of a computation and a communication phase. In each stage, every process uses a different dimension to exchange information with one of its neighbors. We assume that the duration of the compute phase and the amount of information to be exchanged is the same for all the stages and all the processes of the d-cube algorithm. A d-cube algorithm with the above features will be called a compute-and-communicate d-cube algorithm, or a CC d-cube algorithm for short. 'Ihis kind of d-cube algorithms are common in real applications like FIT, some type of sorts, etc. Any parallel algorithm can be modelled as a graph. The vertices of the graph represent the processes of the algorithm and the edges of the graph represent the neighbor relationship among processes. A multicomputer can also be modelled by a graph. The vertices of the graph represeni the nodes of the multicomputer and the edges of the graph represent the point to point links which interconnect these nodes. Multicomputers can be classified according to their interconnection topology. In this paper, we are interested in mesh and toms multicomputets, since they have scalable interconnection topologies. A (kl,k2, ..., kc) c-dimensional tom is an undirected graph in which the nodes can be labeled as c-tuples (i1,iB ..., ic), 0 ij < ki. Every node (i& ,.... ic)of the graph has two neighbors in each dimension of the toms. Its left neighbor in dimension j is (il ,...,($- 1) mod k, ..., ic) and its right neighbor in this dimension is (il, ..., ($+l) mod k, ..., ic). A (k&, ..., k,) c-dimensional mesh is an undirected graph in which the nodes can be labeled as c-tuples (i1.i~. .... i,), 0 I ij e kk Every node of the graph has two neighbors in each dimension] of the mesh if 0 < 4 < k,-1. Its left neighbor is (il ...., 5-1 ,..., ic) and its right neighbor is (il, ..., $+l ,..., i,). If $=O. the node has only a right neighbor and if $=k+ then it only has a left neighbor. A line is a one-dimensional mesh while a one-dimensional torus is called a ring. Figure 1 shows some examples and illustrates how their nodes are labeled. The distance in a graph between two vertices is the minimum number of edges that join those vertices. In the particular case of the graph which models a d-cube, the distance between two vertices is known as the Hamming distance (number of different bits in their binary representations). An embedding of graph G into graph H is a bijective function f from the vertices of G to the vertices of H. We assume that G and H have the same number of vertices. The problem of executing a CC d-cube algorithm on a multicomputer can be modelled as the embedding 0-f graph G, which represents the CC d-cube algorithm, onto graph H, which represents the multicomputer. The dilation of an edge (n,m) of G (edge joining vertices n and m) is the distance in H between .tW andJ7m). If G models a CC d-cube algorithm, an edge exists between vertices n and m if m=Nin), for some i E [O,d-I]. The dilation of this edge will be denoted by Din). Obviously, since n= Nim), Din) = Dim). When a CC d-cube algorithm is executed on a multicomputer, as defined by a given 18 International Co&rence on Application-Specific Array heeors (4 (dl d) (4.4) torus.The pictun also show0 hoaw tho nod.. am labeld. Figure 1: Different types of multicomputers: a) line, b) ring, c) (44) mssh and embedding f; a communication between processes n and Nkn) (required in iteration i of the CC d-cube algorithm) is implemented by a message which is routed through Di(n) point to point links and D.W-1 nodes of the multicomputer represented by H, which are found in the shortest path between nodesfln) andflNkn)). We denote by To the duration of the arithmetic computation phase in every stage of the CC d-cube algorithm, when it is executed on the target multicomputer. We denote by Tc the cost of sending a message through a point to point link on the multicomputer. The time to execute a CC d-cube algorithm on a multicomputer with 9 nodes, as defined by embeddingfcan be expressed as: Tf = dTa + Tcf where Tcfis the cost of the communication component of the CC d-cube algorithm. Tcr can be exprkgsed as follows: Tg = nuu (Td-I(n): n=0..2%) Tiin) =D,in) Tc + nuu (Ti-dn), Ti.l(Nkn)) I i"&) = 0 (a) (b) In the above expressions, Tin) is the cost of the communication component for process n &om the beginning of the execution to the end of stage i. Expression (a) indicates that Tgis equal to the highest communication component cost of any process at the end of the d stages of the CC d-cube algorithm. Expression (b) gives the communication component cost for process n at the end of stage i. In this stage process n must exchange information with its neighbor Nin). ?he cost of exchanging this information is Di(n)T, However, this exchange caauot start until both procaws n and Ni(n) are ready to do it. In general, either process n or process Ndn) will have to wait for its neighbor to arrive to the point in which communication can be started. lMs is why the term "max" appears in expsion (b). In the following, we call those idle periods as waiting periods. Obviously, if the multicomputer has a d-cube intercoIlnection topology then the best embedding isfln) = n (identity embedding). In this case Din) = I (for every i and n) and the execution time is T, = d(Ta+T,) Session 2 Efficient Design Me&& I 19 2.2. Contributions In this paper. we are interested in those embeddings in which Dkn) = Di (i E [O,d-I] and n E [O,2d-I]). This means that every process has its neighbor in dimension i at the same distance in @e target multicomputer. In the following, an embedding with this feature is called embedding with constunt distances and the values of Di (i E [O,d-I]) are called the disrunces of the embedding. Embeddings with constant distances have the property that eveay process takes the same time to communicate in any given stage of the CC d-cube algorithm. Because the duration of the compute phase is also the same for every process, waiting periods are avoided since neighbor processes arrive at the same time to the point at which they have to communicate. The time to execute a CC d-cube algorithm onto a multicomputer. as defined by an embedding with constant distances f is: d1 d1 T, = x (Ta+DiTc) = dTa+TcxDi = d(T,+TcDa) i=O i=O where Dais the average distance of the embedding: d1 XDi = averagedistance (f~ 0, - i=O d Therefore. the embedding with constant distances which minimizes Tfis that whose average distance D, is minimum. An embedding with such property is said to be optimal. As it was mentioned in the introduction, we are interested in executing CC d-cube algorithms on scalable multicomputers. In particular. we are interested in tom multicomputers since for meshes a well-known embedding. described in the next section, is optimal for CC d-cube algorithms. In this paper we propose an embedding with constant distances of CC d-cube algorithms onto tom multicomputers of any arbitrary dimension. Moreover, we prove that the proposed embedding with constant distances is optimal for rings (onedimensional tow). Another additional property of the proposed embedding is its simplicity, which means a negligible cost to compute the location of any process in the multicomputer. 2.3. Relatedwork The problem of embedding d-cubes onto meshes and toruses has been previously considered by othex authors. We mw review some related work. Matic presents in [7] a study of the standard embedding (defined below) of d-cubes onto two-dimensional meshes and toruses. To define the standard embedding (which will be denoted by f$ of a d-cube onto a line or a ring. the nodes of the target multicomputer are numbered from 0 to -I (see figures 1.a and 1.b). Then, the standard embedding is defined by (see figure 2.a): f,,d(n) = ?I nte standard embedding of a d-cube onto a (kl,k =....kc) cdimensional mesh or tom is defined as follows: fs,d(") = (PI*Pt, ...,Pc) 20 International Conference on Application-Specific Array Processors 0123 e------* 12 13 14 01 234561 (a) (b) Figure 2: Standard embeddings ot: a) a 3-conto a line or a ring and b) a kube onto a (4,4) mesh or torus. Each label indkates whkh vertex of the dcube is mapped onto each node of the multicomputer. Wraparound links are not shown for clarity. where: i1 p, = (n modfikj)divnkj Figure 2.b shows an example in which c=2 and kl=k2=4. Obviousl the standard embedding is a constant distance embedding. For the particular case in which ki=g‘, i E[~,c]. the distances of the standard embedding are: j=1 j=l Q = 2 i ie[O, d - I] It can be shown that the standard embedding is optlmal for meshes. in the sense that it minimizes the average distance [3],[8]. However, it is not optimal for toruses, as it will be shown later in this Paper. Harper in [41 and Lai and Spague in [5] solve the problem of embedding d-cubes onto meshes to minimize the dilation of the embedding (the maximum dilation of any edge). Both proposals use the byweight embedding, denoted byfh, which is not an embedding with constant distances. Next, we describe briefly this embedding. In the case of a line, the labels of the vertices which represent the processes of the d-cube algorithm are ordered by their weights. The weight of a label is the number of I’s in its binary representation. Labels with the same weight are ordered in descending order. Then, the processes of the d-cube ordered in that way are allocated to the nodes of the line, from left to right. Figure 3.a shows an example. The byweight embedding can be extended to meshes of any dimension. In particular, Lai and Spague extend this embedding to two-dimensional meshes in [5]. Figure 3.b shows an example. The byweight embedding minimizes the dilation of the embedding. ?his is an interesting property in some particular applications of embeddings. For instance, Lai and Spague propose this embedding to solve the problem of placing the processors of a hypercube on a printed circuit board or a chip (which can be modelled as a two-dimensional mesh). However, the byweight embedding is not an embedding with constant distances, which is an important property in the context of executing CC d-cube algorithms onto multicomputers. ’Iherefore, during the execution of the CC d-cube algorithm, waiting periods will appu which contribute to increase the execution time. To illustrate this fact, figure4 shows an example in which the execution times of a CC 3-cube algorithm Session 2: Efficient Design Methods I 21 OOO 100 010 001 110 101 011 111 (a) Figure 3 Byweight embeddings of: a) a 3-cube onto a line and b) a Scube onto a (8,4) mesh. on a line for both the standard embedding and the byweight embedding are compared. The waiting periods which contribute to make the byweight embedding run slower than the standard embedding are also shown. In [6], Y .W. Ma and L. Tao proposed several embeddings among toruses and meshes of different dimensions. Their proposals are based on generalizing the concepts of gray code for radix-2 numbering system to mix-radix numbering systems. Since a d-cube can also be seen as a d-dimensional mesh or torus with two elements in each dimension. lkir embedding can also be applied to solve the problem addressed in this paper. However, they focus on minimizing the dilation (the largest distance between any two neighbors of the d-cube) and therefore the resulting embeddings in general do not have constant distances, which is a desirable property for our objective. However, if one starts with a d-cube represented by means of a (2.2, ... 2) d-dimensional mesh or torus, then the resulting embedding onto a ring or a two-dimensional torus has constant distances. Nevertheless, its average distance and therefore its pexfonnance for executing our target algorithm is worse than the embedding proposed in this paper. 3. We describe now the proposed embedding with constant distances of a d-cube onto a ring with Zd vertices (we assumed > I). We call this embedding xor embedding and it is denoted byf,, The xor embedding is optimal, in the sense that it minimizes the average distance. The xor embedding is described next. Section 5 presents a proof of its optimality. Let G be the graph which represents the CC d-cube algorithm and R be the graph which re esents the ring multicomputer. Assume that the vertices of R are labeled from 0 to 2 -1clockwise (see figure 1.b). Let (nd-1, nd.2 ...,nl, no) be the label (in binary code) of vertex n in G. This vertex is mapped onto vertex m=f,,(n) in R, whose label in binary code (md+..,ma) is: An embedding with constant distances for rings F mi = ni i E [O, d-11, i # d-2 md.2 = XOR (nd.19 nd.3 where XOR (qb) is the exclusive-or of bits a and b. Figure 5 shows an example for d=4. The distances of the xor embedding are: Di = 2' i E [O, d-21 Dd-1 = 2d-2 22 International Conference on Application-Specific Array Processors 124 332 124 422 124 431 124 431 124 422 124 332 124 321 Computation Communication Waitingperiod fbw (b) (C) Figure 4 a) Dilations for the standard and byweight embeddings (M). Executing a CC 3-cube algorithm on a line using: b) the standard embudding and c) the byweight embedding. merefore, the average distance is: d-2 4. An embedding with constant distances for c-dimensional toruses Now we describe the xor embedding of a d-dimensional hypercube onto a (2d',2d2,...,2d3 c-dimensional torus such that dl+d2+ ...+ d,=d. Given a positive integer x, let diJ denote the ith bit of the binary representation of x. The least significant bit is considered to be the 0th bit. We also define Kjin the following way. K1=0, and for every I<jG+l we have that: j1 Kj = di i= 1 Session 2: Efficient Design Methods I 0 1 2 3 4 5 6 7 121314 15 8 9 10 11 11111111111 - 23 Figure 5: A xor embedding of a 4-cube onto a ring. The labels indicate which node of the dcube is mapped onto the corresponding node of the ring. Let G be the graph which represents the d-cube and T be the graph which represents the torus. men, vertex n of G is mapped onto vettex (mpa ...,mc)=fm in) in T as follows: mJ{i) = n(i+Kj) mJ{dj - 2) = XOR (n(Kj+lI), n(Kj+, - 2)) i E 10, dj - I], i f dj - 2 For the particular case of a (2dc, ..., 99 c-dimensional torus, the distances corresponding to this embedding are: Di = zd/c-2 D. = $m~ddc otherwise if i = 1 (ac) - I, 0 e 1 5 c and the average distance is: d/c-2 . 2dIC-2 [ -k r=O 2’) - - c(2d/c-2+2d/c-11) d d D, = Figure 6 shows an example for d=6. Note the simplicity of functionf’Jn). ?his function, which is used very frequently for routing messages during the execution of the CC d-cube algorithm, consists of simple bit operations and its computational cost is negligible. 5. Proof of optimality off,,, for rings Our criterion to measure the goodness of any embedding with constant distances is its average distance as defined in section 2, since minimizing the average distance implies minimizing the execution time of CC d-cube algorithms. In this section we prove that the xor embedding has the minimum average distance for emwngs with constant distances of hypercubes onto rings. To show that the xor embedding is optimal for rings, we will prove that the average distance of any embedding with constant distances is higher than or equal to the average distance of theh, embedding. This is stated by theorem 10. Before this theorem we present several lemmas and corollaries that are needed to prove that result First we find a lower bound for the sum of any set of d-ldistances corresponding to any embedding with constant distances. men, we find a lower bound for the highest distance of the embedding. Both together give a lower bound for the average distance of any embedding with constant distances. This lower bound is the average distance of the fmr embedding, which proves its optimality. Definition: Given any node of a hypercube, we define Ndn). where D is any subset of dimensions of the hypercube, as the node that we reach if we start at node n and we move through every dimension in D, one after another, using each dimension exactly once (as we know, the order in which the dimensions are used does not matter, the result will be the same). For instance, if D=[l,3), then Ndn) = N3(Nl(n)) = NI(N3(n)).