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

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

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

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

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

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

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

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

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