Multilevel partitioning approaches for circuit partitioning has been shown to be powerful. In this paper we improve the excellent multilevel partitioning algorithm in by taking edge-frequency information into account ...
详细信息
ISBN:
(纸本)9781581130089
Multilevel partitioning approaches for circuit partitioning has been shown to be powerful. In this paper we improve the excellent multilevel partitioning algorithm in by taking edge-frequency information into account during coarsening/uncoarsening, and to break ties. In addition, the uncoarsening phase is guided by an adaptive scheme which adds flexibility to the number of levels in the uncoarsening phase. We apply our algorithm to 13 benchmark circuits and achieve an improvement in min-cut and average min-cut values of up to 8.6% and 34.6% respectively, compared to the method in [2], at no extra runtime. Furthermore, our algorithm provides results of very stable quality. This positions our algorithm as current state of the art in multilevel circuit partitioning.
Combinational verification is an important piece of most equivalence checking tools. In the recent past, many combinational verification algorithms have appeared in the literature. Previous results show that these alg...
详细信息
ISBN:
(纸本)9781581130089
Combinational verification is an important piece of most equivalence checking tools. In the recent past, many combinational verification algorithms have appeared in the literature. Previous results show that these algorithms are able to exploit circuit similarity to successfully verify large designs. However, none of these strategies seems to work when the two input designs are not equivalent. We present our combinational verification algorithm, with evidence, that is designed to be robust for both the positive and the negative problem instances. We also show that a tight integration of different verification techniques, as opposed to a coarse integration of different algorithm, is more effective at solving hard instances.
A floorplanner that can handle convex-rectilinear blocks is developed by enhancing the BSG-based packing algorithm. The ideas are in the introduction of (1) multi-rectangle representation of a block as a superpose of ...
详细信息
A floorplanner that can handle convex-rectilinear blocks is developed by enhancing the BSG-based packing algorithm. The ideas are in the introduction of (1) multi-rectangle representation of a block as a superpose of element-rectangles, (2) parametric-BSG as a generalization of the BSG, (3) multi-BSG which is an arrangement of plural BSG's on a multi-layer, and (4) layer sharing condition of element-rectangles so that non-overlapping is discussed on each layer. A solution space of packings is defined as the set of packings generated by changing parametric-BSG and room assignments. It is guaranteed to contain an optimal packing if the BSG is not smaller than a certain size. A floorplan based on a simulated annealing was implemented. In experiments, it output highly compressed packings.
We discuss the problem of assigning periods in multidimensional periodic scheduling such that storage costs are minimized. This problem originates from the design of high-throughput DSP systems, where highly parallel ...
详细信息
ISBN:
(纸本)9781581130089
We discuss the problem of assigning periods in multidimensional periodic scheduling such that storage costs are minimized. This problem originates from the design of high-throughput DSP systems, where highly parallel execution of loops is of utmost importance, and thus finding an optimal order of the loops is an important task. We formulate the period assignment problem as a linear programming (LP) problem with some additional, non-linear constraints. The non-linear constraints are handled by a branch-and-bound approach, whereas the LP-relaxation is handled by a constraint-generation technique. The effectiveness and efficiency of the approach are good, which is illustrated by means of some practical examples.
Single scan chain architectures suffer from long test application time, while multiple scan chain architectures require large pin overhead and are not supported by Boundary Scan. In this paper, we present a novel meth...
详细信息
ISBN:
(纸本)9781581130089
Single scan chain architectures suffer from long test application time, while multiple scan chain architectures require large pin overhead and are not supported by Boundary Scan. In this paper, we present a novel method to allow a single input line to support multiple scan chains. By appropriately connecting the inputs of all circuits under test during ATPG process such that the generated test patterns can be broadcast to all scan chains when actual testing is executed, we show that 177 and 280 test patterns are enough to detect all detectable faults in all 10 ISCAS'85 combinational circuits and 10 largest ISCAS'89 sequential circuits, respectively.
This paper presents a matrix partitioning scheme for the simulation of coupling capacitances in timing and noise analysis. An error criterion similar to the local truncation error of integration algorithms was develop...
详细信息
ISBN:
(纸本)9781581130089
This paper presents a matrix partitioning scheme for the simulation of coupling capacitances in timing and noise analysis. An error criterion similar to the local truncation error of integration algorithms was developed to control the error due to this matrix partitioning algorithm. The major advantage of the algorithm is that it does not require iterations such as required in relaxation algorithms, and it is designed to work with circuit partitioning for efficient simulation of large circuits in fast circuit/timing simulator like ACES, which forms the basis for an efficient transistor level simulation and analysis. The matrix partitioning algorithm also fits well with controlled explicit integration algorithms. Results demonstrate that the algorithm can ensure simulation accuracy without significantly degrading simulation efficiency for the timing and noise analysis of circuits designed in advanced technologies with small feature sizes.
Accurate simulation of transient device thermal behavior is essential to predict CMOS VLSI circuit failures under electrical overstress (EOS). In this paper, we present an efficient transient electrothermal simulator ...
详细信息
ISBN:
(纸本)9781581130089
Accurate simulation of transient device thermal behavior is essential to predict CMOS VLSI circuit failures under electrical overstress (EOS). In this paper, we present an efficient transient electrothermal simulator that is built upon a SPICE-like engine. The transient device temperature is estimated by the convolution of the device power dissipation and its thermal impulse response which can be derived an analytical solution of the heat diffusion equation. New fast thermal simulation techniques are proposed including a regionwise-exponential (RWE) approximation of thermal impulse response and recursive convolution scheme. The recursive convolution provides a significant performance improvement over the numerical convolution by orders of magnitude, making it computationally feasible to simulate CMOS circuits with many devices.
Increases in delay due to coupling can have a dramatic impact on IC performance for deep submicron technologies. To achieve maximum performance there is a need for analyzing logic stages with large complex coupled int...
详细信息
ISBN:
(纸本)9781581130089
Increases in delay due to coupling can have a dramatic impact on IC performance for deep submicron technologies. To achieve maximum performance there is a need for analyzing logic stages with large complex coupled interconnects. In timing analysis, the worst-case delay of gates along a critical path must include the effect of noise due to switching of nearby aggressor gates. In this paper, we propose a new waveform iteration strategy to compute the delay in the presence of coupling and to align aggressor inputs to determine the worst-case victim delay. We demonstrate the application of our methodology at both the transistor-level and cell-level. In addition, we prove that the waveforms generated in our methodology converge under typical timing analysis conditions.
Due to the exponential growth of both design complexity and the number of gates per pin, functional debugging has emerged as a critical step in the development of a system-on-chip. We introduce a novel debugging appro...
详细信息
ISBN:
(纸本)9781581130089
Due to the exponential growth of both design complexity and the number of gates per pin, functional debugging has emerged as a critical step in the development of a system-on-chip. We introduce a novel debugging approach for programmable systems-on-chip. The new method leverages the advantages of the two complementary functional execution approaches, emulation and simulation. We have developed a set of tools, transparent to both the design and debugging process, which enables the user to run long test sequences in emulation, and upon error detection, roll-back to an arbitrary instance in execution time, and switch over to simulation-based debugging for full design visibility and controllability. The efficacy of the approach is dependent on the method for transferring the computation from one execution domain to another. To enable effective transfer of the computation state, we have identified a set of optimization tasks, established their computation complexity, and developed an efficient suite of optimization algorithms.
Yamashita el. al. introduced a new category for expressing the flexibility that a node can have in a multi-level network. Originally presented in the context of FPGA synthesis, the paper has wider implications which w...
详细信息
ISBN:
(纸本)9781581130089
Yamashita el. al. introduced a new category for expressing the flexibility that a node can have in a multi-level network. Originally presented in the context of FPGA synthesis, the paper has wider implications which were discussed in [12]. SPFDs are essentially a set of incompletely specified functions. The increased flexibility that they offer is obtained by allowing both a node to change as well as its immediate fanins. The challenge with SPFDs is (1) to compute them in an efficient way, and (2) to use their increased flexibility in a controlled way to optimize a circuit. In this paper, we provide a complete implementation of SPFDs using BDDs and apply it to the optimization of Boolean networks. Two scenarios are presented, one which trades literals for wires and the other rewires the network by replacing one fanin at a node by a new fanin. Results on benchmark circuits are very favorable.
暂无评论