ABSTRACT 

The placement problem is one of the processes in LSI layout design. It 
decides the placement of each cell so as to minimize the wiring area from the 
given circuit data and cell data. The number of cells in a chip is very large. 
Thus it a vast solution space must be searched to minimize the wiring area. 

The Simulated Annealing (SA) sequential algorithm is well-known and is 
an efficient technique to solve this kind of combinatorial optimization prob-
lem. Parallel SA (PSA) is a new algorithm proposed for parallel computing 
machines. It automatically decides the value of a control parameter called 
'temperature'. This is a difficult problem when applied to the sequential SA 
algorithm. This experimental system applies PSA, and solves the placement 
problem in LSI layout design on a Parallel Inference Machine. 

The LSI design objective 


The objective of this system is to 
form a standard poly-cell type cells. 

The elements of the circuit are cells 
with various width and uniform height. 
A standard cell consists of plural cell 
blocks constructed from a line of cells. 
The object of this system is to minimize 
the total wiring length used to connect 
each cell and terminal in the LSI. 



Example of standard cell

Sequential Simulated Annealing algorithm 

Sequential SA is a kind of probabilistical algorithm. It iteratively improves 
the solution using pseudo random numbers. When applied to the cell place-
ment problem, the placement is iteratively improved by randomly changing 
arbitrary cell positions. The temperature parameter is used to control the 
system as described below. Global improvements in the initial stage of exe-
cution, and local improvements in the latter. The lower the temperature, the 
greater the emphasis on local improvement. The fine control of the tempera-
ture depends on the objective problem. Individual adjustment is required to 
apply the sequential SA algorithm to specify problems. 


					- 36 -