同時調整標準單元設計的元件尺寸及臨界電壓之演算法

Simultaneous Gate Sizing and Multiple-Vt Assignment for Cell-Based Design

洪士斌(Shih-Pin Hung)

指導教授 ： 陳中平

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2009年)

https://doi.org/10.6342/NTU.2009.10252

摘要

電路最佳化在高效能以及低功率消耗積體電路設計中是非常重要的一個步驟。它對於電路最終的時序、功率消耗以及面積有相當大的影響。在標準單元設計中，元件尺寸及臨界電壓最佳化非常適合用來達成電路設計者對於時序及功率消耗的要求。雖然已經有很多元件尺寸最佳化的方法被提出來，但是大部分的方法都假設元件尺寸是連續的變數，也就是說元件尺寸可以是一個限制在某個範圍內的任意值。然而，在實際的標準單元庫中，可以選擇的元件尺寸大小以及臨界電壓都是非常有限的，使得先求出連續解再用逼近法近似的方法經常導致電路違反時序要求。因此，我們提出一個新的演算法可以直接處理離散的元件尺寸以及臨界電壓。我們把這個問題轉成一個數學規劃問題，最佳化目標為電路的功率消耗，並且能滿足時序的要求。利用拉格朗日鬆弛法，這個數學規劃問題可以被大幅的簡化。然後再利用我們提出的啟發式演算法解決這個問題。實驗結果顯示，比起用連續的方法求解再逼近，我們提出的方法平均可以降低35.5％的漏電功率消耗以及9.1％的總功率消耗，而執行速度能快55倍。

關鍵字

元件尺寸最佳化 ； 臨界電壓最佳化 ； 降低功率消耗 ； 拉格朗日鬆弛法 ； 標準單元設計

並列摘要

Circuit optimization is a very important step in high performance and low power IC design. It has a significant impact on the delay, power dissipation and area of the final circuit. Gate sizing and multiple-Vt assignment are common and useful ways to meet power and timing budgets for cell-based design. There exist some gate sizing techniques, however, most of them handle continuous gate sizing problem which is based on the assumption that gate sizes can be any value within certain range. In realistic standard cell libraries, available gate sizes and threshold voltages are sparse, which makes the nearest rounding approach inapplicable as large timing violations may be introduced. As a result, we propose a novel algorithm which directly handles discrete gate sizes and threshold voltages. We formulate the optimization into a mathematical program with total power cost and timing constraint. The formulation can be greatly simplified based on Lagrangian relaxation. Then we adopt a heuristic algorithm which solves the mathematical program without domain transformation. Experimental results demonstrate that compared to the continuous approach, we achieve average leakage power savings of 35.5% and average total power savings of 9.1% with 55× faster runtime.

並列關鍵字

Gate Sizing ； Multiple-Vt Assignment ； Power Reduction ； Lagrangian Relaxation ； Cell-Based Design

參考文獻

[3] H. Tennakoon and C. Sechen, “Gate sizing using Lagrangian relaxation combined with a fast gradient-based pre-processing step,” Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 395–402,2002.

[4] H. Tennakoon and C. Sechen, “Efficient and accurate gate sizing with piecewise convex delay models,”Proceedings of ACM/IEEE Design Automation Conference, pp. 807–812, 2005.

[5] S. P. Boyd, S. J. Kim, D. D. Patil, and M. A. Horowitz, “Digital circuit optimization via geometric programming,” Operations Research, vol. 53, pp. 899–932, Nov.-Dec. 2005.

[7] O. Coudert, “Gate sizing for constrained delay/power/area optimization,”IEEE Transactions on Very Large Scale Integration Systems, vol. 5, pp. 465–472, Dec. 1997.

[9] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004.