In this paper, we propose a hybrid floorplanning methodology. Two hierarchical strategies for avoiding local optima during iterative improvement are proposed: (1) Partial Clustering, and (2) Module Restructuring. Thes...
详细信息
ISBN:
(纸本)0818675977
In this paper, we propose a hybrid floorplanning methodology. Two hierarchical strategies for avoiding local optima during iterative improvement are proposed: (1) Partial Clustering, and (2) Module Restructuring. These strategies work for localizing nets connecting small modules in small regions, and conceal such small modules and their nets during the iterative improvement phase. This method is successful in reducing both area and wire length in addition to reducing the computational time required for optimization. Although our method only searches slicing floorplans, the results are superior to the results obtained even with non-slicing floorplans. We applied our method to the largest MCNC floorplan benchmark example, ami49, and industrial data. For the ami49 benchmark, we obtained results superior to any published results for both estimated area and routing results.
This paper presents a new method for covering a Boolean network by library cells. In this method, matches are classified according to their properties. Some matches are selected unconditionally into a cover and the re...
详细信息
This paper presents a new method for covering a Boolean network by library cells. In this method, matches are classified according to their properties. Some matches are selected unconditionally into a cover and the remaining nodes are divided into independent portions. Then, a match compatibility graph (MCG) is constructed for each portion and an optimum cover is found for it using the MCG. Thus, our method finds an efficient and closer to optimum cover for the complete network.
The proceedings contains 101 papers from the 1996 internationalconference on computeraided Design. Topics discussed include: technology mapping;interconnect characterization and analysis;high performance routing syn...
详细信息
The proceedings contains 101 papers from the 1996 internationalconference on computeraided Design. Topics discussed include: technology mapping;interconnect characterization and analysis;high performance routing synthesis;sequential circuit testing;formal verification;system design synthesis and compilation;timing analysis;high level design;power and performance in high level synthesis;high performance circuit optimization;circuit partitioning;automatic test pattern generation (ATPG);embedded applications;implication-based logic synthesis;advance numerical simulation techniques;robust routing;yield and technology modeling;power and timing analysis;verification and fault tolerance;and analog CAD and methodology.
The Inversion Algorithm is an event driven algorithm whose performance meets or exceeds that of Levelized Compiled Code simulation, even when the activity rate is unrealistically high. Existing implementations of the ...
详细信息
The Inversion Algorithm is an event driven algorithm whose performance meets or exceeds that of Levelized Compiled Code simulation, even when the activity rate is unrealistically high. Existing implementations of the Inversion Algorithm are based on the Zero Delay model. This paper extends the algorithm to more realistic timing models. The main problems discussed in this paper are avoiding scheduling conflicts, and minimizing the amount of storage space. These problems are made considerably more difficult by the deletion of NOT gates and the collapsing of various connections. These optimizations transform the simulation into a multi-delay simulation under the transport delay model. A complete solution to the scheduling problem is presented under these conditions.
In interactive behavioral synthesis, the designer can control the design process at every stage, including modifying the schedule of the design to improve its performance. In this paper, we present a methodology for p...
详细信息
In interactive behavioral synthesis, the designer can control the design process at every stage, including modifying the schedule of the design to improve its performance. In this paper, we present a methodology for performance optimization in interactive behavioral synthesis. Also proposed are several quality metrics and hints that can assist the user in utilizing the proposed methodology. When the user is optimizing the performance of the design, one important decision is the selection of a clock period. To facilitate clock selection by the user, we have developed an algorithm to estimate the effect of different clock periods on the execution time of the design. We have tested our methodology on several benchmarks. The experimental results support the proposed methodology by demonstrating an average improvement of 46.2% in design performance.
Domino logic is one of the most popular dynamic circuit configurations for implementing high-performance logic designs. Since domino logic is inherently non-inverting, it presents a fundamental constraint of implement...
详细信息
Domino logic is one of the most popular dynamic circuit configurations for implementing high-performance logic designs. Since domino logic is inherently non-inverting, it presents a fundamental constraint of implementing logic functions without any intermediate inversions. Removal of intermediate inverters requires logic duplication for generating both the negative and positive signal phases, which results in significant area overhead. This area overhead can be substantially reduced by selecting an optimal output phase assignment, which results in a minimum logic duplication penalty for obtaining inverter-free logic. In this paper, we present this previously unaddressed problem of output phase assignment for minimum area duplication in dynamic logic synthesis. We give both optimal and heuristic algorithms for minimizing logic duplication.
This paper introduces GRASP (Generic seaRch Algorithm for the Satisfiability Problem), an integrated algorithmic framework for SAT that unifies several previously proposed search-pruning techniques and facilitates ide...
详细信息
This paper introduces GRASP (Generic seaRch Algorithm for the Satisfiability Problem), an integrated algorithmic framework for SAT that unifies several previously proposed search-pruning techniques and facilitates identification of additional ones. GRASP is premised on the inevitability of conflicts during search and its most distinguishing feature is the augmentation of basic backtracking search with a powerful conflict analysis procedure. Analyzing conflicts to determine their causes enables GRASP to backtrack non-chronologically to earlier levels in the search tree, potentially pruning large portions of the search space. In addition, by `recording' the causes of conflicts, GRASP can recognize and preempt the occurrence of similar conflicts later on in the search. Finally, straightforward bookkeeping of the causality chains leading up to conflicts allows GRASP to identify assignments that are necessary for a solution to be found. Experimental results obtained from a large number of benchmarks, including many from the field of test pattern generation, indicate that application of the proposed conflict analysis techniques to SAT algorithms can be extremely effective for a large number of representative classes of SAT instances.
Functional simulation is the most widely used method for design verification. At various levels of abstraction, e.g., behavioral, register-transfer level and gate level, the designer simulates the design using a large...
详细信息
Functional simulation is the most widely used method for design verification. At various levels of abstraction, e.g., behavioral, register-transfer level and gate level, the designer simulates the design using a large number of vectors attempting to debug and verify the design. A major problem with functional simulation is the lack of good metrics and tools to evaluate the quality of a set of functional vectors. Metrics used currently are based on instruction counts and are quite simplistic. Designers are forced to use ad-hoc methods to terminate functional simulation, e.g., CPU time limitations. We propose a new metric for measuring the extent of design verification provided by a set of functional simulation vectors. This metric is universal, and can be used uniformly for all designs. Our metric computes observability information to determine whether effects of errors that are activated by the program stimuli can be observed at the circuit outputs. We provide preliminary experimental evidence that supports the validity of the proposed metric. We believe that using this metric in design verification will result in higher-quality functional tests and improved correctness checking.
This paper presents a new framework for formal logic verification. What is depicted here is fundamentally different from previous approaches. In earlier approaches, the circuit is either not changed during the verific...
详细信息
This paper presents a new framework for formal logic verification. What is depicted here is fundamentally different from previous approaches. In earlier approaches, the circuit is either not changed during the verification process, as in OBDD or implication-based methods, or the circuit is progressively reduced during verification. Whereas in our approach, we actually enlarge the circuits by adding gates during the verification process. Specifically introduced here is a new technique that transforms the reference circuit as well as the circuit to be verified, so that the similarity between the two is progressively enhanced. This requires addition of gates to the reference circuit and/or the circuit to be verified. In the process, we reduce the dissimilarity between the two circuits, which makes it easier to verify the circuits. In this paper, we first introduce a method to identify parts of the two circuits which are dissimilar. We use the number of implications that exist between the nodes of one circuit and the nodes of the other circuit as a metric of similarity. As demonstrated, this can be a very useful metric. We formulate transformations that can reduce the dissimilarity. These are performed on those parts of the circuits which are found to be dissimilar. These admissible transformations are functionality-preserving and based on certain Boolean difference formulations. The dissimilarity reduction transformations introduce new logical relationships between the two circuits that did not previously exist. These logical relationships are extracted as new implications, which are then used to reduce the complexity of the verification problem. These two steps are repeated in succession until the verification process is complete. A complete procedure is presented which demonstrates the power of our logic verification technique. The concept presented in this paper can be useful in accelerating verification frameworks which rely on structural methods.
This tutorial surveys the present and future of multimedia computing systems and outlines new challenges for CAD presented by these systems. Multimedia computing is a challenging domain for several reasons: it require...
详细信息
ISBN:
(纸本)0818672137
This tutorial surveys the present and future of multimedia computing systems and outlines new challenges for CAD presented by these systems. Multimedia computing is a challenging domain for several reasons: it requires both high computation rates and memory bandwidth;it is a multirate computing problem;and requires low-cost implementations for high-volume markets. As a result, the design of multimedia computing systems introduces new challenges for CAD at all levels of abstraction, ranging from layout to system design. After surveying the nature of the multimedia computing problem, we examine two experiences in multimedia computer design from a CAD perspective: the design of VLSI systems-on-chips for multimedia;and the successive refinement of an application from software to a high-volume chip using advanced CAD synthesis tools.
暂无评论