臺灣博碩士論文加值系統

在控制單元(controller) (有限狀態機，finite state machine)的硬體實現中，狀態指派(state assignment)是最重要的問題之一。傳統解決狀態指派的經驗法則評估包括模擬降溫法(simulated annealing, SA)、貪婪方法(greedy approach)和遞迴式最小切割法(recursive Min-Cut partitioning)。我們考量到這些方法大部分是不能同時減少面積和功率的消耗。因此在這篇論文中，我們將提出一個利用整數線性規劃(integer linear programming, ILP)來解決控制器狀態指派的方式。這個整數線性規劃的目標函式主要是利用設定權重(weight)在較少面積與低功率之間做出適當的取捨以得到最佳解，這個方法將可以找出減少控制器面積和功率消耗的最佳編碼。除此之外，同樣的利用整數線性規劃我們還對控制器的輸出訊號作編碼，以減少資料路徑的功率消耗。

最後，我們將所提出的方法實作在MCNC基準測試程式(benchmarks)和控制器資料路徑的系統上，以驗證我們所提出的ILP解決方法的效能。根據實驗數據得知，這個方法確實可以達到在系統效能上功率和面積的節省。

The state assignment is one of the most important problems in hardware implementation of controllers (finite state machines, FSMs). Traditional heuristics include simulated annealing (SA), greedy approach, and recursive Min-Cut partitioning. Since these methods can’t reduce both area and power, thus we propose a new approach which using integer linear programming (ILP) to solve the state assignment. The proposed of ILP approach can set the weight and reach best solution between less area and low power. The approach can find out the best state assignment for both low-area and low power consumption. In addition, we also use ILP to solve the output encoding of controller in order to reduce the power consumption of datapath.

Finally, to verify the effectiveness of our proposed approach, we do some experiments on several MCNC FSM benchmarks and controller-datapath systems. The experimental results show that a significant power and area savings can be achieved.

CHAPTER 1 INTRODUCTION
1.1 Motivation
1.2 Paper Organization
CHAPTER 2 RELATED WORK
2.1 Problem Overview
2.2 Survey
2.3 Design Flow
CHAPTER 3 PREPOSITIVE PROCESS
3.1 Minimum Area
3.1.1 MUSTANG
3.1.1.1 A Fanin-Oriented Algorithm
3.1.1.2 A Fanout-Oriented Algorithm
3.1.1.3 State Assignment by ILP
3.1.2 JEDI
3.2 Minimizing Power Consumption
3.3 MCNC benchmark report
CHAPTER 4 CONTROLLER-DATAPATH SYSTEMS
4.1 Controller-Datapath Architecture
4.1.1 GCD
4.1.2 FIR
4.1.3 HAL
4.2 Graph Model
4.2.1 GCD
4.2.2 FIR
4.2.3 HAL
4.3 ILP State Assignment for Controller Architecture
4.3.1 GCD
4.3.2 FIR
4.3.3 HAL
4.4 Output Encoding
4.4.1 GCD
4.4.2 HAL
4.5 Controller report
4.5.1 GCD
4.5.2 FIR
4.5.3 HAL
4.6 Experiment result
4.6.1 GCD
4.6.2 HAL
CHAPTER 5 CONCLUSION AND FUTURE WORK
5.1 Conclusion
5.2 Future Work
References

[1]B. Lin and A. R. Newton, “Synthesis of multiple-level logic from
symbolic high-level description languages,” in Proc. IFIP Int. Conf. Very
Large Scale Integration, Aug. 1989, pp. 187–196.
[2]S. Devadas, H-K. T. Ma, A. R. Newton, and A. Sangiovanni-Vincentelli,
“MUSTANG: State assignment of finite state machines targeting multilevel logic implementations,” in IEEE Trans. Computer-Aided Design, vol. 7, pp. 1290–1300, Dec. 1988.
[3]X. Du, G. Hactel, B. Lin, and A. R. Newton, “MUSE: A multilevel symbolic encoding algorithm for state assignment,” in IEEE Trans. Computer-Aided Design, vol. 10, pp. 28–38, Jan. 1991.
[4]Villa, T., Sangiovanni-Vincentelli, A.: NOVA: State assignment of finite state
machines for optimal two-level logic implementation. IEEE Trans. Computer-
Aided Design 9 (1990) 905–924
[5]Benini,L.; De Micheli,G, “State Assignment for Low Power Dissipation.” in IEEE Journal for Solid-State Circuits, Vol. 30, No. 3, March 95, pp. 32-40.
[6]L. Benini, G. De Micheli, and F. Vermulen, “Finite State Machine Partitioning for Low Power”, Proc. International Symposium on Circuits and Systems, 1998, pp. 5-8.
[7]J. C. Monterio and A. L. Oliveria, “Finite State Machine Decomposition for Low Power”, Proc. Design Automaton Conference, 1998, pp. 758-763.
[8]E. Olson and S. Kang, “Low-Power State Assignment for Finite State Machines”, Proc. International Symposium on Low Power Design, 1994, pp. 63-68.
[9]C. Y. Tsui, M. Pedram, and A. Despain, “Low-Power State Assignment Targeting Two and Multilevel Implementations”, IEEE Trans. on CAD, vol. 17, 1998, pp. 1281-1291.
[10]Kris Thornburg, Anne Hummel, “LINGO 8.0 TUTORIAL”
[11]B.W. Kernighan and S. Lin, “An Efficient Heuristic Procedure for Partitioning Graphics”, The Bell Sys. Tech.a Journal, vol. 49, no.2, pp. 291-307, 1970
[12]S. H. Chow, et al, “Low Power Realization of Finite State Machines - A decomposition Approach”, ACM Transactions on Design Automation of Electronic System, l(3): pp. 315 - 340, July 1996
[13]J. C. Monteiro, et al, “Finite State Machine Decomposition For Low Power”, in Proceeding of Design Automation Conference 98, pp. 758 - 763, June 1998
[14]Ellen M. Sentovich, Kanwar Jit Singh, Luciano Lavagno, Cho Moon, Rajeev Murgai Alexander Saldanha, Hamid Savoj, Paul R. Stephan, Robert K. Brayton, Alberto Sangiovanni-Vincentelli “SIS: A System for Sequential Circuit Synthesis”, Electronics Research Laboratory Memorandum No. UCB/ERL M92/41, 4 May 1992
[15]D.A. Bader and K. Madduri, “A Parallel State Assignment Algorithm for Finite State Machines”, The 11th International Conference on High Performance Computing (HiPC 2004), L. Bougé and V.K. Prasanna, (eds.), Springer-Verlag LNCS 3296, 297-308, Bangalore, India, December 2004.
[16]Berkeley, University of California, “Berkeley Logic Interchange Format (BLIF)”. July 28, 1992
[17]Synopsys, “PrimePower Manual”, Release 2002.05, May 2002
[18]M. Munch, B. Wurth, R. Mehra, J. Sproch, N. Wehn, "Automating RT-Level Operand Isolation to Minimize Power Consumption in Datapaths," DATE-00: IEEE Design Automation and Test in Europe, pp. 624-631, Paris, France, March 2000. 627.
[19]A. Correale. “Overview of the Power Minimization Techniques Employed in the IBM PowerPC 4xx Embedded Controllers”. In Proceedings of the 1995 ACM/IEEE International Symposium on Low Power Design, pages 75–80, Apr. 1995.
[20]Jiong Luo, Lin Zhong, Yunsi Fei and Niraj K. Jha, "Register binding based RTL power management for control-flow intensive designs," IEEE Trans. on Computer-Aided Design of ICs & Systems, Aug. 2004.
[21]R. Lisanke. “Logic synthesis benchmark circuits for the International Workshop on Logic Synthesis”, May, 1989.
[22]PG Paulin, JP Knight, and EF Girczyc, HAL: A Multi-Paradigm Approach to Automatic Data Path Synthesis Proc. 23rd IEEE/ACM Design Automation Conf. (DAC ''86), pp. 263-270, 1986.