31082095
Fault-Detection by Result-Checking for the Eigenproblem
This paper proposes a new fault detection mechanism for the computation of eigenvalues and eigenvectors, the so called eigenproblem, for which no such scheme existed before, to the best of our knowledge. It consists of a number of assertions that can be executed on the results of the computation to determine their correctness. The proposed scheme follows the Result Checking principle, since it does not depend on the particular numerical algorithm used. It can handle both real and complex matrices, symmetric or not. Many practical issues are handled, like rounding errors and eigenvalue ordering, and a practical implementation was built on top of unmodified routines of the well-known LAPACK library. The proposed scheme is simultaneously very efficient, with less than 2% performance overhead for medium to large matrices, very effective, since it exhibited a fault coverage greater than 99.7% with a confidence level of 99%, when subjected to extensive fault-injection experiments, and very easy to adapt to other libraries of mathematical routines besides LAPACK.
11507520
Web-based Metacomputing with JET
11033391
System-level versus user-defined checkpointing
Checkpointing and rollback recovery is a very effective technique to tolerate transient faults and preventive shutdowns. In the past, most of the checkpointing schemes published in the literature were supposed to be transparent to the application programmer and implemented at the operating-system level. In recent years, there has been some work on higher-level forms of checkpointing. In this second approach, the user is responsible for the checkpoint placement and is required to specify the checkpoint contents. We compare the two approaches: system-level and user-defined checkpointing. We discuss the pros and cons of both approaches and we present an experimental study that was conducted on a commercial parallel machine.
35292815
WPVM: parallel computing for the people
This paper presents WPVM, a PVM implementation for the “MS Windows” — Microsoft Windows Operating System. WPVM stands for “Windows Parallel Virtual Machine” and intends to exploit the potential computational power of the small and medium PC LANs that proliferate in corporations and universities. As the original PVM [1–2], WPVM creates the abstraction of a parallel machine from a cluster of computers connected by a network. This virtual machine appears as a single and manageable resource to the programmer. The difference is that the target machines for WPVM are personal computers with MS Windows instead of UNIX machines. However, this system is compatible with the original PVM, meaning that we can use virtual machines composed simultaneously of UNIX and MS Windows machines.
35428904
Portable checkpointing and recovery
This paper presents a checkpointing scheme that was implemented in a parallel library that runs on top of CHIMP/MPI. The main goals of the checkpointing mechanism are portability and efficiency. It runs on every platform supported by MPI in a machine-independent way. The scheme allows the migration of checkpoints and offers a flexible recovery mechanism based on data-reconfiguration. Some performance results will be presented at the end of the paper together with some techniques that can be used to increase the efficiency of the checkpointing mechanism.
22782109
A Fault-Tolerant Mechanism for Simple Controllers
There are many industrial controllers where no systematic fault-tolerant mechanisms are included because of cost constraints. This paper addresses that problem by making a proposal for a simple and low-cost fault-tolerant technique, yet very effective, that can be used even in the simplest controllers. The mechanism is able of tolerating both hardware and software faults. It uses behaviour-based error detection, with checkpointing and rollback, to give resiliency to the application. The programs are made of possibly non-deterministic processes that communicate solely by messages. The technique, called RP-Actions, also guarantees that the recovery is domino-effect free. Software bugs are caught by acceptance tests as in recovery blocks. Forward error recovery is used for time, since time cannot be rolled back. Several implementations of the proposed mechanisms were made — we present in this paper some important results.
2088546
Combining algorithmic debugging and program slicing
Currently, program slicing and algorithmic debugging are two of the most relevant debugging techniques for declarative languages. They help programmers to find bugs in a semiautomatic manner. On the one hand, program slicing is a technique to extract those program fragments that (potentially) affect the values computed at some point of interest. On the other hand, algorithmic debugging is able to locate a bug by automatically generating a series of questions and processing the programmer's answers. In this work, we show for functional languages how the combination of both techniques produces a more powerful debugging schema that reduces the number of questions that programmers must answer to locate a bug
1093169
An Embedded Language Approach to Router Specification in Curry
The development of modern routers require a significant effort to be designed, built, and verified. While hardware routers are faster, they are difficult to configure and maintain. Software routers, on the other hand, are slower but much more flexible, easier to configure and maintain, less expensive, etc. Recently, a modular architecture and toolkit for building software routers and other packet processors has been introduced: the Click system. It includes a specification language with features for declaring and connecting router elements and for designing abstractions.
62642642
GRASP—a new search algorithm for satisfiability
This paper introduces GRASP (Generic seaRch Algorithm for the Satisfiability Problem), an integrated algorithmic framework for SAT that unifies several previously proposed search-pruning techniques and facilitates identification of additional ones. GRASP is premised on the inevitability of conflicts during search and its most distinguishing feature is the augmentation of basic backtracking search with a powerful conflict analysis procedure. Analyzing conflicts to determine their causes enables GRASP to backtrack non-chronologically to earlier levels in the search tree, potentially pruning large portions of the search space. In addition, by "recording" the causes of conflicts, GRASP can recognize and preempt the occurrence of similar conflicts later on in the search. Finally, straightforward bookkeeping of the causality chains leading up to conflicts allows GRASP to identify assignments that are necessary for a solution to be found. Experimental results obtained from a large number of benchmarks, including many from the field of test pattern generation, indicate that application of the proposed conflict analysis techniques to SAT algorithms can be extremely effective for a large number of representative classes of SAT instances.
568204
Selecting Landmark Points for Sparse Manifold Learning
There has been a surge of interest in learning non-linear manifold models to approximate high-dimensional data. Both for computational complexity reasons and for generalization capability, sparsity is a desired feature in such models. This usually means dimensionality reduction, which naturally implies estimating the intrinsic dimension, but it can also mean selecting a subset of the data to use as landmarks, which is especially important because many existing algorithms have quadratic complexity in the number of observations. This paper presents an algorithm for selecting landmarks, based on LASSO regression, which is well known to favor sparse approximations because it uses regularization with an l1 norm. As an added benefit, a continuous manifold parameterization, based on the landmarks, is also found. Experimental results with synthetic and real data illustrate the algorithm.
42287277
A Divide-and-Conquer Approach to Acquire Syntactic Categories
In this paper we propose an unsupervised strategy for learning syntactic information that proceeds in several steps. First, we identify, cluster, and classify function words from unannotated corpora. Then, the acquired information is used in two different learning processes. On the one hand, it is used to learn morpho-syntactic categories of nouns and, on the other, it turns out to be useful to also induce syntactic/semantic relationships between content words. Experiments performed on Portuguese and English corpora are reported.