Neuromorphic systems are a natural hardware system for robotic control because of their low size, weight, and power implementations, as well as their temporal processing capabilities. In this work, we evaluate how well neuromorphic systems are able to control and work together in a collective swarm of robots. We design simple robot structures, and we evolve and evaluate spiking neural networks to deploy to neuromorphic implementations on those robots.

Neuromorphic computing is a leading option for non von-Neumann computing architectures. With it, neural networks are developed that derive architectural inspiration from how the brain operates with neurons, synapses, and spikes. These networks are often implemented in either software or hardware based neuroprocessors designed to handle specific tasks efficiently. Even if implemented in hardware, software emulation is instrumental in determining the worthwhile features and capabilities of the architecture. In this work two novel neuroprocessors are introduced: the software-based RISP neuroprocessor, and the RAVENS hardware neuroprocessor. Several benchmark tests using control applications are performed with each neuroprocessor configured in various ways to evaluate their comparative performance and training properties.

There are a wide variety of training approaches for spiking neural networks for neuromorphic deployment. However, it is often not clear how these training algorithms perform or compare when applied across multiple neuromorphic hardware platforms and multiple datasets. In this work, we present a software framework for comparing performance across four neuromorphic training algorithms across three neuromorphic simulators and four simple classification tasks. We introduce an approach for training a spiking neural network using a decision tree, and we compare this approach to training algorithms based on evolutionary algorithms, back-propagation, and reservoir computing. We present a hyperparameter optimization approach to tune the hyperparameters of the algorithm, and show that these optimized hyperparameters depend on the processor, algorithm, and classification task. Finally, we compare the performance of the optimized algorithms across multiple metrics, including accuracy, training time, and resulting network size, and we show that there is not one best training algorithm across all datasets and performance metrics.

In the conventional robust$T$-colluding private information retrieval (PIR) system, the user needs to retrieve one of the possible messages while keeping the identity of the requested message private from any$T$colluding servers. Motivated by the possible heterogeneous privacy requirements for different messages, we consider the ($N, T_{1}: K_{1}, T_{2}: K_{2}$) two-level PIR system, where$K_{1}$messages need to be retrieved privately against$T_{1}$colluding servers, and all the messages need to be retrieved privately against$T_{2}$colluding servers where$T_{2}\leq T_{1}$. We obtain a lower bound to the capacity by proposing a novel coding scheme, namely the non-uniform successive cancellation scheme. A capacity upper bound is also derived. The gap between the upper bound and the lower bound is analyzed, and shown to vanish when$T_{1}=T_{2}$.

In this work we describe the design, implementation, and testing of the first neuromorphic robot capable of obstacle avoidance, grid coverage, and targeting controlled by the second generation Dynamic Adaptive Neural Network Array (DANNA2) digital spiking neuromorphic processor. The simplicity of the DANNA2 processor along with the TENNLab hardware/software co-design framework allows for compact spiking networks that can run efficiently on a small, resource-constrained, platform such as a Xilinx Artix-7 field-programmable gate array. Additionally, we present the dynamic reconfigurability of DANNA2 arrays as a method of realizing complex, multi-objective tasks on hardware that is restricted to relatively small networks.

Designing spiking neural networks for neuromorphic deployment is a non-trivial task. It is further complicated when there are resource constraints for the neuromorphic implementation, such as size or power constraints, that may be present in edge applications. In this work, we utilize a previously presented approach, EONS, to design spiking neural networks for a memristive neuromorphic implementation for scientific data applications. We specifically use a multi-objective approach in EONS to maximize network accuracy on the scientific data application task, but also to minimize network size and energy. We illustrate that EONS determines both the network structure and the parameters, removing the burden from the user on determining the appropriate spiking neural network structure, and we show that the resulting networks are very different from the layered structure of typical neural networks. Finally, we show that the multi-objective approach produces smaller, more energy efficient networks than the original EONS approach and produces comparable accuracy to a back-propagation style training approach.

Neuromorphic computing is one promising post-Moore's law era technology, which takes inspiration from biological brains to perform computing tasks. The human brain contains billions of neurons with trillions of synapses and as neuromorphic hardware systems scale to larger and larger sizes, the communication system used to transfer information between neuromorphic elements and traditional computers must scale to keep up. In prior work, we describe the use of a separate neuromorphic array communications controller to support low-latency, high-throughput communication between our neuromorphic systems and a traditional computer. In this work, the neuromorphic array communications controller is used to support the scaling of a neuromorphic development system which uses multiple neuromorphic processors arranged in a two-dimensional array. The neuromorphic array communications controller, along with scalable local connections, is used to create a scalable neuromorphic platform to enable the development and testing of large neuromorphic network arrays.

Neuromorphic Computing is a burgeoning field of research. Many groups are exploring hardware architectures and theoretical ideas about spiking recurrent neural networks. The overarching goal is to exploit the low power promise of these neuromorphic systems. However, it is difficult to train spiking recurrent neural networks (SRNNs) to perform tasks and make efficient use of neuromorphic hardware. Reservoir Computing is an attractive methodology because it requires no tuning of weights for the reservoir itself. Yet, to find optimal reservoirs, manual tuning of hyperparameters such as hidden neurons, synaptic density, and natural structure is still required. Because of this, researchers often have to generate and evaluate many networks, which can result in non-trivial amounts of computation. This paper employs the reservoir computing technique (specifically liquid state machines) and genetic algorithms in order to develop useful networks that can be deployed on neuromorphic hardware. We build on past work in reservoir computing and genetic algorithms to demonstrate the power of combining these two techniques and the advantage it can provide over manually tuning reservoirs for use on classification tasks. We discuss the complexities of determining whether or not to use the genetic algorithms approach for liquid state machine generation.

A key challenge for utilizing spiking neural networks or spiking neuromorphic systems for most applications is translating numerical data into spikes that are appropriate to apply as input to a spiking neural network. In this work, we present several approaches for encoding numerical values as spikes, including binning, spike-count encoding, and charge-injection encoding, and we show how these approaches can be combined hierarchically to form more complex encoding schemes. We demonstrate how these different encoding approaches perform on four different applications, running on four different neuromorphic systems that are based on spiking neural networks. We show that the input encoding method can have a significant effect on application performance and that the best input encoding method is application-specific.

Resource constrained devices are the building blocks of the internet of things (IoT) era. Since the idea behind IoT is to develop an interconnected environment where the devices are tiny enough to operate with limited resources, several control systems have been built to maintain low energy and area consumption while operating as IoT edge devices. Several researchers have begun work on implementing control systems built from resource constrained devices using machine learning. However, there are many ways such devices can achieve lower power consumption and area utilization while maximizing application efficiency. Spiky neuromorphic computing (SNC) is an emerging paradigm that can be leveraged in resource constrained devices for several emerging applications. While delivering the benefits of machine learning, SNC also helps minimize power consumption. For example, low energy memory devices (memristors) are often used to achieve low power operation and also help in reducing system area. In total, we anticipate SNC will provide computational efficiency approaching that of deep learning while using low power, resource constrained devices.

Evolutionary optimization or genetic algorithms have been used to optimize a variety of neural network types, including spiking recurrent neural networks, and are attractive for many reasons. However, a key impediment to their widespread use is the potential for slow training times and failure to converge to a good fitness value in a reasonable amount of time. In this work, we evaluate the effect of different selection algorithms on the performance of an evolutionary optimization method for designing spiking recurrent neural networks, including those that are meant to be deployed in a neuromorphic system. We propose a selection approach that utilizes a richer understanding of the fitness of an individual network to inform the selection process and to promote diversity in the population. We show that including this feature can provide a significant increase in performance over utilizing a standard selection approach.

Neuromorphic computing is one promising post-Moore's law era technology. In order to develop and use neuromorphic systems, traditional von Neumann-based computers must be able to communicate with neuromorphic hardware to support functionality such as monitoring the state of the network, optimizing the array to better perform the task, and input/output data processing. In this paper, we describe our use of a separate neuromorphic array communications controller to support highthroughput, low-latency communication between a traditional computer and our implementations of neuromorphic systems. The goal of the communications controller is to provide enough performance to facilitate the desired interaction between the systems and to enable scaling of the neuromorphic systems to larger sizes.

Neuromorphic computing systems are alternatives to conventional microprocessors, often built from unconventional hardware. Designing and evaluating these systems requires multiple levels of simulation, from the device level to the circuit level to the system level. In this paper, we describe the system level simulator of a neuromorphic computing system based on memristors. We compare it to a circuit level simulator of the same system, both verifying its accuracy and demonstrating its performance improvement. We argue that system level simulation is an essential part of the design process of neuromorphic systems.

In recent years, research on neuromporphic computing platforms has focused on variable-structure, spiking network models. An important methodology for programming these networks is evoluationary optimization (EO), where thousands of networks are generated and then evaluated by determining fitness scores on specific tasks. Fitness scores guide the generation of new networks until a target fitness is achieved. One source of performance overhead during EO is the simulation of the task on each network to determing its fitness. To mitigate this source of overhead, we formulate the Static Fitness Prediction Task (SFPT), for predicting a network's fitness without direct simulation. Our hypothesis is that we can use SFPT to predict a network's fitness sufficiently accurately to reject a significant portion of networks during EO without having to simulate them, thereby making the EO more efficient. We propose a data-driven approach to the SFPT on the neuromorphic model DANNA [1]. Our approach transforms networks into directed graphs and extracts structural features to train an ancillary model for predicting the fitness of new networks. We analyze the extracted features and evaluate several predictive models to predict the fitness of networks for five tasks. Our results demonstrate a predictive capacity in these features and models. Our primary contribution is to demonstrate the utility of graph-level features extracted from variable-structure networks to predict network fitness and circumvent expensive simulations.

Dynamic Adaptive Neural Network Arrays (DANNAs) are neuromorphic computing systems developed as a hardware based approach to the implementation of neural networks. They feature highly adaptive and programmable structural elements, which model artificial neural networks with spiking behavior. We design them to solve problems using evolutionary optimization. In this paper, we highlight the current hardware and software implementations of DANNA, including their features, functionalities and performance. We then describe the development of an Application Development Platform (ADP) to support efficient application implementation and testing of DANNA based solutions. We conclude with future directions.

As new neural network and neuromorphic architectures are being developed, new training methods that operate within the constraints of the new architectures are required. Evolutionary optimization (EO) is a convenient training method for new architectures. In this work, we review a spiking neural network architecture and a neuromorphic architecture, and we describe an EO training framework for these architectures. We present the results of this training framework on four classification data sets and compare those results to other neural network and neuromorphic implementations. We also discuss how this EO framework may be extended to other architectures.

Partial MDS (PMDS) codes are erasure codes combining local (row) correction with global additional correction of entries, while sector-disk (SD) codes are erasure codes that address the mixed failure mode of current redundant arrays of independent disk (RAID) systems. It has been an open problem to construct general codes that have the PMDS and the SD properties, and previous work has relied on Monte-Carlo searches. In this paper, we present a general construction that addresses the case of any number of failed disks and in addition, two erased sectors. The construction requires a modest field size. This result generalizes previous constructions extending RAID 5 and RAID 6.

Partial MDS (PMDS) codes are erasure codes combining local (row) correction with global additional correction of entries, while Sector-Disk (SD) codes are erasure codes that address the mixed failure mode of current RAID systems. It has been an open problem to construct general codes that have the PMDS and the SD properties, and previous work has relied on Monte-Carlo searches. In this paper, we present a general construction that addresses the case of any number of failed disks and in addition, two erased sectors. The construction requires a modest field size. This result generalizes previous constructions extending RAID 5 and RAID 6.

In data storage systems, it is crucial to protect data from loss due to failures. Erasure codes lay the foundation of this protection, enabling systems to reconstruct lost data when components fail. Erasure codes can, however, impose significant performance overhead in two core operations: encoding, where parity is calculated from newly written data, and decoding, where data is reconstructed after failures. This paper focuses on improving the performance of encoding, the more frequent operation. We observed that CPU cache efficiency has great impact on the encoding performance and proposed several encoding scheduling algorithms to optimize the use of cache memory. We call the technique XOR-scheduling and demonstrate how it applies to a wide variety of existing erasure codes. To illustrate the generality of this technique, we have conducted a performance evaluation of scheduling these codes on a variety of platforms and shown that XOR-scheduling significantly improves upon the conventional approach. Hence, we believe that XOR-scheduling has great potential to have wide impact in practical storage systems.

Traditionally, when storage systems employ erasure codes, they are designed to tolerate the failures of entire disks. However, the most common types of failures are latent sector failures, which only affect individual disk sectors, and block failures which arise through wear on SSD’s. This article introduces SD codes, which are designed to tolerate combinations of disk and sector failures. As such, they consume far less storage resources than traditional erasure codes. We specify the codes with enough detail for the storage practitioner to employ them, discuss their practical properties, and detail an open-source implementation.

Large scale, archival and wide-area storage systems use erasure codes to protect users from losing data due to the inevitable failures that occur. All but the most basic erasure codes employ bit-matrices so that encoding and decoding may be effected solely with the bitwise exclusive-OR (XOR) operation. There are CPU savings that can result from strategically scheduling these XOR operations so that fewer XOR's are performed. It is an open problem to derive a schedule from a bit-matrix that minimizes the number of XOR operations. We attack this open problem, deriving two new heuristics called Uber-CHRS and X-Sets to schedule encoding and decoding bit-matrices with reduced XOR operations. We evaluate these heuristics in a variety of realistic erasure coding settings and demonstrate that they are a significant improvement over previously published heuristics. We provide an open-source implementation of these heuristics so that practitioners may leverage our work.

MDS erasure codes are ubiquitous in storage systems that must tolerate failures. While classic Reed-Solomon codes can provide a general-purpose MDS code for any situation, systems that require high performance rely on special-purpose codes that employ the bitwise exclusive-or (XOR) operation, and may be expressed in terms of a binary generator matrix. There are known lower bounds on the density of the generator matrix; however the number of XOR operations required to encode the generator matrix, while related to the density of the matrix, has not been explored. This paper presents a stunning and counter-intuitive result - that the encoding of k message symbols in an MDS code may require fewer than k-1 XOR operations per coding symbol. The result brings into question the lower bounds on the performance of encoding and decoding MDS erasure codes.

RAID-6 codes protect disk array storage systems from two-disk failures. This article presents a complete treatment of a class of RAID-6 codes, called minimum density RAID-6 codes , that have an optimal blend of performance properties. There are two families of minimal density RAID-6 codes: Blaum-Roth codes and Liberation codes, and a separate special-purpose code called the Liber8tion code. The first of these have been known since the late 1990's, while the latter two are new constructions. In this article, we motivate, demonstrate, and evaluate the minimum density codes, comparing them to EVENODD and RDP codes, which represent the state-of-the-art in RAID-6. Following that, we prove that the codes indeed fit the RAID-6 methodology, and cite their implementation in an open-source library.

In large storage systems, it is crucial to protect data from loss due to failures. Erasure codes lay the foundation of this protection, enabling systems to reconstruct lost data when components fail. Erasure codes can however impose significant performance overhead in two core operations: encoding, where coding information is calculated from newly written data, and decoding, where data is reconstructed after failures. This paper focuses on improving the performance of encoding, the more frequent operation. It does so by scheduling the operations of XOR-based erasure codes to optimize their use of cache memory. We call the technique XOR-scheduling and demonstrate how it applies to a wide variety of existing erasure codes. We conduct a performance evaluation of scheduling these codes on a variety of processors and show that XOR-scheduling significantly improves upon the traditional approach. Hence, we believe that XOR-scheduling has great potential to have wide impact in practical storage systems.

RAID-6 storage systems protect k disks of data with twoparity disks so that the system of k+2 disks may toleratethe failure of any two disks. Coding techniques for RAID-6 systems are varied, but an important class of techniquesare those with minimum density, featuring an optimalcombination of encoding, decoding and modificationcomplexity. The word size of a code impacts both how thecode is laid out on each disk's sectors and how large k canbe. Word sizes which are powers of two are especiallyimportant, since they fit precisely into file systemblocks. Minimum density codes exist for many word sizeswith the notable exception of eight. This paper fills thatgap by describing new codes for this important word size.The description includes performancencoding,e properties as well asdetails of the discovery process.

In the past few years, all manner of storage applications, ranging from disk array systems to distributed and wide-area systems, have started to grapple with the reality of tolerating multiple simultaneous failures of storage nodes. Unlike the single failure case, which is optimally handled with RAID Level-5 parity, the multiple failure case is more difficult because optimal general purpose strategies are not yet known. Erasure Coding is the field of research that deals with these strategies, and this field has blossomed in recent years. Despite this research, the decades-old Reed- Solomon erasure code remains the only space-optimal (MDS) code for all but the smallest storage systems. The best performing implementations of Reed-Solomon coding employ a variant called Cauchy Reed-Solomon coding, developed in the mid 1990’s [4]. In this paper, we present an improvement to Cauchy Reed-Solomon coding that is based on optimizing the Cauchy distribution matrix. We detail an algorithm for generating good matrices and then evaluate the performance of encoding using all implementations Reed- Solomon codes, plus the best MDS codes from the literature. The improvements over the original Cauchy Reed-Solomon codes are as much as 83% in realistic scenarios, and average roughly 10% over all cases that we tested.

The problem of efficiently retrieving a file that has been broken into blocks and distributed across the wide-area pervades applications that utilize grid, peer-to-peer, and distributed file systems. While the use of erasure codes to improve the fault-tolerance and performance of wide-area file systems has been explored, there has been little work that assesses the performance and quantifies the impact of modifying various parameters. This paper performs such an assessment. We modify our previously defined framework for studying replication in the wide-area to include both Reed-Solomon and low-density parity-check (LDPC) erasure codes. We then use this framework to compare Reed-Solomon and LDPC erasure codes in three wide-area, distributed settings. We conclude that although LDPC codes have an advantage over Reed-Solomon codes in terms of decoding cost, this advantage does not always translate to the best overall performance in wide-area storage situations.

Erasure codes have profound uses in wide- and medium-area storage applications. While infinite-size codes have been developed with optimal properties, there remains a need to develop small codes with optimal properties. In this paper, we provide a framework for exploring very small codes, and we use this framework to derive optimal and near-optimal ones for discrete numbers of data bits and coding bits. These codes have heretofore been unknown and unpublished, and should be useful in practice. We also use our exploration to make observations about upper bounds for these codes, in order to gain a better understanding of them and to spur future derivations of larger, optimal and near-optimal codes.

As peer-to-peer and widely distributed storage systems proliferate, the need to perform efficient erasure coding, instead of replication, is crucial to performance and efficiency. Low-density parity-check (LDPC) codes have arisen as alternatives to standard erasure codes, such as Reed-Solomon codes, trading off vastly improved decoding performance for inefficiencies in the amount of data that must be acquired to perform decoding. The scores of papers written on LDPC codes typically analyze their collective and asymptotic behavior. Unfortunately, their practical application requires the generation and analysis of individual codes for finite systems. This paper attempts to illuminate the practical considerations of LDPC codes for peer-to-peer and distributed storage systems. The three main types of LDPC codes are detailed, and a huge variety of codes are generated, then analyzed using simulation. This analysis focuses on the performance of individual codes for finite systems, and addresses several important heretofore unanswered questions about employing LDPC codes in real-world systems.

The challenge of efficiently retrieving files that are broken into segments and replicated across the wide-area is of prime importance to wide-area, peer-to-peer, and grid file systems. Two differing algorithms addressing this challenge have been proposed and evaluated. While both have been successful in differing performance scenarios, there has been no unifying work that can view both algorithms under a single framework. We define such a framework, where download algorithms are defined in terms of four dimensions: the number of simultaneous downloads, the degree of work replication, the failover strategy, and the server selection algorithm. We then explore the impact of varying parameters along each of these dimensions.

Over the past two decades, rollback-recovery via checkpoint-restart has been used with reasonable success for long-running applications, such as scientific workloads that take from few hours to few months to complete. Currently, several commercial systems and publicly available libraries exist to support various flavors of checkpointing. Programmers typically use these systems if they are satisfactory or otherwise embed checkpointing support themselves within the application. In this paper, we project the performance and functionality of checkpointing algorithms and systems as we know them today into the future. We start by surveying the current technology roadmap and particularly how Peta-Flop capable systems may be plausibly constructed in the next few years. We consider how rollback-recovery as practiced today will fare when systems may have to be constructed out of thousands of nodes. Our projections predict that, unlike current practice, the effect of rollback-recovery may play a more prominent role in how systems may be configured to reach the desired performance level. System planners may have to devote additional resources to enable rollback-recovery and the current practice of using "cheap commodity" systems to form large-scale clusters may face serious obstacles. We suggest new avenues for research to react to these trends.

In this work we present the Internet Backplane Protocol (IBP), a middleware created to allow the sharing of storage resources, implemented as part of the network fabric. IBP allows an application to control intermediate data staging operations explicitly. As IBP follows a very simple philosophy, very similar to the Internet Protocol, and the resulting semantic might be too weak for some applications, we introduce the exNode, a data structure that aggregates storage allocations on the Internet.

In this paper we present the Logistical Networking principles and the tools we developed to support our ideas. Logistical Networking is defined as the global scheduling and optimization of data movement, storage and computation based on a model that takes into account al the network's underlying physical resources. We introduce then the Internet Backplane Protocol (IBP), a middleware created to allow the sharing of storage resources, implemented as part of the network fabric, the exNode, a data structure that aggregates storage allocations on the Internet, and the L-Bone, a directory service of distributed storage resource.

In this paper we present a novel methodology for improving the performance and dependability of application-level messaging in Grid systems. Based on the Network Weather Service, our system uses nonparametric statistical forecasts of request-response times to automatically determine message timeouts. By choosing a timeout based on predicted network performance, the methodology improves application and Grid service performance as extraneous and overly-long timeouts are avoided. We describe the technique, the additional execution and programming overhead it introduces, and demonstrate the effectiveness using a wide-area test application.

This paper discusses the application of end-to-end design principles, which are characteristic of the architecture of the Internet, to network storage. While putting storage into the network fabric may seem to contradict end-to-end arguments, we try to show not only that there is no contradiction, but also that adherence to such an approach is the key to achieving true scalability of shared network storage. After discussing end-to-end arguments with respect to several properties of network storage, we describe the Internet Backplane Protocol and the exNode, which are tools that have been designed to create a network storage substrate that adheres to these principles. The name for this approach is Logistical Networking, and we believe its use is fundamental to the future of truly scalable communication.

Recent advances in computing and communication have given rise to the computational grid notion (I. Foster and C. Kesselman, 1998). The core of this computing paradigm is the design of a system for drawing compute power from a confederation of geographically dispersed heterogeneous resources, seamlessly and ubiquitously. If high-performance levels are to be achieved, data locality must be identified and managed. We consider the effect of server side staging on the behavior of a class of wide area "task farming" or parameter sweep applications. We show that staging improves task throughput mainly through the increased parallelism rather than the reduction in overall turnaround time per task. We derive a model for farming applications with and without server side staging and verify the model through live experiments as well as simulations.

In this paper we investigate G-commerce-computational economies for controlling resource allocation in Computational Grid settings. We define hypothetical resource consumers (representing users and Grid-aware applications) and resource producers (representing resource owners who "sell" their resources to the Grid). We then measure the efficiency of resource allocation under two different market conditions: commodities markets and auctions. We compare both market strategies in terms of price stability, market equilibrium, consumer efficiency, and producer efficiency. Our results indicate that commodities markets are a better choice for controlling Grid resources than previously defined auction strategies.

Failure identification is a fundamental operation concerning exceptional conditions that network programs must be able to perform. In this paper, we explore the use of timeouts to perform failure identification at the application level. We evaluate the use of static timeouts and of dynamic timeouts based on forecasts using the Network Weather Service. For this evaluation, we perform experiments on a wide-area collection of 31 machines distributed in eight institutions. Though the conclusions are limited to the collection of machines used, we observe that a single static timeout is not reasonable, even for a collection of similar machines over time. Dynamic timeouts perform roughly as well as the best static timeouts and, more importantly, they provide a single methodology for timeout determination that should be effective for wide-area applications.

While a variety of checkpointing techniques and systems have been documented for long-running programs, they are typically not available for programmers that are non-systems experts. We detail a project that integrates three technologies, NetSolve, Starfish and IBP, for the seamless integration of fault-tolerance into long-running applications. We discuss the design and implementation of this project, and present performance results executing on both local and wide area networks.

Checkpointing systems are a convenient way for users to make their programs fault-tolerant by intermittently saving program state to disk and restoring that state following a failure. The main concern with checkpointing is the overhead that it adds to running time of the program. This paper describes memory exclusion, an important class of optimizations that reduce the overhead of checkpointing. Some forms of memory exclusion are well-known in the checkpointing community. Others are relatively new. In this paper, we describe all of them within the same framework. We have implemented these optimization techniques in two checkpointers: libckpt, which works on Unix-based workstations, and CLIP, which works on the Intel Paragon. Both checkpointers are publicly available at no cost. We have checkpointed various long-running applications with both checkpointers and have explored the performance improvements that may be gained through memory exclusion. Results from these experiments are presented and show the improvements in time and space overhead. Copyright © 1999 John Wiley & Sons, Ltd.

Diskless Checkpointing is a technique for checkpointing the state of a long-running computation on a distributed system without relying on stable storage. As such, it eliminates the performance bottleneck of traditional checkpointing on distributed systems. In this paper, we motivate diskless checkpointing and present the basic diskless checkpointing scheme along with several variants for improved performance. The performance of the basic scheme and its variants is evaluated on a high-performance network of workstations and compared to traditional disk-based checkpointing. We conclude that diskless checkpointing is a desirable alternative to disk-based checkpointing that can improve the performance of distributed applications in the face of failures.

Checkpointing is a useful technique for rollback recovery of parallel applications. While extensive research has been performed on checkpointing in parallel environments, there are few checkpointers available to application users on commercial parallel computers. This paper presents one such checkpointer: CLIP. CLIP is a user-level library that provides semi-transparent check-pointing for parallel programs on the Intel Paragon multicomputer. It is publicly available to Paragon users at no cost.Conceptually, checkpointing a multicomputer is quite straightforward. However, when creating an actual tool for checkpointing a complex machine like the Paragon, many more issues arise that require careful design decisions to be made. Sometimes ease-of-use must be sacrificed for efficiency and/or correctness. This paper details what these decisions are, and how they were made in CLIP.We also present performance data when checkpointing several long-running Paragon applications with CLIP. The bottom line is that a convenient, general-purpose checkpointing tool like CLIP can provide fault-tolerance on a massively parallel multicomputer like the Paragon with very good performance.

It is well-known that Reed-Solomon codes may be used to provide error correction for multiple failures in RAID-like systems. The coding technique itself, however, is not as well-known. To the coding theorist, this technique is a straightforward extension to a basic coding paradigm and needs no special mention. However, to the systems programmer with no training in coding theory, the technique may be a mystery. Currently, there are no references that describe how to perform this coding that do not assume that the reader is already well-versed in algebra and coding theory. This paper is intended for the systems programmer. It presents a complete specification of the coding algorithm plus details on how it may be implemented. This specification assumes no prior knowledge of algebra or coding theory. The goal of this paper is for a systems programmer to be able to implement Reed-Solomon coding for reliability in RAID-like systems without needing to consult any external references. © 1997 John Wiley & Sons, Ltd.

Coordinated checkpointing systems are popular and general-purpose tools for implementing process migration, coarse-grained job swapping, and fault-tolerance on networks of workstations. Though simple in concept, there are several design decisions concerning the placement of checkpoint files that can impact the performance and functionality of coordinated checkpointers. Although several such checkpointers have been implemented for popular programming platforms like PVM and MPI, none have taken this issue into consideration. This paper addresses the issue of checkpoint placement and its impact on the performance and functionality of coordinated checkpointing systems. Several strategies, both old and new, are described and implemented on a network of SPARC-5 workstations running PVM. These strategies range from very simple to more complex borrowing heavily from ideas in RAID (Redundant Arrays of Inexpensive Disks) fault-tolerance. The results of this paper will serve as a guide so that future implementations of coordinated checkpointing can allow their users to achieve the combination of performance and functionality that is right for their applications.

Presents the results of an implementation of several algorithms for checkpointing and restarting parallel programs on shared-memory multiprocessors. The algorithms are compared according to the metrics of overall checkpointing time, overhead imposed by the checkpointer on the target program, and amount of time during which the checkpointer interrupts the target program. The best algorithm measured achieves its efficiency through a variation of copy-on-write, which allows the most time-consuming operations of the checkpoint to be overlapped with the running of the program being checkpointed.>

The authors present a checkpointing scheme that is transparent, imposes overhead only during checkpoints, requires minimal message logging, and allows for quick resumption of execution from a checkpointed image. Since checkpointing multicomputer applications poses requirements different from those posed by checkpointing general distributed systems, existing distributed checkpointing schemes are inadequate for multicomputer checkpointing. The proposed checkpointing scheme makes use of special properties of multicomputer interconnection networks to satisfy this set of requirements. The proposed algorithm is efficient both when taking checkpoints and when recovering from checkpointed images.>

We have developed and implemented a checkpointing and restart algorithm for parallel programs running on commercial uniprocessors and shared-memory multiprocessors. The algorithm runs concurrently with the target program, interrupts the target program for small, fixed amounts of time and is transparent to the checkpointed program and its compiler. The algorithm achieves its efficiency through a novel use of address translation hardware that allows the most time-consuming operations of the checkpoint to be overlapped with the running of the program being checkpointed.