Multiple voltages scheduling and partitioning scheme for low power design

在行動產品愈趨多元的今日，低必v的設計需求日益重要，不但可減少熱能發散，並延長產品的使用時間。高階低功率技術具有較大的彈性及效果。本章介紹功率消耗可分為動態必v消耗、短路必v消耗及漏電必v消耗，引進多電壓源技術及其必v消耗模式，並介紹高階合成各步驟及在電路設計中各階層低必v設計技術。 控制資料流程圖(CDFG)是在高階合成中常用的一種圖形，用來表示資料的流動及運算。在第二章介紹其定義、格式及其表示法。並利用工具分析硬體描述語言(VHDL)，產生控制資料流程圖。之後我們會介紹物件導向圖形函式庫。此論文方法利用圖形函式庫來做為之後程式排程、配置及繫結。 第三章對控制資料流程圖做基本排程，包含最早(ASAP)及最晚(ALAP)排程。同時也介紹分割方法及模擬退火法。根據這此資訊，結合區塊分割方法，我們利用模擬退火法提出新的方法，在取代運算時考慮線路上的必v消耗，從模擬退火法的四大要件來說明及其細部方法。在經過排程後的控制資料流程圖會決定每個運算的運算時間，變數的生存時間被決定。藉由建立衝突圖(Conflict Graph)，可得到每個排程後的控制資料流程圖所需的暫存器和多工器。 最後，我們利用8筆測試資料來檢驗此方法的效果，並比較不同分割數及時間限制，數據顯示此方法約可節省20%~40%的必v消耗。A multiple scheduling method is one of the useful techniques for low power high level synthesis which replaces functional units with lower supply voltage. The thesis presents a scheduling scheme combining with partitioning that minimizes power consumption. This scheme takes power consumption of interconnection into account to keep balance between functional units and interconnection. The timing constrained scheduling method is achieved by performing simulated annealing which is an iterative and non-deterministic algorithm that allows uphill moves to escape from local optima. The proposed algorithm consists of two phases, the initial partition and modification process. In the first phase, the initial solution is decided according to list-based scheduling algorithm. In the next stage, two types of modification are introduced during the process of the simulated annealing. One modification is replacement which moves operation from one partition to another. The other is exchange which exchanges operations in different partitions. A power reduction of 20~40% is shown with strict timing constraint.Contents 1 Introduction .................................................................................................... 1 1.1 The trend of low power.......................................................................... 1 1.2 High Level synthesis ............................................................................. 1 1.3 Multiple voltages ................................................................................... 4 1.4 Low power design at various levels of abstraction ............................ 6 1.5 The goal of the thesis ............................................................................ 8 2 CDFG parser, generator and representation ............................................... 10 2.1 CDFG representation ........................................................................... 10 2.2 CDFG format ........................................................................................ 11 2.3 CDFG toolkit ......................................................................................... 13 2.3.1 Parser ............................................................................................ 13 2.3.2 Generator ..................................................................................... 13 3 Scheduling and partitioning scheme for low power .................................... 15 3.1 Basic scheduling and partitioning algorithm ..................................... 15 3.1.1 ASAP scheduling ......................................................................... 16 3.1.2 ALAP Scheduling ........................................................................ 18 3.2 Multiple voltages scheduling with slack time ..................................... 21 3.3 Partitioning ............................................................................................ 22 3.4 Simulated annealing ............................................................................. 23 3.5 Min-cost algorithm based on simulation annealing ........................... 24 3.5.1 Solution space ............................................................................... 25 3.5.2 Neighborhood structure .............................................................. 27 3.5.3 Cost function ................................................................................ 28 3.5.4 Annealing schedule ...................................................................... 32 3.5.5 Initial solution – list based scheduling ....................................... 33 4 4 Allocation and binding .................................................................................. 37 4.1 Conflict graph construction ................................................................. 38 4.2 Heuristic algorithms ............................................................................. 40 5 Experimental results ...................................................................................... 44 5.1 Experimental environment .................................................................. 44 5.2 Experimental results ............................................................................. 45 6 Conclusion ....................................................................................................... 49 Reference ................................................................................................................ 50 Appendix ................................................................................................................ 5