As processor technology continues to evolve into the deepnanometer era, full-custom analog/mixed-signal (AMS) integrated circuits (ICs) must be designed using fin-shaped fieldeffect transistors (FinFETs) to meet performance requirements. While these transistors enjoy reduced leakage currents and superior control of the electric-field within the device channel, the three-dimensional fin-shape structure imposes even more challenges to the already intricate AMS layout process.
Restricted by manufacturability issues, circuit layout in advanced FinFET nodes (e.g., N7, N5) enforce a row-based placement style for fin alignment [1]. As a result, AMS layout implementations rely heavily on layout primitives, the basic building block of an AMS circuit formed by a group of low-level devices (e.g., transistors, resistors) [2]. The use of primitive cells brings several benefits to the layout procedure. By forcing related primitives to have standard heights, the fin alignment problem, as well as numerous complicated design rules in the frontend-of-line (FEOL), can be handled directly. Moreover, specific hard-to-automate layout patterns (e.g., interdigitation) can be directly implemented by layout experts to ensure performance requirements for each primitive. In practice, cell-based primitives are adopted for better coverage of a wide range of AMS circuit classes and a higher degree of design freedom. Figure 1(a) shows partial layout patterns of an optimized primitive cell consisting of ten transistors.
To reduce design complexity without significantly sacrificing solution quality and flexibility, advanced FinFET AMS circuits adopt a region-based layout methodology, where primitive cells with similar properties (e.g., PMOS, NMOS, standard cells) are grouped and placed in the same region. As shown in Figure 1(b), primitives in the same region share the same cell height to meet the row-based placement requirement. Region-based layouts allow easy base-layer design rule checking (DRC) and enable making reusable stand-alone intellectual properties (IPs) as each region is self-contained. In real-world designs, there could be more than five regions in a building block.
As placement determines the overall wiring topology in the later routing stage, various geometrical constraints should be carefully considered to guarantee circuit robustness and the performance specification. Typical constraints include symmetry, proximity, and fixed-boundary constraints [3]. For region-based layouts, additional constraints exhibited in Figure 2 are introduced, including
• Hierarchical Symmetry Constraints that place a set of primitive cells symmetrically with respect to multiple joint axes simultaneously. Violating hierarchical symmetry constraints can result in degraded power-supply rejection ratio, mismatched differential signals, and higher offset voltages [4]. • Array Constraints that force an adjacent placement of some cells in the same region with optional layout patterns such as interdigitation, common-centroid, and central-symmetrical. One can further extend array constraints to a hierarchical structure containing an array of arrays. • Cluster Constraints that place a set of primitive cells as close as possible. Note that a cluster constraint can apply to objects from different regions.
• Extension Constraints that reserve extra spaces around the target object (e.g., primitive, array, region) to be filled with some specified dummy cells. Extension constraints ensure spacing between adjacent cells to reduce electromigration concerns and extension of diffusion to minimize layoutdependent effects. Routability awareness is also a crucial factor. As signal interconnections are increasingly complicated in advanced Fin-FET nodes, placement algorithms without routability consideration could lead to severe routing congestion, making them unroutable. Limited work has demonstrated an effective way to simultaneously consider all the aforementioned constraints and the routability issue. Furthermore, directly extending previous methods for the region-based layout style would incur runtime overhead and solution quality degradation.
In this paper, we proposed a novel AMS placement framework targeting advanced FinFET designs. Translating the placement problem into satisfiability modulo theories (SMT) formulas, the proposed AMS placement framework is capable of handling the above geometrical constraints and routability considerations simultaneously. Highlights of this work are summarized as follows:
• We propose an SMT-based placement framework targeting a new region-based layout for advanced FinFET AMS designs with comprehensive constraint handling. • We develop a window-based pin density checking SMT formulation for placement routability consideration. Without the checking scheme, the placement solutions may be unroutable due to heavy local routing congestion. • We leverage incremental SMT solving techniques for efficient wirelength optimization, enabling the application of our framework to large-scale designs. • Experimental results on advanced industrial designs demonstrate the effectiveness of the proposed placement framework in generating high-quality solutions while satisfying all the specified constraints.
We classify previous AMS placement techniques into two paradigms: 1) stochastic methods and 2) analytical approaches.
Stochastic methods leverage probabilistic techniques (e.g., simulated annealing) to search solutions on topological representations (e.g., sequence pairs, B * -trees). These algorithms have been shown to be effective in handling various geometric constraints, including symmetry [5], common-centroid [6], regularity [7], proximity [8], pre-placed [9], fixed-boundary [10], and mimimum/maximum separation [11]. Performance-related constraints such as monotonic current flows [12] have also been studied. Despite the aforementioned previous work for a wide range of constraint handling, the extensibility of new constraints and the adaptation for region-based layouts are restricted as the manufacturing process evolves.
Analytical approaches optimize placement objectives directly using mathematical formulations. [13] proposes a hierarchical placement framework using mixed-integer linear programming (MILP). However, it suffers from poor scalability for large-scale circuits. In [14], a nonlinear programming (NLP) method is presented to achieve better scalability while considering complex design aspects such as system signal flows. Still, the constraint relaxation and the extra legalization step restrict its potential to handle various constraints simultaneously. [15] encodes the analog placement problem into SMT formulations. The flexible syntax of SMT enables efficient problem modeling and various constraint support. However, it fails to manage routability consideration and wirelength optimization. The use of integer theory may also lead to runtime overhead for system-level designs (e.g., ADC, PLL).
Most of the previous approaches target traditional planar layouts, and limited work has presented an end-to-end placement framework for FinFET circuits. In [16], a meshed tree representation is proposed to handle FinFET-induced constraints (e.g., fin alignment, mask conflict, mask density balance) together with traditional geometric constraints. Nevertheless, the lack of ability to consider routability and additional constraints introduced by the new region-based layout methodology make it unsuitable for designs in more advanced FinFET nodes.
A first-order theory T comprises a signature Σ T and axioms A T , where Σ T contains a set of constants, functions, and predicate symbols; A T is a set of first-order logic (FOL) sentences over Σ T providing the meaning of symbols. Specifically, the axioms A T ensures some legal interpretations in general FOL are not legal under T . A structure G is a T -model if G entails A for every A ∈ A T . Consider a first-order formula F , if there exists a T -model G and variable assignment σ such that G, σ entails F , then F is satisfiable modulo T .
The SMT problem determines whether a FOL formulation F T is satisfiable (SAT) or unsatisfiable (UNSAT) under some background theories. A model and variable assignment G, σ of F T is returned if F T is SAT. Combined theories are also supported for a richer modeling language. Frequently implemented theories in modern SMT solvers include the empty theory (i.e., uninterpreted symbols with equality), arithmetic on integers/reals, bit-vectors (BVs), and the array theory. An example SMT formula can be written as
where it includes atomic formulas over a language of equality, integer arithmetic, and uninterpreted symbols with Boolean combinations.
In this work, we formulate the placement problem with SMT formulas under the BV theory with Boolean combinations. Fully transferable to propositional logic, pure BV formulas can achieve magnitudes of solving time speedup compared with integers theories. Compared with propositional SAT and MILP formulations, SMT formulas supports richer modeling expressions (e.g., if-then-else, either-or, Boolean cardinality), thus amenable for efficient, versatile formulations for placement instances.
The placement problem for region-based FinFET AMS layouts is formulated as follows:
Problem 1 (Region-based FinFET AMS Placement): Given a circuit netlist T , a placement grid pattern, a set of primitive cells
and a set of AMS placement constraints (listed in Section I), generate an overlap-free placement solution such that each cell v i ∈ V locates in the associated region, the specified constraints are satisfied, the routability is considered, and the total placement cost is minimized.
The overall flow of our AMS placement framework is shown in Figure 3, which consists of three main phases: 1) power analysis, which specifies the netlist-dependent power abutment constraints, 2) SMT-based placement, which determines the cells' coordinates with optimized wirelength/routability while satisfying the constraints, and 3) post-processing, which inserts edge/dummy cells for each region and sets the final placement result from the final SMT model and variable assignment.
Before initializing the SMT formulations, we perform power analysis to capture the power abutment constraints. Due to the standard cell-like placement of region-based layout of primitive cells, cells from different power groups should be placed in disjointed rows; otherwise, a short violation between different power nets would occur, as shown in Figure 4.
To simultaneously handle all the constraints while preserving the flexibility of considering new constraints for unseen designs, we adopt SMT formulations to model the AMS placement problem. Additionally, an incremental solving procedure is built upon the SMT placement kernel to optimize the placement objectives efficiently. Table I summarizes the notations used in this paper. Fig. 4: Example of a power abutment constraint violation. The overlapping power pins of cells v i and v j are associated with nets VDD and VDDL, respectively.
1) SMT Variable Initialization: Given a user-specified utilization ratio γ ur and aspect ratio γ ar , we calculate the expected width W and height H of the design as
where A = A γ ur is the estimated total area, and A = vi∈V area(v i ) is the summation of the area of each cell v i ∈ V . Letting the greatest common divider (GCD) of all cell widths and heights be w and h, we scale down the entire design by dividing variables/constants in Table I related to the x-axis, yaxis by w and h, respectively, and define
where L x (resp. L y ) represents the size for BV variables associated with the x (resp. y) coordinate, W = W w denotes the scaled design width, and H = H h is the scaled design height. By scaling down the BV variables, every feasible SMT solution for the placement formulation directly guarantees a row-based implementation demanded by region-based layouts and makes sure that all the leftover spaces can be filled by dedicated dummy cells with width w and height h. Significant runtime speedup is also achieved due to the refined solution search space.
For each region r i , region constraints determine its dimension, ensure non-overlapping between r i and every other region r j ∈ R \ {r i }, and restrict the cells v i ∈ V with f R (v i ) = r i within the boundaries of r i . To decide the dimension of a region r i , we generate a set of scaled width/height candidate pairs S ri such that for each pair (w , h ) ∈ S ri , we have
where
denotes the approximated area of r i , A ri is the area summation of cells in r i , and γ ur ri is the user-defined utilization ratio for r i . We formulate the constraints for region dimension as:
For non-overlapping of regions, we define the SMT formulas as:
where ule(•, •) represents the "unsigned less than or equal to operator (≤)" for BVs, and D x (resp. D y ) is the reserved space for left/right (resp. bottom/top) region edge cells. To limit the cells inside the boundaries of their associated regions, we have
where r = f R (v i ) is the associated region of v i . The nonoverlapping between cells can be formulated similarly as in ( 6) by setting the reserved space to 0. b) Hierarchical Symmetry Constraints: For a symmetry group C sym , we formulate the y-axis symmetry constraints as:
where x sym is an auxiliary BV variable representing the symmetry axis, and v i ∈ C sym is the cell to be placed symmetrically to v i . The symmetry constraints for other symmetry axes can be defined similarly. Note that with a hierarchical symmetry constraint, a cell can be placed symmetrically with respect to multiple symmetry axes simultaneously. c) Array Constraints: We model the array constraints as:
where x l arr , x h arr , y l arr , y h arr are the left, right, bottom, and top array boundaries, and C arr contains the set of cells inside the array. Additional constraints can be formulated to realize specific array patterns. For example, the widely adopted common-centroid pattern can be modeled as: d) Cluster Constraints: For cluster C clus , we add a virtual net connecting the cells in C clus and define four new auxiliary variables x l clus , x h clus , y l clus , and y h clus similarly as in (9) for the net bounding box. Then, by assigning a higher weight constant to the virtual net, cells within a cluster will be placed as close as possible after wirelength optimization.
e) Extension Constraints: For extension constraints on regions, cells, and arrays, we adjust their non-overlapping constraints to reserve extra spaces from their boundaries. For instance, the adjusted non-overlapping constraints on cell v a in Figure 2(d) can be modeled as:
) where D L va and D R va denote the reserved space for v a from the left and right boundaries, respectively. The extension constraints for regions and arrays can be formulated similarly as in (11). pow . Then, for cells in the i th power group P i , we have
Note that the lower (resp. upper) bound of the first (resp. last) power group is bounded by the region boundary constraints. g) Pin Density Constraints: Compared with digital circuits, AMS designs have fewer nets, and thus the routability issue is dominated by local pin density. Therefore, we propose a windowbased pin density checking formulation to prevent localized routing congestion. Let W and H be the scaled width and height of a design, β x and β y be the scaled width and height of a check window, we construct a set of check windows M with |M | = ( Wβ x + 1)( Hβ y + 1) covering the entire design floorplan. For each check window m j ∈ M , we add a set of auxiliary Boolean indicators B such that |B| = |V |, where b i,j ∈ B equals 1 if cell v i overlaps with m j . Let the bottom-left coordinate of m j be (x mj , y mj ). The indicators b i,j satisfy the following formulation:
) where ugt(•, •) denote the "unsigned greater than operator (>)" for BVs. To further restrict the total pin count inside every window by a threshold λ th , we apply pseudo-Boolean constraints
where P (v i ) represents the set of signal pins inside v i . Figure 5 illustrates the concept of window-based pin density checking. Combining ( 13) and ( 14), our formulation improves the overall routability by eliminating local pin density hotspots.
Given an SMT placement instance F T specifying the constraints described above, we optimize the total wirelength by performing incremental SMT solving on F T . Algorithm 1 sketches the incremental solving procedure. For each net n i ∈ N , we attach four auxiliary variables x l ni , x h ni , y l ni , and y h ni signifying the net bounding box. In Lines 1-3, we initialize an SMT expression Φ for the weighted total wirelength with the weight η ni of each net. Virtual nets added by cluster constraints are also included. Then, incremental solving on F T continues until reaching the maximum iteration K iter or the ending criteria (i.e., UNSAT, timeout) is met, as shown in Lines 4-10. If F T is SAT, we record the resulting solution and add a stricter wirelength
G, σ := Model(F T ); Add assumptions to freeze some region/cell variables in Σ T ; 10:
else break; return ( G, σ , Φ); constraint (Φ < ζΦ ) to F T , where ζ ∈ (0, 1] is a constant whose value decreases as the iteration increases, and Φ denote the total wirelength based on the current solution G, σ . By adding assumptions to some regions and cell variables (Line 9), we can achieve significant runtime speedup due to the refined solution space. In practice, we maintain two sorted queues in descending order for regions and cells to select the assumed variables, denoted as Q r and Q v , respectively. The priority functions PR ri for region r i and PR vi for cell v i are defined as:
where P (v i ) denotes the set of pins on v i , N (v i ) is the set of nets connected to v i , deg(n i ) is the degree of n i , and δ 1 , δ 2 are weighted constants. In our implementation, δ 1 and δ 2 are set to 10 and 1, respectively.
The proposed AMS placement framework is implemented in C++ with the Z3 SMT solver [17]. All experiments are conducted on a Linux workstation with an Intel Xeon 2.7 GHz CPU with 128GB memory. We conduct experiments on two industrial designs, including a multiplexing buffer (BUF) and a voltagecontrolled oscillator (VCO). Figure 6 shows the circuit schematics. All benchmark circuits are designed by experienced AMS circuit designers under TSMC 5nm process, and the placement constraints are annotated by layout experts. After generating the placement layouts, the routing is completed by an analog router [18] with slight manual adjustment if needed. Then, we analyze the routed layouts by comparing detailed post-layout extractions and simulations with the optimized manual layout.
The multiplexing buffer is a full-custom design that selects between 16 signals using 4-bit control for performance and status monitoring. The circuit includes an output buffer for driving large parasitic and device loads, as shown in Figure 6(a). Hierarchical symmetry constraints should be applied for lower delay and parasitic capacitance variability between stages. To demonstrate the importance of the proposed constraints, we generate layouts with and without the hierarchical symmetry constraints. Critical constraints such as pin density constraints are applied to both layouts to ensure routablility. Note that for both layouts, the optimization loop (Algorithm 1) terminates after five iterations.
Table III shows the comparisons of the basic placement metrics. Capable of generating numerous solutions while satisfying the constraints, our framework can potentially produce superior placement results. The manual layout results in a 49% larger total area. Comparing the layouts with and without hierarchical symmetry constraints, we observe that the layout without proper constraints results in 35% longer HPWL, 62% longer RWL, 8% more vias, and 6.87× longer runtime, authenticating that with accurate design constraints specified, the proposed SMT-based placer has significant runtime speedup and quality improvement.
Table IV shows the detailed analyses of the insertion delays and rise/fall times, including the results of all internal stages. For the internal stages, the automated layout with proper constraints achieves an 8% reduction in insertion delay with lower delay variability compared to the manual layout. It also obtains lower average rise/fall times with significantly smaller variability. For the delays of all input-to-output paths, the automated layout achieves 6% average insertion delay reduction and considerably smaller delay variability. The notable performance degradation of the layout generated without the additional constraints demonstrates the significance of accurate constraint specification.
The four-stage VCO is designed to generate complimentary 7.7GHz in-phase and quadrature-phase clocks at a nominal 750mV supply. As shown in Figure 6(b), it includes startup circuitry and 3-bit thermometer-encoded control of digitally tunable capacitors for frequency trimming. We apply hierarchical symmetry, array, cluster, and extension constraints on top of the necessary constraints. To highlight the efficacy of the proposed design constraints, we generate another layout without applying the crucial constraints above. The optimization loop terminates after four iterations.
Table V details the results on placement metrics. With superb constraint solving ability, our SMT-based AMS placer achieves a more optimized circuit size where the area of the manual layout is 23% larger. Comparing the two layouts generated by our framework, we can find that without specifying proper constraints it produces 57% longer HPWL, 88% longer RWL, 60% more vias, and 87% longer runtime. Since more constraints are specified for a refined solution space, the runtime of the VCO is faster even though it is a more complicated design with more regions, cells, and nets than the BUF circuit. In practice, complicated AMS systems require sophisticated constraints, thus suited to our framework. Table VI summarizes the post-layout simulation results. One can observe that the layout generated by our framework consistently outperforms the manual design in terms of power consumption and operating frequency under various supply voltages (from 650mV to 900mV). As shown in Table VI, the manual layout results in 2% higher power consumption and 2% slower oscillation frequency on average compared with ours. Comparing the two automated layouts, we observe that the layout without correct constraints results in 12% degradation on the oscillation frequency. To further investigate the layout behavior at ultrahigh speed, we analyze the oscillation frequency for various capacitor trim codes. Figure 7 plots the performance comparisons with different capacitor trim codes. As shown in Figure 7, with various supply voltages, the automated layout with precise constraints consistently achieves higher oscillation frequency for all capacitor trim codes.
This work has presented an end-to-end AMS placement framework for advanced FinFET technology. SMT formulations have been shown to handle various placement constraints simultaneously for region-based AMS layouts. A window-based pin density checking method has been proposed to eliminate local congestion for better routability. An incremental SMT solving scheme has been proposed to optimize the placement objectives. Experimental results have demonstrated the efficiency and effectiveness of the proposed framework in producing high-quality placement solutions. 750mV Supply Voltage Fig. 7: Oscillation frequency v.s. Supply voltage under various capacitor trim codes for the VCO.
Authorized licensed use limited to: University of Texas at Austin. Downloaded on September 19,2022 at 02:32:28 UTC from IEEE Xplore. Restrictions apply.
Design, Automation and Test in Europe Conference (DATE 2022)