Narrow Results

A key issue in performing tree structured parallel computations is to distribute process components of a parallel program over processors in a parallel computer at run time such that both the maximum load and dilation are minimized. The main contribution of this paper is the application of recurrence relations in studying the performance of a dynamic tree embedding algorithm in hypercubes. We develop recurrence relations that characterize the expected load in randomized tree embeddings where, a tree grows by letting its nodes to take random walks of short distance. By using these recurrence relations, we are able to calculate the expected load on each processor. Therefore, for constant dilation embeddings, we are able to evaluate expected loads numerically and analytically. The applicability of recurrence relations is due to the recursive structure of trees and the fact that embeddings of the subtrees of a process node are independent of each other. Our methodology does not depend on the hypercube topology. Hence, it can be applied to studying dynamic tree growing in other networks.

In this paper we show the power of sampling techniques in designing efficient distributed algorithms. In particular, we apply sampling techniques in the design of selection algorithms on the hypercube and de Bruijn networks, and show that the message complexity of selecting an item from a set (file) is less sensitive to the cardinality of the set (file). Given a file with n keys, our algorithm performs a selection on a p-node de Bruijn network or hypercube using only O(p loglog n) messages and suffering a delay of O(τ log p loglog n), with high probability. Our selection scheme outperforms the existing approaches in terms of both message complexity and communication delay. Because of the lesser sensitivity of message complexity and communication delay of our algorithms to the file size, our distributed selection schemes are very attractive in applications where very large database systems are involved. Using our selection algorithms, we also show that both quicksort-based sorting scheme and enumeration sorting scheme can be developed for sorting large distributed files on the hypercube and de Bruijn networks. Both of our sorting algorithms outperform the existing distributed sorting schemes in terms of both message complexity and communication delay.

We study hierarchical configuration of distributed systems for achieving optimized system performance. A distributed system consists of a collection of local processes which are distributed over a network of processors, and work in a cooperative manner to fulfill various tasks. A hierarchical approach is to group and organize the distributed processes into a logical hierarchy of multiple levels, so as to coordinate the local computation/control activities to improve the overall system performance. It has been proposed as an effective way to solve various problems in distributed computing, such as distributed monitoring, resource scheduling, and network routing. The optimization problem considered in this paper is concerned with finding an optimal hierarchical partition of the processors, so that the total traffic flow over the network is minimized. The problem in its general form has been known to be NP-hard. Therefore, we just focus on distributed computing jobs which require collecting and processing information from all processors. By limiting levels of the hierarchy to two, we will establish the analytically optimal hierarchical configurations for two popular interconnection networks: mesh and hypercube. Based on analytical results, partitioning algorithms are proposed to achieve minimal communication cost (network traffic flow). We will also present and discuss heuristic algorithms for multiple-level hierarchical partitions.

Fault tolerance is an important issue in interconnection networks, and the traditional edge connectivity is an important measure to evaluate the robustness of an interconnection network. The component edge connectivity is a generalization of the traditional edge connectivity. The $g$-component edge connectivity $c{\lambda }_g(G)$ of a non-complete graph $G$ is the minimum number of edges whose deletion results in a graph with at least $g$ components. Let $g$ be an integer and $g={\sum }_{i=0}^s{2}^{t_i}$ be the decomposition of $g$ such that $t_0=[{\mathrm{\text{log}}}_{2}g],$ and $t_i=[{\mathrm{\text{log}}}_2(g-{\sum }_{r=0}^{i-1}{2}^{t_r})]$ for $i\ge 1$. In this note, we determine the $g$-component edge connectivity of the hypercube $Q_n$, $c{\lambda }_g(Q_n)=ng-({\sum }_{i=0}^s{t}_i{2}^{t_i-1}+{\sum }_{i=0}^{s}i\cdot 2^{t_i})$ for $g\le 2^{[\frac{n}{2}]}+1,n\ge 7$. Moreover, we classify the corresponding optimal solutions.

Hypercubes and Fibonacci cubes are classical models for interconnection networks with interesting graph theoretic properties. We consider $k$-Fibonacci cubes, which we obtain as subgraphs of Fibonacci cubes by eliminating certain edges during the fundamental recursion phase of their construction. These graphs have the same number of vertices as Fibonacci cubes, but their edge sets are determined by a parameter $k$. We obtain properties of $k$-Fibonacci cubes including the number of edges, the average degree of a vertex, the degree sequence and the number of hypercubes they contain.

In this paper, we study the fault-tolerant capability of hypercubes with respect to the hamiltonian property based on the concept of forbidden faulty sets. We show, with the assumption that each vertex is incident with at least three fault-free edges, that an $n$-dimensional hypercube contains a fault-free hamiltonian cycle, even if there are up to $(4n-13)$ edge faults. Moreover, we give an example to show that the result is optimal with respect to the number of edge faults tolerated.

Large scale multiprocessor systems or multicomputer systems, taking interconnection networks as underlying topologies, have been widely used in the big data era. Fault tolerance is becoming an essential attribute in multiprocessor systems as the number of processors is getting larger. A connected graph $G$ is called strong Menger (edge) connected if, for any two distinct vertices $u$ and $v$, there are $min\{d_G(u),d_G(v)\}$ vertex (edge)-disjoint paths between them. Exchanged hypercube $EH(s,t)$, as a variant of hypercube $Q_n$, remains lots of preferable fault tolerant properties of hypercube. In this paper, we show that $Q_n-Q_k$$(1\le k\le n-1)$ and $EH(s,t)-Q_k$$(2\le k\le min\{s,t\})$ are strong Menger (edge) connected, respectively. Moreover, as a by-product, for dual cube $D_n=EH(n-1,n-1)$, one popular generalization of hypercube, $D_n-Q_k$ is also showed to be strong Menger (edge) connected, where $1\le k\le n-1,n\ge 3$.

We introduce alternate Lucas cubes, a new family of graphs designed as an alternative for the well known Lucas cubes. These interconnection networks are subgraphs of Fibonacci cubes and have a useful fundamental decomposition similar to the one for Fibonacci cubes. The vertices of alternate Lucas cubes are constructed from binary strings that are encodings of Lucas representation of integers. As well as ordinary hypercubes, Fibonacci cubes and Lucas cubes, alternate Lucas cubes have several interesting structural and enumerative properties. In this paper we study some of these properties. Specifically, we give the fundamental decomposition giving the recursive structure, determine the number of edges, number of vertices by weight, the distribution of the degrees; as well as the properties of induced hypercubes, $q$-cube polynomials and maximal hypercube polynomials. We also obtain the irregularity polynomials of this family of graphs, determine the conditions for Hamiltonicity, and calculate metric properties such as the radius, diameter, and the center.

This paper analyses how the symmetry of a processor network influences the existence of a solution for the network orientation problem. The orientation of hypercubes and tori is the problem of assigning labels to each link of each processor, in such a way that a sense of direction is given to the network. In this paper the problem of network orientation for these two topologies is studied under the assumption that the network contains a single leader, under the assumption that the processors possess unique identities, and under the assumption that the network is anonymous. The distinction between these three models is considered fundamental in distributed computing.

It is shown that orientations can be computed by deterministic algorithms only when either a leader or unique identities are available. Orientations can be computed for anonymous networks by randomized algorithms, but only when the number of processors is known. When the number of processors is not known, even randomized algorithms cannot compute orientations for anonymous processor networks.

Lower bounds on the message complexity of orientation and algorithms achieving these bounds are given.

The hypercube as a parallel interconnection network has been of academic and engineering concern for tens of year due to its many merits. However, its increasing node degree is an obvious weakness. Some networks such as the cube-connected cycles (CCC) and the de Bruijn network have been proposed to overcome the increasing degree of the hypercube. In this paper, we present a new cost-effective network which outperforms the cube network. It can overcome the increasing degree of cube networks while keeping the advantages of the cube network such as logarithmic diameter, easy routing, optimal fault tolerance, and suitability for the ASCEND/DESCEND class of parallel problems. Furthermore, the proposed network achieves the logarithmic diameter with a very small constant node degree, 3 or 4.

Dictionary compression belongs to the class of lossless compression methods and is mainly used for compressing text files. The most known examples of this technique are the algorithms of the LZ coding family whose common feature is the use of an adaptive dictionary which is dynamically adjusting during the algorithm execution. In this paper, we present a parallel algorithm for one of these coding algorithms, namely the LZ77 coding algorithm also known as a sliding-window coding algorithm. We also present a parallel algorithm for the corresponding LZ77 decoding algorithm. Although there exist PRAM algorithms for various dictionary compression methods, their rather irregular structure has discouraged their implementation on practical interconnection networks such as the mesh and hypercube. However in the case of LZ77 coding/decoding, we show how to exploit the specific properties of the algorithm in order to achieve an efficient implementation on the hypercube. Specifically, we show how to encode a N-character string on a N-node hypercube in only O(log²N) time. In contrast, a naive simulation of a PRAM algorithm of the LZ77 coding on the hypercube would have O(log³N) complexity. In addition, we further enhance the performance of our parallel algorithms by using some known heuristics from the field of text compression.

We present an optimal embedding of a honeycomb network (honeycomb mesh and honeycomb torus) of size n into a hypercube with expansion ratio of when n is a power of two. When n is not a power of two, the expansion is , which we conjecture to be near optimal. For a honeycomb mesh, the dilation of the embedding is 1. For a honeycomb torus, the dilation can be as large as 2⌈log n⌉+3, because of the extra links connecting symmetric opposite nodes of degree two. A honeycomb network, built recursively using hexagon tessellation, is a multiprocessor interconnection network, and also a Cayley graph, and it is better than the planar mesh with the same number of nodes in terms of degree, diameter, number of links, and bisection width.

We call an edge-coloring of a graph $G$ a rainbow coloring if the edges of $G$ are colored with distinct colors. For every even positive integer $k\ge 4$, let $f(n,k)$ denote the minimum number of colors required to color the edges of the $n$-dimensional cube $Q_n$, so that every copy of $C_k$ is rainbow. Faudree et al. [6] proved that $f(n,4)=n$ for $n=4$ or $n>5$. Mubayi et al. [8] showed that $n\le f(n,6)<n^{1+o(1)}$. In this note, we show that $f(n,6)\ge 2n-1$. Moreover, we obtain the number of 6-cycles of $Q_n$.

Reliability evaluation of interconnection networks is of significant importance to the design and maintenance of interconnection networks. The extra connectivity is an important parameter for the reliability evaluation of interconnection networks. Given a graph $G$ and a positive integer $g$, the $g$-extra connectivity, denoted by ${\kappa }_g(G)$, is the minimum cardinality of a set of vertices in $G$, if exists, whose deletion disconnects $G$ and leaves each remaining component with at least $(g+1)$ vertices. In this paper, we show that the 3-extra connectivity of the $(n,k)$-enhanced hypercube is $(4n-5)$ for $n\ge 7$ and $1\le k\le n-6$. Some previous results in [IEEE Trans. Comput. 63 (2014) 1594–1600] and [Theor. Comput. Sci. 799 (2019) 22–31] are extended.

The implementation of parallel algorithms and the simulation of interconnection networks can be modeled into a graph embedding problem. Several cost parameters are used to assess the quality of an embedding. The wirelength is one of these factors that is frequently taken into account. A fractal cubic network is a new variant of the hypercube graph. In this study, we compute the wirelength of an embedding of the hypercube $Q_{2r}$ into the fractal cubic network $FCN(r-1)$ using ${\mathrm{\Theta }}^{\ast }$-partition.

A t-spanner of a network is a subnetwork in which every two nodes that were connected by an edge in the original network are connected by a path of at most t edges in the subnetwork. This guarantees that if nodes u and v are at distance d(u,v) in the original network, they are at distance no more than t·d(u,v) in the t-spanner. We introduce a more general definition of spanners. A special case of this more general definition is the additive t-spanner: a subnetwork in which every two nodes u and v that were separated by distance d(u,v) in the original network are at distance no more than t+d(u,v) in the subnetwork. We construct low-degree additive t-spanners for hypercubes.

This paper formulates and discusses a processor assignment problem arising in partitionable parallel architectures. A partitionable hypercube multiprocessor can simultaneously execute multiple tasks where each task is independently executed on a subcube. Given a p processor hypercube and n independent tasks, where a task can be assigned a subcube of any size, an assignment determines the size of the subcube — i.e., the number of processors — to be assigned to each task. The objective of our problem is to find the optimal assignment which minimizes the maximum execution time among all tasks. We present an O(n log p max{log log p, log n}) algorithm that determines an optimal assignment. This algorithm can be efficiently parallelized, on the p processor hypercube, to obtain an O((n/p)log p log²(n log p)) parallel assignment algorithm.

This paper deals with the problem of finding the K smallest elements out of a totally ordered but non-sorted set of N elements. This problem, called K-selection, arises often in statistics, image processing and distributed computing. We propose two algorithms to solve this problem in hypercubes. Our first algorithm is asymptotically optimal when K = O((log N)^β), for any constant β. The second enlarges the range of optimality to K = N^∊, ∊ < 1, using a recursive strategy. These are major improvements on previous results.

Gossiping is proposed as the preferred communication primitive for replicating pivot data in dense matrix factorization on message passing multicomputer. Performance gains are demonstrated on a hypercube for LU factorization algorithms based on gossiping as opposed to broadcasting. This finding has consequences for the design of numerical software libraries.

Hypercube is an attractive structure for parellel processing due to its symmetry and regularity. To increase the reliability of hypercube based systems and to allow their use in the presence of faulty nodes, efficient fault-tolerant schemes in hypercubes are necessary. In this paper, we present an algorithm for embedding rings in hypercubes based multiprocessor network in the event of node failures. The algorithm can tolerate up to θ(2^n/2) faults, and guarantee that given any f < (n - 2k)2^k faulty nodes, it can find a ring of size at least 2ⁿ - 2f for k = 0 and 2ⁿ - 2^k f - 2^2k for k ≥ 1 in an n-dimensional hypercube. It improves over existing algorithms in the size of ring.