Authors V.V. Kureichik, D.V. Zaruba, D.Y. Zaporozgets
Month, Year 04, 2015 @en
Index UDC 004.896
Abstract One of the most important tasks of design is the partitioning of ECE schemes components problem. The problem belongs to the class of NP-hard and NP-full problem. So, to solve it in polynomial time, it is reasonable to developed new heuristics methods to find optimal and quasi optimal solutions. The authors described the classical problem statement and formulated a optimization criterion. It is proposed new bioinspired approach to solve the partitioning of ECE schemes components problem on the basis of the modified graph coloring. The developer bioinspired search architecture based on the evolutionary approach applying. Modification of the method consists in implementation of modified coloring of the graph corresponding to the ECE schemes components. A modified partitioning algorithm was developed. This algorithm enabled to the authors to obtain solutions the specified accuracy in polynomial time. An example the problem solution was described. For experimental studies a software environment that implements the proposed algorithm was developed. A set of experiments allowed to specify the theoretical time complexity that is approximately О(n2).

Download PDF

Keywords Design; optimization; partitioning of ECE schemes components; bioinspired search; genetic algorithm.
References 1. Gladkov L.A., Kureychik V.V., Kureychik V.M., Sorokoletov P.V. Bioinspirirovannye metody v optimizatsii [Bioinspired optimization techniques]. 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 evolyutsionnykh vychisleniy [The theory of evolutionary computation]. Moscow: Fizmatlit, 2012, 260 p.
4. Emel'yanov V.V., Kureychik V.V., Kureychik V.M. Teoriya i praktika evolyutsionnogo modelirovaniya [Theory and practice of evolutionary modeling]. Moscow: Fizmatlit, 2003, 432 p.
5. Norenkov I.P. Osnovy avtomatizirovannogo proektirovaniya [Foundations of computer-aided design]. Moscow: Izd-vo MGTU imeni N.E. Baumana, 2006, 360 p.
6. Sherwani N.A. Algorithms for VLSI Physical Design Automation. Third Edition, Kluwer Academic Publisher, USA, 2013.
7. Lim S.K. Practical Problems in VLSI Physical Design Automation, Springer Science + Business Media B.V, Germany, 2008.
8. Alpert C.J., Dinesh P.M., Sachin S.S. Handbook of Algorithms for Physical design Automation, Auerbach Publications Taylor & Francis Group, USA, 2009.
9. Alpert C.J. et all. Hypergraph Partitioning with Fixed Vertices, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, February 2002, Vol. 19, No. 2, pp. 267-271.
10. Zaporozhets D.U., Zaruba, D.V., Kureichik, V.V. Representation of solutions in genetic VLSI placement algorithms, IEEE East-West Design & Test Symposium – (EWDTS’2014) Kiev, Ukraine, 2014, pp. 1-4.
11. Kureychik V.M., Kureychik V.V. Geneticheskiy algoritm razbieniya grafa [A genetic algorithm for graph partitioning], Izvestiya Rossiyskoy akademii nauk. Teoriya i sistemy upravleniya [Journal of computer and systems sciences international], 1999, No. 4, pp. 580-588.
12. Kureichik V.V., Kureichik V.V. Jr., Zaruba D.V. Partitioning of ECE schemes components based on modified graph coloring algorithm, IEEE East-West Design & Test Symposium – (EWDTS’2014) Kiev, Ukraine, 2014, pp. 1-4.
13. Vose M.D. Modeling simple genetic algorithms, In Whitley L.D. (ed): Foundations of Genetic Algorithms 2. Morgan Kaufmann, 2003.
14. Kureychik V.M., Kureychik V.V. Geneticheskie algoritmy v kombinatorno-logicheskikh zadachakh iskusstvennogo intellekta [Genetic algorithms in combinatorial and logical problems of artificial intelligence], Izvestiya TRTU [Izvestiya TSURe], 1999, No. 3 (13), pp. 126-128.
15. Kureychik V.V., Kureychik Vl.Vl. Bioinspirirovannyy algoritm razbieniya skhem pri proektirovanii SBIS [Bioinspired algorithm partitioning schemes in the design of VLSI circuits], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 23-29.
16. Kureychik V.V. Algoritmy razbieniya grafa na osnove geneticheskogo poiska [Graph partitioning based on genetic search], Izvestiya TRTU [Izvestiya TSURe], 1999, No. 3 (13), pp. 97-104.
17. Kureychik V.V., Sorokoletov P.V. Kompozitnye bionicheskie al-goritmy v komponovke blokov [Composite bionic algorithms in the layout blocks], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2006, No. 8 (63), pp. 41-46.
18. Kureychik V.V., Sorokoletov P.V. Evolyutsionnye algoritmy razbieniya grafov i gipergrafov [Evolutionary algorithms partitions of graphs and hypergraphs], Izvestiya TRTU [Izvestiya TSURe], 2004, No. 3 (38), pp. 42-49.
19. Gladkov L.A., Kureichik V.V., Kravchenko Y.A. Evolutionary algorithm for extremal subsets comprehension in graphs // World Applied Sciences Journal. – 2013. – P. 1212-1217.
20. Kacprzyk, J., Kureichik, V.M., Malioukov, S.P., Kureichik, V.V., Malioukov, A.S. Experimental investigation of algorithms developed // Studies in Computational Intelligence, 212. – 2009. – P. 211-223+227-236.

Comments are closed.