[發明專利]一種基于深度圖分割的并行自定義指令選擇方法

有效

• 申請號: 201910394132.X
• 申請日: 2019-05-13
• 公開（公告）號: CN111367526B
• 公開（公告）日: 2023-06-02
• 發明（設計）人: 肖成龍;王晶玥;王珊珊
• 申請（專利權）人: 遼寧工程技術大學
• 主分類號: G06F8/41
• 分類號: G06F8/41;G06F9/30
• 代理公司: 北京華夏正合知識產權代理事務所(普通合伙) 11017
• 代理人: 陳曉寧;王雪飛

1.一種基于深度圖分割的并行自定義指令并行選擇方法，其特征在于，包括步驟：

A、根據候選自定義指令之間的重疊和循環約束為候選自定義指令構建出原始相容圖；

B、通過將原始相容圖分割成相似大小的若干子圖，以將初始問題分割為若干個子問題；

所述初始問題為自定義指令選擇問題，對應到求解原始相容圖的帶權最大團；所述子問題對應到求解子圖的帶權最大團；

C、主節點將生成的若干子問題分配并發送給對應的若干空閑計算節點；

D、每個計算節點各自運行分支定界算法計算出所分配的子問題的最優解，即在其子圖中求解出帶權最大團；

E、主節點收集各個計算節點的計算結果，獲得對應各子圖的各帶權最大團，據此確定出所選的自定義指令；

其中，所述候選自定義指令的定義包括：設S＝{S₁,S₂,...,S_n}是由自定義指令枚舉生成的一組自定義指令，子圖S_i表示所述候選自定義指令；

其中，所述自定義指令選擇問題的定義包括：每個子圖S_i所表示的候選自定義指令獲得的性能增益用P_i表示時，所述自定義指令選擇問題定義為：

問題P：給定一組候選子圖S＝{S₁,S₂,...,S_n}，從S中找到最佳子集C，使最大化整體性能增益同時滿足以下約束：

·所選子圖不重疊，即非重疊約束：

·所選子圖不為彼此提供數據，即非循環性約束：

或

·所選自定義指令的總面積不超過給定的硬件面積限制，即面積約束；

其中Pred(S_j)和Succ(S_j)分別代表S_j的前驅節點集合和后繼節點集合；

其中，所述相容圖是由G＝(V,E)表示的無向圖，其中V是一組由{v₁,v₂,...,v_n}表示的n個頂點的集合，E是由{e₁,e₂,...,e_m}表示的m個邊的集合，G的密度用ρ(G)＝2|E|/(|V|*(|V|-1))來表示；每個團是G的子圖，其中所有頂點之間存在一條邊；最大團MC是具有最多頂點數目的團；帶權最大團MWC是所有頂點權重和最大的團；G中頂點v的相鄰頂點由τ(v,G)＝{w|(v,w)∈E}表示；G_v表示由τ(v,G)導出的子圖；表示子圖的相鄰頂點；ω(C)表示團C的權重；

其中，步驟B包括：

首先，采用貪心算法生成一個貪心解；其中，在生成貪心解的過程中，定義一個G'，其初始值為G，并使G'中的所有頂點按權重的降序排序，在貪心算法的每次迭代中選擇G'中排序為第一的頂點v，并將G'更新為G_v，直到不再有頂點為止；生成的貪心解可用于得到貪心團的權重；

之后，通過將原始相容圖分割成若干子圖來劃分初始問題P，其中給定初始圖G＝(V,E)時，初始問題P被劃分為下述一組子問題：

P₁＝F(v₁∪τ(v₁,G))

P₂＝F(v₂∪τ(v₂,G-{v₁}))

P₃＝F(v₃∪τ(v₃,G-{v₁,v₂}))

...,

P_k＝F(v_k∪τ(v_k,G-{v₁,…,v_k-1}))

...,

P_n＝F(v_n∪τ(v_n,G-{v₁,...,v_n-1}))；

其中n是G中的頂點數，子問題P_k定義為從子圖v_k∪τ(v_k，G-{v₁，...，v_k-1})中尋找帶權最大團，通過上述分割將初始問題P分為|V|個子問題；

其中，如果生成的子圖中帶權最大團的上限小于先前生成的貪心團的權重，則終止對應該子圖的子問題的繼續計算；

其中，上述生成的子問題具有不同的復雜度導致負載不均衡時，首先，采用運行時間預測模型來預測每個子問題的帶權最大團算法的運行時間，其中帶權最大團算法的運行時間與圖G中的節點數及G的密度相關；其中，從給定圖中找出帶權最大團最壞的運行時間是T(G)＝O(α|V|)，其中α是常數，假設：

T(G)＝f(|V|,ρ(G))^|V|；

其中|V|和ρ(G)分別表示圖G中的節點數和G的密度，f(|V|，|E|)是指數函數；

對f(|V|，|E|)進行泰勒級數展開，得到：

其中k是用于控制模型中的擴展程度的參數,a_ij是通過對實驗獲得的數據進行擬合確定的參數；

通過每個子問題的預測運行時間，判斷計算節點是否被分配了具有相似復雜度的子問題，在當前分割結果不能保證負載均衡時，將具有較高預測運行時間的子問題分割為若干較小的子問題，包括：對于給定的一個子問題P_k，如下將其劃分為較小的子問題：

P_k,1＝F({v_k,u₁}∩τ(u₁,G_k-{v_k}))

P_k,2＝F({v_k,u₂}∩τ(u₂,G_k-{v_k,u₁}))

P_k,3＝F({v_k,u₃}∩τ(u₃,G_k-{v_k,u₁,u₂}))

...，

P_k,l＝F({v_k,u_l}∩τ(u_l,G_k-{v_k,u₁,...,u_l-1}))

...,

P_k,m＝F({v_k,u_m}∩τ(u_m,G_k-{v_k,u₁,...,u_m-1}))；

其中G_k＝τ(v_k,G-{v₁,…,v_k-1})；

其中，步驟D包括：

每個計算節點使用分支定界算法從分割子圖中找到帶權最大團，其中，單個計算節點上解決帶權最大團問題的分支定界算法包括：

該算法通過從G＝(V,E)遞歸地添加頂點來增長團C，且使用一個全局變量LB記錄當前找到的帶權最大團；該算法首先通過調用estimatedUB(G)函數來計算帶權最大團的上限UB，然后將UB與LB進行比較，以判斷是否可以避免進一步搜索，如果需要進一步搜索，則從最大權重的G中選擇一個頂點，對于G中任何選定的頂點v，G的帶權最大團是G_v中的團或是G-{v}中的團；

其中，所述estimatedUB(G)函數用來計算G中帶權最大團的上限，包括：首先采用基于著色的方法得到G中最大團的頂點數目上限，然后將最大團的頂點數目上限乘以G中頂點的最大權重來計算帶權最大團的上限。