基于活躍頂點的外存圖計算系統(tǒng)I-O訪問策略.pdf

1、現(xiàn)有的外存圖計算系統(tǒng)中,設(shè)計重點集中在以通用的方式對各類應(yīng)用進(jìn)行處理，在執(zhí)行時通過對圖數(shù)據(jù)的完整遍歷完成計算的迭代過程。但實際上圖應(yīng)用中往往不需要對圖數(shù)據(jù)進(jìn)行完整的訪問，而是根據(jù)自身的需求對部分“活躍頂點”進(jìn)行訪問，利用這一特性，在對外存進(jìn)行訪問時避免訪問無關(guān)的數(shù)據(jù)而只訪問“活躍頂點”相關(guān)的數(shù)據(jù)，可以大幅度的縮小實際計算過程中進(jìn)行 I/O的數(shù)據(jù)量，進(jìn)而大幅提升性能。
　　為了實現(xiàn)在運行時在外存中對所需要的數(shù)據(jù)進(jìn)行定位讀取，提出了一

2、種應(yīng)用在外存圖處理系統(tǒng)中基于活躍頂點進(jìn)行 I/O訪問的方法，通過以頂點為單位對圖數(shù)據(jù)進(jìn)行重新組織使得同一頂點相關(guān)的邊都存放在一起便于讀取，然后以頂點為單位建立索引，使得在對指定頂點相關(guān)數(shù)據(jù)進(jìn)行取時可以快速進(jìn)行定位。基于這種方案，進(jìn)一步改進(jìn)了計算模型，使系統(tǒng)能更好的在不需要構(gòu)建全部子圖的情況下高效運行。
　　這種方法減少了需要進(jìn)行 I/O的數(shù)據(jù)量，但是帶來的一個新問題是由原本的順序訪問變成了隨機(jī)訪問。由于順序訪問的性能遠(yuǎn)高于隨機(jī)訪問

3、。因此如何權(quán)衡大數(shù)據(jù)量的順序訪問與小數(shù)據(jù)量的隨機(jī)訪問的 I/O性能是能否取得性能提升的關(guān)鍵?；谏鲜鰡栴}，本文進(jìn)而提出了一種基于收益評價的 I/O訪問選擇策略。通過預(yù)先分析和計算不同策略進(jìn)行I/O訪問的開銷，選擇開銷較小的方式執(zhí)行應(yīng)用更新。
　　通過將這兩種方法結(jié)合，可以使得應(yīng)用始終以最優(yōu)的方式執(zhí)行迭代更新過程，獲得效率和性能上的提升。在針對不同類型應(yīng)用和數(shù)據(jù)的測試中展現(xiàn)出不同幅度的性能優(yōu)化，在迭代計算類的應(yīng)用中加速比可以達(dá)到1.