Initial Placement of Basic Elements of Large-Scale Integrated Circuits by Random Assignment Method

Аuthors

Dobryakov V. A., Engalichev A. N.^*, Nazarov A. V.^**

Moscow Aviation Institute (National Research University), 4, Volokolamskoe shosse, Moscow, А-80, GSP-3, 125993, Russia

*e-mail: aengalychev@inbox.ru
**e-mail: rat-rut@yandex.ru

Abstract

The purpose of the current paper is obtaining such initial placement for basic elements of integrated circuits which provides higher quality with less computation time compared to known methods; that will increase the efficiency of the optimization methods of the placement such as a method dichotomy or Steinberg’s method
This research is based on the fact that the function of the total links length (TLL) is described under normal distribution law. Authors introduce the probability that at least one placement in progressive series of some random allocations (M) has TLL at any given threshold. Further, using methods of the probability theory, authors obtain the formula that allows one to calculate the value of M based on the predefined threshold and its likelihood value.
The carried out modelling verified that the proposed algorithm yields to the initial placement of basic elements, which in an average differs from optimum no more than 12 percent, with probability 0,9973.
It has to be noted that it takes about 30 minutes for a powerful personal computer to find the solution of the typical task given for circuits containing about one hundred elements.
As far as most of computer time it taken to obtain another random unduplicated set of numbers from 1 to N the paper presents new method that allows decreasing the cost of this calculation significantly.

Keywords:

placement, the method of random assignment, CMOS LSI dual-total length relationships, design automation, basic crystal matrix

References

1. Nazarov A.V., Fomin A.V., Dembickii N.L. Avtomatizaciya konstruirovaniya matrichnih KMOP BIS (Automation of design of matrix CMOS BIS), Moscow, Radio i svyaz, 1991, 256 p.
2. Glushko A.A. Informatika I sistemi upravleniya v XXI veke, Sbornik statei, Moscow, pp.154-163.
3. Grushvizkii R.I., Mursaev A.H., Ugrumov E.P. Proektirovanie system na mikroshemah programmiruemoi logiki (Designing of systems on a chip programmable logic), Spb., BHV, 2002, 608 p.
4. Glushko A.A., Rodionov I.A., Makarchuk V.V. Tehnologiya i konstruirovanie v elektronnoi apparature, 2007, no.4, pp.32-34.
5. Morozov K.K., Odinokov V.G., Kureichik V.M. Avtomatizirovannoe proektirovanie konstrukzii radioelektronnoi apparaturi (Automated design of electronic equipment), Moscow, Radio i svyaz, 1983, 280 p.
6. Potapov I.P., Achkasov A.V., Zolnikov B.R. Voprosi atomnoi nauki i tehniki, 2006, no.1-2, pp. 147-149.
7. Selyutin V.A. Mashinnoe konstruirovanie elektronnih ustroistv (Machinery construction of electronic devices), Moscow, Sovetskoe radio, 1977, 384 p.
8. Ueikerli Dg. F. Proektirovanie cifrovih ustroistv (Designing of digital devices), Moscow, Postmarket, 2002, 545 p.

Download