Modified Ant Algorithm VLSI Planning on the Basis of the Composite Model of the Solution Space

In this paper, the crystal plan is formed by the recursive use of a "guillotine cut". To set the plan means to set the structure of the binary tree of the cuts, i.e. sequence of binary cuts; for internal tree vertices, to indicate the type of the cut H or V; to number the leaves of the tree and indicate the orientation of the modules. The structure of the binary tree of the cuts can be set using the Polish expression on the base of the alphabet A = {M, TR}, where the set of letters M = {m_i|i = 1, 2, ..., n_М} corresponds to the leaves of the section tree (regions), and the set R = {H, V} corresponds to the cuts. We propose a way and methods for solving the problems of planning VLSI based on a modified ant colony. The task of synthesizing the section tree of the plan with the choice of types of sections, identification and orientation of the modules in the work is reduced to the task of forming a modified Polish expression with the identification of elements on the composite model of the solution space, including many alternative vertices. To keep the collective evolutionary memory during the life of the ant population and to form the solution of the problem, we use the complete graph G = (X, U) with alternative vertex states. Each vertex may be in one of two alternative states, i.e., α or β, corresponding to the orientation of the module or the type of the cut. The task of synthesizing the Polish expression is formulated as the task of finding the least-cost route on the solution search graph G = (X, U). A distinctive feature is that when building a route, simultaneously with the choice of the vertex x_i∈ X, the state of this vertex is selected. The time complexity of the algorithm is O(n²). Experiments have shown that for large dimensions, the time indicators of the developed algorithm exceed those of the compared algorithms with the best values of the objective function

This work was supported by the Russian Foundation for Basic Research (RFBR grant no. 17-07-00997а)

References

[1] Kureichik V.M., Lebedev B.K., Lebedev V.B. VLSI floorplanning based on the integration of adaptive search models. J. Comput. Syst. Sci. Int., 2013, vol. 52, iss. 1, pp. 80--96. DOI: https://doi.org/10.1134/S1064230712060056

[2] Lebedev B.K., Lebedev O.B., Lebedev, V.B. Metody, modeli i algoritmy razmeshcheniya [Placement methods, models and algorithms]. Rostov-on-Don, SFeDU Publ., 2015.

[3] Lebedev O.B. Modeli adaptivnogo povedeniya muravinoy kolonii v zadachakh proektirovaniya [Adaptive behavior models of ant colony in design problems]. Rostov-on-Donu, SFeDU Publ., 2013.

[4] Qi L., Xia Y., Wang L. Simulated annealing based thermal-aware floorplanning. ICECC, 2011, pp. 463--466. DOI: 10.1109/ICECC.2011.6067654

[5] Chen J., Zhu W. A hybrid genetic algorithm for VLSI floorplanning. ICIS, 2010, pp. 128--132. DOI: 10.1109/ICICISYS.2010.5658785

[6] Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye prirodoy [Modern search optimization algorithms. Algorithms inspired by nature]. Moscow, BMSTU Publ., 2014.

[7] Chen G., Guo W., Chen Y. A PSO-based intelligent decision algorithm for VLSI floorplanning. Soft Comput., 2010, vol. 14, iss. 12, pp. 1329--1337. DOI: https://doi.org/10.1007/s00500-009-0501-6

[8] Banerjee P., Sangtani M., Sur-Kolay S. Floorplanning for Partially Reconfigurable FPGAs. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 2011, vol. 30, iss. 1, pp. 8--17. DOI: 10.1109/TCAD.2010.2079390

[9] Eroshenko I.N. The development of genetic algorithm for clustered floorplanning. Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2010, no. 7, pp. 54--60 (in Russ.).

[10] Lebedev B.K., Lebedev V.B. Planning on a basis swarm intelligence and genetic evolution. Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2009, no. 4, pp. 25--33 (in Russ.).

[11] Kureychik V.V., Kureychik V.V. The architecture of hybrid search for design. Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, no. 7, pp. 22--27 (in Russ.).

[12] Kureichik V.M., Lebedev B.K., Lebedev O.B. Hybrid evolutionary algorithm of planning VLSI. Proc. GECCO’10. Portland, OR, 2010, рр. 821--822.

[13] Lebedev B.K., Lebedev O.B. [Bioinspired methods for planning the VLSI crystal]. Problemy razrabotki perspektivnykh mikro- i nanoelektronnykh sistem (MES) [Problems of development of promising micro-and nanoelectronic systems], 2014, no. 1, pp. 171--176 (in Russ.).

[14] Lebedev O.B. Planning VLSI on the basis of the ant colony method. Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2010, no. 7, pp. 67--73 (in Russ.).

[15] Potti S., Pothiraj S. GPGPU implementation of parallel memetic algorithm for VLSI floorplanning problem. In: Nagamalai D., Renault E., Dhanuskodi M. (eds). Trends in Computer Science, Engineering and Information Technology. CCSEIT 2011. Communications in Computer and Information Science, vol. 204. Berlin, Heidelberg, Springer, pp. 432--441. DOI: https://doi.org/10.1007/978-3-642-24043-0_44

[16] Shanavas I.H. et al. Evolutionary algorithmical approach for VLSI floorplanning problem. IJCTE, 2009, vol. 1, no. 4, pp. 461--464. DOI: 10.7763/IJCTE.2009.V1.75

[17] Silvaco Library Platform™. Available at: http://www.nangate.com

[18] MCNC: company website. Available at: www.mcnc.org (accessed: 15.02.2019).

[19] hMetis. Available at: http://glaros.dtc.umn.edu/gkhome/metis/hmetis/download (accessed: 15.02.2019).

[20] HB Suite. cadlab.cs.ucla.edu: website. Available at: http://cadlab.cs.ucla.edu/cpmo/HBsuite.html (accessed: 15.04.2019).

[21] Ma Q., Young E.F.Y. Multivoltage floorplan design. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 2010, vol. 29, iss. 4, pp. 607--617. DOI: 10.1109/TCAD.2010.2042895

[22] Lebedev B.K., Lebedev O.B., Lebedeva E.M. Hybrid algorithm of situational trajectory planning under partial uncertainty. Herald of the Bauman Moscow State Technical University, Series Instrument Engineering, 2018, no. 1, pp. 76--93 (in Russ.). DOI: 10.18698/0236-3933-2018-1-76-93