Nanocomputing and related-enabling technologies hold the promise of higher performance and lower power consumption, as well as increased communication capabilities and functionality. In addition to the impact on today computerized systems, nanocomputing is an essential lever to foster the emerging cyberphysical system paradigm. However, the dependability and security of these unprecedentedly small devices, of their deployment, and of their interconnection remain uncertain. The main sources of concern are: • Nanometer devices are expected to be highly sensitive to process variations. The guard-bands used today for avoiding the impact of such variations will not represent a feasible solution in the future. As a consequence, timing errors and their higher frequency of occurrence have to be addressed. • New and intricate failure modes, specific to new materials, are expected to raise serious challenges to the design and test engineers. • Environment induced errors, such as single event upsets (SEU), are likely to occur more frequently than in the case of more conventional semiconductor devices. • Design of hardware architectures encompassing resilience techniques are needed to achieve the development of highly reliable energy efficient systems. • The increased complexity of the systems based on nanotechnology will require improved computer aided design (CAD) tools, as well as better validation techniques. • The security of nanocomputing systems may be threatened by malicious attacks targeting new vulnerable areas in the hardware.

This paper proposes a floorplan method for asynchronous circuits with bundled-data implementation on FPGAs. The proposed method minimizes the delay of the control circuit while considering timing constraints required for bundled-data implementation. Through the implementation of the proposed method, this paper evaluates the proposed method in terms of performance and area for generated floorplans.

The research presented in this paper details a number of further novel developments to a methodology known as “Pair and Swap”. Pair and Swap is a processor-level fault tolerance technique that enables graceful degradation in multi-core chips. The new developments are based around the introduction of a, hardware-based, decision unit into the system. The decision unit is a dependable solution to the problem of being able to reliably compare the comparison results of a pair of cores based on the current core pairings. The decision unit is determined to be more reliable, and efficient, than the cores due to the architectural simplicity it uses to perform the comparison, which is used to update eachcore’s configuration table. This paper will detail the complete decision unit implementation within the pair and swap methodology and show its ability to detect and gracefully degrade from both transient and permanent faults.

In this paper, we propose two new N-way arbiter circuits. One circuit is based on the token-ring arbiters and another circuit is based on the mesh arbiters. The idea of the ring arbiter is to generate a lock signal by a token which is based on the non-return-to-zero signaling. It can achieve low latency and high throughput arbitration for a heavy work load environment. The idea of the mesh arbiter is to perform arbitrations between N/2 pairs at the same level and repeat them N-1 times. They can issue grant signals fairly. In this paper, we compare the performance of these N-way arbiters using 65nm process technologies qualitatively and quantitatively. We conclude that the proposed mesh arbiters are suitable when the number of inputs is 5 or less. We also conclude that we must select the appropriate arbiters considering tradeoff between latency, throughput, area, and energy when the number of inputs is larger than 5.

While monolithic operating system kernels are composed of many subsystems, during runtime they all share a common address space, making fault propagation a serious issue. The code quality of each subsystem is different, as OS development is a complex task commonly divided by different groups with different degrees of expertise. Since the memory space into which this code runs is shared, the occurrence of bugs or errors in one of the subsystems may propagate to others and affect general OS reliability. It is necessary, then, to test how errors propagate between the different kernel subsystems and how they affect reliability. This work presents a simple new technique to inject memory corruption faults and Zapmem, a fault injection tool which uses such technique to test the effect on reliability from memory corruption of statically allocated kernel data. Zapmem associates the runtime memory addresses to the corresponding high level (source code) memory structure definitions, which indicate which kernel subsystem allocated that memory region, and the tool has minimal intrusiveness, as our technique does not require kernel instrumentation. The efficacy of our approach and preliminary results are also presented.

Device drivers can be traced as the source of most operating system (OS) bugs. The Linux kernel includes a fault injection framework which developers can use to implement simple fault injection tools to test device drivers. This paper presents our results in applying the fault injection framework to inject DMA address errors. Our experiments show that while the injected errors reach the device driver, the asynchronous nature of DMA makes the framework an ill-suited approach if the fault injection campaign expects the errors to reach the hardware I/O devices, as when trying to test IOMMU implementations.

This paper addresses the problem of detecting inconsistent values caused by interaction faults originated from an external system.This type of error occurs when a correctly formatted message that is not corrupted during transmission is generated with a field that contains incorrect data.When traditional schemes cannot be used, one alternative is resorting to receiver-based strategies that employ implicit redundancies - relations between events or data, often identified by a human expert.We propose an approach for detecting inconsistent values using implicit redundancies which are automatically located in examples of communications.We show that, even without adding any redundant information to the communication, the proposed approach can achieve a reasonable error detection coverage in fields where sequential relations exist.Other aspects, such as false alarms and latency, are also evaluated.

The present paper focuses on applications that are periodic and have both latency and throughput constraints. For these applications, pipeline scheduling is effective for reducing energy consumption. Thus, the present paper proposes a pipelined task scheduling method for minimizing the energy consumption of GALS MP-SoC under latency and throughput constraints. First, we model target GALS MP-SoC architecture and application tasks. We then show that the energy optimization problem under this model belongs to the class of mixed-integer linear programming. Next, we propose a new scheduling method based on simulated annealing for the purpose of solving this problem quickly. Finally, experimental results demonstrate that the proposed method achieves a significant energy reduction on a real application under a practical architecture

Two important factors that affect the performance of wireless sensor networks (WSNs) are data quality and network lifetime. This paper exploits the tradeoff between data quality and network lifetime to improve data collection precision while the network lifetime is adapted. The problem is to minimize the total error bound for approximate data aggregation in both single-hop and multi-hop WSNs to achieve the adaptive network lifetime. This problem is formulated as an optimization problem by combining the changing pattern of sensor readings, the residual energy of sensor nodes, and the communication cost from the sensor node to the base station. Our method is theoretically analyzed and further evaluated by conducting simulation experiments. To the best of our knowledge, this is the first study on minimizing the total error bound while achieving the adaptive network lifetime.

This paper presents a novel power reduction method for chip multi-processors (CMPs) under real-time constraints. While the power consumption of processing units (PUs) on CMPs can be reduced without violating real-time constraints by dynamic voltage and frequency scaling (DVFS), the clock frequency of each PU cannot be determined independently because of the performance impact caused by the conflict for the shared resources. To minimize power consumption in this situation, we first derive an analytical model which provides the optimal priority and clock frequency setting, and then propose a method of controlling the priority of shared resource accesses in cooperation with DVFS. From the analytical model, in dual-core CMPs, we reveal that the total power consumption is minimized when the clock frequency of two PUs becomes the same. An experiment with a synthetic benchmark supports the validity of the analytical model and the evaluation results with real applications show that the proposed method reduces the power consumption by up to 15% and 6.7% on average compared with a conventional DVFS technique.

Multimedia object caching, by which the same multimedia object can be adapted to diverse mobile appliances through the technique of transcoding, is an important technology for improving the scalability of Web services, especially in the environment of mobile networks. In this paper, we address the cache replacement problem for multimedia object caching by exploring the aggregate effect of caching multiple versions of the same multimedia object. First, we present an optimal solution for calculating the minimal access cost of caching multiple versions of the same multimedia object. Second, based on this solution, we propose an effective cache replacement algorithm for multimedia object caching. Finally, we evaluate the performance of the proposed solution with a set of simulation experiments for various performance metrics over a wide range of system parameters.

Topology discovery is a key task for several computer network applications such as diagnosis, routing and network management. Traditional approaches for topology discovery cannot always be used in dynamic and decentralized networks, such as unstructured peer-to-peer networks and wireless ad hoc networks. This paper introduces a strategy based on mobile agents and swarm intelligence for topology discovery in such environments. The proposed strategy is inspired by ant colonies, employing simple agents that disseminate information about the topology and communicate through stigmergy. Experimental results show that the nodes obtain descriptions which are very close to the real network topology. It is also shown that the stigmergy-based method for the selection of agent destinations produces better results than a random selection, and that the number of agents can be dynamically adjusted as the size of the network changes.

In this paper, a new scenario for tolerating interaction faults is presented. We also address the problem of designing a system capable of tolerating interaction faults generated by the other system. The scenario and other concepts defined in this paper were discussed with more detail. A system is defined as a pair of sub-systems that use a communication standard to interact. Interaction occurs with the exchange of a sequence of messages, each containing a set of data fields. The system that can exhibit faulty behavior is called the external unit. The other system, which is designed to tolerate faults, is the adaptable unit

This paper introduces a new scan control technique to realize low area overhead of scan-latches. Single transparent-latch is popularly used for register of high-throughput datapaths. For the scan-test of those kind of circuits, each transparent-latch is replaced with scan-latch. Conventional scan-latch cells controlled by synchronous signals consist of L1 latch and additional L2 latch, both of which function as master latch and slave latch respectively in scan mode. Apparently, additional L2 latch may result in area overhead. In order to avoid the area impact of such an additional L2 latch, we propose new timing methodology employing asynchronous control technique asP* protocol, and introduce asynchronous controlled scan-paths whose scan-latch employs only L1 latch. We evaluate the operation speed with HSPICE simulations and see they are practical. We also suggest DFT structure with our suggested asynchronous scan-paths, which is suitable for conventional synchronous test systems.

Large cluster systems have become widely utilized because they achieve a good performance/cost ratio especially in high performance computing. Although these cluster systems are distributed memory systems, coordinated checkpointing is a promising way to maintain high availability because the computing nodes are tightly connected to one another. However, as the number of computing nodes gets larger, the probability of multi-node failures increases. To tolerate multi-node failures, a large degree of redundancy is required in checkpointing, but this leads to performance degradation. Thus, we propose a new coordinated checkpointing called skewed checkpointing. In this method, checkpointing is skewed every time. Although each checkpointing itself contains only one degree of redundancy, this skewed checkpointing ensures /spl lfloor/log/sub 2/N/spl rfloor/ degrees of redundancy when the number of nodes is N. In this paper, we present the proposed method and an analysis of the performance overhead. Then, this method is applied to a cluster system and compared with other conventional checkpointing schemes. The results reveal the superiority of our method, especially for large cluster systems.

Nowadays, variable delay arithmetic units have been used for implementing a datapath of a target system in pursuit of performance improvement. However, adoption of variable delay arithmetic units requires modification of a typical synchronous control unit design methodology. A telescopic arithmetic unit based methodology is one of representative methodologies to design synchronous control units for variable delay datapaths. In this paper, we propose two optimization methods for it. Proposed optimization techniques will be analyzed in order to show their performance improvement effects explicitly.

Asynchronous speed independent (Sl) circuits based on an unbounded gate delay model often suffer from high area penalty. It happens due to the lack of efficient global optimization. This paper presents a boolean optimization method based on tranduction method to optimize asynchronous Sl circuits while preserving hazard-freeness.

We propose a method of synthesizing pipeline controllers as four-phase asynchronous circuits from specifications described as two-phase dependency graphs. Pipeline two-phase dependency graphs are transformed into four-phase ones by applying a transformation rule to each simple loop in the graphs. Four-phase dependency graphs are easily mapped onto four-phase asynchronous control circuits. We also discuss some simplification of four-phase dependency graphs.

The Quasi-Delay-Insensitive (QDI) model assumes that all the forks are isochronic. The isochronic-fork assumption requires uniform wire delays and uniform switching thresholds of the gates associated with the forking branches. This paper presents a method for determining such forks that do not have to satisfy the isochronic fork requirements, and presents experimental results that show many isochronic forks assumed for existing QDI circuits do not actually have to be "isochronic" or can be even ignored.

Asynchronous fine-grain pipeline circuits with dynamic gates are increasingly being used for high-performance datapath design in both synchronous and asynchronous processors. The dynamic gates intrinsically have storage elements for their outputs, which can implicitly function as pipeline latches. Therefore, most of fine-grain pipeline circuits are realized without explicit through-latches. For a testable design of such circuits, it is not reasonable to design a scan path with normal scan latch libraries from the viewpoint of area and performance penalty. We present a new testable design, for such asynchronous fine-grain pipelines with little penalty of performance and area overhead. The SPICE simulation shows that the performance overhead for the proposed design is 3.7% with a 0.4 um CMOS technology.

The Bulk-Synchronous Parallel (BSP) Model was proposed as a unifying model for parallel computation. By using Randomized Shared Memory (RSM), the model offers an asymptotically optimal emulation of the Parallel Random Access Machine (PRAM). By using the BSP model with RSM, we construct a gracefully degrading massively parallel system using a fault tolerance (FT) scheme that relies on memory duplication to ensure global memory integrity and to speed up the reconfiguration. After a fault occurs, global reconfiguration restores the logical properties of the system. Work done during reconfiguration is shared equally among the live processors, with minimal coordination. We analyze, at the level of the BSP model, how the performance of a system may change as processors fail and the performance of the interconnection network degrades. We relate the change in overall system performance to the change in computation and communication load on the live processors. Further, we show how to estimate the overhead imposed by the FT scheme. We evaluate the reconfiguration time, the overhead, and graceful degradation of the system experimentally by an implementation on a Massively Parallel Processor (MPP). We show that the predictions about the degradation of the system and the overhead cost of the scheme are accurate.

This paper proposes a new approach for asynchronous logic synthesis from Signal Transition Graph (STG) specifications. The Complete State Coding (CSC) property of STGs is a necessary condition to get a circuit implementation from an STG. We present a novel method to check the CSC property of STGs. We also discuss some heuristics which automatically modify the STG so that the CSC property is satisfied. Our approach gives the designer some freedom to specify in what way a given STG is modified. Experimental results on a large set of benchmarks indicate a clear improvement over previous methods both in terms of time taken and in the reduction of the two level area literals.

With the wire-delay problem moving into dominance in VLSI chip design, a fundamental limitation is being revealed in performance and dependability of synchronous systems which require global clock distribution with as little skew as possible. The worst-case delay is influenced not only by design and fabrication process but also by the operating environment, e.g. the power supply voltage and temperature. Asynchronous systems, with no global clock, can intrinsically enjoy: 1) average case performance instead of worst-case performance, 2) low power consumption, 3) ease of modular design, and 4) timing fault tolerance. We have designed and implemented a 32-bit fully asynchronous microprocessor, TITAC-2, which is the fastest and largest CMOS asynchronous microprocessor that has ever been operational.

Consider a system composed of N nodes that can be faulty or fault-free. The purpose of distributed system-level diagnosis is to have each fault-free node determine the state of all nodes of the system. This paper presents a Hierarchical Adaptive Distributed System-level Diagnosis (Hi-ADSD) algorithm, which is a fully distributed algorithm that allows every fault-free node to achieve diagnosis in, at most, (log/sub 2/ N)/sup 2/ testing rounds. Nodes are mapped into progressively larger logical clusters, so that tests are run in a hierarchical fashion. Each node executes its tests independently of the other nodes, i.e., tests are run asynchronously. All the information that nodes exchange is diagnostic information. The algorithm assumes no link faults, a fully-connected network and imposes no bounds on the number of faults. Both the worst-case diagnosis latency and correctness of the algorithm are formally proved. As an example application, the algorithm was implemented on a 37-node Ethernet LAN, integrated to a network management system based on SNMP (Simple Network Management Protocol). Experimental results of fault and repair diagnosis are presented. This implementation by itself is also a significant contribution, for, although fault management is a key functional area of network management systems, currently deployed applications often implement only rudimentary diagnosis mechanisms. Furthermore, experimental results are given through simulation of the algorithm for large systems of 64 nodes and 512 nodes.

Asynchronous design has a potential of solving many difficulties, such as clock skew and power consumption, which synchronous counterpart suffers with current and future VLSI technologies. This paper proposes a new delay model, the scalable-delay-insensitive (SDI) model, for dependable and high-performance asynchronous VLSI system design. Then, based on the SDI model, the paper presents the design, chip implementation, and evaluation results of a 32-bit asynchronous microprocessor TITAC-2 whose instruction set is based on the MIPS R2000. The measured performance of TITAC-2 is 52.3 MIPS using the Dhrystone V2.1 benchmark.

Fault management is a key functional area of network management systems, but current SNMP-based applications often implement rudimentary diagnosis mechanisms. Although the field of distributed system-level fault diagnosis has been flourishing for years, and a large number of mostly theoretical results have been devised, these results are not yet widely applied to network management systems. This paper presents the application of distributed diagnosis results to practical SNMP-based fault management. We implemented a modified version of the adaptive distributed system-level diagnosis algorithm using SNMP facilities. Two important modifications were introduced in the algorithm.: (1) to permit management of a variety of agents our implementation includes tested-only nodes, in addition to those that both test and are tested; (2) recognizing the need for a network management station (NMS) that doesn't tolerate large diagnosis delays, SNMP traps are used; the result is a diagnosis scheme that has high resilience to network faults and at the same time avoids inconvenient delays. The impact of the diagnosis on the performance of the network is analyzed in terms of the overhead imposed by SNMP diagnosis messages. The influence of both the number of nodes and the testing interval on the demand of bandwidth by the diagnosis process were evaluated, and it is shown that for common LAN capacities, diagnosis consumes less than 1% of the available bandwidth.

Fault management is a key functional area of network management systems, but currently deployed applications often implement rudimentary diagnosis mechanisms. This paper presents a new hierarchical adaptive distributed system-level diagnosis (Hi-ADSD) algorithm and its implementation based on SNMP (simple network management protocol). Hi-ADSD is a fully distributed algorithm that has diagnosis latency of at most (log/sub 2/N)/sup 2/ testing rounds for a network of N nodes. Nodes are mapped into progressively larger logical clusters, so that each node executes tests in a hierarchical fashion. The algorithm assumes no link faults, a fully-connected network and imposes no bounds on the number of faults. Both the worst-case diagnosis latency and correctness of the algorithm are formally proved. Experimental results are given through simulation of the algorithm for large networks. The algorithm was implemented on a small network using SNMP. We present details of the implementation, including device fault management, the role of the network management station, and the diagnosis management information base.

A new fault model for temporary failures is presented. This model is motivated and supported by recent experimental studies on types of temporary failures which cannot be explained by existing models. This new fault is called a Byzantine fault by analogy with the well-known Byzantine Generals problem in distributed systems. An example of an important type of Byzantine fault called a short transient is analyzed. The effects of Byzantine faults on concurrent error checking circuits are discussed. Design techniques to eliminate the effects of Byzantine faults are presented.>

A novel approach to formal verification of computer hardware designs at a higher level of representation than the register-transfer level is presented. In this verification method, the specification of a digital system is defined as the input/output behavior of the external systems that communicate with the target system. The specification description called a cospecification and the implementation description called an FBL (functional block level) description are transformed into a hardware model representation and composed by connecting their related ports in the hardware model. Whether the design is correct or not is verified by producing state transitions of the composite system. This verification method requires only input/output relations between the cospecification description and the FBL description. This feature makes it suitable for verification of a higher-level design in which implementation details may not be explicit.>

A concept of the error-secure and the error-propagating interfaces of the subsystems in a digital system is introduced, and shown to be useful for practical design and verification for a strongly fault-secure system which is known to achieve the totally self-checking (TSC) goal. A sufficient condition is shown for subsystem interfaces to meet for it to be possible to construct a strongly fault-secure system with no checkers used to monitor the embedded interfaces. On the basis of the error-secure/propagating concept, a design is presented for a strongly fault-secure microprocessor which implements the instruction set of Intel's i8080 8-b microprocessor. In the design, a complete set of building blocks is defined and all the partial interfaces are verified for the error secure/propagating property. Only four checkers are used at the embedded interfaces in the resulting strongly fault-secure processor.>

Different ways of defining a totally self-checking system are discussed. Based on the discussion, a self-testing error indicator is defined and shown to provide a useful means to ensure concurrent error detection for fault-tolerant systems. A simple design for the self-testing error indicator is presented.

It is proved that any sequential circuit with its next-state function d and output function w is strongly fault secure for unidirectional faults in d and w if i) the outputs of w are encoded in an unordered code, and ii) d and w are implemented with inverter-free circuits.

Undetectable bridging faults between two arbitrary leads, which may produce feedback loops, in a unate two-level irredundant AND-OR network are anlyzed and their effect on stuck-at fault detection tests is explored. As a result, any complete test set for single stuck-at faults proves to still remain valid in the presence of undetectable bridging faults.

Theorem 2ii), Theorem 7, and Corollary 5ii) with respect to detection and location of feedback bridging faults in the above paper1 are shown to be incorrect by counterexamples. In addition, some misunderstandings about asynchronous behavior of a faulty network with a feedback bridging are pointed out.

A universal single transition time (STT) state assignment is a way to give a valid STT state assignment in which all state variables that must change in a given transition are allowed to change simultaneously without critical races for any asynchronous sequential machine regardless of the configuration of its flow table. This paper presents a new systematic procedure for constructing universal STT state assignments and shows that the procedure can give better upper bounds on the number of state variables required for realizing asynchronous normal flow tables than any known universal STT state assignments, although there is some difference in standpoint between earlier works and the present one. It is further shown that the procedure can also be applied to improve the best known bounds for (2, 1) separating systems which are known to be less restricted universal assignments. The feature of the procedure lies in the idea that two binary code vectors are assigned to each internal state. In the resulting universal STT assignments, the number of state variables required is given by 2 · m1.59 where m = [log2 n], n being the number of states and [X] being the least integer ≥ X. Furthermore, the resulting (2, 1) separating systems require 2 ·m state variables.

One of two constructive procedures for universal single transition time (STT) state assignments presented in the paper [1] by Friedman et al. is not correct. A correct constructive procedure can be obtained by simply modifying the procedure of the literature with an additional restriction.