VLSI CAD中一些最佳化問題之研究

Optimization Problems in Computer-Aided-Design of VLSI circuits

林佑政(Yu-Chung Lin)

指導教授 ： 謝財明

中原大學/工學院/電子工程研究所/博士(2002年)

https://doi.org/10.6840/cycu200100521

摘要

在本論文中，我們將探究數個於超大型積體電路電腦輔助設計(VLSI CAD)中的問題。首先我們將探討邏輯合成步驟中的電路分解問題，並提出了一個具函數性考量的結構型分解演算法(Structural Decomposition)，以求達到時間延遲、電路面積、電源消耗等目標的最佳化。相較於傳統的研究，我們的演算法不僅保留了結構型分解的便利性，且可兼顧到整體電路的架構與特性。
時脈重置的最大瓶頸在於初始狀態問題(Initial State Problem)，由於這個問題的存在，使得時脈重置一直無法被廣泛的使用。在本論文中，我們將提出一個具適應性的演算法，本方法利用homing tree與homing sequence的概念來求得重置電路的初始狀態值。由於homing tree並不需要重建，因此本演算法可用以同時計算與處理多數個重置電路的初始值。更進一步地，此演算法亦可應用於解決局部分配起始狀態問題(partial initial state assignment)且可與其它優良的時脈重置演算法相結合。
最後我們將探討整數線性規劃問題，這類問題通常較困難的地方在於很難歸納出通用的轉換規則，我們將先整理並歸納出一些便利的轉換規則，接著將以通道繞線問題為例，利用所列舉的轉換規則將通道繞線電容耦合值最佳化問題轉換為整數線性規劃描述式，再以解整數線性規劃的商業軟體LINGO來求得問題的最佳解。

關鍵字

最佳化 ； 電腦輔助設計 ； 超大型積體電路

並列摘要

In this thesis we study several problems in Computer Aided Design of Very Large Scale Integrated circuits. First, we study the decomposition technique of logic synthesis stage. We propose a structural decomposition algorithm with functional consideration for delay, area, and power consumption minimization. Contrast to traditional research, our approach not only keeps the convenience of structural decomposition but also considers the structure of the whole circuit and character of the gates.
Due to the initial state problem, retiming can’t be widely applied to optimize the sequential circuits. We will propose an adaptive algorithm to compute the equivalent state using the concept of homing tree and homing sequence. Because the homing tree only need to be constructed once, our adaptive algorithm can be applied to compute the equivalent states for a set of retimed circuits. Furthermore, the algorithm can be applicable to circuits with partial initial state assignment and can be integrated into other retiming algorithms for various objectives (e.g. area, clock period, register number and etc.).
Finally, we study the Integer Linear Programming (ILP) problems. It is difficult to induce the formulating methods for the ILP problems. Therefore, we will propose some useful ILP formulating methods. Then an application of channel routing problem will be introduced for crosstalk minimization with dogleg.

並列關鍵字

Optimization ； Computer-Aided-Design ； VLSI

參考文獻

[1] Akers. Jr., S. B, “Universal Test Sets for Logic Networks.” IEEE Trans. on Computers, 835-839,Sept. 1973.

[3] H. B. Bakoglu, Circuits, Interconnections and Packaging for VLSI, Addison-Wesley, 1990.

[4] B. Becker, and R. Drechsler, “How many decomposition types do we need.” In Proceedings of the European Design and Test Conference, (Paris, March). 1995.

[6] M. Burstein and R. Pelavin, “Hierarchical channel router.” Integreation VLSI J., vol. I, 21-38, 1983.

[7] S. C. Chang, and M. Marek-Sadowska, “Technology mapping via transformations of function graphs.” In Proceedings of the IEEE International Conference on Computer Design (Cambridge, MA, Oct.), 159–162. 1992.