The high abstraction level of Spectrum-based Fault Localization (SFL) reasoning, on the one hand, offers the advantage of a model-free approach to diagnosis, while, on the other, reduces the inherently limited testability of many hardware and software systems. Thus, along with substantial complexity gains, SFL exhibits limited diagnostic performance, compared to Model-Based Diagnosis. This paper describes two algorithms (Lion and Tiger) that exploit low cost heuristics to determine the best location to insert additional test oracles (monitors, probes, invariants) so as to increase the observability within the systems. Experiments show that even simple algorithms can considerably improve SFL's diagnostic accuracy.

k-out-of-nsystems with cold standby units are typically studied for unit lifetime distributions that allow analytical tractability. Often, however, these distributions differ significantly from reality. In this paper, we present an analytical approach to compute the mean failure time fork-out-of-nsystems with a single cold standby unit for the wide class of lifetime distributions that can be captured by the Pearson distribution. The method requires the first four statistical moments of the unit's lifetime distribution to be given, and computes the mean failure time using the Pearson distribution as an intermediate vehicle during the numerical integration. Experimental results for various instances of the Weibull distribution show that the numerical accuracy of the approach is high, with less than 0.5 percent error across a large range ofk-out-of-nsystems.

In the printed version of the above titled paper (ibid., vol. 61, no. 2, pp. 526-532, June 2012), a conversion error printed incorrect and misnumbered equations. The correct equations are presented here.

We present a spectrum-based, sequential software debugging approach coined Sequoia, that greedily selects tests out of a suite of tests to narrow down the set of diagnostic candidates with a minimum number of tests. Sequoia handles multiple faults, that can be intermittent, at polynomial time and space complexity, due to a novel, approximate diagnostic entropy estimation approach, which considers the subset of diagnoses that cover almost all Bayesian posterior probability mass. Synthetic experiments show that Sequoia achieves much better diagnostic uncertainty reduction compared to random test sequencing.Real programs, taken from the Software Infrastructure Repository, confirm Sequoia's better performance, with a test reduction up to 80% compared to random test sequences.

In practically all development processes, regression tests are used to detect the presence of faults after a modification. If faults are detected, a fault localization algorithm can be used to reduce the manual inspection cost. However, while using test case prioritization to enhance the rate of fault detection of the test suite (e.g., statement coverage), the diagnostic information gain per test is not optimal, which results in needless inspection cost during diagnosis. We present RAPTOR, a test prioritization algorithm for fault localization, based on reducing the similarity between statement execution patterns as the testing progresses. Unlike previous diagnostic prioritization algorithms, RAPTOR does not require false negative information, and is much less complex. Experimental results from the Software Infrastructure Repository's benchmarks show that RAPTOR is the best technique under realistic conditions, with average cost reductions of 40% with respect to the next best technique, with negligible impact on fault detection capability.

SUMMARY During regression testing, test prioritization techniques select test cases that maximize the confidence on the correctness of the system when the resources for quality assurance (QA) are limited. In the event of a test failing, the fault at the root of the failure has to be localized, adding an extra debugging cost that has to be taken into account as well. However, test suites that are prioritized for failure detection can reduce the amount of useful information for fault localization. This deteriorates the quality of the diagnosis provided, making the subsequent debugging phase more expensive, and defeating the purpose of the test cost minimization. In this paper we introduce a new test case prioritization approach that maximizes the improvement of the diagnostic information per test. Our approach minimizes the loss of diagnostic quality in the prioritized test suite. When considering QA cost as a combination of testing cost and debugging cost, on our benchmark set, the results of our test case prioritization approach show reductions of up to 60% of the overall combined cost of testing and debugging, compared with the next best technique. Copyright © 2011 John Wiley & Sons, Ltd.

Test cost minimisation approaches have traditionally been devoted to minimising ``execution costs'', while maximising coverage or reliability. However, in a runtime testing context, the amount of coverage or reliability that can be achieved, in other words, the system's Runtime Testability, is limited by the adverse effects that the interferences of runtime tests have on the system. Supporting runtime testing, therefore, introduces an additional cost in ``preparatory'' activities in software, (e.g., testable components) and in hardware (e.g., more memory), before certain runtime tests can be executed. In this paper we present a low-complexity, cost minimisation algorithm for the optimal selection of preparation activities, based on a near-optimal trade-off between preparation cost and a structure-based measurement of Runtime Testability, coined the Runtime Testability Metric (RTM). We perform a theoretical and empirical validation of RTM, showing that RTM is indeed a valid, and reasonably accurate measurement with ratio scale. We also present empirical data demonstrating the near-optimal performance at a low computational cost of our algorithm.

We propose a StochAstic Fault diagnosis AlgoRIthm, called SAFARI, which trades off guarantees of computing minimal diagnoses for computational efficiency. We empirically demonstrate, using the 74XXX and ISCAS-85 suites of benchmark combinatorial circuits, that SAFARI achieves several orders-of-magnitude speedup over two well-known deterministic algorithms, CDA* and HA*, for multiple-fault diagnoses; further, SAFARI can compute a range of multiple-fault diagnoses that CDA* and HA* cannot. We also prove that SAFARI is optimal for a range of propositional fault models, such as the widely-used weak-fault models (models with ignorance of abnormal behavior). We discuss the optimality of SAFARI in a class of strong-fault circuit models with stuck-at failure modes. By modeling the algorithm itself as a Markov chain, we provide exact bounds on the minimality of the diagnosis computed. SAFARI also displays strong anytime behavior, and will return a diagnosis after any non-trivial inference time.

Model-based diagnostic reasoning often leads to a large number of diagnostic hypotheses. The set of diagnoses can be reduced by taking into account extra observations (passive monitoring), measuring additional variables (probing) or executing additional tests (sequential diagnosis/test sequencing). In this paper we combine the above approaches with techniques from Automated Test Pattern Generation (ATPG) and Model-Based Diagnosis (MBD) into a framework called FRACTAL (FRamework for ACtive Testing ALgorithms). Apart from the inputs and outputs that connect a system to its environment, in active testing we consider additional input variables to which a sequence of test vectors can be supplied. We address the computationally hard problem of computing optimal control assignments (as defined in FRACTAL) in terms of a greedy approximation algorithm called FRACTAL-G. We compare the decrease in the number of remaining minimal cardinality diagnoses of FRACTAL-G to that of two more FRACTAL algorithms: FRACTAL-ATPG and FRACTAL-P. FRACTAL-ATPG is based on ATPG and sequential diagnosis while FRACTAL-P is based on probing and, although not an active testing algorithm, provides a baseline for comparing the lower bound on the number of reachable diagnoses for the FRACTAL algorithms. We empirically evaluate the trade-offs of the three FRACTAL algorithms by performing extensive experimentation on the ISCAS85/74XXX benchmark of combinational circuits.

Fault diagnosis approaches can generally be categorized into spectrum-based fault localization (SFL, correlating failures with abstractions of program traces), and model-based diagnosis (MBD, logic reasoning over a behavioral model). Although MBD approaches are inherently more accurate than SFL, their high computational complexity prohibits application to large programs. We present a framework to combine the best of both worlds, coined BARINEL. The program is modeled using abstractions of program traces (as in SFL) while Bayesian reasoning is used to deduce multiple-fault candidates and their probabilities (as in MBD). A particular feature of BARINEL is the usage of a probabilistic component model that accounts for the fact that faulty components may fail intermittently. Experimental results on both synthetic and real software programs show that BARINEL typically outperforms current SFL approaches at a cost complexity that is only marginally higher. In the context of single faults this superiority is established by formal proof.

Locating software components which are responsible for observed failures is the most expensive, error-prone phase in the software development life cycle. Automated diagnosis of software faults can improve the efficiency of the debugging process, and is therefore an important process for the development of dependable software. In this paper we present a toolset for automatic fault localization, dubbed Zoltar, which hosts a range of spectrum-based fault localization techniques featuring BARINEL, our latest algorithm. The toolset provides the infrastructure to automatically instrument the source code of software programs to produce runtime data, which is subsequently analyzed to return a ranked list of diagnosis candidates. Aimed at total automation (e.g., for runtime fault diagnosis), Zoltar has the capability of instrumenting the program under analysis with fault screeners as a run-time replacement for design-time test oracles.

In many practical engineering circumstances, systems reliability analysis is complicated by the fact that the failure time distributions of the constituent subsystems cannot be accurately modeled by standard distributions. In this paper, we present a low-cost, compositional approach based on the use of the first four statistical moments to characterize the failure time distributions of the constituent components, subsystems, and top-level system. The approach is based on the use of Pearson distributions as an intermediate analytical vehicle, in terms of which the constituent failure time distributions are approximated. The analysis technique is presented for -out-of- systems with identical subsystems, series systems with different subsystems, and systems exploiting standby redundancy. The moment-in-moment-out approach allows for the analysis of systems with arbitrary hierarchy, and arbitrary (unimodal) failure time distributions, provided the subsystems are independent such that the resulting failure time can be expressed in terms of sums or order statistics. The technique consistently exhibits very good accuracy (on average, much less than 1 percent error) at very modest computing cost.

Automated diagnosis of software faults can improve the efficiency of the debugging process, and is therefore an important technique for the development of dependable software. In this paper we study different similarity coefficients that are applied in the context of a program spectral approach to software fault localization (single programming mistakes). The coefficients studied are taken from the systems diagnosis/automated debugging tools Pinpoint, Tarantula, and AMPLE, and from the molecular biology domain (the Ochiai coefficient). We evaluate these coefficients on the Siemens Suite of benchmark faults, and assess their effectiveness in terms of the position of the actual fault in the probability ranking of fault candidates produced by the diagnosis technique. Our experiments indicate that the Ochiai coefficient consistently outperforms the coefficients currently used by the tools mentioned. In terms of the amount of code that needs to be inspected, this coefficient improves 5% on average over the next best technique, and up to 30% in specific cases

Accurate fault diagnosis is a crucial success factor in achieving system dependability. The unambiguity of a diagnosis is critically dependent on the number of observations available for the inference process. Observability, therefore, significantly determines diagnostic quality. In this paper we introduce the notion of a temporal and a spatial dimension to observability of Model-Based Diagnosis, and study their impact on diagnostic quality. We use uncertainty, measured as the expected entropy of a diagnosis after observation, as quality metric. Empirical results confirm that for both dimensions an increase in observability always leads to a reduction of expected, diagnostic entropy. However, the temporal and the spatial reduction factors differ in that they decrease and increase respectively with increasing observability. The results from this study are useful for performing practical trade-offs between additional sensor placements and longer measurement horizons.

Current analytic solutions to the execution time distribution of a parallel composition of tasks having stochastic execution times are computationally complex, except for a limited number of distributions. In this paper, we present an analytical solution based on approximating execution time distributions in terms of the first four statistical moments. This low-cost approach allows the parallel execution time distribution to be approximated at ultra-low solution complexity for a wide range of execution time distributions. The accuracy of our method is experimentally evaluated for synthetic distributions as well as for task execution time distributions found in real parallel programs and kernels (NAS-EP, SSSP, APSP, Splash2-Barnes, PSRS, and WATOR). Our experiments show that the prediction error of the mean value of the parallel execution time for N-ary parallel composition is in the order of percents, provided the task execution time distributions are sufficiently independent and unimodal.

Performance prediction is an important engineering tool that provides valuable feedback on design choices in program synthesis and machine architecture development. We present an analytic performance modeling approach aimed to minimize prediction cost, while providing a prediction accuracy that is sufficient to enable major code and data mapping decisions. Our approach is based on a performance simulation language called PAMELA. Apart from simulation, PAMELA features a symbolic analysis technique that enables PAMELA models to be compiled into symbolic performance models that trade prediction accuracy for the lowest possible solution cost. We demonstrate our approach through a large number of theoretical and practical modeling case studies, including six parallel programs and two distributed-memory machines. The average prediction error of our approach is less than 10 percent, while the average worst-case error is limited to 50 percent. It is shown that this accuracy is sufficient to correctly select the best coding or partitioning strategy. For programs expressed in a high-level, structured programming model, such as data-parallel programs, symbolic performance modeling can be entirely automated. We report on experiments with a PAMELA model generator built within a dataparallel compiler for distributed-memory machines. Our results show that with negligible program annotation, symbolic performance models are automatically compiled in seconds, while their solution cost is in the order of milliseconds.

In compile-time task scheduling for distributed-memory systems, list scheduling is generally accepted as an attractive approach, since it pairs low cost with good results. List-scheduling algorithms schedule tasks in order of their priority. This priority can be computed either (1) statically, before the scheduling, or (2) dynamically, during the scheduling. In this paper, we show that list scheduling with statically-computed priorities (LSSP) can be performed at a significantly lower cost than existing approaches, without sacrificing performance. Our approach is general, i.e. it can be applied to any LSSP algorithm. The low complexity is achieved by using low-complexity methods for the most time-consuming parts in list-scheduling algorithms, i.e. processor selection and task selection, preserving the criteria used in the original algorithms. We exemplify our method by applying it to the MCP (Modified Critical Path) algorithm. Using an extension of this method, we can also reduce the time complexity of a particular class of list scheduling with dynamic priorities (LSDP) [including algorithms such as DLS (Dynamic Level Scheduling), ETF (Earliest Task First) and ERT (Earliest Ready Task)]. Our results confirm that the modified versions of the list-scheduling algorithms obtain a performance comparable to their original versions, yet at a significantly lower cost. We also show that the modified versions of the list-scheduling algorithms consistently outperform multi-step algorithms, such as DSC-LLB (Dynamic Sequence Clustering with List Load Balancing), which also have higher complexity and clearly outperform algorithms in the same class of complexity, such as CPM (Critical Path Method).

A relatively new trend in parallel programming scheduling is the so-called mixed task and data scheduling. It has been shown that mixing task and data parallelism to solve large computational applications often yields better speedups compared to either applying more task parallelism or pure data parallelism. In this paper we present a new compile-time heuristic, named critical path and allocation (CPA), for scheduling data-parallel task graphs. Designed to have a very low cost, its complexity is much lower compared to existing approaches, such as TSAS, TwoL or CPR, by one order of magnitude or even more. Experimental results based on graphs derived from real problems as well as synthetic graphs, show that the performance loss of CPA relative to the above algorithms does not exceed 50%. These results are also confirmed by performance measurements of two real applications (i.e., complex matrix multiplication and Strassen matrix multiplication) running on a cluster of workstations.

It is well-known that mixing task and data parallelism to solve large computational applications often yields better speedups compared to either applying pure task parallelism or pure data parallelism. Typically, the applications are modeled in terms of a dependence graph of coarse-grain data-parallel tasks, called a data-parallel task graph. In this paper we present a new compile-time heuristic, named Critical Path Reduction (CPR), for scheduling data-parallel task graphs. Experimental results based on graphs derived from real problems as well as synthetic graphs, show that CPR achieves higher speedup compared to other well-known existing scheduling algorithms, at the expense of some higher cost. These results are also confirmed by performance measurements of two real applications (i.e., complex matrix multiplication and Strassen matrix multiplication) running on a cluster of workstations.

This paper describes a novel compile-time list-based task scheduling algorithm for distributed-memory systems, called Fast Load Balancing (FLB). Compared to other typical list scheduling heuristics, FLB drastically reduces scheduling time complexity to O(V(log(W)+log (P))+E), where V and E are the number of tasks and edges in the task graph, respectively, W is the task graph width and P is the number of processors. It is proven that FLB is essentially equivalent to the existing ETF scheduling algorithm of O(W(E+V)P) time complexity. Experiments also show that FLB performs equally to other one-step algorithms of much higher cost, such as MCP. Moreover, FLB consistently outperforms multi-step algorithms such as DSC-LLB that also have higher cost.

This paper presents a novel heuristic, called Fast Critical Path (FCP), intended as a compile-time scheduling algorithm on a distributed-memory system.While similar to existing list scheduling algorithms, FCP has two important differences: (a) it does not sort all the tasks at the beginning but maintains only a limited number of tasks sorted at any given time, and (b) instead of considering all processors as possible target for a given task, the choice is restricted to either the processor from which the last messages to the given task arrives or the processor which becomes idle the earliest.As a result, the time complexity is drastically reduced to O(V log (P) + E), where V and E are the number of tasks and edges in the task graph, respectively, and P is the number of processors.We demonstrate through theory and experiments that FCP performs equally to existing list scheduling algorithms of much higher complexity. *This research is part of the Automap

This paper proposes a new compile time scheduling algorithm for distributed-memory systems, called Global Load Balancing (GLB). GLB is intended as the second step in the multi-step class of scheduling algorithms. Experimental results show that compared with known scheduling algorithms of the same low-cost complexity, the proposed algorithm improves schedule lengths up to 30%. Compared to algorithms with higher order complexities, the typical schedule lengths obtained with the proposed algorithm are at most twice longer.

Presents a method to explore the design space of multi-threaded architectures using PAMELA (PerformAnce ModEling LAnguage). The domain of applications we consider is digital signal processing (DSP), where high performance is derived by exploiting both fine-grain and coarse-grain parallelism in the application. The modeling scheme takes an unified view of both fine-grain and coarse-grain parallelism in a given application to measure the performance of the architecture. The application-written using a high-level language-is compiled, and a trace generated for benchmark data in terms of the instruction set architecture of the processor. The generated trace is for a single uni-threaded, uni-processor system. This trace is pre-processed and re-targeted to generate multi-threaded architecture-specific PAMELA code. Using a material-oriented approach, the resulting PAMELA code is executed to evaluate various architecture options over the entire design space iteratively, subject to implementation constraints. We demonstrate the suitability and simplicity of the approach with an example.

In automatic mapping of parallel programs to target parallel machines the efficiency of the compile-time cost estimation needed to steer the optimization process is highly dependent on the choice of programming model. Recently a new parallel programming model, called SPC, has been introduced that specifically aims at the efficient computation of reliable cost estimates, paving the way for automatic mapping. In SPC all algorithm level parallelism is explicitly specified, relying on compile-time transformation of the possibly unbounded algorithm level (data) parallelism to that of the actual target machine. In this paper we present SPC's process-algebraic framework in terms of which we demonstrate that the transformations needed to efficiently support unbounded process parallelism at program level are straightforward.

In automatic, retargetable compilation low-cost, analytic cost estimation techniques are crucial in order to efficiently steer the optimization process.Programming models aimed at optimum expressiveness of parallelism, however, are not amenable to static cost estimation.We present a new coordination model, called SPC, that imposes specific restrictions in the synchronization structures that can be programmed.Imposing these restrictions enables the efficient computation of reliable cost estimations paving the way for automatic optimization.Regarding SPC's limited expressiveness we present a conjecture stating that the loss of parallelism when programming in SPC is typically limited to a constant factor of 2 compared to the unrestricted case.This limited loss is outweighed by the unlocked potential of automatic performance optimization as well as the portability that is achieved.We demonstrate how SPC enables automatic program optimizations through a compilation caSe study involving a line relaxation kernel on a distributedmemory machine.

We present Spar, a programming language for semi-automatic parallel programming, in particular for the programming of array-based applications. The language has been designed as part of the Automap project, in which a compiler and runtime system are being developed for distributed-memory systems. As suggested by its name, Automap aims at completely automatic code and data mapping at either compile time or runtime. This relieves the programmer of a difficult task, and makes Spar programs completely portable. Apart from a few minor modifications, Spar is a superset of Java. This provides Spar with a modern, solid, language as its basis, and makes Spar more accessible. Spar extends Java with constructs forparallel programming, extensive support for array manipulation, and a number of other powerful language extensions. © 1997 John Wiley & Sons, Ltd.

A technique is described to automatically compile performance models in the course of program translation. The performance models are fully symbolic in order to preserve as much diagnostic information as possible. Although compiled statistically, the models account for the effects of resource contention, due to the introduction of a novel algorithm within the symbolic compilation scheme. It is shown that the compilation approach fundamentally outperforms traditional static estimation procedures in terms of precision at a negligible increase in cost. This claim is illustrated by a case study of an LU factorization algorithm on a multiprocessor.

In this paper we present a new methodology for the performance prediction of parallel programs on parallel platforms ranging from shared-memory to distributed-memory (vector) machines. The methodology comprises a procedural program and machine specification paradigm based on PAMELA (PerformAnce ModEling LAnguage), along with a performance calculus, called “serialization analysis”. This calculus extends conventional parallel program analysis technology by explicitly accounting for resource contention, yet at the low evaluation cost typical for static techniques. It is shown that, where conventional techniques introduce fundamental errors, predictions from serialization analysis remain realistic. Apart from the merits of the methodology itself, this high reliability/cost ratio makes PAMELA an attractive candidate for compile-time application within the performance prediction hierarchy often found in parallel programming environments.

This paper describes a translation method for the automatic parallelization of programs based on a separately specified representation of the data. The method unifies the concept of data-representation on the algorithm-level as well as machine-level, based on the so-called view concept. It is shown that given a decomposition of the data, application of the translation method to the view-based Booster programming language results in efficient SPMD-code for distributed- as well as shared-memory architectures. It will be argued that the method is not restricted to Booster, but can also be applied to other languages.