[發(fā)明專利]一種基于SCC?DAG的圖計(jì)算迭代處理方法

在審

• 申請?zhí)枺?/td>: 201611070021.6
• 申請日: 2016-11-28
• 公開（公告）號(hào): CN106776858A
• 公開（公告）日: 2017-05-31
• 發(fā)明（設(shè)計(jì)）人: 廖小飛;金海;石翔;張宇;李陳希
• 申請（專利權(quán)）人: 華中科技大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 華中科技大學(xué)專利中心42201
• 代理人: 趙偉

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

本發(fā)明屬于計(jì)算機(jī)大數(shù)據(jù)處理的圖計(jì)算領(lǐng)域，更具體地，涉及一種基于SCC-DAG的圖計(jì)算迭代處理方法。

背景技術(shù)

“圖”是一種表達(dá)對(duì)真實(shí)世界中對(duì)象與對(duì)象之間的連接關(guān)系的數(shù)據(jù)結(jié)構(gòu)，基于圖的結(jié)構(gòu)運(yùn)行圖算法對(duì)圖進(jìn)行分析可得到其中包含的有用信息。譬如，通過PageRank算法可獲取圖中頂點(diǎn)的重要性；通過SSSP算法可獲取頂點(diǎn)間的最短路徑；這些算法通過多輪的迭代最終達(dá)到收斂的狀態(tài)；收斂狀態(tài)的數(shù)據(jù)即為算法運(yùn)行的結(jié)果。

迭代方法包括同步迭代和異步迭代；同步迭代方法基于傳統(tǒng)的BSP模型，嚴(yán)格的區(qū)分每一輪迭代的先后順序，下一輪迭代須等待上一輪迭代的完成；每一輪迭代都需要遍歷所有的圖數(shù)據(jù)一遍，當(dāng)多次遍歷圖后，圖達(dá)到收斂狀態(tài)。同步迭代存在以下問題：(1)負(fù)載不均衡：由于圖中頂點(diǎn)的邊數(shù)量的差異，帶來了圖頂點(diǎn)計(jì)算量的差異，每次迭代都需要等待整張圖遍歷完成，使得邊數(shù)量很少的頂點(diǎn)需要等待邊數(shù)量很大的頂點(diǎn)計(jì)算完成；(2)收斂緩慢，圖算法迭代收斂的本質(zhì)是根據(jù)圖中頂點(diǎn)鏈接的結(jié)構(gòu)，讓數(shù)據(jù)在頂點(diǎn)間得到充分傳遞；由于每一輪迭代是基于上一輪的迭代數(shù)據(jù)，使得每一輪的迭代操作只能夠?qū)?shù)據(jù)傳遞到頂點(diǎn)的鄰居頂點(diǎn)，數(shù)據(jù)傳遞效率慢，使得圖收斂緩慢。

異步迭代方法打破了BSP模型的屏障，迭代不再分為每一輪進(jìn)行，迭代的單位也不再是整張圖。當(dāng)某個(gè)頂點(diǎn)達(dá)到計(jì)算條件時(shí)，無需等待其它無關(guān)頂點(diǎn)的計(jì)算是否完成，即可立即開始計(jì)算。因此消除了負(fù)載不均衡的問題，也加速了數(shù)據(jù)在頂點(diǎn)間的傳遞。但異步迭代仍然存在以下問題：(1)計(jì)算不飽和：由于頂點(diǎn)滿足條件即可進(jìn)行計(jì)算，使得一些頂點(diǎn)在未積累夠足夠的數(shù)據(jù)，便開始計(jì)算，造成計(jì)算不飽和；(2)不穩(wěn)定：數(shù)據(jù)在頂點(diǎn)間的傳遞不是同時(shí)的，而是各自在頂點(diǎn)間的傳遞，造成數(shù)據(jù)在頂點(diǎn)間來回震蕩，無法有效的完成圖的收斂。

在大數(shù)據(jù)環(huán)境下，無論是同步迭代方法還是異步迭代方法，除了上述問題外，還面臨著一個(gè)巨大的問題--計(jì)算冗余；計(jì)算冗余體現(xiàn)在迭代收斂中的“木桶效應(yīng)”上。即在迭代時(shí)，大部分收斂的頂點(diǎn)會(huì)被少部分未收斂的頂點(diǎn)影響，變得不收斂，進(jìn)而每次迭代都需計(jì)算整張圖的大部分或全部，帶來大量的計(jì)算冗余，導(dǎo)致大量的CPU資源消耗。并且，在大數(shù)據(jù)環(huán)境下，圖數(shù)據(jù)的規(guī)模達(dá)到上百億甚至上千億條記錄，使得計(jì)算冗余也消耗了大量的IO資源，因?yàn)閮?nèi)存已經(jīng)無法滿足對(duì)圖數(shù)據(jù)的存儲(chǔ)，需要使用外設(shè)資源，繼而在迭代時(shí)存在大量的IO換入換出操作，造成巨大的IO資源消耗。

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

針對(duì)現(xiàn)有技術(shù)的以上缺陷或改進(jìn)需求，本發(fā)明提供了一種基于SCC-DAG(Strongly Connected Component-Directed Acyclic Graph)的圖計(jì)算迭代處理方法，其目的在于減小大數(shù)據(jù)環(huán)境下圖處理中同步迭代與異步迭代的計(jì)算冗余。

為實(shí)現(xiàn)上述目的，按照本發(fā)明的一個(gè)方面，提供了一種基于SCC-DAG的圖計(jì)算迭代處理方法，包括如下步驟：

(1)預(yù)處理：獲取給定的圖中所有的SCC，并對(duì)SCC進(jìn)行拓?fù)渑判?，根?jù)SCC的拓?fù)漤樞驑?gòu)建SCC-DAG；

(2)計(jì)算：按照SCC的拓?fù)漤樞蛞来卧赟CC-DAG的各SCC內(nèi)進(jìn)行迭代，直至所有SCC收斂。

本發(fā)明中，SCC(Strongly Connected Component)是指圖的強(qiáng)連通分量，是給定圖中的極大強(qiáng)連通子圖；給定的圖包括多個(gè)SCC；一個(gè)SCC也可以是一個(gè)頂點(diǎn)；

DAG(Directed Acyclic Graph)是指有向無環(huán)圖，是不存在環(huán)路的圖結(jié)構(gòu)；將DAG中的邊作為數(shù)據(jù)的流向，則DAG中的數(shù)據(jù)只會(huì)從“上游”流向“下游”；

在本發(fā)明中，對(duì)于給定的圖，首先把圖中所有的SCC找出來，然后將SCC抽象成點(diǎn)，由SCC之間的連接構(gòu)成DAG，將這種由強(qiáng)連通分量構(gòu)成的有向無環(huán)圖定義為SCC-DAG。

優(yōu)選地，上述基于SCC-DAG的圖計(jì)算迭代處理方法，其步驟(2)包括如下子步驟：

(2.1)根據(jù)SCC-DAG中SCC的拓?fù)漤樞驈乃鯯CC-DAG中選定一個(gè)SCC；

(2.2)在選定的SCC中執(zhí)行實(shí)際需求實(shí)現(xiàn)所對(duì)應(yīng)的算法，并采用同步迭代或異步迭代對(duì)每個(gè)頂點(diǎn)進(jìn)行計(jì)算；

步驟(2.1)中選定的SCC就是本步驟的迭代計(jì)算的對(duì)象；本步驟中執(zhí)行何種算法是由實(shí)際需求所決定的，與實(shí)際需求相應(yīng)；

譬如：若需要計(jì)算網(wǎng)頁排名，則實(shí)現(xiàn)pagerank算法；若需要計(jì)算最短路徑，則實(shí)現(xiàn)SSSP算法；