A Boolean expression-based approach for maximum incomplete subcubeidentification in faulty hypercubes

An incomplete hypercube possesses virtually every advantage of complete hypercubes, including simple deadlock-free routing, a small diameter, bounded link traffic density, a good support of parallel algorithms, and so on. It is natural to reconfigure a faulty hypercube into a maximum incomplete cube so as to lower potential performance degradation, because a hypercube so reconfigured often results in a much larger system than what is attainable according to any conventional reconfiguration scheme which identifies only complete subcubes. A maximum incomplete subcube involves one maximum complete subcube, plus certain smaller complete subcubes, and, thus, may accommodate multiple jobs of different sizes simultaneously, delivering a higher performance level. This paper proposes an efficient approach for identifying all the maximum incomplete subcubes present in a faulty hypercube. The proposed approach is on the basis of manipulating Boolean expressions, with the search space reduced considerably by taking advantage of the basic properties of faulty hypercubes during expression manipulation. It is distributed, in that every healthy node executes the same identification algorithm independently, at the same time, it is confirmed by fault simulation that our approach indeed gives rise to significantly larger reconfigured systems and requires short execution times     

Embedding and reconfiguration of binary trees in faulty hypercubes

We consider the problem of embedding and reconfiguring binary tree structures in faulty hypercubes. We assume that the number of faulty nodes is at most (n-2), where n is the number of dimensions of the hypercube; we further assume that the location of faulty nodes are known. Our embedding techniques are based on a key concept called free dimension, which can be used to partition a cube into subcubes such that each subcube contains at most one faulty node. Using this approach, two distributed schemes are provided for embedding and reconfiguration in faulty hypercubes. We extend the free dimension concept to degree of occupancy and use this to develop a distributed scheme for reconfiguration of binary tree in faulty hypercubes with up to [3n/2] node faults     

Traffic analysis and simulation performance of incompletehypercubes

The incomplete hypercube with arbitrary nodes provides far better incremental flexibility than the complete hypercube, whose size is restricted to exactly a power of 2. After faults arise in a complete hypercube system, it is desirable to reconfigure the system so as to retain as many healthy nodes as possible, often leading to an incomplete hypercube of arbitrary size. In this paper, the highest traffic density over links in an incomplete hypercube under uniform message distribution is shown to be bounded by 2 (messages per link per cycle), independent of its size and despite its structural nonhomogeneity. As a result, it is easily achievable to construct an incomplete hypercube with sufficient link communication capability where any potential points of congestion are avoided, ensuring high performance. Simulation results for the incomplete hypercube reveal that mean latency for delivering messages is roughly the same in an incomplete hypercube as in a compatible complete hypercube under both packet-switching and wormhole routing. The incomplete hypercube thus appears to be an attractive and practical architecture, since it shares every advantage of complete hypercubes while eliminating the restriction on the system size     

Incomplete hypercubes: Algorithms and embeddings

The hypercube, though a popular and versatile architecture, has a major drawback in that its size must be a power of two. In order to alleviate this drawback, Katseff [1988] defined theincomplete hypercube, which allows a hypercube-like architecture to be defined for any number of nodes. In this paper we generalize this definition and introduce the namecomposite hypercube. The main result of our work shows that these incomplete architectures can be used effectively and without the size penalty. In particular, we show how to efficiently implement Fully Normal Algorithms on composite hypercubes. Development of these types of algorithms on composite hypercubes allows us to efficiently execute several algorithms concurrently on a complete hypercube. We also show that many host architectures, such as binary trees, arrays and butterflies, can be optimally embedded into composite hypercubes. These results imply that algorithms originally designed for any such host can be optimally mapped to composite hypercubes. Finally, we show that composite hypercubes exhibit many graph theoretic properties that are common with complete hypercubes. We also present results on efficient representations of composite hypercubes within a complete hypercube. These results are crucial in task allocation and job scheduling problems.This research was supported in part by the National Science Foundation under grant USE-90-52346. A preliminary version of this work appeared in the5th International Parallel Processing Symnposium, May 1991.     

Near-optimal message routing and broadcasting in faulty hypercubes

A distributed routing algorithm for faulty hypercubes is described. This algorithm uses a directed depth-first approach to find a path between the sender and receiver of a message whenever at least one non-faulty path exists. We show that, when an arbitrary number of elements of the hypercube can be faulty, the algorithm always routes messages using fewer than 2N hops, whereN is the number of nodes in the hypercube. This performance is shown to be within a factor of two of the optimal worst-case routing efficiency. Through foult simulations, we show that, even when up to half of the elements in the cube are faulty, complete the analysis, we prove that our algorithm is deadlock-free. Finally, we present two extensions of the algorithm. The first uses local storage to reduce the overhead of the algorithm while the second allows reliable broadcasting in the presence of an arbitrary number of faults.Supported in part by the National Science Foundation under Grant CCR-9010547.Supported in part by the National Science Foundation Instrumentation Grant CDA-8820627.     

Simulation of Complete Binary Tree Structures in a Faulty Flexible Hypercube

The Flexible Hypercube is a generalization of binary hypercube networks in that the number of nodes can be arbitrary in contrast to a strict power of 2. Restated, the Flexible Hypercube retains the connectivity and diameter properties of the corresponding hypercube. Although the embedding of complete binary trees in faulty hypercubes has received considerable attention, to our knowledge, no paper has demonstrated how to embed a complete binary tree in a faulty Flexible Hypercube. Therefore, this investigation presents a novel algorithm to facilitate the embedding job when the Flexible Hypercube contains faulty nodes. Of particular concern are the network structures of the Flexible Hypercube that balance the load before as well as after faults start to degrade the performance of the Flexible Hypercube. Furthermore, to obtain the replaceable node of the faulty node, 2-expansion is permitted such that up to (n – 2) faults can be tolerated with congestion 1, dilation 4 and load 1. That is, (n – 1) is the dimension of a Flexible Hypercube. Results presented herein demonstrate that embedding methods are optimized.     

Fast compaction in hypercubes

Compaction relocates active subcubes in a fragmented hypercube so as to produce a contiguous free region and eliminate the adverse impact of fragmentation on performance. The overhead of compaction is often contributed primarily by task migration, which makes use of disjoint paths for transmitting migrated data. Since task migration usually involves transmitting a large amount of data, the time required for migration with single paths is long, making compaction an undesirably lengthy process. This paper considers fast compaction through the use of all disjoint paths in existence for migration simultaneously from a source subcube to its target subcube, effectively reducing the size of data transmitted over a path and shortening the migration time. This approach leads to considerable savings in the compaction time for hypercubes which support circuit switching or wormhole routing, when compared with that using single migration paths     

A fault-tolerant distributed subcube management scheme forhypercube multicomputer systems

This paper proposes a fault-tolerant distributed subcube management scheme for hypercube multicomputer systems. Gracefully degradable subcube management is supported by a data structure, called the distributed subcube table (DST), and a fault-tolerant broadcast protocol, called the reliably synchronized broadcast (RSB). In an n-dimensional hypercube, DST is the collection of 2ⁿ local subcube tables (LSTs), DST={LST₀, LST, ..., LST_2-1 ⁿ}, where LST, is a bit-mapped table assigned to N_x, a fault-free node whose address is x. LST_x, ∀_x, is n+1 bits long, and it records the status (free/busy) of certain subcubes adjacent to N_x. The RSB diagnoses and avoids faults during interprocessor communication to prevent faulty nodes from being allocated for job execution. In addition to possessing a fault-tolerant design, our scheme can also achieve comparable or better performance than existing centralized schemes, as verified by extensive simulation     

An effective routing algorithm in incomplete hypercubes

An incomplete hypercube appears interesting and practical because of its relaxed restriction on the system size and possession of salient properties of complete hypercubes. The performance of incomplete hypercubes can be improved considerably by reducing communication time, which can be achieved by forwarding messages through two parallel paths between a pair of nodes. This paper presents a simple and effective two-parallel-paths routing algorithm for incomplete hypercubes which takes advantage of the flexibility provided by incomplete hypercubes, and yet prevents traffic congestion and deadlock. Simulation results indicate that the mean latency for sending large sized messages is reduced and the degree of reduction becomes larger when the system load grows. This significant reduction in latency could translate to a respectable performance improvement. This algorithm can also tolerate one fault in the system by sending duplicate copies of messages through two parallel paths with little increase in the mean latency under light-traffic load.     

Embedding and reconfiguration of spanning trees in faultyhypercubes

The problem of tolerating faulty nodes in hypercubes has been studied by many researchers either by using spares or by reconfiguration. Algorithms for tolerating faulty nodes and links in hypercubes are presented. The algorithms are based on using general spanning trees (GST), complete unbalanced spanning trees (CUST), and balanced spanning trees (BST) for reconfiguring the hypercube to avoid faulty nodes and links. The algorithms contain two phases: the first phase involves the construction of the spanning tree and the second one is for reconfiguring the hypercube should a faulty node be detected. The reconfiguration process consists of two basic steps. First, the faulty node is disconnected from the spanning tree. Then, a new spanning tree is constructed by reconnecting the children of the faulty node to the spanning tree. One hundred percent single fault correction (avoidance) and almost 100 percent fault correction (avoidance) of double and triple faults are achieved by the proposed algorithms for hypercubes having a dimension of n⩾6. Simulation results for the algorithm under more than three faults also are presented. For any k faulty nodes (1⩽k⩽2ⁿ-1), the reconfiguration algorithm may be applied k times to avoid these k faulty nodes as long as no combination of any two of the faults results in a blocking situation. The proposed reconfiguration algorithms tolerate all possible single-link faults. The reconfiguration algorithms are extended to tolerate (k⩽n-1) multiple faults, causing blocking situation, with a backtracking     

Parallel routing algorithms for incomplete hypercube interconnection networks

Hypercube interconnection networks have been receiving considerable attention in the supercomputing environment. However, the number of processors must be exactly 2^r for an r-cube complete hypercube. This restriction severely limits its applicability. In this paper, we address three variant hypercube topologies with more flexibility in system sizes, the labelled hypercubes I_m^r, I_M^r, and I_A^r. Incomplete hypercube I_m^r consists of an r-cube and an m-cube complete hypercubes; I_m^r is composed of 2^r and Σ_{m ε M} 2^m nodes; I_Ar comes from an r-cube complete hypercube which operates in a degraded manner and allows that the missing nodes to be arbitrarily distributed. Specifically, we focus on the parallel paths routing algorithms for these three classes of incomplete hypercubes. Parallel paths between any given two nodes mean that these paths have the same source and destination nodes but with different intermediate nodes. Parallel communication is important as it will allow us to use the full bandwidth of the multiprocessors for the data transfer operation between any two nodes, and3these redundant paths can increase system fault-tolerance and communication reliability. With these parallel routing algorithms, one can use them as a criterion to design multiprocessor systems.     

Fuzzy hypercubes: Linguistic learning/reasoning systems for intelligent control and identification

This paper introduces a new tool for intelligent control and identification. A robust and reliable learning and reasoning mechanism is addressed based upon fuzzy set theory and fuzzy associative memories. The mechanism storesa priori an initial knowledge base via approximate learning and utilizes this information for identification and control via fuzzy inferencing. This architecture parallels a well-known scheme in which memory implicative rules are stored disjunctively. We call this process afuzzy hypercube. Fuzzy hypercubes can be applied to a class of complex and highly nonlinear systems which suffer from vagueness uncertainty and incomplete information such as fuzziness and ignorance. Evidential aspects of a fuzzy hypercube are treated to assess the degree of certainty or reliability. The implementation issue using fuzzy hypercubes is raised, and finally, a fuzzy hypercube is applied to fuzzy linguistic control.     

Embedding of generalized Fibonacci cubes in hypercubes with faultynodes

The generalized Fibonacci cubes (abbreviated to GFCs) were recently proposed as a class of interconnection topologies, which cover a spectrum ranging from regular graphs such as the hypercube to semiregular graphs such as the second order Fibonacci cube. It has been shown that the kth order GFC of dimension n+k is equivalent to an n-cube for 0⩽n相似文献   

Processor allocation in hypercube multiprocessors

The processor allocation problem requires recognizing and locating a free subcube that can accommodate a request for a subcube of a specified size for an incoming task. Methods reported in the literature fall into two strategies: bottom-up or bit mapped technique (BMT) and top-downer available cube technique (ACT). Our algorithm that solves the allocation problem in faulty hypercubes falls into the category of ACT's which offer the advantage over BMT's of quickly recognizing whether or not a requested subcube is available in the list of fault-free subcubes. We introduce new algebraic functions and the concept of separation factor to select a subcube for allocation. The notion of overlap-syndrome, defined in the text, quantifies the overlap among free subcubes. Our technique has full subcube recognition ability and thus recognizes more subcubes as compared to bit mapped techniques: Buddy, Gray code and its variants. The advantages of our approach over some of the existing ACT's in terms of fragmentation and overall completion time are described in the text and in simulation results     

Embedding ofk-ary Complete Trees into Hypercubes with Uniform Load

The main result of this paper is an algorithm for embeddingk-ary complete trees into hypercubes with uniform load and asymptotically optimal dilation. The algorithm is fully scalable—the dimension of the hypercube can be chosen independent of the arity and height of the tree. The embedding enables to emulate optimally both Divide&Conquer computations onk-ary complete trees where only one level of nodes is active at a time and general computations based onk-ary complete trees where all tree nodes are active simultaneously. As a special case, we get an algorithm for embedding thek-ary complete tree of given height into its optimal hypercube with load 1 and asymptotically optimal dilation.     

A top-down processor allocation scheme for hypercube computers

An efficient processor allocation policy is presented for hypercube computers. The allocation policy is called free list since it maintains a list of free subcubes available in the system. An incoming request of dimension k (2^k nodes) is allocated by finding a free subcube of dimension k or by decomposing an available subcube of dimension greater than k. This free list policy uses a top-down allocation rule in contrast to the bottom-up approach used by the previous bit-map allocation algorithms. This allocation scheme is compared to the buddy, gray code (GC), and modified buddy allocation policies reported for the hypercubes. It is shown that the free list policy is optimal in a static environment, as are the other policies, and it also gives better subcube recognition ability compared to the previous schemes in a dynamic environment. The performance of this policy, in terms of parameters such as average delay, system utilization, and time complexity, is compared to the other schemes to demonstrate its effectiveness. The extension of the algorithm for parallel implementation, noncubic allocation, and inclusion/exclusion allocation is also given     

Distributed computing on oriented anonymous hypercubes with faulty components

We give efficient algorithms for distributed computation on oriented, anonymous, asynchronous hypercubes with possible faulty components (i.e. processors and links) and deterministic processors. Initially, the processors know only the size of the network and that they are inter-connected in a hypercube topology. Faults may occur only before the start of the computation (and that despite this the hypercube remains a connected network). However, the processors do not know where these faults are located. As a measure of complexity we use the total number of bits transmitted during the execution of the algorithm and we concentrate on giving algorithms that will minimize this number of bits. The main result of this paper is an algorithm for computing Boolean functions on anonymous hypercubes with bit cost , where is the number of faulty components (i.e. links plus processors), is the number of links which are either faulty, or non-faulty but adjacent to faulty processors, and is the diameter of the hypercube with faulty components. Received: October 1992 / Accepted: April 2001     

Incomplete Hypercubes: Embeddings of Tree-Related Networks

We consider the incomplete hypercubes, a generalization of the binary hypercube networks in the sense that the number of nodes can be arbitrary as opposed to a strict power of 2. The capability of the incomplete hypercubes to execute parallel programs is studied here using graph embedding techniques. We show optimal (or nearly optimal) embeddings of various guest networks such as X-trees, full-ringed binary trees, tree machines, mesh of trees, and pyramids into the optimum-sized incomplete hypercube host.     

Operationally enhanced folded hypercubes

Recently, several variations of the hypercube have been proposed to enhance its performance and reliability. The folded hypercube is one of these variations, in which an extra link is added to each node providing a direct connection to the node located farthest from it. In this paper, we propose a new operation mode of the folded hypercube to enhance its performance and fault-tolerance. There are (_kⁿ⁺¹) regular k-cubes within a folded hypercube of dimension n, denoted by FQ_n. We introduce another type of hypercube, called the twisted hypercube, to improve the performance and fault tolerance of the folded hypercube. The problems of finding a subcube of given size in an FQ_n and routing messages within the subcube are addressed for the proposed operation mode. The advantages of the proposed operation mode over the regular-hypercube operation mode are analyzed in terms of dependability and robustness. The proposed operation mode is shown to make significant improvements over the regular-hypercube operation mode in both dependability and robustness. Because the new operation mode can be applied to only an (n-1)-subcube level for a given FQ_n, we present general form of folded hypercube, thus enhancing the availability of subcubes of any dimension m相似文献