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

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

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

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