View All Items

Title: Analysis of a novel class of fault-tolerant multistage interconnection networks.
Creator: Huang, Chien-Jen, Florida Atlantic University, Mahgoub, Imad, College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
Abstract/Description: Multistage interconnection networks (MINs) have become an important subset of the interconnection networks which are used to communicate between processors and memory modules for large scale multiprocessor systems. Unfortunately, unique path MINs lack fault tolerance. In this dissertation, a novel scheme for constructing fault-tolerant MINs is presented. We first partition the given MINs into even sized partitions and show some fault-tolerant properties of the partitioned MINs. Using three...
Show moreMultistage interconnection networks (MINs) have become an important subset of the interconnection networks which are used to communicate between processors and memory modules for large scale multiprocessor systems. Unfortunately, unique path MINs lack fault tolerance. In this dissertation, a novel scheme for constructing fault-tolerant MINs is presented. We first partition the given MINs into even sized partitions and show some fault-tolerant properties of the partitioned MINs. Using three stages of multiplexers/demultiplexers, an augmenting scheme which takes advantage of locality in program execution is then proposed to further improve the fault-tolerant ability and performance of the partitioned MINs. The topological characteristics of augmented partitioned multistage interconnection networks (APMINs) are analyzed. Based on switch fault model, simulations have been carried out to evaluate the full access and dynamic full access capabilities of APMINs. The results show that the proposed scheme significantly improves the fault-tolerant capability of MINs. Cost effectiveness of this new scheme in terms of cost, full access, dynamic full access, locality, and average path length has also been evaluated. It has been shown that this new scheme is more cost effective for high switch failure rate and/or large size networks. Analytical modeling techniques have been developed to evaluate the performance of AP-Omega network and AP-Omega network-based multiprocessor systems. The performance of Omega, modified Omega, and AP-Omega networks in terms of processor utilization and processor waiting time have been compared and the results show that the new scheme indeed, improves the performance both in network level and in system level. Finally, based on the reliability of serial/parallel network components, models for evaluating the terminal reliability and the network reliability of AP-Omega network using upper and lower bound measures have also been proposed and the results show that applying locality improve APMINs' reliability.
Show less
Date Issued: 1993
PURL: http://purl.flvc.org/fcla/dt/12345
Subject Headings: Integratged circuits--Very large scale integration, Fault-tolerant computing, Computer architecture, Parallel processing (Electronic computers)
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: Checkpointing schemes for high-performance parallel applications in networks of workstations.
Creator: He, Fusen., Florida Atlantic University, Wu, Jie
Abstract/Description: In this thesis, a low interprocessor communication overhead and high performance data parallelism parallel application model in a network of workstations (NOWs) is proposed. Checkpointing and rollback technologies are used in this model for performance enhancement purpose. The proposed model is analyzed both theoretically and numerically. The simulation results show that a high performance of the parallel application model is expected. As a case study, the proposed model is used to the...
Show moreIn this thesis, a low interprocessor communication overhead and high performance data parallelism parallel application model in a network of workstations (NOWs) is proposed. Checkpointing and rollback technologies are used in this model for performance enhancement purpose. The proposed model is analyzed both theoretically and numerically. The simulation results show that a high performance of the parallel application model is expected. As a case study, the proposed model is used to the parallel Everglades Landscape Fire Model (ELFM) code which was developed by South Florida Water Management District (SFWMD). The parallel programming environment is Message-Passing Interface (MPI). A synchronous checkpointing and rollback mechanism is used to handle the spread of fire which is a dynamic and irregular component of the model. Results show that the performance of the parallel ELFM using MPI is significantly enhanced by the application of checkpointing and rollback.
Show less
Date Issued: 1998
PURL: http://purl.flvc.org/fcla/dt/15597
Subject Headings: Computer networks, Electronic data processing--Distributed processing, Fault-tolerant computing
Format: Document (PDF)

Title: Damage detection for autonomous underwater vehicles.
Creator: Rae, Graeme John Stuart., Florida Atlantic University, Dunn, Stanley E., College of Engineering and Computer Science, Department of Ocean and Mechanical Engineering
Abstract/Description: A method of on-line monitoring AUV onboard systems is described. This algorithm determines deviations from normal operating conditions based on a damage level calculated from recursive least squares system identification performed on the system under consideration, followed by a gradient detection technique which extracts significant changes in identified model parameters System damage types are characterized together with likely system responses to such failures. Extensive testing of the...
Show moreA method of on-line monitoring AUV onboard systems is described. This algorithm determines deviations from normal operating conditions based on a damage level calculated from recursive least squares system identification performed on the system under consideration, followed by a gradient detection technique which extracts significant changes in identified model parameters System damage types are characterized together with likely system responses to such failures. Extensive testing of the algorithm is performed using several simulated AUV on-board systems undergoing different types of failures while carrying out different mission scenarios.
Show less
Date Issued: 1993
PURL: http://purl.flvc.org/fcla/dt/12331
Subject Headings: Submersibles--Automatic control, Fault-tolerant computing, Algorithms--Data procedssing
Format: Document (PDF)

Title: Design and modeling of hybrid software fault-tolerant systems.
Creator: Zhang, Man-xia Maria., Florida Atlantic University, Wu, Jie, College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
Abstract/Description: Fault tolerant programming methods improve software reliability using the principles of design diversity and redundancy. Design diversity and redundancy, on the other hand, escalate the cost of the software design and development. In this thesis, we study the reliability of hybrid fault tolerant systems. Probability models based on fault trees are developed for the recovery block (RB), N-version programming (NVP) and hybrid schemes which are the combinations of RB and NVP. Two heuristic...
Show moreFault tolerant programming methods improve software reliability using the principles of design diversity and redundancy. Design diversity and redundancy, on the other hand, escalate the cost of the software design and development. In this thesis, we study the reliability of hybrid fault tolerant systems. Probability models based on fault trees are developed for the recovery block (RB), N-version programming (NVP) and hybrid schemes which are the combinations of RB and NVP. Two heuristic methods are developed to construct hybrid fault tolerant systems with total cost constraints. The algorithms provide a systematic approach to the design of hybrid fault tolerant systems.
Show less
Date Issued: 1992
PURL: http://purl.flvc.org/fcla/dt/14783
Subject Headings: Computer software--Reliability, Fault-tolerant computing, Algorithms
Format: Document (PDF)

Title: The design of reliable decentralized computer systems.
Creator: Wu, Jie., Florida Atlantic University, Fernandez, Eduardo B., College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
Abstract/Description: With the increase in the applications of computer technology, there are more and more demands for the use of computer systems in the area of real-time applications and critical systems. Reliability and performance are fundamental design requirements for these applications. In this dissertation, we develop some specific aspects of a fault-tolerant decentralized system architecture. This system can execute concurrent processes and it is composed of processing elements that have only local...
Show moreWith the increase in the applications of computer technology, there are more and more demands for the use of computer systems in the area of real-time applications and critical systems. Reliability and performance are fundamental design requirements for these applications. In this dissertation, we develop some specific aspects of a fault-tolerant decentralized system architecture. This system can execute concurrent processes and it is composed of processing elements that have only local memories with point-to-point communication. A model using hierarchical layers describes this system. Fault tolerance techniques are discussed for the applications, software, operating system, and hardware layers of the model. Scheduling of communicating tasks to increase performance is also addressed. Some special problems such as the Byzantine Generals problem are considered. We have shown that, by combining reliable techniques on different layers and with consideration of system performance, one can provide a system with a very high level reliability as well as performance.
Show less
Date Issued: 1989
PURL: http://purl.flvc.org/fcla/dt/12237
Subject Headings: Electronic digital computers--Reliability, Fault-tolerant computing, System design, Computer software--Reliability
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: 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)

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: Fault tolerant scheduling for multiprocessor systems.
Creator: Mahanthi, Gangadhar., Florida Atlantic University, Wu, Jie, College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
Abstract/Description: In the last few years, it has become profound to achieve higher performance of computers by solely upgrading logic technology. This required a move to a parallel processing system or a multiprocessor system in order to build faster computer systems. The importance of multiprocessor systems is increasing due to many reasons, one of which is reliability. In a multiprocessor system, a number of tasks may concurrently exist. To operate the system efficiently, one must carefully schedule the tasks...
Show moreIn the last few years, it has become profound to achieve higher performance of computers by solely upgrading logic technology. This required a move to a parallel processing system or a multiprocessor system in order to build faster computer systems. The importance of multiprocessor systems is increasing due to many reasons, one of which is reliability. In a multiprocessor system, a number of tasks may concurrently exist. To operate the system efficiently, one must carefully schedule the tasks. This thesis proposes a set of algorithms to schedule these tasks exploiting the inherent redundancy of processors in a multiprocessor system. Also discussed are some reliability issues and application to different networks with some examples.
Show less
Date Issued: 1992
PURL: http://purl.flvc.org/fcla/dt/14822
Subject Headings: Multiprocessors, Fault-tolerant computing, Electronic digital computers--Reliability
Format: Document (PDF)

Title: Fault-tolerant distributed shared memories.
Creator: Brown, Larry., Florida Atlantic University, Wu, Jie, College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
Abstract/Description: Distributed shared memory (DSM) implements a shared-memory programming interface on message-passing hardware. The shared-memory programming paradigm offers several advantages over the message-passing paradigm. DSM is recognized as an important technology for massively parallel computing. However, as the number of processors in a system increases, the probability of a failure increases. To be widely useful, the DSM must be able to tolerate failures. This dissertation presents a method of...
Show moreDistributed shared memory (DSM) implements a shared-memory programming interface on message-passing hardware. The shared-memory programming paradigm offers several advantages over the message-passing paradigm. DSM is recognized as an important technology for massively parallel computing. However, as the number of processors in a system increases, the probability of a failure increases. To be widely useful, the DSM must be able to tolerate failures. This dissertation presents a method of implementing fault-tolerant DSM (FTDSM) that is based on the idea of a snooper. The snooper monitors DSM protocol messages and keeps a backup of the current state of the DSM. The snooper can respond on behalf of failed processors. The snooper-based FTDSM is an improvement over existing FTDSMs because it is based on the efficient dynamic distributed manager DSM algorithm, does not require the repair of a failed processor in access the DSM, and does not query all nodes to rebuild the state of the DSM. Three snooper-based FTDSM systems are developed. The single-snooper (SS) FTDSM has one snooper and is restricted to a broadcast network. Additional snoopers are added in the multiple-snooper (MS) FTDSM to improve performance. Two-phase commit (2PC) protocols are developed to coordinate the activities of the snoopers, and a special data structure is used to store causality information to reduce the amount of snooper activity. Snooping is integrated with each processor in the integrated snooper (IS) FTDSM. The IS FTDSM is scalable because it is not restricted to a broadcast network. The concept of dynamic snooping is introduced for the IS FTDSM and several snooper migration algorithms are studied. Several recovery algorithms are developed to allow failed processors to rejoin the system. The properties of data structures used to locate owners and snoopers are studied and used to prove that the system can tolerate any single fault. A flexible method of integrating application-level recovery with the FTDSM is presented, and a reliability analysis is conducted using a Markov-chain modeling tool to show that the snooper-based FTDSM is a cost effective way to improve the reliability of DSM.
Show less
Date Issued: 1993
PURL: http://purl.flvc.org/fcla/dt/12349
Subject Headings: Fault-tolerant computing, Electronic data processing--Distributed processing, Parallel processing (Electronic computers), Computer networks
Format: Document (PDF)

Title: A fault-tolerant memory architecture for storing one hour of D-1 video in real time on long polyimide tapes.
Creator: Monteiro, Pedro Cox de Sousa., Florida Atlantic University, Glenn, William E., College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
Abstract/Description: Research is under way to fabricate large-area thin-film transistor arrays produced on a thin polyimide substrate. The polyimide substrate is available in long thirty centimeter wide rolls of tape, and lithography hardware is being developed to expose hundreds of meters of this tape with electrically addressable light modulators which can resolve 2 $\mu$m features. A fault-tolerant memory architecture is proposed that is capable of storing one hour of D-1 component digital video (almost 10^12...
Show moreResearch is under way to fabricate large-area thin-film transistor arrays produced on a thin polyimide substrate. The polyimide substrate is available in long thirty centimeter wide rolls of tape, and lithography hardware is being developed to expose hundreds of meters of this tape with electrically addressable light modulators which can resolve 2 $\mu$m features. A fault-tolerant memory architecture is proposed that is capable of storing one hour of D-1 component digital video (almost 10^12 bits) in real-time, on eight two-hundred meter long tapes. Appropriate error correcting codes and error concealment are proposed to compensate for drop-outs resulting from manufacturing defects so as to yield video images with error rates low enough to survive several generations of copies.
Show less
Date Issued: 1992
PURL: http://purl.flvc.org/fcla/dt/14869
Subject Headings: Polyimides, Computer architecture, Memory hierarchy (Computer science), Fault-tolerant computing
Format: Document (PDF)

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: 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: Fault-tolerant routing in two-dimensional and three-dimensional meshes.
Creator: Chen, Xiao., Florida Atlantic University, Wu, Jie, College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
Abstract/Description: Mesh-connected multicomputers are one of the simplest and least expensive structures to build a system using hundreds and even thousands of processors. The nodes communicate with each other by sending and receiving messages. As the system gets larger and larger, it not only requires the routing algorithms be efficient but also fault-tolerant. The fault model we use in 2-D meshes is a faulty block while in 3-D meshes, the fault model is a faculty cube. In order to route messages through...
Show moreMesh-connected multicomputers are one of the simplest and least expensive structures to build a system using hundreds and even thousands of processors. The nodes communicate with each other by sending and receiving messages. As the system gets larger and larger, it not only requires the routing algorithms be efficient but also fault-tolerant. The fault model we use in 2-D meshes is a faulty block while in 3-D meshes, the fault model is a faculty cube. In order to route messages through feasible minimum paths, the extended safety level is used to determine the existence of a minimal path and faulty block (cube) information is used to guide the routing. This dissertation presents an in-depth study of fault-tolerant minimal routing in 2-D tori, 3-D meshes, and tree-based fault-tolerant multicasting in 2-D and 3-D meshes using extended safety levels. Also path-based fault-tolerant deadlock-free multicasting in 2-D and 3-D meshes is studied. In fault-tolerant minimal routing in 2-D meshes, if no faulty block is encountered, any adaptive minimal routing can be used until the message encounters a faulty block. The next step is guided by the faulty block information until the message gets away from the faulty block. After that, any minimal adaptive routing can be used again. The minimal routing in 2-D tori is similar to that in 2-D meshes if at the beginning of the routing a conversion is made from a 2-D torus to a 2-D mesh. The fault-tolerant minimal routing in 3-D meshes can be done in a similar way. In the tree-based multicasting in 2-D and 3-D meshes, a time-step optimal and traffic-step suboptimal algorithm is proposed. Several heuristic strategies are presented to resolve a conflict, which are compared by simulations. A path-based fault-tolerant deadlock-free multicast algorithm in 2-D meshes with inter-block distance of at least three is presented to solve the deadlock problem in tree-based multicast algorithms. The approach is then extended to 3-D meshes and to inter-block distance of at least two in 2-D meshes. The path is Hamiltonian that is only updated locally in the neighborhood of a faulty block when a faulty block is encountered. Two virtual channels are used to prevent deadlock in 2-D and 3-D meshes with inter-block (inter-cube) distance of at least three and two more virtual channels are added if the inter-block distance is at least two.
Show less
Date Issued: 1999
PURL: http://purl.flvc.org/fcla/dt/12597
Subject Headings: Fault-tolerant computing, Computer algorithms
Format: Document (PDF)

Title: THE IMPLEMENTATION OF SOFTWARE FAULT TOLERANCE IN THE INTEL 80286 PROCESSOR.
Creator: OZAKI, BRENDA., 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 the architecture of the Intel 80286 microprocessor may be used to implement fault tolerant software structures. The Multi-Micro Programming Line, MML, and the Intel 80286 kernel, K286, are used as tools to illustrate the implementation of software fault tolerance in an 80286 environment. The recovery metaprogram approach is supported by software layers which use the privilege levels in the 80286. Implementation of recovery blocks, N-version programming, exceptions,...
Show moreThis thesis analyzes how the architecture of the Intel 80286 microprocessor may be used to implement fault tolerant software structures. The Multi-Micro Programming Line, MML, and the Intel 80286 kernel, K286, are used as tools to illustrate the implementation of software fault tolerance in an 80286 environment. The recovery metaprogram approach is supported by software layers which use the privilege levels in the 80286. Implementation of recovery blocks, N-version programming, exceptions, and conversations using a recovery metaprogram are covered. While the details are specific to the 80286 architecture, the general results apply to any architecture with three or more rings of privilege and a segmented virtual memory using descriptors.
Show less
Date Issued: 1987
PURL: http://purl.flvc.org/fcla/dt/14399
Subject Headings: Fault-tolerant computing, Intel 80286 (Microprocessor)
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: Massively parallel fault simulator.
Creator: Parigi, Eshwar V., Florida Atlantic University, Mazuera, Olga, College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
Abstract/Description: Fault simulators can be used for various purposes, such as the determination of the Fault coverage, the Automatic test pattern generation and the preparation of the Fault dictionaries. As the size of the digital circuits increases, the number of gates present increases and the time taken for fault simulation also increases. In order to reduce the fault simulation time, massively parallel computers are being used. We have developed a fault simulator on MASPAR, a massively parallel Single...
Show moreFault simulators can be used for various purposes, such as the determination of the Fault coverage, the Automatic test pattern generation and the preparation of the Fault dictionaries. As the size of the digital circuits increases, the number of gates present increases and the time taken for fault simulation also increases. In order to reduce the fault simulation time, massively parallel computers are being used. We have developed a fault simulator on MASPAR, a massively parallel Single Instruction Multiple Data machine, based on the principles of parallel pattern parallel fault simulation. In order to eliminate the limitation of limited memory on MASPAR, we have designed an algorithm which reduces the amount of memory required for storing the circuit. We have implemented these algorithms in two different ways. These algorithms were tested on ISCAS85 benchmark circuits. The results have shown an improvement over other parallel algorithms.
Show less
Date Issued: 1994
PURL: http://purl.flvc.org/fcla/dt/15050
Subject Headings: Fault-tolerant computing, Parallel processing (Electronic computers)
Format: Document (PDF)

Title: A methodology for object-oriented modeling and design of real-time, fault-tolerant systems.
Creator: Hancock, Debera R., Florida Atlantic University, Fernandez, Eduardo B.
Abstract/Description: Many methodologies for software modeling and design include some form of static and dynamic modeling to describe the structural and behavioral views respectively. Modeling and design of complex real-time software systems requires notations for describing concurrency, asynchronous event handling, communication between independent machines, timing properties, and accessing real time. Function-oriented structured analysis methodologies such as Ward and Mellor's SA/RT and Harel's Statecharts have...
Show moreMany methodologies for software modeling and design include some form of static and dynamic modeling to describe the structural and behavioral views respectively. Modeling and design of complex real-time software systems requires notations for describing concurrency, asynchronous event handling, communication between independent machines, timing properties, and accessing real time. Function-oriented structured analysis methodologies such as Ward and Mellor's SA/RT and Harel's Statecharts have provided extensions for real-time system modeling. Dynamic modeling of real time systems using object-oriented methodologies also requires extensions to the traditional state machine notations in order to convey the real time system characteristics and constraints. Shaw's Communicating Real Time State Machines (CRSM's), Harel's O-Chart notations, and the Octopus methodology provide methods for modeling real-time systems consistent with object-oriented methods. This thesis proposes an object-oriented analysis and design methodology that augments the traditional Object Modeling Technique (OMT) dynamic model with real-time extensions based on high-level parallel machines and communication notations from CRSM. An example of the proposed methodology is provided using a realistic but hypothetical example of an automated passenger train system. A design refinement step is included for fault tolerant considerations. An evaluation of the proposed methodology with its extended notations is provided.
Show less
Date Issued: 1997
PURL: http://purl.flvc.org/fcla/dt/15405
Subject Headings: Object-oriented methods (Computer science), Fault-tolerant computing, Real-time programming
Format: Document (PDF)

Title: A multiprocessor simulator to test fault detection and reconfiguration algorithms.
Creator: Bhathija, Unmesh Jethanand., Florida Atlantic University, Fernandez, Eduardo B.
Abstract/Description: In recent years multiprocessor systems are becoming increasingly important in critical applications. In particular, their fault tolerance properties are of great importance for their ability to be used in these type of applications. We have developed a multiprocessor simulator that can be used to test different fault detection algorithms. The processors must have four communication links. This simulator operates by passing messages between processors. An algorithm was developed for routing...
Show moreIn recent years multiprocessor systems are becoming increasingly important in critical applications. In particular, their fault tolerance properties are of great importance for their ability to be used in these type of applications. We have developed a multiprocessor simulator that can be used to test different fault detection algorithms. The processors must have four communication links. This simulator operates by passing messages between processors. An algorithm was developed for routing the messages among the processors. The simulator can also be used to try different reconfiguration strategies. In particular we have tested Malek's comparison algorithm using different multiprocessor configurations. We also developed a program which determines the configuration of an unknown network of transputers.
Show less
Date Issued: 1990
PURL: http://purl.flvc.org/fcla/dt/14622
Subject Headings: Multiprocessors, Fault-tolerant computing
Format: Document (PDF)

Hypercube networks (Computer networks) (7)	+ -
Multiprocessors (5)	+ -
Parallel processing (Electronic computers) (5)	+ -
Computer architecture (4)	+ -
Computer software--Reliability (3)	+ -

Algorithms (2)	+ -
Computer algorithms (2)	+ -
Computer networks (2)	+ -
Electronic data processing--Distributed processing (2)	+ -
Electronic digital computers--Reliability (2)	+ -
Algorithms--Data procedssing (1)	+ -
Computers--Reliability (1)	+ -
Embedded computer systems (1)	+ -
Flight control (1)	+ -
Integrated circuits--Very large scale integration (1)	+ -
Integratged circuits--Very large scale integration (1)	+ -
Intel 80286 (Microprocessor) (1)	+ -
Memory hierarchy (Computer science) (1)	+ -
Object-oriented methods (Computer science) (1)	+ -
Polyimides (1)	+ -
Real-time data processing (1)	+ -
Real-time programming (1)	+ -
Submersibles--Automatic control (1)	+ -
System design (1)	+ -
Trees (Graph theory) (1)	+ -

College of Engineering and Computer Science (19)	+ -
Department of Computer and Electrical Engineering and Computer Science (18)	+ -
Wu, Jie (13)	+ -
Fernandez, Eduardo B. (7)	+ -
Bhathija, Unmesh Jethanand. (1)	+ -

Brown, Larry. (1)	+ -
Buechler, Peter Charles. (1)	+ -
Chen, Xiao. (1)	+ -
Department of Ocean and Mechanical Engineering (1)	+ -
Dunn, Stanley E. (1)	+ -
GAO, LIXIN. (1)	+ -
Glenn, William E. (1)	+ -
Goyal, Praduemn K. (1)	+ -
Hancock, Debera R. (1)	+ -
He, Fusen. (1)	+ -
Huang, Chien-Jen (1)	+ -
Huang, Ke. (1)	+ -
Jiang, Zhen. (1)	+ -
Leu, Shao-Wei. (1)	+ -
Luo, Yinqiu. (1)	+ -
Mahanthi, Gangadhar. (1)	+ -
Mahgoub, Imad (1)	+ -
Mazuera, Olga (1)	+ -
Monteiro, Pedro Cox de Sousa. (1)	+ -
More, Hemant B. (1)	+ -
OZAKI, BRENDA. (1)	+ -
Parigi, Eshwar V. (1)	+ -
Qian, Haifeng. (1)	+ -
Rae, Graeme John Stuart. (1)	+ -

Search In

Pages

Pages

Sort Results By:

Narrow results by:

Collection

Topical Subject

Genre

Type of Resource

Language

Creator

Format

Owner