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]

Threshold voltage assignment is a very effective technique to reduce leakage power consumption in modern integrated circuit design. As feature size continues to decrease, the layout constraints [called minimum implant area (MinIA) constraints] on the implant area, which determines the threshold voltage of a device, are becoming increasingly difficult to satisfy. It is necessary to take these constraints into consideration during the placement stage. In this paper, we propose to resolve the MinIA constraint violations of a given placement by performing simultaneous detailed placement and threshold voltage refinement. We first present an optimal and efficient mixed integer-linear programming (MILP)-based algorithm to handle intrarow MinIA constraints. We then extend the MILP-based algorithm to handle both inter-row and intrarow MinIA constraints. Both of our algorithms guarantee to fix all MinIA constraint violations. Experimental results demonstrate that our algorithms only perturb the original placement and threshold voltage assignment solutions minimally to eliminate all violations and are fast in practice. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM PUBLISHER]

Electron-beam (e-beam) lithography has long been employed for mask writing but the write time is increasing due to the escalating mask pattern complexity. Besides, e-beam direct write is being pursued as an alternative solution for chip production in the sub-22 nm regime. To improve the throughput of e-beam lithography, character projection method is commonly employed and a critical problem is to pack as many useful characters as possible onto the stencil. In this paper, we consider three enhancements in packed stencil design over previous works. First, the fact that the pattern of a character can be located anywhere within its enclosing projection region is exploited to facilitate flexible blank space sharing. Second, the use of multiple shaping apertures with different sizes is explored. Third, the use of overlapping shots for printing some characters is investigated. For the packed stencil design problem with flexible blank space sharing and multiple shaping apertures, two dynamic programming-based algorithms are proposed, one allows overlapping shots and the other does not. Experimental results show that the proposed enhancement and the associated algorithms can significantly reduce the total shot count and hence improve the throughput of e-beam lithography. [ABSTRACT FROM PUBLISHER]

This paper presents an efficient, scalable, and optimal slack-driven shaping algorithm for soft blocks in nonslicing floorplan. The proposed algorithm is called SDS. SDS is specifically formulated for fixed-outline floorplanning. Given a fixed upper bound on the layout width, SDS minimizes the layout height by only shaping the soft blocks in the design. Iteratively, SDS shapes some soft blocks to minimize the layout height with the guarantee that the layout width would not exceed the given upper bound. Rather than using some simple heuristic as in previous work, the amount of change on each block is determined by systematically distributing the global total amount of available slack to individual block. During the whole shaping process, the layout height monotonically reduces and eventually converges to an optimal solution. Two optimality conditions are presented to check the optimality of a shaping solution for fixed-outline floorplanning. In practice, to terminate the process of convergence early, we propose two different stopping criteria. We also extend SDS to handle other floorplanning problems, e.g., classical floorplanning. To validate the efficiency and effectiveness of SDS, comprehensive experiments are conducted on MCNC and HB benchmarks. Compared with previous work, SDS achieves the best experimental result with a significantly faster runtime. [ABSTRACT FROM AUTHOR]

Wire bonding is currently the most popular method for connecting signals between dies in system-in-package (SiP) design. Pad assignment, which assigns inter-die signals to die pads so as to facilitate wire bonding, is an important physical design problem for SiP design because the quality of a pad assignment solution affects both the cost and the performance of an SiP design. In this paper, we study a pad assignment problem, which prohibits the generation of illegal crossings and aims to minimize the total signal wirelength, for die-stacking SiP design. We first consider the two-die cases and die-stacks with a bridging die, and present a minimum-cost flow-based approach to optimally solve them in polynomial time. We then describe an approach, which uses a modified left-edge algorithm and an integer linear programming technique, for pyramid die-stacks with no bridging die. Finally, we discuss extensions of the two approaches to handle additional design constraints. Encouraging experimental results are shown to support our approaches. [ABSTRACT FROM AUTHOR]