Current Search: Hypercube networks Computer networks (x)
View All Items
 Title
 Faulttolerant 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, Faulttolerant computing
 Format
 Document (PDF)
 Title
 Dynamic routing in gridconnected 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 gridconnected networks with faults occurring during the routing process. The gridconnected network, such as hypercubes, 2D meshes, and 3D 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 gridconnected networks with faults occurring during the routing process. The gridconnected network, such as hypercubes, 2D meshes, and 3D 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 faulttolerant 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 ndimensional hypercube can be easily calculated through (n  1)rounds information exchanges among neighboring nodes. A ksafe 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 handinhand. 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 faultinformationbased routing in the gridconnected 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
 Faulttolerant computing, Hypercube networks (Computer networks)
 Format
 Document (PDF)
 Title
 The balanced hypercube: A versatile cubebased 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 ndimensional balanced hypercube BHn has the same desirable topological properties of the 2ndimensional standard hypercube Q2n such as size (2^2n nodes and n2^2n edges), regularity and symmetry, connectivity (2n nodedisjoint pathes between any pair of nodes), and diameter (2n when n = 1 or n is even). Moreover, BHn has smaller diameter (2n1) 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 ndimensional balanced hypercube BHn has the same desirable topological properties of the 2ndimensional standard hypercube Q2n such as size (2^2n nodes and n2^2n edges), regularity and symmetry, connectivity (2n nodedisjoint pathes between any pair of nodes), and diameter (2n when n = 1 or n is even). Moreover, BHn has smaller diameter (2n1) 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), Faulttolerant 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, Faulttolerant computing
 Format
 Document (PDF)
 Title
 Softwareimplemented 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, Nversion 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, Nversion 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 clusterbased 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 clusterbased 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 clusterbased 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 clusterbased 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 clusterbased 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 computationintensive 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 clusterbased hypercube show the order of complexity of executing an n x n matrix problem on the clusterbased 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 clusterbased hypercube system as the conventional hypercube system, the computation to communication ratio of the clusterbased hypercube executing a matrix problem by parallel simplex algorithm increases when the number of nodes of the clusterbased hypercube is decreased. Selfdriven simulations were developed to run parallel simplex and parallel Gaussian elimination algorithms on the proposed clusterbased 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 clusterbased hypercube. We also observe that for increased link delays, the performance gap increases significantly in favor of the clusterbased hypercube architecture when both the clusterbased 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 analysisComputer programs, Hypercube networks (Computer networks), Parallel computers
 Format
 Document (PDF)
 Title
 Faulttolerant parallel computing using shuffle exchange hypercube and cubeconnected 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 divideandconquer paradigm. It is shown that by incorporating shuffles and exchanges, the execution of the divideandconquer class of algorithms on the hypercube can be made fault tolerant. We develop this technique into a faulttolerant computing scheme for execution of divideandconquer class of parallel algorithms, which we call Shuffle Exchange Hypercube (SEH). We propose a new recursively defined interconnection architecture for parallel computation called CubeConnected Cubes (CCCubes). It is shown that the CCCubes architecture can emulate both the hypercube and the CubeConnected Cycles (CCC) architectures. The CCCubes architecture is recursively extended into the kth order Generalized CubeConnected 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
 Faulttolerant 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 realtime systems with faulttolerant 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, Realtime 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(n2) + 2F(n4). 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(n2) + 2F(n4). 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 circuitsVery large scale integration, Hypercube networks (Computer networks), Algorithms, Faulttolerant 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, Faulttolerant computing, Embedded computer systems
 Format
 Document (PDF)