基于并行架構(gòu)的大規(guī)模圖著色算法
完整資料進(jìn)入【數(shù)字空間】查看——baidu搜索"writebug"
摘 要
隨著當(dāng)前信息時(shí)代的日益發(fā)展，數(shù)據(jù)量的逐漸增大，大規(guī)模圖數(shù)據(jù)的處理在網(wǎng)頁搜索應(yīng)用，社交網(wǎng)絡(luò)和交通網(wǎng)絡(luò)等場景中作用也愈發(fā)明顯。因此，大規(guī)模圖著色的研究也開始成為高性能計(jì)算領(lǐng)域的熱點(diǎn)。而通用GPU（Graphics Processing Unit）的發(fā)展使其作用逐漸廣泛，用于圖著色的加速也成了一種研究的趨勢。但調(diào)研后，現(xiàn)有的較廣泛的并行圖著色均存在以下問題中的部分或全部：反復(fù)著色，在著色時(shí)，后續(xù)迭代輪次中頂點(diǎn)顏色會(huì)導(dǎo)致已著色頂點(diǎn)顏色出錯(cuò)，需要重新修改；并行度不夠，每輪著色中，正確的著色頂點(diǎn)比例稀少；長尾問題，在著色最后，每輪著色頂點(diǎn)數(shù)大幅度減少；負(fù)載不均衡，每個(gè)線程運(yùn)行時(shí)間開銷相差過大，導(dǎo)致整體性能較差。
設(shè)計(jì)的新的基于并行架構(gòu)的圖著色算法，解決了反復(fù)著色，并行度不夠以及長尾的問題。首先，預(yù)處理圖數(shù)據(jù)，將其變成只有小編號(hào)頂點(diǎn)指向大編號(hào)頂點(diǎn)的有向圖，避免了反復(fù)著色，也確保了算法能在有限輪次后終止。此外，配合使用CSR和CSC的存儲(chǔ)格式保存圖數(shù)據(jù)，可以做到一定程度的連續(xù)訪存，并減少修正工作一半的工作量。其次，著色過程采用無沖突的并行著色思路，每一輪分為著色和修正兩個(gè)步驟，提高了并行度，并可以避免原子操作。最后，在未著色頂點(diǎn)數(shù)剩余極少時(shí)，避免多次迭代，將著色策略變成串行，解決長尾問題。
本算法使用CUDA C語言編程設(shè)計(jì)完成，提供了針對(duì)不同的圖數(shù)據(jù)的接口參數(shù)。通過在相同環(huán)境下針對(duì)普遍的大規(guī)模圖數(shù)據(jù)進(jìn)行的實(shí)驗(yàn)，結(jié)果表明，該算法相較于CPU下的貪心著色算法有1.51-125.81倍的性能提升，相較于JPL（Jones-Plassman-Luby）有8.37-71.07倍的性能提升。
關(guān)鍵詞：圖著色；圖形處理器；并行運(yùn)算技術(shù)；兩階段
一、緒 論
本章我們首先介紹了當(dāng)前發(fā)展圖著色算法的目的以及意義，介紹了國內(nèi)外在圖著色領(lǐng)域的相關(guān)研究工作，并對(duì)算法的主要研究內(nèi)容及工作意義作了具體說明，最后簡略介紹了論文的整體結(jié)構(gòu)。
1.1 課題背景
當(dāng)前，隨著互聯(lián)網(wǎng)的大規(guī)模普及，社會(huì)面向數(shù)字化的變遷以及經(jīng)濟(jì)的迅猛發(fā)展，表達(dá)數(shù)據(jù)之間關(guān)聯(lián)性的圖數(shù)據(jù)的規(guī)模正在呈指數(shù)級(jí)增長。由于圖計(jì)算能夠用于分析數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系，因此其在互聯(lián)網(wǎng)應(yīng)用、科學(xué)計(jì)算、社會(huì)計(jì)算、商業(yè)計(jì)算等諸多領(lǐng)域得到應(yīng)用廣泛，已經(jīng)成為大數(shù)據(jù)處理的主流模式之一。而圖的著色算法便是其中的一種，其在時(shí)間規(guī)劃調(diào)度，頻道分配問題安全裝箱問題等實(shí)際問題方面有著極為重要的作用，其中與圖著色聯(lián)系最緊密，實(shí)際應(yīng)用最為廣泛的即為寄存器分配技術(shù)。比如，相交圖（interference graph）是用來表示程序變量是否擁有相交的生命期的。而一個(gè)寄存器同時(shí)只能被一個(gè)變量使用，如果用顏色表示寄存器，用頂點(diǎn)表示變量，該問題可抽象成一個(gè)圖著色問題。
研究表明，在眾多的圖著色算法中，啟發(fā)式算法和基于貪婪法的算法能夠獲得較好的著色數(shù)。然而，基于貪婪法的圖著色算法具有O(n^2)的時(shí)間復(fù)雜度。由于實(shí)際圖的大小不斷增長，即使是具有線性時(shí)間的算法也需要求助于并行計(jì)算來縮減實(shí)際的求解時(shí)間。
