分布式圖處理系統(tǒng)的計算代價與通信效率優(yōu)化.pdf

1、隨著近些年電子信息和數(shù)據(jù)的爆炸性增長，分布式圖處理系統(tǒng)作為有效支持大規(guī)模圖數(shù)據(jù)處理的關(guān)鍵技術(shù)，獲得越來越多的關(guān)注。能效問題是分布式圖處理系統(tǒng)用戶和社會各界最為關(guān)注的問題之一，即用戶總是希望系統(tǒng)能夠用更少的計算節(jié)點在更短的時間內(nèi)完成他們的圖計算作業(yè)，從而有效地降低計算成本以及能耗。根據(jù)圖計算作業(yè)對時間敏感程度以及用戶擁有硬件資源的不同，不同類型用戶對高能效的需求也不同。對于高端用戶而言，他們擁有更多的計算資源和更充裕的資金支持，他們的圖計

2、算作業(yè)往往對時效性的要求也更高。因此，高端用戶希望通過提高圖計算速度來提高系統(tǒng)的能效，以達到更好的計算資源利用率。對于中低端用戶而言，更為關(guān)注硬件成本，他們往往希望在性能可接受的前提下，通過大幅減少系統(tǒng)規(guī)模來提高系統(tǒng)的能效。然而，由于現(xiàn)有分布式圖處理系統(tǒng)對計算機集群的計算、內(nèi)外存以及網(wǎng)絡(luò)等關(guān)鍵資源的單項或綜合利用率不高，導(dǎo)致系統(tǒng)性能不足或性價比不高，進而降低系統(tǒng)能效。主要原因是作業(yè)調(diào)度策略、計算模型、數(shù)據(jù)組織方式、編程模型以及通信機制的

3、效率不高。
　　由于圖計算作業(yè)對數(shù)據(jù)訪問的不規(guī)則性，分布式圖處理系統(tǒng)普遍采用基于內(nèi)存的計算模式。然而，現(xiàn)有基于內(nèi)存的分布式圖處理系統(tǒng)存在以下三個問題：一是當(dāng)處理大規(guī)模圖時，例如擁有幾千億條邊的圖，則需要一個大規(guī)模集群。高昂的硬件成本很大程度上約束了中低端用戶的大規(guī)模圖計算作業(yè)部署。二是高昂的通信開銷限制了系統(tǒng)的性能以及可擴展性。三是在預(yù)處理階段完成后的整個圖計算過程中，外存資源被閑置。針對現(xiàn)有基于內(nèi)存的分布式圖處理系統(tǒng)性價比不高的

4、問題，提出一種基于流水線的圖計算作業(yè)內(nèi)外存間任務(wù)調(diào)度策略，在小規(guī)模集群上采用流水線的方法在內(nèi)外存間調(diào)度大規(guī)模圖計算作業(yè)，使每個計算節(jié)點的磁盤I/O時間以及通信時間與其它計算節(jié)點的計算時間重疊，有效地隱藏了磁盤I/O時延和通信時延，使圖計算作業(yè)的執(zhí)行時間幾乎縮短到計算時間，同時達到低硬件成本和高性能，即獲得更高的系統(tǒng)能效?；谠撜{(diào)度策略實現(xiàn)了一個高性價比的分布式圖處理系統(tǒng)DD-Graph。實驗測試顯示：相對于GPS和Giraph而言，DD

5、-Graph節(jié)省了40％～75%的硬件成本，并且獲得約10%的性能提升。
　　基于(Bulk Synchronous Parallel，BSP)計算模型的分布式圖處理系統(tǒng)中以頂點為中心的子圖構(gòu)建方法以及計算與通信重疊的計算模型導(dǎo)致高昂的通信成本，約束了系統(tǒng)性能，進而降低能效。針對這一問題，提出一種基于邊數(shù)據(jù)塊子圖構(gòu)建方法的計算與通信分離計算模型LCC-BSP，將每個超步進一步劃分為計算步驟和通信步驟。這是因為我們觀察到圖計算作業(yè)計

6、算負(fù)載輕，計算步驟時間短，并且通信步驟可以采用高度并發(fā)的通信方式瞬時完成。通信步驟的高效性源于基于邊數(shù)據(jù)塊子圖構(gòu)建方法，它有效地避免了導(dǎo)致現(xiàn)有基于BSP計算模型的分布式圖處理系統(tǒng)高昂通信成本的四個因素：（1）高比例的附加通信量，用于攜帶目標(biāo)頂點名字；（2）用戶態(tài)數(shù)據(jù)遷移開銷，發(fā)送端和接收端各一次；（3）接收端消息塊的解析開銷；（4）低效率的通信技術(shù)?；贚CC-BSP計算模型，實現(xiàn)了一個高性能的分布式圖處理系統(tǒng)LCC-Graph。實驗結(jié)

7、果顯示：LCC-Graph比現(xiàn)有主流分布式圖處理系統(tǒng)快一個數(shù)量級。
　　隨著網(wǎng)絡(luò)技術(shù)的快速發(fā)展，高帶寬網(wǎng)絡(luò)已經(jīng)普遍存在。然而，現(xiàn)有主流分布式圖處理系統(tǒng)中以頂點為中心的編程模型以及以頂點為目標(biāo)的通信機制產(chǎn)生、發(fā)送、接收消息的速度太慢，導(dǎo)致高帶寬網(wǎng)絡(luò)資源不能被充分利用，延長了用戶等待時間。另外，在迭代式的圖計算作業(yè)執(zhí)行過程中，系統(tǒng)需要提供足夠內(nèi)存空間，用以緩存兩個相鄰超步的中間消息，導(dǎo)致內(nèi)存資源利用率低。針對這一問題，提出一種頂點間快

8、速消息產(chǎn)生及交換方法，通過兩項關(guān)鍵措施大幅提高了系統(tǒng)的性能及內(nèi)存利用率。一是提出一種精簡頂點計算量的快速消息產(chǎn)生編程模型，通過精簡每個頂點的工作負(fù)載，大大提高了消息產(chǎn)生速度。二是提出一種高內(nèi)存利用率的輕量級以消息為中心通信機制，通過減少每個消息的平均通信開銷，大幅提高消息的收發(fā)速度。另外，該通信機制不需要緩存兩個相鄰超步間的中間消息，大幅提高了內(nèi)存資源的利用率，使得相同規(guī)模的集群能處理更大規(guī)模的圖計算作業(yè)。對上述技術(shù)進行系統(tǒng)級實驗。實驗