并行遞歸Cilk靜態(tài)優(yōu)化負(fù)載均衡數(shù)據(jù)重用碩士論文

1、面向Cilk的并行遞歸程序優(yōu)化技術(shù)研究計算機(jī)科學(xué)與技術(shù)， 2010， 碩士【摘要】 隨著多核體系結(jié)構(gòu)的出現(xiàn)和快速發(fā)展,如何在多核體系結(jié)構(gòu)上進(jìn)行簡單高效的并行程序設(shè)計以充分利用多核所提供的并行性已變得日益重要。然而要在傳統(tǒng)的并行程序語言上編寫出高效的并行程序,程序員需要對底層細(xì)節(jié)和程序結(jié)構(gòu)有清晰的認(rèn)識。因此,需要有一種新的編程模型既能簡單的實現(xiàn)并行,同時又能高效的執(zhí)行。有研究指出利用分治法和遞歸模型能在實現(xiàn)這一目的的過程中起到很大的作用。目前有一種簡單的基于線程的并行程序設(shè)計語言Cilk能自然的實現(xiàn)并行遞歸。作為對C語言的精簡擴(kuò)展,程序員在編寫Cilk程序時,更多的關(guān)注于開發(fā)并行性和局部性,而不

2、用關(guān)心底層的調(diào)度和負(fù)載均衡。但是我們研究中發(fā)現(xiàn),在并行度遠(yuǎn)高于處理器個數(shù)的情況下,特別是并行遞歸程序,會因為派生過多的例程導(dǎo)致過多的開銷,甚至使并行程序的性能還不如串行程序,因此需要通過降低這部分開銷來優(yōu)化Cilk并行遞歸程序,以提高其性能。本文根據(jù)不同并行遞歸問題的計算過程,總結(jié)出其輔助性能模型。在該模型下,能推斷出例程派生開銷對程序性能的影響,進(jìn)一步的可以推斷出減少這部分開銷后對并行遞歸程序的性能影響。本文首先對Cilk程序進(jìn)行靜態(tài)優(yōu)化,包含并行度優(yōu)化和負(fù)載均衡優(yōu)化。并行. 更多還原【Abstract】 Along with the fast development of mul

3、ti-core architecture, it becomes more and more important how to realize efficient parallel programming to make use of the parallelism provided by the multi-core.However, when writing parallel program on traditional parallel programming languages, programmers need to know the bottom details and the s

4、tructure of the program well; thereby its needed that a new programming model for realizing parallel simply and efficiently. Studies have pointed out that the us. 更多還原 【關(guān)鍵詞】 并行遞歸； Cilk； 靜態(tài)優(yōu)化； 負(fù)載均衡； 數(shù)據(jù)重用； 【Key words】 Parallel recursion； Cilk； static optimization； Load balance； data reuse； 摘要 8-9

5、 Abstract 9 第一章 引言 10-13 1.1 課題背景 10 1.2 研究現(xiàn)狀 10-11 1.3 本文工作 11-12 1.4 論文結(jié)構(gòu) 12-13 第二章 背景知識 13-27 2.1 Cilk 介紹 13-18 2.1.1 Cilk 編程模型 13-16 2.1.2 Cilk 調(diào)度策略 16-17 2.1.3 Cilk 性能模型 17-18 2.2 Lex 和Yacc 介紹 18-23 2.2.1 Lex 介紹 18-20 2.2.2 Yacc 介紹 20-23 2.3 傳統(tǒng)數(shù)據(jù)重用模型介紹51,52 23-27 2.3.1 串行循環(huán)數(shù)據(jù)重用51,52 23-24 2.3.2

6、 并行循環(huán)數(shù)據(jù)重用52 24-27 第三章 Cilk 并行遞歸程序并行度及負(fù)載均衡優(yōu)化 27-43 3.1 Cilk 并行遞歸程序案例分析 27-29 3.1.1 實驗平臺 27 3.1.2 案例分析及實驗結(jié)果 27-29 3.2 Cilk 并行遞歸程序優(yōu)化理論模型 29-31 3.3 Cilk 并行遞歸程序并行度優(yōu)化技術(shù)研究 31-34 3.4 并行度優(yōu)化進(jìn)一步分析 34-35 3.5 Cilk 負(fù)載均衡優(yōu)化技術(shù)研究 35-43 3.5.1 靜態(tài)優(yōu)化：例程深度優(yōu)化 38-41 3.5.2 動態(tài)優(yōu)化：例程再次派生實現(xiàn) 41-43 第四章 Cilk 并行遞歸程序數(shù)據(jù)重用模型 43-57 4.1

7、基于例程的并行遞歸數(shù)據(jù)重用模型 43-48 4.2 面向Cilk 應(yīng)用的并行遞歸數(shù)據(jù)重用模型 48-55 4.2.1 單層并行子遞歸例程模式 51-52 4.2.2 二層并行子遞歸例程模式 52-55 4.3 小結(jié) 55-57 第五章 Cilk 優(yōu)化技術(shù)編譯實現(xiàn)方案 57-69 5.1 靜態(tài)優(yōu)化編譯實現(xiàn)技術(shù)研究 57-67 5.1.1 Cilk 程序編譯詞法分析 59-61 5.1.2 Cilk 程序編譯語法分析及實現(xiàn) 61-67 5.2 動態(tài)優(yōu)化編譯實現(xiàn)方案研究 67-69 第六章 優(yōu)化模型實驗驗證 69-74 6.1 矩陣乘程序分析及性能測試 69-72 6.1.1 矩陣乘Cilk 實現(xiàn)及分