- 學位論文
以多階層式力導向演算法為基礎之低功率導向的標準元件擺置
Low Power Driven Standard-Cell Placement Based on a Multilevel Force-Directed Algorithm
摘要
隨著製程技術進入深次微米，功率消耗變得越來越重要。在考量電路的功率消耗之外，功率均勻分佈也將是另一個必須注意的問題。本論文中，我們提出一個以多階層式力導向演算法為基礎之低功率導向的標準元件擺置。此方法包含了四個階段，分別為切割、群組、擺置、以及元件交換。在第一階段，我們切割晶片成數個區塊(bin)。第二階段則是將標準元件(standard cell)群組形成模組(module)，並形成多階層式架構。第三階段，我們分配群組後的每一個模組到每一個區塊，此區塊的中心點即為模組的初始位置。接著，使用力導向演算法搬動每一個模組到力平衡的位置，並將模組反群組(uncoarsen)。重複此動作直到反群組成最初的標準元件。開始擺置標準元件在最上方的列(row)及最下方的列(row)，並且再將未擺置的標準元件使用力導向演算法更新其位置。直到所有列都被標準元件擺置。前三個階段在使得導線切換功率最小化。最後一階段，則是交換標準元件達到功率均勻分佈。 本程式以整合入商業設計流程。從實驗結果可以顯示出在權重函式中加入導線切換功率能有效降低導線切換功率。我們也研究加入群組階段對於功率消耗的影響，並且考量交換標準元件後所必需付出的成本。詳細結果請參照第五章。
並列摘要
As the process technology enters the deep sub-micron era, power consumption of a circuit becomes more important. Besides considering power consumption, uniform power distribution is also very important for longer life time of a chip. A low-power driven placement method based on multi-level force-directed algorithm is proposed. This approach includes four phases that are partitioning, coarsening, placement, and standard cell exchange. In the first phase, we partition a chip into several bins. In the second phase, we coarsen standard cells to form one module and build multi-level structure. In the third phase, we assign every coarsened module to one bin and the center position of bin is the initial position of module. Then, we move every coarsened module to its force-balanced location and uncoarsen every coarsened module. This action is repeated until all the coarsened module are uncarsened to the original standard cells. We start to place standard cells to the top row and the bottom row and the position of all non-placed standard cells are updated by using force-directed algorithm. Repeating this process until all rows are formed, the third phase is completed. The first three phases tries to minimize the switching power of wires. In the final phase, we exchange standard cells in order to balance power distribution of standard cells. We have integrated this approach into commercial design flow. The experimental result shows that adding switching rate to cost function can effectively reduce total switching power of wire. We also study the effect due to the coarsen phase and analyze the trade off between minimum power consumption and uniform power distribution. Experimental results are shown in chapter 5.