Simulated quenching: a new placement method for module generation

ABSTRACT

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.

References

1. 1.Kirkpatrick, S., C. D. Gelatt, and M. P. Vecchi, "Optimization by Simulated Annealing," Science, Vol. 220, (1983), pp671-680.
2. 2.C. K. Cheng, and E. S. Kuh, "Module Placement Based on Resistive Network Optimization," IEEE Trans. on Computer-Aided Design Vol. CAD- 3(3), Jul. 1984, pp218-25.
3. 3.J. Li, J. Lillis and C. K. Cheng, "Linear Decomposition Algorithm for VLSI Design Applications," Proc. IEEE Int. Conf. on Computer-Aided Design 1995, pp223-8.
4. 4.L. Hagen, and A. B. Kahng, "Fast Spectral Methods for Ratio Cut Partitioning and Clustering," Proc. IEEE Int. Conf. on Computer-Aided Design, 1991, ppl0-3.
5. 5.B. M. Riess, K. Doll, and F. M. Johannes, "Partitioning Very Large Circuits Using Analytical Placement Techniques," Proc. 31th A CM/IEEE Design Automation Conference, 1994, pp646-51.
6. 6.G. Sigl, K. Doll, and F. M. J ohanness, "Analytical Placement: A Linear or a Quadratic Objective Function?" Proc. 28th A CM/IEEE Design Automation Conference, 1991, pp427-32.
7. 7.J. Li., J. Lillis, L. T. Liu, and C. K. Cheng. "New Spectral Linear Placement and Clustering Approach," Proc. 33rd A CM/IEEE Design Automation Conference, 1996.
8. 8.R. S. Tsay, E. S. Kuh, and C. P. Hsu, "PROUD: A Fast Sea-of-Gates Placement Algorithm", Proc. 25th A CM/IEEE Design Automation Conference, 1988, pp318-23.
9. 9.R. S. Tsay, and E. S. Kuh, "A unified approach to partitioning and placement (VLSI layout)," IEEE Trans. on Circuits and Systems, Vol.38(5), May 1991, pp521-33.
10. 10.J.M. Kleinhans, G. Sigl, F. M. Johannes, and K. J. Antreich, "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization," IEEE Trans. on Computer-Aided Design, Vol.10(3), Mar. 1991, pp356-65.
11. 11.N.R.Quinn, "The Placement Problem as Viewed from the Physics of Classical Mechanics," Proceedings of the 12th Design Automation Conference, pp. 173-178, 1975
12. 12.D.F.Wong, H.W.Leong, and C.L.Liu, Simulated Annealing for VLSI Design, Kluwer Academic Publishers, 1988

Index Terms

• Applied computing

  • Physical sciences and engineering

    • Engineering

• Hardware

  • Electronic design automation

    • Physical design (EDA)

      • Placement

      • Wire routing

  • Very large scale integration design

    • Application-specific VLSI designs

      • Application specific processors

• Mathematics of computing

  • Mathematical software