Search

In this paper, we propose Lagrangian relaxation (LR)-based algorithms to optimize both circuit performance and total wirelength at the global placement stage. We introduce a general timing-driven global placement problem formulation that is applicable to three different circuit design styles: 1) synchronous circuits; 2) synchronous circuits with sequential optimization techniques; and 3) asynchronous circuits. LR is applied to handle the timing constraints of the formulated problem. Based on how the cell spreading constraints are handled, two different approaches are proposed: one approach handles the spreading constraints inside the LR framework and transforms the timing-driven placement (TDP) problem into a series of weighted wirelength minimization problems, which can be solved by directly leveraging existing wirelength-driven placers. The other approach handles the spreading constraints outside the LR framework. Thus, only timing constraints need to be taken care of in the LR framework and better solutions can be expected. In both approaches, we simplified the LR subproblem using Karush–Kuhn–Tucker conditions. Our algorithms are implemented based on a state-of-the-art wirelength-driven quadratic placer. The experiments demonstrate that the proposed algorithms are able to achieve significant improvements on circuit performance compared with a commercial wirelength-driven placement flow and a commercial asynchronous TDP flow. [ABSTRACT FROM PUBLISHER]

IC3 is one of the most successful algorithms for hardware model checking. Since its invention in 2010, several variants of the original algorithm have been published, proposing optimizations and/or alternative procedures for many different steps of the algorithm. In this paper, we present a thorough empirical comparison of a large set of optimizations and procedures for the steps of IC3, considering “high-level” variants/extensions to the basic algorithm, as well as “low-level” optimizations/configuration settings. We implemented each of them in the same tool, optimizing the implementations to the best of our knowledge. This enabled for a flexible experimentation in a controlled environment, and to gain new insights about their most important differences and commonalities, as well as about their performance characteristics. We conducted the experiments using as benchmarks the problems used in the last four editions of the hardware model checking competition. The analysis helped us to identify several settings leading to significant improvements with respect to a basic implementation of IC3. [ABSTRACT FROM AUTHOR]

Due to the rapidly increasing design complexity in modern integrated circuit design, more and more timing failures are detected at late stages. Without deferring time-to-market, metal-only engineering change order (ECO) is an economical technique to correct these late-found failures. Typically, a design might need to undergo many ECO runs in design houses; consequently, the usage of spare cells for ECO is of significant importance. In this paper, we aim at timing ECO by using as few spare cells as possible. We observe that a path with good timing is desired to be geometrically smooth. Unlike negative slack and gate delay used in most prior work, we propose a new metric of timing criticality, fixability, by considering the smoothness of timing violating paths. To measure the smoothness of a path, we use the Bézier curve as the golden path. Furthermore, in order to concurrently fix timing violations, we derive a propagation property to divide violating paths into independent segments. Based on Bézier curve smoothing, fixability identification, and the propagation property, we develop an efficient algorithm to fix timing violations. Experimental results show that we can effectively resolve all timing violations with significant speedups over the state-of-the-art works. [ABSTRACT FROM AUTHOR]

For modern designs, delay optimization significantly facilitates success in design closure owing to its more realistic metric than wirelength in routing. Obstacle-avoiding rectilinear Steiner tree (OARST) construction is an essential routing problem. With the trends toward Internet protocol-block-based system-on-chip designs, OARST with buffer insertion has been surveyed to diminish the delay of long wires. Previous works on performance-driven (PD) OARST without and with buffer insertion can only handle small circuits. This paper develops a novel routing algorithm in obstacle-avoiding spanning graph to construct OARST with optimized delay efficiently. The proposed multisource single-target maze routing is first employed to identify the critical trunks, and the critical-trunk-based tree growth mechanism connects the unconnected pins to critical trunks under delay constraints of every sink. We apply the proposed critical-trunk-based tree growth mechanism to solve PD and slack-driven (SD) OARST problems. The proposed algorithms are extended to consider buffer insertion during PD and SD OARST constructions. Experimental results demonstrate that the proposed algorithms achieve an average 25.84% improvement in the maximum delay over obstacle-avoiding rectilinear Steiner minimal tree in the PD OARST problem and successfully solve 66.67% worst negative slack violations in the SD OARST problem. Compared to the simultaneous routing and buffer insertion approach, the proposed buffer-aware (BA) algorithm generates satisfactory timing results with almost identical wire length (WL). Moreover, the proposed BA SD OARST algorithm utilizes less WL than the BA rectilinear Steiner tree construction does by 17.99% on average. The runtime comparison with previous works shows the efficiency and scalability of this paper. [ABSTRACT FROM PUBLISHER]

Clock mesh networks are well known for their variation tolerance. But their usage is limited to high-end designs due to the significantly high resource requirements compared to clock trees and the lack of automatic mesh synthesis tools. Most existing works on clock mesh networks either deal with semi-custom design or perform optimizations on a given clock mesh. However, the problem of obtaining a good initial clock mesh has not been addressed. Also, the problem of achieving a smooth tradeoff between variation tolerance and resource requirements has not been addressed adequately. In this paper, we present our MeshWorks framework, the first comprehensive automated framework for planning, synthesis, and optimization of clock mesh networks that addresses the above issues. Experimental results suggest that our algorithms can achieve an additional reduction of 31% in buffer area, 21% in wirelength, and 23% in power, compared to the best previous work, with similar worst case maximum frequency. We also demonstrate the effectiveness of our framework under several practical issues such as blockages, multiple clocks, uneven load distribution, and electromigration violations. [ABSTRACT FROM AUTHOR]

Satisfying a clock skew constraint is one of the most important tasks in clock tree synthesis. Moreover, the task becomes much harder to solve when the clock tree is designed in a multiple power mode environment, in which the voltage applied to some design module varies as the power mode changes. Recently, it has been shown that an adjustable delay buffer (ADB), whose delay can be tuned dynamically, can be used to solve the clock skew problem effectively under multiple power modes. However, due to the area or control overhead by ADBs, it is very important to minimize the number of ADBs to be allocated. This paper provides a complete solution to the problem of clock skew optimization using ADBs under multiple power modes. We propose a linear-time algorithm that simultaneously solves the problems of computing: 1) the minimum (optimal) number of ADBs to be used; 2) the location where each ADB is to be placed; and 3) the delay value of each ADB to be assigned to each power mode. Experimental results show that, in comparison with the previous work, which iteratively performs the ADB allocation, placement, and value assignment, our integrated algorithm produces consistently better designs for all tested benchmarks; it reduces the numbers of ADBs by 9.27% on average under the skew bound of 30–50 ps, even with shorter clock latencies compared to that of previous algorithm of ADB allocation, placement, and delay assignment. To make it practically feasible, we also propose a new ADB design technique and systematic algorithmic solutions to address the problems of discrete delay values, slew rate variation, nonzero initial ADB delay, and a possible exploration of ADB resizing. [ABSTRACT FROM AUTHOR]

This paper presents a new approach for automatic computation of matching constraints for analog sizing. The method automatically analyzes a circuit netlist to generate sizing constraints. These sizing constraints are considered during a subsequent numerical optimization. It is the first method that computes symmetry constraints for sizing, based on the hierarchical structure of the circuit and a qualitative signal flow. As a unique feature, the method is capable of handling multiple signal and feedback paths, leading to multiple symmetry axes. It can be applied to linear and nonlinear circuits and any available sizing algorithm. Experimental results show that the runtime of analog sizing, as well as of result quality, are greatly improved. [ABSTRACT FROM AUTHOR]

We propose a self-contained, flat, quadratic global placer that is simpler than existing placers and easier to integrate into timing-closure flows. It maintains lower-bound and upper-bound placements that converge to a final solution. The upper-bound placement is produced by a novel look-ahead legalization algorithm. Our placer SimPL outperforms mPL6, FastPlace3, NTUPlace3, APlace2, and Capo simultaneously in runtime and solution quality, running 7.10 times faster than mPL6 (when using a single thread) and reducing wirelength by 3% on the ISPD 2005 benchmark suite. More significant improvements are achieved on larger benchmarks. The new algorithm is amenable to parallelism, and we report empirical studies with SSE2 instructions and up to eight parallel threads. [ABSTRACT FROM PUBLISHER]

There is an increasing trend toward application specific processing, particularly in embedded computing devices that have stringent performance requirements. Achieving the desired area and throughput constraints requires careful tuning of the underlying architecture and high-level design tools are gaining increasing acceptance to achieve this goal while decreasing the design time. Most existing tools employ a bottom-to-top methodology, which piece together functional units, interconnect, and control logic based on the given application; this tends to scale poorly. We developed a tool, simulate and eliminate (S&E), that is fundamentally different from the existing high-level design tools as it employs a top-to-bottom methodology. S&E provides automatic generation of a variety of general purpose processing cores with different parameterization options. Then, the provided application(s) are simulated on this general-purpose architecture and the unneeded functionality is eliminated resulting in application specific architecture. S&E generates completely synthesizable hardware description language for an input C and/or MATLAB code. S&E provides different design methods and parameterization options to enable the user to study area and performance tradeoffs over a large number of different architectures and find the optimum architecture for the desired objective. [ABSTRACT FROM PUBLISHER]

We describe BonnPlaceLegal, an algorithm for VLSI placement legalization. Based on a minimum-cost flow algorithm that iteratively augments flows along paths, our approach ensures that only augmentations are considered that can be realized exactly by cell movements. Hence, this method avoids realization problems that are inherent to previous flow-based legalization algorithms. As a result, it combines the global perspective of minimum-cost flow approaches with the efficiency of local search algorithms. The tool is mainly designed to minimize total and maximum cell movement, but it is flexible enough to optimize other objective functions provided that the effect of single cell movements on them can be estimated efficiently. We compare our approach to legalization tools from industry and academia by experiments on dense recent real-world designs and public benchmarks. The results show that we are much faster and produce significantly better results in terms of average (linear and quadratic) and maximum movement than any other tool. The experiments also demonstrate that by minimizing squared movement we also produce a smaller increase in net length than the other tools. [ABSTRACT FROM AUTHOR]

A flow is presented for the automatic synthesis of an analog circuit layout based on a schematic and a list of circuit design parameter values. The flow is driven by design, placement, and routing constraints—no layout template is necessary. Every possible layout for each device in the circuit is investigated; the layouts with the best geometric features and smallest quantization error (due to manufacturing grid alignment) are kept. For circuit placement, a complete enumeration of possible circuit placements, limited only by usual constraints of symmetry, proximity, and common centroid, is performed. Out of this enumeration a final circuit placement is selected and routed. The new flow is integrated with a deterministic nonlinear optimization algorithm to perform layout-driven circuit sizing; layouts are synthesized during both gradient approximation and next step determination. Layout-driven circuit sizing was applied to two example circuits. Sizing of the first circuit example took 8\times the amount of CPU time needed for traditional circuit sizing, but remained feasible at 2.1 h of wall clock time on a contemporary workstation. [ABSTRACT FROM PUBLISHER]