[發(fā)明專利]一種GPU上MapReduce的負載分配和線程結(jié)構(gòu)優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 201410323420.3
• 申請日: 2014-07-08
• 公開（公告）號: CN104156268B
• 公開（公告）日: 2017-07-07
• 發(fā)明（設(shè)計）人: 郭兵;沈艷;王繼禾;陳輝;馬群;楊奔;盛志遠;黃勇;張放;陳英超
• 申請（專利權(quán)）人: 四川大學(xué)
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06T1/20
• 代理公司: 暫無信息
• 代理人: 暫無信息

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

本發(fā)明涉及嵌入式系統(tǒng)以及數(shù)據(jù)并發(fā)領(lǐng)域，尤其是涉及一種基于GPU上MapReduce的負載分配和線程結(jié)構(gòu)優(yōu)化方法。

背景技術(shù)

各種高性能計算加速器的成功，圖形處理單元(GPU)，現(xiàn)場可編程門陣列(FPGA)，以及英特爾Xeon處理器(Intel Xeon Phi)。由于加速器在計算能力、內(nèi)存帶寬、高度并行和能效等方面的優(yōu)勢，從數(shù)據(jù)中心領(lǐng)域到嵌入式系統(tǒng)領(lǐng)域，這些加速器已經(jīng)越來越受到重視。然而，在這些平臺上編程仍然具有很大的挑戰(zhàn)性。開發(fā)商必須使用特定加速器的編程語言，例如CUDA，OpenCL和Verilog等。

近年來，上述加速器中，GPU在高性能計算和嵌入式計算領(lǐng)域中獲得了很大的成功。由于采用大規(guī)模并行架構(gòu)，GPU線程能夠成百上千地并發(fā)執(zhí)行。GPU的計算能力已應(yīng)用到包括圖像處理、電子自動化設(shè)計、密碼學(xué)等在內(nèi)的眾多方法中。

本發(fā)明的研究重點是使用MapReduce模型來設(shè)計高性能的GPU應(yīng)用程序。設(shè)計GPU上的高性能MapReduce框架并非易事，主要難點在于性能調(diào)整和設(shè)計參數(shù)的選擇。在MARS(目前GPU上最先進的MapReduce框架)中，線程結(jié)構(gòu)(例如線程塊數(shù)、每塊的線程數(shù))由占用率確定。占用率定義為GPU上的活動線程數(shù)與允許的最大線程數(shù)之比。使用占用率為衡量標準，MARS趨向于高度的并行性。然而，最近的一項研究表明，高度的并行可能會獲得次優(yōu)的性能。由于GPU性能取決于單個線程的性能以及多個線程的并行程度，而高并行可能會導(dǎo)致單個線程占用的計算資源較低，從而降低了單個線程的性能，如果高并行產(chǎn)生的性能不足以彌補單個線程所損失的性能，則整體性能就能會降低。此外，并行程度高，還可能會導(dǎo)致嚴重的資源爭用，例如共享cache和內(nèi)存，從而降低單線程性能和整體性能。

MapReduce通常用于數(shù)據(jù)密集型應(yīng)用，處理大量的輸入數(shù)據(jù)。由于受到內(nèi)存大小的限制，當數(shù)據(jù)量較大時，MapReduce需要多輪處理，每輪處理一個數(shù)據(jù)塊數(shù)據(jù)。本發(fā)明將負載分配定義為選擇最佳的數(shù)據(jù)塊大小來提高性能。數(shù)據(jù)塊大小決定每輪處理的時間和需要處理的總輪數(shù)。數(shù)據(jù)塊小可能會使得GPU利用率低，而數(shù)據(jù)塊大則可能會導(dǎo)致資源爭用。因此，在GPU中負載分配是非常重要的。然而，MARS框架忽略了負載分配的重要性。

負載分配和線程結(jié)構(gòu)需要協(xié)同考慮，才能使得GPU取得最佳性能。當我們將這兩方面結(jié)合起來時，發(fā)現(xiàn)這是一個巨大的設(shè)計空間。例如，考慮大小為1TB的數(shù)據(jù)和一個可以執(zhí)行多達數(shù)千個線程塊、每個塊1024個線程的現(xiàn)代GPU，假設(shè)每個線程都可以處理1KB的數(shù)據(jù)，則總設(shè)計空間包含大約10^7個解決方案。強力搜索(即運行或模擬每個解決方案)最優(yōu)解是不可能的。同時，我們觀察到這樣的設(shè)計空間其實是非常不規(guī)則、不平滑的，所以不太可能會有非常好的性能模型能夠直接模擬這種設(shè)計空間。

針對這些難點，本發(fā)明提出了一種新的方法。該方法能夠非常有效而準確地為MapReduce框架找出數(shù)據(jù)塊大小和線程結(jié)構(gòu)兩個性能參數(shù)。我們觀察到，當負載分配固定時，性能與線程結(jié)構(gòu)間的關(guān)系可以精確地建模為表面平滑的多項式函數(shù)。在此時間函數(shù)的基礎(chǔ)上，本發(fā)明設(shè)計一個結(jié)合數(shù)據(jù)塊大小和線程結(jié)構(gòu)的分層搜索方法。

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

本發(fā)明的目的在于提供一種基于GPU上MapReduce的負載分配和線程結(jié)構(gòu)優(yōu)化方法。

本發(fā)明解決其技術(shù)難題所采用的技術(shù)方案的步驟如下：

1)heir-archical搜索方法的提出

定義MapReduce框架的輸入數(shù)據(jù)大小為H。由于在GPU有限的內(nèi)存空間，將H分割(split)為許多塊，每次處理一個塊。定義數(shù)據(jù)塊大小為D，因此，總共需要次來處理整個數(shù)據(jù)H。假定只有一個GPU，處理每個塊的時間為t_Dt_D，則輸入數(shù)據(jù)H的總處理時間為[H/d]×t_Dt_D。對于一個特定的基于MapReduce框架的應(yīng)用程序，其線程的負載(數(shù)據(jù)大小)一般由程序員決定。用d表示每個線程的負載(工作量)，則可以得出D/d＝x×y，其中x和y是線程塊的數(shù)量和每個塊中線程的數(shù)量。