隨著多核體系結(jié)構的出現(xiàn)和快速發(fā)展,如何在多核體系結(jié)構上進行簡單高效的并行程序設計以充分利用多核所提供的并行性已變得日益重要。然而要在傳統(tǒng)的并行程序語言上編寫出高效的并行程序,程序員需要對底層細節(jié)和程序結(jié)構有清晰的認識。因此,需要有一種新的編程模型既能簡單的實現(xiàn)并行,同時又能高效的執(zhí)行。有研究指出利用分治法和遞歸模型能在實現(xiàn)這一目的的過程中起到很大的作用。目前有一種簡單的基于線程的并行程序設計語言——Cilk能自然的實現(xiàn)并行遞歸。作為對C語言的精簡擴展,程序員在編寫Cilk程序時,更多的關注于開發(fā)并行性和局部性,而不用關心底層的調(diào)度和負載均衡。但是我們研究中發(fā)現(xiàn),在并行度遠高于處理器個數(shù)的情況下,特別是并行遞歸程序,會因為派生過多的例程導致過多的開銷,甚至使并行程序的性能還不如串行程序,因此需要通過降低這部分開銷來優(yōu)化Cilk并行遞歸程序,以提高其性能。本文根據(jù)不同并行遞歸問題的計算過程,總結(jié)出其輔助性能模型。在該模型下,能推斷出例程派生開銷對程序性能的影響,進一步的可以推斷出減少這部分開銷后對并行遞歸程序的性能影響。本文首先對Cilk程序進行靜態(tài)優(yōu)化,包含并行度優(yōu)化和負載均衡優(yōu)化。并行... 

【文章來源】：國防科技大學湖南省 211工程院校 985工程院校

【文章頁數(shù)】：83 頁

【學位級別】：碩士

【部分圖文】：

計算fib(4)流程圖

當限制例程數(shù)最大值小于某臨界點時，第一次任務竊取后計算終會一直以串行副本執(zhí)行計算，而其他例程的計算任務 fi得該例程是整個計算過程中執(zhí)行計算時間最長的例程。在程其他處理器會不停的執(zhí)行任務竊取而且不斷失敗，從而從根果。此節(jié)點也就位于關鍵路徑之上，即便是在無窮多個處理如此，這也是導致'T 增加的根源所在，其結(jié)果必然導致負載夠大的 NUMTHREADS 也能解決這個問題，但是這樣的后果例程，會在一定程度上對提高性能起到副作用，這與優(yōu)化的，需要針對這個問題進一步優(yōu)化。原來的優(yōu)化方法降低了工作能，但是卻降低了均衡�，F(xiàn)在需要在原來限制例程派生數(shù)的，從而進一步的提高性能。 靜態(tài)優(yōu)化：例程深度優(yōu)化出了優(yōu)化后程序還存在的均衡問題，本節(jié)將進一步提高均衡

種基于線程的并行程序設計語言，能較好的應用于共過添加幾個關鍵字來指出并實現(xiàn)并行，不需要額外的體系結(jié)構中，不僅主存共享，一般而言末級 Cache 也常適合在目前的多核處理器上進行并行程序設計。在據(jù)重用模型后，我們將提出面向 Cilk 的并行遞歸程序4.1 基于例程的并行遞歸數(shù)據(jù)重用模型的模型中，并行執(zhí)行體的調(diào)度單位將是并行子遞歸例例程的并行遞歸數(shù)據(jù)重用。基于例程的并行遞歸數(shù)據(jù)并行子遞歸之間的關系。在 Cilk 程序中，并行子遞歸，因此，面向 Cilk 應用的并行遞歸數(shù)據(jù)重用理論將在間的關系。通過下圖可以看出基于例程的并行遞歸數(shù)的并行遞歸數(shù)據(jù)重用模型的關系。


本文編號：2915245