考量固定大小框架面積之平面規劃為目前實體設計中必需考量之因素； 除此之外，在晶片上經常擺放著某些已經先行擺置之區塊，因此為了得到一個可用的平面規劃結果，一個好的平面規劃工具必需能同時滿足這些條件，這使得平面規劃的問題變得越來越困難。在這本碩士論文中，我們第一個提出能在固定框架平面規劃之中考量先行擺置區塊之方法，並且分別於全域分佈規劃和局部合理化統一使用凸面最佳化演算法以解決這個問題。在第一階段全域分佈規劃中，我們提出了一推拉模型(Push-Pull Model)將模組均勻分散在固定區域內並且同時減少整體之繞線長度；而在第二階段中，我們則會根據所得到模組之位置並利用Delaunary三角化方法，來擷取模組間之相對位置以建立出拓樸關係限制圖，以限制模組間能不相互重疊，最後再根據一個二次函數附加以固定邊界之限制，來決定區塊確實之位置與形狀。根據實驗的結果顯示，我們的方法在考慮了更複雜的設計限制條件下，仍能得到比目前文獻更佳之結果。

Fixed-outline floorplanning has attracted more attention for the real requirement in current IC design flow. In addition, there may exist several pre-placed modules in the specified region. In order to get a feasible foorplan, a floorplanner should have the ability to consider these constraints, which makes foorplanning a more difficult problem. In this thesis, we propose a it first work to consider pre-placed modules in a fixed-outline floorplan. Two-stages unified convex optimization methods, called UFO, are used in a global distribution and a local legalization stages, respectively. In the first stage, a pull-push model is used to distribute modules over a fixed outline under the wirelength consideration. In the second stage, the geometrical relations between modules are extracted by applying the Delaunay triangulation method on the result of the first stage. Then, a quadratic function as well as the constraint graphs are used to determine the locations and shapes of modules so that no module overlaps and all modules are in the outline. Experimental results have demonstrated that UFO clearly outperforms the results reported in the literature on the GSRC benchmarks.

[1] S. N. Adya and I. L. Markov. “Fixed-outline floorplanning: enabling hierarchical design.” IEEE TVLSI, Vol.11, No.6, pages 1120-1135, 2003.
[2] S. N. Adya, S. Chaturvedi, J. A. Roy, D. A. Papa and I. L. Markov.“Unification of partitioning, placement and floorplanning.” In Proc. of ICCAD, pages 550-557, 2004.
[3] M. F. Anjos and A. Vannelli. “A new mathematical-programming frame-work for facility-layout design.” INFORMS Journal on Computing, Vol.18, No.1, pages 111-118, 2006.
[4] Y.-C. Chang, Y.-W. Chang, G.-M. Wu, and S.-W. Wu. “B*-trees: A new representation for non-slicing floorplans.” In Proc. of DAC, pages 458-463, 2000.
[5] T.-C. Chen, Y.-W. Chang and S.-C. Lin. “IMF: interconnect-driven multilevel floorplanning for large-scale building-module designs.” In Proc. of ICCAD, pages 159-164, 2005.
[6] T. Chen and Y. W. Chang. “Modern floorplanning based on B*-tree and fast simulated annealing.” IEEE TCAD, Vol. 25, No. 4, pages 637-650, 2006.
[7] S. Chen and T. Yoshimura. “A stable fixed-Outline floorplanning method.” In Proc. ISPD, pages 119-126, 2007.
[8] Edwin K. P. Chong and Stanislaw H. ZAK. “An Introduction to Optimization.”John Wiley & Sons, Inc., second edition, 2001.
[9] J. Cong, M. Romesis, and J. Shinnerl. “Fast floorplanning by look ahead enabled recursive bipartitioning.” IEEE TCAD., Vol. 25, No. 9, pages
1719-1732, Sep. 2006.
[10] J. Cong, G. Nataneli, M. Romesis, and J. Shinnerl. “An area-optimality study of floorplanning.” In Proc. of ISPD, pages 78-83, 2004.
[11] Yan Feng, Dinesh P. Mehta , Hannah Yang. “Constrained modern floorplanning.” In Proc. of ISPD, pages 128-135, 2003.
[12] Yan Feng and Dinesh P. Mehta. “Constrained floorplanning using network flows.” IEEE TCAD, Vol. 23, No.4, APRIL 2004.
[13] P.-N. Guo, C.-K. Cheng, and T. Yoshimura. “An O-Tree representation of non-slicing floorplan and its applications.” In Proc. of DAC, pages 268-273, 1999.
[14] O. He, S. Dong, J. Bian, S. Goto, C.-K. Chen. “A novel fixed-outlined floorplanner with zero dead space for hierarcical design.” In Proc. of ICCAD, pages 16-23, 2008.
[15] 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. of ICCAD, pages 8-12, 2000.
[16] H. Itoga, C. Kodama and K. Fujuyoshi. “A Graph Based Soft Module Handling in Floorplan.”IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E88-A No.12, pages 3390-3397, 2005.
[17] L. Jin, D. Kim, L. Mu, D.-S. Kim and S.-M. Hu. “A sweepline algorithm for Euclidean Voronoi diagram of circules.” IEEE TCAD, Vol. 38, pages 260-272, 2006.
[18] A. B. Kahng. “Classical floorplanning harmful?” In Proc. of ISPD, pages 207-213, 2000.
[19] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi.”Optimization by simulated annealing.” Science, vol. 220, no. 4598, pages 671-680, 1983.
[20] C. Lin, D. Chen and Y. Wang. “Robust fixed-outline floorplanning through evolutionary search.” In Proc. of ASP-DAC, pages 42-44, 2004.
[21] J.-M Lin and Y.-W Chang. “TCG: A transitive closure graph-based representation for non-slicing floorplans.” In Proc. of DAC, pages 764-769, 2001.
[22] Chaomin Luo, Miguel F. Anjos, Anthony Vannelli. “Large-scale fixed-outline floorplanning design using convex optimization Techniques.” In Proc. of ASP-DAC, pages 198-203, 2008.
[23] R. Liu, S. Dong, X. Hong and Y. Kajitani. “Fixed-outline floorplanning with constraints through instance augmentation.” In Proc. of ISCAS, pages 1883-1886, 2005
[24] C. Lin, H. Zhou and C. C. N. Chu. “A Revisit to Floorplan Optimization by Lagrangian Relaxation.” In Proc. of ICCAD, pages 164-171, 2006.
[25] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani. “Rectangle-packing based module placement.” In Proc. of ICCAD, pages 472-479, Nov, 1995.
[26] T.-S. Moh, T.-S. Chang and S. L. Hakimi. “Globally optimal floorplanning for a layout problem.”IEEE TCS, Vol.43, No.9, pages 713-720,1996.
[27] S. Nakatake, K. Fujiyoshi, H. Murata, and Y.Kajitani. “Module placement on BSG-structure and IC layout applications.” In Proc. of ICCAD, pages 484-491, 1996.
[28] R.H.J.M. Otten. “Automatic floorplan design.” In Proc. of DAC, pages 261-267, June 1982.
[29] D. F. Wong, and C.-L. Liu. “A new algorithm for floorplan design.” In Proc. of DAC, pages 101-107, June 1986.
[30] Jackey Z. Yan and Chris Chu. “DeFer: Deferred decision making enabled fixed-outline floorplanner.” In Proc. of DAC, pages 161-166, June 2008.
[31] H. Zhou and J. Wang., “Acg. adjacent constraint graph for general floorplans,” In Proc. of ICCD, pp. 572-575, 2004.
[32] Y. Zhan, Y. Feng and S. Sapatnekar. “A fixed-die floorplanning algorithm using an analytical approach." In Proc. of ASP-DAC, pages 771-776, 2006.