In this paper, we propose an algorithm to quickly find the maximum cycle ratio (MCR) on an incrementally changing directed cyclic graph. Compared with traditional MCR algorithms which have to recalculate everything from scratch at each incremental change, our algorithm efficiently finds the MCR by just leveraging the previous MCR and the corresponding largest cycle before the change. In particular, the previous MCR allows us to safely break the graph at the changed node. Then, we can detect the changing direction of the MCR by solving a single source longest path problem on a graph without positive cycle. A distance bucket approach is proposed to speed up the process of finding the longest paths. Our algorithm continues to search upward or downward based on whether the MCR is detected as increased or decreased. The downward search is quickly performed by a modified Karp-Orlin algorithm reusing the longest paths found during the cycle detection. In addition, a cost shifting idea is proposed to avoid calculating MCR on certain type of incremental changes. We evaluated our algorithm on both random graphs and circuit benchmarks. A timing-driven detailed placement approach which applies our algorithm is also proposed. Compared with Howard's and Karp-Orlin MCR algorithm, our algorithm shows much more efficiency on finding the MCR in both random graphs and circuit benchmarks.

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.

This paper presents a novel flip-flop clustering and relocation framework to help reduce the overall chip power consumption. Given an initial legalized placement, our goal is to reduce the wirelength of the clock network by reducing distance between flip-flops and their drivers, while minimize the disturbance of original placement result. The idea is to form flip-flops into clusters, such that all flip-flops within each cluster can be placed near a single clock buffer and connected by a simple routing structure. Therefore, overall clock network wirelength can be greatly reduced and significant power savings can be achieved. In particular, we propose a modified K-means algorithm which effectively assigns flops into clusters at the clustering step. Then, at the relocation step, flops are actually relocated and regularly structured clusters are formed. Our framework is evaluated on real industrial benchmarks. We compare our framework with a flow without flop clustering and an industrial window based flop clustering flow. Experimental results show our framework can achieve significant dynamic power savings while has less disturbance of the original placement.

Conventional detailed placement algorithms typically assume all standard cells in the design have the same height. However, as the complexity and design requirement increase in modern very large-scale integration design, designs with mixed single-row height and double-row height standard cells come into existence in order to address the emerging standard cell design challenges. A detailed placement algorithm without considering these double-row height cells will either have to deal with a lot of movable macros or waste a significant amount of placement area, depending on what type of techniques people use to accommodate such design. This paper proposes a new placement approach which can handle designs with any number of double-row height standard cells. We transform design with mixed-height standard cells into one which only contains same height standard cells by pairing up single-row height cells into double-row height. Then conventional detailed placement algorithms can be applied. In particular, we generate cell pair candidates by formulating a maximum weighted matching problem. A subset of the cell pair candidates are then carefully selected to form double-row height cells based on the local bin density. A refinement procedure is performed at the end to further improve our placement quality. We compare our approach with two alternative detailed placement methods on mixed-height asynchronous and synchronous designs. The experimental results show that our approach can achieve much better quality and robustness.

Placement is one of the most important problems in electronic design automation. Although it has been investigated for several decades, a more efficient core engine is critically needed for the following reasons: (1) design scale becomes huge; (2) placement is typically run again and again to explore the design space at early design stages (e.g., physical synthesis); (3) placement core engine is called many times to iteratively optimize other objectives (e.g., timing and routability). In this paper, we propose a new ultrafast global placement engine called POLAR 3.0, which explores parallelism in state-of-the-art quadratic placer. POLAR 3.0 can make full use of multi-core system and it delivers 7-30× speedup over state-of-the-art academic placers by using a 8-core CPU, while the solution quality is competitive.

Recent asynchronous VLSI circuit placement approach tries to leverage synchronous placement tools as much as possible by manual loop-breaking and creation of virtual clocks. However, this approach produces an exponential number of explicit timing constraints which is beyond the ability of synchronous placement tools to handle. Thus, synchronous placer can only produce suboptimal results. Also, it can be very costly in terms of runtime. This paper proposed a new placement approach for asynchronous VLSI circuits. We formulated the asynchronous timing-driven placement problem and transform this problem into a weighted wirelength minimization problem based on a Lagrangian relaxation framework. The problem can then be efficiently solved using any standard wirelength-driven placement engine that can handle net weights. We demonstrate our approach on QDI PCHB asynchronous circuit with a state-of-art quadratic placer. The experimental results show that our algorithm can effectively improve the asynchronous circuits performance at placement stage. In addition, the runtime of our algorithm is shown to be more scalable to large-scale circuits compared with the loop-breaking approach.