The module placement problem is to determine the co-ordinates of logic modules in a chip such that no two modules overlap and some cost (e.g. silicon area, interconnection length, etc.) is optimised. To shorten connections between inputs and outputs and/or make related modules adjacent, it is desired to place some modules along the specific boundaries of a chip. To deal with such boundary constraints, we explore the feasibility conditions of a B*-tree with boundary constraints and develop a simulated annealing-based algorithm using B*-trees. Unlike most previous work, the proposed algorithm guarantees a feasible B*-tree with boundary constraints for each perturbation. Experimental results show that the algorithm can obtain a smaller silicon area than the most recent work based on sequence pairs.
References
-
-
1)
-
Ma, Y., Dong, S., Hong, X., Cai, Y., Cheng, C.-K., Gu, J.: `VLSI floorplanning with boundary constraints based on corner block list', Proceedings of Asia and South Pacific Design Automation Conference, ASP-DAC’01, Jan. 2001, Yokohama, Japan, p. 509–514.
-
2)
-
Guo, P.-N., Cheng, C.-K., Yoshimura, T.: `An O-tree representation of non-slicing floorplan and its applications', Proceedings of 36th Design Automation Conference, DAC’99, June 1999, LA, CA, USA, p. 268–273.
-
3)
-
Tang, X., Wong, D.F.: `FAST-SP: A fast algorithm for block placement based on sequence pair', Proceedings of Asia and South Pacific Design Automation Conference, ASP-DAC’01, Jan. 2001, Yokohama, Japan, p. 521–526.
-
4)
-
Nakatake, S., Fujiyoshi, K., Murata, H., Kajitani, Y.: `Module placement on BSG-structure and IC layout applications', Proceedings of International Conference on Computer aided design, ICCAD’96, Nov. 1996, CA, USA, p. 484–491.
-
5)
-
Wong, D.F., Liu, C.L.: `A new algorithm for floorplan design', Proceedings of 23rd Design Automation Conference, DAC’86, June 1986, USA, p. 101–107.
-
6)
-
Otten, R.H.J.M.: `Automatic floorplan design', Proceedings of 19th Design Automation Conference, DAC’82, June 1982, USA, p. 261–267.
-
7)
-
Lin, J.-M., Chang, Y.-W.: `TCG: A transitive closure graph-based representation for non-slicing floorplans', Proceedings of 38th Design Automation Conference, DAC’01, June 2001, NV, USA, p. 764–769.
-
8)
-
Hong, X., Huang, G., Cai, T., Gu, J., Dong, S., Cheng, C.-K., Gu, J.: `Corner block list: An effective and efficient topological representation of non-slicing floorplan', Proceedings of International Conference on Computer aided design, ICCAD’00, Nov. 2000, CA, USA, p. 8–12.
-
9)
-
Lai, J., Lin, M.-S., Wang, T.-C., Wang, Li.-C.: `Module placement with boundary constraints using the sequence-pair representation', Proceedings of Asia and South Pacific Design Automation Conference, ASP-DAC’01, Jan. 2001, Yokohama, Japan, p. 515–520.
-
10)
-
Murata, H., Fujiyoshi, K., Nakatake, S., Kajitani, Y.: `Rectangle-packing based module placement', Proceedings of International Conference on Computer aided design, ICCAD’95, Nov. 1995, CA, USA, p. 472–479.
-
11)
-
Young, F.Y., Wong, D.F.: `Slicing floorplans with boundary constraint', Proceedings of Asia and South Pacific Design Automation Conference, ASP-DAC’99, Feb. 1999, Yokohama, Japan, p. 17–20.
-
12)
-
S. Kirkpatrick ,
C.D. Gelatt ,
M.P. Vecchi
.
Optimization by simulated annealing.
Science
,
4598 ,
671 -
680
-
13)
-
Chang, Y.-C., Chang, Y.-W., Wu, G.-M., Wu, S.-W.: `B*-Trees: A new representation for non-slicing floorplans', Proceedings of 37th Design Automation Conference, DAC’00, June 2000, CA, USA, p. 458–463.
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-cds_20020433
Related content
content/journals/10.1049/ip-cds_20020433
pub_keyword,iet_inspecKeyword,pub_concept
6
6