適用於設計流程應用於超大型積體電路性能最佳化之標準元件尺寸調整方法

A Robust and Design Flow Compatible Standard Cell Sizing Method for VLSI Circuit Performance Optimization

陳奕翰(Yi-Han Chen)

指導教授 ： 陳中平

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

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

摘要

在超大型積體電路的設計流程中，電路最佳化是相當重要的一個步驟，尤其對於要求高效能或低功耗的電路設計而言。一直以來，元件尺寸最佳化的技術在電路時序、功率消耗及面積的取捨中提供了一個非常有效的方式。一些現有的演算法使用基於元件尺寸連續的最佳化方法來解決元件尺寸調整的問題，並且假設元件尺寸可以是一個範圍區間內的任意值。但當我們在實際情況中使用離散分布的標準元件庫時，一個元件的尺寸選擇是非常有限的，並且元件的尺寸分布相當鬆散。尺寸連續的調整方法這時就面臨到必須將連續解用逼近法近似到離散元件尺寸的狀況，這個步驟經常導致電路違反時序要求。
在這篇論文中，我們使用動態規劃尋找最佳解的方式來解決離散的元件尺寸最佳化問題。我們將元件尺寸選擇一致性的條件鬆弛，使得動態規劃可以應用在電路對應的有向圖上，並且我們在動態規劃局部解合併的過程中運用了加速的合併技術。我們根據動態規劃得到的結果來決定元件的尺寸，並且解決尺寸選擇不一致的問題。最後，我們使用一個以敏感度作為導引的啟發式演算法進行電路面積及功率消耗的極小化，並且更進一步的改善電路的時序延遲。
實驗結果顯示，在我們的最佳化流程中使用窮盡搜尋動態規劃的方式，最佳化結果優於商用軟體產生的結果。使用加速的合併技術，也可達到接近的時序結果並且減少面積以及功率的消耗。

關鍵字

電路最佳化 ； 元件尺寸最佳化 ； 動態規劃 ； 敏感度 ； 減少面積 ； 降低功率消耗

並列摘要

In the VLSI circuit design flow, circuit optimization is a very important step especially for high performance and low power IC designs. The gate sizing technique has always been an effective method in delay, power dissipation and area trade-offs. Some existing methods use continuous approach to solve the gate sizing problem, which is based on the assumption that gate sizes can be any value within a certain range. Unfortunately, when using existing discrete standard cell libraries in real situation, the sizes available of a gate type are limited and sparsely distributed. Continuous methods thus suffers from rounding the continuous result back to discrete cell size, and often results in timing violations.
In this thesis, we provide a method to solve the discrete gate sizing problem by a dynamic programming solution searching method with a relaxation-restriction flow. The dynamic programming solution search can be applied to a directed acyclic graph with solution consistency relaxation. A speed-up solution merging technique is used in dynamic programming solution searching process. We determine the gate sizes following the dynamic programming solution while handling the inconsistency of reconvergence paths. Finally, a sensitivity guided heuristic algorithm is performed to reduce the area/power and further improves the circuit timing delay.
Experimental results show that our optimization results can beat the results generated by commercial tool when exhausted dynamic programming search is applied. With the speed-up solution merging technique applied, the optimization results can achieve comparable circuit delay while improving area and power dissipation.

並列關鍵字

Circuit Optimization ； Gate Sizing ； Dynamic Programming ； Sensitivity ； Area Reduction ； Power Reduction

參考文獻

[3] S. P. Boyd, S. J. Kim, D. D. Patil, and M. A. Horowitz, “Digital circuit optimization via geometric programming,” in Operations Research, vol. 53,

[4] P. K. Chan, “Algorithms for library-specific sizing of combinational logic,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 353–356, 1990.

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

[7] S. Roy, W. Chen and C. P. Chen, "ConvexFit: an optimal minimum-error convex fitting and smoothing algorithm with application to gate-sizing," in Proceedings of IEEE/ACM International conference on Computer-aided design, pp. 196-203, 2005.

[9] Y. Liu and J. Hu, "A new algorithm for simultaneous gate sizing and threshold voltage assignment," in Proceedings of international symposium on Physical design, pp. 27-34, 2009.