We propose a transistor placement algorithm to generate standard cell layout in a two-dimensional placement style. The algorithm optimizes the one-dimensional placement in the first stage, folds the large transistors in the second stage, and optimizes the two-dimensional placement in the final stage. We also propose "cost function" based on wiring length, which closely match the cell optimization. This transistor placement algorithm has been applied to several standard cells, and demonstrated the capability to generate a two-dimensional placement that is comparable to manually designed placement.

We present a new multi-layer over-the-cell channel router for standard cell layout design using simulated annealing. This new approach, STANZA-M consists of two key features. The first key feature of our router is a new scheme for simulated annealing in which we use a cost function to evaluate both the total net-length and the channel heights, and an effective simulated annealing process by a limited range to obtain an optimal chnnel wiring in practical time. The second feature of our router is a basic layer assignment procedure in which we assign all horizontal wiring inside a channel to feasible layers by considering the height of channel including cell region with a one dimensional channel compaction process. We implemented our three-layer cannel router in C language on a Solbourne Series 5 Work Station (22 MIPS). Experimental results for benchmarks such as Deutsch's Difficult Example and MCNC's PRIMARY1 channel routing problems indicate that STANZA-M can achieve superior results compared to the conventional routers, and the process times are very fast despite the use of simulated annealing.

In this paper we describe a new non-deterministic optimization method for standard-cell placement based on a method of theoretical physics, which we call the Trembling Spot-Check (TSC). First we discuss the analogy between a primitive cell placement system and a magnetic spin system by mapping from the placement evaluation function to the energy function, where the primitive placement system consists of the same area size cell and interconnections related to its four neighbor cells. Then we introduce a computational state calculation method using the theory for the magnetic spin system, called the `mean-field method'. The placement improvement process by TSC is similar to the energy minimization process by the mean-field method at temperature 0. To prevent the final state of the system from falling into a local minima, we adopt the redundance factor to this method by paying attention to the concept of fluctuation in statistical physics. This method of optimization, called TSC, has two such special features that it needs no annealing process and requires only one parameter definition concerning the redundancy. These two faculities in TSC make it possible to achieve the minimal solution without the bore process such as in the method of Simulated Annealing (SA). This new non-deterministic method of optimization is applied to both primitive and standard-cell placement problems. In the standard-cell placement problem each cell has the same height and various widths, and the interconnections between cells are very complicated. In the primitive placement experiments, TSC is compared with SA by the total interconnection length costs of the final states and CPU time to obtain them. In the standard-cell placement problem, the area size is evaluated. We suggest a simple model for standard-cell evaluation function derived from the area size estimation. It consists of averaged values of channel heights and their standard deviations. The results in the primitive placements show that TSC requires almost 1/10 times less CPU time than SA to achieve the same level solution. Almost the same results can be observed in the experiments of standard-cell placement.

Another high performance simulated annealing is proposed which we call widely stepping simulated annealing (WSSA). It flies from a starting high temperature to a finishing low temperature staying at only twenty or so temperatures to approach thermal equilibriums. We survey the phase transition in simulated annealing process and estimate the major cost variation (dEc) at the critical temperature. The WSSA uses a function (H(t)) that represents the probability for a hill-climbing with the dEc of cost increase to be accepted in Metropolis' Monte Carlo simulation at temperature t. We have applied the first version of WSSA to one dimensional transistor placement optimizations for several industrial standard cells, and compared its performance with simulated annealing with a geometrically scheduled cooling. The solutions by the WSSA are as good as, and sometimes much better than, the solutions by the simulated annealing, while the time consumption by the WSSA is properly under one 30th of that by the simulated annealing.

This paper describes a new clustering approach for VLSI placement, which is based on a fractal dimension analysis for the topological structure of modules in a logic diagram. A distinctive feature of this approach is that a measure of the 'fractal dimension' has been introduced into a logic diagram in such a way that the clustering of modules is iterated while the fractal dimension among clustered modules is retained in a prescribed range. A part of experimental results is also shown, which demonstrates that our clustering approach raises the placement performance much higher than the conventional clustering methods.

The importance of technology retargeting for hard IPs is getting increased. However, recent advances in process technologies make layout reuse too complicated to be done by conventional compactors. As an efficient approach, this paper proposes a flexible layout abstraction model and a new layout synthesis algorithm. The synthesis algorithm provides a concurrent procedure of detailed wiring, compaction, and transistor layout generation by using a scan line to get better layout results than conventional compactors. We have applied this method to the technology retargeting of actual cell layouts and have achieved quite good results comparable to hand-crafted designs.