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 -