分布式主存系統(tǒng)上自動(dòng)數(shù)據(jù)和計(jì)算分解和相關(guān)研究.pdf

1、數(shù)據(jù)和計(jì)算分解是并行化的基礎(chǔ)，對應(yīng)的數(shù)據(jù)分布和計(jì)算劃分是并行化編譯的重要組成部分。 自動(dòng)數(shù)據(jù)分布需要同時(shí)考慮程序的并行性、局部性、目標(biāo)機(jī)器特性、后端編譯器優(yōu)化等一系列問題。這大大增加了自動(dòng)數(shù)據(jù)分布的復(fù)雜性和難度。采用整數(shù)線性規(guī)劃方法的自動(dòng)數(shù)據(jù)分布框架可以擁有更好的目標(biāo)程序適應(yīng)性，不過前人的方案存在復(fù)雜度高，性能模型不夠精確的缺點(diǎn)。針對這些問題，我們提出了一種新的高實(shí)用性的自動(dòng)數(shù)據(jù)分布框架。該框架提供了對多維分布、多分割分布方式、

2、多層流水并行的發(fā)掘以及動(dòng)態(tài)重分布的支持，具有高性能，可擴(kuò)展性和低開銷等特點(diǎn)，因而有比較高的實(shí)用性 部分重復(fù)計(jì)算劃分是計(jì)算劃分階段進(jìn)行的重要優(yōu)化，可以有效的減少節(jié)點(diǎn)間通信和同步，從而提高程序的性能和可擴(kuò)展性。前人的研究工作局限于一個(gè)循環(huán)套的范圍，并且沒有性能模型的支持。我們擴(kuò)展了原有部分重復(fù)計(jì)算劃分的優(yōu)化范圍，給出了顯式的性能模型和求解方法。 本文主要貢獻(xiàn)如下： 1．提出基于并行性和數(shù)據(jù)依賴關(guān)系的樹形程序分解方法，

3、提高了大范圍統(tǒng)一數(shù) 據(jù)分布情況下的性能估計(jì)精度，在候選產(chǎn)生算法中，對每一個(gè)程序片斷只產(chǎn)生一 個(gè)局部最優(yōu)的數(shù)據(jù)分布方式，從而大大降低了算法的復(fù)雜性。利用附屬階段等方 法，適應(yīng)實(shí)際應(yīng)用中常見的一些特色，降低了問題復(fù)雜度。 2．提出自動(dòng)進(jìn)行基于拉丁方格的多分割數(shù)據(jù)分布方式，對多維的流水并行性提 供了更好的支持，能夠自動(dòng)搜索優(yōu)化的處理器空間配置。 3．給出具有以上特色的求解全局自動(dòng)數(shù)據(jù)分布的整數(shù)線性規(guī)劃求解框架。

4、 4．給出廣義的部分重復(fù)計(jì)算的概念，擴(kuò)展了部分重復(fù)計(jì)算劃分的優(yōu)化范圍。從 全局范圍的部分重復(fù)計(jì)算劃分、利用可用數(shù)組區(qū)域的部分重復(fù)計(jì)算劃分、多層次 部分重復(fù)計(jì)算劃分等方面，說明新定義所提供的優(yōu)化機(jī)會(huì)。 5．提出了相應(yīng)的線性性能模型，采用基于定義點(diǎn)的冗余通信檢測方法來估計(jì)通信優(yōu)化的作用。此方法在自動(dòng)數(shù)據(jù)分布和部分重復(fù)計(jì)算劃分中都有所應(yīng)用。 6．給出了一種解決此問題的啟發(fā)式框架，能夠比較有效的解決一大類應(yīng)用程序的部分重復(fù)計(jì)