Post-silicon testing and validation -- whether to screen out defective parts, confirm proper operation in the target application, or test robustness in the presence of transient issues induced by environmental factors -- is especially crucial for safety-critical devices. These activities sometimes leverage information gathered prior to fabrication through the injection and testing of stuck-at and transient faults. Traditionally, this process requires a gate-level model in which faulty logic nodes are modeled as 0 and 1 either statically or dynamically. Operating on this unfamiliar gate-level model is a laborious task for engineering teams, requiring a significant investment in time and compute power. This complicates the tasks of better equipping designs for safety-critical needs and augmenting production test quality metrics using well-chosen functional tests. This paper presents research into new techniques for speeding up this process using RTL models and RTL simulation.

In advanced nanometer designs, various electrical effects could introduce unexpected circuit delays and lead to performance failures. Although electrically induced timing errors could be detected by applying delay testing, tools for debugging this type of error are still not widely adopted. We propose a general silicon debug framework which focuses on diagnosing silicon electrical bugs under functional test patterns. In this paper, we present FCR (Failure Candidate Ranker) which is one of the key components of the proposed framework. FCR employs various reasoning techniques including backward active/trigger tracing and forward symptom matching. We'll apply FCR to several industrial cases and show the effectiveness of identifying the error sources.

Several emerging Design-for-Debug (DFD) methodologies are addressing silicon debug by making internal signal values and other data observable. Most of these methodologies require the instrumentation of on-chip logic for extracting the internal register data from in situ silicon. Unfortunately, lack of visibility of the combinational network values impedes the ability to functionally debug the silicon part. Visibility enhancement techniques enable the virtual observation of combinational nodes with minimal computational overhead. These techniques also cover the register selection analysis for DFD and multi-level design abstraction correlation for viewing values at the register transfer level (RTL). Experimental results show that visibility enhancement techniques can leverage a small amount of extracted data to provide a high amount of computed combinational signal data. Visibility enhancement provides the needed connection between data obtained from the DFD logic and HDL simulation-related debug systems.

Conventional register transfer level (RTL) debugging is based on overlaying simulation results on structural connectivity information of the Hardware Description Language (HDL) source. This process is helpful in locating errors but does little to help designers reason about the how and why. Designers usually have to build a mental image of how data is propagated and used over the simulation run. As designs get more and more complex, there is a need to facilitate this reasoning process, and automate the debugging. In this paper, we present innovative debug techniques to address this shortage in adequate facilities for reasoning about behavior, and debugging errors. Our approach delivers significant technology advances in RTL debugging; it is the first comprehensive and methodical approach of its kind that extracts, analyzes, traces, explores, and queries a design's multi-cycle temporal behavior. We show how our automatic tracing scheme can shorten debugging time by orders of magnitude for unfamiliar designs. We also demonstrate how the advanced debug techniques reduce the number of regression iterations.

An interesting property of a latch-based design is that the combinational path delay is allowed to be longer than the clock cycle as long as it can "borrow" time from the shorter paths in the subsequent logic stages. This gives designers a lot of flexibility in designing circuits, especially high performance ones. However, it also increases the complexity in timing analysis. Finding the best clock period or determining how much time to borrow from the subsequent logic stages is difficult especially for designs containing multiple clocks, mixed-clock paths, user-specified multicycle paths, and false paths. In this article, we formulate the time borrowing problem as a linear programming problem. An optimal time borrowing solution can be found by solving the formulation. Based on this time borrowing solver, algorithms are proposed for timing optimization to achieve the optimal clock period. Experimental results show our algorithm is efficient and yields very good results.

Wire delay estimation has been a problem in designs of very deep submicron (VDSM) technologies with feature size under 0.25 /spl mu/m. The conventional back-annotation approach does not guarantee timing convergence due to different estimation techniques for prelayout and post-layout timing. In this paper, a post-routing timing optimization algorithm is presented. Experimental results show that this algorithm provides better result after detail routing is completed.

Previous work has shown that sizable power reductions can be achieved by shutting down a system's sub-circuits when they are not needed. However, these shutdown techniques focus on shutting down only portions of the controller or the datapath of a single custom hardware processor. We propose a higher level shutdown technique that considers both the controller and datapath simultaneously; in particular, we partition a processor into multiple simpler mutually-exclusive communicating processors, and then shut down the inactive processors (i.e., the inactive controller/datapath pairs). Power reduction is accomplished because only one smaller processor is active at a time. In addition to power reduction, functional partitioning also provides solutions to a variety of synthesis problems and does not require the modification of the synthesis tool. We present results showing that this FSMD functional partitioning technique can reduce power, on average, 42% over unoptimized systems.

Article Free Access Share on Post-routing timing optimization with routing characterization Authors: Chieh Changfan Computer Science Dept. University of California, Riverside and Avant! Corporation, 46871 Bayside Parkway, Fremont, CA Computer Science Dept. University of California, Riverside and Avant! Corporation, 46871 Bayside Parkway, Fremont, CAView Profile , Yu-Chin Hsu Avant! Corporation, 46871 Bayside Parkway, Fremont, CA Avant! Corporation, 46871 Bayside Parkway, Fremont, CAView Profile , Fur-Shing Tsai Avant! Corporation, 46871 Bayside Parkway, Fremont, CA Avant! Corporation, 46871 Bayside Parkway, Fremont, CAView Profile Authors Info & Claims ISPD '99: Proceedings of the 1999 international symposium on Physical designApril 1999 Pages 30–35https://doi.org/10.1145/299996.300013Published:12 April 1999Publication History 0citation212DownloadsMetricsTotal Citations0Total Downloads212Last 12 Months19Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In high-level synthesis, resource sharing may result in a circuit containing false loops that create great difficulty in timing validation during the design sign-off phase. It is hence desirable to avoid generating any false loops in a synthesized circuit. Previous work [Stok 1992; Huang et al. 1995] considered mainly data path sharing for false loop elimination. However, for a complete circuit with both data path and control path, false loops can be created due to control logic sharing. In this article, we present a novel approach to detect and eleminate the false loops caused by control logic sharing. An effective filter is devised to reduce the computational complexity of false loop detection, which is based on checking the level numbers that are propagated from data path operators to imputs and outputs of the control path. Only the input/output pairs of the control path identified by the filter are further investigated by traversing into the data path for false loop detection. A removal algorithm is then applied to eliminate the detected false loops, followed by logic minimization to further optimize the circuit. Experimental results show that for the nine example circuits we tested, the final designs after false loop removal and logic minimization give only slightly larger area than the original ones that contain false loops.

Incorporating functional partitioning into a synthesis methodology leads to several important advantages. In functional partitioning, we first partition a functional specification into smaller subspecifications and then synthesize structure for each, in contrast to the current approach of first synthesizing structure for the entire specification and then partitioning that structure. One advantage is the improvement in I/O performance and package count, when partitioning among hardware blocks with size and I/O constraints, such as FPGAs or blocks within an ASIC. A second advantage is reduction in synthesis runtimes. We describe these important advantages, concluding that further research on functional partitioning can lead to inproved results from synthesis environments.

The synthesis of VHDL procedures and functions is studied from the VHDL transformation point of view. Among all the proposed methods, inline expansion and modules can be integrated into a VHDL synthesis system by a source-to-source transformation, while a control-subroutine approach requires additional work at the higher-level synthesis phases before it can be linked to a logic synthesis tool. The possibility of carrying out a lot of optimization is explored during the process. We also present various generations of the control-subroutine approach, including the synthesis of recursive programs, a behavioral partitioning methodology that divides the controller into several communicating state machines, and a methodology that mixes the execution of subprograms. Our study shows that the combination of these approaches is flexible enough to be adapted to various applications in an efficient way.

This paper presents our experience on domain-specific high-level modeling and synthesis for Fujitsu ATM switch design. We propose a high-level design methodology using VHDL, where ATM switch architectural features are considered during behavior modeling, and a high-level synthesis compiler, MEBS, is prototyped to synthesize the behavior model down to a gate-level implementation. Since the specific ATM switch architecture is incorporated into both modeling and syntheses phases, a high-quality design is efficiently derived. The synthesis results show that given the design constraints, the proposed high-level design methodology can produce a gate-level implementation by MEBS with about 15% area reduction in shorter design cycle when compared with manual design.

No abstract available.

Presents a new algorithm for constructing a rectilinear Steiner tree (RST) for a given set of points. Starting from a rectilinear minimum spanning tree (MST), the algorithm works by incrementally introducing "good" Steiner points into the point set and generating an MST from the enlarged point set. Steiner points are introduced in two stages according to their essentiality and cost. In the first stage, they are generated from the local structure of the tree; in the second stage, they are generated from the global structure using a loop detection method. The proposed algorithm outperforms most other algorithms of its class by the fact that the average cost improvement over the rectilinear minimum spanning tree is 10.4%, and its time complexity is O(n/sup 2/ log n).>

In this paper, we present methods for scheduling and partitioning behavioral descriptions (e.g., CDFG's) in order to synthesize application-specific multiprocessor systems. Our target application domain is digital signal processing (DSP). In order to meet the user given constraints (such as timing), maximizing the system throughput and minimizing the amount of communication between processors are important. A model of a target processor and the communication device (i.e., bus, FIFO and delay element) is defined as a basis for the synthesis. We use an integer linear programming formulating to solve the partitioning and scheduling problems simultaneously. The optimization complexity for large applications can be reduced by using a simplified formulation. For even larger applications, we propose an iterative partitioning heuristic to solve. Finally, the formulations are extended to take into account of conditional branches, loops, and critical signals.>

We present a new technique to synthesize high throughput pipelined data paths for those algorithms containing nested loops. Given an initiation interval constraint, the objective is to synthesize a low cost data path for the problem in register transfer level (RTL). Mapping algorithms for processor array synthesis which do not take initiation interval into account cannot be applied to our case; while traditional pipeline synthesis techniques suffer from complex interconnection and high register cost. Our contributions include proposing (1) an approach which conserves the regularities of nested loops, and (2) an architecture which possesses the advantages of both the highly multiplexed and lowly multiplexed architecture styles. Experiments on several algorithms in the image and DSP applications show this approach is very efficient.

A technique for the resource constrained scheduling problem in high level synthesis is presented. The approach works by successively partitioning the control steps into zones and solving each of them by a 0.1 integer linear programming (ILP) technique. By specifying the maximum, number of 0-1 variables involved within a zone, the model can be turned into optimal ILP scheduling, list scheduling, or something in between with different speed/quality characteristics. Experiments show that better results than those achieved by list scheduling have been obtained with an acceptable computation overhead.>

The authors point out that pipelining is an effective method for optimizing the execution of a loop, especially for digital signal processing (DSP) applications where data enter a circuit regularly. Although throughput and turnaround time are two important optimization criteria, previous work emphasized mainly the throughput. It is shown that the delay time for executing an iteration of a loop has a strong relationship to the cost of the registers and the controller. By minimizing the delay, there is more silicon area to allocate to additional resources, which in turn increases throughput. Forward scheduling and a backward scheduling are iteratively used to achieve this purpose. The algorithm, called PipeLining Scheduler or PLS, can be used to pipeline a loop with or without loop-carried dependencies. Real examples are used to illustrate the method. Experiments on benchmark examples show that considerable improvement over previous approaches is attained.>

A layout style that enables either an automatic layout synthesizer or a layout designer to take full advantage of the second metal layer available from today's technology is proposed. The style not only facilitates power/ground diffusion overlapping but also simplifies the intracell routing problem by having power/ground in the middle and routing in the upper and the lower constraint-free regions. An automatic leaf cell layout synthesizer, called THEDA.P, that is based on the proposed style has been implement. Using the same transistor placement algorithm, THEDA.P outperforms a synthesizer based on T. Uehara and W.M. van Cleemput's (1981) approach by almost 20% in layout compactness across a wide range of small-scale integrated circuits. THEDA.P has been used to build a standard cell library that was previously handcrafted. Results from designing two modules show that THEDA.P's layout quality is very competitive.>

The STAR package consists of three phases-preprocessing, data path construction (DPC), and data path refinement (DPR). The data structures are created and the lower limit of each area-dominant resource is determined in the preprocessing phase. In the DPC phase, the allocation is vertically divided into three subtasks: data transfer binding, operation assignment, and variable binding. Data transfers, operations and variables are grouped into clusters of manageable size, and a branch-and-bound search is performed in each cluster for each subtask. In the DPR phase, the data path is refined globally by evaluating the binding quality of each object. The contributions include: (1) a novel technique to evaluate the binding quality of an object on the basis of a sharing of hardware resources in which the object uses; (2) a method to judge the potential for upgrading a data path; and (3) an iterative improvement technique based on the idea of a relation network and state transition.>

We present an algorithm for pipelining loop execution in the presence of loop catried dependence.We optimize both the initiation interval and the turn around time of a schedule.Given constraints on the number of functional units and buses, we tirst determine an initiation interval and then incrementally partition the operations into blocks to fit into the execution windows.A refinement procedure is inwrporated to improve the turn around time.The novel feature which differs our approach from others is that the scheduled operations me iteratively moved up and down to accommodate the ready yet unscheduled opera-tio~.The algorithm produces very encourageous results.

We propose a new layout style that enables an automatic layout synthesizer to take full advantage of the second metal layer available from today's technology.our style not only facilitates power/grotmd-diffttsion overlapping but also sirnplities the intra-cell routing problem.We have implemented an automatic layout synthesizer, called THEDA.P (Tsing Hua Electronic Design Automation), based on the proposed style.Using the same transistor placement algorithm, THEDA.P outperforms a synthesizer based on [Ueh8 1]'s style by almost 20% in layout mmpacmess across a wide range of SS1 circuits.THEDA.P has been used to build a standard cell library that was previously handcrafted.Results from designing two ASIC modules show that THEDA.P's layout quality is very competitive.

The authors present a controller synthesizer for application-specific multi-function-unit processors. They describe the data path, control path, and timing scheme of the design. They discuss the optimization problems for this architecture, including the translation of a controller-independent schedule into a microprogram to fit the timing scheme and the address assignment of micro-words. They verify the designs using a function simulator and a timing simulator. The synthesized results are proved to be correct by simulation, and a design with 22 ns for each phase, which corresponds to 23 MHz, has been obtained.>

The authors present an approach that combines logic minimization and folding for a programmable logic array (PLA). An efficient algorithm is proposed for optimal bipartite column folding. In the algorithm, the authors model the PLA personality matrix as a network and the bipartite PLA folding as a partitioning problem of that network. This folding algorithm is able to find optimal solutions for the benchmarks from the literature. The algorithm also substitutes product terms by their alternatives in order to find the one best suited for folding. The authors combine this algorithm and a logic minimization algorithm into a folding system. When comparing the results to those by a conventional approach, about one half of the benchmarks show area gain if product-term-alternatives exist.>

An automatic layout generation system, called LiB, for the small-scale integrated (SSI) cells used in CMOS VLSI design, is presented. LiB takes a transistor-level circuit schematic in SPICE format and outputs a mask layout in CIF. The layout style is a modification of that proposed by T. Uehara, and W. M. van Cleemput (IEEE Trans. Comput., vol.C-30, no.5, p.305-12, 1981). An optimal transistor chaining algorithm has been developed to derive a transistor placement with a minimum number of diffusion separations. To meet the cell height constraint, large transistors are folded into multiple columns algorithmically. The whole cell is divided into five routing regions. Two are on the diffusion island and the others are rectilinear-shaped routing channels. A graph-theoretic method for selecting nets (subnets) for routing on the diffusion island is proposed. A global routing algorithm has been developed to assign the remaining nets to the three rectilinear channels. For the detailed routing SILK, a simulated evolution router, is employed. LiB can be used as a cell library builder or as a subsystem of a random logic module generator. Users can alternate LiB's layout using a symbolic editor.>

An integer linear programming (ILP) model for the scheduling problem in high-level synthesis is presented. In addition to time-constrained scheduling and resource-constrained scheduling, a scheduling problem called feasible scheduling, which provides a paradigm for exploring the solution space, is constructed. Extensive consideration is given to the following applications: scheduling with chaining, multicycle operations by nonpipelined function units, and multicycle operations by pipelined function units; functional pipelining; loop folding; mutually exclusive operations; scheduling under bus constraint; and minimizing lifetimes of variables. The complexity of the number of variables in the formulation is O(s*n) where s and n are the number of control steps and operations, respectively. Since the as soon as possible (ASAP), as late as possible (ALAP), and list scheduling techniques are used to reduce the solution space, the formulation becomes very efficient. A solution to a practical problem, such as the fifth-order filter, can be found optimally in a few seconds.>

We present an automatic layout generation system, called LiB, for the library cells used in CMOS ASIC design. LiB takes a transistor-level circuit schematic in SPICE format and outputs a symbolic layout. Our layout style is similar to that proposed by Uehara and van Cleemput in [17]. We propose several heuristic algorithms to solve the transistor-clustering, -pairing, -chaining, -folding, the chain placement, the routing, and the net assignment problems, respectively. Experimental results are presented to show the capability of LiB.

We propose a graph-theoretic approach for the data path allocation problem. We decompose the problem into three subproblems: (1) register allocation, (2) operation assignment, and (3) connection allocation. The first two subproblems are modeled as two bipartite weighted matching problems and solved using the Hungarian Method [Pap82]. The third subproblem is solved using a greedy method. While previous researches suffer controversy over which one of subproblems (1) and (2) should be done first, we show that, by taking the other into consideration while performing one, equally satisfactory results can be obtained. We have implemented two programs, LYRA and ARYL, to solve the subproblems in different orders, namely, “(1), (2), then (3)” and “(2), (1), then (3)”, respectively. The matching paradigm allows us to take a more global approach toward the problem than previous researches do. For register allocation, our approach is the first one to guarantee minimal usage of registers while being able to take the interconnection cost into account. For all the benchmarks from the literature, both LYRA and ARYL produced designs as good as, if not better than, those by others in very short time. This research has demonstrated that the bipartite weighted matching algorithm is indeed a very good solution for the data path allocation problem.

This paper presents an integer linear programming model for the scheduling problem in high level synthesis under resource constraints. Extensive consideration is given to the following applications:

A novel algorithm is presented for constructing a rectilinear Steiner tree (RST) of a given set of points. The algorithm works by incrementally introducing Steiner points from a rectilinear minimum spanning tree (MST) and generating a refined Steiner tree. Steiner points are introduced in two stages according to their importance and cost. In the first stage, they are generated from the local structure of the tree; in the second stage, they are generated from the global structure using a loop detection method. The proposed algorithm outperforms most other algorithms; the average cost improvement over the rectilinear minimum spanning tree is 10.6% and its time complexity is O(n/sup 2/ log n).>

A system is described for the data path allocation problem in digital signal processor synthesis. The system, STAR, consists of three phases-preprocessing, data path construction (DPC), and data path refinement (DPR). The actions taken in each phase are described. The authors' contributions include the following: (1) theorems for the lower bound of the number of interconnections; (2) in the DPR phase, a more global view of the allocation problem is taken by ripping up and reallocating different types of objects simultaneously; (3) a novel technique to evaluate the binding quality of an object on the basis of a sharing of hardware resources which the object uses; (4) a method to judge the potential for upgrading a data path; and (5) an iterative improvement technique based on the idea of a relation network. The system currently supports the synthesis of architecture in linear topology and random topology. Parameters can be specified to explore different design alternatives and design space. Experiments on benchmarks show promising results.>

A fast algorithm is proposed for the transistor-chaining problem in CMOS functional cell layout based on the layout style of T. Uehara and W.M. van Cleemput (1981). The algorithm takes a transistor-level circuit schematic and outputs a minimum set of transistor chains. Possible diffusion abutments between the transistor pairs are modeled as a bipartite graph. A depth-first search algorithm is used to search for the optimal chaining. Theorems on the set of branches that needs to be explored at each node of the search tree are derived. A theoretical lower bound on the size of the chain set is also derived. This bound enables one to prune the search tree efficiently. The algorithm has been implemented and tested and is able to find optimal solutions almost instantly for all the cases from the literature that were examined.>

A general-purpose routing algorithm for very-large-scale integrated (VLSI) circuits and printed circuit board (PCB) designs is proposed. Ideas behind the maze-running algorithm and the hierarchical routing algorithm are combined into a powerful algorithm called hybrid routing. The new algorithm demonstrates a speed compatible to a hierarchical router and produces routings with quality equivalent to that obtained by a maze router. Hybrid routing is based on the maze-running method with a third search dimension added. The extra search space is built by recursively constructing a hierarchy of coarser grid meshes. By means of a parameter-controlled expansion into the coarser meshes, the hybrid router is able to find the preferred search region very quickly and will not miss local information as a hierarchical router does. A user-given parameter can turn the algorithm into a pure maze router, a pure hierarchical router, or a wide spectrum of hybrid routers with different speed/quality characteristics between the extremes. The algorithm has been implemented and integrated into a global router that can handle large-scale routing, such as that encountered in the sea-of-gates layout.>

A fast algorithm is produced for the optimal transistor chaining problem in CMOS functional cell layout based on T. Uehara and W.M. van Cleemput's layout style (IEEE Trans. Comput., vol. C-30, p.305-12, May 1981). The algorithm takes a transistor-level circuit schematic and outputs a minimum set of chains. Possible diffusion abutments between the transistor pairs are modeled as a bipartite graph. A depth-first search algorithm is used to search for the optimal chaining. Theorems on the number of branches needed to be explored at each node of the search tree are derived. A theoretical lower bound on the size of the chain set is derived. This bound enables pruning the search tree efficiently. The algorithm has been implemented and tested. It is able to find optimal solutions almost instantly for all the cases available to use from the literature.>

A novel approach is presented to the operation scheduling problem in a data path synthesis. After obtaining the start time and the require time of each operation by the ASAP (as soon as possible) and ALAP (as late as possible) methods, respectively, an integer linear programming (ILP) formulation is formed to solve the scheduling problem. The objective is to fully utilize the hardware resources, i.e. to minimize the requirement of function units under a given timing constraint. The formulation can be generalized to support multicycle operations, multiple operations per cycle, pipelined data paths, mutually exclusive operations, and variables' lifetime consideration in a data path. A fifth-order filter containing 26 addition and 8 multiplication operations can be scheduled optimally for the cases from 17 cycles to 21 cycles per minute on a VAX-11/8800.>

A general-purpose routing algorithm is proposed. Ideas behind both the maze-running algorithm and the hierarchical routing algorithm are combined into a hybrid routing algorithm. The new algorithm demonstrates a speed compatible to a hierarchical router and produces routings with quality equivalent to that by a maze router. Hybrid routing is based on the maze-running method with a third search dimension added. The extra search space is built by recursively constructing a hierarchy of coarser grid meshes. A user-given parameter can turn this algorithm into a pure maze router, a pure hierarchical router, or a wide spectrum of hybrid routers with different speed/quality characteristics between the extremes. With this approach, it is possible to handle easily a routing of large size, such as those encountered in the sea-of-gate layout.>

The authors present a rip-up-and-rerouter based on a matrix representation scheme and simulated evolution technique for solving detailed routing problems in VLSI layout. The status of the routing region is represented as a matrix. Rip-up and reroute operations are emulated as matrix subtractions and additions, respectively. The quality of a routing result can be measured by a few simple matrix operations on the matrix. A rip-up and reroute switch-box/channel router, called SILK, using a simulated evolution technique has been implemented based on this representation alone. Experimental results showed that SILK, when solving all the benchmarks from the literature, outperformed WEAVER, the most successful switch-box router to date, in both quality and speed aspects.>

A representation scheme for a rip-up and rerouter is presented. The status of the routing region is represented as a four-dimensional matrix. Rip-up and re-route operations are emulated as matrix subtractions and additions, respectively. The quality of a routing result can be measured by performing a few simple matrix operations. A rip-up and reroute switch-box/channel router called SILK, using a simulated evolution technique, has been implemented on the basis of this representation scheme. Experimental results showed that SILK outperformed WEAVER, the most successful switch-box router to date, in both quality and speed aspects, for all the classical benchmarks available.>