臺灣博碩士論文加值系統

電路導線的可繞度是現今數位電路實體設計的重要課題。在擺置階段不考慮可繞度，可能會使得繞線階段導線密度過高壅塞而無法成功繞線，甚至導致重新擺置、不斷重複擺置與繞線。另一項重要課題是障礙物，包括已決定好位置的巨集電路。過往的巨集電路擺置演算法能有效處理放在晶片邊緣的障礙物，卻無法有效率的處理非晶片邊緣的障礙物。有些類比電路擺置演算法能有效處理非晶片邊緣的障礙物，然而這些演算法無法直接套用在巨集電路擺置。以手動擺置作為靈感、結合角落縫合、角落序列與四元樹演算法，我們提出能有效同時處理邊緣障礙物與非邊緣障礙物的近似線性時間複雜度巨集電路擺置演算法，並能針對可繞度來最佳化擺置結果。因為擺置演算法保證巨集電路之間不會重疊，模擬退火能專注於從沒有重疊的擺置結果中尋找最佳解、因而提昇演算法速度。雖然實驗沒有完成、無法與過往演算法完整比較，但是實驗仍證實了本演算法在平均情況下呈線性的時間複雜度。

Routability of nets has become an important concern in modern digital circuit design. A placement solution with bad routability may cause congestion of nets and thus time is wasted in iterations between placement stage and routing stage. Another important concern in macro placement is blockage, or pre-placed macros. Previous works of macro placement handle boundary blockage well, but cannot cope with non-boundary blockage effectively. Though some works of analog placement are designed for non-boundary blockage, they cannot be applied to digital circuit design directly. By borrowing the concept of manual placement and integrating corner stitching, corner sequence and quadtrees together, the proposed method of this paper can deal with both boundary and non-boundary blockage effectively with average case linear time complexity, and at the same time keep good routability result for macro placement. Because the proposed method guarantees placing macros without overlap, simulated annealing can be sped up by focusing on finding the best result among valid solutions. However, experiments for comparing running time with previous works are not yet performed and thus the research of this paper is not complete.

Acknowledgements ii
Abstract (Chinese) iii
Abstract v
List of Tables ix
List of Figures x
Chapter 1. Introduction 1
1.1 Three-Stage Mixed-Size Placement 1
1.2 Previous Blockage-Aware Works 2
1.3 Motivation 6
1.4 Our Contributions 8
Chapter 2. Preliminaries 9
2.1 Review of Corner Sequence 9
2.2 Generalized Corner Sequence 10
2.3 Review of Corner Stitching 10
2.4 Extension of Corner Stitching 12
2.5 Review of Quadtree 12
2.6 Review of Routability-Aware Wirelength 13
2.7 Problem Formulation 14
Chapter 3. The Proposed Algorithm 15
3.1 The Central Idea 15
3.2 Placing Macros at Corners 18
3.2.1 De fining Corners by Corner Stitching 18
3.2.2 Querying Corners by Quadtrees 20
3.2.3 Checking Overlap by Corner Stitching 21
3.2.4 Updating Corner Stitching and Quadtrees 21
3.3 Rearranging Macros by Corner Sequence 22
3.4 Placement Cost Evaluation 23
3.5 Time Complexity 25
Chapter 4. Experimental Results 27
Chapter 5. Conclusions 30
5.1 Future Works 30
Bibliography 31

[1] Y.-C. Chang, Y.-W. Chang, G.-M. Wu, and S.-W. Wu, "B*-trees: A new representation for nonslicing
oorplans," Proc. ACM/IEEE Des. Autom. Conf., pp. 458--463, 2000.
[2] T.-C. Chen, P.-H. Yuh, Y.-W. Chang, F.-J. Huang, and T.-Y. Liu, "MP-trees: A packing-based macro placement algorithm for modern mixed-size designs," in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 9, pp. 1621--1634, 2008.
[3] Y.-F. Chen, C.-C. Huang, C.-H. Chiou, Y.-W. Chang, and C.-J. Wang, "Routability-driven blockage-aware macro placement," Design Automation Conference (DAC), 2014 51st ACM/EDAC/IEEE, pp. 1--6, 2014.
[4] C.-H. Chiou, C.-H. Chang, S.-T. Chen, and Y.-W. Chang, "Circular-contour-based obstacle-aware macro placement," 21th Asia and South Paci c Design Automation Conference, ASP-DAC 2016, pp. 172--177, 2016.
[5] R. A. Finkel and J. L. Bentley, "Quad trees: A data structure for retrieval on composite keys," Acta Informatica, vol. 4, no. 1, pp. 1--9, 1974.
[6] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by simulated annealing," Science, vol. 220, no. 4598, pp. 671--680, 1983.
[7] J.-M. Lin, Y.-W. Chang, and S.-P. Lin, "Corner sequence--a P-admissible floorplan representation with a worst case linear-time packing scheme," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 11, no. 4, pp. 679--686, 2003.
[8] J. K. Ousterhout, "Corner stitching: A data-structuring technique for VLSI layout tools," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. CAD-3, no. 1, pp. 87|-100, 1984.
[9] H.-F. Tsao, P.-Y. Chou, S.-L. Huang, Y.-W. Chang, M. P.-H. Lin, D.-P. Chen, and D. Liu, "A corner stitching compliant B*-tree representation and its applications to analog placement," International Conference on Computer-Aided Design (ICCAD), 2011 IEEE/ACM, pp. 507--511, 2011.
[10] I.-P. Wu, H.-C. Ou, and Y.-W. Chang, "QB-trees: Towards an optimal topological representation and its applications to analog layout designs," DAC ''16 Proceedings of the 53rd Annual Design Automation Conference, pp. 1--6, 2016.