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

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

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

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