Authors V.V. Kureichik, Vl.Vl. Kureichik
Month, Year 02, 2015 @en
Index UDC 321.628
Abstract This article deal with one of the key problem of the computer aided design of the computer hardware such as the VLSI fragments placement within restricted area of chip. This problem belongs to NP-hard and NP-full class of the optimization problem. A combined approach to solution of the VLSI fragments placement problem is described in the article. The statement of the VLSI fragments placement problem is shown. The authors propose new search architecture on the basis of multi-level approach. The fundamental difference of the proposed approach is search process division into two stages. At each stage different methods are used. At the first stage of search the circuit compresses on the basis of the fractals aggregation mechanism. At the second stage a genetic algorithm is applied. It allows for effective transposition of VLSI fragments. This enables to parallelize the search process and get the optimal and quasi optimal solutions in a time comparable to the time of iterative algorithms implementation. The authors describe an example of the placement problem solution based on the fractals aggregation mechanism and genetic search. Computational experiments were carried out with the use of several benchmarks. The placement quality based on the combined search technique is higher at the average of 6.38 per cent if it is compared with the placement based on the well-known algorithms such as the Capo 8.6, Feng Shui 2.0, Dragon 2.23. Therefore we demonstrate the effectiveness of the suggested approach. Series of tests and experiments showed a perspective of this approach. The time complexity of the developed algorithms in the best case is represented by ≈O(nlogn) and in the worst case is represented by О(n3).

Download PDF

Keywords Combined search; design; VLSI; genetic algorithm; fractals aggregation.
References 1. Bushin S.A., Kureychik V.V. Razmeshchenie uzlov i blokov radioelektronnoy i elektronnovychislitel'noy tekhniki na osnove bionicheskikh metodov [Placement of electronic components and units and computer equipment on the basis of bionic methods], Programmnye produkty i sistemy [Software Products and Systems], 2010, No. 1, pp. 12-14.
2. Kureychik V.V., Zaporozhets D.Yu. Sovremennye problemy pri razmeshchenii elementov SBIS [Modern placement’s problems of VLSI], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2011, No. 7 (120), pp. 68-73.
3. Sherwani N.A. Algorithms for VLSI Physical Design Automation. Third Edition, Kluwer Academic Publisher, USA, 2013.
4. Alpert C.J., Dinesh P.M., Sachin S.S. Handbook of Algorithms for Physical design Automation, Auerbach Publications Taylor & Francis Group, USA, 2009.
5. Kacprzyk J., Kureichik V.M., Malioukov S.P., Kureichik V.V., Malioukov A.S. General Questions of automated design and engineering, Studies in Computational Intelligence, 212, 2009, pp. 1-22.
6. Lim S.K. Practical Problems in VLSI Physical Design Automation, Springer Science + Business Media B.V, Germany, 2008.
7. Kureychik V.V., Kureychik V.M., Rodzin S.I. Teoriya evolyutsionnykh vychisleniy [The theory of evolutionary computation]. Moscow: Fizmalit, 2012, 260 p.
8. Gladkov L.A, Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy [Genetic algorithms]. Moscow: Fizmatlit, 2010, 368 p.
9. Kureychik V.V., Kureychik Vl.Vl. Bioispirirovannyy poisk pri proektirovanii i upravlenii [Search inspired by natural systems, for the design and management], Izvestiya YuFU. Tekhnicheskie nauki
[Izvestiya SFedU. Engineering Sciences], 2012, No. 11 (136), pp. 178-183.
10. Kureychik V.V., Bova V.V., Kureychik Vl.Vl. Kombinirovannyy poisk pri proektirovanii [Combined search in the design], Obrazovatel'nye resursy i tekhnologii [Educational Technologies], 2014, No. 2 (5), pp. 90-94.
11. Kureychik V.V., Kureychik V.M. Geneticheskiy algoritm razmeshcheniya grafa [Genetic placement algorithm graph], Izvestiya RAN. Teoriya i sistemy upravleniya [Izvestiya RAN. Teoriya i sistemy upravleniya], 2000, No. 5, pp. 67-78.
12. Kureychik V.V., Kureychik Vl.Vl. Integrirovannyy algoritm razmeshcheniya fragmentov CBIS [Integrated VLSI fragment placement algorithm], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2014, No. 7 (156), pp. 84-93.
13. Mandel'brot B. Fraktal'naya geometriya prirody [The fractal geometry of nature]. Moscow: Institut komp'yuternykh issledovaniy, 2002, 666 p.
14. Kureichik V.V., Kureichik V.M. Fractal algorithm for graph partitioning, Izvestiya Rossiyskoy akademii nauk. Teoriya i sistemy upravleniya [Izvestiya RAS. Theory and Control Systems], 2002, No. 4, pp. 65-75.
15. Kureychik V.V., Kureychik Vl.Vl. Arkhitektura gibridnogo poiska pri proektirovanii [The architecture of hybrid search for design], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 7 (132), pp. 22-27.
16. Bova V.V., Kureychik V.V. Integrirovannaya podsistema gibridnogo i kombinirovannogo poiska v zadachakh proektirovaniya i upravleniya [Integrated subsystem hybrid and combined search in problems of design and management], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2010, No. 12 (113), pp. 37-42.
17. Kureichik V.V., Kureichik V.M. Genetic search-based control, J. Automation and Remote Control, No. 62 (10), pp. 1698-1710.
18. Zaporozhets D.Y., Zaruba D.V., Kureichik V.V. Representation of solutions in genetic VLSI placement algorithms, Design & Test Symposium (EWDTS), 2014 East-West, 2014, pp. 1-4.
19. Kacprzyk J., Kureichik V.M., Malioukov S.P., Kureichik V.V., Malioukov A.S. Experimental investigation of algorithms developed, Studies in Computational Intelligence, 2009, No. 212, pp. 211-223+227-236.
20. IBM-PLACE 2.0 benchmark suits. Available at:

Comments are closed.