一種基於負載平衡的cpu和gpu兩級動態任務劃分方法
2023-05-10 12:38:36 3
專利名稱：一種基於負載平衡的cpu和gpu兩級動態任務劃分方法
技術領域：
本發明涉及使用圖形處理單元GPU(Graphics Processing Unit，)加速科學計算的優化方法，尤指一種基於負載平衡的CPU和GPU兩級動態任務劃分方法。
背景技術：
GPU過去通常用於圖形圖像應用領域，隨著GPU硬體技術的不斷發展以及編程模型的發展，GPU強大的計算能力受到越來越多的重視，大量的科學計算程序都採用GPU加速其關鍵代碼段，獲得了良好的加速比。同時隨著CPU多核時代的到來，CPU的計算能力也在不斷增強，如果在GPU進行運算的同時，CPU也參與運算，將獲得更好的加速比。這種CPU+GPU異構系統的混合編程方法負載平衡是關鍵，如果劃分的任務不平衡，則將造成CPU或GPU中一方先完成，需要等待另一方任務完成，造成CPU或GPU空轉，使得整個任務完成時間延遲，從而降低了並行效率。
科學計算領域使用GPU加速是將整個應用程式劃分為多個CPU執行區和多個GPU加速區，CPU執行區的任務一般為應用程式的入口和出口、為GPU加速區準備數據、獲取GPU加速區的數據以及處理一些不適合在GPU上運行的任務，GPU加速區一般為數據密集型的並行任務，執行時間佔據整個應用程式的主要部分。一般GPU加速區由GPU單獨執行，此時CPU空閒。隨著多核CPU的出現，CPU的計算能力越來越強，為了利用空閒的CPU，出現了將GPU加速區任務在GPU和CPU上進行劃分然後並行執行的方法，目前這些方法已經比較成熟。不同的科學計算問題有不同的劃分方法。例如矩陣乘運算Cm×k＝Am×n×Bn×k，即矩陣Am×n乘以矩陣Bn×k，結果存在矩陣Cm×k中。這樣的運算可以劃分為兩個矩陣乘Cm0×k＝Am0×n×Bn×k和Cm1×k＝Am1×n×Bn×k，其中m0+m1＝m，Cm0×k和Cm1×k組合成為Cm×k。其中的一個矩陣乘在GPU上執行，另一個在CPU上執行。為了充分發揮多核CPU的性能，GPU加速區中CPU負擔的那部分任務將進一步劃分，每個CPU核負擔一部分任務，劃分方法與GPU與CPU間的劃分方法相同。問題的關鍵是如何確定劃分的比例，劃分比例將直接影響GPU與CPU、CPU各核之間的任務量，任務的不平衡會大大降低並行效率。目前，GPU與CPU之間的任務劃分比例通常按照GPU和CPU的理論或實測性能靜態確定，Massimiliano Fatica的論文「Accelerating Linpack withCUDA on heterogenous clusters」，Proceedings of 2nd Workshop on General PurposeProcessing on Graphics Processing Units，GPGPU 2009，Washington，DC，USA，March 8，2009，pp.46-51給出了一個劃分比例η＝Ggpu/(Ggpu+Gcpu)，即劃分到GPU上的任務佔總任務的比例為η，劃分到CPU上的任務佔總任務的比例為1-η，公式中Ggpu指GPU的實測性能，Gcpu指CPU的實測性能，單位都是Gflops(109次浮點運算每秒)。CPU核之間由於是同構關係，它們的任務劃分採用平均分配方法，即每個核負擔的任務量相同。但是這種靜態的任務劃分方法難以達到GPU與CPU、CPU各核之間的負載平衡。
CPU與GPU之間採用靜態方法進行任務劃分難以達到負載平衡的原因有兩個.第一，每個任務的問題規模各不相同，而GPU性能對問題規模十分敏感.問題規模與具體任務相關，指任務中需要處理的數據總量的相對值，可以有不同的度量.例如在矩陣乘(Am×n×Bn×k)中可以使用
也可以使用計算量m×n×k×2×10-9(單位GFLOPS，109次浮點運算)進行度量，在粒子碰撞模擬應用中可以使用模擬區域內的粒子數進行度量。第二，GPU性能受其他因素的影響較大，性能波動範圍大。如GPU與系統內存之間的通訊通過PCI-E總線傳輸，而CPU至GPU的PCI-E總線速度在實際測試中變化範圍可達2.5GB/秒至5.0GB/秒。
CPU各核之間採用平均分配方法難以達到負載平衡的原因是在CPU+GPU的異構平臺上各CPU核之間的處理能力有所不同，存在較大差異，可以分成三類。第一類CPU核只包含一個CPU核，主要負責與GPU進行數據傳輸，為了不影響GPU的運算，基本上不參與計算任務；第二類CPU核是與第一類CPU核具有共享cache的CPU核，包含一個或多個CPU核，它們的計算能力受第一類核的影響較大；第三類CPU核是除第一類和第二類以外剩餘的CPU核，與前兩類核不共享cache，受前兩類核的影響較小。如果平均分配任務，勢必會造成計算能力強的核任務不足而空閒，計算能力弱的核執行時間更長，而整個任務的完成時間以最後完成的CPU核為準，最終降低了CPU的整體性能。
綜上所述，目前在CPU+GPU的異構平臺上，使用GPU加速科學計算程序雖然有很多成功的方法，但仍存在下面兩個問題 1.CPU與GPU間的任務劃分比例採用靜態方法指定，造成CPU與GPU任務負載不平衡。
2.CPU核間的任務劃分比例採用平均分配方法，造成CPU核間任務負載不平衡。
目前針對上述問題，本領域技術人員都在探索如何找到一個動態任務劃分方法，在任務運行時自動調整CPU與GPU、CPU各核之間的任務劃分比例，達到整體負載平衡。
發明內容
本發明要解決的技術問題在於針對CPU和GPU之間、CPU核之間的任務負載不平衡問題，提出一種兩級動態任務劃分方法，實現CPU和GPU之間、以及CPU多核之間的任務負載平衡，提高科學計算程序利用GPU加速的性能。
本發明的技術方案為為CPU和GPU之間以及CPU多核之間的任務劃分建立兩個資料庫，記錄任務的劃分比例，其中CPU與GPU之間的任務劃分比例根據問題規模確定，在整個應用程式執行過程中根據CPU和GPU的實測性能自動調整任務劃分的比例，實現任務劃分的負載平衡。
採用Gsplit值定義GPU所分配的任務佔整個CPU和GPU並行任務的比例。採取按問題規模取值的方法解決Gsplit值隨問題規模變化的問題，同時根據實測性能不斷更新Gsplit值，從而達到GPU與CPU間任務負載平衡。使用資料庫定義多個問題規模範圍的Gsplit值，用於區分落在不同問題規模範圍內的Gsplit值。初始的多個Gsplit值是根據問題規模、CPU計算峰值、GPU計算峰值估計得到的，在反覆的任務運行過程中，根據實測的CPU和GPU的實際計算能力不斷更新各自問題規模下的Gsplit值，本次更新的Gsplit值又作為下一次CPU和GPU並行任務劃分的依據。
對於劃分為CPU完成的那部分任務，進一步在各CPU核之間進行任務劃分.如前所述，由於CPU和GPU協同計算，各個CPU核的計算能力並不相同，存在較大差異，進行靜態任務劃分不能充分挖掘各自的計算能力獲得好的負載平衡.同時，由於CPU各核的性能受問題規模影響較少，無需根據問題規模調整任務的劃分比例.用Csplit值定義CPU各核所分配的任務佔整個CPU並行任務的比例.具體方法如下為每個參與任務的CPU核建立任務劃分比例的資料庫，設參與任務的CPU核數為N，將每個CPU核對應的Csplit值初始化為1/N，即初始狀態下所有CPU計算任務平均分配到每個CPU核上.並行執行任務，同時統計各自完成的時間從而獲得各CPU核的實測性能.在反覆的任務運行過程中，根據實測的CPU核的實際計算能力不斷更新任務劃分的比例值，本次更新的值又作為下一次CPU核並行任務劃分的依據. 具體技術方案為 第一步、構建並初始化CPU-GPU間任務劃分比例資料庫DB1，DB1記錄M組不同問題規模下的Gspliti，i為整數且i∈
，M為正整數，取值範圍為50～200。記錄過多的問題規模會造成資料庫內容過多，查找和更新資料庫將耗費更多時間。另外，相近的問題規模對應其的Gsplit值也相近，記錄太多的問題規模也無必要。但是另一方面，記錄過少的問題規模將不能反映Gsplit值的變化趨勢，使得根據此資料庫取得的Gsplit值不能獲得很好的效果。構建資料庫DB1的具體步驟如下 1.1DB1包含M組問題規模的Gsplit值，其形式為{(F0，Gsplit0)，(F1，Gsplit1)，...，(FM-1，GsplitM-1)}，其中Fi＝g(i)，Gspliti∈
，Fi為記錄的問題規模，g(i)為記錄的問題規模的分布函數，是一個單調遞增函數，表示DB1第i項記錄的問題規模為g(i)，Gspliti表示問題規模F落在[Fi，Fi+1)範圍內的並行任務塊應採取的任務劃分比例因子，即比例為Gspliti的任務劃分在GPU上執行，比例為1-Gspliti的任務劃分在CPU上執行。當F≥FM-1時，任務劃分比例因子取值GsplitM-1。函數g(i)一般情況下可採用等間距分布函數g(i)＝a+b×i，其中a，b為常量。定義具體任務的問題規模範圍[Fmin，Fmax]，Fmin≤Fmax，Fmin指問題規模的下界，Fmax指問題規模的上界，當任務確定後，它們的值通過分析任務算法和流程計算獲得，或者通過模擬執行的方法統計獲得。根據Fmin和Fmax的值計算出a，b的值a＝Fmin，b＝(Fmax-Fmin)/(M-1)。
1.2初始化Gspliti值。
i ∈
，Pcpu為參與運算的CPU核的理論峰值性能，Pgpu為GPU的理論峰值性能。
第二步、構建並初始化CPU核間的任務劃分比例資料庫DB2，記錄參與執行任務的各CPU核所佔CPU總任務的比例。DB2為向量形式{Csplit0，Csplit1，…，CsplitN-1}，其中N為參與執行任務的CPU核數。Cspliti的初值為1/N，j∈
。
第三步、啟動應用程式。與通常應用程式運行相同。
第四步、執行應用程式CPU執行區代碼。與通常應用程式運行相同，完全在CPU上執行。
第五步、進入GPU加速區入口，計算此次並行任務的問題規模F和總的計算量S。計算量S為並行任務中的所有定點、浮點運算數目之和，可通過分析任務算法計算獲得或使用工具模擬任務的整個執行過程並進行統計獲得。
第六步、根據資料庫DB1的值進行CPU、GPU的任務劃分。搜索DB1，若F滿足F∈[Fi，Fi+1)，取得第i項中的Gspliti值；若F≥FM-1，Gspliti取值為GsplitM-1.將佔總任務的比例值為Gspliti的任務劃分到GPU，GPU上的計算量為Sgpu＝S×Gspliti，將佔總任務的比例值為1-Gspliti的任務劃分到CPU上，CPU上的計算量為Scpu＝S-S×Gspliti。
第七步、根據資料庫DB2的值進行CPU核之間的任務劃分。針對CPU上的每個核j，搜索資料庫DB2，取得第j項中的Csplitj值。劃分CPU核上的任務，方法是將佔總CPU任務的比例值為Csplitj的任務分給第j個核，第j個核的計算量為Scpu[j]＝(S-S×Gspliti)×Csplitj。
第八步、執行GPU加速區的並行任務，即將劃分好的GPU任務和CPU各核上的任務並行執行，同時記錄各自任務的執行時間。
第九步、同步GPU加速區的並行任務。等待各任務執行完畢，搜集各任務的執行時間(Tgpu，Tc
，Tc[1]，…，Tc[N-1])，其中Tgpu表示GPU上任務完成的時間，Tc[j]，j∈
表示第j個CPU核上任務完成的時間。Tcpu＝MAX(Tc
，Tc[1]，…，Tc[N-1])為CPU上的並行任務總的完成時間。
第十步、更新資料庫DB1。GPU的實測性能為
CPU的實測性能為
調整第六步根據問題規模F得到的Gspliti值，方法是計算
用GsplitiΔ值覆蓋資料庫DB1中對應的Gspliti值。
第十一步、更新資料庫DB2。每個CPU核的實測性能為
計算每個CPU核負擔的任務比例
用向量{Csplit0Δ，Csplit1Δ，…，CsplitN-1Δ}覆蓋資料庫DB2中的向量{Csplit0，Csplit1，…，CsplitN-1}。
第十二步、判斷應用程式是否結束，若結束，即應用程式中所有的任務執行完畢，則結束應用程式；若未結束，跳轉至第四步。
與現有技術相比，採用本發明可達到以下技術效果 1.大規模科學計算程序執行過程中，根據不同的問題規模選擇最合適的任務分配比例值Gsplit，Gsplit值在應用程式運行時不斷的自動修正，保證了CPU和GPU的任務負載平衡； 2.由於CPU各個核的計算能力差異，採用動態任務劃分方法自動調整每個核的任務比例值Csplit，充分挖掘每個核的計算能力，平衡每個核之間的任務負載，提高了多核CPU的性能。
圖1是本發明總體流程圖； 圖2是資料庫DB1記錄的不同問題規模下任務劃分比例的初值，以及應用程式運行後自動調整得到的劃分比例對比圖。
圖3是資料庫DB2記錄的不同CPU核上任務劃分比例的初值，以及應用程式運行後自動調整得到的劃分比例對比圖。
圖4是本發明方法與背景技術中的靜態劃分方法程序性能的比較圖。
具體實施例方式 圖1是本發明總體流程圖。本發明包括以下步驟 第一步、構建並初始化CPU-GPU間任務劃分比例資料庫DB1，DB1記錄M組不同問題規模下的Gspliti，i∈
值。
第二步、構建並初始化CPU核間的任務劃分比例資料庫DB2，記錄參與執行任務的各CPU核所佔CPU總任務的比例。
第三步、啟動應用程式。
第四步、執行應用程式CPU執行區代碼。
第五步、進入GPU加速區入口，計算此次並行任務的問題規模F和總的計算量S，計算量S包括並行任務中的所有定點、浮點運算。
第六步、根據資料庫DB1的值進行CPU、GPU的任務劃分。
第七步、根據資料庫DB2的值進行CPU核之間的任務劃分。
第八步、執行GPU加速區的並行任務。
第九步、同步GPU加速區的並行任務。
第十步、更新資料庫DB1。
第十一步、更新資料庫DB2。
第十二步、判斷應用程式是否結束，若結束，即應用程式中所有的任務執行完畢，則結束應用程式；若未結束，跳轉至第四步。
為了檢驗CPU、GPU的動態任務劃分效果，國防科大計算機學院在CPU+GPU的混合結構上進行了實驗驗證，具體配置為CPUIntel Xeon 5450，四核，頻率3.0GHz，雙精度浮點計算理論峰值48Gflops；GPU加速器ATI RADEON HD 4870×2，為了增加穩定性測試時使用了單卡，其核心頻率由750MHz降為625MHz，雙精度浮點計算理論峰值200Gflops；在該平臺上採用AMD CAL編程模型實現了雙精度浮點稠密矩陣乘加的GPU加速。測試的應用程式為HPLinpack2.0，程序的核心是使用LU分解方法求解稠密矩陣線性方程組，矩陣數據為隨機生成的雙精度浮點值。應用程式的主要輸入參數為N＝46000，NB＝1216，P＝Q＝1。GPU加速區為矩陣乘加運算(Am×n×Bn×k+Cm×n)，問題規模使用計算量m×n×k×2×10-9(單位GFLOPS，109次浮點運算)進行度量，通過分析任務的算法得到問題規模範圍為
。
測試時使用CPU中的一個核與GPU進行通訊，不參與運算，剩餘的三個核參與任務分配，總的峰值性能為(48/4)×3＝36Gflops。根據背景技術中介紹的靜態劃分方法，GPU所佔總任務的比例為200/(200+36)＝84.75％。採用本發明進行劃分時，步驟如下 第一步、構建並初始化CPU-GPU間任務劃分比例資料庫DB1，DB1記錄了50組不同問題規模下的Gspliti，i∈
值。具體步驟如下 1.1定義包含50組問題規模的Gsplit值的任務劃分比例資料庫DB1，{(F0，Gsplit0)，(F1，Gsplit1)，...，(F49，Gsplit49)}，其中Fi＝g(i)，Gspliti∈
，i∈
。g(i)＝a+b×i，根據問題規模範圍
確定Fmin＝0，Fmax＝4900。根據公式a＝Fmin，b＝(Fmax-Fmin)/(M-1)得到a＝0，b＝100，即g(i)＝100×i。最終定義的DB1為{(0，Gsplit0)，(100，Gsplit1)，(200，Gsplit2)，...，(4900，Gsplit49)} 1.2初始化Gspliti值。參與運算的CPU核的理論峰值性能Pcpu為36Gflops，GPU的理論峰值性能Pgpu為200Gflops。根據公式
得到
i∈
。
第二步、構建並初始化CPU核間的任務劃分比例資料庫DB2，記錄參與執行任務的各CPU核所佔CPU總任務的比例。參與執行任務的CPU核數N為3，平均分配任務，初始化DB2為向量形式{0.3333，0.3333，0.3334}。
第三步、啟動應用程式。
第四步、執行應用程式CPU執行區代碼。
第五步、進入GPU加速區入口，計算此次任務的問題規模F和總的計算量S。GPU加速區任務為矩陣乘加運算Am×n×Bn×k+Cm×n，m，n，k為傳給本任務的參數，問題規模F使用計算量m×n×k×2×10-9度量，計算量S＝F。
第六步、根據資料庫DB1的值進行CPU、GPU的任務劃分。搜索DB1，取得第i項中的Gspliti值，滿足F∈[Fi，Fi+1)；或者當F≥F49時，Gspliti取值Gsplit49。將佔總任務的比例值為Gspliti的任務劃分到GPU，GPU上的計算量為Sgpu＝S×Gspliti，將佔總任務的比例值為1-Gspliti的任務劃分到CPU上，CPU上的計算量為Scpu＝S-S×Gspliti。
第七步、根據資料庫DB2的值進行CPU核之間的任務劃分。針對CPU上的每個核j∈
，搜索資料庫DB2，取得第j項中的Csplitj值。劃分CPU核上的任務，方法是將佔總CPU任務的比例值為Csplitj的任務分給第j個核，第j個核的計算量為Scpu[j]＝(S-S×Gspliti)×Csplitj。
第八步、執行GPU加速區的並行任務。將劃分好的GPU任務和CPU各核上的任務並行執行，同時記錄各自任務的執行時間。
第九步、同步GPU加速區的並行任務。等待各任務執行完畢，搜集各任務的執行時間(Tgpu，Tc
，Tc[1]，Tc[2])。
第十步、更新資料庫DB1。GPU的實測性能為
CPU的實測性能為
計算
用GsplitiΔ值覆蓋資料庫DB1中對應的Gspliti值。
第十一步、更新資料庫DB2。每個CPU核的實測性能為
j∈
，計算每個CPU核負擔的任務比例
用向量{Csplit0Δ，Csplit1Δ，Csplit2Δ}覆蓋資料庫DB2中的向量{Csplit0，Csplit1，Csplit2}。
第十二步、判斷應用程式是否結束，若結束，即應用程式中所有的任務執行完畢，則結束應用程式；若未結束，跳轉至第四步。
圖2是國防科大所做上述實驗中資料庫DB1記錄的不同問題規模下任務劃分比例的初值，以及應用本發明後自動調整得到的劃分比例對比圖.橫坐標是問題規模F的分布，單位GFLOPS.縱坐標是GPU任務所佔的比例值.對於任意一個問題規模F，GPU任務所佔的比例值初始值均為0.8475，採用本發明後，應用程式會自動調整這個比例，達到任務的負載平衡.最終得到的比例值與初始值有所不同，並且隨問題規模變化. 圖3是資料庫DB2記錄的不同CPU核上任務劃分比例的初值，以及應用程式運行後自動調整得到的劃分比例對比圖。橫坐標是CPU核的編號，縱坐標是CPU核所佔CPU總任務的比例。最終每個核的劃分比例有所不同，分別為{0.3412，0.3290，0.3298}。
圖4是本發明方法與背景技術中的靜態劃分方法程序性能的比較圖。橫坐標表示使用背景技術的靜態劃分方法和使用本發明的動態劃分方法；縱坐標為測量的應用程式性能，單位為Gflops(109次浮點運算每秒)，由HPLinpack輸出文件得到。使用本發明時應用程式運行時間為389.25秒，性能為166.7Gflops；使用靜態劃分方法時應用程式執行時間為435.96秒，性能為148.8Gflops。使用本發明方法獲得的性能提升約為12.03％。
權利要求
1.一種基於負載平衡的CPU和GPU兩級動態任務劃分方法，所述GPU是指圖形處理單元，其特徵在於包括以下步驟
第一步、構建並初始化CPU-GPU間任務劃分比例資料庫DB1，DB1記錄M組不同問題規模下的Gspliti，i∈
，M為正整數；構建DB1的具體步驟是
1.1DB1的形式為{(Fx，Gsplit0)，(F1，Gsplit1)，...，(FM-1，GsplitM-1)}，其中Fi＝g(i)，Gspliti∈
，Fi為記錄的問題規模，g(i)為記錄的問題規模的分布函數，是一個單調遞增函數，DB1第i項記錄的問題規模為g(i)，Gspliti表示問題規模F落在[Fi，Fi+1)範圍內的並行任務塊應採取的任務劃分比例因子，即比例為Gspliti的任務劃分在GPU上執行，比例為1-Gspliti的任務劃分在CPU上執行；
1.2初始化Gspliti值，
Pcpu為參與運算的CPU核的理論峰值性能，
Pgpu為GPU的理論峰值性能；
第二步、構建並初始化CPU核間的任務劃分比例資料庫DB2，記錄參與執行任務的各CPU核所佔CPU總任務的比例，DB2為向量形式{Csplit0，Csplit1，…，CsplitN-1}，其中N為參與執行任務的CPU核數，Cspliti的初值為1/N，j∈
；
第三步、啟動應用程式；
第四步、執行應用程式CPU執行區代碼；
第五步、進入GPU加速區入口，計算此次並行任務的問題規模F和總的計算量S，計算量S為並行任務中的所有定點、浮點運算數目之和，通過分析任務算法計算獲得或使用工具模擬任務的整個執行過程並進行統計獲得；
第六步、根據資料庫DB1的值進行CPU、GPU的任務劃分搜索DB1，若F滿足F∈[Fi，Fi+1)，取得第i項中的Gspliti值；將佔總任務的比例值為Gspliti的任務劃分到GPU，GPU上的計算量為Sgpu＝S×Gspliti，將佔總任務的比例值為1-Gspliti的任務劃分到CPU上，CPU上的計算量為Scpu＝S-S×Gspliti；
第七步、根據資料庫DB2的值進行CPU核之間的任務劃分針對CPU上的每個核j，搜索資料庫DB2，取得第j項中的Csplitj值，劃分CPU核上的任務，方法是將佔總CPU任務的比例值為Csplitj的任務分給第j個核，第j個核的計算量為Scpu[j]＝(S-S×Gspliti)×Csplitj；
第八步、執行GPU加速區的並行任務，即將劃分好的GPU任務和CPU各核上的任務並行執行，同時記錄各自任務的執行時間；
第九步、同步GPU加速區的並行任務等待各任務執行完畢，搜集各任務的執行時間(Tgpu，Tc
，Tc[1]，…，Tc[N-1])，其中Tgpu表示GPU上任務完成的時間，Tc[j]，j∈
表示第j個CPU核上任務完成的時間，Tcpu＝MAX(Tc
，Tc[1]，…，Tc[N-1])為CPU上的並行任務總的完成時間；
第十步、更新資料庫DB1GPU的實測性能為
CPU的實測性能為
調整第六步根據問題規模F得到的Gspliti值，方法是計算
用GsplitiΔ值覆蓋資料庫DB1中對應的Gspliti值；
第十一步、更新資料庫DB2每個CPU核的實測性能為
計算每個CPU核負擔的任務比例
用向量{Csplit0Δ，Csplit1Δ，…，CsplitN-1Δ}覆蓋資料庫DB2中的向量{Csplit0，Csplit1，…，CsplitN-1}；
第十二步、判斷應用程式是否結束，若結束，即應用程式中所有的任務執行完畢，則結束應用程式；若未結束，跳轉至第四步。
2.如權利要求1所述的一種基於負載平衡的CPU和GPU兩級動態任務劃分方法，其特徵在於當問題規模F≥FM-1時，任務劃分比例因子Gspliti取值為GsplitM-1。
3.如權利要求1所述的一種基於負載平衡的CPU和GPU兩級動態任務劃分方法，其特徵在於函數g(i)採用等間距分布函數g(i)＝a+b×i，其中a，b為常量，a＝Fmin，b＝(Fmax-Fmin)/(M-1)，Fmin指問題規模的下界，Fmax指問題規模的上界，任務的問題規模範圍為[Fmin，Fmax]，Fmin≤Fmax，當任務確定後，Fmin和Fmax的值通過分析任務算法和流程計算獲得，或者通過模擬執行的方法統計獲得。
4.如權利要求1所述的一種基於負載平衡的CPU和GPU兩級動態任務劃分方法，其特徵在於M取值範圍為50～200。
全文摘要
本發明公開了一種基於負載平衡的CPU和GPU兩級動態任務劃分方法，要解決的技術問題在於實現CPU和GPU之間、CPU多核之間的任務負載平衡。技術方案是為CPU和GPU之間以及CPU多核之間的任務劃分建立兩個資料庫，記錄任務的劃分比例，其中CPU與GPU之間的任務劃分比例根據問題規模確定，且在整個應用程式執行過程中根據CPU和GPU的實測性能自動調整任務劃分的比例，實現任務劃分的負載平衡。採用本發明既能保證CPU和GPU的任務負載平衡，提高科學計算程序利用GPU加速的性能，又能平衡CPU每個核之間的任務負載，提高多核CPU的性能。
文檔編號G06F9/50GK101706741SQ20091022718
公開日2010年5月12日 申請日期2009年12月11日 優先權日2009年12月11日
發明者廖湘科, 王 鋒, 楊燦群, 陳娟, 杜雲飛, 易會戰, 黃春, 趙克佳 申請人:中國人民解放軍國防科學技術大學