[發(fā)明專利]基于圖相似性分析的異構(gòu)可重構(gòu)任務(wù)劃分信息處理方法

有效

• 申請?zhí)枺?/td>: 201110440675.4
• 申請日: 2011-12-23
• 公開（公告）號: CN102902588A
• 公開（公告）日: 2013-01-30
• 發(fā)明（設(shè)計）人: 曾國蓀;王偉;郝水霞
• 申請（專利權(quán)）人: 同濟(jì)大學(xué);上海紅神信息技術(shù)有限公司
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 上海科盛知識產(chǎn)權(quán)代理有限公司 31225
• 代理人: 趙志遠(yuǎn)

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

本發(fā)明涉及一種計算機(jī)任務(wù)的劃分信息處理方法，尤其是涉及一種基于圖相似性分析的異構(gòu)可重構(gòu)任務(wù)劃分信息處理方法。

背景技術(shù)

異構(gòu)可重構(gòu)計算是目前高性能計算中一種新的體系結(jié)構(gòu)，是一種基于同構(gòu)體系結(jié)構(gòu)新的發(fā)展。異構(gòu)可重構(gòu)計算是基于異構(gòu)可重構(gòu)計算是目前高效能并行計算的最典型的模式。要實(shí)現(xiàn)計算任務(wù)在體系結(jié)構(gòu)高效能的運(yùn)行，關(guān)鍵是要將計算任務(wù)合理的分配到相應(yīng)的異構(gòu)可重構(gòu)計算系統(tǒng)上，充分利用異構(gòu)部件特性。如何實(shí)現(xiàn)計算任務(wù)有效的分配及運(yùn)行，首先需要將計算任務(wù)實(shí)現(xiàn)合理劃分。目前還沒有直接顯示劃分的有效辦法，但任務(wù)劃分是并行計算的首要步驟，也是高效能計算設(shè)計的關(guān)鍵步驟，任務(wù)劃分策略的好壞直接影響到負(fù)載平衡性、通信復(fù)雜度、任務(wù)間的依賴性以及任務(wù)間的同步方式和同步頻繁程度等。

通常任務(wù)劃分的方法有遞歸劃分、功能劃分、數(shù)據(jù)劃分、探測性劃分等等，這些方法在宏觀上解決了計算任務(wù)的顯示劃分。在微觀上，常用的技術(shù)方法有圖劃分，超圖劃分技術(shù)等。其中利用DAG圖進(jìn)行任務(wù)劃分是最典型的方法。DAG的劃分方法目前已經(jīng)有很多，例如圖的等分劃分技術(shù)，各種啟發(fā)式的任務(wù)劃分方法。這些方法在一定程度上解決了同構(gòu)系統(tǒng)的任務(wù)劃分。但是異構(gòu)可重構(gòu)計算和傳統(tǒng)的并行計算的最大區(qū)別在于處理器異構(gòu)，系統(tǒng)可重構(gòu)，僅從計算任務(wù)來進(jìn)行任務(wù)劃分而不考慮實(shí)際的并行系統(tǒng)的異構(gòu)及重構(gòu)情況，就會造成資源浪費(fèi)，系統(tǒng)利用率降低，不能充分發(fā)揮系統(tǒng)的性能。

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

本發(fā)明的目的就是為了克服上述現(xiàn)有技術(shù)存在的缺陷而提供一種基于圖相似性分析的異構(gòu)可重構(gòu)任務(wù)劃分信息處理方法。

本發(fā)明的目的可以通過以下技術(shù)方案來實(shí)現(xiàn)：

一種基于圖相似性分析的異構(gòu)可重構(gòu)任務(wù)劃分信息處理方法，其特征在于，包括以下步驟：

1)給定計算任務(wù)TG＝(V，E，H，W，C)，異構(gòu)可重構(gòu)體系結(jié)構(gòu)圖AG＝(P^*，E^*，H^*，W^*，C^*)V表示任務(wù)節(jié)點(diǎn)，E表示任務(wù)間通信關(guān)系，H表示異構(gòu)特征，W表示任務(wù)計算量，C表示通信量；P^*表示處理器節(jié)點(diǎn)，E^*表示處理器之間的通信關(guān)系，H^*表示處理器的異構(gòu)特征，W^*表示處理器的計算能力，C^*表示處理器之間的通信能力；

2)在TG利用貪心算法找到與AG共同的最大子圖CurG；

3)將這個子圖作為G₁加入TG劃分集P，并將此子圖從TG中刪除；

4)在剩余的TG中，找一個起始點(diǎn)V₂，并依次加入其相鄰的變和頂點(diǎn)，最終形成G₂，將G₂加入TG劃分集P，并將此子圖從TG中刪除，依次類推，劃分完整個TG，直至最后的G_k+1與AG的相似度小于設(shè)定的閾值；

3)最終形成AG的劃分集P＝{G₁，G₂，…，G_k}。

所述的TG利用貪心算法找到與AG共同的最大子圖CurG具體步驟為：

首先對AG和TG分別進(jìn)行寬度優(yōu)先遍歷得到A，B子序列，然后確定A在B中的位置，此位置在TG的點(diǎn)即為V₁；若記CurG＝{V₁}，逐步將B的子串加入CurG，若和V₁關(guān)聯(lián)，直接將其加入CurG中，否則找下一個字母，直至遍歷完B的子串。

所述的找一個起始點(diǎn)V₂，并依次加入其相鄰的邊和頂點(diǎn)，最終形成G₂具體為：

首先對AG和TG-CurG分別進(jìn)行寬度優(yōu)先遍歷得到A，B子序列，然后確定A在B中的位置，此位置在TG-CurG的點(diǎn)即為V₂；并記G₂＝{V₂}，逐步將B的子串加入G₂，若和V₂關(guān)聯(lián)，直接將其加入G₂中，否則找下一個字母，直至遍歷完B的子串。

與現(xiàn)有技術(shù)相比，本發(fā)明具有以下優(yōu)點(diǎn)：

1、借鑒傳統(tǒng)圖相似理論，提出通過圖相似分析計算任務(wù)和體系結(jié)構(gòu)內(nèi)在的聯(lián)系，用兩者之間的存在部分相似關(guān)系來彌補(bǔ)計算任務(wù)和體系結(jié)構(gòu)不匹配的情況。