[發明專利]基于圖相似性分析的異構可重構任務劃分信息處理方法

有效

• 申請號: 201110440675.4
• 申請日: 2011-12-23
• 公開（公告）號: CN102902588A
• 公開（公告）日: 2013-01-30
• 發明（設計）人: 曾國蓀;王偉;郝水霞
• 申請（專利權）人: 同濟大學;上海紅神信息技術有限公司
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 上海科盛知識產權代理有限公司 31225
• 代理人: 趙志遠

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

1)給定計算任務TG＝(V，E，H，W，C)，異構可重構體系結構圖AG＝(P^*，E^*，H^*，W^*，C^*)，其中V表示任務節點，E表示任務間通信關系，H表示異構特征，W表示任務計算量，C表示通信量；P^*表示處理器節點，E^*表示處理器之間的通信關系，H^*表示處理器的異構特征，W^*表示處理器的計算能力，C^*表示處理器之間的通信能力；

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

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

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

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

2.根據權利要求1所述的一種基于圖相似性分析的異構可重構任務劃分信息處理方法，其特征在于，所述的TG利用貪心算法找到與AG共同的最大子圖CurG具體步驟為：

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

3.根據權利要求1所述的一種基于圖相似性分析的異構可重構任務劃分信息處理方法，其特征在于，所述的找一個起始點V₂，并依次加入其相鄰的邊和頂點，最終形成G₂具體為：

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