發(fā)布時間：2014-07-27 06:32

                                                                                                                                                                                      

摘要： 目前在并行計算研究領域中很大一部分工作是將串行程序并行化，本文根據(jù)題目的要求，在合理的假設下，首先發(fā)掘串行程序中存在的并行性，一個好的方法就是構(gòu)造其對應的并行任務（DAG）圖，論文分析了串行程序中存在的數(shù)據(jù)依賴關(guān)系，并以此為根據(jù)，提出了一種由現(xiàn)有的串行程序構(gòu)造對應的并行任務（DAG）圖的算法，然后再對剩下的串行程序分段，提出并行劃分模型，基于這種模型提出了一種并行劃分算法PDMA；并根據(jù)程序段的相關(guān)程度提出了一種對PDMA進行改進的并行劃分算法RPDMA。然后再通過一個串性程序的實例，運用此方案對其進行運算，最后對串行程序運算下的時間復雜度和進行此方案運算下的時間復雜度進行比較，得出此方案的優(yōu)越。

　　1.問題的重述

　　并行計算是將一個計算任務分攤到多個處理器上并同時運行的計算方法。由于單個CPU的運行速度難以顯著提高，所以計算機制造商試圖將多個CPU聯(lián)合起來使用。在計算機上早已采用專用的多處理器設計，臺式機和筆記本電腦現(xiàn)在也已廣泛地采用了雙核或多核CPU。雙核CPU從外部看起來是一個CPU，但是內(nèi)部有兩個運算核心，它們可以獨立進行計算工作。在同時處理多個任務的時候，筆耕論文新浪博客，多核處理器可以自然地將不同的任務分配給不同的核心。最容易被并行化的計算任務稱為“易并行”的，它可以直觀地立即分解成為多個獨立的部分，并同時執(zhí)行計算問題。

　　要求：

　�。�1）運行一個以常規(guī)的串行代碼寫成的程序時，如何將計算任務拆分成多個部分并分解到多個核心上同時運行。

　�。�2）建立合理有效的模型，并依據(jù)模型對現(xiàn)成的串行算法進行處理。將能夠使用雙核心并行處理的部分分解開，并分配到兩個核心上同時運行。以期達到比單核CPU處理更快速的目的。

　　2.模型的假設

　　1.忽略硬件及環(huán)境因素，假設每次執(zhí)行時硬件條件和環(huán)境條件是完全一致的。

　　2.對算法的時間復雜度并不考慮其精確度量,而只是關(guān)心其量級

　　3.雙核及多核CPU在運算時,互不干擾.

　　4.設文中的算法最終得到的DAG圖中消除了原有的反依賴和輸出依賴.

　　3.問題分析

　　由于單個CPU的運行速度難以顯著提高，所以現(xiàn)在廣泛采用了雙核或多核CPU,如何將一個常規(guī)的串行程序分解成兩部分，使之能夠同時采用了雙核或多核CPU，雙核CUP內(nèi)部的兩個運算核心可以獨立進行工作，并且希望能夠充分發(fā)揮雙核心的計算能力。首先我們根據(jù)任務之間存在的數(shù)據(jù)依賴以及控制依賴關(guān)系，將先發(fā)掘串行程序中存在的并行性，從而減少了直接將串行程序并行化的復雜度，也提高了效率。然后再針對剩下的串行程序進行并行化處理，從而使它的效率達到更理想的狀態(tài)．

　　現(xiàn)在的問題是：

　�。ǎ保┤绾握业揭粋�好的方法去發(fā)掘串行程序中的存在的并行性；

　�。ǎ玻┰O計一種將串行程序并行劃分的模型，再基于這個模型提出一種并行劃分算法．

　　4.建模前的準備

　　4.1對于一個輸入的串行程序, 我們首先發(fā)掘串行程序中存在的并行性構(gòu)造其對應的并行任務DAG圖. 構(gòu)造DAG圖的時候, 主要的一個問題就是發(fā)現(xiàn)任務之間的依賴關(guān)系. 本文首先對任務之間存在的一種依賴關(guān)系作一個簡單的介紹。
 

 

本文編號：7617