Algorithms for packing soft blocks of VLSI systems

• Autorzy: Iwaniec M. , Janiak A.
• Języki publikacji: EN

Abstrakty

EN

This paper contains a review of literature concerning the packing of hard-blocks (of fixed dimensions) and soft-blocks (of fixed area – changeable within specified constraints). These considerations are applicable to the designing of large scale integration chips. In order to solve the problem of packing soft-blocks, three algorithms are introduced and compared: simulated annealing, heuristic constructional algorithm based on five operations to improve packing quality and the algorithm which combines two previous algorithms. Experiments were conducted to compare these algorithms to the best from the literature.

Słowa kluczowe

EN

soft-blocks; hard-blocks; VLSI; packing problem

• Wydawca: Łukasiewicz Industrial Research Institute for Automation and Measurements PIAP
• Czasopismo: Journal of Automation Mobile Robotics and Intelligent Systems
• Rocznik: 2013
• Tom: Vol. 7, No. 3
• Strony: 37--42
• Opis fizyczny: Bibliogr. 32 poz., rys.

Twórcy

autor

Iwaniec M.

• Institute of IT, Automated Control Engineering and Robotics, Wrocław University of Technology, Z. Janiszewskiego 11/17, 50-372 Wrocław, Poland

autor

Janiak A.

• Institute of IT, Automated Control Engineering and Robotics, Wrocław University of Technology, Z. Janiszewskiego 11/17, 50-372 Wrocław, Poland

Bibliografia

• [1] Chan H., Markov I., “Practical slicing and nonslicing block-packing without simulated Annealing”, In: Proc. Great Lakes Symposium on VLSI (GLSVLSI), 2004, pp. 282–287.
• [2] Chen T.C., Chang Y.W., Lin S.C., “IMF: Interconnectdriven multilevel floorplanning for large-scale building-module designs. In: Proc. ICCAD'05, ACM/IEEE, 2005, pp. 159–164.
• [3] Chen T.C., Chang Y.W. Modern floorplanning based on B*-tree and fast simulated Annealing”, IEEE Trans. on CAD, vol. 25, no. 4, 2006, pp. 637–650.
• [4] Chen S., Yoshimura T., “Fixed-outline floorplanning: block-position enumeration and a ew method for calculating area costs”, IEEE Trans. Computer – Aided Des. Integrated Circuits Syst., vol. 27, no. 5, 2008, pp. 858–871.
• [5] Chen J., Zhu W., Ali M.M., “A hybrid simulated annealing algorithm for nonslicing VLSI floorplanning”, IEEETrans. Syst., Man, and Cybernetics, Part C: Appl. Rev., vol. 41, no. 4, 2011, pp. 544–553.
• [6] Chiang C.W., “Ant colony optimization for VLSI floorplanning with clustering constraint”, J. Chin. Inst. Ind. Eng., vol. 26, no. 6, 2009, pp. 440–448.
• [7] Hayes J.P., Murray B.T., Testing ICs: getting to the core of the problem, IEEE Computer Magazine, no. 11, 1996, pp. 32–38.
• [8] Itoga H., Kodama C., Fujiyoshi K., “A graph based soft module handling in floorplan”, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., E88-A(12), 200, 5, pp. 3390–3397.
• [9] Janiak A., Kozik A., Lichtenstein M., “New perspectives in VLSI design automation: deterministic packing by Sequence Pair”, Annals of Operations Research, Springer Netherlands, 179, 2010, pp. 35–56
• [10] Kang M., Dai W.-M., “General floorplanning with lshaped, t-shaped and soft blocks based on bounded slicing grid structure”. In: Design Automation Conference 1997. Proceedings of the ASP-DAC ’97. Asia and South Pacific, 1997, pp. 265–270.
• [11] Kirkpatrick S., Gelatt C., Vecchi M., “Optimization by Simulated Annealing”, Science, no. 220(4598), 1983.
• [12] Liu J., Zhong W.C., Jiao L.C., Li X., “Moving block sequence and organizational evolutionary algorithm for general floorplanning with arbitrarily shaped rectilinear blocks”, IEEE Trans. Evol. Comput., vol. 12, no. 5, 2008, pp. 630–646.
• [13] Ma Y., Hong X., Dong S., Cai Y., Cheng C.-K., Gu J., Floorplanning with abutment constraints based on corner block list, Integration, the VLSI Journal, 31(1), 2001, pp. 65–77.
• [14] Murata H., Fujiyoshi K., Nakatake S., Kajitani Y., “VLSI module placement based on rectanglepacking by the sequence pair”, IEEE Transaction on Computer Aided Design of Integrated Circuits and Systems, vol. 15, no. 12, 1996.
• [15] Otten R.H.J.M., van Ginneken L.P.P.P., “Floorplan design using simulated annealing”. In: Proc. Intl. Conf. on CAD, 1984, pp. 96–98.
• [16] Rebaudengo M., Reorda M.S., “GALLO: genetic algorithm for floorplan area optimization”, IEEE Trans. Comput. – Aided Des. Integrated Circuits Syst., vol. 15, no. 8, 1996, pp. 943–951.
• [17] Valenzuela C.L., Wang P.Y., “VLSI Placement and Area Optimization Using a Genetic Algorithm to Breed Normalized Postfix Expressions”, IEEE Transactions on Evolutionary Computation, vol. 6, no. 4, 2002, pp. 390–401.
• [18] Wang H.Y., Hu K., Liu J., Jiao L.C., „Multiagent evolutionary algorithm for floorplanning using moving block sequence”, IEEE Congr. Evol. Comput., 2007, pp. 4372–4377.
• [19] Wong D.F., Liu C.L., “A new algorithm for floorplan design”. In: Proc. Design Autom. Conf., 1986, pp. 101–107.
• [20] Xiaoping T., Ruiqi T., Wong D.F., “Fast evaluation of sequence pair in block placement by longest common subsequence computation”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 20, no. 12,2001, pp. 1406–1413.
• [21] Xiong E.S.J., Wong Y.-C., He L., “Constraint driven i/o planning and placement for chip-package codesign”. In: Proc. Asia and South Pacific Design Autom. Conf., 2006, pp. 207–212.
• [22] Yang S., Logic synthesis and optimization benchmarks, Microelectronics Center of North Carolina, Research Triangle Park, N.C., Tech., 1991.
• [23] Young F., Chu C., Luk W., Wong Y., “Handling soft modules in general nonslicingfloorplan using lagrangian relaxation”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 20, no. 5, 2001, pp. 687–692.