成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	謝政宏 Hsieh, Cheng-Hung
論文名稱：	資料驅動多執行緒之多核心系統資源管理器設計 Design of a Resource Manager for Data-Driven Multithreading on Multicore Systems
指導教授：	周哲民 Jou, Jer-Min
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 電機工程學系 Department of Electrical Engineering
論文出版年：	2014
畢業學年度：	102
語文別：	中文
論文頁數：	127
中文關鍵詞：	多核心系統、循序程式平行化、資料驅動多執行緒、資源管理器
外文關鍵詞：	Multicore System, Parallel Execution of Sequential Program, Data-Driven Multithreading, Resource Manager
相關次數：	點閱：94 下載：3
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

多核心系統的興起迫使SoC設計師必須考慮應用程式執行緒之間的平行性，因為應用程式只有在被分割成執行緒且平行執行在多個核心上時才能夠妥善利用多核心系統的資源。編譯階段的平行將會無法應付多核心環境中的動態變化且使得程式執行效率低落。為了使應用程式在眾多的軟體與硬體環境中得以有效率地平行執行，在本論文中，我們將提出一個基於軟硬體共同設計的運行時資源管理器來動態、持續且智慧地在動態的執行情況下管理應用程式的平行執行。管理器將會在多核心環境中對平行應用程式的執行緒進行有效率地排程、映射、同步與負載平衡。在本運算平台的實驗結果顯示，循序程式可以經由所提出的方法轉換為平行程式，且這些平行程式在同時執行時能比他們的循序版本提高約1.37倍的執行速度。

The rise of multicore systems forces SoC designers to take advantage of parallelism among threads in the applications, because an application can use multicore resource appropriately only when it can be separated as the threads which could be executed in the cores in parallel. Compiled-time parallel execution can fail to be efficient and unable to account for dynamic changes in the multicore run-time environment. In order to make time-efficient parallel execution of applications in a wide range of hardware and software environments, in this thesis, we propose a hardware-software co-design based run-time resource manager to dynamically, continuously and judiciously manage program's parallel execution in the dynamic execution conditions. It will schedule, map, synchronize, do load balance among threads of parallel applications in the multicore environment efficiently. Experimental results show that the sequential programs could be transformed into parallel programs as proposed, and those programs could be executed simultaneously with 1.37x faster than their sequential version.

摘要	I
SUMMARY	II
誌謝	VII
目錄	VIII
表目錄	XIV
圖目錄	XV
第1章 緒論	1
1	研究動機	1
2	研究目的	1
3	論文架構	2
第2章 背景知識與相關研究	3
1	平行運算架構	3
1.1	單處理器系統	4
1.2	多處理器系統	4
1.3	多計算機系統	5
1.4	Flynn的分類法	6
2	循序程式平行化	7
2.1	任務資料流圖	7
2.2	尋找平行性	8
2.3	撰寫平行程式	9
2.4	Foster的設計方法	10
2.5	平行運算所產生的問題	11
2.6	程序間通訊方式	13
3	資料驅動多執行緒模型	15
3.1	任務與同步圖	15
3.2	執行緒同步單元	16
4	相關研究	17
4.1	Cilk	17
4.2	HELIX	17
4.3	TFlux	18
4.4	DDMCPP	19
4.5	DDM-CMP	19
4.6	D2NOW	20
4.7	REEact	21
4.8	ADM	22
4.9	DTA-C	23
4.10	PD	24
4.11	AME	25
4.12	Linux Scheduler v2.6.38	25
4.12.1	程序、執行緒的建立	26
4.12.2	程序分類	26
4.12.3	排程目標、排程策略	27
4.12.4	排程類別、排程器	27
4.12.5	程序優先權、靜態負載、虛擬運行時間的計算	28
4.12.6	排程域、排程組	28
4.12.7	多核心的負載平衡	30
第3章 資料驅動多執行緒資源管理器之設計	31
1	資料驅動多執行緒資源管理器的設計考量	31
1.1	DDM資源管理系統的分層設計	31
1.2	與DDM程式碼獨立的程式進入介面函式庫	32
1.3	階層式的多核心資源管理器模型	33
1.4	任務與執行緒的關係	34
1.5	執行緒映射與同步圖分割的設計緣由	36
1.6	任務排程與執行緒同步的設計緣由	37
1.7	執行緒負載平衡的設計緣由	38
2	資料驅動多執行緒資源管理器的組成	39
3	資料驅動多執行緒資源管理器的行為	40
3.1	資源管理器的啟動	40
3.2	程式同步圖的分割	41
3.3	程式同步圖、執行緒的全域映射	41
3.4	執行緒的任務排程、本地映射	42
3.5	執行緒的本地同步	43
3.6	執行緒的全域同步	43
3.7	執行緒的本地負載平衡	44
3.8	執行緒的全域負載平衡	45
3.9	系統資訊的蒐集與監控	45
4	資料驅動多執行緒資源管理器的設計優缺點	46
第4章 資料驅動多執行緒資源管理器之實現	48
1	資料驅動多執行緒程式的轉換流程	48
1.1	任務的平行分割	49
1.2	描述程式同步圖	49
1.3	產生資料驅動多執行緒程式碼	49
1.4	使用編譯器編譯	50
1.5	實做範例	51
2	資料驅動多執行緒資源管理器的實現考量	55
2.1	使用者層級的虛擬執行環境	56
2.2	資料流方式的執行緒通訊方式	56
2.3	使用者操作介面	57
2.4	隨時下達操作指令	57
2.5	同時管理多程式多執行緒	58
3	資料驅動多執行緒資源管理器的組成	58
3.1	全域管理單元	58
3.2	本地管理單元	62
3.3	系統資訊蒐集單元	66
3.4	資料驅動多執行緒程式	67
4	資料驅動多執行緒資源管理器的行為	69
4.1	資料驅動多執行緒資源管理器的啟動與初始化	69
4.1.1	偵測系統配置	70
4.1.2	計算本地管理單元數量	71
4.1.3	建立本地管理單元、系統資訊蒐集單元程序	73
4.1.4	信號的初始化	73
4.2	資料驅動多執行緒資源管理器的週期性行為	75
4.2.1	刷新使用者介面資訊	75
4.2.2	獲取使用者指令	76
4.2.3	獲取處理器資源利用率資訊	77
4.3	執行資料驅動多執行緒程式	78
4.3.1	指令解碼	79
4.3.2	建立使用者程式程序	80
4.3.3	建立同步圖、同步子圖表共享記憶體區塊	80
4.3.4	建立執行緒	80
4.4	程式同步圖的分割、全域映射	81
4.4.1	載入同步圖	82
4.4.2	計算任務優先權	82
4.4.3	計算程式最大平行度	84
4.4.4	分割同步圖	84
4.4.5	建立同步子圖、同步子圖表共享記憶體區塊	88
4.4.6	獲得閒置本地管理單元代號	89
4.4.7	添加新執行緒	90
4.5	資料驅動執行緒的任務排程、本地映射	90
4.5.1	任務排程	91
4.5.2	獲得閒置處理器代號	93
4.5.3	設置處理器親和性	94
4.5.4	執行任務函式	95
4.6	資料驅動執行緒的本地同步	96
4.7	資料驅動執行緒的全域同步	97
4.8	資料驅動執行緒的本地負載平衡	98
4.8.1	檢查本地負載是否平衡	99
4.8.2	尋找被遷移執行緒代號	99
4.8.3	更改執行緒資訊	100
4.9	資料驅動執行緒的全域負載平衡	101
4.9.1	檢查全域負載是否平衡	101
4.9.2	尋找被遷移程序代號	102
4.9.3	尋找被遷移執行緒代號	102
4.9.4	遷出執行緒資訊	102
4.9.5	遷入執行緒資訊	102
4.9.6	更改執行緒資訊	103
4.10	系統資源利用率的傳遞	104
4.11	資料驅動多執行緒資源管理器的系統結束	105
5	資料驅動多執行緒資源管理器的實現優缺點	106
第5章 實驗環境與數據分析	108
1	測試程式	108
2	實驗環境配置	109
3	資料驅動多執行緒資源管理器配置	110
4	多個程式在虛擬與實體多核心環境的實驗結果	112
5	資料驅動多執行緒資源管理器的執行時間量測	118
6	實驗總結	119
第6章 結論與未來展望	121
1	結論	121
2	未來展望	121
參考文獻	122
附錄	126
                                    

[1]Arvind and Gostelow, K. P. "The U-interpreter." Computer 15.2 (1982): 42-49.
[2]Amdahl, Gene M. "Validity of the single processor approach to achieving large scale computing capabilities." Proceedings of the April 18-20, 1967, spring joint computer conference. ACM, 1967.
[3]C. Kyriacou, P. Evripidou, and P. Trancoso. "Data-driven multithreading using conventional microprocessors." Parallel and Distributed Systems, IEEE Transactions on 17.10 (2006): 1176-1188.
[4]D. Sanchez, R. M. Yoo, and C. Kozyrakis. "Flexible architectural support for fine-grain scheduling." ACM Sigplan Notices. Vol. 45. No. 3. ACM, 2010.
[5]D. Tam , R. Azimi , M. Stumm. "Thread clustering: sharing-aware scheduling on SMP-CMP-SMT multiprocessors." ACM SIGOPS Operating Systems Review. Vol. 41. No. 3. ACM, 2007.
[6]Foster Ian, "Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering", Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
[7]Fiduccia, Charles M., and Robert M. Mattheyses. "A linear-time heuristic for improving network partitions." Design Automation, 1982. 19th Conference on. IEEE, 1982.
[8]Feng Li, A. Pop, and A. Cohen. "Automatic extraction of coarse-grained data-flow threads from imperative programs." Micro, IEEE 32.4 (2012): 19-31.
[9]H. Vandierendonck, P. Polyvios, and S. N. Dimitrios. "Parallel programming of general-purpose programs using task-based programming models." Proceedings of the 3rd USENIX conference on hot topic in parallelism. USENIX Association, 2011.
[10]H. Vandierendonck, G. Tzenakis, and D. S. Nikolopoulos, "A unified scheduler for recursive and task dataflow parallelism", Parallel Architectures and Compilation Techniques, 2011 International Conference on. IEEE, 2011.
[11]Kernighan, B. W., and S. Lin. "An eﬂicient heuristic procedure for partitioning graphs." Bell system technical journal 49.2 (1970): 291-307.
[12]M.R. Guthaus et al., "MiBench: A free, commercially representative embedded benchmark suite," Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop on. IEEE, 2001.
[13]M. Frigo, C. E. Leierson, and K. H. Randall, "The implementation of the Cilk-5 multi-threaded language", ACM Sigplan Notices. Vol. 33. No. 5. ACM, 1998.
[14]P. Evripidou and J. Gaudiot. "A Decoupled graph/computation Data-Driven architecture with variable resolution actors". No. CONF-900874-5. University of Southern California, Los Angeles, CA (United States). Dept. of Electrical Engineering, 1990.
[15]R. Giorgi, Z. Popovic, N. Puzovic, "DTA-C: A Decoupled multi-Threaded Architecture for CMP Systems", Computer Architecture and High Performance Computing, 2007. SBAC-PAD 2007. 19th International Symposium on. IEEE, 2007.
[16]R. Knauerhase, P. Brett, B. Hohlt, T. Li, and S. Hahn, "Using OS observations to improve performance in multicore systems", IEEE micro 28.3 (2008): 54-66.
[17]Stavrou, Kyriakos, Paraskevas Evripidou, and Pedro Trancoso. "DDM-CMP: data-driven multithreading on a chip multiprocessor." Embedded Computer Systems: Architectures, Modeling, and Simulation. Springer Berlin Heidelberg, 2005. 364-373.
[18]Stavrou, Kyriakos, et al. "Tflux: A portable platform for data-driven multithreading on commodity multicore systems." Parallel Processing, 2008. ICPP'08. 37th International Conference on. IEEE, 2008.
[19]S. Sridharan , G. Gupta , G.S. Sohi, "Holistic run-time parallelism management for time and energy efficiency", Proceedings of the 27th international ACM conference on International conference on supercomputing. ACM, 2013.
[20]S. Campanoni, T. Jones, et al., "HELIX: automatic parallelization of irregular programs for chip multiprocessing", Proceedings of the Tenth International Symposium on Code Generation and Optimization. ACM, 2012.
[21]Trancoso, Pedro, Kyriakos Stavrou, and Paraskevas Evripidou. "DDMCPP: The data-driven multithreading C pre-processor." The 11th Workshop on Interaction between Compilers and Computer Architectures. 2007.
[22]Wang, Wei, et al. "REEact: a customizable virtual execution manager for multicore platforms." ACM SIGPLAN Notices. Vol. 47. No. 7. ACM, 2012.
[23]Wei Wang, et al, "Performance analysis of thread mappings with a holistic view of the hardware resources", Performance Analysis of Systems and Software (ISPASS), 2012 IEEE International Symposium on. IEEE, 2012.
[24]Z. Zhang , D.S. Katz , M. Ripeanu , M. Wilde , I.T. Foster, "AME: an anyscale many-task computing engine", Proceedings of the 6th workshop on Workflows in support of large-scale science. ACM, 2011.
[25]Blaise B., "Introduction to Parallel Computing", Lawrence Livermore National Laboratory
[26]Quinn, Michael J., "Parallel Programming in C with MPI and OpenMP", McGrawHill
[27]Die.Net linux main pages. http://linux.die.net/man/
[28]GCC, the GNU Compiler Collection. http://gcc.gnu.org/
[29]IEEE. Threads Extension for Portable Operating Systems (Draft 6), February 1992. P1003.4a/D6.
[30]OpenMP: Simple, portable, scalable SMP programming. http://www.openmp.org, 2006.
[31]IBM DeveloperWorks. http://www.ibm.com/developerworks/
[32]Linux Kernel Document. https://www.kernel.org/
[33]Linux kernel profiling with perf. https://perf.wiki.kernel.org/index.php/Tutorial
[34]SLOC Counter. http://www.dwheeler.com/sloccount/

校內：2017-08-14公開
校外：2017-08-14公開

簡易檢索 / 詳目顯示

相關論文