This paper addresses a placement method good for module generation. Conventional partitioning based method can not guarantee the best quality in consecutive partitioning, even if it can find a sequence of the minimum partitioning of a circuit into two subcircuits. Also, when size of cells varies very much, which is often seen in module generation as leaf cells, it is sometimes too strong constraint for them to get the minimum partitioning under ``partitioning into two similar size of subcircuits''. On the other hand, although conventional Simulated Annealing (SA) based method gives a better result, it requires extremely long computation time, since they do not employ any divide and conquer technique. It is the purpose of this paper to propose an algorithm which is based on SA method and employs the divide and conquer technique so that it gives better quality than partitioning based method and also it gives drastically faster computation time than SA method. As the first step, we applied this idea to the linear placement. Our algorithm is based on sorting inside subgroups, and this subgroup generation is done by plural cut-lines with a constant pitch. This constant pitch will be decreased from sufficiently large value to small value gradually, and this decreasing schedule is similar to the cooling schedule of SA method. And also, since there is a variation of offset in applying cut-lines even with the same pitch value, we randomly select one of them like SA method chooses a pair of components to be switched at random. Sorting inside subgroups is only a rearrangement depending on the connection between subgroups and is very fast. It is found that the total wiring length is improved about 10% compared to that of spectral method which was recognized to be the best (SLPC2). Also, computation time was dramatically reduced over the SA method.
['Shinji Sato']
Simulated quenching: a new placement method for module generation