基于低冗余迭代模式的高效圖處理系統(tǒng).pdf

1、圖數(shù)據(jù)結(jié)構(gòu)是對(duì)現(xiàn)實(shí)世界某些場(chǎng)景下的一種抽象形式。在圖上進(jìn)行圖計(jì)算，對(duì)圖進(jìn)行分析，是分析現(xiàn)實(shí)場(chǎng)景的一種重要的手段。目前出現(xiàn)了很多進(jìn)行圖算法計(jì)算的圖處理系統(tǒng)?，F(xiàn)有的圖處理系統(tǒng)主要采用同步迭代或異步迭代模式。然而，這些傳統(tǒng)的迭代模式受到迭代收斂的木桶效應(yīng)的影響，存在大量計(jì)算冗余。在大數(shù)據(jù)時(shí)代，大規(guī)模的圖數(shù)據(jù)使得計(jì)算冗余量非常巨大。造成圖處理系統(tǒng)處理速度緩慢，浪費(fèi)了大量的計(jì)算資源。
　　基于SCC-DAG（Directed Acyclic

2、 Graph composed of Strongly Connected Com-ponents）的迭代模式，將圖數(shù)據(jù)抽象成SCC（Strongly Connected Components）組成的DAG（Directed Acyclic Graph）結(jié)構(gòu)，以SCC為迭代計(jì)算單位，按照DAG順序進(jìn)行計(jì)算，減少了大量的計(jì)算冗余。基于SCC-DAG迭代模式的高并行核外圖處理系統(tǒng)，是SCC-DAG迭代模式的實(shí)現(xiàn)。一方面，實(shí)現(xiàn)了SCC-DAG

3、迭代模式的并行化處理方案。采用level算法實(shí)現(xiàn)了SCC間DAG的并行，采用以路徑為中心圖數(shù)據(jù)組織形式實(shí)現(xiàn)了SCC內(nèi)部的并行，同時(shí)區(qū)分不同大小的SCC實(shí)現(xiàn)了負(fù)載均衡。另一方面，實(shí)現(xiàn)了SCC-DAG迭代模式的核外計(jì)算方案。采用內(nèi)存映射的方案實(shí)現(xiàn)了對(duì)大量數(shù)據(jù)的高效訪問。采用基于SCC-DAG的順序存儲(chǔ)結(jié)構(gòu)和壓縮策略，減少了I/O數(shù)據(jù)量，提高了系統(tǒng)計(jì)算性能。
　　實(shí)驗(yàn)結(jié)果表明?；赟CC-DAG的迭代模式能夠有效減少傳統(tǒng)迭代模式的計(jì)算冗