[發明專利]自動并行化多級并行代價評估方法

有效

• 申請號: 201310153710.3
• 申請日: 2013-04-27
• 公開（公告）號: CN103246541A
• 公開（公告）日: 2013-08-14
• 發明（設計）人: 趙榮彩;龐建民;韓林;徐金龍;傅立國
• 申請（專利權）人: 中國人民解放軍信息工程大學
• 主分類號: G06F9/45
• 分類號: G06F9/45
• 代理公司: 鄭州大通專利商標代理有限公司 41111
• 代理人: 陳大通

1.一種自動并行化多級并行代價評估方法，其特征在于：包含如下步驟：

步驟1、粗粒度自動并行化代價評估，面向分布存儲結構的消息通信自動并行化進行代價收益分析，即MPI收益代價評估；

步驟2、中粒度自動并行化代價評估，面向共享存儲結構的自動并行化進行代價收益分析，即OpenMP收益代價評估；

步驟3、細粒度自動并行化代價評估，面向短向量運算部件的自動向量化進行代價收益分析，即SIMD收益代價評估；

步驟4、對上述三種粒度的并行收益進行綜合，得到總的并行收益。

2.根據權利要求1所述的自動并行化多級并行代價評估方法,其特征在于:所述

步驟1還包含包含如下步驟：

步驟1.1、基于計算數組的并行代價預評估，包含內容如下：

步驟1.1.1、首先對源程序分析獲得包含有數組生命周期的定義-引用圖G（V，E）；

步驟1.1.2、根據定義-引用圖G（V，E），計算源程序中任一數組的主導值；

設數組x，源程序中數組x的定義次數為i，對其定義-引用圖添加數組生命周期標志將其劃分成若干子圖G1、G2……Gi；

在任意子圖G_m中，設定義循環為u_m，共有j次引用，其中任一引用循環為v_mn，數組x的數據集合表示數組x從v向上暴露于u的數組區域，數組x的數據集合expose[vmn]uxm]]>代表定義-引用邊(um,vmn,expose[vmn]uxm)]]>的權重，ψ(x,v)是數組x在循環v中的外層無關索引的迭代總數，則數組的主導值表示為：

Wx=Σm=1m=iΣn=1n=j(um,vmn,expose[vmn]uxm);]]>

步驟1.1.3、用數組主導值進行代價預評估，選擇并行代價相對較小的數組予以劃分，獲得預并行的循環，即預并行區域；

步驟1.2、循環代價精準評估，由主導值代價評估得到預劃分的循環，即預并行區域，并行精確代價為并行計算代價、并行通信代價和網絡擁塞代價的疊加，計算公式如下：

設并行計算代價為S_p，并行通信代價為S_c，網絡阻塞代價為S_b，則并行精確代價為：

S=S_p+S_c+S_b

設目標計算系統的原子計算代價為S_cell，原子計算總量為amount_comp，則循環串行的計算代價為S_s=S_cell*amount_comp，設計算系統擁有np個計算結點，將循環的串行計算代價均分給每個計算結點，則并行計算代價為：

Sp=Ssnp=Scell*amount_compnp]]>

一次通信的代價為該次通信步代價與此次通信通信步總量的乘積，設第i次消息傳遞的步代價為T_i，原子通信代價為T_cell，原子通信總量為amount_comm，則此次通信的步代價T_i=T_cell*amount_comm，

設計算系統擁有的進程數為np，通信方式為組內全通信，則消息傳遞的步總量為step_i=log2^np，則此次通信的代價為：

S_i=T_i*step_i；

通信次數為n，循環的通信代價為：

Sc=Σi=1nSi=Σi=1nTi*stepi]]>

計算網絡擁塞代價，通過對計算系統網絡多次性能測試，測得其次通信平均代價D，通信次數為n，循環的網絡擁塞代價為：

Sb=Σi=1nDi=n*D;]]>

步驟1.3、計算出預并行區域的并行精確代價S后，與串行代價S_s進行對比，評估并行收益，判斷是否對源程序中預并行化區域予以并行化執行。