[發(fā)明專利]一種交互式并行化編譯系統(tǒng)及其編譯方法

有效

• 申請(qǐng)?zhí)枺?/td>: 200910153082.2
• 申請(qǐng)日: 2009-09-30
• 公開（公告）號(hào): CN101667135A
• 公開（公告）日: 2010-03-10
• 發(fā)明（設(shè)計(jì)）人: 李瑩;孫煦雪;袁新宇;徐印成
• 申請(qǐng)（專利權(quán)）人: 浙江大學(xué)
• 主分類號(hào): G06F9/45
• 分類號(hào): G06F9/45;G06F9/38
• 代理公司: 杭州裕陽專利事務(wù)所（普通合伙）
• 代理人: 應(yīng)圣義

技術(shù)領(lǐng)域

本發(fā)明涉及編譯技術(shù)，更具體地說涉及一種交互式并行化編譯系統(tǒng)及編譯 方法。

背景技術(shù)

隨著片上多核處理器時(shí)代的到來，如何使應(yīng)用程序在多核體系結(jié)構(gòu)下獲得 好的性能，已成為一個(gè)研究熱點(diǎn)。加快應(yīng)用程序的執(zhí)行速度的方法主要有兩種： 一種是程序員顯式使用并行編程技術(shù)來開發(fā)應(yīng)用程序，該方法由于受限于現(xiàn)有 語言模型的局限性和求解問題的復(fù)雜度，沒能得到大規(guī)模的推廣；另一種就是 依賴于并行編譯器自動(dòng)或半自動(dòng)地將串行程序并行化。

串行程序并行化是并行處理領(lǐng)域研究的熱點(diǎn)問題，也是高性能計(jì)算領(lǐng)域需 要解決的問題之一。并行化分為全自動(dòng)并行化和交互式并行化兩種模式。近年 來，人們?cè)诓⑿谢碚摵蛯?shí)用方法兩方面都取得了一些進(jìn)展，出現(xiàn)了一些全自 動(dòng)并行化系統(tǒng)，如UIUC(伊利諾伊大學(xué)厄本那-香檳分校)的Polaris， Stanford(斯坦福)的SUIF，復(fù)旦大學(xué)的AFT等。這些全自動(dòng)并行化系統(tǒng)，通過 采用過程間分析、符號(hào)數(shù)據(jù)相關(guān)性分析、數(shù)組私有化、歸約識(shí)別、復(fù)雜形式的 歸納變量識(shí)別以及運(yùn)行時(shí)分析等技術(shù)，不需要人為干預(yù)，可以自動(dòng)發(fā)現(xiàn)程序中 可并行的部分來生成并行代碼，具有一定的并行化能力。但是，由于在全自動(dòng) 并行化系統(tǒng)中使用的并行化算法還不能有效地處理復(fù)雜的應(yīng)用程序，以及無法 有效處理多個(gè)拆分后的小程序之間的依賴關(guān)系并同時(shí)保持原有串行程序語義， 導(dǎo)致編譯的實(shí)際效果不太理想。這類全自動(dòng)并行化系統(tǒng)主要應(yīng)用在科學(xué)計(jì)算， 不能適用于如桌面應(yīng)用、多媒體以及服務(wù)器等更廣泛的領(lǐng)域。交互式并行化系 統(tǒng)則是通過給用戶提供程序中的有效信息，包括相關(guān)性分析結(jié)果、程序調(diào)用圖、 性能預(yù)測(cè)結(jié)果等幫助用戶進(jìn)行并行化工作，例如Greenwich(格林威治大學(xué))大 學(xué)的CAPTools，Rice大學(xué)的Fortran?D系統(tǒng)和Applied?Parallel?Research(應(yīng) 用并行計(jì)算研究所)公司的Forge90等均是交互式并行化系統(tǒng)。這些交互式并 行化系統(tǒng)，在盡可能采取自動(dòng)并行化技術(shù)的同時(shí)，允許在并行化過程中人為查 看和修改并行化結(jié)果，通過利用人工的能力來提高并行化效果，在部分程度上 彌補(bǔ)了全自動(dòng)并行化系統(tǒng)的不足。但是，上述交互式并行化系統(tǒng)普遍都沒有采 用最新的自動(dòng)并行化技術(shù)，而且其交互方法以及與用戶間協(xié)作的緊密性有待提 高，因此，它們的并行化效果在現(xiàn)行多核體系結(jié)構(gòu)下仍然不夠理想。

發(fā)明內(nèi)容

本發(fā)明所要解決的技術(shù)問題是提出一種提供友好的交互手段、使用戶與編 譯器緊密協(xié)作、并結(jié)合最新的先進(jìn)并行化技術(shù)、并使串行應(yīng)用程序在多核體系 結(jié)構(gòu)下獲得好的性能的交互式并行化編譯系統(tǒng)及其編譯方法。

本發(fā)明為解決其技術(shù)問題提供了一種交互式并行化編譯系統(tǒng)，包括基于編 譯器，通過與用戶交互來對(duì)串行程序編譯為可由計(jì)算機(jī)的多核處理器來并行處 理的裝置，所述編譯器為Eclipse編譯器；所述交互式并行化編譯系統(tǒng)還包括： 交互式并行化插件，用于與用戶交互來獲取交互信息，交互式并行化引擎接收 所述交互信息并進(jìn)行自動(dòng)化程序分析，確定串行程序的計(jì)算結(jié)構(gòu)特性的裝置； 交互式并行化引擎，用于交互式并行化插件與用戶交互獲取交互信息，對(duì)所述 線性任務(wù)計(jì)算，根據(jù)交互信息建立開銷模型，采用基于圖模型理論方法，對(duì)程 序圖模型進(jìn)行劃分和調(diào)度，以挖掘粗粒度任務(wù)級(jí)并行性，對(duì)所述遞歸任務(wù)計(jì)算， 采用分治算法，使用并行庫對(duì)程序進(jìn)行變換，對(duì)所述規(guī)則數(shù)據(jù)流計(jì)算，根據(jù)交 互信息建立性能模型，采用仿射劃分算法對(duì)程序進(jìn)行變換，獲得流水級(jí)并行， 對(duì)所述特定計(jì)算，采用開銷驅(qū)動(dòng)、基于采樣和反饋的用戶經(jīng)驗(yàn)信息指導(dǎo)的投機(jī) 多線程并行化方法挖掘其并行性，并將并行化結(jié)果傳遞給所述交互式并行化插 件，以及Eclipse編譯器顯示并行化結(jié)果的裝置。