， ,

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

計(jì)算機(jī)能效是當(dāng)前計(jì)算機(jī)領(lǐng)域研究的熱點(diǎn)議題之一.隨著云計(jì)算與大數(shù)據(jù)時(shí)代的到來(lái)，數(shù)據(jù)中心的能效問(wèn)題更加凸顯，大型數(shù)據(jù)中心耗費(fèi)一座城市的電能.據(jù)統(tǒng)計(jì)，數(shù)據(jù)中心的電力消耗以每年15%～20%的速度在增長(zhǎng)，大規(guī)模數(shù)據(jù)中心的能源成本快速攀升并迅速超過(guò)硬件本身的成本.數(shù)據(jù)中心的能耗成為日益關(guān)切的問(wèn)題，能耗管理成為現(xiàn)代數(shù)據(jù)中心重要的度量與設(shè)計(jì)標(biāo)準(zhǔn)，已開(kāi)展了大量研究工作[1-2].在降低能耗方面，古輝等[3]在構(gòu)建停車(chē)場(chǎng)無(wú)線(xiàn)傳感網(wǎng)絡(luò)過(guò)程中，基于某個(gè)特定的場(chǎng)景，提出了基于LEACH的簇樹(shù)網(wǎng)絡(luò)的路由算法改進(jìn)方法，使節(jié)點(diǎn)能耗有很大的下降.郝平等[4]在自主開(kāi)發(fā)的能源監(jiān)測(cè)系統(tǒng)上提出了利用基于數(shù)據(jù)倉(cāng)庫(kù)的OLAP分析和改進(jìn)的分層挖掘Apriori算法，并以此建設(shè)成一套區(qū)域能耗預(yù)警系統(tǒng)，從而提高區(qū)域能耗監(jiān)察管理和預(yù)警能力.峰值功率是數(shù)據(jù)中心的一個(gè)重要因素.在數(shù)據(jù)中心，冷卻與電力供應(yīng)是根據(jù)峰值功率來(lái)設(shè)計(jì)的，降低峰值功率可以緩解這方面的限制.Felter等[5]通過(guò)單獨(dú)估算各個(gè)耗能部件的峰值功率來(lái)估算系統(tǒng)整體峰值功率，根據(jù)對(duì)服務(wù)器部件前一區(qū)間的活動(dòng)檢測(cè)來(lái)預(yù)測(cè)下一區(qū)間活動(dòng)情況，而由此根據(jù)事先分配的功率來(lái)確定處理器、內(nèi)存的節(jié)流閾值，限制各部件的活動(dòng)來(lái)進(jìn)行功率調(diào)節(jié).Meisner等[6]為解決數(shù)據(jù)中心的功率封頂開(kāi)展了數(shù)據(jù)中心峰值功率建模，功率封頂是數(shù)據(jù)中心對(duì)服務(wù)器設(shè)置功率消耗上限的技術(shù)，通過(guò)CPU利用率與轉(zhuǎn)換模式功率供給單元間的關(guān)系，建立數(shù)據(jù)中心的峰值功率估算模型.但在數(shù)據(jù)庫(kù)系統(tǒng)應(yīng)用中，各個(gè)部件不會(huì)同時(shí)達(dá)到峰值點(diǎn)，系統(tǒng)供能超額配置.Chen 等[7-8]分別從進(jìn)程以及函數(shù)級(jí)對(duì)功率進(jìn)行了評(píng)估；楊良懷等[9]考察了CPU、內(nèi)存、外存和CPU執(zhí)行頻率等因素，對(duì)數(shù)據(jù)庫(kù)服務(wù)器系統(tǒng)整機(jī)系統(tǒng)進(jìn)行功率建模，構(gòu)建其軟功率計(jì),考察的是實(shí)時(shí)功率.由于峰值功率是并發(fā)操作最大聚集和，在查詢(xún)執(zhí)行中需要捕捉猝發(fā)或短期功率現(xiàn)象，評(píng)估峰值功率需要獲取CPU瞬時(shí)利用率，而CPU瞬時(shí)利用率在操作執(zhí)行過(guò)程中才能獲取，因此這項(xiàng)指標(biāo)不能用于預(yù)測(cè)峰值功率.

數(shù)據(jù)庫(kù)系統(tǒng)是數(shù)據(jù)中心的核心軟件之一，對(duì)其峰值功率的感知與控制具有重要的意義.獲取數(shù)據(jù)庫(kù)系統(tǒng)查詢(xún)操作的峰值功率是通過(guò)實(shí)際測(cè)量獲取峰值和通過(guò)軟件評(píng)估的兩種方式預(yù)測(cè)峰值.對(duì)于功率感知查詢(xún)優(yōu)化器，需要在查詢(xún)執(zhí)行前選擇具有合適峰值功率的查詢(xún)計(jì)劃，無(wú)法事先測(cè)量，通過(guò)軟件評(píng)估的方式預(yù)測(cè)峰值功率才是可行方案.Kunjir等[10]剖析了3個(gè)商用數(shù)據(jù)庫(kù)系統(tǒng)的峰值功率行為，查詢(xún)處理中峰值功率有時(shí)相當(dāng)大，可以覆蓋計(jì)算平臺(tái)整個(gè)動(dòng)態(tài)范圍，其實(shí)驗(yàn)結(jié)果表明峰值功率的行為與相應(yīng)的平均功率行為大為不同，需要對(duì)這兩個(gè)指標(biāo)分別進(jìn)行研究；同一查詢(xún)，不同商用數(shù)據(jù)庫(kù)系統(tǒng)峰值功率差別很大，說(shuō)明對(duì)峰值功率的控制是數(shù)據(jù)庫(kù)系統(tǒng)可一進(jìn)行決策的參數(shù).Yang等[11]在串行操作方式下針對(duì)查詢(xún)操作中的連接算法，在不同頻率下建立了峰值功率評(píng)估模型，并用4種連接算法進(jìn)行了驗(yàn)證，取得了一定的準(zhǔn)確性.數(shù)據(jù)庫(kù)系統(tǒng)中為改善連接算法的性能通常是基于異步I/O方式實(shí)現(xiàn)的，如何解決異步I/O連接算法的峰值功率建模問(wèn)題成為熱點(diǎn).

1 模型建立

查詢(xún)處理器需要在系統(tǒng)運(yùn)行前知道操作可能產(chǎn)生的功耗.峰值功率中需要對(duì)并行操作顯式處理，峰值功率是并發(fā)操作最大聚集和，運(yùn)行時(shí)CPU利用率是一個(gè)密切相關(guān)指標(biāo).但CPU利用率是運(yùn)行時(shí)指標(biāo)，無(wú)法用于峰值功率建模，需要找到一個(gè)類(lèi)似CPU利用率的綜合指標(biāo)來(lái)估算峰值功率，即使用CPU密集度指標(biāo)來(lái)建立峰值功率估算模型.

1.1 CPU密集度

Yang等[11-12]都引入了CPU密集度的概念，區(qū)別在于后者所考慮的負(fù)載特征中，CPU運(yùn)行狀態(tài)只包括CPU計(jì)算密集型與內(nèi)存訪問(wèn)密集型兩種，而前者把操作算法運(yùn)行中，I/O訪問(wèn)密集型也考慮進(jìn)CPU的狀態(tài)中.CPU的運(yùn)行狀態(tài)可細(xì)分為4種：CPU運(yùn)算、訪問(wèn)內(nèi)存、訪問(wèn)外存(I/O)和空閑.前3種統(tǒng)稱(chēng)為活動(dòng)態(tài).從功率評(píng)估的角度來(lái)看，CPU在不同狀態(tài)所消耗功率不同，若在不同狀態(tài)的時(shí)間能夠進(jìn)行估算，則可以近似計(jì)算計(jì)算相應(yīng)算法的功率消耗.對(duì)于數(shù)據(jù)庫(kù)連接操作，通過(guò)功耗儀測(cè)量實(shí)際運(yùn)行的功率可知，CPU在運(yùn)算和訪問(wèn)內(nèi)存這2種狀態(tài)下功率基本一致，而與IO訪問(wèn)時(shí)的功率差別較大，其原因是CPU為系統(tǒng)主要的耗能部件，前2種狀態(tài)CPU的利用率較高，而訪問(wèn)外存對(duì)CPU的利用率較低，因此把CPU運(yùn)算、訪問(wèn)內(nèi)存這兩種狀態(tài)統(tǒng)稱(chēng)為CPU密集型.采用CPU密集度定義，即在單位時(shí)間(1 s)內(nèi)CPU密集型時(shí)間所占比率(CPU密集型時(shí)間+I/O密集型時(shí)間=1 s)，CPU密集度計(jì)算式為

(1)

式中：Bcpu為CPU密集度；tcpu為CPU密集型操作的時(shí)間；T為單位時(shí)間.計(jì)算CPU密集度的關(guān)鍵在于對(duì)tcpu的估算，而tcpu的估算與操作的負(fù)載特征相關(guān).

在軟硬件配置不變的情況下，算法的峰值功率產(chǎn)生階段是不變的，連接算法的峰值功率產(chǎn)生在連接階段.合理使用異步I/O可以減少CPU等待數(shù)據(jù)的阻塞時(shí)間，故使用異步I/O來(lái)實(shí)現(xiàn)的塊嵌套循環(huán)連接(BNLJ)算法為例來(lái)說(shuō)明峰值功率的估算.

1.2 BNLJ算法峰值階段密集度計(jì)算

假設(shè)連接的兩個(gè)關(guān)系表設(shè)為R表和S表.令|R|與|S|分別表示兩個(gè)關(guān)系表的大小，且設(shè)|R|<|S|；磁盤(pán)I/O基本單位為數(shù)據(jù)塊，|IB|表示輸入緩存大小，即S表1次讀入的數(shù)據(jù)塊大?。粅OB|表示輸出緩存大小，即連接結(jié)果一次寫(xiě)出到磁盤(pán)的數(shù)據(jù)塊大??；Rblk表示R表每次讀入到緩存的大小；可用總緩存大小為M.

基于異步I/O方式實(shí)現(xiàn)的連接算法采用傳統(tǒng)雙緩存機(jī)制.輸入緩存由兩部分組成，分別用IB和IB'表示，它們的大小都用|IB|表示，其中IB區(qū)表示正在進(jìn)行CPU密集型操作的緩存區(qū)，而IB'區(qū)表示正在讀入元組的緩存區(qū)；同理，輸出緩存也由兩部分組成，分別用OB和OB'表示，它們的大小都用|OB|表示，其中OB區(qū)表示正在寫(xiě)入結(jié)果的緩存區(qū)，而OB'區(qū)表示正在將結(jié)果寫(xiě)出到磁盤(pán)的緩存區(qū).在某些情況下，IB區(qū)和OB區(qū)分別也可以進(jìn)行CPU密集型操作和寫(xiě)出操作，即當(dāng)IB'區(qū)還在進(jìn)行讀入操作時(shí)，而IB區(qū)已完成CPU密集型操作，這時(shí)將會(huì)阻塞，IB區(qū)可同時(shí)進(jìn)行讀入操作；同理，當(dāng)OB'區(qū)還在進(jìn)行寫(xiě)出操作時(shí)，而OB區(qū)已完成結(jié)果的寫(xiě)入操作，這時(shí)也會(huì)阻塞，OB區(qū)可同時(shí)進(jìn)行寫(xiě)出操作.

單位時(shí)間內(nèi)tcpu的長(zhǎng)短與讀和寫(xiě)數(shù)據(jù)塊的時(shí)間密切相關(guān)，因此需要估算讀、寫(xiě)操作的耗時(shí).設(shè)磁盤(pán)的輸入、輸出速率分別為γi，γo；讀入|IB|大小的數(shù)據(jù)塊所需的時(shí)間Tr=|IB|/γi，寫(xiě)出結(jié)果的時(shí)間Tw=|OB|/γo.其次，需要估算CPU密集型操作的耗時(shí).

對(duì)于BNLJ算法，最理想的狀態(tài)是兩個(gè)關(guān)系都可以完全讀入到內(nèi)存中并進(jìn)行連接操作，這時(shí)其性能可以達(dá)到最高.但由于內(nèi)存有限，小表R往往不能一次性讀入到可用內(nèi)存中，需要通過(guò)分割成多個(gè)數(shù)據(jù)塊多次讀入內(nèi)存來(lái)進(jìn)行.基于異步I/O實(shí)現(xiàn)的BNLJ算法基本流程是：先確定輸入緩存大小|IB|和輸出緩存大小|OB|，將R表的一部分讀入緩存中并構(gòu)建其哈希表；然后將S表循環(huán)讀入輸入緩存IB和IB'區(qū)進(jìn)行連接操作，連接結(jié)果放入輸出緩存OB和OB'區(qū)，最后輸出到磁盤(pán)中；遍歷完S表后(內(nèi)層循環(huán)結(jié)束)，清理原先讀入的一部分R表并讀入新的一部分，重復(fù)以上操作，直至將小表R完全遍歷(外層循環(huán)結(jié)束).

元組在連續(xù)的連接過(guò)程中不訪問(wèn)外存，是CPU密集型操作；但在連接過(guò)程中，元組連接速度很快，且輸入輸出緩存大小有限，在所考察的單位時(shí)間T內(nèi)可能會(huì)發(fā)生I/O，即從磁盤(pán)中讀入S表/R表或?qū)懗鲞B接結(jié)果到磁盤(pán)，而這兩種操作皆為IO密集型操作，所以tcpu為單位時(shí)間內(nèi)連接元組的時(shí)間長(zhǎng)度.由于需要估算CPU密集型操作的耗時(shí)，故設(shè)連接|IB|大小的數(shù)據(jù)塊所需的時(shí)間設(shè)為T(mén)ij，連接結(jié)果填充滿(mǎn)|OB|大小的輸出緩存所需的連接時(shí)間設(shè)為T(mén)oj.

估算BNLJ的連接時(shí)間tcpu時(shí)，筆者采用單位時(shí)間內(nèi)連接元組數(shù)N與平均每對(duì)元組連接用時(shí)的乘積來(lái)計(jì)算.元組在連接時(shí)分兩種情況，一種是元組探測(cè)后找到可連接元組，并進(jìn)行連接；另一種是元組探測(cè)后發(fā)現(xiàn)沒(méi)有匹配的連接對(duì)象，直接丟棄.因此，估算連接時(shí)間時(shí)需要對(duì)這兩種操作進(jìn)行區(qū)分.假設(shè)輸入緩存IB或IB'中可與Rblk元組進(jìn)行連接概率為P，其估計(jì)可以根據(jù)關(guān)系R與S在連接屬性Y上相等的概率為1/max(V(R,Y),V(S,Y))計(jì)算，其中V(*,Y)表示某關(guān)系在屬性Y取相異值的個(gè)數(shù)，則輸入緩存IB或IB'連接所需要的時(shí)間計(jì)算式為

Tjoin(P,Njoin)=NblkR·Njoin·Tprobe+
P·Njoin·Tjoin

(2)

式中：NblkR為Rblk包含的元組數(shù)；Njoin為單位時(shí)間里連接S表的元組數(shù)；Tprobe，Tjoin分別為探測(cè)和連接.

式(2)中直接確定連接總元組數(shù)Njoin比較困難，在每次讀入輸入緩存后，通常連接過(guò)程會(huì)遇到兩種情況：1) 連接結(jié)果未填滿(mǎn)輸出緩存區(qū)，而輸入緩存區(qū)的元組已經(jīng)完成連接，必須從磁盤(pán)讀數(shù)據(jù)至輸入緩存；2) 連接結(jié)果填滿(mǎn)輸出緩存區(qū)，必須對(duì)其進(jìn)行輸出.由于連接過(guò)程可能是非連續(xù)的，為了計(jì)算Njoin則必須重現(xiàn)連接的邏輯過(guò)程，對(duì)整個(gè)單位時(shí)間里的連接元組數(shù)量進(jìn)行累計(jì)，為此需設(shè)計(jì)相應(yīng)算法進(jìn)行處理.

在提出算法之前，還需要估算Tij和Toj兩個(gè)參數(shù).評(píng)估這兩個(gè)參數(shù)需要分別確定|IB|大小數(shù)據(jù)塊中包含的元組數(shù)量NblkS和產(chǎn)生|OB|大小的連接結(jié)果所需連接元組條數(shù)NS-needed.假設(shè)元組大小均勻分布，R表與S表的平均元組大小分別表示為|tR|與|tS|，則NblkR與NblkS分別為Rblk/|tR|，|IB|/|tS|；由于連接是將兩條元組進(jìn)行拼接，對(duì)應(yīng)產(chǎn)生的結(jié)果大小可表示為|tR|+|tS|，再結(jié)合連接概率為P，則NS-needed計(jì)算式為

(3)

由式(2，3)可得：Tij=Tjoin(P,NblkS)，Toj=Tjoin(P,NS-needed).

1.3 CPU密集度估算方法

按照CPU密集度的定義，峰值階段從不同的起始位置取單位時(shí)間間隔得到的CPU密集型操作時(shí)間長(zhǎng)短不同，即CPU密集度不一樣，而功率測(cè)量值是單位時(shí)間的積分值.故從理論上來(lái)說(shuō)，峰值功率對(duì)應(yīng)操作執(zhí)行過(guò)程中CPU密集度最大點(diǎn)，對(duì)峰值功率對(duì)應(yīng)的CPU密集度的估算需要選擇使CPU密集度最大的起始點(diǎn).

評(píng)估連接算法的峰值功率就是找出算法執(zhí)行過(guò)程中CPU密集度最大的單位時(shí)間段.對(duì)此，有以下命題：

命題在無(wú)I/O阻塞情況下，形成最大CPU密集度的單位時(shí)間段起始點(diǎn)在輸入緩存區(qū)IB讀取完成，且IB'讀取完成的時(shí)刻不晚于IB連接完成的時(shí)刻.

證明首先證明起始點(diǎn)是在輸入緩存區(qū)IB讀取完成時(shí).假設(shè)起始點(diǎn)不在輸入緩存區(qū)IB讀取完成時(shí)，即當(dāng)前IB未讀取完數(shù)據(jù)，那么單位時(shí)間內(nèi)必定有段時(shí)間是要等待其完成讀入，CPU密集度無(wú)法達(dá)到最大，故起始點(diǎn)是在輸入緩存區(qū)IB讀取完成時(shí).其次證明由于IB'讀取完成的時(shí)刻不晚于IB連接完成的時(shí)刻.由于使用雙緩存形式來(lái)實(shí)現(xiàn)基于異步I/O的BNLJ連接算法，故在整個(gè)連接過(guò)程中，IB和IB'會(huì)不斷重復(fù)地進(jìn)行“讀取數(shù)據(jù)-連接”循環(huán)操作.當(dāng)IB區(qū)完成連接時(shí)，若IB'區(qū)未完成讀入，則會(huì)阻塞一段時(shí)間，在單位采樣時(shí)間內(nèi)，將會(huì)有段時(shí)間用于I/O操作.對(duì)于IB'而言，就相當(dāng)于其計(jì)算密集度的起始時(shí)間前移.因此，IB'讀取完成的時(shí)刻不晚于IB連接完成的時(shí)刻.綜合上述情況，可得出在無(wú)I/O阻塞情況下，形成最大CPU密集度的單位時(shí)間段起始點(diǎn)在輸入緩存區(qū)IB讀取完成，且IB'讀取完成的時(shí)刻不晚于IB連接完成的時(shí)刻這一結(jié)論.

CPU密集度估算需用到幾個(gè)變量：tij為完成IB未連接部分預(yù)計(jì)需要的連接時(shí)間，根據(jù)前述命題，最大CPU密集度發(fā)生在輸入緩存IB讀取完成后，因此tij初始值賦為T(mén)ij；toj為填滿(mǎn)輸出緩存OB剩余空間預(yù)計(jì)需要的連接時(shí)間，由于輸出緩存初始為空，因此toj初始值賦為T(mén)oj；tir為從磁盤(pán)讀取數(shù)據(jù)填滿(mǎn)IB剩余空間預(yù)計(jì)所需的讀取時(shí)間，同理根據(jù)最大CPU密集度發(fā)生在輸入緩存讀取完成后，tir初始值賦為0；tow為完成OB未寫(xiě)出部分預(yù)計(jì)所需的寫(xiě)出時(shí)間，由于一開(kāi)始輸出緩沖區(qū)為空，故tow初始值賦為0；tr為從磁盤(pán)讀取數(shù)據(jù)填滿(mǎn)IB'剩余部分所需的讀取時(shí)間，根據(jù)命題IB與IB'一開(kāi)始可以同時(shí)異步讀取完成，故tr初始值賦為0；tw為完成OB'未寫(xiě)出部分所需的寫(xiě)出時(shí)間，由于一開(kāi)始輸出緩沖區(qū)為空，故tw初始值賦為0.由于CPU密集度定義為在單位時(shí)間(1 s)內(nèi)CPU密集型操作時(shí)間所占的比率，故引入表示剩余運(yùn)行時(shí)間的變量tleft，初值賦為1 s.

得到上述參數(shù)后，可以進(jìn)行模擬BNLJ連接算法峰值功率產(chǎn)生階段的執(zhí)行過(guò)程.算法在連接階段的基本流程為：初始狀態(tài)時(shí)IB和IB'已完成讀取，可進(jìn)行連接操作；OB和OB'為空，可進(jìn)行連接結(jié)果的寫(xiě)入操作.IB進(jìn)行連接時(shí)，將其連接結(jié)果寫(xiě)入OB，使用異步I/O的方式實(shí)現(xiàn)算法，故與此同時(shí)可進(jìn)行IB'的讀入與OB'的寫(xiě)出，要分別更新兩者的時(shí)間tr和tw.當(dāng)IB的元組完成連接時(shí)，若IB'已完成讀入，則交換IB與IB'，繼續(xù)進(jìn)行連接；否則，阻塞.同理，當(dāng)OB被連接結(jié)果填滿(mǎn)時(shí)，若OB'已完成寫(xiě)出，即已可用，則交換OB與OB'，繼續(xù)進(jìn)行連接；否則，阻塞.

連接過(guò)程中將會(huì)出現(xiàn)3種阻塞情況：

1) 當(dāng)IB完成連接操作，而IB'還未完成讀取操作，其阻塞時(shí)間取決于IB'的tr時(shí)間；

2) 當(dāng)OB完成連接結(jié)果的寫(xiě)入操作，而OB'還未完成寫(xiě)出操作，其阻塞時(shí)間取決于OB'的tw時(shí)間；

3) 當(dāng)上述2種情況同時(shí)存在，即當(dāng)IB'未完成讀取且OB'未完成寫(xiě)出造成阻塞，其阻塞時(shí)間為tr和tw兩者中的較長(zhǎng)者.阻塞時(shí)，只進(jìn)行I/O操作.

給定參數(shù)上述參數(shù)后，可對(duì)tcpu進(jìn)行估算.CPU密集度最大的單位時(shí)間段的計(jì)算算法，見(jiàn)算法ComputeAIO-tcpu.

算法1ComputeAIO-tcpu

輸入：|IB|,|OB|；輸出：?jiǎn)挝粫r(shí)間中CPU密集型操作的時(shí)間tcpu.

1) 初始化CPU占用時(shí)間tcpu←0，單位時(shí)間1 s中所剩余時(shí)間tleft←1，完成連接輸入緩存IB中元組所需時(shí)間tij←Tij，填滿(mǎn)輸出緩存OB所需連接時(shí)間toj←Toj，讀取IB'未讀入部分所需時(shí)間tr←0，讀取IB未讀入部分所需時(shí)間tir←0，寫(xiě)出OB'未寫(xiě)出部分所需時(shí)間tw←0，以及寫(xiě)出OB區(qū)未寫(xiě)出部分所需時(shí)間tow←0.

2) 判斷tleft是否大于0，若是則轉(zhuǎn)至步驟3)，否則終止并輸出tcpu.

3) 若剩余時(shí)間tleft足夠連接完IB，轉(zhuǎn)至步驟4)，否則轉(zhuǎn)至步驟8).

4) 若IB連接的結(jié)果不夠填滿(mǎn)OB，則轉(zhuǎn)至步驟7)，否則轉(zhuǎn)至步驟5).

5) 若IB連接的結(jié)果多于填滿(mǎn)OB所需的量，則將IB的部分元組進(jìn)行連接(tij←tij-toj)，與此同時(shí)，可異步進(jìn)行IB'的讀入(Update(tr,toj))與OB'的寫(xiě)出(Update(tw,toj))，直到連接結(jié)果填滿(mǎn)OB為止(tow←Tw)，更新tcpu←tcpu+toj和tleft←tleft-toj，獲取可用的輸出緩存(getEmptyOB())并記為OB，重復(fù)步驟2)，否則轉(zhuǎn)至步驟6).

6) 若IB連接的結(jié)果剛好填滿(mǎn)OB，更新tcpu←tcpu+toj和tleft←tleft-toj，與此同時(shí)，可異步進(jìn)行IB'的讀入(Update(tr,toj))與OB'的寫(xiě)出(Update(tw,toj))，直到IB連接完成并且連接結(jié)果填滿(mǎn)OB為止(tir←Tr，tow←Tw).若IB'的未讀入部分所需時(shí)間比OB'未寫(xiě)出部分所需時(shí)間短，即阻塞等待OB'完成寫(xiě)出，先獲取可用的輸入緩存(getReadyIB())并記為IB，再獲取可用的輸出緩存(getEmptyOB())并記為OB；否則，阻塞等待IB'完成讀入，先獲取可用輸出緩存并記為OB，再取可用的輸入緩存并記為IB，重復(fù)步驟2).

7) 連接IB的所有剩余元組(toj←toj-tij)，與此同時(shí)，可異步進(jìn)行IB'的讀入(Update(tr,tij))與OB'的寫(xiě)出(Update(tw,tij))，直到完成IB連接(tir←tr)，更新tleft←tleft-tij和tcpu←tcpu+tij，獲取可用的輸入緩存(getReadyIB())并記為IB，重復(fù)步驟2).

8) 若剩余時(shí)間tleft足夠連接填滿(mǎn)OB，則將IB剩余部分元組進(jìn)行連接(tij←tij-toj)，與此同時(shí)，可異步進(jìn)行IB'的讀入(Update(tr,toj))與OB'的寫(xiě)出(Update(tw,toj))，直到連接結(jié)果填滿(mǎn)OB為止(tow←tw)，更新tleft←tleft-toj和tcpu←tcpu+toj，獲取可用的輸出緩存(getEmptyOB())并記為OB，重復(fù)步驟2).否則轉(zhuǎn)至步驟9).

9) 即剩余時(shí)間tleft不夠連接完IB且不夠連接填滿(mǎn)OB，將IB的部分元組進(jìn)行連接，連接結(jié)果寫(xiě)入OB，更新tcpu←tcpu+tleft，直到tleft←0.

算法2Update(t,tp)

輸入：t,tp；輸出：緩存區(qū)剩余讀/寫(xiě)所需時(shí)間t.

1) 若tp小于等于緩存區(qū)剩余讀/寫(xiě)所需時(shí)間t，則更新t←t-tp，否則轉(zhuǎn)至步驟2).

2) 緩存區(qū)剩余讀/寫(xiě)所需時(shí)間t←0.

算法3getReadyIB()

輸入：tleft,tr,tir,tw,tow；輸出：可用的輸入緩存IB，tleft.

1) 判斷IB'是否讀取完整，若是則轉(zhuǎn)至步驟5)，否則轉(zhuǎn)至步驟2).

2) 判斷剩余時(shí)間tleft是否足夠讀取填滿(mǎn)IB'，若是則轉(zhuǎn)至步驟3)，否則轉(zhuǎn)至步驟4).

3) 將元組讀取填滿(mǎn)IB'，與此同時(shí)，可異步進(jìn)行IB的讀入(Update(tir,tr))，OB和OB'的寫(xiě)出(Update(tw,tr) , Update(tow,tr))，更新tleft←tleft-tr，轉(zhuǎn)至步驟5).

4) 剩余時(shí)間tleft不夠讀取填滿(mǎn)IB'，則tleft←0，轉(zhuǎn)至步驟5).

5)IB'已讀取完整，則交換IB與IB'，更新IB'未連接部分時(shí)間tr←tir，IB未連接部分時(shí)間tir←0.

算法4getEmptyOB()

輸入：tleft,tr,tir,tw,tow；輸出：可用的輸出緩存OB,tleft.

1) 判斷OB'是否完成寫(xiě)出，若是則轉(zhuǎn)至步驟5)，否則轉(zhuǎn)至步驟2).

2) 判斷剩余時(shí)間tleft是否足夠?qū)懗鯫B'，若是則轉(zhuǎn)至步驟3)，否則轉(zhuǎn)至步驟4).

3) 將OB'數(shù)據(jù)進(jìn)行寫(xiě)出，與此同時(shí)，可異步進(jìn)行IB和IB'的讀入(Update(tr,tw) , Update(tir,tw))，OB的寫(xiě)出(Update(tow,tw))，更新tleft←tleft-tw，轉(zhuǎn)至步驟5).

4) 剩余時(shí)間tleft不夠完成OB'寫(xiě)出，則tleft←0，轉(zhuǎn)至步驟5).

5)OB'已完成寫(xiě)出，則交換OB與OB'，更新OB'未寫(xiě)出部分時(shí)間tw←tow，OB未寫(xiě)出部分時(shí)間tow←0.

1.4 峰值模型建立

峰值功率對(duì)應(yīng)于算法執(zhí)行過(guò)程中CPU密集度最大點(diǎn)，在測(cè)量數(shù)據(jù)過(guò)程中峰值功率對(duì)應(yīng)的實(shí)際起始點(diǎn)與理論起始點(diǎn)可能會(huì)略有偏差，考慮到測(cè)量的準(zhǔn)確性，對(duì)測(cè)量進(jìn)行多次重復(fù)，為了避免偏差較大的值干擾，取每組測(cè)量所得的眾數(shù)作為測(cè)量結(jié)果.為產(chǎn)生不同CPU利用率的人工負(fù)載，對(duì)BNLJ算法進(jìn)行改造，通過(guò)控制讀入數(shù)據(jù)塊(多次重復(fù)連接同一塊數(shù)據(jù))，改變連接結(jié)果輸出緩存的大小，從而產(chǎn)生不同大小的CPU密集度，據(jù)此進(jìn)行CPU密集度與峰值功率關(guān)系的建模.

計(jì)算機(jī)空閑態(tài)功率是維持各個(gè)部件正常運(yùn)行的基本功率，不同執(zhí)行頻率下對(duì)應(yīng)的空閑態(tài)功率相同，這部分功率作為靜態(tài)功率.為了更直觀地表示算法執(zhí)行狀態(tài)對(duì)功率的影響，在構(gòu)建功率模型時(shí)將去除這部分功率，即用測(cè)量得到的整機(jī)功率減去靜態(tài)功率所得到的動(dòng)態(tài)功率作為測(cè)量功率在圖表中進(jìn)行展示.測(cè)量人工負(fù)載在不同CPU密集度時(shí)在不同頻率下(2.8，3.1，3.3 GHz)其峰值功率的大小，得到峰值功率與CPU密集度(Bcpu)關(guān)系如圖1所示.

圖1 不同頻率下CPU密集度與峰值功率關(guān)系Fig.1 The relationship between CPU-boundedness and peak power with varying frequencies

由圖1可知：不同頻率下，峰值功率隨CPU密集度變化呈現(xiàn)了3個(gè)階段.CPU密集度在第1階段時(shí)處于平穩(wěn)狀態(tài)，其原因是算法運(yùn)行時(shí)必須要耗費(fèi)一定的能量才能維持基本的運(yùn)行，所以在這個(gè)階段呈現(xiàn)平穩(wěn)趨勢(shì)；CPU密集度在第2階段時(shí)處于較為明顯的上升狀態(tài)；CPU密集度在第3階段時(shí)又處于平穩(wěn)狀態(tài)，其原因是CPU被不斷請(qǐng)求操作，在機(jī)器耗能尚未瞬間降低時(shí)，而新的請(qǐng)求又到達(dá)，從而導(dǎo)致CPU一直處于高耗能狀態(tài).可見(jiàn)CPU密集度對(duì)峰值功率的影響只是在一定范圍內(nèi)呈現(xiàn)正相關(guān)的關(guān)系.為此，先針對(duì)CPU執(zhí)行頻率為3.3 GHz的情況對(duì)CPU密集度與峰值功率進(jìn)行建模，使用建模工具Eureqa對(duì)獲得的測(cè)量數(shù)據(jù)進(jìn)行回歸建模，擬合曲線(xiàn)時(shí)可以選取不同類(lèi)型的運(yùn)算和不同的擬合曲線(xiàn)，選取常數(shù)C，變量x，+，-，×，/，power函數(shù)和logistic函數(shù).經(jīng)過(guò)多種模型的嘗試，選取模型為

P=4.69+6.58×logistic(45.8×Bcpu-13.6)

(4)

式(4)擬合的均方根誤差RMSE(Root-mean-square error)為0.351，模型擬合CPU密集度與峰值功率關(guān)系如圖2所示，CPU密集度取值范圍為0.13～1.

圖2 不同模型的峰值功率預(yù)測(cè)Fig.2 Peak power prediction by different models

對(duì)不同頻率下的CPU密集度與功率之間的關(guān)系仍然采用上述方法進(jìn)行擬合，分別得到的標(biāo)準(zhǔn)誤差RMSE均在0.37以?xún)?nèi)，整體模型用抽象形式表示，即在頻率為f時(shí)峰值功率P與CPU密集度Bcpu之間的關(guān)系，即

Pf=α+β×logistic(γ×Bcpu-δ)

(5)

式中：α，β，γ，δ分別為常數(shù)參數(shù)，各頻率下的常數(shù)參數(shù)值與RMSE值如表1所示.

表1不同頻率下預(yù)測(cè)模型的參數(shù)值及RMSE值

Table1ParametersandRMSEofpredictmodelsunderdifferentCPUfrequency

f/GHzαβγδRMSE3.34.696.5845.813.60.3513.14.676.7555.320.40.3642.810.3-5.56-79.5-24.20.359

2 實(shí)驗(yàn)評(píng)價(jià)

為了評(píng)價(jià)第1節(jié)中預(yù)測(cè)模型的準(zhǔn)確性，采用C++以及異步I/O機(jī)制實(shí)現(xiàn)了BNLJ算法，對(duì)BNLJ配置不同緩存，得到21組不同值的CPU密集度，用功耗儀測(cè)量不同CPU密集度時(shí)對(duì)應(yīng)的峰值功率，比較峰值功率的實(shí)際值與預(yù)測(cè)值的相對(duì)誤差來(lái)評(píng)價(jià)模型準(zhǔn)確性.功耗儀采樣率1 Hz.

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

實(shí)驗(yàn)環(huán)境采用的硬件配置以及軟件版本如表2所示.

表2 實(shí)驗(yàn)環(huán)境Table 2 Experimental environment

2.2 實(shí)驗(yàn)設(shè)計(jì)及結(jié)果

實(shí)驗(yàn)涉及到CPU密集度的計(jì)算，給定具體的參數(shù)|R|，|S|，|IB|，|OB|，Rblk后，針對(duì)實(shí)驗(yàn)環(huán)境需要確定1.1節(jié)中各個(gè)待定參數(shù)γi，γo，|tR|，|tS|，P，Tprobe，Tjoin.使用Iometer工具對(duì)硬盤(pán)進(jìn)行測(cè)量，得出磁盤(pán)I/O速率在不同塊大小下的速率統(tǒng)計(jì)表如表3所示.

表3 磁盤(pán)I/O速率統(tǒng)計(jì)Table 3 The statistics of disk I/O rate

實(shí)驗(yàn)中連接的兩張表采用TPC-H測(cè)試基準(zhǔn)規(guī)模5產(chǎn)生的CUSTOMER(對(duì)應(yīng)前面的R表，大小為129 MB，元組數(shù)NR=750 000)和ORDERS(對(duì)應(yīng)前面的S表，大小為948 M，元組數(shù)NS=7500 000)，作為連接算法的負(fù)載.經(jīng)過(guò)估算R表與S表的平均元組大小|tR|與|tS|都均為170字節(jié).

由數(shù)據(jù)表的分布特征可知max(V(R,Y),V(S,Y))為NR.對(duì)BNLJ算法而言，通常由于|R|>M而將R表分割多次讀入，故每趟讀入的Rblk<|R|，則S表與Rblk的連接概率P為NblkR/NR，其中Rblk大小為(M-2·|IB|-2·|OB|)/F.

通過(guò)連接探測(cè)或連接大量的元組對(duì)Tprobe和Tjoin估算，用測(cè)得的總時(shí)間除以連接的元組對(duì)數(shù)得到每對(duì)元組探測(cè)和連接排序的平均時(shí)間.筆者對(duì)2種頻率下的數(shù)據(jù)進(jìn)行測(cè)量，結(jié)果如表4所示.

表4 元組探測(cè)和連接時(shí)間統(tǒng)計(jì)Table 4 Time of probe and join

在獲取以上參數(shù)后，便可以根據(jù)BNLJ運(yùn)行時(shí)的軟硬件配置環(huán)境計(jì)算得到21組不同的CPU密集度.利用21組輸入輸出緩存大小對(duì)BNLJ算法進(jìn)行配置，測(cè)量對(duì)應(yīng)的峰值功率，與模型預(yù)測(cè)值進(jìn)行對(duì)比.兩種頻率的驗(yàn)證結(jié)果如圖3所示，不同CPU頻率下模型的平均相對(duì)誤差如表5所示.

圖3 不同頻率下峰值功率實(shí)際值與預(yù)測(cè)值對(duì)比Fig.3 The comparison of real and predict values

f /GHz2.83.13.3平均相對(duì)誤差/%3.753.943.27

由實(shí)驗(yàn)結(jié)果可知：各個(gè)算法在不同頻率下的平均相對(duì)誤差范圍在4%以?xún)?nèi)，說(shuō)明具有一定的準(zhǔn)確性.

3 結(jié) 論

針對(duì)功率感知數(shù)據(jù)庫(kù)系統(tǒng)中連接算法的峰值功率建模問(wèn)題，使用了CPU密集度指標(biāo)作為CPU功率的指示量，建立了基于異步I/O方式實(shí)現(xiàn)的連接算法的峰值功率預(yù)測(cè)模型，并對(duì)其進(jìn)行了實(shí)驗(yàn)驗(yàn)證，結(jié)果表明：預(yù)測(cè)模型具有較好的準(zhǔn)確性，其平均相對(duì)誤差小于4%.數(shù)據(jù)庫(kù)系統(tǒng)可采用此方法對(duì)查詢(xún)操作各個(gè)算法的峰值功率進(jìn)行評(píng)估，在連接算法執(zhí)行之前只需給定數(shù)據(jù)庫(kù)統(tǒng)計(jì)信息以及當(dāng)時(shí)系統(tǒng)配置信息，便可以估算峰值功率產(chǎn)生階段的CPU密集度來(lái)預(yù)測(cè)相應(yīng)的峰值功率，可用于功率感知數(shù)據(jù)庫(kù)系統(tǒng)的查詢(xún)處理與優(yōu)化.