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.

In this paper, we propose a new clock tree synthesis method for semi-synchronous circuits. A clock tree obtained by the proposed method is a multi-level multi-way clock tree such that a clock-input timing of each register is a multiple of a predefined unit delay and the wire length from a clock buffer to an element driven by it is bounded. The clock trees are constructed for several practical circuits. The size of constructed clock tree is comparable to a zero skew clock tree. In order to assure the practical quality of the clock trees, they are examined under the five delay conditions, which cover various environmental and manufacturing conditions. As a result, they are proved stable under each condition and improve the clock speed up to 17.3% against the zero skew clock trees.

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.

In several researches in recent years, it is shown that the circuit of a higher clock frequency can be obtained by controlling the clock-input timing of each register. However, the power consumption of the clock-tree obtained by them tends to be larger since the locations of registers are not well taken into account in clock scheduling. In this paper, we propose a novel clock tree synthesis that attains both the higher clock frequency and the lower power consumption. Our proposed algorithm determines the clock-input timings of registers step by step in constructing a clock tree structure. First, the clock period of a circuit is improved by controlling the clock-input timing of each register, and second, the clock-input timings are modified to construct a low power clock tree without deteriorating the obtained clock period. According to our experiments using several benchmark circuits, the power consumption of our clock trees attain about 9.5% smaller than previous methods.

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.

IP (Intellectual Property) reuse plays an important role in modern IC design so that IP Protection (IPP) technique is get concerned. In this paper, we introduce a new efficient watermarking system for IPP on post-layout design stage. The signature (which indicates the designer) is encrypted with a secret key by DES (Data Encryption Standard) to produce a bit string, which is then embedded into the layout design as constraints by using a specific incremental router. Once the design is watermarked successfully, the signature can be extracted accurately by the system. The system also has a strong resistance to the attack on watermarking due to the DES functionality. This watermarking technique uniquely identifies the circuit origin, yet is difficult to be detected or fabricated without our tool. We evaluated the watermarking system on IBM-PLACE 2.0 benchmark suites. The results show the system robustness and strength: the system success probability achieves 100% in suitable time with no extra area and wire length cost on design performances.