在這本碩士論文中，我們提出了一種可以應用於不可分割區塊
之平面規劃表示法稱為SKB-tree。因為SKB-tree它能動態的分配區域來擺置不同之區塊，所以它是一種適合用來處理具有固定框架
(Fixed-Outline)限制之平面規劃表示法。不同於其它的表示法，在執行模擬退火(Simulated Annealing)之目標函數，我們只需要考慮線長而不必加入限制區塊空間之項目，因此SKB-tree可以獲得比其它方法較好之結果。由於SKB-tree之良好特性，我們將它運用於電壓島(Voltage Island)之平面規劃。有別於以往電壓島的平面規劃設計，為了節省電源網線的繞線資源，簡化電源線規劃流程，以及減少IR Drop，這本論文中我們限制操作在相同工作電壓下之區塊必須被群聚在一起。根據實驗結果證明，SKB-tree是可以非常有效處理固定框架平面規劃問題之表示法，它與A-FP，Parquet4.0，ZDS與SAFFOA在框架長寬比為1:1 之實驗結果比較，可分別達成39.8%，49.4%，25.6%以及18.4%之平均線長改善率。而在不同長寬比之框架平面規劃結果相比較，我們的方法仍然比A-FP和SAFFOA具有較好的平均線長改善率。另外，在電壓島平面規劃的實驗結果中，我們的方法與Ma 和Young [23]的方法做比較，仍可得到比其少14.7%的功率消耗以及18.5%的線長改善率。

In this thesis, we propose an SKB-tree representation for non-slicing floorplanning. Since SKB-tree dynamically allocates regions for a set of blocks, all
blocks can be placed into a specify outline for each solution, which makes it become a suitable representation for dealing with the fixed-outline constraint.
More importantly, because it does not need to add an additional term in the cost function for the constraint, it can get better results than other representations.
Due to this good property, we also use it to deal with the voltage-island driven floorplanning. In order to save power routing resource, simplify power planning, and reduce IR Drop, we constrain blocks of the same voltage to
be placed into a continuous locations unlike most works do not have these constraints. Experimental results show the promise of SKB-tree. For the fixed-outeline constraint with the aspect ratio 1:1, SKB-tree achieved average
improvements in wirelength of 39.8%, 49.4%, 25.6%, and 18.4% better than A-FP, Parquet 4.0, ZDS, and SAFFOA, respectively. Compared to the floorplans with other aspect ratios, our method is also better than A-FP and SAFFOA.
For voltage island driven floorplanning, SKB-tree can also take 14.7% and 18.5% less power consumption and wirelength than Ma and Young [23].

[1] S. N. Adya and I. L.Markov, “Fixed-outline floorplanning through better local search,” In Proc. ICCD, pp. 328-334, 2001.
[2] S. N. Adya and I. L. Markov, “Fixed-outline floorplanning: enabling hierarchical design,” In IEEE Trans. on VLSI Systems, vol 11(6), pp.1120-1135, December 2003.
[3] Y.-C. Chang, Y.-W. Chang, G.-M. Wu, and S.-W. Wu, “B*-Trees: a new representation for non-slicing floorplans,” In Proc. DAC, pp. 458-463, 2000.
[4] T.-C. Chen, Y.-W. Chang and S.-C. Lin, “IMF: interconnect-driven multilevel floorplanning for large-scale building-module designs,” In Proc. ICCAD, pp. 159-164, 2005.
[5] R.L.S. Ching and E.F.Y. Young, “Post-placement voltage island generation,” In Proc. ICCAD, pp. 641-646, 2006.
[6] J. Cong, M. Romesis, and J. Shinnerl. “Fast floorplanning by look-ahead enabled recursive bipartitioning,” In IEEE Trans. on CAD, vol 25(9),
pp.1719-1732, September, 2006.
[7] J. Cong, G. Nataneli, M. Romesis, and J. Shinnerl. “An area-optimality study of floorplanning,” In Proc. ISPD, pp. 78-83, 2004.
[8] P.-N. Guo, C.-K. Cheng, and T. Yoshimura, “An O-Tree representation of non-slicing floorplan and its applications,” In Proc. DAC, pp. 268-273, 1999.
[9] X. Hong, G. Huang, Y. Cai, J. Gu, S. Dong, C.-K. Cheng, and J. Gu,“Corner Block List: An effective and efficient topological representation of non-slicing floorplan,” In Proc. ICCAD, pp. 8-12, 2000.
[10] J. Hu, Y. Shin, N. Dhanwada, and R. Marculescu, “Architecting voltage islands in core-based system-on-a-chip designs,” In Proc. ISLPED, pp.180-185, 2004.
[11] W.-L. Hung, G.M. Link, Y. Xie, N. Vijaykrishnan, N. Dhanwada and J.Conner, “Temperature-aware voltage islands architecting in system-on-chip design,” in Proc. ICCD, pp. 689-696, 2005.
[12] A. B. Kahng, “Classical floorplanning harmful?,” In Proc. ISPD, pp.207-213, 2000.
[13] S.Kirkpatrick,C.D.Gelatt, and M.P.Vecchi,“Optimization by simulated annealing,” In Science, vol. 220, no. 4598, pp. 671-680, May 1983.
[14] D. E. Lackey, P. S. Zuchowski, T. R. Bednar, D.W. Stout, S.W. Gould, and J .M. Cohn,“Managing power and performance for system-on-chip designs using voltage islands,” In Proc. ICCAD , pp. 195-202, 2002.
[15] J.-M Lin and Y.-W Chang, “TCG: A transitive closure graph-based representation for non-slicing floorplans,” In Proc. DAC, pp. 764-769, 2001.
[16] W.-P. Lee, H.-Y. Liu, and Y.-W. Chang, “Voltage island aware floorplanning for power and timing optimization,” In Proc. ICCAD, pp. 389-394, 2006.
[17] W.-P. Lee, H.-Y. Liu and Y.-W. Chang, “An ILP algorithm for post-floorplanning voltage-island generation considering power-network planning,” In Proc. ICCAD, pp. 650-655, 2007.
[18] Jai-Ming Lin, Huai-En Yi, and Yao-Wen Chang, “Module placement with boundary constraints using B*-trees,” In IEE Proceedings–Circuits, Devices and Systems, vol. 149, No. 4, pp. 251-256, August 2002.
[19] C.-T. Lin, D.-S. Chen, and Y.-W. Wang, “Robust fixed-outline floorplanning through evolutionary search,” In Proc. ASP-DAC, pp. 42-44, 2004.
[20] P.-H. Lin and S.-C. Lin, “Analog placement based on novel symmetry-island formulation,” In Proc. DAC, pp. 465-470, 2007.
[21] B. Liu, Y. Cai, Q. Zhou, and X. Hong, “Power driven placement with layout aware supply voltage assignment for voltage island generation in dual-vdd designs,” In Proc. ASP-DAC, pp. 582-587, 2006.
[22] H. Liu, W. Lee and Y. Cheng, “A provably good approximation algorithm for power optimization using multiple supply voltages,” In Proc. DAC, pp. 887-890, 2007.
[23] Q.Ma and E.F.Y. Young, “Voltage island-driven floorplanning,” In Proc. ICCAD, pp. 644-648, 2007.
[24] W.-K. Mak and J.-W. Chen, “Voltage island generation under performance requirement for SoC designs,” In Proc. ASP-DAC, pp. 798-803, 2007.
[25] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, “Rectangle packing based module placement,” In Proc. ICCAD, pp. 472-479, 1995.
[26] S. Nakatake, K. Fujiyoshi, H. Murata, and Y. Kajitani, “Module placement on BSG-structure and IC layout applications,” In Proc. ICCAD, pp. 484-491, 1996.
[27] Ruchir Puri, Leon Stok, John Cohn, David Kung, David Pan, Dennis Sylvester, Ashish Srivastava, Sarvesh Kulkarni, “Pushing ASIC performance in a power envelope,” In Proc. DAC, pp. 788-793, 2003.
[28] Ruchir Puri, David Kung, Leon Stok, “Minimizing power with flexible voltage islands,” In Proc. ISCAS, pp. 21-24, 2005.
[29] D. Sengupta, R. Saleh,“Application-driven floorplan-aware voltage island design,” In Proc. DAC, pp. 155-160, 2008.
[30] R.H.J.M. Otten, “Automatic floorplan design,” In Proc. DAC, pp. 261-267, 1982.
[31] Ou He, S. Dong, J. Bian, S. Goto, C-K Cheng, “A novel fixed-outline floorplanner with zero deadspace for hierarchical design,” In Proc. ICCAD, pp. 16-23, 2008.
[32] John G. Spooner,“Chip designers voyage voltage island,”http://news.com.com/Chip designers voyage to voltage island/2100-1001 3-934355.html, 2002.
[33] D. F. Wong, and C.-L. Liu, “A new algorithm for floorplan design,” In Proc. DAC, pp. 101-107, 1986.
[34] H. Wu, I.M. Liu, D.F. Wong, and Y. Wang, “Post-placement voltage island generation under performance requirement,” In Proc. ICCAD, pp. 309-316, 2005.
[35] H. Wu, D.F. Wong, and I.-M. Liu, “Timing-constrained and voltage-island-aware voltage assignment,” In Proc. DAC, pp. 429-432, 2006.
[36] Jackey Z. Yan and Chris Chu, “DeFer: Deferred decision making enabled fixed-outline floorplanner,” In Proc. DAC, pp. 161-166, 2008.
[37] H. Zhou and J. Wang., “Acg. adjacent constraint graph for general floorplans,” In Proc. ICCD, pp. 572-575, 2004.
[38] Y. Zhan, Y. Feng and S. Sapatnekar. “A fixed-die floorplanning algorithm using an analytical approach.” In Proc. ASP-DAC, pp. 771-776, 2006.