Parallel Cell Placement Experimental System 

ABSTRACT 

This experimental system has been constructed to examine the efficiency of 
the parallel algorithm when applied to cell placement problems in LSI-CAD 
,i.e., the combinatorial optimization problem. 

This problem requires the circuit data and cell data as input, and decides 
the placement of each cell so as to minimize the wiring area. 

FEATURES 

Parallel Simulated Annealing (PSA) is proposed. 

   ･ Plural SA processes execute iterative improvement under various val-
     ues in the parameter (temperature). 
     --- Global searching at higher temperatures, and local searching at 
     lower temperatures. 

   ･ The probabilistical and periodical exchange of solutions between ad-
     jacent temperatures automates the cooling schedules. 

Improvements in placement are monitored with the expert being allowed to 
  interact with the system. 

   ･ Displaying the estimated values of solutions on a line graph in real-
     time. 

   ･ Suspension and Re-execution are allowed to let the expert modify the 
     cell placements. 



Construction of parallel cell placement experimental system 
- 35 - 

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. 

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 -

Parallel Simulated Annealing algorithm 

Parallel SA(PSA) automates in temperature control which is difficult in 
sequential SA. In PSA, unique and fixed values of the temperature are given 
to each processor. Improvements in placement using random numbers are 
executed individually. Periodic comparison and exchange of solutions is con-
ducted between processors with adjacent temperatures. If the estimated value 
of the higher temperature is lower than that of the lower one or if two val-
ues are closed, the solutions of adjacent temperatures are exchanged. As a 
result, global improvement and local improvement are selected suitably as 
the execution proceeds, and the automatic in temperature control is realized. 
Finally the most improved solution appears in the processor with the lowest 
temperature. 







Concept of Parallel SA algorithm 
- 37 -

Abstract of demonstration 

We demonstrate the following two topics on Multi-PSI(64PE). Sixty three 
processor elements(PEs) are used to execute PSA under unique and fixed 
temperature values. Iterative improvements are executed simultaneously on 
these PEs. One PE is used to monitor the process of improvements. 

(1)Use artificial data which is small and has a known optimum solution. 

   ･ The data consists of 25 cells and 40 nets. 
   ･ The execution states are shown until the optimum solution is reached. 
   ･ The optimum solution is reached when the cells are placed in a 5 x 5 
     square. 

(2)Use real data with an unknown optimum solution. 

   ･ The data consists of 125 cells, #147 nets and 24 I/O's. 
   ･ At first, random initial placement is executed, and the estimated value 
     and channel density of the state are shown. The channel density is 
     shown on a bar chart in the figure titled "Initial Placement". 
   ･ The process of improvement is monitored by estimated values that are 
     displayed in real-time. 
   ･ After executing improvements in placement for a period of time, a 
     result is obtained. Check the improvement in estimated value and the 
     uniform expansion and flatness of the channel density. 




Initial Placement 
- 38 -