基于混合著色算法的GPU異步圖計(jì)算系統(tǒng).pdf

1、大規(guī)模圖數(shù)據(jù)處理已經(jīng)成為大數(shù)據(jù)時(shí)代的一個(gè)重要組成部分，無(wú)論是在社交網(wǎng)絡(luò)，還是在Web應(yīng)用、生物信息網(wǎng)絡(luò)等場(chǎng)景中都有所涉及。圖計(jì)算系統(tǒng)的研究，也因此成為了高性能計(jì)算領(lǐng)域的熱點(diǎn)。隨著通用GPU技術(shù)的發(fā)展，GPU被用來(lái)加速圖數(shù)據(jù)的處理成為了一種趨勢(shì)。然而通過(guò)調(diào)研發(fā)現(xiàn)，當(dāng)前的GPU圖計(jì)算系統(tǒng)以同步處理模型為基礎(chǔ)，這種處理模型需要在每次迭代執(zhí)行之后，同步所有頂點(diǎn)的更新數(shù)據(jù)，然而由于數(shù)據(jù)劃分不均衡，導(dǎo)致同步過(guò)程開銷巨大，也減緩了圖算法的收斂速度，同

2、時(shí)不能高效利用GPU的并行計(jì)算能力。
　　采用異步處理模型的GPU圖計(jì)算系統(tǒng)Frog，解決了迭代過(guò)程同步開銷大、GPU并行計(jì)算能力受限、算法收斂速度慢的問(wèn)題。首先，F(xiàn)rog采用異步處理模型，在保證異步處理過(guò)程中數(shù)據(jù)一致性的同時(shí)，避免了當(dāng)前系統(tǒng)中存在的同步通信開銷；其次，F(xiàn)rog采用基于混合著色算法的數(shù)據(jù)劃分策略，通過(guò)對(duì)所有頂點(diǎn)進(jìn)行混合著色處理，整合計(jì)算任務(wù)少的頂點(diǎn)，保證在GPU的每個(gè)更新窗口中都有足夠的計(jì)算任務(wù)在執(zhí)行，從而提高GP

3、U的并發(fā)資源利用率；最后，F(xiàn)rog通過(guò)加快迭代計(jì)算過(guò)程中消息的傳遞速度，從而使所有頂點(diǎn)都能夠訪問(wèn)到最新的更新值，進(jìn)而加快圖算法的收斂速度。此外，F(xiàn)rog通過(guò)對(duì)超出GPU內(nèi)存的圖進(jìn)行分塊處理，保證每個(gè)數(shù)據(jù)塊都能夠適應(yīng)GPU內(nèi)存大小，從而有效地處理超大規(guī)模的圖數(shù)據(jù)。
　　Frog以CUDA語(yǔ)言為基礎(chǔ)進(jìn)行編程設(shè)計(jì)，并提供了開放的API接口，使得用戶可以方便地進(jìn)行GPU編程。實(shí)驗(yàn)表明，F(xiàn)rog比現(xiàn)有的GPU圖計(jì)算系統(tǒng)能夠獲得3.2倍以上的