跳到主要內容

臺灣博碩士論文加值系統

(3.231.230.177) 您好!臺灣時間:2021/07/27 11:13
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:簡萬獅
研究生(外文):Wan-Shih Chien
論文名稱:動態可重組系統之模擬退火硬體排程演算法
論文名稱(外文):Simulated Annealing Based Hardware Task Scheduling on Dynamically Reconfigurable Systems
指導教授:李宗演李宗演引用關係
指導教授(外文):TRONG-YEN LEE
口試委員:嚴茂旭熊博安
口試委員(外文):Mao-Hsu YenPao-Ann Hsiung
口試日期:2011-12-16
學位類別:碩士
校院名稱:國立臺北科技大學
系所名稱:電腦與通訊研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:46
中文關鍵詞:模擬退火演算法現場可程式邏輯閘陣列硬體排程動態可重組系統
外文關鍵詞:Simulated annealing algorithmfield-programmable gate arrayhardware task schedulingdynamically reconfigurable systems
相關次數:
  • 被引用被引用:0
  • 點閱點閱:114
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
現場可程式邏輯閘陣列在設計時有彈性、低成本以及設計週期時短的特性。同時現場可程式邏輯閘陣列的動態可重組特性是一個有前瞻性的技術之一。但動態可重組技術在硬體排程上需要花費較多的重組時間,這也導致效率變低和功率消耗變大。在本論文中,我們用模擬退火演算法在可重組硬體上尋找最接近全域最佳排程解以提升排程效率。本文提出之方法的實驗結果與相關論文比較之下,本方法比基因演算法(Genetic Algorithm)減低21%排程時間、比螞蟻殖民地演算法(Ant-Colony Algorithm)降低3.4%排程時間。

Run time reconfigurable (RTR) feature on field-programmable gate array (FPGA) is absolutely one of the promising technologies on reconfigurable computing for its flexibility, low cost, and short design cycle. However, RTR technology on hardware task scheduling consumes considerable configuration overhead and power consumption. This paper focuses on the hardware task scheduling in order to get the minimal configuration overhead on dynamically reconfigurable hardware (DRHW) and FPGAs by simulated annealing algorithm. Comparison of proposed method with Genetic Algorithm (GA) and Ant-Colony based algorithm, the experimental results show that the proposed Simulation Annealing algorithm is 21% better than GA and 3.4% better than Ant-Colony based algorithm in hardware task scheduling.

ABSTRACT(Chinese) i
ABSTRACT i
ACKNOWLEDGEMENT iii
CONTENTS iv
LIST OF TABLES vi
LIST OF FIGURES 1
Chapter 1 INTRODUCTION 1
1.1 Reconfigurable Computing 1
1.2 Task Scheduling 3
1.3 Motivation and Contribution 4
1.4 Organization 5
Chapter 2 RELATED WORK 6
2.1 Task Scheduling 6
2.2 Heuristic Algorithm 6
Chapter 3 SYSTEM ARCHITECTURES AND PROBLEM DESCRIPTION 9
3.1 FPGA Architecture 9
3.1.1 Advantages of FPGA 9
3.1.2 Basic Process Technology Types of FPGA 10
3.1.3 Basic FPGA Architecture 11
3.2 Dynamically Reconfigurable Hardware Architecture 12
3.3 1-D and 2-D Reconfigurable Architecture 13
3.4 Task Model 13
3.5 Task Graphs 14
Chapter 4 SIMULATED ANNEALING ALGORITHM 16
4.1 Simulated Annealing Algorithm 16
4.2 Simulated Annealing Algorithm on Hardware Task Scheduling 18
4.2.1 Perturbation Function 18
4.2.2 Placer Algorithm 21
4.3 Proposed Simulated Annealing Algorithm 23
Chapter 5 EXPERIMENTAL RESULTS 28
5.1 Task Graphs for Free 28
5.1.1 System and Algorithm Parameters for TGFF 30
5.1.2 Performance Comparison of Algorithms in TGFF 31
5.2 Joint Photographic Experts Group (JPEG) 32
5.2.1 System and Algorithm Parameters for JPEG 33
5.2.2 Performance Comparison of Algorithms in JPEG 34
Chapter 6 CONCLUSION AND FUTURE WORK 35
BIBLIOGRAPHY 36
APPENDIX 38
Conference Papers 38



[1]http://www.axis.com.tw
[2]http://www.xilinx.com.tw
[3]http://www.intel.com.tw
[4]K. Compton and S. Hauck, “Reconfigurable computing: a survey of systems and software,” ACM Computing Surveys, Vol. 34, pp. 171-210, June 2002.
[5]Y. Qu, J.-P. Soininen, and J. Nurmi, “A genetic algorithm for Scheduling tasks onto dynamically reconfigurable hardware,” in Proc. of the IEEE International Symposium on Circuits and Systems, May 2007, pp. 161-164.
[6]Y. Qu, J.-P. Soininen, and J. Nurmi, “Static scheduling techniques for dependent tasks on dynamically reconfigurable devices,” Journal of Systems Architecture, Vol. 53, pp. 861-876, Nov. 2007.
[7]R. Crodone, F. Redaelli, M. A. Redaelli and M. D. Santambrogio, “Partitioning and Scheduling of Task Graphs on Partially Dynamically Reconfigurable FPGAs,” IEEE Trans. Computer-Aided Design of Intergrated Circuits and Systems, Vol. 28, no. 5, pp. 662–675, May 2009.
[8]T. Y. Lee, W. T. Wu, Ch. P. Hu, and C. C. Tsai, “Ant-Colony Based Task Scheduling for Dynamic Partial Reconfigurable Systems,” in Proc. of Electronic Technology Symposium, Kaohsiung Taiwan, BO-01, Jun. 2009.
[9]S. Banerjee and N. Dutt, “Efficient Search Space Exploration for HW-SW Partitioning,” in Proc. of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, Sept. 2004, pp. 122-127.
[10]S Kirkpatrick, C. D. Gelatt, M. P. Vechi, “Optimization by simulated annealing,” Science, Vol. 220, pp. 671-680, 1983.
[11]R. P. Dick, D. L. Rhodes, and W. Wolf, “TGFF:task graphs for free,” in Proc. of the Sixth International Workshop on Hardware/Software Codesign, Mar. 1998, pp. 97-101.
[12]Y. Qu, J-P. Soininen, J. Nurmi, “A parallel configuration model for reducing the run-time reconfiguration overhead,” in IEEE Proc. of the Design, Automation, and Test in Europe Conference, 2006, pp. 965-970.
[13]F. Redaelli, M. D. Santambrogio, D. Sciuto, “Task Scheduling with Configuration Prefetching and Anti-Fragmentation Techniques on Dynamically Reconfigurable Systems,” in Proc. of the conference on Design, automation and test in Europe, 2008, pp. 519-522.
[14]S. Banerjee, E. Bozorgzadeh, and N. Dutt., “Parlgran: parallelism granularity selection for scheduling task chains on dynamically reconfigurable architectures,” in Proc. of Asia and South Pacific Design Automation Conference, Jan. 2006, pp. 491-496.
[15]M. M. Bassiri and H. Sh. Shahhoseini, “On-line HW/SW Partitioning and Co-scheduling in Reconfigurable Computing Systems,” in Proc. of ICCSIT 2nd IEEE International Conference, Aug. 2009, pp. 557-562.


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top