Authors O.B. Lebedev, O.A. Purchina
Month, Year 06, 2015 @en
Index UDC 681.325
Abstract This paper presents a synthesis algorithm of single layer routing sketch in over-the-cell (OTC) field VLSI layout. Develop new mechanisms for solving the problem tracing, using mathematical methods, which lays down the principles of the natural mechanisms of decision-making. For the synthesis of single layer routing sketch uses a new paradigm of combinatorial optimization tree ant colony optimization (T-ACO)), based on the ideas of adaptive behavior of an ant colony and first of all on the idea of indirect exchange – stigmiergy, which allows for the synthesis of a tree. Unlike the canonical paradigm of ant algorithm the ant at a special graph to find solutions G=(X,U) is constructed decision trees. The structure and method of forming a special graph to find solutions G=(X,U) are described. Are offered the principles of interpretation of the ants solutions in the form of a single layer trace sketch. The problem is solved in various productions with different type of trace areas boundaries. Program OTC trace was implemented in C++ forthe IBM PC. In all of these productions was received result close to optimum. When using "broken" border procedures "sticking" and consistent trace OTC able to further reduce the overall density of channels up to 40 %. The proposed router is fully applicable to "gridless" trace of different widths connections. Experimental researches were carried out on IBM PC. The time complexity of the algorithm, obtained by experiment, almost the same as the theoretical research and test problems is considered about O(n2), where n – number of connections. For the objective of the experiments were used known test problems represented in the literature and the Internet. To provide reliable conclusions was held not one but a series of experiments, experiments. In comparison with existing algorithms improve the results achieved on 2–3 %.

Download PDF

Keywords Swarm intelligence; ant colony; adaptive behavior; trees ant colony optimization; trace; over the cell areas.
References 1. Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar. Handbook of algorithms for physical design automation. CRC Press, New York, USA, 2009.
2. Roy J.A. High-Performance routing at the nanometer scale, IEEE Trans. Comput.-Aided Design Integr. Syst., – June 2008, Vol. 27, issue 6, pp. 1066-1077.
3. Lebedev B.K., Lebedev V.B. Poiskovye protsedury kanal'noy trassirovki baziruyushchiesya na modelirovanii adaptivnogo povedeniya roya chastits v prostranstve resheniy s neuporyadochennym lingvisticheskim shkalirovaniem [Search procedures of channel trace in space of decisions with disorder linguistic scales, based on modelling of adaptive behaviour of a plenty of particles], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2009, No. 12 (101), pp. 15-22.
4. Lebedev O.B. Trassirovka v kanale metodom murav'inoy kolonii [Chanel routing bases on method of unt colony optimization], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2009, No. 4 (93), pp. 46-52.
5. Lebedev B.K. Intellektual'nye protsedury sinteza topologii SBIS [Intellectual procedure of synthesis of VLSI topology]. Taganrog: Izd-vo TRTU, 2003.
6. Dorigo M. and Stьtzle T. Ant Colony Optimization. MIT Press, Cambridge, MA, 2004.
7. Dorigo M., Stьtzle T. Ant Colony Optimization: Overview and Recent Advances. M. Gendreau and Y. Potvin, editors, Handbook of Metaheuristics, 2nd edition. Vol. 146 in International Series in Operations Research & Management Science. Springer, Verlag, New York, 2010, pp. 227-263.
8. Lebedev B.K., Lebedev V.B. Optimizatsiya metodom kristallizatsii rossypi al'ternativ[Optimization by the crystallization of alternatives field (CAF) Method], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 11-17.
9. Lebedev O.B. Modeli adaptivnogo povedeniya murav'inoy koloniiv v zadachakh proektirovaniya [Models of adaptive behaviour formic colonies in the task of designing]. Taganrog: Izd-vo YuFU, 2013.
10. Lebedev O.B. Pokrytie metodom murav'inoy kolonii [The coating method of the ant colony], Dvenadtsataya natsional'naya konferentsiya po iskusstvennomu intellektu s mezhdunarodnym uchastiem KII-2010. Trudy konferentsii [Twelfth national conference on artificial intelligence with international participation KII-2010. The conference proceedings]. Vol. 2. Moscow: Fizmatlit, 2010, pp. 423-431.
11. Lebedev B.K., Lebedev V.B. Postroenie kratchayshikh svyazyvayushchikh setey na osnove metoda murav'inoy kolonii [Build shortest connecting networks based on ant colony method], Nechetkie sistemy i myagkie vychisleniya: sb. st. Tret'ey Vserossiyskoy nauchnoy konferentsii [Fuzzy systems and soft computing: a collection of articles of the Third all-Russian scientific conference]. In 2 volumes. Vol .II. Volgograd state technical University. Volgograd, 2009, pp. 42-50.
12. Kureychik V.M., Lebedev B.K., Lebedev O.B. Razbienie na osnove modelirovaniya adaptivnogo povedeniya biologicheskikh sistem [Partitioning based on simulation of adaptive behavior of biological systems], Neyrokomp'yutery: razrabotka, primenenie [Neurocomputers:
Development, Application], 2010, No. 2, pp. 28-34.
13. Lebedev V.B. Postroenie kratchayshikh svyazyvayushchikh setey na osnove roevogo intellekta [Construction of the shortest connecting networks on the basis of swarm intelligence], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2011, No. 7 (120), pp. 37-44.
14. Lebedev B.K., Lebedev O.B. Modelirovanie adaptivnogo povedeniya murav'inoy kolonii pri poiske resheniy, interpretiruemykh derev'yami [Modelling of an ant colony adaptive behaviour by search of the decisions interpreted by trees], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 7 (132), pp. 27-35.
15. Lebedev V.B., Lebedev O.B. Roevoy intellekt na osnove integratsii modeley adaptivnogo povedeniya murav'inoy i pchelinoy koloniy [Swarm intelligence on the basis of the adaptive behaviour models integration of the ant and beer colonies], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 41-47.

Comments are closed.