隨著製程技術進步到深次微米時代，連線對電路效能及訊號完整性而言，扮演著重要的角色。而製程的進步，使得電路元件尺寸及元件之間的間隔大小日益縮減，造成電路間的耦合電容日漸增加，由串音(Crosstalk)所引起的雜訊問題的也愈來愈受到重視。緩衝器的使用，是現有技術中用來降低連線延遲及處理耦合電容效應最有效而且普遍的方法。在傳統超大型積體電路設計流程中，通常在電路佈局(layout)後才會利用緩衝器來處理連線的各種問題; 然而，由於緩衝器數目之需求可能高達數十萬，但是在電路經佈局後，大部份可用區域都巳被連線所佔據，使得可插入緩衝器的空間大為受限。因此，將緩衝器規劃的步驟由傳統電路佈局後提前至平面設計階段中是有其必要性的。在此論文中，我們首先推導出利用緩衝器來達成時間延遲以及降低雜訊最佳化之公式，接著應用此公式來計算同時滿足時間延遲與雜訊兩種限制的可行的區域(feasible regions)，以供規劃緩衝器時使用，為了取得更好的效能，我們將緩衝器規劃整合到平面規劃中，同步對面積、時序、雜訊及壅塞做最佳化的運算。而在平面規劃後，我們應用Lagrangian relaxation 來對面積做進一步地改善。根據實驗結果，我們的方法只增加了0.1%(0.2%)面積的代價，而使得94.9%(86.4%)的連線可以成功地滿足時序限制(時序及雜訊的限制); 相較之下，先前的研究BBP/FR [6]並未考量雜訊限制，且在效能上所達成之成功率僅為72.8%，同時付出額外1.03%面積的代價。

As the process technology advances into the deep submicron
era, interconnect plays a dominant role in optimizing circuit
performance and signal integrity. Crosstalk-induced noise has been attracting increasing attention when technology improves, spacing diminishes and coupling capacitance increases. Buffer insertion is one of the most effective and popular techniques to reduce interconnect delay and decouple coupling effects. It is traditionally applied to post-layout optimization. However, it is obviously infeasible to insert hundreds of thousands buffers during the post-layout stage when most routing regions are occupied. Therefore, it is desirable to incorporate buffer
planning into floorplanning to ensure timing closure and design
convergence. In this thesis, we first derive formulae of buffer
insertion for both timing and noise optimization, apply
these formulae to compute the feasible regions for inserting
buffers to meet both timing and noise constraints, cluster buffers into blocks in their feasible regions, and then integrate buffer planning with floorplanning to optimize area, timing, noise, and congestion (routability) simultaneously. In particular, we treat each buffer block as a soft module and apply Lagrangian relaxation to optimize the floorplan area. Experimental results shows the effectiveness of our algorithms.

chapter 1 Introdution
1.1 introduction
1.2 buffer insertion for timing optimization
1.2.1 post-layout buffer insertion
1.2.2 buffer block planning
1.2.3 buffer site distribution
1.3 buffer insertion for timing and noise optimization
1.4 organization of the thesis
chapter 2 Preliminaries
2.1 delay Model
2.2 boise Model
2.3 problem Formulation
chapter 3 buffer planning
3.1 buffer block
3.1.1 definition
3.1.2 L-shaped contour
3.2 feasible region
3.3 feasible regions for multiple-pin nets
chapter 4 unified buffer planning and floorplanning
4.1 simulated annealing based floorplanning
4.1.1 sequence pair representation
4.1.2 annealing scheme
4.2 buffer insertion
4.3 reshaping buffer block
chapter 5 experimental results
chapter 6 conclusion
biblography

C. J. Alpert and A. Devgan, ``Wire Segmenting for Improved buffer insertion, Proc. DAC , pp. 588--593, 1997.
C. J. Alpert and A. Devgan, S. T. Quay, ``Buffer Insertion for Noise and Delay Optimization, IEEE Trans. CAD, Vol. 18, Issue 11, pp. 1633--1645, Nov.1999.
C. J. Alpert, T. C. Hu, J. H. Huang, A. B. Kahng, and D. Karger,
Prim-Dijkstra Tradeoffs for Improved Performance-Driven Routing Tree Design,IEEE Trans. CAD, Vol. 14, pp. 890--896, 1995.
C. J. Alpert, J. Hu, S. S. Sapatnekar, P. G. Villarrubia, ``A Practical Methodology for Early Buffer and Wire Resource Allocation, Proc. DAC, pp. 189--194, 2001.
H. B. Bakoglu, Circuit, Interconnections, and Packaging for VLSI, Addison-Wesley, 1990.
J. Cong, T. Kong and Z. D. Pan, Buffer Block Planning for
Interconnect-Driven Floorplanning, Proc. ICCAD, pp.358--363, 1999.
J. Cong, T. Kong and Z. D. Pan, Buffer Block Planning for
Interconnect Planning and Predicition, IEEE Trans. VLSI
Systems, 2001.
A. Devgan, Efficient coupled noise estimation for on-chip
interconnects, Proc. IEEE/ACM Int. Conf. CAD, pp.147--151, 1997.
F. Dragan, A. Kahng, I. Mandoiu, S. Muddu, and A. Zelikovsky,
Provably good global buffering using an available buffer block
plan, Proc. Int. Conf. CAD, pp. 104--109, Nov. 2000.
W. C. Elmore, The transient response of damped linear networks with particular regard to wide band amplifiers, J. Appl. Phys., vol. 19, pp. 55--63, 1948.
L. P. P. P. van Ginneken, ``Buffer Placement in Distributed RC-tree Network for Minimal Elmore Delay, Proc. ISCAS, pp. 865--868, 1990.
L. Gal, On-chip crosstalk--The new signal integrity challenge, Proc. Custom Integrated Circuits Conf, pp. 12.1.1--12.1.4, 1995.
F. S. Hillier and G. J. Lieberman Introduction to Operations Research, McGraw-Hill, 1995.
S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by Simulated Annealing, Science, vol. 220, no. 4598, May 13, 1983, pp.671--680.
D. Li, A. Pua, P. Srivastava, and U. Ko, A Repeater-Optimazation Methodology for Deep Sub-Micron, High-Performance Processors, Proc. ICCAD, pp.726--731, 1997.
H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, VLSI Module Placement Based on Rectangle-Packing by the Sequence-Pair IEEE Trans. CAD , Vol. 15, pp. 1518--1524, 1996.
J. M. Rabaey, Digital Integrated Circuits: A Design Perspective, Prentice Hall, 1996.
S. Sait and H. Youssef, VLSI Physical Design Automation,
IEEE Press, 1995.
P. Sarkar and C.K. Koh, Routability-Driven Repeater Block
Planning for Interconnect-Centric Floorplanning, IEEE
Trans. on Computer-Aided Design, vol. 20, no. 5, pp. 660--671,
May 2001.
P. Sarkar, V. Sundararaman and C.K. Koh, Routability-Driven
Repeater Block Planning for Interconnect-Centric Floorplanning,
, pp. 186--191, 2000.
Semiconductor Industry Association, National Technology Roadmap for Semiconductors}, 1997 Edition.
Semiconductor Industry Association, National Technology Roadmap for Semiconductors, 1999 Edition.
K. L. Shephard and V. Narayan, Noise in submicron digital design, Proc. IEEE/ACM ICCAD}, pp. 524--531, 1996.
T. Stohr, M. Alt, A. Hetzel, and J. Koehl, Analysis, reduction
and avoidance of crosstalk on VLSI chips, Proc. ISPD, pp.
211--218, 1998.
X. Tang and D.F. Wong Planning Buffer Locations by Network Flows Proc. ISPD, pp. 180--185, 2000.
A. Vittal and M. Marek-Sadowska, Crosstalk reduction for VLSI, IEEE Trans. Computer-Aided Design, vol. 16, pp. 290--298,
1997.
F. Y. Young, Chris C. N. Chu, W. S. Luk, and Y. C. Wong Handling
Soft Modules in General Nonslicing Floorplan Using Lagrangian
Relaxation, IEEE Trans. CAD, Vol. 20, pp. 687--692, 2001.