The performance of various analog circuits depends significantly on the precise matching of elements [1]. Matching of elements can be impacted by two types of variations: random and spatial. Random variations can be reduced by increasing the area of the device [2] [3]. However, larger device may have more spatial variations as the distance between the devices increases [3]. Several factors, including process variations, thermal distribution or uneven mechanical stress from other circuit layers, can contribute to spatial variations [3]. The spatial variations can be modeled by Taylor series, where the lower order terms have greater impacts on the mismatch among devices [3][4] [5] [6]. Commoncentroid (CC) is a special layout technique which has been shown to be beneficial in reducing first-order variations [6] [7][8] [9]. However, for high performance systems, layout must be optimized considering nonlinear or higher order effects [3][4] [5] [6][10] [11].
Implementing any type of symmetricity in the layout can bring various challenges. Routing becomes more complicated with CC type layout, circuit area can increase if diffusion region is not shared, layout dependent effect can affect device threshold voltage, mobility and circuit performance [7] [12] [13]. Sharma et. al. [14] [7] have proposed custom algorithm for sym-metric transistor placement, which handles layout constraints. However, this method is limited to producing layouts of the CC type, making it inefficient in handling nonlinear variations. The method also lacks a welldefined objective in the problem formulation, hindering the ability to prioritize one constraint over another. Furthermore, the layout constraints are handled separately through post-processing steps after placement, which can lead to sub-optimal results.
Several prior studies have considered nonlinear spatial variations in device placement optimization. Lin et. al. [4] perform global placement of capacitors by adopting a conjugate gradient method and then legalizing the placement with an integer linear programming formulation. McAndrew [6] cancels the effect of nonlinear variations by swapping symmetrical devices. However, this approach can only manage two devices, and a dimension constraint requires the number of unit cells in each column to be a multiple of four. Vadipour [10] has proposed a ring-like structure to compensate for quadratic error. However, the techniques reported in [3][4][10] [11] may not apply to general transistor circuits, and some of the approaches [4][5] [6][10] dealing with device placement, focus on spatial variations and do not consider important layout constraints.
We present a simulated annealing based general transistor placement algorithm which can optimize nonlinear spatial variations while handling important layout constraints. Simulated annealing, a popular optimization technique [15], has found applications in both digital [16][17] and analog placement [3][18] [19]. The general idea behind these approaches revolves around the random selection of sub-blocks, followed by swapping to enhance performance. However, these approaches have limitations -they are inherently customized to specific systems and are not well-suited for addressing the general transistor placement problem. This is particularly evident when considering the absence of critical layout constraints within their formulations.
We adopt a strategy similar to random selection and swap, yet our approach is more general. It can handle transistor placement of varied configurations, such as current mirror, differential input pair, load pair, so can find application across a wide spectrum of analog systems. Our approach starts with an initial placement of unit cells, subsequently fine-tuning it through a dynamic process involving random selection and swapping. At each iteration, the placement is evaluated with models, developed for this work, guiding the process. The major contributions are as follows.
• We propose a simulated annealing based general approach for analog transistor placement considering nonlinear spatial variations.
• Compared to the state of the art [14] [7], where layout constraints are handled separately through post-processing steps, our approach considers the constraints within the optimization.
• Experimental results show the proposed approach beats the state-of-the-art in important parameters while minimizing nonlinear spatial variations.
• The proposed approach provides users with better control over the objectives than the state-of-the-art. The rest of the paper is organized as follows. Section II formulates the problem, Section III describes the proposed approach, Section IV presents experimental results, and Section V concludes the paper.
Spatial variations can cause mismatch issues in analog circuits. Spatial variations have linear and nonlinear components. In Fig. 1(b)-(c), two different layouts of a differential pair (Fig. 1(a)) are shown. While the layout in Fig. 1(b) is effective when only considering the firstorder effect, it is not the best layout for minimizing nonlinear variations. To reduce nonlinear variations, as a general rule, devices must be placed with the highest possible dispersion [6], as shown in Fig. 1(c). It is important to note that both these layouts are CC type. While it is possible to generate a CC layout that performs well for nonlinear variations involving a few units and devices, in general, as the number of units or devices increases, a non-CC layout consistently outperforms a CC layout. However, a layout that is designed to perform well for spatial variations may not align with critical layout constraints such as diffusion break, routing complexity, and layout-dependent effects. Therefore, our transistor placement formulation problem encompasses all these constraints to achieve a comprehensive and balanced optimization approach.
Based on the mismatch in spatial variations function 𝑀𝑉(•), routing complexity function 𝑅𝐶(•), mismatch in length of diffusion function 𝑀𝐼𝐿𝐷(•), and diffusion break function 𝐷𝐵(•), the optimization objective is defined as follows.
Here, 𝑓 𝑝 is a feasible layout solution and 𝜂 𝑐 , 𝑐 ∈ {𝑀𝑉 , 𝑅𝐶, 𝑀𝐼𝐿𝐷} denotes the coefficients. A hard constraint is put on diffusion sharing as this parameter has the most impact on the quality of the layout, directly or indirectly. A layout that does not share diffusion region can lead to worse routing length and may degrade spatial variations due to increased layout area. Consequently, our proposed method can ensure diffusion-break-free layout which is not possible with other methods [14][20] [8]. Importantly, [14] is more focused on generating CC layout, constraints are handled separately through post-processing steps. We handle layout constraints directly within the optimization framework, this can lead to better results. Moreover, our formulation allows users control over the objectives through coefficients 𝜂 𝑐 , which is not possible by other methods due to a fixed-type formulation that lacks a well-defined objective.
We first discuss the details on the funtions in Eqs. ( 1) and ( 2) before presenting the optimization algorithm in Section III-E to solve them.
Thermal-induced and technology-related spatial variations can be approximated using a Taylor series, which takes the following form [3][4][5] [6].
Here, (𝑥, 𝑦) is the location of a unit cell and 𝐶 is a constant independent of 𝑥 and 𝑦. 𝐺 𝑖 (𝑥, 𝑦) is the 𝑖 𝑡 ℎ order variations component and 𝑝 𝑛 (𝑥, 𝑦) is the sum of such components. Our objective is to minimize the difference (or mismatch) in spatial variations for all the devices. We propose the following model.
Here, 𝑁 is the number of devices and 𝑛 𝑙 , 𝑛 𝑚 is the number of units for the device 𝑙 and 𝑚, respectively. 𝑝 𝑢 (𝑥, 𝑦) is the sum of first and second-order spatial variations with coefficients 𝑔 1,0 , 𝑔 0,1 , 𝑔 2,0 , 𝑔 1,1 , 𝑔 0,2 being modeled as multivariate Gaussian random variables. By iterating mismatch calculation following Eq. ( 5), 𝑀 times, 𝑀 number of mismatch values are obtained and the standard deviation of these values represents the magnitude of difference in spatial variations over all devices, referred to as 𝑀𝑉(•).
The routing complexity is affected by the position of the unit cells in the layout, making it essential to take routing considerations into account during the placement optimization. Sharma et al. [14] address routing complexity, but the approach has a limitation in that it handles routing after placement step, which can lead to sub-optimal results. In our approach, routing model is integrated within the placement step.
We use rectilinear minimum spanning tree (RMST) to calculate routing complexity separately for every net in the netlist and sum the values. For illustration purpose, we use the circuit in Fig. 2, where each device has 4 units. First, we construct an undirected graph in which a unit cell connected to the net is represented by a node, and rectilinear edges are used to connect every pair of nodes on the net. For example, net1 has unit cells from 𝑀2, so a total of 4 nodes and 6 edges, net3 has unit cells from 𝑀2 and 𝑀0, so a total of 8 nodes and 28 edges. We determine the RMST that connects all the units on the net with the fewest possible edges. For example, the routing complexity of net1 and net3 are 7 and 9 units, respectively. Total routing complexity is determined by summing the edge weights of the spanning trees for all the nets, which in this case is 56. A pseudocode is presented below. The time complexity of our algorithm is 𝑂(𝑛 2 ) with 𝑛 being the number of units.
Among several layout dependent effects (LDEs), the most critical is length of diffusion (𝐿𝑂𝐷), which captures the variations in the threshold voltage (𝑉 𝑡 ℎ ) of a transistor due to stress effect [12][13] [14].
Here, 𝑛 is the number of unit cells, 𝐿 𝑔 is the gate length of the unit. 𝑆𝐴 𝑖 and 𝑆𝐵 𝑖 are the distances from polygate of the unit cell 𝑖 to the diffusion/active edge on either side of the layout. Two unit cells with different 𝑆𝐴 𝑖 , 𝑆𝐵 𝑖 values will lead to the mismatch in threshold voltage shift (Δ𝑉 𝑡 ℎ ). To reduce variations induced by 𝐿𝑂𝐷, we aim to minimize the difference (i.e. mismatch) of the mean values of 1 𝐿𝑂𝐷 over all devices, referred to as 𝑀𝐼𝐿𝐷(•). We propose the following model for 𝑀𝐼𝐿𝐷(•).
𝑁 is the number of devices and 𝑛 𝑖 is the number of unit cells of the device 𝑖. Hence, there are 𝑁 𝑖=1 𝑛 𝑖 number of unit cells in total. ( 1 𝐿𝑂𝐷 ) 𝑖 is the 1 𝐿𝑂𝐷 value of the device 𝑖. For the comparison between different placement, it is not essential to calculate the exact value of 1 𝐿𝑂𝐷 , rather the following simplification of Eq. ( 7) is sufficient.
(
Here, 𝑥 𝑢 is the column of unit cell 𝑢 and 𝑤 is the number of unit cells in each row, and these values can be easily obtained with changing placements. For example, if the unit cell 𝑢 is placed at the lowest left corner of 4 × 6 placement grid, 𝑥 𝑢 is 1 and 𝑤 is 6.
The diffusion region can be shared between two units of the same device and between units from different devices if their drain/source regions are connected. This practice can significantly reduce layout area, thereby improving routing length and spatial variations. In cases where sharing is not possible, there is diffusion break. Our objective is to have zero diffusion break.
Below, we present pseudocode for counting the number of diffusion breaks. The algorithm iterates through each unit in the row following the layout pattern. In each iteration, we maintain two units: 'curr' and 'next,' each comprising three fields: 'name,' 'left' terminal, and 'right' terminal. The process begins by checking whether starting from a drain ('D') as the leftmost terminal would result in a diffusion-break-free solution. Following the netlist, if two consecutive units are found to be not connected, the process is repeated with the source ('S') as the leftmost terminal. If we still reach two consecutive units having no connection, it indicates the presence of a diffusion break. To resolve this, a dummy unit is inserted between the units. Now, the left terminal of the unit, next to the dummy, becomes the leftmost terminal. The process continues until the end of the row is reached. The process is repeated for every row, and the diffusion break numbers 𝑛_𝑑𝑏(𝑖), 𝑖 ∈ {1, 2, ..., 𝑟𝑜𝑤} are summed up to determine the total number of diffusion breaks. The time complexity of our algorithm is 𝑂(𝑛), where 𝑛 is the number of units.
Simulated annealing (SA) is a probabilistic optimization technique based on a global search metaheuristic [15]. SA is particularly useful when the search space is discrete. While SA typically performs well for small to medium size problems, it may have problems for large size problems, potentially getting stuck in local minima. Additionally, due to its iterative nature, SA can be time-consuming when applied to large problems. The motivation behind using SA is that the search space in our problem is not large enough that SA would be considered inefficient, and it is also not small enough that a brute force method would work. Note that there are
possible placement solutions, where 𝑛 𝑖 is the number of units for the device 𝑖 and 𝑁 is the number of devices.
Let 𝑓 : 𝒮 → R be an objective function defined in the solution space 𝒮, and 𝒩(𝑠) be the neighbor function for 𝑠 ∈ 𝒮. SA starts with an initial solution 𝑠 ∈ 𝒮. At each iteration, neighboring solution 𝑠 ′ ∈ 𝒩(𝑠) of the current solution 𝑠 is selected through a predefined perturbation strategy. The metropolis criterion determines the acceptance probability for the system's transition from the current solution 𝑠 to a candidate counterpart 𝑠 ′ according to the following.
where 𝑓 (•) is the objective function defined in Eq. ( 1) and 𝑡 𝑘 represents the temperature value at the 𝑘 𝑡 ℎ iteration. The metropolis criterion guides the system toward a state of lower cost.
1) Initial Solution: The initial step in our proposed algorithm involves determining the number of rows and columns based on the width and height of the unit cell and the total number of units from the netlist. It is understood that a square-like pattern offers the best matching performance [14] [11]; therefore, we strive to achieve such a pattern, even if it necessitates the inclusion of dummy devices. The initial pattern is then generated with a sequential placement of device (with units of the same device placed together) with two consecutive devices sharing either drain and source, or source and source, or source and drain in the netlist. For example, for the circuit in Fig. 2, we can place units of 𝑀2, 𝑀0, 𝑀1, and 𝑀3 in the four rows, from top to bottom, respectively. This sequential arrangement ensures there is no diffusion break to begin with. We have observed that this technique of initial pattern generation yields better final results than starting from a completely random placement. In cases where we begin from a completely random placement, the algorithm may fail to converge to a diffusion-break-free solution.
2) Random Perturbation: A neighboring placement solution is produced by some predefined perturbation strategy. We follow the below rules for the perturbation.
• Swap only if the pair is from different devices.
• Swap only if the new solution does not degrade diffusion break. • Swap if there is an improvement in the objective.
• Swap a worse solution with some probability defined in Eq. (10). We measure the quality of a swap using models developed in prior sections. When we encounter a candidate that improves the current best objective (Eq. ( 1)) without degrading diffusion break, best solution is updated. We update the current solution if a candidate improves the current objective without degrading diffusion break. We may also update the current solution with the candidate solution even if it deteriorates the objective. The likelihood of that happening decreases as the temperature decreases. Note that a solution is never accepted if it degrades diffusion break. Fig. 3(a) shows the execution of the algorithm, how best, current, and candidate objectives change over the course of the iterations as temperature changes. Below, we present a pseudocode of the placement optimization algorithm. Algorithm 3 Optimize Placement Input : netlist, init_pattern, n_iteration, temp, 𝜂 𝑐 , 𝑐 ∈ {𝑀𝑉 , 𝑅𝐶, 𝑀𝐼𝐿𝐷} Output : best_pattern 1: best.obj = f(init_pattern, netlist, 𝜂 𝑐 ); best.DB = 𝐷𝐵(init_pattern, netlist) 2: curr = best 3: for i=1 to n_iteration do 4: Generate random number, x and y 5: cand = curr 6: tmp.pattern = cand.pattern 7: cand.pattern(x.row, x.col) = curr.pattern(y.row, y.col) 8: curr.pattern = tmp.pattern 9: cand.obj = f(cand_pattern, netlist, 𝜂 𝑐 ); cand.DB = 𝐷𝐵(cand_pattern, netlist) 10: if cand.obj < cand.obj ∧ cand.DB ≤ cand.DB then best = cand 11: 𝑡 𝑖 = temp/(i+1) 12: diff.obj = cand.obj -curr.obj 13: diff.DB = cand.DB -curr.DB 14: metropolis = exp(-diff.obj/𝑡 𝑖 ) 15: Generate random number, z 16: if (diff.obj < cand.obj ∧ diff.DB ≤ 0) ∨ (z < metropolis ∧ cand.DB ≤ best.DB) then 17: curr = cand 18: return best_pattern
We have implemented the proposed algorithm in Python, referred to as SA here. We contacted the authors of the paper [14] and discussed the implementation of their algorithm, which we refer to as SOTA (State-of-the-Art). Some of the results presented for the SOTA approach are based on this discussion and others are taken directly from [14]. Since it is difficult to obtain the exact values of the coefficients in Eq. ( 6) [3], and the second order terms can be as significant as the first order terms [6], we define the five random variables in Eq. ( 6), with a mu of [0 0 0 0 0], and a positive semidefinite covariance matrix of [0.9 0.8 0.7 0.6 0.5; 0.8 0.9 0.8 0.7 0.6; 0.7 0.8 0.9 0.8 0.7; 0.6 0.7 0.8 0.9 0.8; 0.5 0.6 0.7 0.8 0.9], following the multivariate statistics. Correlation of these variables is shown in Fig. 3(c). 𝜂 𝑐 for 𝑐 ∈ {𝑀𝑉 , 𝑅𝐶, 𝑀𝐼𝐿𝐷}, and 𝑡𝑒𝑚𝑝 in the simulated annealing algorithm are set to 1, and 100, respectively. In all the tests, our algorithm converges within 1000 iterations (𝑛_𝑖𝑡𝑒𝑟 𝑎𝑡𝑖𝑜𝑛). All experiments are conducted on a Linux environment with an Intel Core 3.3𝐺𝐻𝑧 CPU with 128𝐺𝐵 memory.
To compare the proposed approach with SOTA, we use five configurations of the current mirror structure, as reported in [14], referred to as CM:1-5 in Table I. Our algorithm outperforms SOTA. Both algorithms produce layout free of diffusion break (𝐷𝐵). We further validate quality of the layout using standard industry tool. We place the devices following the pattern generated by the algorithms and auto-route the circuit. The total route length ('Router' in Table I) is estimated using a script provided by industry representative. Our algorithm consistently performs better than SOTA, thereby validating correctness of the routing model. It is important to note that a shorter route length should result in reduced parasitics and IR drop, an important requirement in analog design. However, standard industry tools do not factor in spatial variations, as foundry models lack sensitivity to the distance between devices. While these tools do consider 𝐿𝑂𝐷 effect, quantifying its isolated impact is challenging due to the presence of other layout effects and random variations. LDEs are considered in post-layout simulation in [14], nevertheless, the improvement in circuit offset performance mainly comes from the dummies, placed around the CC structure. In Fig. 4(b), we present the layout pattern of the circuit in Fig. 4(a). Fig. 4(c) presents histogram plot of the mismatch in spatial variations. The actual layout of this example is presented in Fig. 4(d).
We have created six more tests in Table II, two from each of the three different configurations, CM (Fig. 4(a)), DIPC (Fig. 2), and DLPC (Fig. 4(e)). The proposed algorithm outperforms SOTA. Importantly, the
Authorized licensed use limited to: University of Texas at Austin. Downloaded on January 30,2025 at 20:21:13 UTC from IEEE Xplore. Restrictions apply.