|Article title||MODERNIZED ANT MARK ALGORITHM FOR THE SYNTHESIS OF THE IDENTIFIED TREE OF THE GUILOTE SECTION IN VLSI PLANNING|
|Authors||B. K. Lebedev, O. B. Lebedev, E. M. Lebedeva|
|Section||SECTION I. DESIGN AUTOMATION|
|Month, Year||07, 2017 @en|
|Abstract||The planning task is solved on the basis of the modified canonical paradigm of the ant colony. To represent the plan, a binary tree of the guillotine cut with identified vertices is used. The structure of the tree of cuts is given in the form of a Polish expression for a binary tree. The basic properties of the Polish expression are formulated, the execution of which is necessary so that the records correspond to the tree of cuts. In this paper we consider the approach in which the formation of the tree structure of the sections by the ant algorithm and the marking of all tree vertices is carried out in parallel. The task of synthesizing a cut tree with vertex identification is reduced to the task of forming the corresponding Polish expression. To reflect the collective evolutionary memory during the lifetime of the ant population and to form the solution of the problem, a complete graph with alternative states of vertices is used in the work. The vertices of the set X1 correspond to the set of modules M. Each vertex can be in one of two alternative states corresponding to the type of orientation of the module. The vertices of the set X2 correspond to cuts. Each vertex can be in one of two alternative states, corresponding to the type of cut - horizontal or vertical. The key problem that has been solved in this paper is related to the development of a composite structure of the solution space that allows you to simultaneously take into account the orientation of the elements, the cut type and the module label when constructing the tree of sections. The structure of the modified Polish expression allowing us to take into account the orientation of the elements, the type of the cut and the label of the module is developed. This helped to reduce the time complexity of the planning task and improve the quality of the solution. The process of finding solutions is iterative. Each iteration l consists of three steps. At the first stage, the ant finds a solution. Developed heuristics of the ant"s behavior when moving in the solution search graph, allowing to form a legitimate route. In the second stage, the ants lay pheromone, in the third stage the pheromone is evaporated. The agent"s route is transformed into a Polish expression, which in turn is transformed into a tree of cuts with identified vertices, and the tree of cuts is transformed into a plan. The C ++ programming language was used in the Microsoft Visual Studio 2010 environment for Windows with the method of ant colony, because the main emphasis was on the speed of the application. For the experiments of the program, a procedure was used to synthesize test cases with the known optimum Fopt, in analogy with the known method AFEKO – Floorplanning Examples with Known Optimal area. The study was subjected to examples containing up to 1000 modules. Quality assessment is the "quality level" – the value of Fopt/F, where F is the estimate of the solution obtained. Comparison with known algorithms has shown that, with a shorter working time, the deviation of the objective function from the optimal value obtained by the developed algorithm is less by an average of 6 %. The time complexity of this algorithm depends on the lifetime of the colony l (the number of iterations), the number of vertices of the graph n, and the number of ants m, and is defined as O(l∙n2∙m).|
|Keywords||Blocks; planning; tree of cuts; Polish expression; synthesis; alternative; paradigm; ant al-gorithm.|
|References||1. Kahng A.B. Classical Floorplanning Harmful, ISPD 2000, pp. 207-213.
2. Lin C.-T. et al. GPE: A New Representation for VLSI Floorplan Problem, IEEE International Conference on Computer Design (ICCD'02), 2002,Ppp 42-44.
3. Sengupta D. et al. Sequence pair based voltage island floorplanning, IEEE International Green Computing Conference, 2011, pp. 1-6.
4. Nakatake S. et al. The channeled-BSG: a universal floorplan for simultaneous place/route with IC applications, International Conference on Computer-Aided Design, November 8-12, 1998, pp. 418-425.
5. Guo P.N. Floorplanning Using a Tree Representation, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, February 2001, Vol. 20, No. 2, pp. 281-289.
6. Nirmala R.D.G., Rajaram S. Performance Driven VLSI Floorplanning with B*Tree Represen-tation Using Differential Evolutionary Algorithm, Trends in Network and Communications in Computer and Information Science, 2011, Vol. 197, Part 2, pp. 445-456.
7. Wang R. et al. An Improved P-admissible Floorplan Representation Based on Corner Block List, Proceedings of the 2005 Asia and South Pacific Design Automation Conference, 2005, pp. 1115-1118.
8. Lin J.-M., Chang Y.-W. TCG: A Transitive Closure Graph-Based Representation for Non-Slicing Floorplans, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Feb-ruary 2005, Vol. 13, Issue 2, pp. 288-292.
9. Sassone T.P.G. and Lim S.K. A novel geometric algorithm for fast wire-optimized floorplanning, In Proc. Int. Conf. Comput. Aided Design, 2003, pp. 74-80.
10. Lai M., and Wong D.F. Slicing Tree Is a Complete Floorplan Representation, In Proc. DATE, 2001, pp. 228-232.
11. Cheng L., Wong D.F. Floorplan Design for Multi-million Gate FPGAs, DAC, 2004, pp. 292-313.
12. Fang J.-P. et al. A Parallel Simulated Annealing Approach for Floorplanning in VLSI, Pro-ceedings of the 9th International Conference on Algorithms and Architectures for Parallel Processing, 2009, pp. 291-302.
13. Qi L. et al. Simulated annealing based thermal-aware floorplanning, International Conference on Electronics, Communications and Control (ICECC), 2011, pp. 463-466.
14. Young F.Y. et al. Slicing floorplans with boundary constraints, IEEE Transactions on Comput-er-Aided Design, 1999, pp. 1385-1389.
15. Chen T.-C., Chang Y.-W., and Lin S.-C. A new multilevel framework for large-scale intercon-nect-driven floorplanning, IEEE Trans. Comput.-Aided Design Integrat. Circuits Syst., 2008, Vol. 27, No. 2, pp. 286-294.
16. Singhal L. and Bozorgzadeh E. Multilayer floorplanning for reconfig¬urable designs, IET Comput. Digit. Tech., 2007, Vol. 1, No. 4, pp. 276-294.
17. Pritha Banerjee, Megha Sangtani, and Susmita Sur-Kolay. Floorplanning for Partially Recon-figurable FPGAs, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 2011, Vol. 30,
No. 1, pp. 8-17.
18. Chuan-Wen Chiang. Ant Colony Optimization for VLSI Floorplanning with Clustering Con-straints, Journal of the Chinese Institute of Industrial Engineers, 2009, Vol. 26, Issue 6,
19. Lin C.-T. et al. An efficient genetic algorithm for slicing floorplan area optimization, Proceed-ings of the International Symposium on Circuits and Systems, 2002, pp. 879-882.
20. Chen J., Zhu W. A hybrid genetic algorithm for VLSI floorplanning, IEEE International Con-ference on Intelligent Computing and Intelligent Systems (ICIS), 2010, pp. 128-132.
21. Shanavas .I H. et al. Evolutionary Algorithmical Approach for VLSI Floorplanning Problem, International Journal of Computer Theory and Engineering, 2009, Vol. 1, No. 4, pp. 461-464.
22. Lebedev B.K., Lebedev V.B. Planirovanie SBIS na osnove evolyutsionnoy adaptatsii [Planning VLSI on the basis of evolutionary adaptation], Izvestiya TRTU [Izvestiya TSURE], 2006,
No. 9 (64), pp. 93-97.
23. Kureychik V.M., Lebedev B.K., Lebedev V.B. Planirovanie sverkhbol'shikh integral'nykh skhem na osnove integratsii modeley adaptivnogo poiska [Planning of super large integral schemes based on integration of adaptive search models], Izvestiya RAN. Teoriya i sistemy upravleniya [Izvestiya RAN. Theory and Control Systems], 2013, No. 1, pp. 84-101.
24. Tang, Maolin and Yao, Xin. A memetic algorithm for VLSI floorplanning, IEEE Transactions On Systems, Man, And Cybernetics – Part B: Cybernetics, 2007, Vol. 37 (1).
25. Lebedev B.K., Lebedev O.B. Bioinspirirovannye metody planirovaniya kristalla SBIS
[A memetic algorithm for VLSI floorplanning], MES-2014. VI Vserossiyskaya nauchno-tekhnicheskaya konferentsiya «Problemy razrabotki perspektivnykh mikro- i nanoelektronnykh sistem - 2014»: Sbornik trudov [MES-2014. VI All-Russia scientific and technical conference "Problems of development of promising micro- and nanoelectronic systems - 2014". Collection of works]. Moscow: IPPM RAN, 2012, pp. 171-176.
26. Alpert C.J. In Proceeding of the International Symposium on Physical Design, The ISPD98 circuit benchmark suite, 1998, pp. 85-90.
27. Cong J., Romesis M. и Xie M. UCLA Optimality Study Project. Available at: http://cadlab.cs.ucla.edu/~pubbench. 2004.
28. MCNC Electronic and Information Technologies (Online). Available at: www.mcnc.org.
29. hMetis [Online]. Available at: http://www-users.cs.umn.edu/karypis/metis/ hmet300. HB Floorplan Benchmarks [Online]. Available at: http://cadlab.cs.ucla.edu/ cpmo/HBsuite.html.