本文選題：外存模式圖處理系統(tǒng) + 多任務(wù)�。� 參考：《華中科技大學(xué)》2016年碩士論文

【摘要】：圖處理系統(tǒng)正被廣泛的應(yīng)用于各個(gè)領(lǐng)域的數(shù)據(jù)分析中,隨著圖處理任務(wù)的增加,它們需要有效的應(yīng)對多任務(wù)環(huán)境�，F(xiàn)有的圖處理系統(tǒng)一般針對單一任務(wù)設(shè)計(jì),在執(zhí)行并行任務(wù)時(shí)存在圖數(shù)據(jù)的重復(fù)和數(shù)據(jù)訪問帶寬的競爭。內(nèi)存模式圖處理系統(tǒng)節(jié)點(diǎn)間的交換數(shù)據(jù)為圖處理任務(wù)私有,執(zhí)行并行任務(wù)時(shí)對網(wǎng)絡(luò)帶寬的競爭是系統(tǒng)的瓶頸�，F(xiàn)有的外存模式圖處理系統(tǒng)可以避免網(wǎng)絡(luò)通信開銷,但是并行任務(wù)對圖數(shù)據(jù)訪問的不一致易造成I/O爭用,影響性能。通過對現(xiàn)有外存模式圖處理系統(tǒng)I/O優(yōu)化方法的分析,提出了基于I/O去重、圖數(shù)據(jù)共享的數(shù)據(jù)訪問模型,從理論上論證了在面對并行任務(wù)時(shí)相對于傳統(tǒng)模型的優(yōu)勢與局限性�；谠撃Ｐ�,設(shè)計(jì)并實(shí)現(xiàn)了面向多任務(wù)環(huán)境的外存模式圖處理系統(tǒng)GraphDeSh。GraphDeSh通過對外存數(shù)據(jù)的統(tǒng)一訪問消除了I/O重復(fù),通過共享緩存的設(shè)計(jì)平衡了并行任務(wù)執(zhí)行速度的差異,優(yōu)化了并行任務(wù)的數(shù)據(jù)等待時(shí)間。使用不同的數(shù)據(jù)集和不同的算法組合測試了GraphDeSh的性能,驗(yàn)證了基于I/O去重、圖數(shù)據(jù)共享的模型的有效性。測試結(jié)果顯示,兩任務(wù)GraphDeSh相對于傳統(tǒng)的并行方式,最大達(dá)到了理想的2倍加速比。GraphDeSh的優(yōu)化效果隨著圖算法的計(jì)算比例下降而下降,平均加速比為1.45倍。在不同數(shù)據(jù)集上,GraphDeSh的加速比相對于并行GraphChi的加速比提高了32.5%-60.7%,相對于并行X-Stream的加速比提高了84.5%-107.1%。
[Abstract]:Graph processing systems are widely used in data analysis in various fields. With the increase of graph processing tasks, they need to deal with multi-task environment effectively. The existing graph processing systems are generally designed for a single task, and there is duplication of graph data and competition of data access bandwidth when executing parallel tasks. The exchange of data between nodes of the memory pattern graph processing system is private to the graph processing task, and the competition of network bandwidth when executing parallel tasks is the bottleneck of the system. The existing memory schema graph processing system can avoid network communication overhead, but the inconsistency of parallel task to graph data access can cause I / O contention and affect performance. Based on the analysis of the existing I / O optimization method of the external mode graph processing system, a data access model based on I / O de-reduplication and graph data sharing is proposed. The advantages and limitations of the traditional model in the face of parallel tasks are theoretically demonstrated. Based on this model, we design and implement a multitasking environment oriented memory schema graph processing system (GraphDeSh.GraphDeSh), which eliminates I / O duplication through unified access to external memory data, and balances the difference of parallel task execution speed through the design of shared cache. The data wait time of parallel task is optimized. The performance of GraphDeSh is tested by using different data sets and different algorithms, and the validity of the model based on I / O de-reduplication and graph data sharing is verified. The test results show that compared with the traditional parallel method, the optimization effect of the two-task GraphDeSh reaches the ideal speed ratio of 2 times. GraphDeSh decreases with the decrease of the calculation ratio of the graph algorithm, and the average speedup ratio is 1.45 times. The speedup ratio of GraphDeSh is 32.5-60.7 higher than that of parallel GraphChi on different data sets, and 84.5% -107.1% higher than that of parallel X-Stream.
【學(xué)位授予單位】：華中科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TP391.41

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 楊紅;可分割網(wǎng)柵系統(tǒng)下并行任務(wù)的劃分與分布[J];計(jì)算技術(shù)與自動化;1995年04期

2 郝水俠;許金超;;云計(jì)算中相似驅(qū)動的并行任務(wù)劃分方法[J];計(jì)算機(jī)科學(xué)與探索;2012年08期

3 曹潔;曾國蓀;;云環(huán)境下計(jì)算資源動態(tài)能耗感知的并行任務(wù)調(diào)度方法[J];計(jì)算機(jī)科學(xué);2013年10期

4 田新民，王鼎興，沈美明，鄭緯民;并行任務(wù)動態(tài)派生的積極惰性化控制方法[J];軟件學(xué)報(bào);1994年02期

5 王紅展;范麗珍;章偉;;一種并行任務(wù)的調(diào)度方法[J];信息通信;2014年05期

6 金燁,李玉家;并行任務(wù)的組織規(guī)劃綜述[J];制造業(yè)自動化;2000年12期

7 白宇;郭顯娥;;求解云計(jì)算壓力測試中并行任務(wù)密度的高速算法[J];計(jì)算機(jī)應(yīng)用;2014年07期

8 羅昕，，黃仲偉，李蓮治;一種將串行程序劃分成并行任務(wù)的方法[J];哈爾濱工業(yè)大學(xué)學(xué)報(bào);1995年05期

9 劉小峰，李伯虎;并行任務(wù)自動劃分及調(diào)度算法SMPS[J];系統(tǒng)仿真學(xué)報(bào);1996年01期

10 舒繼武,趙金熙,趙金熙,周維四,張德富;基于多層油藏問題負(fù)載均衡的并行任務(wù)劃分[J];軟件學(xué)報(bào);1999年10期

相關(guān)碩士學(xué)位論文 前3條

1 鮑匡迪;基于減少外存訪問的多任務(wù)圖處理系統(tǒng)研究[D];華中科技大學(xué);2016年

2 余金果;并行任務(wù)在線排序的若干問題研究[D];北京郵電大學(xué);2014年

3 任碧巖;多核實(shí)時(shí)并行任務(wù)系統(tǒng)能耗最小化調(diào)度算法的研究[D];東北大學(xué);2012年

本文編號：1805966