We propose an electrostatics-based placement algorithm for large-scale mixed-size circuits (ePlace-MS). ePlace-MS is generalized, flat, analytic and nonlinear. The density modeling method eDensity is extended to handle the mixed-size placement. We conduct detailed analysis on the correctness of the gradient formulation and the numerical solution, as well as the rationale of dc removal and the advantages over prior density functions. Nesterov's method is used as the nonlinear solver, which shows high yet stable performance over mixed-size circuits. The steplength is set as the inverse of Lipschitz constant of the gradient function, while we develop a backtracking method to prevent overestimation. An approximated nonlinear preconditioner is developed to minimize the topological and physical differences between large macros and standard cells. Besides, we devise a simulated annealer to legalize the layout of macros and use a second-phase global placement to reoptimize the standard cell layout. All the above innovations are integrated into our mixed-size placement prototype ePlace-MS, which outperforms all the related works in literature with better quality and efficiency. Compared to the leading-edge mixed-size placer NTUplace3, ePlace-MS produces up to 22.98% and on average 8.22% shorter wirelength over all the 16 modern mixed-size benchmark circuits with the same runtime.

We develop a flat, analytic, and nonlinear placement algorithm, ePlace , which is more effective, generalized, simpler, and faster than previous works. Based on the analogy between placement instance and electrostatic system, we develop a novel placement density function eDensity , which models every object as positive charge and the density cost as the potential energy of the electrostatic system. The electric potential and field distribution are coupled with density using a well-defined Poisson's equation, which is numerically solved by spectral methods based on fast Fourier transform (FFT). Instead of using the conjugate gradient (CG) nonlinear solver in previous placers, we propose to use Nesterov's method which achieves faster convergence. The efficiency bottleneck on line search is resolved by predicting the steplength using a closed-form equation of Lipschitz constant. The placement performance is validated through experiments on the ISPD 2005 and ISPD 2006 benchmark suites, where ePlace outperforms all state-of-the-art placers (Capo10.5, FastPlace3.0, RQL, MAPLE, ComPLx, BonnPlace, POLAR, APlace3, NTUPlace3, mPL6) with much shorter wirelength and shorter or comparable runtime. On average, of all the ISPD 2005 benchmarks, ePlace outperforms the leading placer BonnPlace with 2.83% shorter wirelength and runs 3.05× faster; and on average, of all the ISPD 2006 benchmarks, ePlace outperforms the leading placer MAPLE with 4.59% shorter wirelength and runs 2.84× faster.

ePlace is a generalized analytic algorithm to handle large-scale standard-cell and mixed-size placement. We use a novel density function based on electrostatics to remove overlap and Nesterov's method to minimize the nonlinear cost. Steplength is estimated as the inverse of Lipschitz constant, which is determined by our dynamic prediction and backtracking method. An approximated preconditioner is proposed to resolve the difference between large macros and standard cells, while an annealing engine is devised to handle macro legalization followed by placement of standard cells. The above innovations are integrated into our placement prototype ePlace, which outperforms the leading-edge placers on respective standard-cell and mixed-size benchmark suites. Specifically, ePlace produces 2.83%, 4.59% and 7.13% shorter wirelength while runs 3.05×, 2.84× and 1.05× faster than BonnPlace, MAPLE and NTUplace3-unified in average of ISPD 2005, ISPD 2006 and MMS circuits, respectively.

We consider a system subject to shocks that arrive according to a nonhomogeneous pure birth process (NHPBP). As a shock occurs, the system has two types of failures. Type-I failure (minor failure) is rectified by a general repair, whereas type-II failure (catastrophic failure) is removed by an unplanned replacement. The probabilities of these two types of failures depend on the number of shocks since the last replacement. We consider a policy with which the system is replaced at thenth type-I failure, or at any type-II failure. The aim of this paper is to determine the optimal policyn*, the number of minor failures up to replacement that minimizes the expected cost rate of the system subject to NHPBP shocks. The model is a generalization of the existing models, and is more applicable in practice. We present some numerical examples, and show that several classical models are the special cases of our model.

This note studies the block replacement policy with general repairs for an operating system subject to shocks occurring according to a non-homogeneous pure birth process. A shock causes the system to fail. There are two types of failures: a type-I failure (minor failure) is fixed by a general repair, whereas a type-II failure (catastrophic failure) is removed by an unplanned (or unscheduled) replacement. The failure type probabilities depend on the number of type-I failure shocks that occurred since the last replacement. Under the block replacement policy, the operating system is replaced every time units to reduce the chances of more expensive unplanned replacements due to type-II failures. The aim of this note is to determine the optimal block interval T*, which minimizes the expected cost rate and the expected total discounted cost rate of the proposed policy. As the shock process is a more general non-homogeneous pure birth process, several previous models become the special cases of our model.

An error in the above titled paper (ibid., vol. 58, pp. 397-405, Jun 2009) is pointed out and a revision is presented here.

A system is subject to shocks that arrive according to a non-homogeneous Poisson process. As these shocks occur, the system experiences one of two types of failures: a type-I failure (minor), rectified by a minimal repair; or a type-II failure (catastrophic) that calls for a replacement. In this paper, we consider a periodic replacement model with minimal repair based on a cumulative repair-cost limit. Under such a policy, the system is anticipatively replaced at then-th type-I failure, or at thek-th type-I failure (k <; n) at which the accumulated repair cost exceeds the pre-determined limit, or at any type-II failure, whichever occurs first. The minimum-cost replacement policy is studied by showing its existence, uniqueness, and structural properties. Our model is a generalization of several classical models in maintenance literature. Some numerical analyses are also presented.

This paper presents a generalized periodic imperfect preventive maintenance (PM) model for a system with age-dependent failure type. The imperfect PM model proposed in this study incorporates improvement factors vis-a-vis the hazard-rate function, and effective age. As failures occur, the system experiences one of the two types of failure: type-I failure (minor), and type-II failure (catastrophic). Type-I failures are rectified with minimal repair. In a PM period, the system is preventively maintained following the occurrence of a type-II failure, or at age T, whichever takes place first. At the N th PM, the system is replaced. An approach that generalizes the existing studies on the periodic PM policy is proposed. Taking age-dependent failure type into consideration, the objective consists of determining the optimal PM & replacement schedule that minimize the expected cost per unit of time, over an infinite horizon.

Placement is an important step in the overall IC design process in deep submicron technologies, as it defines the on-chip interconnects which have become the bottleneck in determining circuit performance. The rapidly increasing design complexity, combined with the demand for the capability of handling nearly flattened designs for physical hierarchy generation, poses significant challenges to existing placement algorithms. There are very few studies dedicated to understanding the optimality (i.e., the comparison of the solution of an algorithm to the optimal solution) and scalability (i.e., the analysis of the degradation of the performance of an algorithm as the input size of the problem increases) of placement algorithms, due to the limited sizes of existing benchmarks and limited knowledge of optimal solutions. The contribution of this work includes three parts. 1) We implemented an algorithm [Placement Examples with Known Optimal (PEKO) algorithm] for generating synthetic benchmarks that have known optimal wirelengths and can match any given net degree distribution profile. 2) Using benchmarks of 10 k to 2 M placeable modules with known optimal solutions, we studied the optimality and scalability of four state-of-the-art placers, Dragon (Wang et al., 2000), Capo (Caldwell et al., 2000), mPL (Chan et al., 2000), and mPG (Chang et al., 2002) from academia, and a leading edge industrial placer, QPlace (Cadence 1999) from Cadence. For the first time our study reveals the gap between the results produced by these tools versus true optimal solutions. The wirelengths produced by these tools are 1.59 to 2.40 times the optimal in the worst cases, and are 1.43 to 2.12 times the optimal on average. As for scalability, the average solution quality of each tool deteriorates by an additional 9% to 17% when the problem size increases by a factor of ten. These results indicate significant room for improvement in existing placement algorithms. 3) We studied the impact of nonlocal nets on the quality of the placers by extending the PEKO algorithm (PEKU algorithm) to generate synthetic placement benchmarks with a known upper bound of the optimal wirelength. For these benchmarks, the wirelengths produced by these tools are 1.75 to 2.18 times the wirelength upper bound in the worst case, and are 1.62 to 2.07 times the wirelength upper bound on average. Moreover, in our study we found that the effectiveness of the algorithms varies for circuits with different characteristics.

Placement is an important step in the overall IC design process in DSM technologies, as it defines the on-chip interconnects, which have become the bottleneck in determining circuit performance. The rapidly increasing design complexity, combined with the demand for the capability of handling nearly flattened designs for physical hierarchy generation, poses significant challenges to existing placement algorithms. There are very few studies on understanding the optimality and scalability of placement algorithms, due to the limited sizes of existing benchmarks and limited knowledge of optimal solutions. The contribution of this paper includes two parts: 1) We implemented an algorithm for generating synthetic benchmarks that have known optimal wirelengths and can match any given net distribution vector. 2) Using benchmarks of 10K to 2M placeable modules with known optimal solutions, we studied the optimality and scalability of three state-of-the-art placers, Dragon [4], Capo [1], mPL [24] from academia, and one leading edge industrial placer, QPlace [5] from Cadence. For the first time our study reveals the gap between the results produced by these tools versus true optimal solutions. The wirelengths produced by these tools are 1.66 to 2.53 times the optimal in the worst cases, and are 1.46 to 2.38 times the optimal on the average. As for scalability, the average solution quality of each tool deteriorates by an additional 4% to 25% when the problem size increases by a factor of 10. These results indicate significant room for improvement in existing placement algorithms.

In this paper we study the large-scale mixed-size placement problem where there is a significant size variation between big and small placeable objects (the ratio can be as large as 10,000). We develop a multi-level optimization algorithm, MPGMS, for this problem which can efficiently handle both large-scale designs and large size variations. Compared with the recently published work [1] on large-scale mixed macro and standard cell placement benchmarks for wirelength minimization, our method can achieve 13% wirelength reduction on average with comparable runtime.

A design methodology for the implementation of multi-million gate system-on-chip designs is described. The new methodology is based on the creation of a silicon virtual prototype early in the back-end design process. The prototype is generated in a fraction of the time required to complete the traditional back-end flow but still maintains very high correlation with the final design. The physical prototype becomes the 'cockpit' where many design implementation decisions can be optimized by leveraging the short iteration times. Hierarchical design methodologies benefit from the prototyping stage by enabling a more optimal partitioning. The silicon virtual prototype also alters the nature of the hand-off model between front-end and back-end designers. The netlist can now be quickly validated using the prototype: the physical reality is being injected early in the design process resulting in fewer iterations between front-end and back-end.

In this paper, we develop a multilevel global placement algorithm (MGP) integrated with fast incremental global routing for directly updating and optimizing congestion cost during physical hierarchy generation. Fast global routing is achieved using a fast two-bend routing and incremental A-tree algorithm. The routing congestion is modeled by the wire usage estimated by the fast global router. A hierarchical area density control is developed for placing objects with significant size variations. Experimental results show that, compared to GORDIAN-L, the wire length-driven MGP is 4-6.7 times faster and generates slightly better wire length for test circuits larger than 100000 cells. Moreover, the congestion-driven MGP improves wiring overflow by 45%-74% with 5% larger bounding box wire length but 3%-7% shorter routing wire length measured by a graph-based A-tree global router.

In this paper, we develop a multi-level physical hierarchy generation (mPG) algorithm integrated with fast incremental global routing for directly updating and optimizing congestion cost during placement. The fast global routing is achieved by using a fast two-bend routing and incremental A-tree algorithm. The routing congestion is modeled by the wire usage estimated by the fast global router. A hierarchical area density control is also developed for placing objects with significant size variations. Experimental results show that, compared to Gordian-L, the wire length driven mPG is 3-6.5 times faster and generates slightly better wire length for test circuits larger than 100K cells. Moreover, the congestion driven mPG improves 50% wiring overflow with 5% larger bounding box wire length but 3-6% shorter routing wire length measured by graph based A-tree.

This paper presents a new pseudopin assignment (PPA) algorithm with crosstalk noise control in multilayer gridless general-area routing. We propose a two-step approach that considers obstacles and minimizes the weighted sum of total wire length and the estimated number of vias under crosstalk noise constraints. We test our algorithms on a set of MCM examples and a set of standard-cell examples. Without crosstalk noise control in PPA, the average noise in the MCM test cases after detailed routing is 0.13-0.22 V/sub DD/ with up to 11% of nets larger than 0.3 V/sub DD/. However, if the noise constraint of each net is set to 0.3 V/sub DD/ in PPA, the average noise in each case reduces to 0.11-0.15 V/sub DD/ (15%-31% reduction) with no crosstalk noise violations. Most of the nets in our standard-cell test cases do not have noise problems. Our PPA algorithms still give better noise distributions and have 1%-10% noise reduction on the global nets in these standard-cell test cases. Even without ripup and reroute, the detailed routing completion rate is 93%-99% and the average vias per net is only 0.7-1.4 for our MCM test cases and 1.0-1.7 for our standard-cell test cases.

This paper presents a new pseudo pin assignment (PPA) algorithm with crosstalk noise control in multi-layer gridless general-area routing.We propose a two-step approach that considers obstacles and minimizes the estimated number of vias under crosstalk noise constraints.Without crosstalk noise control in PPA, the average noise after detailed routing of our test cases is 0.13-0.22VDD with up to 8% of nets larger than 0.3 VD~.However, if the noise constraint of each net is set to 0.3 VDD in PPA, the average noise reduces 15%-31% to 0.11-0.15VDD with no crosstalk noise violations.Even without rip-up and reroute, the detailed routing completion rate is 95%-99% and the ratio of vias to nets is only 0.7-1.2.

In this paper we present an efficient heuristic algorithm for the post-layout layer assignment and via minimization problem of multilayer gridless integrated circuit (IC), printed circuit board (PCB), and multichip module (MCM) layouts. We formulate the multilayer layer assignment problem by introducing the notion of the extended conflict-continuation (ECC) graph. When the formulated ECC graph of a layer assignment problem is a tree, we show that the problem can be solved by an algorithm which is both linear time and optimal. When the formulated ECC graph is not a tree, we present an algorithm which constructs a sequence of maximal induced subtrees from the ECC graph, then applies our linear time optimal algorithm to each of the induced subtrees to refine the layer assignment. Our experiments show that, on average, the number of vertices of an induced subtree found by our algorithm is between 12% and 34% of the total number of vertices of an ECC graph. This indicates that our algorithm is able to refine a large portion of the, layout optimally on each refinement, thus, producing highly optimized layer assignment solutions. We applied this algorithm to the via minimization problem and obtained very encouraging results, We achieved 13%-15% via reduction on the routing layout generated by the V4R router, which is a router known to have low usage of vias. Our algorithm has been successfully applied to routing examples of over 30 000 wire segments and over 40 000 vias. Finally, we outline how our layer assignment algorithm can also be used for delay and crosstalk minimization in high-performance IC, PCB, and MCM designs.

In this paper, we present an efficient heuristic algorithmfor the layer assignment and via minimization problem formulti-layer gridless IC, PCB, and MCM layout.We introducethe notion of the extended conflict-continuation (ECC)graph to represent the multi-layer layer assignment problem.Our algorithm is based on a linear time optimal algorithmthat solves a special case of the layer assignment problemwhen the ECC graph is a tree.For the general layer assignmentconstructs a sequence of induced subtrees in theECC graph and applies our linear time optimal algorithmto each of the induced subtrees.We have applied this algorithmto the via minimization problem and get very encouragingresults.We have achieved 13%-16% via reduction onthe routing layout generated by V4R router, which is arouter known to have low usage of vias.We successfully appliedour algorithm to routing examples of over 30,000 wiresegments and over 40,000 vias.