[發(fā)明專利]一種GPU上基于內(nèi)存統(tǒng)一管理的MapReduce實(shí)現(xiàn)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310710435.0
• 申請(qǐng)日: 2013-12-20
• 公開（公告）號(hào): CN103714009A
• 公開（公告）日: 2014-04-09
• 發(fā)明（設(shè)計(jì)）人: 金海;鄭然;劉凱;章勤;馮曉文
• 申請(qǐng)（專利權(quán)）人: 華中科技大學(xué)
• 主分類號(hào): G06F12/02
• 分類號(hào): G06F12/02;G06F17/30
• 代理公司: 華中科技大學(xué)專利中心 42201
• 代理人: 朱仁玲

1.一種GPU上基于內(nèi)存統(tǒng)一管理的MapReduce實(shí)現(xiàn)方法，其特征在于，包括以下步驟：?

（1）初始化GPU中塊的數(shù)量Bs、每個(gè)塊中的線程數(shù)目N、以及用戶的輸入數(shù)據(jù)量大小M；?

（2）為每個(gè)塊在全局內(nèi)存上分配中間數(shù)據(jù)緩沖區(qū)，對(duì)map計(jì)算生成的鍵值對(duì)進(jìn)行連續(xù)的歸約操作，通過在鍵值對(duì)的值中設(shè)置歸約次數(shù)和在計(jì)算中不斷累計(jì)，統(tǒng)計(jì)鍵值對(duì)出現(xiàn)的頻率信息，并根據(jù)出現(xiàn)頻率對(duì)鍵值對(duì)進(jìn)行排序，提取出高頻的鍵值對(duì)；?

（3）將步驟（2）得到的高頻鍵值對(duì)插入到共享內(nèi)存中，在任務(wù)處理中，通過使用標(biāo)記數(shù)組對(duì)全局內(nèi)存和共享內(nèi)存的分配進(jìn)行統(tǒng)一管理，且只有當(dāng)共享內(nèi)存資源使用完畢之后，才開始在全局內(nèi)存中分配空間。?

2.根據(jù)權(quán)利要求1所述的MapReduce實(shí)現(xiàn)方法，其特征在于，塊的數(shù)量Bs的取值范圍是1至30，線程數(shù)量N的取值范圍是32至512。?

3.根據(jù)權(quán)利要求1所述的MapReduce實(shí)現(xiàn)方法，其特征在于，步驟（2）包括以下子步驟：?

（2-1）在全局內(nèi)存上為GPU的每個(gè)塊分配大小為gm_size的中間數(shù)據(jù)緩沖區(qū)，同時(shí)分配一個(gè)大小為global_size的全局結(jié)果緩沖區(qū)和大小為num_sort的排序結(jié)果緩沖區(qū)sort_index[]，中間數(shù)據(jù)緩沖區(qū)和全局結(jié)果緩沖區(qū)中均包括索引數(shù)組buckets[]、內(nèi)存分配區(qū)gm_pool[]；?

（2-2）在共享內(nèi)存上設(shè)置針對(duì)全局結(jié)果緩沖區(qū)內(nèi)存分配的偏移數(shù)組global_offset[]和針對(duì)中間數(shù)據(jù)緩沖區(qū)內(nèi)存分配的偏移數(shù)組gm_offset[]；?

（2-3）初始化GPU的線程號(hào)tid、塊號(hào)bid、總線程數(shù)num_threads=Bs*N，將每個(gè)塊中的線程進(jìn)行分組，并獲取線程分組的數(shù)目num_groups=?num_threads/32，線程分組號(hào)gid=tid/32，偏移數(shù)組global_offset[]中每個(gè)線程分組的起始內(nèi)存分配地址global_object_offset[gid]=global_size*(gid+num_groups*bid)/(num_groups*Bs)，以及偏移數(shù)組gm_offset[]中每個(gè)線程分組的起始內(nèi)存分配地址gm_offset[gid]=gm_size*gid/num_groups；?

（2-4）設(shè)置計(jì)數(shù)器i=bid*N+tid；?

（2-5）判斷i是否小于M*p%，若是則轉(zhuǎn)入步驟（2-6），否則轉(zhuǎn)入步驟（2-11）；?

（2-6）每個(gè)線程分別取出輸入數(shù)據(jù)中的第i條記錄，并對(duì)第i條記錄執(zhí)行map計(jì)算，以生成鍵值對(duì)；?

（2-7）每個(gè)線程在對(duì)應(yīng)的中間數(shù)據(jù)緩沖區(qū)中查找是否已經(jīng)存在與步驟（2-6）相同鍵值的鍵值對(duì)，若是則轉(zhuǎn)入步驟（2-8），否則轉(zhuǎn)入步驟（2-9）；?

（2-8）對(duì)中間數(shù)據(jù)緩沖區(qū)中的鍵值對(duì)和步驟（2-6）生成的鍵值對(duì)執(zhí)行reduce計(jì)算，并在鍵值對(duì)的值中累計(jì)歸約次數(shù)；?

（2-9）在塊號(hào)bid對(duì)應(yīng)的中間數(shù)據(jù)緩沖區(qū)中的內(nèi)存分配區(qū)gm_pool[]中分配新的全局內(nèi)存空間，用于存放步驟（2-6）生成的鍵值對(duì)，在該鍵值對(duì)的值中初始化歸約次數(shù)為1，并將該鍵值對(duì)的偏移地址填入索引數(shù)組buckets[]中；?

（2-10）設(shè)置i=i+num_threads；然后返回步驟（2-5）；?

（2-11）所有線程進(jìn)行同步操作，并將所有塊對(duì)應(yīng)的中間數(shù)據(jù)緩沖區(qū)的鍵值對(duì)合并到全局結(jié)果緩沖區(qū)；?

（2-12）從全局結(jié)果緩沖區(qū)中的鍵值對(duì)中提取出現(xiàn)頻率較高的鍵值對(duì)，獲取該鍵值對(duì)的數(shù)量H，并將H個(gè)鍵值對(duì)在偏移數(shù)組global_offset[]中對(duì)應(yīng)的值保存在排序結(jié)果緩沖區(qū)sort_index[]中。?

4.根據(jù)權(quán)利要求3所述的MapReduce實(shí)現(xiàn)方法，其特征在于，步驟（2-12）中，所有鍵值對(duì)中出現(xiàn)頻率最高的5%-10%的鍵值對(duì)是高頻率的鍵?值對(duì)。?

5.根據(jù)權(quán)利要求1所述的MapReduce實(shí)現(xiàn)方法，其特征在于，步驟（3）包括以下子步驟：?

（3-1）重新初始化GPU每個(gè)塊對(duì)應(yīng)的中間數(shù)據(jù)緩沖區(qū)中索引數(shù)組buckets[]和內(nèi)存分配區(qū)gm_pool[]的所有元素為零，并在中間數(shù)據(jù)緩沖區(qū)中設(shè)置內(nèi)存分配標(biāo)記數(shù)組mem_flag[]；?

（3-2）在共享內(nèi)存中建立內(nèi)存分配區(qū)sm_pool[]，初始化內(nèi)存分配區(qū)sm_pool[]的偏移地址sm_offset=0，內(nèi)存分配區(qū)sm_pool[]的內(nèi)存占滿標(biāo)記sm_flag=0；?

（3-3）設(shè)置計(jì)數(shù)器i=tid；?

（3-4）判斷i是否小于H，若是則轉(zhuǎn)入步驟（3-5），否則轉(zhuǎn)入步驟（3-8）；?

（3-5）取出排序結(jié)果緩沖區(qū)sort_index[i]對(duì)應(yīng)的鍵值對(duì)，并將該鍵值對(duì)中的歸約次數(shù)初始化為0；?

（3-6）將步驟（3-5）得到的鍵值對(duì)存放在共享內(nèi)存的內(nèi)存分配區(qū)sm_pool[]中，，將該鍵值對(duì)的偏移地址填入索引數(shù)組buckets[]中，并在內(nèi)存分配標(biāo)記數(shù)組mem_flag[]中分配空間，并填入標(biāo)記1；?

（3-7）設(shè)置i=i+Bs，然后返回步驟（3-4）；?

（3-8）GPU的所有線程進(jìn)行同步操作；?

（3-9）設(shè)置i=tid+M*p%；?

（3-10）判斷i是否小于M，若是則轉(zhuǎn)入步驟（3-11），否則轉(zhuǎn)入步驟（3-21）；?

（3-11）每個(gè)線程分別取出輸入數(shù)據(jù)中的第i條記錄，并對(duì)第i條記錄執(zhí)行map計(jì)算，以生成鍵值對(duì)；?

（3-12）每個(gè)線程在對(duì)應(yīng)的中間數(shù)據(jù)緩沖區(qū)中查找是否已經(jīng)存在與步驟（3-11）相同鍵值的鍵值對(duì)，若是則轉(zhuǎn)入步驟（3-13），否則轉(zhuǎn)入步驟（3-17）；?

（3-13）獲取查找到的鍵值對(duì)的下標(biāo)k，判斷mem_flag[k]是否為1，若是則轉(zhuǎn)入步驟（3-14），否則轉(zhuǎn)入步驟（3-15）；?

（3-14）從內(nèi)存分配區(qū)sm_pool[]中取出查找到的鍵值對(duì)，然后轉(zhuǎn)入步驟（3-16）；?

（3-15）從內(nèi)存分配區(qū)gm_pool[]中取出查找到的鍵值對(duì)；?

（3-16）對(duì)中間數(shù)據(jù)緩沖區(qū)中的鍵值對(duì)和步驟（3-11）生成的鍵值對(duì)執(zhí)行reduce計(jì)算；?

（3-17）判斷內(nèi)存占滿標(biāo)記sm_flag是否為0，若是則轉(zhuǎn)入步驟（3-18），否則轉(zhuǎn)入步驟（3-21）；?

（3-18）在內(nèi)存分配區(qū)sm_pool[]中劃分新的空間，用于存放生成的鍵值對(duì)，將該鍵值對(duì)的偏移地址寫入索引數(shù)組buckets[]中，并在內(nèi)存分配標(biāo)記數(shù)組mem_flag[]中分配空間，并填入標(biāo)記1；?

（3-19）判斷內(nèi)存分配區(qū)sm_pool[]的空間是否占滿，若是則轉(zhuǎn)入步驟（3-20），否則轉(zhuǎn)入步驟（3-22）；?

（3-20）設(shè)置sm_flag=1，然后轉(zhuǎn)入步驟（3-22）；?

（3-21）在內(nèi)存分配區(qū)gm_pool[]中劃分新的空間，用于存放生成的鍵值對(duì)，將該鍵值對(duì)的偏移地址寫入索引數(shù)組buckets[]中，并在內(nèi)存分配標(biāo)記數(shù)組mem_flag[]中分配空間，并填入標(biāo)記0；?

（3-22）設(shè)置i=i+num_threads，然后返回步驟（3-10）；?

（3-23）GPU的所有線程進(jìn)行同步操作，并將所有塊對(duì)應(yīng)的中間數(shù)據(jù)緩沖區(qū)的鍵值對(duì)合并到全局結(jié)果緩沖區(qū)。?