面向圖計(jì)算系統(tǒng)的異步計(jì)算-加載模型

周曉麗，陳 榕

(上海交通大學(xué) 軟件學(xué)院 并行與分布式系統(tǒng)研究所，上海 200240)

1 引 言

目前，針對大規(guī)模數(shù)據(jù)的圖計(jì)算系統(tǒng)被漸漸關(guān)注起來，許多現(xiàn)實(shí)問題都可以被抽象成圖模型，并用圖計(jì)算系統(tǒng)得到解決，例如社交網(wǎng)絡(luò)、商品推薦等.分布式框架常被用于圖計(jì)算系統(tǒng)中，例如PowerGraph[1]，PowerLyra[2]，Giraph[3]文獻(xiàn)[4]都是近些年提出的分布式圖計(jì)算系統(tǒng).通過集群強(qiáng)大的計(jì)算資源，它們可以處理規(guī)模龐大的圖數(shù)據(jù)，但機(jī)器數(shù)量的增多也會為管理、協(xié)調(diào)帶來難度，例如會有負(fù)載不平衡和通信代價(jià)的問題.

基于外存的核外(Out-of-core)技術(shù)為大規(guī)模圖數(shù)據(jù)計(jì)算提供了另一種解決方案，通過高效訪問外存(如，硬盤)和內(nèi)存，該類系統(tǒng)使得在單個服務(wù)器上執(zhí)行大規(guī)模圖數(shù)據(jù)的計(jì)算成為可能，例如有GraphChi[5]，X-Stream[6]，GridGraph[7]等.GraphChi將邊劃分成不同區(qū)間并存儲在外存中，它使用“并行滑動窗口”的方法載入這些邊進(jìn)入內(nèi)存，通過順序訪問來保證合理的I/O性能.X-Stream采用了“邊中心”式的計(jì)算模型，通過邊在頂點(diǎn)間傳遞數(shù)據(jù)，它的性能提升主要在于只允許隨機(jī)訪問發(fā)生在內(nèi)存內(nèi)，而保證對速度較慢的外存訪問是順序的.GridGraph首先提出了二維劃分邊的方法“網(wǎng)格劃分法”，它將邊按照起始和結(jié)束頂點(diǎn)劃分到不同的網(wǎng)格區(qū)間中，劃分目的是讓數(shù)據(jù)布局更有利于CPU訪問.為了減少I/O數(shù)量，它在邏輯上將多個網(wǎng)格中的邊合并成一個大的I/O數(shù)據(jù)塊，一同載入內(nèi)存執(zhí)行.GridGraph的性能要優(yōu)于GraphChi和X-Stream，這主要是因?yàn)樗苡行p少I/O數(shù)量并且較合理的利用I/O帶寬.

目前的out-of-core圖計(jì)算系統(tǒng)大都側(cè)重于優(yōu)化I/O性能，例如確保順序訪問，減少I/O數(shù)量，充分利用帶寬等，卻沒有意識到隨著硬盤帶寬的不斷提升，計(jì)算時(shí)間逐漸凸顯，尤其對于一些計(jì)算密集型的圖算法，它們需要更多的計(jì)算時(shí)間，這些計(jì)算時(shí)間可能成為系統(tǒng)性能的瓶頸.GridGraph是三個代表性系統(tǒng)中性能最優(yōu)的，但同樣存在上述問題.由于使用了同步計(jì)算-加載模型，計(jì)算過程和I/O加載過程缺乏并行性，工作線程既要負(fù)責(zé)I/O任務(wù)也要負(fù)責(zé)計(jì)算任務(wù)，且計(jì)算任務(wù)阻塞于I/O任務(wù)，這主要因?yàn)樗褂玫耐絀/O引擎使得線程在發(fā)送I/O請求后，不得不等待I/O操作的完成，浪費(fèi)了大量的計(jì)算資源.

1http://law.di.unimi.it/webdata/clueweb12/

2http://lse.sourceforge.net/io/aio.html

3http://wufei.org/2016/09/16/linux-io-data-flow/

本文通過實(shí)驗(yàn)數(shù)據(jù)說明，當(dāng)硬盤帶寬逐漸增加時(shí)，I/O讀寫的時(shí)間會進(jìn)一步減少，計(jì)算時(shí)間會越來越突出甚至成為瓶頸.如圖1所示，在GridGraph上運(yùn)行圖算法PageRank[8]，輸入數(shù)據(jù)為ClueWeb1，當(dāng)SSD數(shù)量從1增加到6時(shí)，I/O的帶寬能力也呈線性增長，但計(jì)算時(shí)間與I/O時(shí)間的比例也隨之增加，當(dāng)SSD數(shù)量為6時(shí)，計(jì)算時(shí)間幾乎和I/O時(shí)間齊平，可以預(yù)見當(dāng)SSD數(shù)量繼續(xù)增加時(shí)，計(jì)算時(shí)間就會成為整個系統(tǒng)性能的瓶頸.

圖1 計(jì)算時(shí)間與I/O時(shí)間比Fig.1 Ratio of computation time to I/O time

此外，同步計(jì)算-加載模型沒有區(qū)分計(jì)算線程和I/O線程，線程數(shù)量往往由服務(wù)器的核數(shù)決定，這樣的線程創(chuàng)建數(shù)量的確有利于計(jì)算任務(wù)的并發(fā)性，卻不利于I/O訪問.一方面，操作系統(tǒng)對外存的訪問方式缺乏并行性；另一方面，I/O有限的帶寬并不需要服務(wù)器核數(shù)數(shù)量的線程就能填滿.這些原因決定了下層I/O無法很好的支持用戶程序大量的并發(fā)請求，因此在使用同步計(jì)算-加載模型的這類系統(tǒng)中，例如GridGraph，它們往往由于不合理的I/O線程數(shù)量而無法充分利用硬盤帶寬.

針對上述問題，本文提出了異步計(jì)算-加載模型，該模型使得圖計(jì)算系統(tǒng)中計(jì)算過程和I/O過程能夠并行起來，較長的I/O時(shí)間可以很好地“隱藏”計(jì)算時(shí)間，據(jù)此，本文也稱這種模型為IOC(I/O Overlapping Computation).該模型將線程按照所執(zhí)行任務(wù)的類型區(qū)分為計(jì)算線程和I/O線程，并根據(jù)不同的訪問需求創(chuàng)建不同的線程數(shù)量.對于計(jì)算線程而言，線程數(shù)量應(yīng)該由服務(wù)器的計(jì)算能力決定，它們擁有獨(dú)立的子任務(wù)數(shù)據(jù)，互不干擾，IOC創(chuàng)建與服務(wù)器核數(shù)一致的線程數(shù)量來盡可能提高計(jì)算的并發(fā)性；對于I/O線程而言，線程數(shù)量應(yīng)該由下層I/O的處理能力決定，IOC的策略是創(chuàng)建能夠填滿硬盤帶寬的最小線程數(shù)量，避免造成額外開銷.為了進(jìn)一步提高I/O性能，IOC拋棄了其他系統(tǒng)使用的PSYNC I/O引擎，這類引擎接口簡單，但這主要是由于下層操作系統(tǒng)向上屏蔽了很多實(shí)現(xiàn)細(xì)節(jié)，不利于上層用戶程序的優(yōu)化.IOC使用了異步的I/O引擎LIBAIO2，I/O線程使用該類型的接口向操作系統(tǒng)發(fā)出I/O請求后，無需等待I/O操作完成就立即返回，繼續(xù)處理下個請求，通過這種方式，單個線程單位時(shí)間內(nèi)可以處理更多的I/O請求.此外，LIBAIO的batch機(jī)制在保證硬盤帶寬被填滿的前提下，還能接收粒度更細(xì)的I/O請求數(shù)據(jù)，這同樣有助于線程間的負(fù)載平衡.

本文的主要貢獻(xiàn)在于：1)提出了異步計(jì)算-加載模型IOC，使得I/O時(shí)間能夠“隱藏”計(jì)算時(shí)間，避免了硬盤帶寬不斷提升后，計(jì)算時(shí)間逐漸凸顯成為瓶頸的問題.2)IOC區(qū)分計(jì)算線程和I/O線程，并能夠結(jié)合硬件資源的限制，合理分配計(jì)算線程和I/O線程數(shù)量，以滿足不同執(zhí)行任務(wù)的訪問需求.3)IOC使用的異步I/O引擎LIBAIO，在保證充分利用硬盤帶寬的前提下，允許上層用戶提交粒度更細(xì)的I/O數(shù)據(jù)塊，優(yōu)化了負(fù)載的平衡性.4)本文在最后通過實(shí)驗(yàn)結(jié)果表明IOC模型無論是在運(yùn)行時(shí)間，I/O帶寬，還是負(fù)載平衡方面都能明顯優(yōu)于同步計(jì)算-加載模型.

2 背景介紹

2.1 同步計(jì)算-加載模型

比較常用的一類計(jì)算模型是同步計(jì)算-加載模型.該模型沒有區(qū)分計(jì)算線程和I/O加載線程.在將任務(wù)劃分之后，每個線程都有一份獨(dú)自的子任務(wù)，每個線程首先從外存中載入子任務(wù)所需數(shù)據(jù)，在I/O加載過程中，各個線程一直處于等待狀態(tài)，直到該數(shù)據(jù)被加載進(jìn)內(nèi)存，線程才能重新被CPU調(diào)度并執(zhí)行計(jì)算過程.在線程等待I/O的過程中，CPU一直處于閑置狀態(tài)，浪費(fèi)計(jì)算資源.

該模型的問題還不僅僅在于浪費(fèi)計(jì)算資源，不區(qū)分計(jì)算線程和I/O線程還會影響I/O性能.在使用該模型的系統(tǒng)中，線程數(shù)量通常由服務(wù)器的核數(shù)決定，一般會創(chuàng)建20-40個線程，這些線程并行的向操作系統(tǒng)發(fā)出I/O請求，而目前Linux系統(tǒng)對外存的訪問方式還缺乏并行性[9]，例如Linux內(nèi)核順序的對I/O任務(wù)排序以及輪詢地向底層發(fā)送I/O任務(wù).也就是說，下層的操作系統(tǒng)無法滿足上層用戶程序大量的并行I/O請求.

更糟糕的是過多的線程同時(shí)訪問I/O會降低I/O帶寬.在收到用戶的I/O請求后，Linux內(nèi)核會執(zhí)行4個操作3：plug，unplug，dispatch，completion.為了優(yōu)化I/O性能，內(nèi)核會在unplug階段對當(dāng)前所有I/O請求排序，從而盡可能順序的訪問硬盤.內(nèi)核的這種機(jī)制在保證底層硬盤訪問性能時(shí)，卻可能造成對不同線程的I/O請求的響應(yīng)時(shí)間不均衡，這種不均衡在順序讀文件時(shí)最為明顯，圖4 (a)說明了這一點(diǎn).

目前大部分out-of-core圖計(jì)算系統(tǒng)都使用同步的計(jì)算-加載模型，一方面計(jì)算線程阻塞于I/O，大大浪費(fèi)計(jì)算資源；另一方面，這類模型簡單的將計(jì)算線程用于I/O訪問，不僅加重I/O負(fù)載、造成額外開銷，而且有背于內(nèi)核的優(yōu)化原則，影響I/O性能.

2.2 PSYNC和LIBAIO

PSYNC和LIBAIO是Linux系統(tǒng)向上提供的兩種I/O引擎接口.PSYNC為同步I/O類型，主要包括pread/pwrite調(diào)用，pread根據(jù)指定的文件描述符、文件偏移量讀取指定長度的數(shù)據(jù)到內(nèi)存，pwrite根據(jù)文件描述符、偏移量寫入指定長度的數(shù)據(jù)到外存.LIBAIO是Linux的原生異步I/O，用戶程序可以通過io_submit系統(tǒng)調(diào)用以batch的方式向Linux內(nèi)核發(fā)送I/O請求，通過io_getevents調(diào)用來獲取一組完成的I/O數(shù)據(jù).

2.2.1 阻塞與非阻塞

PSYNC為阻塞式的I/O.用戶程序在發(fā)起阻塞I/O調(diào)用后，會一直處于等待狀態(tài)，直到內(nèi)核將完成的I/O數(shù)據(jù)拷貝到用戶程序空間后，才從相關(guān)系統(tǒng)調(diào)用中返回，用戶進(jìn)程阻塞于整個pread過程.而LIBAIO卻是一種非阻塞型的I/O機(jī)制.用戶進(jìn)程發(fā)起io_submit系統(tǒng)調(diào)用后，無需等待I/O完成就可返回，內(nèi)核負(fù)責(zé)向底層設(shè)備傳遞I/O請求并將返回的I/O數(shù)據(jù)先載入到內(nèi)核緩沖區(qū)中，整個過程期間用戶進(jìn)程可以執(zhí)行其他操作.當(dāng)用戶進(jìn)程需要I/O數(shù)據(jù)時(shí)，主動發(fā)起io_getevents進(jìn)行數(shù)據(jù)“收割”，內(nèi)核負(fù)責(zé)將數(shù)據(jù)拷貝至用戶進(jìn)程的內(nèi)存空間.

圖2 非batch和batch的比較 Fig.2 Comparison of non-batch and batch

不難發(fā)現(xiàn)，阻塞型I/O會造成用戶進(jìn)程大量的等待時(shí)間，但目前的很多圖計(jì)算系統(tǒng)都采取這種方式.它們通常開辟服務(wù)器核數(shù)的線程，并行發(fā)起pread/pwrite調(diào)用，這些線程阻塞于整個I/O調(diào)用過程，無法進(jìn)行計(jì)算，導(dǎo)致大量計(jì)算資源的浪費(fèi).

2.2.2 非batch和batch

LIBAIO可以batch提交I/O請求，通過參數(shù)BLOCKSIZE、IODEPTH可以分別指定單個IO請求塊的大小和批量處理的塊數(shù)量.相比PSYNC，LIBAIO的batch機(jī)制可以用來支持更細(xì)粒度的I/O請求.上文提到了Linux系統(tǒng)處理I/O請求的四個階段plug，unplug，dispatch，completion，在plug階段，內(nèi)核會將每個I/O task對應(yīng)的I/O請求塊合并到plug-list中，當(dāng)plug-list中的數(shù)量達(dá)到一定閾值之后才會進(jìn)入unplug階段，之后才會向底層硬盤發(fā)出傳輸請求.為了最大效率的利用硬盤帶寬，上層用戶程序需要盡可能快的提交一定數(shù)量的I/O請求數(shù)據(jù)來填滿plug-list，如圖2所示，沒有batch機(jī)制的PSYNC只能增大每次請求數(shù)據(jù)的BLOCKSIZE，而支持batch機(jī)制的LIBAIO可以通過增大batch的數(shù)量IODEPTH，從而支持更細(xì)粒度的BLOCKSIZE.

在同步計(jì)算-加載模型中，每個線程的計(jì)算數(shù)據(jù)的粒度和I/O請求數(shù)據(jù)的粒度相同，如果該模型使用PSYNC，I/O請求數(shù)據(jù)的粗粒度也直接決定了計(jì)算數(shù)據(jù)的粗粒度，在動態(tài)分配任務(wù)的計(jì)算模型中，將會導(dǎo)致各個線程工作負(fù)載的不平衡，從而影響整體系統(tǒng)的性能.

3 異步計(jì)算-加載模型IOC

異步計(jì)算-加載模型IOC區(qū)分了計(jì)算線程和I/O線程，計(jì)算線程無需管理I/O的讀寫，僅僅負(fù)責(zé)數(shù)據(jù)的計(jì)算，只要有待處理的數(shù)據(jù)就會不斷地被CPU調(diào)度執(zhí)行.I/O的讀寫操作由專門的I/O線程管理，這些線程無需關(guān)心上層計(jì)算，只負(fù)責(zé)發(fā)送I/O請求和“收割”I/O數(shù)據(jù)，只要有足夠的內(nèi)存空間就會不斷地將數(shù)據(jù)從硬盤中載入進(jìn)來.計(jì)算線程和I/O線程并行執(zhí)行各自的任務(wù)，這樣一來較長的I/O時(shí)間便可以“隱藏”計(jì)算時(shí)間，從用戶程序的角度，整個系統(tǒng)的運(yùn)行時(shí)間就只有I/O時(shí)間.

3.1 挑戰(zhàn)

但實(shí)現(xiàn)IOC模型并不容易，關(guān)鍵難點(diǎn)就在于如何在內(nèi)存容量限制的前提下，協(xié)同I/O線程和計(jì)算線程：I/O線程將從硬盤中載入的I/O數(shù)據(jù)塊緩存在內(nèi)存緩沖區(qū)中，計(jì)算線程從緩沖區(qū)中獲取待處理的數(shù)據(jù)塊，那么如何在內(nèi)存緩沖區(qū)剩余空間不足時(shí)，同步I/O線程放慢(或停止)I/O操作，當(dāng)沒有新載入的I/O數(shù)據(jù)塊時(shí)又如何通知計(jì)算線程.這看起來像一個生產(chǎn)者-消費(fèi)者問題，但卻復(fù)雜的多.

傳統(tǒng)的生產(chǎn)者-消費(fèi)者算法存在兩個明顯弊端：

1)生產(chǎn)者和消費(fèi)者都是按序連續(xù)的使用內(nèi)存緩沖區(qū)，不夠靈活.

2)生產(chǎn)和消費(fèi)過程都涉及到數(shù)據(jù)的拷貝，并且拷貝時(shí)相應(yīng)線程獨(dú)占整個緩沖區(qū)資源，其他線程只能等待，缺乏并行性.在IOC中，計(jì)算線程相當(dāng)于消費(fèi)者，I/O線程相當(dāng)于生產(chǎn)者，但如果直接使用上述算法，還是會有不少問題：

1)按序連續(xù)使用內(nèi)存的方式不夠靈活，只能支持同步I/O引擎PSYNC，而支持不了異步I/O引擎LIBAIO，這主要因?yàn)楫?dāng)I/O線程主動調(diào)用io_getevents請求“收割”I/O數(shù)據(jù)時(shí)，操作系統(tǒng)將I/O數(shù)據(jù)從內(nèi)核緩沖區(qū)拷貝至用戶的內(nèi)存緩沖區(qū)中，但并不能保證按照用戶內(nèi)存的地址順序來進(jìn)行拷貝，也就無法保證內(nèi)存緩沖區(qū)被連續(xù)使用.

2)如果每次計(jì)算線程和I/O線程“生產(chǎn)”和“消費(fèi)”時(shí)都需要進(jìn)行數(shù)據(jù)拷貝，首先會增加內(nèi)存負(fù)擔(dān)，其次拷貝過程需要消耗一部分計(jì)算資源，這些都將影響IOC的性能.所以，實(shí)現(xiàn)IOC并不能簡單的套用傳統(tǒng)的“生產(chǎn)者-消費(fèi)者”模型，具有一定挑戰(zhàn)性.

3.2 關(guān)鍵設(shè)計(jì)

為了解決上面的問題，圖計(jì)算系統(tǒng)需要更加靈活的異步計(jì)算-加載模型IOC，靈活體現(xiàn)在允許離散的使用內(nèi)存緩沖區(qū)空間以支持LIBAIO引擎；此外，還需減少計(jì)算、加載過程中數(shù)據(jù)的拷貝.為了解決這些問題，本文提出了基于地址管理的IOC模型.

首先將內(nèi)存緩沖區(qū)按照I/O數(shù)據(jù)塊的大小進(jìn)行劃分，假設(shè)內(nèi)存緩沖區(qū)的總空間為BUFSIZ，I/O數(shù)據(jù)塊的大小為BLKSIZ，那么就將緩沖區(qū)劃分成BUFSIZ/BLKSIZ塊，第i塊的地址為i*BLKSIZ.IOC將這些塊區(qū)分為數(shù)據(jù)塊和空閑塊，并使用隊(duì)列來記錄它們的地址，隊(duì)列中相鄰的塊地址可能指向離散的物理內(nèi)存空間.

如圖3所示，隊(duì)列computing記錄著等待計(jì)算線程處理的數(shù)據(jù)塊地址，I/O loading隊(duì)列記錄著等待I/O線程載入數(shù)據(jù)的空閑塊地址.兩組線程分別查找各自隊(duì)列以獲取所要的塊地址，避免了競爭，同時(shí)也通過彼此隊(duì)列實(shí)現(xiàn)同步.圖3描述了具體的同步過程:

1)計(jì)算線程訪問computing queue，請求獲取可計(jì)算的數(shù)據(jù)塊地址，如果隊(duì)列為空，則進(jìn)入等待狀態(tài)，否則成功返回；

2)計(jì)算線程通過地址訪問到該數(shù)據(jù)塊并執(zhí)行計(jì)算，計(jì)算結(jié)束后就釋放該數(shù)據(jù)塊以用于載入新的I/O數(shù)據(jù)，將該數(shù)據(jù)塊的地址插入到I/O loading queue中，該數(shù)據(jù)塊變?yōu)榭臻e塊.

4http://law.di.unimi.it/webdata/uk-union-2006-06-2007-05/

3)I/O線程訪問I/O loading隊(duì)列，請求獲取一個可用空閑塊的地址用來載入I/O數(shù)據(jù)，如果該隊(duì)列為空則等待，否則執(zhí)行I/O操作.

4)I/O操作完成后，該地址指向的空閑塊中填充了I/O數(shù)據(jù)，下一步就是交給計(jì)算線程計(jì)算，I/O線程將該空閑塊的地址插入到computing queue中，空閑塊又變?yōu)閿?shù)據(jù)塊.從靜態(tài)角度看，在某個時(shí)刻，緩沖區(qū)內(nèi)的某個內(nèi)存塊為數(shù)據(jù)塊或空閑塊，它們對應(yīng)的地址只可能出現(xiàn)在兩個隊(duì)列中的其中一個.從動態(tài)角度看，這些內(nèi)存塊的地址在兩個隊(duì)列之間不停流轉(zhuǎn)，構(gòu)成了整個IOC的同步過程.

圖3 異步計(jì)算-加載模型IOCFig.3 Model of asynchronous computation-I/O (IOC)

計(jì)算和I/O線程并行執(zhí)行各自任務(wù)，并通過隊(duì)列同步、協(xié)作，共同完成圖計(jì)算系統(tǒng)的任務(wù)，算法1也表示了這一過程.最開始，computing隊(duì)列為空表示當(dāng)前無可計(jì)算的數(shù)據(jù)塊，所有內(nèi)存塊都是空閑狀態(tài)，它們的地址都被插入到 loading隊(duì)列中.隊(duì)列通過鎖機(jī)制保證了多線程訪問時(shí)數(shù)據(jù)的正確性，front_pop()為同步操作，只有當(dāng)隊(duì)列不為空時(shí)，當(dāng)前線程才能成功獲取地址，否則進(jìn)入等待狀態(tài).計(jì)算線程可以通過返回地址p_data_blk訪問到數(shù)據(jù)塊data_blk，并進(jìn)入處理數(shù)據(jù)階段.傳統(tǒng)的“生產(chǎn)者-消費(fèi)者”算法先將數(shù)據(jù)塊內(nèi)容拷貝至計(jì)算線程自己的內(nèi)存空間中，釋放鎖之后再計(jì)算，但拷貝操作無疑會增加內(nèi)存和計(jì)算資源的負(fù)擔(dān).考慮到大部分圖算法的計(jì)算過程都比較簡單、時(shí)間較短，IOC中計(jì)算線程會直接對內(nèi)存緩沖區(qū)中的數(shù)據(jù)data_blk進(jìn)行計(jì)算，而不是預(yù)先拷貝副本，直到處理完data_blk中的數(shù)據(jù)后，才會通過間接操作地址的方法釋放該數(shù)據(jù)塊.它將data_blk的地址p_data_blk插入到loading隊(duì)列中，等待I/O線程主動獲取并重新利用.I/O線程成功獲取空閑塊地址p_free_blk后，開始執(zhí)行do_io操作，并準(zhǔn)備向操作系統(tǒng)發(fā)送I/O請求，IOC靈活使用內(nèi)存的方式可以用來支持異步發(fā)送I/O請求.當(dāng)I/O線程通過LIBAIO提供的io_submit發(fā)送請求時(shí)，會向操作系統(tǒng)傳遞兩大基本參數(shù)：需要讀取的數(shù)據(jù)塊地址范圍、讀到內(nèi)存的地址p_free_blk，傳遞完畢后就返回.之后，操作系統(tǒng)將該范圍的數(shù)據(jù)塊從外存載入到內(nèi)核緩沖區(qū)中，在“收割”數(shù)據(jù)階段，再直接將數(shù)據(jù)從內(nèi)核緩沖區(qū)拷貝至p_free_blk指向的空閑塊中.完成“收割”后，該空閑塊轉(zhuǎn)化為數(shù)據(jù)塊，I/O線程隨即將該塊地址插入到computing queue中.

算法1.異步計(jì)算-加載模型(IOC)

// completed or not

Boolean done = 0;

Queue computing { 0 };

Queue loading { BUFSIZ/BLKSIZ };

1 procedurecompute() {

2 while (!done) {

3 Addr p_data_blk = computing.front_pop();

4 do_compute(p_data_blk);

5 loading.append(p_data_blk);

6 }

7 }

8 procedureio() {

9 while (!done) {

10 Addr p_free_blk = loading.front_pop();

11 do_io(p_free_blk);

12 computing.append(p_free_blk);

13 }

14 }

基于地址管理的IOC算法更加靈活.當(dāng)某個空閑塊地址中的內(nèi)存被填充好I/O數(shù)據(jù)后，它就立刻被I/O線程處理，并被插入到computing queue中，而無需等待那些地址在它之前但還未完成I/O操作的空閑塊，這點(diǎn)可以用來支持異步的I/O發(fā)送接收方式(LIBAIO引擎).當(dāng)某個數(shù)據(jù)塊被處理完畢后，計(jì)算線程隨即將它插入到loading queue中，而無需因?yàn)閮?nèi)存連續(xù)使用的限制而等待.此外，兩組線程都是通過內(nèi)存地址直接對緩沖區(qū)中的數(shù)據(jù)進(jìn)行操作，有效避免了數(shù)據(jù)的拷貝，從而節(jié)省了一部分內(nèi)存和計(jì)算資源.

3.3 使用LIBAIO支持更細(xì)粒度的I/O數(shù)據(jù)塊

IOC使用LIBAIO作為I/O引擎.一方面，I/O線程可以非阻塞的發(fā)送I/O請求，而無需等待I/O操作的完成，這樣可以增強(qiáng)系統(tǒng)發(fā)送I/O請求的能力，盡快地填滿硬盤帶寬.另一方面，LIBAIO的batch機(jī)制可以支持更細(xì)粒度的I/O數(shù)據(jù)塊，這些I/O數(shù)據(jù)塊被填滿I/O數(shù)據(jù)后，地址被插入到computing queue中，等待計(jì)算線程的處理，這就相當(dāng)于通過“動態(tài)分配”的方式讓所有計(jì)算線程來“競爭”這些數(shù)據(jù)塊.粒度更小，各個工作線程的負(fù)載就越平衡，4.3通過實(shí)驗(yàn)說明了這點(diǎn).

3.4 合理的I/O線程數(shù)

為了適應(yīng)內(nèi)核的I/O訪問機(jī)制，合理的做法是分配能夠填滿I/O帶寬的最小線程數(shù)量，IOC也遵從這一原則.例如對于1個SSD(最大帶寬為450MBps)，單個線程就可以填滿，IOC僅分配1個I/O線程.在順序讀取文件時(shí)，單個線程按照文件順序發(fā)出I/O請求，文件偏移量低的數(shù)據(jù)塊會優(yōu)先到達(dá)，內(nèi)核也會按照這樣的順序向I/O通道傳遞請求，這樣一來，到達(dá)的數(shù)據(jù)塊都會被及時(shí)處理，I/O請求的完成時(shí)間比較均衡.

為了更有說服力，本文通過實(shí)驗(yàn)比較了對文件順序讀時(shí)，使用40個線程和1個線程的I/O請求時(shí)間.實(shí)驗(yàn)在GridGraph上運(yùn)行PageRank算法，輸入數(shù)據(jù)為UK圖4，使用1個SSD.結(jié)果如圖4所示，橫軸為按照文件偏移順序排列的各個I/O請求，縱軸為請求的完成時(shí)間.圖4(a)為40個線程順序讀時(shí)各個I/O請求的時(shí)間，抖動很大；圖4(b)為使用單個線程的結(jié)果，各個I/O請求的完成時(shí)間比較均衡且遠(yuǎn)遠(yuǎn)低于40個線程的數(shù)值.這也就說明了過多的I/O線程不僅會加大I/O負(fù)載，還會造成I/O請求完成時(shí)間的不均衡，增大延遲，從而影響整個圖計(jì)算系統(tǒng)的I/O性能.

5http://law.di.unimi.it/webdata/gsh-2015/

6http://law.di.unimi.it/webdata/eu-2015/

圖4 I/O完成時(shí)間比較Fig.4 Comparison of I/O completion time

4 性能評測

GridGraph是目前性能比較出色的out-of-core圖計(jì)算系統(tǒng)，它的性能要優(yōu)于X-Stream和GraphChi，這也是本文選取它為參照的原因.GridGraph使用同步計(jì)算-加載模型，并通過PSYNC提供的I/O接口來處理I/O請求.本文的實(shí)驗(yàn)直接修改了GridGraph代碼，使它支持使用LIBAIO引擎的異步計(jì)算-加載模型，并著重探究兩種模型對圖計(jì)算系統(tǒng)性能的影響，主要從以下三個方面探究：運(yùn)行時(shí)間，計(jì)算負(fù)載的平衡性，I/O帶寬.

表1 實(shí)驗(yàn)數(shù)據(jù)集Table 1 Experimental data sets

4.1 實(shí)驗(yàn)環(huán)境

本文的所有實(shí)驗(yàn)均在單個多核服務(wù)器上完成，服務(wù)器配置為：40個超線程vCPU cores，25MB LLC Cache，116GB memory，1-6 800GB SSDs，6個SSD順序讀的最大吞吐量均可達(dá)到450MB/s-500MB/s.

4.2 運(yùn)行時(shí)間

下面實(shí)驗(yàn)分別在使用不同計(jì)算-加載模型的GridGraph中運(yùn)行PageRank和SPMV[10]算法，使用6個SSDs (RAID0)，輸入數(shù)據(jù)如表1所示，這些圖數(shù)據(jù)(UK，GSH5，ClueWeb，EU6)描述了從不同域名爬取的網(wǎng)頁信息.PageRank和SPMV均為計(jì)算密集型算法，計(jì)算時(shí)間所占比重較大，使用IOC模型之后，它們的計(jì)算時(shí)間被I/O時(shí)間“隱藏”，因此整體系統(tǒng)性能的提升比較明顯.圖5(a)為PageRank算法下兩種模型的時(shí)間比較，左邊為GridGraph的運(yùn)行結(jié)果，包括下面的I/O時(shí)間和上面的計(jì)算時(shí)間，緊挨著的右邊為基于IOC模型的GridGraph (IOC-Grid)的運(yùn)行總時(shí)間.兩個模型的運(yùn)行時(shí)間都隨著輸入圖規(guī)模的增加而上升，但I(xiàn)OC-Grid的運(yùn)行時(shí)間要始終少于GridGraph，這主要?dú)w功于計(jì)算時(shí)間被I/O加載時(shí)間“隱藏”；此外，IOC能更好的利用硬盤帶寬，I/O加載時(shí)間少于GridGraph，這主要?dú)w功于IOC模型靈活的區(qū)分I/O線程和計(jì)算線程，并創(chuàng)建合理的I/O線程數(shù)，既能填滿硬盤帶寬又不會造成額外開銷，從而提高了I/O性能.圖5(b)為SPMV算法的運(yùn)行結(jié)果，IOC-Grid性能依然保持領(lǐng)先.SPMV算法中的邊是帶權(quán)重的，與PageRank相比，需要多載入邊的權(quán)值數(shù)據(jù)，因此也就需要更多的運(yùn)行總時(shí)間.

圖5 GridGraph與IOC-Grid的運(yùn)行時(shí)間Fig.5 Runtime of GridGraph and IOC-Grid

IOC-Grid在不同的輸入數(shù)據(jù)集上有不同的性能提升，其中ClueWeb圖的提升最為明顯，這主要因?yàn)樵搱D的計(jì)算時(shí)間最突出，幾乎與I/O時(shí)間齊平.GridGraph的計(jì)算性能受數(shù)據(jù)布局的影響較大，好的數(shù)據(jù)布局有助于頂點(diǎn)數(shù)據(jù)的順序訪問，提高cache命中率，從而減少計(jì)算時(shí)間.但ClueWeb的數(shù)據(jù)布局不及其他三個數(shù)據(jù)集，這點(diǎn)從表2所示的LLC 未命中率就可以看出，這就導(dǎo)致它的計(jì)算時(shí)間最為突出，幾乎與I/O時(shí)間齊平.IOC將這最明顯的計(jì)算時(shí)間“隱藏”，使得整體性能能夠提升到一半.

表2 不同數(shù)據(jù)集的LLC 未命中率Table 2 LLC cache miss rate of different data sets

4.3 計(jì)算線程負(fù)載的平衡性

為了比較兩種模型下計(jì)算線程負(fù)載的平衡性，下面實(shí)驗(yàn)在原先和修改后的GridGraph上分別運(yùn)行PageRank算法，創(chuàng)建了40個計(jì)算線程，輸入的圖數(shù)據(jù)為UK，使用1個SSD.圖6(a)為GridGraph的運(yùn)行結(jié)果，使用了PSYNC引擎的同步計(jì)算-加載模型；圖6(b)是支持LIBAIO的IOC模型的運(yùn)行結(jié)果.可以明顯看出IOC中計(jì)算線程的負(fù)載要更加平衡，這主要?dú)w功于LIBAIO可以支持更細(xì)粒度的I/O數(shù)據(jù)塊.Grid-Graph使用的PSYNC引擎為了填滿硬盤帶寬，I/O數(shù)據(jù)塊小被設(shè)定在24MB，而IOC為128KB.兩者的I/O數(shù)據(jù)塊大小都決定了計(jì)算數(shù)據(jù)塊的大小，128KB和24MB相比明顯粒度更細(xì)，這也使得IOC中負(fù)載的分配能夠更加公平，各個計(jì)算線程的負(fù)載更加均衡.

圖6 GridGraph與IOC-Grid的負(fù)載平衡性Fig.6 Load balance of GridGraph and IOC-Grid

4.4 不同SSD數(shù)量下的帶寬比較

表3為不同SSD數(shù)量下，IOC-Grid和GridGraph的帶寬比較結(jié)果.可以發(fā)現(xiàn)，IOC-Grid始終能保持更高的帶寬利用率，在1個SSD下最為明顯.這主要?dú)w功于IOC能夠根據(jù)下層I/O的處理能力合理的分配I/O線程數(shù)量，而GridGraph中 I/O線程數(shù)量取決于服務(wù)器核數(shù)，大量的I/O線程數(shù)量會增加資源競爭和額外開銷.隨著SSD數(shù)量增多，下層I/O的處理能力增強(qiáng)，能夠稍微緩解上層大量I/O并發(fā)請求的競爭，GridGraph受益于此，I/O帶寬有所提升，但依然不及IOC-Grid.

表3 不同SSD數(shù)量下的帶寬，單位MBpsTable 3 I/O bandwidth under different SSD number，MBps

5 結(jié) 論

核外(Out-of-core)圖計(jì)算系統(tǒng)使得在單點(diǎn)服務(wù)器上執(zhí)行大規(guī)模圖數(shù)據(jù)成為可能，已有的該類型系統(tǒng)都是通過優(yōu)化I/O訪問來提高性能，卻忽略了隨著硬盤訪問能力的提升，計(jì)算時(shí)間越來越突出的問題.對此，本文提出了異步計(jì)算-加載模型IOC，在該模型中計(jì)算過程不再阻塞于I/O加載過程，較長的I/O時(shí)間能夠“隱藏”計(jì)算時(shí)間.IOC根據(jù)硬件資源的訪問能力分配不同數(shù)量的線程數(shù)，既保證高效的計(jì)算能力又保證充分的帶寬利用.IOC摒棄了傳統(tǒng)同步計(jì)算-加載模型使用的PSYNC I/O引擎，改用LIBAIO，異步的處理方式提高了接受I/O請求的能力，LIBAIO提供的batch機(jī)制也使得各個線程的負(fù)載更加均衡.本文最后通過實(shí)驗(yàn)結(jié)果說明，IOC能將out-of-core圖計(jì)算系統(tǒng)的性能提升高達(dá)1倍，并且有更好的帶寬利用率和負(fù)載平衡性.