© The Institution of Engineering and Technology
Even though enumeration is a common technique adapted in very large-scale integration (VLSI) floorplanning, its impact in terms of wirelength, whitespace, as well as runtime on the floorplanning has never been investigated comprehensively. In this study, enumerative floorplanner (EFP) is proposed here by using enumeration. The impact of the maximum enumeration order on VLSI floorplan layout is investigated and the tradeoff relationship with the wirelength, area and runtime is analysed as well. In EFP, dynamic programming enumerative clustering (DEC) technique is employed to reduce the worst-case time complexity and runtime. DEC also introduces the same number of possible permutations of modules while reducing the redundancy created in enumerative clustering (EC) without the usage of dynamic programming. A straightforward cost function is adapted to assist DEC to select the best cluster permutation, and a rigorous local refinement is proposed to compensate the EC's impact on the floorplan wirelength. Experimental results show that EFP is a high performance floorplanner when compared to existing methods in terms of robustness, scalability and stability.
References
-
-
1)
-
16. Valenzuela, C.L., Wang, P.Y.: ‘VLSI placement and area optimization using a genetic algorithm to breed normalized postfix expressions’, IEEE Trans. Evol. Comput., 2002, 6, (4), pp. 390–401 (doi: 10.1109/TEVC.2002.802872).
-
2)
-
2. Hoo, C.-S., Jeevan, K., Ganapathy, V., Ramiah, H.: ‘Variable-order ant system for VLSI multiobjective floorplanning’, Appl. Soft Comput., 2013, 13, (7), pp. 3285–3297 (doi: 10.1016/j.asoc.2013.02.011).
-
3)
-
12. Karypis, G., Kumar, V.: ‘Multilevel k-way hypergraph partitioning’. Proc. ACM/IEEE DAC, 1999, pp. 343–348.
-
4)
-
20. Banerjee, P., Sur-Kolay, S., Bishnu, A.: ‘Fast unified floorplan topology generation and sizing on heterogeneous FPGAs’, IEEE Trans. Comput.-Aid. Design Integr. Circuits Syst., 2009, 28, (5), pp. 651–661 (doi: 10.1109/TCAD.2009.2015738).
-
5)
-
5. Chen, T.-C., Chang, Y.-W.: ‘Modern floorplanning based on B*-trees and fast simulated annealing’, IEEE Trans. Comput.-Aid. Design Integr. Circuits Syst., 2006, 25, (4), pp. 637–650 (doi: 10.1109/TCAD.2006.870076).
-
6)
-
11. Yan, J.Z., Chu, C.: ‘SDS: an optimal slack-driven block shaping algorithm for fixed-outline floorplanning’, IEEE Trans. Comput.-Aid. Design Integr. Circuits Syst., 2013, 32, (2), pp. 175–188 (doi: 10.1109/TCAD.2012.2228304).
-
7)
-
14. Yeap, F.K.-H., Sarrafzadeh, M.: ‘A unified approach to floorplan sizing and enumeration’, IEEE Trans. Comput.-Aid. Design Integr. Circuits Syst., 1993, 12, (12), pp. 1858–1867 (doi: 10.1109/43.251149).
-
8)
-
27. Dunlop, A.E., Kerninghan, B.W.: ‘A procedure for placement of standard-cell VLSI circuits’, IEEE Trans. Comput.-Aid. Design Integr. Circuits Syst., 1985, 4, (1), pp. 92–98 (doi: 10.1109/TCAD.1985.1270101).
-
9)
-
26. Simon, H.D., Teng, S.H.: ‘How good is recursive bisection?’, SIAM J. Sci. Comput., 1997, 18, (5), pp. 1436–1445 (doi: 10.1137/S1064827593255135).
-
10)
-
10. Cong, J., Romesis, M., Shinnerl, J.R.: ‘Fast floorplanning by look-ahead enabled recursive bipartitioning’, IEEE Trans. Comput.-Aid. Design Integr. Circuits Syst., 2006, 25, (9), pp. 1719–2006 (doi: 10.1109/TCAD.2005.859519).
-
11)
-
9. Sassone, P.G., Lim, S.K.: ‘Traffic: a novel geometric algorithm for fast wire-optimized floorplanning’, IEEE Trans. Comput.-Aid. Design Integr. Circuits Syst., 2006, 25, (6), pp. 1075–1086 (doi: 10.1109/TCAD.2005.855921).
-
12)
-
13)
-
1. Adya, S.N., Markov, I.L.: ‘Fixed-outline floorplanning: enabling hierarchical design’, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 2003, 11, (6), pp. 1120–1135 (doi: 10.1109/TVLSI.2003.817546).
-
14)
-
7. Chen, S., Yoshimura, T.: ‘Fixed-outline floorplanning: Block-position enumeration and a new method for calculating area costs’, IEEE Trans. Comput.-Aid. Design Integr. Circuits Syst., 2008, 27, (5), pp. 858–871 (doi: 10.1109/TCAD.2008.917968).
-
15)
-
30. Wang, J., Zhou, H.: ‘Exploring adjacency in floorplanning’. Asia and South Pacific Design Automation Conf., 2009, pp. 367–372.
-
16)
-
17. Van Ginneken, L.P.P.P., Otten, R.H.J.M.: ‘Optimal slicing of plane point placements’. Proc. Eur. DAC, 1990, pp. 322–326.
-
17)
-
6. Chen, T.C., Chang, Y.W., Lin, S.C.: ‘A new multilevel framework for large-scale interconnect-driven floorplanning’, IEEE Trans. Comput.-Aid. Design Integr. Circuits Syst., 2007, 27, (2), pp. 286–294 (doi: 10.1109/TCAD.2007.907065).
-
18)
-
25. Hendrickson, B., Leland, R.: ‘An improved spectral graph partitioning algorithm for mapping parallel computations’, SIAM J. Sci. Comput., 1995, 16, (2), pp. 452–469 (doi: 10.1137/0916028).
-
19)
-
20)
-
21)
-
19. Dasgupta, P.S., Sur-Kolay, S., Bhattachary, B.B.: ‘A unified approach to topology generation and optimal sizing of floorplans’, IEEE Trans. Comput.-Aid. Design Integr. Circuits Syst., 1998, 17, (2), pp. 126–135 (doi: 10.1109/43.681262).
-
22)
-
15. Otten, R.H.J.M.: ‘Efficient floorplan optimization’. IEEE Int. Conf. Computer Design, 1983, pp. 499–502.
-
23)
-
4. Hoo, C.-S., Yeo, H.-C., Jeevan, K., Ganapathy, V., Ramiah, H., Badruddin, I.A.: ‘Hierarchical congregated ant system for bottom-up VLSI placements’, Eng. Appl. Artif. Intell., 2013, 26, (1), pp. 584–602 (doi: 10.1016/j.engappai.2012.04.007).
-
24)
-
18. Wang, T.-C., Wong, D.F.: ‘Optimal floorplan area optimization’, IEEE Trans. Comput.-Aid. Design Integr. Circuits Syst., 1992, 11, (8), pp. 992–1002 (doi: 10.1109/43.149770).
-
25)
-
13. Yan, J.Z., Chu, C.: ‘Defer: Deferred decision making enabled fixed-outline floorplanning algorithm’, IEEE Trans. Comput.-Aid. Design Integr. Circuits Syst., 2010, 29, (3), pp. 367–381 (doi: 10.1109/TCAD.2010.2041850).
-
26)
-
21. Lai, M., Wong, D.F.: ‘Slicing tree is a complete floorplan representation’. Proc. Design, Automation Test Eur. Conf. Exhibition, 2001, pp. 228–232.
-
27)
-
3. Roy, J.A., Adya, S.N., Papa, D.A., Markov, I.L.: ‘Min-cut floorplacement’, IEEE Trans. Comput.-Aid. Design Integr. Circuits Syst., 2006, 25, (7), pp. 1313–1326 (doi: 10.1109/TCAD.2005.855969).
-
28)
-
29. Kahng, A.B., Lienig, J., Hu, J.: ‘VLSI physical design: from graph partitioning to timing closure’ (Springer, 2011).
-
29)
-
30)
-
8. Ranjan, A., Bazargan, K., Ogrenci, S., Sarrafzadeh, M.: ‘Fast floorplanning for effective prediction and construction’, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 2001, 9, (2), pp. 341–351 (doi: 10.1109/92.924056).
-
31)
-
31. Li, Y., Li, Y., Zhou, M.: ‘A greedy algorithm for wire length optimization’. IEEE Int. Conf. Electronics, Circuits System, 2011, pp. 366–369.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cds.2013.0003
Related content
content/journals/10.1049/iet-cds.2013.0003
pub_keyword,iet_inspecKeyword,pub_concept
6
6