Article

Article title HIERARCHICAL APPROACH FOR VLSI COMPONENTS PLACEMENT
Authors V.V. Kureichik, D.V. Zaruba, D.U. Zaporoghetz
Section SECTION II. AUTOMATION OF DESIGNING
Month, Year 07, 2014 @en
Index UDC 004.896
DOI
Abstract A modified hierarchical approach for solving VLSI components problem, consisting of three levels, proposed in this paper. On the ground level there is a preliminary decomposition of the whole space of the search group using an evolutionary approach. Geometric parameters of each group determined the total area of its constituent components. At the second level of decomposition is performed accommodation within groups based on a modified genetic algorithm. Modification of the algorithm is to use adapted to the solution of this problem crossover operators. The proposed operators allow knowingly receive the correct solution that reduces the time the final result. At the third level, based on genetic search, placed themselves decompositional group. To perform genetic procedures authors proposed a method of encoding and decoding of multiple alternative solutions using reverse polish notation. A computational experiment, which has confirmed the theoretical estimates of the performance and efficiency of the developed algorithms. A comparison with the classical algorithms and bioinspired search. The time complexity of the algorithm is ~ O (n log n).

Download PDF

Keywords VLSI design automation; placement; layout; multi-level optimization; genetic algorithm; bioinspired search.
References 1. Gladkov L.A., Kureychik V.V., Kureychik V.M., Sorokoletov P.V. Bioinspirirovannye metody v optimizatsii [Bioinspiration methods in optimization]. Moscow: Fizmatlit, 2009, 384 p.
2. Gladkov L.A., Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy [Genetic algorithms]. Moscow: Fizmatlit, 2010, 368 p.
3. Kureychik V.V., Kureychik V.M., Rodzin S.I. Teoriya evolyuеtsonnykh vychisleniy. Moscow: Fizmatlit, 2012, 260 p.
4. Kureychik V.V., Kureychik V.Vl. Evolyutsionnyy algoritm proektirovaniya kombinatsionnykh logicheskikh skhem [Evolutionary algorithm design of combinational logic circuits], Izvestiya Kabardino-Balkarskogo nauchnogo tsentra RAN [Izvestiya Kabardino-Balkar scientific centre of the RAS], 2013, No. 4 (54), pp. 42-47.
5. 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.
6. Zaporozhets D.Yu., Zaruba D.V., Lezhebokov A.A. Ob odnom sposobe kodirovaniya resheniya dlya zadachi razmeshcheniya [One method of encoding solutions of location problems], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 11 (136), pp. 183-188.
7. 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.
8. Kureychik V.M., Kureychik V.V. Geneticheskiy algoritm razbieniya grafa [Genetic algorithm for graph partitioning], Izvestiya RAN. Teoriya i sistemy upravleniya [Izvestiya of the Russian Academy of Sciences. Theory and control system], 1999, No. 4.
9. Kureychik V.V., Kureychik Vl.Vl. Bioinspirirovannyy algoritm razbieniya skhem pri proektirovanii SBIS [Biospherology partitioning algorithm of schemes in the design of VLSI], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 23-29
10. Zaporozhets D.Yu., Kudaev A.Yu., Lezhebokov A.A. Mnogourovnevyy algoritm resheniya zadachi parametricheskoy optimizatsii na osnove bioinspirirovannykh evristik [Multilevel algorithm for solving the problem of parametric optimization based on bioinspiration heuristics], Izvestiya Kabardino-Balkarskogo nauchnogo tsentra RAN [Izvestiya Kabardino-Balkar scientific centre of the RAS], 2013, No. 4, pp. 21-28.
11. 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.
12. 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.
13. Kurejchik V.V., Kurejchik V.M. On genetic-based control, Avtomatika i telemekhanika [Automatics and telemechanics], 2001, No. 10, pp. 174-187.
14. Kureychik V.V., Kureychik Vl.Vl. Bioispirirovannyy poisk pri proektirovanii i upravlenii [Biospherology search in the design and management], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 11 (136), pp. 178-183.
15. Kureychik V.V., Zaporozhets D.Yu. Roevoy algoritm v zadachakh optimizatsii [Swarm algorithm in optimization problems] Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2010, No. 7 (108), pp. 28-32.

Comments are closed.