The Vehicle Routing Problem (VRP) is an NP-Hard optimization problem that has been widely studied over the last decades due to its wide practical applications. The goal of the VRP is to design efficient routes for vehicles performing service functions such as the distribution of goods from one or more central locations. There exist many variants to the VRP. These variations arise due to application-specific constraints such as vehicle capacities, delivery time windows, split deliveries, and many more. Due to the complexity of the problem, solvers are usually designed for specific variants and do not generally scale well to larger problem instances. As we approach the physical scaling limits of Moore's law, different novel special-purpose hardware are being designed for solving combinatorial optimization problems such as quantum and quantum-inspired devices. However, these devices are able to solve problems up to fixed variable sizes. In this work, we carry out experiments on the Fujitsu Digital Annealer (DA), quantum-inspired hardware, and show that we are able to get near-optimal results for instances of the Capacitated VRP (CVRP) that can be directly solved on the DA. We further develop a hybrid method for solving large-scale VRP instances. In order to achieve this, we develop a novel candidate route generation method, whose core solves a multi-objective clustering problem on the DA. Once a set of candidate routes has been selected, we then solve a Set Partitioning Problem on the DA to get a final solution. We apply our method to the CVRP and the CVRP with Time-Windows and show that we are able to get near-optimal solutions for problem instances significantly larger the base solvers could solve directly, within the same amount of computation time.

Automated unit test generation bears the promise of significantly reducing test cost and hence improving software quality. However, the maintenance cost of the automatically generated tests presents a significant barrier to adoption of this technology. To address this challenge, we propose a novel technique for automated and fine-grained incremental generation of unit tests through minimal augmentation of an existing test suite. The technique uses iterative, incremental refinement of test-drivers and symbolic execution, guided by a diagnostics engine. The diagnostics engine works off a novel precise and efficient byte-level dynamic dependence analysis built using Reduced Ordered Binary Decision Diagrams (ROBDDs). We present a tool FSX implementing this technique and evaluate it under two practical use-cases of incremental unit test generation, on five revisions of the open-source software iPerf, as well as on 3 large subjects, comprising more than 60 thousand lines of code, from in-house commercial network products. The evaluation shows that FSX can generate high-quality unit tests on large industrial software while minimizing the maintenance cost of the overall test-suite.

Automated unit test generation bears the promise of significantly reducing test cost and hence improving software quality. However, the maintenance cost of the automatically generated tests presents a significant barrier to adoption of this technology. To address this challenge, in previous work, we proposed a novel technique for automated and fine-grained incremental generation of unit tests through minimal augmentation of an existing test suite. In this paper we describe a tool FSX, implementing this technique. We describe the architecture, user-interface, and salient features of FSX, and specific practical use-cases of its technology. We also report on a real, large-scale deployment of FSX, as a practical validation of the underlying research contribution and of automated test generation research in general.

We study the problem of reducing test cases generated by bit vector based symbolic execution test generators. In particular, we first consider a guileless test case generation approach that generates assignment statements for each symbolic scalars, array and structure elements and object fields. We show that test cases generated by this approach can be significantly verbose. We then propose a method for making the generated test cases more succinct using a novel analysis entitled don't care analysis. Don't care analysis identifies assignment statements that can be safely removed from the test cases without affecting the overall code coverage. Our algorithm is based on binary and delta-debugging search. Because it exploits the knowledge of the internal SAT solver, it is effective and efficient in practice. To our knowledge, this is the first fully automatic approach that reduces the sizes of test cases generated using symbolic execution. We implement our test case reduction technique for the KLEE test generation tool and evaluate on 295 programs and functions. Our results are encouraging: in average, the reduced test cases are 50 times smaller than the test cases generated by the guileless test case generator. In addition, since our don't care analysis is tightly integrated into the test case generation tool, its overhead to the overall test generation process is negligible.

We present SymJS, a comprehensive framework for automatic testing of client-side JavaScript Web applications. The tool contains a symbolic execution engine for JavaScript, and an automatic event explorer for Web pages. Without any user intervention, SymJS can automatically discover and explore Web events, symbolically execute the associated JavaScript code, refine the execution based on dynamic feedbacks, and produce test cases with high coverage. The symbolic engine contains a symbolic virtual machine, a string-numeric solver, and a symbolic executable DOM model. SymJS's innovations include a novel symbolic virtual machine for JavaScript Web, symbolic+dynamic feedback directed event space exploration, and dynamic taint analysis for enhancing event sequence construction. We illustrate the effectiveness of SymJS on standard JavaScript benchmarks and various real-life Web applications. On average SymJS achieves over 90% line coverage for the benchmark programs, significantly outperforming existing methods.

In this paper we present JST, a tool that automatically generates a high coverage test suite for industrial strength Java applications. This tool uses a numeric-string hybrid symbolic execution engine at its core which is based on the Symbolic Java PathFinder platform. However, in order to make the tool applicable to industrial applications the existing generic platform had to be enhanced in numerous ways that we describe in this paper. The JST tool consists of newly supported essential Java library components and widely used data structures; novel solving techniques for string constraints, regular expressions, and their interactions with integer and floating point numbers; and key optimizations that make the tool more efficient. We present a methodology to seamlessly integrate the features mentioned above to make the tool scalable to industrial applications that are beyond the reach of the original platform in terms of both applicability and performance. We also present extensive experimental data to illustrate the effectiveness of our tool.

Programs written for GPUs often contain correctness errors such as races, deadlocks, or may compute the wrong result. Existing debugging tools often miss these errors because of their limited input-space and execution-space exploration. Existing tools based on conservative static analysis or conservative modeling of SIMD concurrency generate false alarms resulting in wasted bug-hunting. They also often do not target performance bugs (non-coalesced memory accesses, memory bank conflicts, and divergent warps). We provide a new framework called GKLEE that can analyze C++ GPU programs, locating the aforesaid correctness and performance bugs. For these programs, GKLEE can also automatically generate tests that provide high coverage. These tests serve as concrete witnesses for every reported bug. They can also be used for downstream debugging, for example to test the kernel on the actual hardware. We describe the architecture of GKLEE, its symbolic virtual machine model, and describe previously unknown bugs and performance issues that it detected on commercial SDK kernels. We describe GKLEE's test-case reduction heuristics, and the resulting scalability improvement for a given coverage target.

This paper presents a framework for high-level design validation using an efficient register-transfer level (RTL) automatic test pattern generator (ATPG). The RTL ATPG algorithm first generates a test environment for each validation objective, which includes variable assignments, conditional statements, and arithmetic expressions in the hardware description language (HDL) description. The test environment for a given validation objective is a set of symbolic conditions that allow for full controllability and observability of that objective. After the RTL ATPG terminates, a back-end translator intelligently translates the test environments into validation vectors by filling in the necessary values. Since the observability of error effect is naturally handled by the RTL ATPG algorithm, this approach is superior to most existing validation methods, which only focus on the excitation of HDL constructs. A set of heuristics is proposed to utilize high-level circuit information to enhance the RTL ATPG algorithm and to maximize the validation efficiency. The RTL ATPG algorithm is also coupled with an improved RTL validation-coverage metric, which can help users to gain a higher degree of confidence on the quality of generated validation vectors. The usage of the coverage metric also results in the generation of compact vector sets. Experimental results on academic and industrial benchmark circuits demonstrate that our method is able to obtain very high design-error coverage in short execution times.

This talk focuses on an industrial effort to generate sequential test patterns automatically from functional register transfer level (RTL) circuits that target detection of stuck-at faults in the circuit at the logic level. The RTL circuit is assumed to be described in some high level description language (HDL) like VHDL or Verilog which is currently a standard practice in industrial ASIC designs. Currently only block level circuits of the order of tens of thousands of HDL lines are targeted

Software programs written in some programming languages like C, C++, Java, etc, are mostly verified by functional simulation. Since exhaustive functional simulation is impossible for even a small C program, it is important to quantitatively measure the extent of design verification during simulation by a set of test vectors. Various coverage metrics have been proposed for measuring the degree of design verification. Most of them compute the extent of design excitation (controllability) but are unable to say whether the excitation responses have propagated to observable points in the program (observability). In this paper we propose a metric for code coverage analysis of C programs that addresses not only controllability but tackles observability as well. Thus, this metric is able to tell what percentage of the simulation responses have been propagated to observable points in the program like primary outputs or printed variables. We improve upon a recently proposed observability enhanced software coverage metric by increasing the accuracy of the analysis as well as decreasing the simulation runtime overhead by using an event-driven coverage analysis method. We report some experimental results of using our coverage analysis tool for several C programs.

We present a framework for high-level design validation using an efficient register-transfer level (RTL) automatic test pattern generator (ATPG). The RTL ATPG generates the test environments for validation targets, which include variable assignments, conditional statements, and arithmetic expressions in the HDL description. A test environment is a set of conditions that allow for full controllability and observability of the validation target. Each test environment is then translated to validation vectors by filling in the unspecified values in the environment. Since the observability of error effect is naturally handled by our ATPG, our approach is superior to methods that only focus on the excitation of HDL descriptions. The experimental results on ITC99 benchmark circuits and an industrial circuit demonstrate that very high design error coverage can be obtained in a small CPU times.

In this paper, we examine how good validation test benches can be automatically generated starting from the RTL description of a circuit. We develop our methodology based on extensive experiments performed with several popular benchmarks as well as industrial circuits.

We present a precomputation-based guarding technique to reduce both dynamic and static power consumptions in CMOS VLSI circuits. More precisely, a high threshold sleep transistor is placed in series with some portions of the circuit. Based on the input values of the circuit, the sleep transistor is turned on and off, thus, saving both dynamic and static power. We show how to apply this technique to a number of common arithmetic blocks, including comparators, adders and multipliers. Finally, dynamic guarding and sleep transistor activity reduction techniques for improving the performance of the method are presented. Experimental results show 81% reduction in the power consumption of data path modules of a commercial VLIW processor can be achieved using our techniques. This is 20% higher than what has been achieved by previous methods.

We present an efficient register-transfer level automatic test pattern generation (ATPG) algorithm. First, our ATPG generates a series of sequential justification and propagation paths for each RTL primitive via a deterministic branch-and-bound search process, called a test environment. Then the precomputed test vectors for the RTL primitives are plugged into the generated test environments to form gate-level test vectors. We augment a 9-valued algebra to efficiently represent the justification and propagation objectives at the RT Level. Our ATPG automatically extracts any finite state machine (FSM) from the circuit, constructs the state transition graph (STG), and uses high-level information to guide the search process. We propose new static methods to identify embedded counter structures, and we use implication-based techniques and static learning to find the FSM traversal sequences sufficient to control the counters. Finally, a simulation-based RTL extension is added to augment the deterministic test set in a few cases when there is additional room for the improvement in fault coverage. Experimental results show that our new deterministic RTL techniques achieve several orders of magnitude reduction of test generation time without compromising fault coverage when compared to gatelevel ATPG tools. Our ATPG also outperforms a recently reported simulation-based high-level ATPG tool in terms of both fault coverage and CPU time. 1.

In this paper, we present an algorithm for generating test patterns automatically from functional register-transfer level (RTL) circuits that target detection of stuck-at faults in the circuit at the logic level. In order to do this, we utilize a data structure named assignment decision diagram that has been proposed previously in the field of high-level synthesis. With the advent of RTL synthesis tools, functional RTL designs are now widely used in the industry to cut design turn around time. This paper addresses the problem of test pattern generation directly at this level due to a number of advantages inherent at the RTL. Since the number of primitive elements at the RTL is usually less than the logic level, the problem size is reduced leading to a reduction in the test-generation time over logic-level automatic test pattern generation (ATPG). Also, a reduction in the number of backtracks can lead to improved fault coverage and reduced test application time over logic-level techniques. The test patterns thus generated can also be used to perform RTL-RTL and RTL-logic validation. The algorithm is very versatile and can tackle almost any type of single-clock design, although performance varies according to the design style. It gracefully degrades to an inefficient logic-level ATPG algorithm if it is applied to a logic-level circuit. Experimental results demonstrate that over 1000 times reduction in test-generation time can be achieved by this algorithm on certain types of RTL circuits without any compromise in fault coverage.

In this paper, we address an important problem associated with hierarchical design flows (termed the mapping problem): identifying correspondences between a signal in a high-level specification and a net in its lower level implementation. Conventional techniques use shared names to associate a signal with a net whenever possible. However, given that a synthesis flow may not preserve names, such a solution is not universally applicable. This work provides a robust framework for establishing register-transfer level (RTL) signal to gate-level net correspondences for a given design. Our technique exploits the observation that circuit diagnosis provides a convenient means for locating faults in a gate-level network. Since our problem requires locating gate-level nets corresponding to RTL signals, we formulate the mapping problem as a query whose solution is provided by a circuit diagnosis engine. Our experimental work with industrial designs for many mapping cases shows that our solution to the mapping problem is 1) fast and 2) precise in identifying the gate-level equivalents (the number of nets returned by our mapping engine for a query is typically one or two even for designs with tens of thousands of VHDL lines).

In this paper, we present an algorithm for generating test patterns automatically from functional register transfer level (RTL) circuits that target detection of stuck-at faults in the circuit at the logic level. To do this we utilize a data structure named assignment decision diagram which has been proposed previously in the field of high level synthesis. The advent of RTL synthesis tools have made functional RTL designs widely popular. This paper addresses the problem of test pattern generation directly at this level due to a number of advantages inherent at the RTL. Since the number of primitive elements at the RTL is usually lesser than the logic level, the problem size is reduced leading to a reduction in the test generation time over logic-level ATPG. A reduction in the number of backtracks can lead to improved fault coverage and reduced test application time over logic-level techniques. The test patterns thus generated can also be used to perform RTL-RTL and RTL-logic validation. The algorithm is very versatile and can tackle almost any type of single-clock design though performance varies according to the design style. It gracefully degrades to an inefficient logic-level ATPG algorithm if it is applied to a logic-level circuit. Experimental results demonstrate that over 1000 times reduction in test generation time can be achieved by this algorithm on certain types of RTL circuits without any compromise in fault coverage.

In this paper, we consider the mapping problem of identifying correspondences between a signal in a high-level specification and a net in a lower-level implementation for a given design. Conventional techniques use shared names to associate a signal with a net whenever possible. However, given that a synthesis flow may not preserve names, solutions to the above problem eventually take recourse to expensive alternatives such as formal verification. This paper provides a robust framework for identifying RTL signal to gate-level net correspondences for a given design. Our technique exploits the observation that circuit diagnosis provides a convenient means for locating faults in a gate-level network. Since our problem requires locating gate-level nets corresponding to RTL signals, we formulate the mapping problem as a query whose solution is provided by a circuit diagnosis engine. Our experimental work with industrial designs for many mapping cases shows that our solution to the mapping problem is (i) fast, and (ii) precise in identifying the gate-level equivalents (the number of nets returned by our mapping engine for a query is typically or 2 even for designs with tens of thousands of VHDL lines).

This paper proposes a new methodology for testing a core-based system chip, targeting the simultaneous reduction of test area overhead and test application time. At the core level, testability and transparency can be achieved by the core provider by reusing existing logic inside the core, providing different versions of the core having different area overheads and transparency latencies. The technique analyzes the topology of the system-chip to select the core versions that best meet the user's desired test area overhead and test application time objectives. Application of the method to example system-chips demonstrates the ability to design highly testable system-chips with minimized test area overhead, minimized test application time, or a desired tradeoff between the two. Significant reduction in area overhead and test application time compared to existing system chip testing techniques is also demonstrated.

This paper introduces a novel scheme for testing register-transfer level (RTL) controller/data paths using built-in self-test (BIST). The scheme uses the controller netlist and the data path of a circuit to extract a test control/data flow (TCDF) graph. This TCDF is used to derive a set of symbolic justification and propagation paths (known as the test environment) to test some of the operations and variables present in it. If it becomes difficult to generate such test environments with the derived TCDF's, a few test multiplexers are added at suitable points in the circuit to increase its controllability and observability. The test environment of an operation (variable) guarantees the existence of a path from the primary inputs of the circuit to the inputs of the module (register) to which the operation (variable) is mapped, and a path from the output of the module (register) to a primary output of the circuit. Since the search for a test environment is done symbolically, it is very fast and needs to be done only once for each module or register,in the circuit. This test environment can then be used to exercise a module or register in the circuit with pseudorandom pattern generators which are placed only at the primary inputs of the circuit. The test responses can he analyzed with signature analyzers which are only placed at the primary outputs of the circuit. Unlike many RTL BIST schemes, an increase in the data path bit-width does not adversely impact the complexity of our testability analysis scheme since the analysis is symbolic. Every module in the module library is made random-pattern testable, whenever possible, using gate-level testability insertion techniques. This is a one-time cost. Finally, a BIST controller is synthesized to provide the necessary control signals to form the different test environments during testing, and a BIST architecture is superimposed on the circuit. Experimental results on a number of industrial and university benchmarks show that high fault coverage (>99%) can be obtained with our scheme. The average area overhead of the scheme is 6.9% which is much lower than many existing logic-level BIST schemes. The average delay overhead is only 2.5%. The test application time to achieve the high fault coverage for the whole circuit is also quite low.

In a fundamental paradigm shift in system design, entire systems are being built on a single chip, using multiple embedded cores. Though the newest system design methodology has several advantages in terms of time-to-market and system cost, testing such core-based systems is difficult, mainly due to the problem of justifying test sequences at the inputs of a core embedded deep in the circuit and propagating test responses from the core outputs. In this paper, we first present a design for testability technique for testing such core-based systems. In this scheme, untestable cores are first made testable using hierarchical testability analysis techniques. If necessary, additional testability hardware is added to the cores to make them transparent so that they can propagate test data without information loss. This testability and transparency technique is currently applicable to cores of the following types: application-specific integrated circuits, application-specific programmable processors, and application-specific instruction processors. Other core types can be made testable and transparent using traditional techniques. The testable and transparent cores can then he integrated together with some system-level testability hardware to ensure justification of precomputed test sequences of each core from system primary inputs to the core inputs and propagation of test responses from core outputs to system primary outputs. Justification and propagation of test sequences are done at the system level by extending and suitably modifying the symbolic hierarchical testability analysis method that has been successfully applied to register-transfer level circuits. Since the testability analysis method is symbolic, the system test generation method is independent of the bit-width of the cores. The system-level test set is obtained as a byproduct of the testability analysis and insertion method without further search. The test methodology was applied to six example systems. Besides the proposed test method, the two methods that are currently used in the industry were also evaluated: (1) FScan-BScan, where each core is full-scanned, and system test is performed using boundary scan and (2) FScan-TBus, where each core is full-scanned, and system test is performed using a test bus. The experiments show that the proposed scheme has significantly lower area overhead, delay overhead, and test application time compared to FScan-BScan and FScan-TBus, without any compromise in the system fault coverage.

In this paper, we present design for testability (DFT) and hierarchical test generation techniques for facilitating the testing of application-specific programmable processors (ASPPs) and application-specific instruction processors (ASIPs). The method utilizes the register-transfer level (RTL) circuit description of an ASPP or ASIP to come up with a set of test microcode patterns which can be written into the instruction read-only memory (ROM) of the processor. These lines of microcode dictate a new control/data flow in the circuit and can be used to test modules which are not easily testable. The new control/data flow is used to justify precomputed test sets of a module from the system primary inputs to the module inputs and propagate output responses from the module output to the system primary outputs. The testability analysis, which is based on the relevant control/data flow extracted from the RTL circuit, is symbolic. Thus, it is independent of the bit-width of the data path and is extremely fast. The test microcode patterns are a by-product of this analysis. If the derived test microcode cannot test all untested modules in the circuit, then test multiplexers are added (usually to the off-critical paths of the data path) to test these modules. This is done to guarantee the testability of all modules in the circuit. If the control microcode memory of the processor is erasable, then the test microcode lines can be erased once the testing of the chip is over. In that case, the DFT scheme has very little overhead (typically less than 1%). Otherwise, the test microcode lines remain as an overhead in the control memory. The method requires the addition of only one external test pin. Application of this technique to several examples has resulted in a very high fault coverage (above 99.6%) for all of them. The test generation time is about three orders of magnitude smaller compared to an efficient gate-level sequential test generator. The average area overhead (without assuming an erasable ROM) is 3.1% while the delay overheads are negligible. This method does not require any scan in the controller or data path. It is also amenable to at-speed testing.

This paper proposes a new methodology for testing a core-based system-on-chip (SOC), targeting the simultaneous reduction of test area overhead and test application time. Testing of embedded cores is achieved using the transparency properties of surrounding cores. At the core level, testability and transparency can be achieved by reusing existing logic inside the core, and providing different versions of the core having different area overheads and transparency latencies. At the chip level, the technique analyzes the topology of the SOC to select the core versions that best meet the user's desired test area overhead and test application time objectives. Application of the method to example SOCs demonstrates the ability to design highly testable SOCs with minimized test area overhead, minimized test application time, or a desired trade-off between the two. Significant reduction in area overhead and test application time compared to an existing SOC testing technique is also demonstrated.

This paper introduces a novel scheme for testing register-transfer level controller/data paths using built-in self-test (BIST). The scheme uses the controller netlist and the data path of a circuit to extract a test control/data flow (TCDF) which consists of operations mapped to modules in the circuit and variables mapped to registers. This TCDF is used to derive a set of symbolic justification and propagation paths (known as test environment) to test some of the operations and variables present in it. If it becomes difficult to generate such test environments with the derived TCDFs, a few test multiplexers are added at suitable points in the circuit to increase its controllability and observability. This test environment can then be used to exercise a module or register in the circuit with pseudorandom pattern generators which are placed only at the primary inputs of the circuit. The test responses can be analyzed with signature analyzers which are only placed at the primary outputs of the circuit. Every module in the module library is made random-pattern testable, whenever possible, using gate-level testability insertion techniques. Finally, a BIST controller is synthesized to provide the necessary control signals to form the different test environments during testing, and a BIST architecture is superimposed on the circuit. Experimental results on a number of industrial and university benchmarks show that high fault coverage (>99%) can be obtained with our scheme in a small number of test cycles at an average area (delay) overhead of only 6.4% (2.5%).

In this paper, we present a technique for extracting functional (control/data flow) information from register-transfer level controller/data path circuits, and illustrate its use in design for hierarchical testability of these circuits. This scheme does not require any additional behavioral information. It identifies a suitable control and data flow from the register-transfer level circuit, and uses it to test each embedded element in the circuit by symbolically justifying its precomputed test set from the system primary inputs to the element inputs and symbolically propagating the output response to the system primary outputs. When symbolic justification and propagation become difficult, it inserts test multiplexers at suitable points to increase the symbolic controllability and observability of the circuit. These test multiplexers are mostly restricted to off-critical paths. Testability analysis and insertion are completely based on the register-transfer level circuit and the functional information automatically extracted from it, and are independent of the data path bit width owing to their symbolic nature. Furthermore, the data path test set is obtained as a byproduct of this analysis without any further search. Unlike many other design-for-testability techniques, this scheme makes the combined controller-data path very highly testable. It is general enough to handle control-flow-intensive register-transfer level circuits like protocol handlers as well as data-flow intensive circuits like digital filters. It results in low area/delay/power overheads, high fault coverage, and very low test generation times (because it is symbolic and independent of bit width). Also, a large part of our system-level test sets can be applied at speed. Experimental results on many benchmarks show the average area, delay, and power overheads for testability to be 3.1, 1.0, and 4.2%, respectively. Over 99% fault coverage is obtained in most cases with two-four orders of magnitude test generation time advantage over an efficient gate-level sequential test pattern generator and one-three orders of magnitude advantage over an efficient gate-level combinational test pattern generator (that assumes full scan). In addition, the test application times obtained for our method are comparable with those of gate-level sequential test pattern generators, and up to two orders of magnitude smaller than designs using full scan.

Abstract — In this paper, we present design for testability (DFT) and hierarchical test generation techniques for facilitating the testing of application-specific programmable processors (ASPP’s) and application-specific instruction processors (ASIP’s). The method utilizes the register-transfer level (RTL) circuit description of an ASPP or ASIP to come up with a set of test microcode patterns which can be written into the instruction read-only memory (ROM) of the processor. These lines of microcode dictate a new control/data flow in the circuit and can be used to test modules which are not easily testable. The new control/data flow is used to justify precomputed test sets of a module from the system primary inputs to the module inputs and propagate output responses from the module output to the system primary outputs. The testability analysis, which is based on the relevant control/data flow extracted from the RTL circuit,

In a fundamental paradigm shift in system design, entire systems are being built on a single chip, using multiple embedded cores. Though the newest system design methodology has several advantages in terms of time-to-market and system cost, testing such core-based systems is difficult due to the problem of justifying test sequences at the inputs of a core embedded deep in the system, and propagating test responses from the core outputs. In this paper, we present a design for testability and symbolic test generation technique for testing such core-based systems on a chip. The proposed method consists of two parts: (i) core-level DFT to make each core testable and transparent, the latter needed to propagate test data through the cores, and (ii) system-level DFT and test generation to ensure the justification and propagation of the precomputed test sequences and test responses of the core. Since the hierarchical testability analysis technique used to tackle the above problem is symbolic, the system test generation method is independent of the bit-width of the cores. The system-level test set is obtained as a by-product of the testability analysis and insertion method without further search. Besides the proposed test method, the two methods that are currently used in the industry were also evaluated on two example systems: (i) FScan-BScan, where each core is full-scanned, and system test is performed using boundary scan, and (ii) FScan-TBus, where each core is full-scanned, and system test is performed using a test bus. The experiments show that the proposed scheme has significantly lower area overhead, delay overhead, and test application time compared to FScan-BScan and FScan-TBus, without any compromise in the system fault coverage.

In recent years, there has been growing interest in behavioral (high-level) synthesis for testability. This is due to the fact that testability features, such as scan or the built-in self-test, may incur large overheads if introduced during logic synthesis in the later phase of the design cycle. Related previous work attempted to generate system-level test sets using hierarchical testability during behavioral synthesis. There, the test generation scheme is independent of bit width and is, therefore, capable of handling complex controller/data path circuits with large data path bit widths (e.g., 32), which has posed a serious challenge to logic-level sequential test generators. However, this previous work is not applicable when another high-level synthesis system is used. In this paper, we present techniques that add minimal test hardware to a given register-transfer level (RTL) circuit obtained by behavioral synthesis in order to ensure that the embedded elements in the circuit are hierarchically testable. An important byproduct of our design for testability (DFT) procedure is a system-level test set that delivers precomputed test sets to each element in the RTL circuit. This eliminates the need to apply gate-level sequential test generation to the combined controller/data path. We performed extensive experiments with several complex controller/data path circuits synthesized by three different high-level synthesis systems which do not target testability. The key advantages of our method, illustrated by these experiments, include: 1) the area, delay, and power overheads incurred for testability are very low (the average area, delay, and power overheads for a large number of benchmarks are 3.5, 0.5, and 3.4%, respectively), 2) both the DFT hardware addition and test generation algorithms are independent of the data path bit width.

We present a technique for extracting functional (control/dataflow) information from register transfer level (RTL) controller/data path circuits and illustrate its use in design for hierarchical testability of these circuits. This testing procedure and design for testability (DFT) technique is general enough to handle RTL control flow intensive circuits like protocol handlers as well as data flow intensive circuits like digital filters. It makes the combined controller-data path highly testable and does not require any external behavioral information. This scheme has the advantages of low area/delay/power overheads (average of 3.2%, 0.9% and 4.1%, respectively, for benchmarks), high fault coverage (over 99% for most cases), very low test generation times (because it is independent of bit-width), and the advantage of at-speed testing. Experiments show a 2-to-4 (1-to-3) orders of magnitude test generation time advantage over an efficient gate-level sequential test generator (combinational test generator that assumes full scan).

Most behavioral synthesis and design for testability techniques target subsequent gate-level sequential test generation, which is frequently incapable of handling complex controller/data path circuits with large data path bit-widths. Hierarchical testing attempts to counter the complexity of test generation by exploiting information from multiple levels of the design hierarchy. We present techniques that add minimal test hardware to the given register-transfer level (RTL) design obtained through behavioral synthesis in order to ensure that all the embedded modules in the circuit are hierarchically testable. An important by-product of our DFT procedure is a system-level test set that is guaranteed to deliver pre-computed module test sets to each module in the RTL circuit. This eliminates the need to apply gate-level sequential test generation to the controller/data path. We performed extensive experiments with several complex data path/controller circuits synthesized by two different high level synthesis systems which do not target testability.

This paper describes the design and the VLSI implementation of a novel architecture that performs image rotation in real time. In order to improve throughput, we divide an image-frame into a number of windows. The rotation of each window-center as well as the final displacement of individual pixels within a window is then calculated. A CORDIC-based scheme is used to compute the displacement of a pixel. Our architectural design is incorporated into a chip that has been laid out using VTI (VLSI Technology Inc.) tools obeying the 1.5 μm SCMOS design rules. The chip owes its high processing capability to a combination of pipelining and parallel-processing techniques. For a clock frequency greater than 10.6 MHz, we can perform the rotation of a 512×512 gray-level digital image at the rate of 30 frames per second. The chip utilizes around 35,000 transistors and has an estimated silicon area of 211 mils×276 mils.