Processor arrays, featuring modularity, regular interconnection, and high parallelism, are well suited for VLSI/WSI implementation and specific applications with high computational requirements. Error detection and recovery are important for some applications of processor arrays. Concurrent error detection (CED) techniques, which check normal system operations, are designed to detect errors caused by transient and intermittent faults, However, CED techniques typically suffer from costly hardware penalties or performance costs. This paper describes the periodic application of concurrent error detection (PACED) technique which allows the performance costs incurred through the use of time-redundant CED in processor array architectures to be reduced. The application of CED is varied in both time and space to provide probabilistic detection of errors in processor arrays. The probability of correctness of outputs from processor arrays is studied. Formulae are derived that predict, upon error detection, the amount of possibly erroneous output, for single processors, linear arrays and 2-dimensional mesh processor arrays. The results indicate that the error coverage can be surprisingly high when PACED is applied in processor arrays, e.g., 95% for checking performed 50% of the time.

Redundant Arrays of Distributed Disks (RADD) can be used in a distributed computing system or database system to provide recovery in the presence of disk crashes and temporary and permanent failures of single sites. In this paper, we look at the problem of partitioning the sites of a distributed storage system into redundant arrays in such a way that the communication costs for maintaining the parity information are minimized. We show that the partitioning problem is NP-hard. We then propose and evaluate several heuristic algorithms for finding approximate solutions. Simulation results show that significant reduction in remote parity update costs can be achieved by optimizing the site partitioning scheme.

We study the performance of two redun dant disk array organizations in a transaction processing environment and compare it to that of mirrored disk organi zations and organizations using no striping and no redun dancy. Redundant disk arrays and mirrored disks are used for providing rapid recovery from mediafailures in systems requiring high availability. The disk array organizations examined are: data striping with rotated parity (RAIDS) and Parity Striping. RAIDS provides high data transfer rates by striping the data over multiple disks. It also pro vides better load balancing over the disks in the array. At the same time, data striping increases disk arm use which can lead to longer queuing delays. In transaction process ing environments, because of the nature of I/O requests, namely a large number of small size requests, disk arms are a more valuable resource than data transfer bandwidth. Hence, parity striping was proposed as an alternative to RAIDS. It provides rapid recovery from failure at the same low storage cost without interleaving the data over multiple disks. In this study, we use data from a large scale commer cial transaction processing site to evaluate and compare the performance of the above organizations. We consider both non-cached systems as well as systems using a non-volatile cache in the controller.

The authors propose a method for using redundant disk arrays to support rapid recovery from system crashes and transaction aborts in addition to their role in providing media failure recovery. A twin-page scheme is used to store the parity information in the array, making it possible to keep the old version of the parity along with the new version. The old version of the parity is used to undo updates performed by aborted transactions or by transactions interrupted by a system failure. Using an analytical model, it is shown that the proposed method achieves a significant increase in the throughput of database systems using redundant disk arrays by reducing the number of recovery operations needed to maintain the consistency of the database.>

The authors present efficient methods for testing packet-switched multistage interconnection networks. In addition to testing the data paths and routing capabilities, tests for detecting faults in the control circuitry including the conflict resolution capabilities are provided. Using a general model of the switch, testing sequences are constructed for the internal functions of the f*f switch requiring only O(f/sup 2/2/sup f/) tests in the case of round-robin priority and O(f2/sup f-1/) in the case of fixed priority (f is usually a constant that is less than or equal to eight). Algorithms are then presented to test the entire network using at most twice the number of tests needed to test a switch, independently of the network size, which results in O(log N) testing time for an N-processor network. It is shown that the method achieves higher coverage and several-orders-of-magnitude reduction in the testing time of complex multiprocessor systems compared to previous methods.>

Topological testing is introduced and its applications are presented. Topological testing uses graph-theoretic optimization methods such as the traveling salesman problem, the Chinese postman problem, coloring, path covering, and partitioning to minimize the test time. The topological testing techniques can be applied to test a system's behavior and its organization at each level of the system's hierarchy, namely, circuit, logic, register transfer, instruction, and processor-memory-switch levels. Specifically, the topological testing approach is demonstrated by developing tests for the multistage interconnection network and the hypercube network. Time optimization for the testing of these networks gives very promising results by taking advantage of inherent parallelism and removing test redundancy. Three-orders-of-magnitude improvement is achieved by applying topological testing techniques to the testing of an existing multistage interconnection network.>