View All Items

Title: Fault-tolerant multicasting in hypercube multicomputers.
Creator: Yao, Kejun., Florida Atlantic University, Wu, Jie, College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
Abstract/Description: Interprocessor communication plays an important role in the performance of multicomputer systems, such as hypercube multicomputers. In this thesis, we consider the multicast problem for a hypercube system in the presence of faulty components. Two types of algorithms are proposed. Type 1 algorithms, which are developed based on local network information, can tolerate both node failures and link failures. Type 2 algorithms, which are developed based on limited global network information, ensure...
Show moreInterprocessor communication plays an important role in the performance of multicomputer systems, such as hypercube multicomputers. In this thesis, we consider the multicast problem for a hypercube system in the presence of faulty components. Two types of algorithms are proposed. Type 1 algorithms, which are developed based on local network information, can tolerate both node failures and link failures. Type 2 algorithms, which are developed based on limited global network information, ensure that each destination receives message through the shortest path. Simulation results show that type 2 algorithms achieve very good results on both time and traffic steps, two main criteria in measuring the performance of interprocessor communication.
Show less
Date Issued: 1993
PURL: http://purl.flvc.org/fcla/dt/14896
Subject Headings: Hypercube networks (Computer networks), Computer architecture, Fault-tolerant computing
Format: Document (PDF)

Title: Dynamic routing in grid-connected networks.
Creator: Jiang, Zhen., Florida Atlantic University, Wu, Jie, College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
Abstract/Description: This dissertation describes the effect of collection and distribution of fault information on routing capacity in grid-connected networks with faults occurring during the routing process. The grid-connected network, such as hypercubes, 2-D meshes, and 3-D meshes, is one of the simplest and least expensive structures to build a system using hundreds and even thousands of processors. In such a system, efficient communication among the processors is critical to performance. Hence, the routing of...
Show moreThis dissertation describes the effect of collection and distribution of fault information on routing capacity in grid-connected networks with faults occurring during the routing process. The grid-connected network, such as hypercubes, 2-D meshes, and 3-D meshes, is one of the simplest and least expensive structures to build a system using hundreds and even thousands of processors. In such a system, efficient communication among the processors is critical to performance. Hence, the routing of messages is an important issue that needs to be addressed. As the number of nodes in the networks increases, the chance of failure also increases. The complex nature of networks also makes them vulnerable to disturbances. Therefore, the ability to route messages efficiently in the presence of faulty components, especially those might occur during the routing process, is becoming increasingly important. A central issue in designing a fault-tolerant routing algorithm is the way fault information is collected and used. The safety level model is a special coded fault information model in hypercubes which is more cost effective and more efficient than other information models. In this model, each node is associated with an integer, called safety level, which is an approximated measure of the number and distribution of faulty nodes in the neighborhood. The safety level of each node in an n-dimensional hypercube can be easily calculated through (n - 1)-rounds information exchanges among neighboring nodes. A k-safe node indicates the existence of at least one Hamming distance path (also called optimal path or minimal path) from this node to any node with Hamming distance k. We focus on routing capacity using safety levels in a dynamic system. In this case, the update of safety levels and the routing process proceed hand-in-hand. During the converging period, the routing process may experience extra hops based on unstable (inconsistent) information. Under the assumption that the total number of faults is less than n, we provide an upper bound of extra hops and show its accuracy and effectiveness. After that, we extend the results to meshes. Our simulation results show the effectiveness of our information model and scalability of our fault-information-based routing in the grid-connected networks with dynamic faults. Because our information is easy to update and maintain and optimality is still preserved, it is more cost effective than the others.
Show less
Date Issued: 2002
PURL: http://purl.flvc.org/fcla/dt/12002
Subject Headings: Fault-tolerant computing, Hypercube networks (Computer networks)
Format: Document (PDF)

Title: The balanced hypercube: A versatile cube-based multicomputer system.
Creator: Huang, Ke., Florida Atlantic University, Wu, Jie, College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
Abstract/Description: We propose the balanced hypercube (BH), which is a variant of the standard hypercube (Q), as a multicomputer topological structure. An n-dimensional balanced hypercube BHn has the same desirable topological properties of the 2n-dimensional standard hypercube Q2n such as size (2^2n nodes and n2^2n edges), regularity and symmetry, connectivity (2n node-disjoint pathes between any pair of nodes), and diameter (2n when n = 1 or n is even). Moreover, BHn has smaller diameter (2n-1) than Qn's (2n)...
Show moreWe propose the balanced hypercube (BH), which is a variant of the standard hypercube (Q), as a multicomputer topological structure. An n-dimensional balanced hypercube BHn has the same desirable topological properties of the 2n-dimensional standard hypercube Q2n such as size (2^2n nodes and n2^2n edges), regularity and symmetry, connectivity (2n node-disjoint pathes between any pair of nodes), and diameter (2n when n = 1 or n is even). Moreover, BHn has smaller diameter (2n-1) than Qn's (2n) when n is odd other than 1. In addition, BHn is load balanced, i.e., for every node v of BHn, there exists another node v', called v's matching node, such that v and v' share the same adjacent node set. Therefore, BHn has a desirable fault tolerance feature: when a node v fails, we can simply shift the job execution on v to its matching node v' and the communication pattern between jobs remains the same. In this dissertation, we study the topological properties of BHn and explore its fault tolerance feature. Other design issues are considered, such as communication primitives, capability of simulating other multicomputer systems through graph embedding, resource placement. and VLSI/WSI layout. Finally, the use of BHn is illustrated by an application.
Show less
Date Issued: 1997
PURL: http://purl.flvc.org/fcla/dt/12519
Subject Headings: Hypercube networks (Computer networks), Fault-tolerant computing
Format: Document (PDF)

Title: Load balancing on multiprocessor systems.
Creator: More, Hemant B., Florida Atlantic University, Wu, Jie, College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
Abstract/Description: The utilization of a multiprocessor system is enhanced when idle time of processors is reduced. Allocation of processes from overloaded processors to idle processors can balance the load on multiprocessor systems and increase system throughput by reducing the process execution time. This thesis presents a study of parameters, issues and existing algorithms related to load balancing. The performance of load balancing on hypercubes using three new algorithms is explored and analyzed. A new...
Show moreThe utilization of a multiprocessor system is enhanced when idle time of processors is reduced. Allocation of processes from overloaded processors to idle processors can balance the load on multiprocessor systems and increase system throughput by reducing the process execution time. This thesis presents a study of parameters, issues and existing algorithms related to load balancing. The performance of load balancing on hypercubes using three new algorithms is explored and analyzed. A new algorithm to balance load on hypercubes in the presence of link faults is presented and analyzed here. Another algorithm to balance load on hypercube systems containing faulty processors is proposed and studied. The applicability of load balancing to real life problems is demonstrated by showing that the execution of branch and bound problem on hypercubes speeds up when load balancing is used.
Show less
Date Issued: 1993
PURL: http://purl.flvc.org/fcla/dt/14957
Subject Headings: Hypercube networks (Computer networks), Multiprocessors, Fault-tolerant computing
Format: Document (PDF)

Title: Software-implemented fault tolerance in a hypercube multiprocessor.
Creator: Sahai, Shankar., Florida Atlantic University, Fernandez, Eduardo B., College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
Abstract/Description: This thesis analyzes how software fault tolerance can be implemented in a hypercube multiprocessor. For concreteness we consider a multiprocessor using Intel 80286/386/486 processors. The Recovery Metaprogram approach (an architecture that isolates all fault tolerance functions in a special layer) has been used to implement application transparent and application specific fault tolerance technigues such as recovery blocks, N-version programming, exceptions and others. A fault tolerant routing...
Show moreThis thesis analyzes how software fault tolerance can be implemented in a hypercube multiprocessor. For concreteness we consider a multiprocessor using Intel 80286/386/486 processors. The Recovery Metaprogram approach (an architecture that isolates all fault tolerance functions in a special layer) has been used to implement application transparent and application specific fault tolerance technigues such as recovery blocks, N-version programming, exceptions and others. A fault tolerant routing algorithm is also described. While the details are specific to the 80286/386/486 processor these results apply also to any other processor with similar features.
Show less
Date Issued: 1990
PURL: http://purl.flvc.org/fcla/dt/14633
Subject Headings: Hypercube networks (Computer networks), Intel 80x86 (Microprocessor)
Format: Document (PDF)

Title: Analysis of a cluster-based architecture for hypercube multicomputers.
Creator: Obeng, Morrison Stephen., Florida Atlantic University, Mahgoub, Imad, College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
Abstract/Description: In this dissertation, we propose and analyze a cluster-based hypercube architecture in which each node of the hypercube is furnished with a cluster of n processors connected through a small crossbar switch with n memory modules. Topological analysis of the cluster-based hypercube architecture shows that it reduces the complexity of the basic hypercube architecture by reducing the diameter, the degree of a node and the number of links in the hypercube. The proposed architecture uses the higher...
Show moreIn this dissertation, we propose and analyze a cluster-based hypercube architecture in which each node of the hypercube is furnished with a cluster of n processors connected through a small crossbar switch with n memory modules. Topological analysis of the cluster-based hypercube architecture shows that it reduces the complexity of the basic hypercube architecture by reducing the diameter, the degree of a node and the number of links in the hypercube. The proposed architecture uses the higher processing power furnished by the cluster of execution processors in each node to address the needs of computation-intensive parallel application programs. It provides a smaller dimension hypercube with the same number of execution processors as a higher dimension conventional hypercube architecture. This scheme can be extended to meshes and other architectures. Mathematical analysis of the parallel simplex and parallel Gaussian elimination algorithms executing on the cluster-based hypercube show the order of complexity of executing an n x n matrix problem on the cluster-based hypercube using parallel simplex algorithm to be O(n^2) and that of the parallel Gaussian elimination algorithm to be O(n^3). The timing analysis derived from the mathematical analysis results indicate that for the same number of processors in the cluster-based hypercube system as the conventional hypercube system, the computation to communication ratio of the cluster-based hypercube executing a matrix problem by parallel simplex algorithm increases when the number of nodes of the cluster-based hypercube is decreased. Self-driven simulations were developed to run parallel simplex and parallel Gaussian elimination algorithms on the proposed cluster-based hypercube architecture and on the Intel Personal Supercomputer (iPSC/860), which is a conventional hypercube. The simulation results show a response time performance improvement of up to 30% in favor of the cluster-based hypercube. We also observe that for increased link delays, the performance gap increases significantly in favor of the cluster-based hypercube architecture when both the cluster-based hypercube and the Intel iPSC/860, a conventional hypercube, execute the same parallel simplex and Gaussian elimination algorithms.
Show less
Date Issued: 1995
PURL: http://purl.flvc.org/fcla/dt/12435
Subject Headings: Computer architecture, Cluster analysis--Computer programs, Hypercube networks (Computer networks), Parallel computers
Format: Document (PDF)

Title: Fault-tolerant parallel computing using shuffle exchange hypercube and cube-connected cubes.
Creator: Goyal, Praduemn K., Florida Atlantic University, Wu, Jie, College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
Abstract/Description: The hypercube has become one of the most popular architectures for a wide variety of parallel processing applications and has been used in several commercial and research multiprocessors. Its topological and reliability properties have been studied extensively and several techniques have been proposed for enhancing its reliability. We first present a survey of the techniques that have been used for analyzing and enhancing the reliability of the hypercube and propose a classification framework...
Show moreThe hypercube has become one of the most popular architectures for a wide variety of parallel processing applications and has been used in several commercial and research multiprocessors. Its topological and reliability properties have been studied extensively and several techniques have been proposed for enhancing its reliability. We first present a survey of the techniques that have been used for analyzing and enhancing the reliability of the hypercube and propose a classification framework in which the surveyed reliability analysis techniques can be critically evaluated. Invariably, the techniques for enhancing the fault tolerance of the hypercube require modification of the processing nodes to include redundant elements, or alternatively, degrade the hypercube to a lower dimension cube when faults occur. We propose a technique using unmodified processing elements that takes advantage of the dataflow patterns of a specific class of parallel algorithms belonging to the divide-and-conquer paradigm. It is shown that by incorporating shuffles and exchanges, the execution of the divide-and-conquer class of algorithms on the hypercube can be made fault- tolerant. We develop this technique into a fault-tolerant computing scheme for execution of divide-and-conquer class of parallel algorithms, which we call Shuffle Exchange Hypercube (SEH). We propose a new recursively defined interconnection architecture for parallel computation called Cube-Connected Cubes (CCCubes). It is shown that the CCCubes architecture can emulate both the hypercube and the Cube-Connected Cycles (CCC) architectures. The CCCubes architecture is recursively extended into the kth order Generalized Cube-Connected Cubes (GCCCubes) architecture. We propose several classes of CCCubes and GCCCubes architectures and study their topological and reliability properties. A comparison of the reliability and topological properties of the proposed architectures with those of the hypercube is provided and it is shown that the CCCubes and GCCCubes architectures present practical alternatives to the hypercube. Finally, some areas worthy of further pursuit are presented, which include the problem of determining a switch route schedule for SEH, extension of shuffles and exchanges to CCCubes and GCCCubes, and the determination of a VLSI layout for the proposed CCCubes and GCCCubes architectures.
Show less
Date Issued: 1998
PURL: http://purl.flvc.org/fcla/dt/12581
Subject Headings: Fault-tolerant computing, Hypercube networks (Computer networks), Parallel processing (Electronic computers)
Format: Document (PDF)

Title: Processor allocation in hypercube computers.
Creator: Sua, Jose Reinier., Florida Atlantic University, Mahgoub, Imad, College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
Abstract/Description: In this thesis, processor allocation in hypercube computers is viewed to consist of the following three components. The ability to have complete subcube recognition, the heuristics and methods to speedup the recognition of free subcubes, and the policy to schedule incoming tasks to reduce the fragmentation of the hypercube. We propose a fast processor allocation strategy for hypercube computers called modified gray code (MGC). The MGC strategy achieves full subcube recognition with much less...
Show moreIn this thesis, processor allocation in hypercube computers is viewed to consist of the following three components. The ability to have complete subcube recognition, the heuristics and methods to speedup the recognition of free subcubes, and the policy to schedule incoming tasks to reduce the fragmentation of the hypercube. We propose a fast processor allocation strategy for hypercube computers called modified gray code (MGC). The MGC strategy achieves full subcube recognition with much less complexity than the multiple gray code and the tree collapse strategies. It is the first bitmapped strategy to incorporate binary search and heuristics to locate free subcubes, and has a new scheduling policy which significantly reduces the fragmentation of the hypercube. Simulation programs have been developed to compare the performance of the MGC to that of the other strategies so as to demonstrate its effectiveness. Results obtained showed that, in most of the situations, the MGC outperformed the other strategies, especially when the system load is high. We have also investigated processor allocation methods for real-time systems with fault-tolerant considerations. We propose methods that can handle a minimum of two dynamically occurring faults, without slowdown in execution and with a constant slowdown in communication of 3.
Show less
Date Issued: 1993
PURL: http://purl.flvc.org/fcla/dt/14904
Subject Headings: Hypercube networks (Computer networks), Computer architecture, Real-time data processing
Format: Document (PDF)

Title: Enhanced Fibonacci Cubes.
Creator: Qian, Haifeng., Florida Atlantic University, Wu, Jie, College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
Abstract/Description: We propose the enhanced Fibonacci cube (EFC), which is defined based on the sequence Fn = 2(n-2) + 2F(n-4). We study its topological properties, embeddings, applications, routings, VLSI/WSI implementations, and its extensions. Our results show that EFC retains many properties of the hypercube. It contains the Fibonacci cube (FC) and extended Fibonacci cube of the same order as subgraphs and maintains virtually all the desirable properties of FC. EFC is even better in some structural...
Show moreWe propose the enhanced Fibonacci cube (EFC), which is defined based on the sequence Fn = 2(n-2) + 2F(n-4). We study its topological properties, embeddings, applications, routings, VLSI/WSI implementations, and its extensions. Our results show that EFC retains many properties of the hypercube. It contains the Fibonacci cube (FC) and extended Fibonacci cube of the same order as subgraphs and maintains virtually all the desirable properties of FC. EFC is even better in some structural properties, embeddings, applications and VLSI designs than FC or hypercube. With EFC, there are more cubes with various structures and sizes for selection, and more backup cubes into which faulty hypercubes can be reconfigured, which alleviates the size limitation of the hypercube and results in a higher level of fault tolerance.
Show less
Date Issued: 1995
PURL: http://purl.flvc.org/fcla/dt/15196
Subject Headings: Integrated circuits--Very large scale integration, Hypercube networks (Computer networks), Algorithms, Fault-tolerant computing, Multiprocessors
Format: Document (PDF)

Title: Embedding binomial trees in faulty hypercube multiprocessors.
Creator: Luo, Yinqiu., Florida Atlantic University, Wu, Jie, College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
Abstract/Description: We study the embedding of binomial trees with variable roots in faulty hypercubes. Based on novel embedding strategies, we propose three embedding algorithms with variable nodes as the root. The first algorithm can tolerate up to n - 1 faulty links, but the execution can be done within log2(n - 1) subcube splits. The second one can tolerate up to [(3(n - 1))\2] faulty links. The last one can tolerate up to [(3(n - 4))\2] faulty nodes.
Date Issued: 1996
PURL: http://purl.flvc.org/fcla/dt/15345
Subject Headings: Hypercube networks (Computer networks), Trees (Graph theory), Multiprocessors, Parallel processing (Electronic computers), Computer algorithms, Fault-tolerant computing, Embedded computer systems
Format: Document (PDF)

Hypercube networks (Computer networks) (10)	+ -
Fault-tolerant computing (7)	+ -
Computer architecture (3)	+ -
Multiprocessors (3)	+ -
Parallel processing (Electronic computers) (2)	+ -

Algorithms (1)	+ -
Cluster analysis--Computer programs (1)	+ -
Computer algorithms (1)	+ -
Embedded computer systems (1)	+ -
Integrated circuits--Very large scale integration (1)	+ -
Intel 80x86 (Microprocessor) (1)	+ -
Parallel computers (1)	+ -
Real-time data processing (1)	+ -
Trees (Graph theory) (1)	+ -

College of Engineering and Computer Science (10)	+ -
Department of Computer and Electrical Engineering and Computer Science (10)	+ -
Florida Atlantic University (10)	+ -
Wu, Jie (7)	+ -
Mahgoub, Imad (2)	+ -

Fernandez, Eduardo B. (1)	+ -
Goyal, Praduemn K. (1)	+ -
Huang, Ke. (1)	+ -
Jiang, Zhen. (1)	+ -
Luo, Yinqiu. (1)	+ -
More, Hemant B. (1)	+ -
Obeng, Morrison Stephen. (1)	+ -
Qian, Haifeng. (1)	+ -
Sahai, Shankar. (1)	+ -
Sua, Jose Reinier. (1)	+ -
Yao, Kejun. (1)	+ -

Search In

Sort Results By:

Narrow results by:

Collection

Topical Subject

Genre

Type of Resource

Language

Creator

Format

Owner