Increasing amount of electronics is being embedded into auto-motives. We are witnessing the conversion of the automotive from a purely mechanical device to an electrical/electronic/mechanical device. Purely electrical and hybrid-electrical vehicles are replacing the gasoline/diesel-driven vehicles. A variety of driver assistance systems are already available in modestly priced to high-end cars. Self-driven cars have been deployed in some cities on an experimental basis. The manufacturing sector is witnessing a similar revolution. Robots are being used in smart factories and warehouses. In a world where cyber-physical systems and life-forms will coexist, it is imperative that the electronics embedded into auto-motives and industrial systems has a long life and operates reliably in its environment. Reducing power and energy dissipation in these systems is important from many perspectives, including environmental impact, heating, and system reliability. In this paper, we survey the landscape of research and development towards the building of robust, low power semiconductor for automotive and industrial applications.

Today's SoCs are complex designs with multiple embedded processors, memory subsystems, and application specific peripherals. The memory architecture of embedded SoCs strongly influences the power and performance of the entire system. Further, the memory subsystem constitutes a major part (typically up to 70%) of the silicon area for the current day SoC. In this article, we address the on-chip memory architecture exploration for DSP processors which are organized as multiple memory banks, where banks can be single/dual ported with non-uniform bank sizes. In this paper we propose two different methods for physical memory architecture exploration and identify the strengths and applicability of these methods in a systematic way. Both methods address the memory architecture exploration for a given target application by considering the application's data access characteristics and generates a set of Pareto-optimal design points that are interesting from a power, performance and VLSI area perspective. To the best of our knowledge, this is the first comprehensive work on memory space exploration at physical memory level that integrates data layout and memory exploration to address the system objectives from both hardware design and application software development perspective. Further we propose an automatic framework that explores the design space identifying 100's of Pareto-optimal design points within a few hours of running on a standard desktop configuration.

Ultra low-power devices are being developed for embedded applications in bio-medical electronics, wireless sensor networks, environment monitoring and protection, etc. The testing of these low-cost, low-power devices is a daunting task. Depending on the target application, there are stringent guidelines on the number of defective parts per million shipped devices. At the same time, since such devices are cost-sensitive, test cost is a major consideration. Since system-level power-management techniques are employed in these devices, test generation must be power- management-aware to avoid stressing the power distribution infrastructure in the test mode. Structural test techniques such as scan test, with or without compression, can result in excessive heat dissipation during testing and damage the package. False failures may result due to the electrical and thermal stressing of the device in the test mode of operation, leading to yield loss. This paper considers different aspects of testing low-power devices and some new techniques to address these problems.

The memory subsystem is a major contributor to the performance, power, and area of complex SoCs used in feature rich multimedia products. Hence, memory architecture of the embedded DSP is complex and usually custom designed with multiple banks of single-ported or dual ported on-chip scratch pad memory and multiple banks of off-chip memory. Building software for such large complex memories with many of the software components as individually optimized software IPs is a big challenge. In order to obtain good performance and a reduction in memory stalls, the data buffers of the application need to be placed carefully in different types of memory. In this paper we present a unified framework (MODLEX) that combines different data layout optimizations to address the complex DSP memory architectures. Our method models the data layout problem as multi-objective genetic algorithm (GA) with performance and power being the objectives and presents a set of solution points which is attractive from a platform design viewpoint. While most of the work in the literature assumes that performance and power are non-conflicting objectives, our work demonstrates that there is significant trade-off (up to 70%) that is possible between power and performance.

The Test industry has come a long way over the past few decades. As a whole we have made great strides in the areas of:

With increasing use of low cost wire-bond packages for mobile devices, excessive dynamic IR-drop may cause tests to fail on the tester. Identifying and debugging such scan test failures is a very complex and effort-intensive process. A better solution is to generate correct-by-construction "power-safe" patterns. Moreover, with glitch power contributing to a significant component of dynamic power, pattern generation needs to be timing-aware to minimize glitching. In this paper, we propose a timing-based, power and layout-aware pattern generation technique that minimizes both global and localized switching activity. Techniques are also proposed for power-profiling and optimizing an initial pattern set to obtain a power-safe pattern set, with the addition of minimal patterns. The proposed technique also comprehends irregular power grid topologies for constraints on localized switching activity. Experiments on ISCAS benchmark circuits reveal the effectiveness of the proposed scheme

Process variation is an increasingly dominant phenomenon affecting both power and performance in sub-100 nm technologies. Cost considerations often do not permit over-designing the power supply infrastructure for test mode, considering the worst-case scenario. Test application must not over-exercise the power supply grids, lest the tests will damage the device or lead to false test failures. The problem of debugging a delay test failure can therefore be highly complex. We argue that false delay test failures can be avoided by generating "safe" patterns that are tolerant to on-chip variations. A statistical framework for power-safe pattern generation is proposed, which uses process variation information, power grid topology and regional constraints on switching activity. Experimental results are provided on benchmark circuits to demonstrate the effectiveness of the framework.

In sub-70nm technologies, leakage power becomes a significant component of the total power. Designers address this concern by extensive use of adaptive voltage scaling techniques to reduce dynamic as well as leakage power. Low-power scan test schemes that have evolved in the past primarily address dynamic power reduction, and are less effective in reducing the total power. We propose a Power-Managed Scan (PMScan) scheme which exploits the presence of adaptive voltage scaling logic to reduce test power. We also discuss some practical implementation challenges that arise when the proposed scheme is employed on industrial designs. Experimental results on benchmark circuits and industrial designs show a significant reduction in dynamic and leakage power. The proposed method can also be used as a vehicle to trade-off test application time with test power by suitably adjusting the scan shift frequency and scan-mode power supplies.

Excessive dynamic voltage drop in the power supply rails during test mode is known to result in false failures and impact yield when testing devices that use low-cost wire-bond packages. Identifying and debugging such test failures is a complex and effort-intensive process, especially when scan compression is involved. From a design cycle-tune view point, it is best to avoid this problem by generating "power-safe" scan patterns. The generation of power-safe patterns must take into consideration the DFT architecture, physical design, tuning and power constraints. In this paper, the authors propose such a framework and show experimental results on some benchmark circuits. The framework can address a non-uniform power grid and region-based power constraints. The authors show that glitching activity on nodes must be considered in order to correctly handle constraints on instantaneous peak power. The framework includes a power profiler that can analyze a pattern source for violations and a PODEM-based pattern generation engine for generating power-safe patterns.

At-speed testing is becoming crucial for modern very-large-scale-integration systems, which operate at clock speeds of hundreds of megahertz. In a scan-based test methodology, it is common to use a transition delay fault model for at-speed testing. The launching of the transition can be done either in the last cycle of scan shift [launch-off-shift (LOS)], or in a functional launch cycle that follows the scan shift and precedes the fast capture [launch-off-capture (LOC)]. The LOS technique offers significant advantages over the LOC in terms of coverage and pattern count, but since it requires the scan enable (SEN) signal to change state in the time period of one functional clock cycle, considerable engineering resources are required to close the timing on the SEN signal. Low-cost testers will not be able to provide the at-speed SEN signal as required by the LOS technique. We propose a scan-based at-speed methodology that generates “local” SEN signals that are guaranteed to switch in one functional clock cycle even when the external SEN signal does not change state at functional speed. Our technique is based on encapsulating the SEN control signal in the scan test data. A new scan cell, which is called the last transition generator, must be inserted in every scan chain for generating internal SEN signals. The proposed method is robust, practical, and readily implemented using commercial tools available today.

Power reduction during test application is important from the viewpoint of chip reliability and for obtaining correct test results. One of the ways to reduce scan test power is to block transitions propagating from the outputs of scan cells through combinational logic. In order to accomplish this, some researchers have proposed setting primary inputs to appropriate values or adding extra gates at the outputs of scan cells. In this article, we point out the limitations of suchfull gatingtechniques in terms of area overhead and performance degradation. We propose an alternate solution where a partial set of scan cells is gated. A subset of scan cells is selected to give maximum reduction in test power within a given area constraint. An alternate formulation of the problem is to treat maximum permitted test power as a constraint and achieve a test power that is within this limit using the fewest number of gated scan cells, thereby leading to the least impact in area overhead. Our problem formulation also comprehends performance constraints and prevents the inclusion of gating points on critical paths. The area overhead is predictable and closely corresponds to the average power reduction.

Power reduction during test application is important from the viewpoint of chip reliability and for obtaining correct test results. One of the ways to reduce scan test power is to block transitions from propagating from the outputs of scan cells through combinational logic. In order to accomplish this, some authors have proposed the setting of primary inputs to appropriate values or adding extra gates at the outputs of scan cells. In this paper, we point out the limitations of such full gating technique. We propose an alternate solution where a partial set of scan cells is gated. The subset of scan cells is selected to give maximum reduction in test power within a given area constraint. An alternate formulation of the problem is to treat maximum permitted test power and area overhead as constraints and achieve a test power that is within these limits using the fewest number of gated scan cells, thereby leading to least impact in area overhead. Our problem formulation also comprehends performance constraints and prevents the inclusion of gating points on critical paths. The area overhead is predictable and closely corresponds to the average power reduction.

A novel scan-based at-speed test is proposed in which a transition can be launched either from the scan path or the functional path. The technique improves the controllability of transition fault testing and it does not require the scan enable to change at-speed. The scan enable control information is encapsulated in the test data and transferred during the scan operation to generate the local scan enable signals during the launch and capture cycle. A new scan cell, referred to as local scan enable generator (LSEG), is inserted in the scan chains to generate the local scan enable signals. The proposed technique is robust, practice-oriented and suitable for designs targeted for very low cost ATEs.

We propose a clock-domain-based partitioning technique for practicing scan test in large system-on-chips with multiple clock domains with the intent of reducing test application time and test power.

With today's design size in millions of gates and working frequency in gigahertz range, at-speed test is crucial. The launch-off-shift method has several advantages over the launch-off-capture but imposes strict requirements on transition fault testing due to at-speed scan enable signal. A novel scan-based at-speed test is proposed which generates multiple local fast scan enable signals. The scan enable control information is encapsulated in the test data and transferred during the scan operation. A new scan cell, referred to as last transition generator (LTG), is inserted in the scan chains to generate the fast local scan enable signal. The proposed technique is robust, practice-oriented and suitable for use in an industrial flow.

While design-for-test methods such as scan, ATPG, and memory BIST are now well established for ASIC products, their run-time for multi-million gate designs has become a problem. Too often, a tape-out is held up because pattern generation and verification are incomplete. This work describes a holistic design-for-test approach which exploits both hierarchy and parallelism on every aspect of the DFT to minimize the run-time impact.

The goal of this paper is to reduce the test application time for microprocessors. Since the functional fault model is used for testing microprocessors, test development time is greatly reduced. But functional test generation leads to a large number of tests. The size of the test set is an important factor, as it determines both the storage for test instructions in the test equipment, as well as the test application time. The problem becomes still more serious when the processor is embedded as a core in a system-on-chip. Hence, in this paper we try to address the problem of reducing the number of tests. We use the available structural information about the microprocessors to drop some of the functional tests. Some valid assumptions about the faults that are present in the microprocessor, e.g., only single stuck at faults are present, is made to reduce the number of tests. We develop fault-grading concepts and use them to reduce the number of tests. We generate tests for Intel 8086, Motorola 68000 microprocessors using functional testing procedures and reduce the number of tests using our fault grader.

We address the problem of scheduling test sessions for core based systems-on-chip (SOC). We assume the built-in self-test methodology for testing individual cores and permit sharing of test resources (pattern generators and signature registers) among cores. Our objective is to minimize the test application time and the test area overhead, treating the total power dissipation as a constraint. A vast solution space exists for the problem of test scheduling. At one end of the spectrum is an entirely sequential test schedule which will consume the least test power, and at the other end of the spectrum is a fully concurrent test schedule which will consume the largest test power. Each of these solutions will differ in terms of the test area overhead and the test application time. We show a polynomial-time algorithm for finding an optimum power-constrained schedule which minimizes the test time. In our formulation, we implicitly address the problem of minimizing the test area overhead by introducing the notion of area penalty for merging the test sessions for two different cores. We argue that the merger of two test sessions for two different cores must address such issues as similarity of the cores being tested as well as layout-related issues. We capture these area penalties in the form of a desirability matrix which is the essential data structure for our scheduling algorithm. We report the results of our implementation of the scheduling algorithm on two circuits.

While core-based design is itself a challenging task, it is equally challenging for a core vendor to provide information about a core without compromising on the protection of intellectual property. A number of issues are to be taken into consideration when designing a core. While conventional goals such as minimal area and maximal performance continue to hold, additional constraints such as core testability and power dissipation will have to be considered. Since the vendor of a core does not reveal details about the internals of the core, it is often the responsibility of the vendor to provide the test plan for the core. In this paper, we present our experiences in designing a testable CORDIC core.

The "system-on-chip" revolution has posed a number of new challenges to the test engineers. We address the issue of high power dissipation during testing, which can reach levels that are beyond the safe upper limit associated with the chosen packaging technology. A study undertaken by Zorian (1993) reveals that test power can be as large as 200% or more in comparison to the normal power. In the test mode, input vectors are normally applied in an uncorrelated manner, leading to an increase in the average Hamming distance between two successive vectors. This implies a larger switching activity, and, for CMOS circuits, implies a larger power dissipation. In this paper, our attempt is to look at Built-in Self-Test (BIST) architectures from the view point of power dissipation, fault-coverage, area, and test length. We report experimental results for a CORDIC chip. Our results indicate that BIST architectures differ significantly from one another in terms of power dissipation, giving the test designer an opportunity to address the problem of excessive heating during testing.

As the amount of data transmitted over a network increases and high bandwidth applications requiring point to multipoint communications like videoconferencing, distributed database management or cooperative work become widespread, it becomes very important to optimize network resources. One such optimization is multicast tree generation. The problem of generating a minimum cost multicast tree given the network topology and costs associated with the connecting links can be modelled as a Steiner tree problem which is NP-complete. Much work has been done in the direction of obtaining near-optimal multicast trees when the objective is only to minimize the cost. However, many real time applications such as videoconferencing require that data be sent within prespecified delay limits in order to avoid problems such as anachronism and lack of synchronization. We deal with the delay-bounded cost-optimal multicast tree (DBCPAT) generation problem. Specifically, we discuss a closely related problem which is to find a delay-bounded cost-optimal path (DBCP) between a specified source and destination node. Such a path can be used as a starting point to solve the DBCMT. We present an exact solution to the DBCP which is based on the branch-and-bound paradigm. We also propose a heuristic technique to solve the DBCP using the principle of evolutionary computing. The results obtained using the two techniques are compared for several large networks.

Although distributed computing over a network of computers has become a reality, its success mainly depends on the performance of the underlying network. In this paper, we consider the problem of designing a local area network with specified cost and performance constraints. The cost and performance of a local area network (LAN) are directly related to its topology. Using the a priori knowledge of the approximate number of users of the network and the kind of communication traffic that must be supported, the designer can optimize the design of the of a LAN for superior performance. Design decisions include the number of LAN segments, number of bridges, assignment of users to segments, and the method to interconnect the segments through bridges. In case of ATM networks, the decisions are regarding the number of ATM switches, the assignment of hosts to switches, and the way to connect switches through cross-connects. While assigning too many users to the same segment may cause large delays due to the sharing of network bandwidth, splitting the LAN into too many segments will increase the cost of the LAN. We report a greedy heuristic algorithm for local area network design. We propose an interesting method to construct good initial solutions to the topology design problem using a heuristic method which is based on the three-opt technique for solving the travelling salesperson problem. Our experimental results indicate that the heuristic algorithm finds good solutions.

The problem of finding an optimal multicast tree in a point to point network translates to the Steiner problem in graphs. Since the Steiner problem is NP complete, heuristic approaches are required for path setup. The problem takes a new dimension in wide area networks, where centralized algorithms are not feasible, and distributed schemes are needed. It is also desirable that node participation for path setup is limited to nodes directly involved in the multicast. An additional requirement that comes from the nature of the applications such as video conferencing that use the multicast support from the network is that of bounded end to end delays along any path from the source to each destination in the multicast tree. We present a heuristic algorithm that ensures delay bounds, is distributed and produces trees that are only slightly more expensive than those produced by centralized algorithms. Further we examine the degradation in performance in case of changing delays along network links (where QoS guarantees on delay are not available), and propose ways of making the tree adaptive to these changes. This dynamic routing approach minimizes resource reservation demands and also makes changing multicast groups permissible.

The existing algorithms for deadlock-free multicasting in interconnection networks assume the Hamiltonian property in the networks topology. However, these networks fail to be Hamiltonian in the presence of faults. This paper investigates the use of Euler circuits in deadlock-free multicasting. Not only are Euler circuits known to exist in all connected networks, a fast polynomial-time algorithm exists to find an number circuit in a network. We present a multicasting algorithm which works for both regular and irregular topologies. Our algorithm is applicable to store-and-forward as well as wormhole-routed networks. We show that at most two virtual channel are required per physical channel for any connected network. We also prove that no virtual channels are required to achieve deadlock-free multicasting on a large class of networks. Unlike other existing algorithms for deadlock-free multicasting in faulty networks, our algorithm requires a small amount of information to be stored at each node. The potential of our technique is further illustrated with the help of various examples. A performance analysis on wormhole-routed networks shows that our routing algorithm out-performs existing multicasting procedures.

In this paper, we report a tool called MODET for automatic test generation for path delay faults in modular combinational circuits. Our technique uses precomputed robust delay tests for individual modules to compute robust delay tests for the module-level circuit. We propose a novel technique for path selection in module-level circuits and report efficient algorithms for delay test generation. MODET has been implemented and tested against a number of hierarchical circuits with impressive speedups in relation to gate level test generation.

A digital optical computer architecture consists of several stages, or slots, of optical arrays. Each slot can be viewed as a rectangular array of locations which are classified as vital and extraneous, depending on whether or not the location is on an optical signal path. A defective optical array can be used in a slot provided that the defective locations of the array do not coincide with the vital locations of the slot. The problem of low manufacturing yield of optical arrays can be alleviated by utilizing defective arrays that are consistent with slots. The mapping of arrays to slots so as to maximize the number of machines that can be assembled is a difficult discrete optimization problem. This is because a larger array can become consistent to a slot through transformations such as translation and rotation. We propose the use of evolutionary programming for the assembly of optical computers. Our experimental results indicate that a genetic algorithm is a powerful technique to search the vast solution space efficiently.

STAFAN (statistical fault analysis) is a well known testability analysis program which predicts the fault coverage of a digital circuit under the stuck-at fault model, without actually performing fault simulation. STAFAN offers speed advantage over other testability analysis programs such as SCOAP; further, it explicitly predicts the fault coverage for a given test set, unlike other testability measures which are harder to interpret. STAFAN works on gate-level digital circuits composed of basic logic gates. In this work, we show how a STAFAN-like testability analysis program can be constructed for circuits built out of register-level modules. With the proliferation of high-level synthesis and testability-driven synthesis, it is becoming more and more important to have fast testability analysis tools which operate on register-level components such as adders, multipliers, multiplexers, busses, and so on. Our testability analysis algorithm, which we call F-STAFAN, fills this void. We have implemented F-STAFAN on a Sun/SPARC workstation and describe its performance on several register-level circuits.

A number of existing multiprocessors are based on the hypercube interconnection network. The popularity of the hypercube is due to its small communication diameter, which grows logarithmically with the cube size, its fault-tolerant properties, and its modularity which makes it possible to build a larger cube from smaller subcubes. The star graph has been studied as a network topology for fault-tolerant parallel com puting. Unfortunately, the size of the network grows too sharply with n to be affordable for values of n larger than 7 or 8. We introduce a novel intercon nection network known as the incomplete star graph, which overcomes the above problem while retaining the most of the advantages of the star graph. We present the architecture of the incomplete star graph and compare its performance with the full star as well as competing architectures such as the incomplete hypercube and arrangement graphs. We provide routing algorithms for both non-faulty and faulty incompletestar graphs, and study their performance.

Describes a parallel search-and-learn technique for obtaining high quality solutions to the traveling salesperson problem (TSP). The combinatorial search space is decomposed so that multiple processors can simultaneously look for local optimal solutions in the subspaces. The local optima are then compared to learn which moves are good-a move is defined to be good if all the search processes have voted in consensus for the move. Based on this learning, the original problem is transformed into a constrained optimization; a constraint requires a specific edge to be included in the final tour. The constrained optimization problem is modeled as a TSP of smaller size, and is again solved using the parallel search technique. This process is repeated until a TSP of manageable size is reached, which can be solved effectively; the tour obtained at this last stage is then expanded retrogressively until the tour for the original problem is obtained. The results of parallel implementation on a 32-node transputer are described.