Authors V.V. Kureichik, Vl.Vl. Kureichik
Month, Year 07, 2014 @en
Index UDC 321.628
Abstract One of the important tasks of the design engineering such as VLSI placement problem is presented in this article. It belongs to the class of NP-hard problem. The paper contains formulation of the placement problem. The models represent the problem of locating and proved multilevel hierarchical decomposition structure. Formulated heuristics, allowing to allocate associated fragments of a graph model of a circuit diagram in the form of building blocks formed by short chains. It was suggested a combined search, implemented by a hierarchical principle on the basis of genetic, evolutionary and algorithms modeling decision-making mechanisms in natural systems. It was developed an integrated algorithm that allows to parallelize the process of solving the problem and partly to eliminate preliminary convergence. Computational experiment was performed. Carried out a series of tests and experiments allowed to specify the theoretical estimation of the time complexity of algorithms and organize their behavior for circuits with different structures. In the best case time complexity of algorithms is about O (nlogn), in the worst case – O (n3).

Download PDF

Keywords Combined search; design engineering; ant algorithm; placement; genetic algorithm.
References 1. Kureychik V.V., Kureychik V.M., Gladkov L.A., Sorokoletov P.V. Bionspirirovannye metody v optimizatsii [Inspirowanie methods in optimization]. Moscow: Fizmalit, 2009, 384 p.
2. Kureychik V.V., Kureychik Vl.Vl. Arkhitektura gibridnogo poiska pri proektirovanii [Hybrid search when designing], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 7 (132), pp. 22-27.
3. Gladkov L.A, Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy [Genetic algorithms]. Moscow: Fizmatlit, 2010, 366 p.
4. Dorigo M., Maniezzo V., Colorni A. The Ant System: Optimization by a colony of cooperating objects, IEEE Trans. on Systems, Man, and Cybernetics, 1996, Part B, No. 26 (1), pp. 29-41.
5. Kureychik V.V., Kureychik V.M., Rodzin S.I. Teoriya evolyutsionnykh vychisleniy [The theory of evolutionary computation]. Moscow: Fizmalit, 2012, 260 p.
6. Bova V.V., Kureychik V.V. Integrirovannaya podsistema gibridnogo i kombinirovannogo poiska v zadachakh proektirovaniya i upravleniya [Integrated hybrid and combined search in the problems of design and management], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2010, No. 12 (113), pp. 37-42.
7. Kureychik V.V., Zaporozhets D.Yu. Sovremennye problemy pri razmeshchenii elementov SBIS [Modern problems when placing elements of VLSI], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2011, No. 7 (120), pp. 68-73.
8. Kureychik V.V., Kureychik V.M. Geneticheskiy algoritm razmeshcheniya grafa [Genetic algorithm for accommodation count], Izvestiya RAN. Teoriya i sistemih upravleniya [Izvestiya of the Russian Academy of Sciences. Theory and control system], 2000, No. 5, pp. 67-78.
9. Kureichik V.M., Kureichik V.V. Genetic algorithm for the graph placement, Journal of Computer and Systems Sciences International, 2000, Vol. 39, No. 5, pp. 733-740.
10. Bushin S.A., Kureychik V.V. Razmeshchenie uzlov i blokov radioelektronnoy i elektronnovychislitelnoy tekhniki na osnove bionicheskikh metodov [Accommodation units and blocks for radio-electronic and computer engineering on the basis of the bionic methods], Programmnye produkty i sistemy [Software and systems], 2010, No. 1, pp. 12-14.
11. Kurejchik V.V., Kurejchik V.M. On genetic-based control, Avtomatika i telemekhanika [Automatics and telemechanics], 2001, No. 10, pp. 174-187.
12. Kureychik V.V., Sorokoletov P.V. Kontseptualnaya model predstavleniya resheniy v geneticheskikh algoritmakh [Conceptual model of representations of solutions in genetic algorithms], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2008, No. 9 (86), pp. 7-12.
13. Kureychik V.M., Kureychik V.V., Rodzin S.I. Modeli parallelizma evolyutsionnykh vychisleniy [Concurrency models of evolutionary computing], Vestnik RGUPS [Vestnik RGUPS], 2011, No. 3, pp. 93-97.

Comments are closed.