Detecting data races in multithreaded programs is critical to ensure the correctness of the programs. To discover data races precisely without false alarms, dynamic detection approaches are often applied. However, the overhead of the existing dynamic detection approaches, even with recent innovations, is still substantially high. In this paper, we present a simple but efficient approach to parallelize data race detection in multicore SMP (Symmetric Multiprocessing) machines. In our approach, data access information needed for dynamic detection is collected at application threads and passed to de-tection threads. The access information is distributed in a way that the operation performed by each detection thread is inde-pendent of that of other detection threads. As a consequence, the overhead caused by locking operations in data race detection can be alleviated and multiple cores can be fully utilized to speed up and scale up the detection. Furthermore, each detection thread deals with only its own assigned memory access region rather than the whole address space. The executions of detection threads can exploit the spatial locality of accesses leading to an improved cache performance. We have applied our parallel approach on the FastTrack algorithm and demon-strated the validity of our approach on an Intel Xeon machine. Our experimental results show that the parallel FastTrack detector, on average, runs 2.2 times faster than the original FastTrack detector on the 8 core machine.

Software instrumentation has been a convenient and portable approach for dynamic analysis, debugging, or profiling of program execution. Unfortunately, instrumentation may change the temporal behavior of multi-threaded program execution and result in different ordering of thread operations, which is called probe effect. While the approaches to reduce instrumentation overhead, to enable reproducible execution, and to enforce deterministic threading have been studied, no research has yet answered if an instrumented execution has the same behavior as the program execution without any instrumentation and how the execution gets changed if there were any. In this paper, we propose a simulation-based analysis to detect the changes of execution event ordering that are induced by instrumentation operations. The execution model of a program is constructed from the trace of instrumented program execution and is used in a simulation analysis where instrumentation overhead is removed. As a consequence, we can infer the ordering of events in the original program execution and verify the existence of probe effect resulted from instrumentation.

To detect races precisely without false alarms, vector clock based race detectors can be applied if the overhead in time and space can be contained. This is indeed the case for the applications developed in object-oriented programming language where objects can be used as detection units. On the other hand, embedded applications, often written in C/C++, necessitate the use of fine-grained detection approaches that lead to significant execution overhead. In this paper, we present a dynamic granularity algorithm for vector clock based data race detectors. The algorithm exploits the fact that neigh boring memory locations tend to be accessed together and can share the same vector clock archiving dynamic granularity of detection. The algorithm is implemented on top of Fast Track and uses Intel PIN tool for dynamic binary instrumentation. Experimental results on benchmarks show that, on average, the race detection tool using the dynamic granularity algorithm is 43% faster than the Fast Track with byte granularity and is with 60% less memory usage. Comparison with existing industrial tools, Val grind DRD and Intel Inspector XE, also suggests that the proposed dynamic granularity approach is very viable.

For program optimization and debugging, dynamic analysis tools, e.g., profiler, data race detector, are widely used. To gather execution information, software instrumentation is often employed for its portability and convenience. Unfortunately, instrumentation overhead may change the execution of a program and lead to distorted analysis results, i.e., probe effect. In embedded software which usually consists of multiple threads and external inputs, program executions are determined by the timing of external inputs and the order of thread executions. Hence, probe effect incurred in an analysis of embedded software will be more prominent than in desktop software. This paper presents a reliable dynamic analysis method for embedded software using deterministic replay. The idea is to record thread executions and I/O with minimal record overhead and to apply dynamic analysis tools in replayed execution. For this end, we have developed a record/replay framework called P-Replayer, based on Lamport's happens-before relation. Our experimental results show that dynamic analyses can be managed in the replay execution enabled by P-Replayer as if there is no instrumentation on the program.

Java has been making its way into the embedded systems and mobile devices like Android. The Java platform specifies the Java Native Interface (JNΓ) which allows Java code that runs within a JVM to interoperate with applications or libraries that are written in other languages and compiled to the host CPU. JNI plays an important role in embedded system as it provides a mechanism to interact with libraries specific to the platform and to take the advantage of fast execution of native programs. To address the overhead incurred in the JNI due to reflection and serialization, this paper proposes to cache class, field, and method information obtained from reflection for subsequent usage. It also provides a function to pin objects to their memory locations such that they can be accesses through the known reference. The Android emulator is used to evaluate the performance of these techniques and we observed that there was 1030 % performance gain in the Java Native Interface for two Android applications.

The non-deterministic behavior of multi-threaded embedded software makes cyclic debugging difficult. Even with the same input data, consecutive runs may result in different executions and reproducing the same bug is itself a challenge. Despite the fact that several approaches have been proposed for deterministic replay, none of them attends to the capabilities and functionalities that replay can comprise for better debugging. This paper introduces a practical replay mechanism for multi-threaded embedded software. The Replay Debugger, based on Lamport clock, offers a user controlled debugging environment in which the program execution follows the identical partially ordered happened-before dependency among threads and IO events as that of the recorded run. With the order of thread synchronizations assured, users can focus their debugging effort in the program behavior of any threads while having a comprehension of thread-level concurrency. Using a set of benchmark programs, experiment results of a prototyped implementation show that, in average, the software based approach incurs a small probe effect of 3.3% in its record stage.

As software systems are encompassing a wide range of fields and applications, software reliability becomes a crucial step. The need for safety analysis and test cases that have high probability to uncover plausible faults are necessities in proving software quality. System models that represent only the operational behavioral of a system are incomplete sources for deriving test cases and performing safety analysis before the implementation process. Therefore, a system model that encompasses faults is required. This paper presents a technique that formalizes a safety model through the incorporation of faults with system specifications. The technique focuses on introducing semantic faults through the integration of fault trees with system specifications or statechart. The method uses a set of systematic transformation rules that tries to maintain the semantics of both fault trees and statechart representations during the transformation of fault trees into statechart notations.

Persistence in applications saves a computation state that can be used to facilitate system recovery upon failures. As we begin to adopt virtual execution environments (VMs) for mission-critical real-time embedded applications, persistence service will become an essential part of VM to ensure high availability of the systems.In this paper, we focus in a schedulable persistence system in VMs and show a prototype persistence system constructed on CLI 's open source platform, MONO. By employing object serialization, the system enables concurrent and preemptible persistence operation, i.e., the task in charge of persistence service runs concurrently with application tasks and is a target of real-time scheduling. Thus, the execution of application tasks can be interleaved with the operations of persistence service, and the task timeliness can be guaranteed as the pause time caused by persistence service is bounded. The experiment output on the prototyped system illustrates that persistence service is appropriate for realtime applications because of its controllable pause time and its optimized overhead.

We present a schedulable garbage collection for realtime applications in virtual machine environments. The design objective is to make the pause time caused by garbage collection operations controllable, and the invocation of garbage collection predictable. Thus, real-time applications can be schedulable along with garbage collection. We develop a prototype for a schedulable garbage collection in MONO CLI execution environment. A cost model of garbage collection is established based on measured WCET to predict the execution time and overhead of garbage collection operations. A scheduling algorithm of garbage collection and application tasks is presented to illustrate how the time and memory constraints of real-time systems can be met. The experiment result of the scheduling algorithm for a periodic task set on the prototype is included in the paper.

Common language infrastructure (CLI) has been introduced as a core technology of Microsoft .NET. It enables "writing in multiple languages, running in multiple platforms" by providing virtual execution system (VES), common intermediate language, and common type system etc. The advantages of using CLI, including portability, compactness, and interoperability, could benefit the productivity of application software development and deployment. However, for embedded real-time systems, the applications' time-constraints cannot be satisfied easily due to several features of CLI runtime environment, such as thread priority, thread scheduling, garbage collection etc. In this paper, we aim to have a garbage collection mechanism applicable on real-time applications in CLI and other virtual machine environments. We achieve the goal by making the pause time of garbage collection operations predictable, and the invocation of garbage collection and applications schedulable. A cost model based on measured WCET is established to predict the execution time and overhead of garbage collection operations.

Time and energy is expended in switching between power modes (e.g., active, hibernate, sleep, etc.). Powering off cache is one major reason for this. When there is a switch in the power-mode involving cache power-off, the system spends time and energy in filling the cache with new data (inherent cache misses). In our technique, before powering off the cache, we save its state in Embedded DRAM and bring it back when the previous power mode is restored. Our experiments have showed that in a majority of cases the cache contents are too valuable to be erased. By saving the contents we can reduce switching speed and energy. We present a heuristic to save the most relevant cache contents so that power and delay overheads are minimized. To measure the area overhead a synthesizable VHDL model was designed.

Summary form only given. Pfair scheduling for periodic tasks on multiple processors in a time slotted environment can not only guarantee task deadlines to be respected, but also make tasks execute at steady progressive rates. We consider pfair schedulability of periodic tasks with allocation constraints in the sense that some tasks can only be assigned to one or more specified processors. The contributions of the paper lie in the following four aspects. Firstly, we prove that there exists pfair schedule in the case that fixed tasks are assigned to disjoined processor subsets. Secondly, we give a sufficient and necessary condition of the existence of pfair schedule for periodic tasks with arbitrary allocation constraints. Thirdly, we show that pfair schedulability test of periodic tasks with arbitrary allocation constraints can be done in polynomial time. Finally, an online approximate pfair scheduling algorithm called HPA (hierarchical pfair algorithm) is proposed for scheduling fixed and migrating tasks. With HPA although idea a fixed task is not guaranteed to respect its deadline completely, the amount of time by which it misses its deadline is bounded.

741-750

Modern embedded systems are often severely resource-constrained. In current research, the reduction of dynamic power has been the focus. However, with increased chip speed and density in submicron scale, the static (leakage) power consumption has become an increasingly significant fraction of the total. Indeed, a five-fold increase in leakage power per technology generation has been observed. At this pace, leakage power could soon equal dynamic power. In this paper, we investigate scheduling policies to reduce leakage power in real-time systems. We show that with simple scheduling techniques, overall leakage energy can be reduced by an order of magnitude.

In this paper we propose a frame-oriented scheduling discipline, EDF-RR (earliest-deadline-first round-robin), for OQ (output-queued) switch architecture and data traffic consisting of fixed-length cells. Bandwidth reservation for an active session is performed by holding a number of cell slots for the session in frames. Each cell that is going to be transferred in a frame is assigned a virtual release time and a virtual deadline according to the bandwidth reservation scheme. The transmitting order of the cells in frames is thus determined by nonpreemptive nonidling EDF algorithm so that cells of a backlogged session in frames are distributed as uniformly as possible. Through the analysis applying real-time scheduling theory and network calculus as well as network simulation, EDF-RR takes the advantage of low computational complexity, and possesses tight delay bounds and lenient buffer requirements. The proposed scheduling discipline is appropriate for distributed real-time systems as we show that sessions can be configured based on message traffic models and deadline requirements. Also, a modified version of EDF-RR, called EDF-DRR, can be applied as traffic regulator when jitter requirements exist among active sessions.

Provides an overview of the technical articles and features presented in this issue.

Many embedded systems operate under severe power and energy constraints. Voltage clock scaling is one mechanism by which energy consumption may be reduced: it is based on the fact that power consumption is a quadratic function of the voltage, while the speed is a linear function. We show how voltage scaling can be scheduled to reduce energy usage while still meeting real-time deadlines.

To facilitate the integration of real-time applications in a common platform, temporal and spatial partitioning should be provided. A strongly partitioned integrated real-time system (SPIRIT) is reported in this paper that adopts a two-level hierarchical scheduling mechanism to ensure temporal partitioning. At the lower level, multiple partitions (applications) are dispatched under a cyclic scheduling, whereas, at the higher level, multiple periodic tasks of a partition are scheduled within the partition according to a fixed priority algorithm. The proposed Distance Constraint guaranteed Dynamic Cyclic (DC2( scheduler applies three basic operations, left-sliding, right-putting and compacting, to dynamically schedule aperiodic tasks and, in the meantime, guarantees the distance constraint characteristics of a partition cyclic schedule. In addition, the slack time calculation of these dynamic operations can be applied for scheduling hard aperiodic tasks. With simulation studies, we observe that the DC2 algorithm can result in a significant performance enhancement in terms of the average response time of soft aperiodic tasks and the acceptance rate for hard aperiodic tasks.

Scaling down power supply voltage yields a quadratic reduction in dynamic power dissipation and also requires a reduction in clock frequency. In order to meet task deadlines in hard real-time systems, the delay penalty in voltage scaling needs to be carefully considered to achieve low power consumption. In this paper, we focus on dynamic reclaiming of early released resources in Earliest Deadline First (EDF) scheduling using voltage scaling. In addition to a static voltage assignment, we propose a new dynamic-mode assignment, which has a flexible voltage mode setting at run-time enabling much larger energy savings. Using simulation results and exploiting the interplay between power supply voltage, frequency, and circuit delay in CMOS technology, we find the optimal two-level voltage settings that minimize energy consumption.

Observing that it is impractical to use traditional methods to control concurrency in a broadcast-based asymmetric communication environment, we introduce a concurrency control protocol designed for broadcast-based transaction processing called STUBcast (Server Timestamp and Update Broadcast Supported Concurrency). STUBcast supports two new correctness criteria proposed - single serializability and local serializability. These criteria are weaker than global serializability but are practical and easier to achieve in a broadcast environment. This article also shows some simulation results. These results suggest that STUBcast could be very efficient in a realistic application environment.

Ethernet technology has received much attention in embedded system industries because of its cost efficiency, high availability, and popularity. This trend is not an exception even in safety critical real-time systems such as integrated modular avionics systems. To overcome the lack of deterministic characteristics in the Ethernet protocol, we propose a software-oriented approach based on table-driven proportional access. In addition to the protocol details, performance and schedulability analyses, as well as a prototype platform, are described.

In the recent development of avionics systems, integrated modular avionics (IMA) is advocated for next generation architecture that needs integration of mixed criticality real-time applications. These integrated applications meet their own timing constraints while sharing avionics computer resources. To guarantee timing constraints and dependability of each application, an IMA-based system is equipped with the schemes for spatial and temporal partitioning. We refer the model as SP-RTS (strongly partitioned real-time system), which deals with processor partitions and communication channels as its basic scheduling entities. This paper presents a partition and channel-scheduling algorithm for the SP-RTS. The basic idea of the algorithm is to use a two-level hierarchical schedule that activates partitions (or channels) following a distance-constraints guaranteed cyclic schedule and then dispatches tasks (or messages) according to a fixed priority schedule. To enhance schedulability, we devised heuristic algorithms for deadline decomposition and channel combining. The simulation results show the schedulability analysis of the two-level scheduling algorithm and the beneficial characteristics of the proposed deadline decomposition and channel combining algorithms.

In this paper, we investigate a scheduling algorithm, called circular window control (CWC) scheme, for packet switch fabrics. The scheme is simple and efficient. It uses a fixed length window with circular transmission sequences to minimize possible switch and output contentions. The scheme can attain a maximal throughput of 100%; in nonblocking switches as well as banyan-based blocking switches. The performance analyses and simulation results of the CWC scheme an also presented.

In communication and computer systems, autonomous sources may assign priorities to their messages or jobs locally and independently. When a remote service (e.g., message transmission or RPC) is requested at a shared server, the server cannot use priority scheduling schemes effectively unless it can make a comparison between priorities defined by individual sources. The authors investigate the strategies under which the service received by requests of one source is not affected by the priority assignments at other sources. The first approach is a combination of processor-sharing and priority queue strategies. The second approach is to map locally defined priorities onto a global priority system. The performance of these approaches is examined in terms of the average response time of all requests, the average response time of the highest priority requests and a fairness measure.>

Given a linear array of n heterogeneous traffic sources which generate multiple types of traffic among themselves, we consider the problem of finding a set of disjoint clusters to cover n traffic sources such that it minimizes the total communication cost for the entire system where the cost of intra-cluster communication is usually lower than that of inter-cluster communication for each type of traffic. The optimization problem is transformed into the dual based on the relative cost which is the communication cost if a pair of nodes are in different clusters of a partition. Using the relative cost matrix, an efficient algorithm of O(mn/sup 2/), where m is the number of clusters in a partition, is designed by dynamic programming.

Nonblocking algorithms for concurrent objects guarantee that an object is always accessible, in contrast to blocking algorithms in which a slow or halted process can render part or all of the data structure inaccessible to other processes. A number of algorithms have been proposed for shared FIFO queues, but nonblocking implementations are few and either limit the concurrency or provide inefficient solutions. The authors present a simple and efficient nonblocking shared FIFO queue algorithm with O(n) system latency, no additional memory requirements, and enqueuing and dequeuing times independent of the size of the queue. They use the compare & swap operation as the basic synchronization primitive. They model their algorithm analytically and with a simulation, and compare its performance with that of a blocking FIFO queue. They find that the nonblocking queue has better performance if processors are occasionally slow, but worse performance if some processors are always slower than others.>

A simple algorithm that shows how to optimally schedule the test-application and the signature-analysis phases of VLSI testing is presented. The testing process is broken into subintervals, the signature is analyzed at the end of each subinterval, and future tests are aborted if the circuit is found to be faulty, thus saving test time. The mathematical proofs associated with the algorithm are given.>

In this paper we examine the issue of robust transaction routing in a locally distributed database environment where transaction characteristics such as reference locality imply that certain processing systems can be identified as being more suitable than others for a given transaction class. A response time based routing strategy can strike a balance between indiscriminate sharing of the load and routing based only on transaction affinity. Since response time estimates depend on workload and system parameters that may not be readily available, it is important to examine the robustness of routing decisions to information accuracy. We find that a strategy which strictly tries to minimize the response time of incoming transactions is sensitive to the accuracy of certain parameter values. On the other hand, naive strategies, that simply ignore the parameters in making routing decisions, have even worse performance. Three alternative strategies are therefore examined: threshold, discriminatory, and adaptive. Instead of just optimizing an incoming transaction's response time, the first two strategies pursue a strategy that is somewhat more oriented towards global optimization. This is achieved by being more restrictive on either the condition or the candidate for balancing the load. The third strategy, while trying to minimize the response time of individual incoming transactions, employs a feedback process to adaptively adjust future response time estimates. It monitors the discrepancy between the actual and estimated response times and introduces a correction factor based on regression analysis. All three strategies are shown to be robust with respect to the accuracy of workload and system parameters used in the response time estimation.

A communication architecture and a dynamic control protocol are presented for real-time communication in multiple token ring networks. The network can be formed by multiple channels through bandwidth subdivision of a high-speed ring. A flexible preemption and dynamic load allocation scheme is developed which can reduce the lost percentage of critical packets and can maintain a high channel utilization at the same time. This performance improvement is demonstrated with extensive simulation results.>

An adaptive approach which utilizes the information embedded in indexes to identify the tuples satisfying a given predicate or having a match in a join operation is proposed. An access path (index or table scan) and a join method (index join, nested loop, sort-merge) are chosen to construct the results adaptively. This leads to the optimal evaluation of queries. With an efficient implementation, the adaptive decision process becomes a part of a query evaluation procedure, so that the overhead of the approach is minimized.>

The issue of transaction routing in a heterogeneous database environment is examined where transaction characteristics like reference locality implies that certain processing systems can be identified as being, in general, more suitable than others for a given transaction class. Routing which ignores these distinctions in an attempt to balance system load can degrade system performance. An adaptive routing strategy is considered which: (1) estimates the response time based on a steady-state analysis; (2) monitors how well actual response time conforms to the estimate; and (3) adaptively adjusts future estimates through a feedback control based on (2). It is found that the adaptive strategy greatly enhances performance robustness as compared to the results of the strategy without feedback. The feedback process used alleviates the sensitivity to accurate estimations of workload and system parameters. Various simulation studies are used to illustrate the adaptive strategy's robustness.>

1188-1198

A simple algorithm is presented which minimizes the mean testing time for VLSI circuits. By breaking up the testing process into subintervals, and analyzing the signature are the end of each subinterval, it is possible to abort future tests if the circuit is found to be faulty, thus saving test time. Subdivision of the test process also reduces the probability of aliasing, thus increasing the effective coverage of the signature analysis process. If the process is sufficiently subdivided, it may be possible to use the test results not only to determine if the circuit is faulty or not, but to diagnose the fault.>

Three factors determine the optimum configuration of a multiprocessor at any epoch: the workload, the reward structure, and the state of the computer system. An algorithm is presented for the optimal (more realistically, quasi-optimal) configuration of such systems used in real-time applications with periodic reward rates and workloads. The algorithm is based on Markov decision theory. It is suggested that a change in the workload or the reward structure should be as powerful a motivation for reconfiguration as component failure. Such changes occur naturally over the course of operation: an example of an online transaction processing system with a workload and reward structure that has a period of a day is given.>

In this paper, a new method is presented for (i) determining an optimal retry policy and (ii) using retry for fault characterization , which is defined as classification of the fault type and determination of fault durations. First, an optimal retry policy is derived for a given fault characteristic, which determines the maximum allowable retry durations so as to minimize the total task completion time. Then, the combined fault characterization and retry decision, in which the characteristic of a fault is estimated simultaneously with the determination of the optimal retry policy, are carried out. Two solution approaches are developed: one is based on point estimation and the other on Bayes sequential decision analysis. Numerical examples are presented in which all the durations associated with faults (i.e., active, benign, and interfailure durations) have monotone hazard rate functions (e.g., exponential Weibull and gamma distributions). These are standard distributions commonly used for modeling and analyses of faults.

A method for determining the optimal testing period and measuring the production yield is discussed. With the increased complexity of VLSI circuits, testing has become more costly and time-consuming. The design of a testing strategy, which is specified by the testing period based on the coverage function of the testing algorithm, involves trading off the cost of testing and the penalty of passing a bad chip as good. The optimal testing period is first derived, assuming the production yield is known. Since the yield may not be known a priori, an optimal sequential testing strategy which estimates the yield based on ongoing testing results, which in turn determines the optimal testing period, is developed next. Finally, the optimal sequential testing strategy for batches in which N chips are tested simultaneously is presented. The results are of use whether the yield stays constant or varies from one manufacturing run to another.>

The authors investigate dynamic transaction routing strategies for locally distributed database systems in which the database is partitioned and distributed among multiple transaction-processing systems, and the incoming transactions are routed by a common front-end processor. If a transaction issues a database request referencing a nonlocal database partition, the request has to be shipped to the system owing the referenced partition for processing. Various dynamic strategies are studied. Their performance is compared with that of the optimal static strategy. A class of dynamic transaction routing strategies which take into account routing history and minimize the estimated response time of incoming transactions is proposed; they are found to provide a substantial improvement over the optimal static strategy. The robustness of the strategies is further studied through sensitivity analysis over various transaction loads, communication overheads, and database reference distributions.>

The purpose of testing is to determine the correctness of the unit under test in come optimal way. One difficulty in meeting the optimality requirement is that the stochastic properties of the unit are usually unknown a priori. For instance, one might not know exactly the yield of a VLSI production line before one tests the chips made as a result. Given the probability of unit failure and the coverage of a test, the optimal test period is easy to obtain. However, the probability of failure is not usually known a priori. We there- fore develop an optimal sequential testing strategy which estimates the production yield based on ongoing test results, and then use it to determine the optimal test period.

A new quantitative approach to the problem of reconfiguring a degradable multimodule system is presented. The approach is concerned with both assigning some modules for computation and arranging others for reliability. Conventionally, a fault-tolerant system performs reconfiguration only upon a subsystem failure. Since there exists an inherent trade-off between the computation capacity and fault tolerance of a multimodule computing system, the conventional approach is a passive action and does not yield a configuration that provides an optimal compromise for the trade-off. By using the expected total reward as the optimal criterion, the need and existence of an active reconfiguration strategy, in which the system reconfigures itself on the basis of not only the occurrence of a failure but also the progression of the mission , are shown. Following the problem formulation, some important properties of an optimal reconfiguration strategy, which specify (i) the times at which the system should undergo reconfiguration and (ii) the configurations to which the system should change, are investigated. Then, the optimal reconfiguration problem is converted to integer nonlinear knapsack and fractional programming problems. The algorithms for solving these problems and a demonstrative example are given. Extensions of the optimal reconfiguration problem are also discussed.

The demand for on-line transaction processing has grown rapidly in recent years. To meet the transaction demand, several DB (database management) and DC (data communication management) subsystems can be coupled together to form a distributed DB/DC system. A key problem is to provide these distributed systems with effective means to recover transactions upon failure while paying little performance penalty during normal processing. Also, there should be minimal interference of fault-free components, during the recovery of failed component. By decentralizing recovery management, and using transaction level structural information to eliminate costly lower level handshaking protocols, proposed progressive transaction recovery protocols seek to solve the problem. A queueing model for evaluating the transaction response time during normal processing for the progressive and pessimistic protocols is developed and solved, via simulation. The progressive recovery protocols are shown to reduce normal processing overhead and lead to performance improvement over the pessimistic protocol.

Analytical models for the design and evaluation of checkpointing of real-time tasks are developed. First, the execution of a real-time task is modeled under a common assumption of perfect coverage of on-line detection mechanisms (which is termed a basic model). Then, the model is generalized (to an extended model) to include more realistic cases, i.e., imperfect coverages of on-line detection mechanisms and acceptance tests. Finally, we determine an optimal placement of checkpoints to minimize the mean task execution time while the probability of an unreliable result (or lack of confidence) is kept below a specified level. In the basic model, it is shown that equidistant intercheckpoint intervals are optimal, whereas this is not necessarily true in the extended model. An algorithm for calculating the optimal number of checkpoints and intercheckpoint intervals is presented with some numerical examples for the extended model.

The time interval between the occurrence of a fault and the detection of the error caused by the fault is divided by the generation of that error into two parts: fault latency and error latency. Since the moment of error generation is not directly observable, all related works in the literature have dealt with only the sum of fault and error latencies, thereby making the analysis of their separate effects impossible. To remedy this deficiency, we 1) present a new methodology for indirectly measuring fault latency, 2) derive the distribution of fault latency from the methodology, and 3) apply the knowledge of fault latency to the analysis of two important examples.

In this paper we consider the design and evaluation of a fault-tolerant multiprocessor with a rollback recovery mechanism.

Conventionally, reliability analyses either assume that a fault/error is detected immediately as it occurs, or ignore damage caused by imperfect detection mechanisms and error latency, namely, the time interval between the occurrence of an error and the detection of that error.

Three alternatives for implementing recovery blocks (RB's) are conceivable for backward error recovery in concurrent processing. These are the asynchronous, synchronous, and the pseudorecovery point implementations. Asynchronous RB's are based on the concept of maximum autonomy in each of concurrent processes. Consequently, establishment of RB's in a process is made independently of others and unbounded rollback propagations become a serious problem. In order to completely avoid unbounded rollback propagations, it is necessary to synchronize the establishment of recovery blocks in all cooperating processes. Process autonomy is sacrificed and processes are forced to wait for commitments from others to establish a recovery line, leading to inefficiency in time utilization. As a compromise between asynchronous and synchronous RB's we propose to insert pseudorecovery points (PRP's) so that unbounded rollback propagations may be avoided while maintaining process autonomy. We developed probabilistic models for analyzing these three methods under standard assumptions in computer performance analysis, i.e., exponential distributions for related random variables. With these models we have estimated 1) the interval between two successive recovery lines for asynchronous RB's, 2) mean loss in computation power for the synchronized method, and 3) additional overhead and rollback distance in case PRP's are used.

This paper presents a tree-structured multiprocessor called the hierarchical multimicroprocessor (HM2p), each node of which is composed of a cluster of processor modules (PM's), common memory, DMA interface, switches, communication lines, and a data processor associated with it. The HM2p consists of two different hierarchies, one for data processing and the other for data distribution, which provide clean, structured separation between processing components and user interface components.