Sub-7nm technology nodes have introduced new challenges, specifically in the lower metal layers. Extreme Ultraviolet Lithography (EUV) and multi-patterning-based lithography such as Self-Aligned Double Patterning (SADP) solutions have become key choices for the manufacturing of these layers. The demand for microprocessors has increased tremendously in the last few years and this imposes another challenge to the chip manufacturers to build their products at a very rapid rate. These days a mix of different lithography solutions for the manufacturing of metal layers is quite common. We propose a first-of-its-kind routing plugin which solves design rule violations for multiple lithography technologies without making any changes in the existing routers. Our plugin consists of a practical line-end optimization (LEO) algorithm, which solves most line-end problems in a few minutes, even for very large designs. Our solution is implemented in the development of a 7nm, industrial microprocessor design.

Latch clustering is a critical stage to reduce power consumption at cost of timing disruption during a modern SoC design flow. However, most existing latch clustering researches mitigate timing disruptions by indirectly minimizing latch displacement during clustering, which is inaccurate and insufficient for timing closure in the design flow. Further, most researches do not control the amount of inserted clock buffers during clustering, which is the key factor to provide flexibility for timing and power trade-off. To address the two issues above, this paper presents a novel timing-power co-optimized latch clustering framework: we augment an integer linear programming (ILP) formulation of a facility-location allocation (FLA) problem to (1) directly optimize timing with a path-based timing model and (2) accurately control the number of inserted buffers by the FLA formulation for power optimization. We evaluate the framework with a displacement-optimized clustering approach and a state-of-the-art approach. Experimental results show 46% total negative slack timing overhead reduction, and 21% reduction for total power consumption.

Double patterning is a widely used technique for sub-22nm. Among various double patterning techniques, Self-Aligned Double Patterning (SADP) is a promising technique for good mask overlay control. Based on SADP, a new set of standard cells (T-cells) are developed using thicker metal wires for stronger drive strength. By applying this kind of gates on critical paths, it helps to improve the design performance. However, a mixed design with T-cells and normal cells (N-cells) requires that T-cells are placed on circuit rows with thicker metal, and the normal cells are on the normal circuit rows. Therefore, a placer is needed to adjust the cells to the matched circuit rows. In this paper, a two-stage min-cost max-flow based legalization flow is presented to adjust N/T gate locations for a legal placement. The experimental results demonstrate the effectiveness and efficiency of our approach.

Interconnect optimization, including buffer insertion and Steiner tree construction, continues to be a pillar technology that largely determines overall chip performance. Buffer insertion algorithms in published literature are mostly focused on optimizing only the most critical path. This is a sensible approach for the first order effect. As people strive to squeeze out more performance in the post Moore's law era, the timing of near critical paths is worth considering as well. In this work, a p-norm based Figure Of Merit (pFOM) is proposed to account for both the critical and near critical path timing. Accordingly, a pFOM-driven buffer insertion method is developed. Further, the interaction with timing driven Steiner tree is investigated. The proposed techniques are validated in an industrial design flow and the results confirm their advantages.

The continued delay of higher resolution alternatives for lithography, such as EUV, is forcing the continued adoption of multi-patterning solutions in new technology nodes, which include triple and quadruple patterning using several lithography-etch steps. In the design space each pattern of a multi-patterning solution is modeled as a color on a shape. Designers or EDA tools must determine the colors that each shape is assigned so that the relative position of any two shapes of the same color does not violate the design rules. This results in a shapes layout coloring problem which is formulated as the traditional k-coloring problem in a graph. Because color interactions cross cell boundaries, coloring of a flat (as opposed to hierarchical) design becomes necessary, tremendously increasing the size of the input graph. If a color conflict occurs, any attempt to fix it may cause a chain reaction propagating through the whole design space which makes any approach of the type color_greedily - fix_conflicts - loop_back infeasible. Given the situation, it is extremely desirable to have a set of design rules which provably guarantee k-colorability and admit a practical coloring algorithm. In this paper we formulate such sets of design rules for triple and quadruple patterning problems. For these sets of rules we provide proofs of colorability along with the coloring algorithms with the runtime upper bound of O(n·log n). We also show that our sets of design rules are almost tight in the sense that even a very small relaxation of the formulated rules leads to existence of not k-colorable designs.

We present algorithms for routing in advanced technology nodes, used by BonnRoute (BR) to obtain efficient and almost design rule clean wire packings and pin access solutions. Designs with dense standard cell libraries in presence of complex industrial design rules, with a special focus on multiple patterning lithography are considered. The key components of this approach are a multilabel interval-based shortest path algorithm for long on-track connections, and a dynamic program for computing packings of pin access paths and short connections between closely spaced pins. The multilabel path search implementation is very general and is driven with different labeling rules, allowing to trade-off runtime against accuracy in terms of obeyed design rules. We combine BR with an industrial router for cleaning up the remaining design rule violations, and demonstrate superior results over that industrial router in our experiments in terms of wire length, number of vias, design rule violations, and runtime.

Routing congestion has become a critical layout challenge in nanoscale circuits since it is a critical factor in determining the routability of a design. An unroutable design is not useful even though it closes on all other design metrics. Fast design closure can only be achieved by accurately evaluating whether a design is routable or not early in the design cycle. Lately, it has become common to use a “light mode” version of a global router to quickly evaluate the routability of a given placement. This approach suffers from three weaknesses: (i) it does not adequately model local routing resources, which can cause incorrect routability predictions that are only detected late, during detailed routing; (ii) the congestion maps obtained by it tend to have isolated hotspots surrounded by noncongested spots, called “noisy hotspots”, which further affects the accuracy in routability evaluation; and (iii) the metrics used to represent congestion may yield numbers that do not provide sufficient intuition to the designer, and moreover, they may often fail to predict the routability accurately. This article presents solutions to these issues. First, we propose three approaches to model local routing resources. Second, we propose a smoothing technique to reduce the number of noisy hotspots and obtain a more accurate routability evaluation result. Finally, we develop a new metric which represents congestion maps with higher fidelity. We apply the proposed techniques to several industrial circuits and demonstrate that one can better predict and evaluate design routability and that congestion mitigation tools can perform much better to improve the design routability.

Industry routers are very complex and time consuming, and are becoming more so with the explosion in design rules and design for manufacturability requirements that multiply with each technology node. Global routing is just the first phase of a router and serves the dual purpose of (i) seeding the following phases of a router and (ii) evaluating whether the current design point is routable. Lately, it has become common to use a "light mode" version of the global router, similar to today's academic routers, to quickly evaluate the routability of a given placement. This use model suffers from two primary weaknesses: (i) it does not adequately model the local routing resources, while the model is important to remove opens and shorts and eliminate DRC violations, (ii) the metrics used to represent congestion are non-intuitive and often fail to pinpoint the key issues that need to be addressed. This paper presents solutions to both issues, and empirically demonstrates that incorporating the proposed solutions within a global routing based congestion analyzer yields a more accurate view of design routability.

Traditionally, the goal of physical synthesis has been to produce a physical realization of the input netlist that meets its timing constraints with minimum area. However, design routability has emerged from a secondary objective to perhaps the primary objective, in no small part due to the myriad of rules and constraints that emerge with each successive technology. This work overviews the complexities with modeling congestion during physical synthesis and discusses how optimizations may be able to provide some relief.

In this paper, we investigate reducing the power consumption of a synchronous digital system by minimizing the total power consumed by the clock signals. We construct activity-driven clock trees wherein sections of the clock tree are turned off by gating the clock signals. Since gating the clock signal implies that additional control signals and gates are needed, there exists a tradeoff between the amount of clock tree gating and the total power consumption of the clock tree. We exploit similarities in the switching activity of the clocked modules to reduce the number of clock gates. Assuming a given switching activity of the modules, we propose three novel activity-driven problems: a clock tree construction problem, a clock gate insertion problem, and a zero-skew clock gate insertion problem. The objective of these problems is to minimize the system's power consumption by constructing an activity-driven clock tree. We propose an approximation algorithm based on recursive matching to solve the clock tree construction problem. We also propose an exact algorithm employing the dynamic programming paradigm to solve the gate insertion problems. Finally, we present experimental results that verify the effectiveness of our approach. This paper is a step in understanding how high-level decisions (e.g., behavioral design) can affect a low-level design (e.g., clock design).

Throughout its history, from the early four-circuit gate-array chips of the late 1960s to today's billion-transistor multichip module, IBM has invested in tools to support its leading-edge technology and high-performance product development. The combination of demanding designs and close cooperation among product, technology, and tool development has given rise to many innovations in the electronic design automation (EDA) area and provided IBM with a significant competitive advantage. This paper highlights IBM's contributions over the last four decades and presents a view of the future, where the best methods of multimillion gate ASIC and gigahertz microprocessor design are converged to enable highly productive system-on-a-chip designs that include widely diverse hardware and software components.

In this paper we present a novel formulation for the net-based timing-driven placement problem. The new formulation performs budgeting #net delay upper bounds# and placement modi#cation simultaneously thus alleviates the problem of going back-and-forth between budgeting and placement. An algorithm to accomplished the proposed task is presented. The proposed algorithm uses a simulated annealing approach and a modi#ed graph-based simplex method. A general formulation of timing-sriven placement is presented. It is proved that both net-based and path-based approaches to timing-driven placement are special cases of a more general formulation. The proposed algorithm has been incorporated into a #timing-driven# placement package. Experiments on MCNC benchmarks show strong results. The proposed algorithm o#ers 54# to 68# reduction over the longest path compared with the existing algorithms. 1. INTRODUCTION Timing-driven placement is a problem that is becoming increasingly important in VLSI d...

Article A VLSI artwork legalization technique based on a new criterion of minimum layout perturbation Share on Authors: Fook-Luen Heng IBM Corporation, 32-138, T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY IBM Corporation, 32-138, T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NYView Profile , Zhan Chen Dept. of ECE, Univ. of Massachusetts, Amherst, MA Dept. of ECE, Univ. of Massachusetts, Amherst, MAView Profile , Gustavo E. Tellez IBM Corporation, 32-138, T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY IBM Corporation, 32-138, T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NYView Profile Authors Info & Claims ISPD '97: Proceedings of the 1997 international symposium on Physical designApril 1997 Pages 116–121https://doi.org/10.1145/267665.267701Published:01 April 1997 30citation407DownloadsMetricsTotal Citations30Total Downloads407Last 12 Months8Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In this paper, we present a new, general approach to the problem of computing upper bounds on net delays. The upper bounds on net delays are computed so that timing constraints between input and output signals are satisfied. The set of delay upper bounds is called a delay budget. The objective of this work is to compute a delay budget that will lead to timing feasible circuit placement and routing. In our formulation, we find a delay budget so that the placement phase has "maximum flexibility." We formulate this problem as a convex programming problem and prove that it has a special structure. We utilize the special structure of the problem to propose an efficient graph-based algorithm. We present experimental results for our algorithms with the MCNC placement benchmarks. Our experiments use budgeting results as net length constraints for the TimberWolf placement program, which we use to evaluate the budgeting algorithms. We obtain an average of 50% reduction in net length constraint violations over the well-known zero-slack algorithm (ZSA). We also study different delay budgeting objective functions, which yield 2/spl times/ performance improvements without loss of solution quality. Our results and graph-based formulation show that our proposed algorithm is suitable for modern large-scale budgeting problems.

In this paper, we investigate the problem of computing a lower bound on the number of buffers required when given a maximum clock slew rate (or rise time) constraint and a predefined clock tree. Using generalized properties of published CMOS timing models, we formulate a novel nonlinear buffer insertion problem. Next, we derive an algorithm that bounds the capacitance for each buffer stage without sacrificing the generality of the timing models. With this capacitance bound we formulate a second linear buffer insertion problem, which we solve optimally in O(n) time. The basic formulation and algorithm are extended to include a skew upper bound constraint. Using these algorithms we propose further algorithmic extensions that allow area and phase delay tradeoffs. Our results are verified using SPICE3e2 simulations with MCNC MOSIS 2.0 /spl mu/ models and parameters. Experiments with these test cases show that the buffer insertion algorithms proposed herein can be used effectively for designs with high clock speeds and small skews.

Sleep mode operation and exploiting it to minimize the average power consumption are o f g r e at importance.In this paper, we formulate the memory segmentation/partitioning problem to exploit sleep mode operation and show that the problem is NP-complete.We present polynomial time algorithms for special classes of the problem.Some generalizations of the problem are discussed.Preliminary experiments are c onducted to show the eectiveness of the algorithms and applicability of the approach.The experimental data con rm that a careful partitioning allows up to 40% more sleep time which could be exploited to minimize the average power consumption.Directions for further research in this area a r e presented.

In this paper we investigate activity-driven clock trees to reduce the dynamic power consumption of synchronous digital CMOS circuits. Sections of an activity-driven clock tree can be turned on/off by gating the clock signals during the active/idle times of the clocked elements. We propose a method of obtaining the switching activity patterns of the clocked circuits during the high level design process. We formulate three novel activity-driven problems. The objective of these problems is to minimize system's dynamic power consumption. We propose an approximation algorithm based on recursive matching to solve the clock tree construction problem. We solve the gate insertion problems with an exact algorithm employing the dynamic programming paradigm. Finally, we present experimental results that verify the effectiveness of our approach. Our work in this paper is a step in understanding how high level decisions (e.g. behavioral design) can affect a low level design (e.g. clock design).

Given a set of terminals on the plane N=(s,/spl nu//sub 1/,...,/spl nu//sub n/,), with a sink terminal s, a Rectilinear Distance-Preserving Tree (RDPT) T(V, E) is defined as a tree rooted at s, connecting all terminals in N. The rectilinear distance between source and sinks in an RDPT is equal to the length that source to sink path. A Min-Cost Rectilinear Distance Preserving Tree (MRDPT) is an RDPT T* such that all other RDPTs T' connecting s and N have C(T*)/spl les/C(T'), where C(T) denotes the total length of tree T. MRDPTs minimize the total wire length while maintaining minimal source to sink linear delay, making them suitable for high performance interconnect applications. In this paper we investigate exact algorithms for restricted versions of the problem. These algorithms have O(n/sup 2/) time complexity. We propose a heuristic algorithm for the general problem where we partition the points into sets of points that we can solve optimally. The results of our algorithms are tested on random point sets and compared our results are compared with Minimum Cost Steiner tree approximations, showing total wire-length comparisons. The results of these comparisons show that the algorithms proposed herein produce promising results.