吳林陽 羅 蓉 郭雪婷 郭 崎

(中國科學(xué)院計算技術(shù)研究所 北京 100190)(wulinyang@ict.ac.cn)

在設(shè)計現(xiàn)代計算機系統(tǒng)時首先要考慮的因素是能效.為了提高系統(tǒng)能效，諸如FPGA，GPU和定制加速器等硬件加速器已被廣泛應(yīng)用于工業(yè)領(lǐng)域.使用硬件加速器的典型案例有：微軟組建FPGA服務(wù)器用于加速大規(guī)模的數(shù)據(jù)中心服務(wù)[1]；亞馬遜于2010年開始部署GPU云服務(wù)器；惠普實驗室為Memcached定制加速器[2].通常，硬件加速器集成在處理器芯片中(例如SIMD單元、卷積引擎[3]、IBM的PowerEN[4])，或部署為一個獨立的芯片(例如GPU顯卡、FPGA板卡和Xeon Phi協(xié)處理器)，通過PCI-E與主處理器進行通信.

隨著靠近數(shù)據(jù)的處理(near-data processing)技術(shù)的出現(xiàn)，將硬件加速器集成到DRAM堆棧中以降低數(shù)據(jù)移動的成本成為一種新的系統(tǒng)設(shè)計思路.其基本思想是利用3D堆疊技術(shù)，將一些包含加速器的邏輯die和多個DRAM die垂直集成到一個芯片中[5-7].然而，由于3D堆疊DRAM在面積、功耗、散熱和制造等方面的限制，能夠集成到DRAM中的加速器的數(shù)量和類型是有限的.因此，給定一個需要加速的目標(biāo)應(yīng)用，確定其中哪些部分最適合在DRAM中加速是至關(guān)重要的.

理想的加速目標(biāo)應(yīng)該是內(nèi)存帶寬受限的，因為3D堆疊DRAM具有比現(xiàn)有系統(tǒng)高一個數(shù)量級的高內(nèi)存帶寬.一個最典型的例子是數(shù)據(jù)重組操作，它是許多應(yīng)用領(lǐng)域的關(guān)鍵組成部分，如高性能計算、信號處理和生物信息學(xué).數(shù)據(jù)重組只包含CPU和DRAM之間的往返數(shù)據(jù)移動，它不消耗浮點運算周期.因此，在DRAM中加速數(shù)據(jù)重組是很自然的想法，文獻(xiàn)[8]中論證了這項工作.但是對于大多數(shù)真實應(yīng)用程序來說，它們混合了計算和數(shù)據(jù)移動，情況更為復(fù)雜.

在本文中，我們進行了一個hash joins的案例研究，探索如何將它在CPU和DRAM之間進行合適的加速任務(wù)劃分.選擇hash joins有3個原因：1)hash joins不僅是傳統(tǒng)數(shù)據(jù)庫系統(tǒng)的基本操作，還是諸如Spark[9]等主流大數(shù)據(jù)系統(tǒng)的關(guān)鍵操作；2)很多文獻(xiàn)都對hash joins做了充分研究[10-15]，因此加速的baseline已經(jīng)高度優(yōu)化；3)最先進的hash joins: optimized version of radix join algorithm(PRO)[11,15]是帶寬資源受限的，它可能會從內(nèi)存加速中受益.我們對PRO以及PARSEC benchmark suite中具有代表性的多線程應(yīng)用程序分別進行了帶寬分析，如圖1所示.平均來看，PRO對帶寬的需求比使用8線程的PARSEC benchmark高3.6倍.與PARSEC benchmark suite中帶寬資源受限最嚴(yán)重的streamcluster相比，在2，4和8線程下，PRO仍多消耗143%，117%和18%的帶寬資源.

為了研究在PRO中內(nèi)存訪問對總能耗的貢獻(xiàn)，我們對PRO的3個不同階段：partition，build和probe，進行了詳細(xì)的能耗分析.雖然所有階段的內(nèi)存帶寬都趨于飽和，但各個階段中計算所消耗的能量差異是很大的.在partition階段，計算消耗的能量還不到該階段總能量的50%；而在build和probe階段，計算消耗的能量占總能量的85%以上.換句話說，數(shù)據(jù)移動消耗的能量是partition階段能耗的主要部分.主要的原因是在partition階段有許多高代價的非規(guī)則內(nèi)存訪問，而其他2個階段只有常規(guī)的內(nèi)存訪問.因此，僅在DRAM端加速partition階段，在CPU端加速其余階段是有意義的.為了加速partition階段，我們構(gòu)建了適合于3D堆疊結(jié)構(gòu)的hash分區(qū)加速器(hash partition accelerator, HPA).為了加快build和probe階段，我們采用傳統(tǒng)的SIMD加速單元來提高計算效率.

Fig. 1 Memory bandwidth of PARSEC benchmarks and Radix hash join圖1 PARSEC benchmarks和Radix hash join的內(nèi)存帶寬分析

本文的創(chuàng)新點和貢獻(xiàn)可以概括如下：

1) 以數(shù)據(jù)移動為驅(qū)動的加速任務(wù)劃分方法.我們提出了一種以數(shù)據(jù)移動為驅(qū)動的方法來劃分CPU和DRAM之間的加速任務(wù)，使得我們能夠在滿足3D堆疊DRAM面積、功耗、發(fā)熱的嚴(yán)格限制條件下，充分挖掘其加速性能.

2) 最先進的hash joins的詳細(xì)分析.我們對最先進的hash joins算法進行了詳細(xì)的性能和能耗分析.性能分析結(jié)果顯示，最先進的hash joins(PRO)本質(zhì)上是內(nèi)存受限的.我們的能耗分析結(jié)果顯示，在partition階段，總能量的50%以上被數(shù)據(jù)移動和流水線阻塞所消耗，這可以通過在內(nèi)存端進行加速得到顯著緩解.在build和probe階段，只有大約15%的能量被數(shù)據(jù)移動和流水線阻塞所消耗，這仍然可以利用現(xiàn)有的CPU端加速單元(如SIMD單元)進行加速.

3) hash分區(qū)加速器的設(shè)計.我們設(shè)計了一個hash分區(qū)加速器(HPA)，并將其集成到3D堆疊DRAM的邏輯層中.HPA包含3個主要的部件：hash unit， histogram unit和shuffle unit.此外，我們探索了設(shè)計空間，使得我們能夠在多種3D堆疊DRAM配置中找到HPA的最佳設(shè)計方案.實驗結(jié)果表明，與現(xiàn)有系統(tǒng)相比，HPA提高了3個數(shù)量級的能效.

4) 針對hash joins的混合加速系統(tǒng).我們建立了一個混合加速系統(tǒng)，該系統(tǒng)包含內(nèi)存端定制的加速器和處理器端SIMD加速器，這個系統(tǒng)能提高h(yuǎn)ash joins的整體能效.實驗結(jié)果表明，平均而言，該系統(tǒng)在英特爾Haswell和Xeon Phi處理器上分別提高了48倍和20倍的能效.

1 背景介紹

1.1 hash joins

join操作是將2個或多個關(guān)系表中的元組組合起來的基本數(shù)據(jù)庫操作，hash joins被認(rèn)為是內(nèi)存數(shù)據(jù)庫管理系統(tǒng)中最流行的join算法之一.此外，hash joins也被廣泛應(yīng)用在Spark等大數(shù)據(jù)平臺中.現(xiàn)有的hash joins算法大致可以分為2類，即不考慮硬件結(jié)構(gòu)的hash joins和考慮硬件結(jié)構(gòu)的hash joins[11].

1) 不考慮硬件結(jié)構(gòu)的join.該類join算法不關(guān)心運行算法的底層硬件結(jié)構(gòu).簡單hash joins算法(SHJ)就是一種典型的不考慮硬件結(jié)構(gòu)join算法，它包括2個階段：build和probe.在build階段，掃描較小的關(guān)系表R，建立一個hash表;然后在probe階段，遍歷S關(guān)系表中的每個元組，在hash表中找到與之匹配的R關(guān)系表中的元組.文獻(xiàn)[10]提出了SHJ的并行版本：no partition algorithm (NPO)，用以挖掘多核架構(gòu)的并行性.NPO的關(guān)鍵是把輸入關(guān)系表R和S分成相等大小的部分，每個部分被分配到一個工作線程進行處理.然而，由于NPO的hash過程中存在大量的隨機內(nèi)存訪問，可能導(dǎo)致大量的cache miss，使得能效下降.這就是不考慮硬件結(jié)構(gòu)的join算法的缺點.

2) 考慮硬件結(jié)構(gòu)的join.為了更好地利用高速緩存的層次結(jié)構(gòu)，考慮硬件結(jié)構(gòu)的join算法被大量研究.文獻(xiàn)[16]提出了一種新的可以充分利用高速緩存的磁盤連接算法DBCC-join.它將執(zhí)行過程分成了2個階段：JPIPT構(gòu)建階段和結(jié)果輸出階段，并在JPIPT構(gòu)建階段構(gòu)建索引時充分考慮了高速緩存的特性.此外，為了充分利用高速緩存和TLB的局部性，radix partition被廣泛采用[17].PRO[11,15]是目前最先進的一種hash joins算法.PRO算法分為3個階段：partition,build和probe.

① partition.圖2給出了PRO的partition階段.該階段可以進一步分為4個階段：local histogram, prefix sum, output addressing, data shuffling.其中，local histogram和data shuffling階段占總執(zhí)行時間的99%以上.在local histogram階段，掃描分塊的輸入關(guān)系表(R或S)rel，建立一個histogram數(shù)組my_hist；在data shuffling階段，rel中的元組根據(jù)存儲在dst數(shù)組中的位置被復(fù)制到目標(biāo)分組tmp，完成對關(guān)系表rel的劃分.

Fig. 2 The partition phase of PRO
圖2 PRO的partition階段

② build.圖3給出了PRO的build階段.在這一階段中掃描較小的關(guān)系表R，建立next和bucket數(shù)組.next數(shù)組用于追蹤被hash到同一個簇中的上一個R元組；而bucket數(shù)組用于追蹤被hash到當(dāng)前簇的最后一個R元組.

Fig. 3 The build phase of PRO
圖3 PRO的build階段

③ probe.圖4給出了PRO的probe階段.關(guān)系表S中的每一個元組hash成一個bucket數(shù)組的索引.然后檢索bucket和next，嘗試找到與該S元組匹配的R元組.

Fig. 4 The probe phase of PRO
圖4 PRO的probe階段

1.2 內(nèi)存端加速

作為減少計算單元與內(nèi)存之間通信開銷的一種有前景的技術(shù)，內(nèi)存中處理(PIM)在過去幾十年受到了廣泛關(guān)注.PIM的基本思想是將簡單的處理邏輯集成到傳統(tǒng)的DRAM或嵌入式DRAM(eDRAM)陣列中[18].比如，可以將SIMD加速單元集成到DRAM die中[19-20]；還可以將可重構(gòu)計算邏輯集成到DRAM die中，構(gòu)建ActivePage[21].然而，PIM技術(shù)的實現(xiàn)面臨一個主要障礙：內(nèi)存加工工藝與邏輯單元加工工藝有很大的不同.用同樣的工藝制造出單個芯片不能充分發(fā)揮出PIM的優(yōu)勢.

垂直3D die堆疊技術(shù)允許將多個存儲器die直接疊加在處理器die上，從而提高內(nèi)存帶寬[22-25].這些 die與短、快速、密集的TSV集成在一起，提供了非常高的內(nèi)部帶寬.雖然發(fā)熱問題是異構(gòu)die堆疊的一個主要問題，但是仍然出現(xiàn)了一些3D堆疊內(nèi)存產(chǎn)品，比如三星、Tezzaron、Micron生產(chǎn)的3D堆疊內(nèi)存.以Micro的Hybrid Memory Cube(HMC)為例，它在邏輯層之上堆疊多個DRAM die，邏輯層中包含能夠訪問垂直bank的vault controller，以及與其他處理單元和stack通信的link controller.通過在HMC的邏輯層直接集成加速器來獲得極高的內(nèi)部帶寬，可以避免在計算單元和內(nèi)存之間進行來回的數(shù)據(jù)搬運.

雖然有一些關(guān)于集成加速單元的文獻(xiàn)，如高能效處理器核[26]、可編程GPU[5]、SIMD單元[7]和定制的加速器[6,27]，但當(dāng)給定一個應(yīng)用程序時，CPU和DRAM之間的執(zhí)行任務(wù)的劃分仍舊是一個值得研究的問題，因為CPU在這些系統(tǒng)中仍然是不可或缺的.

2 hash joins分析

這一部分，我們在商用多核處理器上對hash joins操作的訪存和能耗進行了詳盡的分析.

2.1 分析方法

我們對最先進的hash joins算法PRO進行了詳細(xì)的性能分析和能耗分析，該算法針對現(xiàn)代多核系統(tǒng)進行了特殊的優(yōu)化.我們建立了如表1所示的多核評測系統(tǒng).為了收集如訪存帶寬、cache miss和功耗等執(zhí)行細(xì)節(jié)，我們使用了Intel的Performance Counter Monitor(PCM)2.8提供的編程接口.在該評測平臺上，我們可以收集L1L2緩存未命中率、內(nèi)存控制器的讀寫字節(jié)數(shù)等關(guān)鍵信息.此外，通過查看Intel的RAPL(Runtime Average Power Limit)[28]提供的計數(shù)器，我們也可以獲得處理器和DRAM的能耗信息.

Table 1 The Hardware System Used for Evaluation表1 用作評估的硬件系統(tǒng)

2.2 訪存分析

雖然hash joins算法的性能瓶頸已經(jīng)得到了很好的研究，但是在分析hash joins訪存行為細(xì)節(jié)方面仍然缺乏研究工作.

如圖1所示，雖然PRO整體的內(nèi)存帶寬要求高于傳統(tǒng)的多線程應(yīng)用程序(比如PARSEC benchmark)，但我們將進一步研究PRO是否受限于可用的內(nèi)存帶寬.如表2所示，根據(jù)內(nèi)存設(shè)備的物理特性計算，系統(tǒng)的理論最大帶寬為21.2 GBps,但是在實際應(yīng)用中理論帶寬是難以達(dá)到的.對于實際應(yīng)用來說，一種充分挖掘內(nèi)存帶寬的方法是采用流式(stream)訪存.在高性能計算領(lǐng)域中，STREAM benchmark[29]被廣泛用于測量系統(tǒng)的可持續(xù)內(nèi)存帶寬.使用STREAM benchmark對我們的評測平臺進行測試，發(fā)現(xiàn)平臺的可持續(xù)內(nèi)存帶寬約為18.49 GBps.在運行8線程的PRO中，我們測得實際內(nèi)存帶寬為17.24 GBps，約為可持續(xù)帶寬的93.2%.換句話說，PRO幾乎使評測平臺的可持續(xù)內(nèi)存帶寬達(dá)到飽和.

Table 2 Bandwidth Measurement表2 帶寬評估

PRO包含partition,build和probe這3個主要執(zhí)行階段，我們進一步測量每個階段的訪存帶寬.如圖5(a)所示，在8個線程下，partition階段的內(nèi)存帶寬為17.2 GBps，其余2個階段的內(nèi)存帶寬約為15.6 GBps.這一觀察結(jié)果表明，在PRO的整個執(zhí)行過程中，內(nèi)存帶寬利用率始終很高.但是，如表3所示，partition階段的最后一級cache未命中率遠(yuǎn)遠(yuǎn)高于其他2個階段.從內(nèi)存帶寬利用率和cache miss兩個不同角度觀察，我們發(fā)現(xiàn)導(dǎo)致PRO不同階段都有如此高的帶寬利用率的根本原因是不同的.由于partition階段中data shuffling過程(參見圖2)存在大量隨機訪存行為，導(dǎo)致大量cache miss，從而使得帶寬利用率看起來很高，但實際的數(shù)據(jù)移動效率卻較低；而build和probe階段是流式訪存，所以帶寬利用率和數(shù)據(jù)移動效率都較高.

我們進一步研究partition階段，其中l(wèi)ocal histogram(LH)和data shuffling(DS)的執(zhí)行時間占總執(zhí)行時間的99%以上.如圖5(b)顯示，當(dāng)使用4個線程運行時，LH階段受到可用內(nèi)存帶寬的限制，原因是關(guān)系表的順序訪存容易使內(nèi)存帶寬達(dá)到飽和.對于DS的階段，在運行8個線程時內(nèi)存帶寬達(dá)到峰值.我們可以看到，DS階段內(nèi)存帶寬低于LH階段.究其原因，是由于鍵(key)在各自位置上的分布性，在DS階段存在很多不規(guī)則的訪存.

Fig. 5 Detailed bandwidth analysis of PRO圖5 PRO的詳細(xì)帶寬分析

Table 3 L3 Cache Miss Ratio of PRO表3 PRO的cache miss率

基于以上分析，我們認(rèn)為由于密集的訪存行為(規(guī)則的和不規(guī)則的)，最先進的hash joins算法在商用多核結(jié)構(gòu)上被可用帶寬所限制.這種密集的訪存行為不僅會導(dǎo)致性能下降，而且具有較高的能耗.在hash joins算法中，計算部分相對簡單，比如位操作、hash(如圖2中的行③)、數(shù)組索引(如圖2中的行)和整數(shù)增量(如圖2中的行).因此，預(yù)計移動數(shù)據(jù)產(chǎn)生的能耗比計算本身更為嚴(yán)重.為了驗證這一假設(shè)，我們進行進一步的實驗來確定hash joins算法的能耗瓶頸.

2.3 能耗分析

我們從2個級別來進行能耗分析：粗粒度級別和細(xì)粒度級別.在粗粒度級別，我們分析了partition,build+probe階段的能耗.在細(xì)粒度級別，我們將能消耗分為3類：數(shù)據(jù)移動、流水線阻塞和計算能耗，我們采用了文獻(xiàn)[30-31]中提出的評測方法.

1) 粗粒度級別分析結(jié)果.圖6給出了在不同輸入大小(32～256 M)和線程數(shù)(1～4)情況下，partition和build+probe階段的能耗比較.平均來看，partition階段能耗約占總能耗的86.4%.因此，對于CPU和DRAM來說，有必要降低partition階段的能耗.

2) 細(xì)粒度級別分析結(jié)果.圖7展示了整個hash joins過程的細(xì)粒度能耗分解.我們測量由數(shù)據(jù)移動和流水線阻塞帶來的能耗，流水線阻塞主要是由數(shù)據(jù)移動操作和功能單元的爭搶引起的,剩余的能耗是由計算和其他原因?qū)е碌?

Fig. 6 Energy of the partition and build+probe圖6 partition階段和build+probe階段的能耗

Fig. 7 Energy breakdown of the hash joins operation圖7 hash joins操作的能耗分解

對于build+probe階段，由數(shù)據(jù)移動引起的能耗相對較小，僅占總能耗的1.8%.相比之下，計算引起的能耗約占總能耗的11%，是數(shù)據(jù)移動能耗的6.4倍.與build+probe階段相比，partition階段能耗情況則完全不同.

在運行1個工作線程時，在數(shù)據(jù)移動、流水線阻塞和計算+其他方面消耗的能量分別為18.6%,31.9%和35.8%.可以看出，數(shù)據(jù)移動和流水線阻塞對整體能耗有很大的貢獻(xiàn).

雖然hash joins的所有階段幾乎使內(nèi)存帶寬飽和(參考3.2節(jié))，但partition和build+probe階段的數(shù)據(jù)移動能耗有著顯著的不同.在partition階段，數(shù)據(jù)shuffle過程存在大量高代價的不規(guī)則的訪存行為，導(dǎo)致數(shù)據(jù)移動開銷大.而在build+probe階段，只有常規(guī)的流式訪存，使得數(shù)據(jù)移動成本可以忽略不計.因此，設(shè)計DRAM中加速器的首要考慮的因素是數(shù)據(jù)移動的成本，而不是內(nèi)存帶寬.

現(xiàn)代處理器為了降低內(nèi)存訪問延遲，設(shè)計了多個層次的存儲結(jié)構(gòu)，因此數(shù)據(jù)移動操作可以進一步分為4類：L1到寄存器、L2到寄存器、L3到寄存器和內(nèi)存到寄存器.這4類操作的能耗分布如圖8所示.從DRAM到寄存器數(shù)據(jù)移動的能耗約占總能耗的60%，而處理器內(nèi)的移動數(shù)據(jù)(包括L1到寄存器、L2到寄存器和L3到寄存器)的能耗約占總能耗的40%.因此，有必要同時從CPU和DRAM兩端降低數(shù)據(jù)移動的能耗.

Fig. 8 Breakdown of energy caused by data movement in the partition phase圖8 partition階段數(shù)據(jù)移動帶來的能耗分解

Fig. 9 The overview of proposed hybrid accelerated system圖9 混合加速系統(tǒng)的總體架構(gòu)

綜上，雖然最好的hash joins算法是內(nèi)存受限的，但由于partition階段有著不規(guī)則的內(nèi)存訪問，大部分的能耗是由流水線阻塞和數(shù)據(jù)移動產(chǎn)生的；而對于訪存有規(guī)律的build+probe階段，大部分能量消耗在計算上.為了在面積、功耗、散熱受限的DRAM邏輯層上提高整體的能效，我們建議只在DRAM中加速partition階段，而把build+probe階段的加速留給CPU.

2.4 在DRAM中加速的收益

通過將加速器集成到DRAM中，可以從各個方面減少partition階段的能耗，從而減少總體能耗.

1) 數(shù)據(jù)移動的能耗.通過將加速器集成到DRAM中，可以避免CPU和DRAM之間高代價的往返數(shù)據(jù)傳輸，從而直接降低數(shù)據(jù)移動能耗.

2) 流水線阻塞的能耗.由于相當(dāng)緩慢的內(nèi)存訪問導(dǎo)致了大量的流水線阻塞，因此數(shù)據(jù)訪問的改進(通過將計算移動到更接近數(shù)據(jù)位置)也有助于減少流水線阻塞帶來的能耗.

3) 計算的能耗.使用自定義hash分區(qū)加速器(HPA)可以顯著降低計算能耗.

3 系統(tǒng)概覽

圖9展示了hash joins混合加速系統(tǒng)的總體結(jié)構(gòu)，包括多眾核的主機處理器和一個或多個3D DRAM stack.在每個DRAM stack的邏輯層中，我們將hash分區(qū)加速器(HPA)集成到每個vault controllor上，使HPA可以充分利用3D DRAM中極高的內(nèi)部帶寬.

1) 主機處理器.主機處理器是一個傳統(tǒng)的多眾核處理器，例如Intel的Haswell或Xeon Phi處理器.它通過高速連接(用于傳統(tǒng)的HMC系統(tǒng)中)或者interposer(用于Intel的Knights Landing中)與3D DRAM stack進行通信.主機處理器可以通過引入SIMD單元、定制的加速器或GPU等加速器增強自身性能，從而提高大多數(shù)應(yīng)用的性能.在我們的混合系統(tǒng)中，主機處理器主要側(cè)重于利用SIMD單元來加速build和probe階段.

2) 集成加速器的3D堆疊DRAM.針對每個3D DRAM stack，我們集成多個HPA來充分利用其高內(nèi)存帶寬，從而降低整體的能耗.由于每個3D DRAM stack包含多個vault，并且每個vault都由邏輯層的vault controller訪問，所以我們將一個HPA集成到vault controller上.

為加速partition階段而設(shè)計的hash分區(qū)加速器(HPA)包含3個主要部件：hash unit，histogram unit和shuffle unit.這些單元通過vault controller訪問DRAM層，并且與開關(guān)電路相連.

4 hash分區(qū)加速器

在這一部分，我們首先介紹HPA的設(shè)計架構(gòu).然后，探索可能的設(shè)計空間來找到最優(yōu)的設(shè)計方案.

4.1 加速器設(shè)計

每個HPA的詳細(xì)架構(gòu)如圖10所示.HPA通過vault controller訪問DRAM.

1) hash unit.如圖10(a)所示，我們以一個處理并行度為4的hash unit為例，介紹hash unit的架構(gòu).它以流式訪問的方式從DRAM中讀取關(guān)系表中的多個元組，然后并行地處理它們的keys，以位移或者掩碼的方式來產(chǎn)生hash索引.由于hash unit會被histogram unit和shuffle unit復(fù)用，所以加入了多路選擇器(MUX)用于決定hash索引的輸出目標(biāo).

2) histogram unit.圖2中的原始histogram算法應(yīng)該串行執(zhí)行.為了增加histogram操作的并行度，我們采用本地存儲器(local memory, LM)來保存my_hist的多個副本，每個副本都由單獨的處理單元處理.如圖10(b)所示，并行的histogram操作被分解為2個階段：并行增量階段(INC)和串行歸約階段(RED).在INC階段，hash unit產(chǎn)生的hash索引idx用于更新對應(yīng)的LM當(dāng)前的histogram值.在處理完從DRAM中讀取的所有鍵后，最后的RED階段進行所有LM的整合，以獲得一個完整且保持?jǐn)?shù)據(jù)一致性的my_hist.

Fig. 10 The architecture of HPA圖10 HPA的架構(gòu)

histogram unit設(shè)計中需要關(guān)心的是LM的功耗和面積.LM的數(shù)量越多，處理my_hist的并行度越高，但是相應(yīng)地會增加面積和功耗.同時為了減少TLB miss，LM的大小還受到TLB項數(shù)量的限制[11].具體來說，每個my_hist副本大小最好與TLB項數(shù)量相等.在現(xiàn)代處理器中針對L1設(shè)計的數(shù)據(jù)TLB通常是64或128項.因此，給定一個很高的并行度，比如512，LM的總大小為256 KB(512×128×4).當(dāng)然，我們應(yīng)該謹(jǐn)慎選擇并行度，在性能、功耗和面積之間做設(shè)計權(quán)衡.

3) shuffle unit.與 histogram unit的并行設(shè)計思路類似，shuffle unit的設(shè)計的挑戰(zhàn)是如何將多個元組同時寫入到各自在tmp數(shù)組中的目標(biāo)地址(tmp[dst[idx]])，然后更新dst數(shù)組中的目標(biāo)地址(如圖2所示).如果多個處理路徑中具有相同目的地址的元組，還需要處理目標(biāo)地址沖突問題.

我們提出的并行shuffle unit由4個階段組成：第1階段(DIST)是根據(jù)hash索引(idx)從dst數(shù)組中并行地讀取多個目標(biāo)地址(圖2的第行).第2階段(DECONF)用于檢測多個處理路徑之間有沖突的目的地址.DECONF階段產(chǎn)生基于原始目標(biāo)地址的偏移，從而確定在tmp數(shù)組中正確的目的地址.同時DECONF階段也產(chǎn)生相同目的地址的計數(shù)值來更新idx數(shù)組.第3階段(SCATTER)將元組移動到正確的位置，正確的位置根據(jù)DECONF階段產(chǎn)生的偏移和DIST階段產(chǎn)生的存儲在tmp數(shù)組的原始目的地址聯(lián)合計算得出.最后一個階段(UPDATE)根據(jù)DECONF階段產(chǎn)生的計數(shù)值更新目的地址.

DECONF本質(zhì)上是一個在原始目的地址上執(zhí)行XNOR操作的XNOR網(wǎng)絡(luò).圖11給出了XNOR網(wǎng)絡(luò)的結(jié)構(gòu)示例，在此示例中，4個目的地址的數(shù)值d0,d1,d2和d3從dst數(shù)組中并行的讀出.為了計算d0的總數(shù)量count(d0)，首先d0分別與d1,d2和d3進行同或操作，然后所有同或的數(shù)值進行求和.同樣地，通過對xnor(d1,d0), xnor(d1,d2)和xnor(d1,d3)求和計算得出count(d1).計算目標(biāo)地址偏移也可以通過復(fù)用XNOR網(wǎng)絡(luò)來實現(xiàn).例如，offset(d1)是xnor(d1,d2)和xnor(d1,d3)的和.

Fig. 12 The throughput and power of the histogram operation圖12 histogram操作的吞吐率和功耗

Fig. 11 XNOR network圖11 XNOR網(wǎng)絡(luò)圖示

4.2 設(shè)計空間探索

在HPA的設(shè)計過程中，在并行度和頻率上存在多種選擇，同時3D堆疊DRAM也可以選擇不同的配置.表4列出了3種可能的3D堆疊DRAM配置：HI，MD和LO，它們的內(nèi)部帶寬在860 GBps～360 GBps之間.我們探索了由每個vault的并行度(1～512)、操作頻率(0.4～2.0 GHz)和DRAM配置組成的設(shè)計空間，嘗試在在并行度和功耗之間進行設(shè)計權(quán)衡.更多的細(xì)節(jié)和評估方法論可以在第6節(jié)中找到.

Table 4 3D-Stacked DRAM Configurations表4 3D堆疊內(nèi)存配置

4.2.1 histogram操作

圖12顯示了使用HI和LO DRAM配置，在不同的頻率和并行度下histogram操作的吞吐率和功耗.第1個觀察結(jié)果是吞吐率隨著并行度和頻率的增加而增加，這充分說明了我們設(shè)計的可伸縮性.針對HI配置，在2 GHz下當(dāng)并行度從8增加到16，相應(yīng)的吞吐率也增加了約2倍.然而，隨著頻率和并行度的不斷增加，所需的內(nèi)存帶寬也會增加，從而使吞吐率受到可用內(nèi)存帶寬的限制.在另一個例子中，給定0.4 GHz的頻率，雖然并行度從32增加到64時，吞吐率增加了約2倍，但是當(dāng)并行度從64增加到128時，吞吐率只有1.6倍的增加.另外，當(dāng)并行度從256增加到512時，吞吐率的增益僅為1.06.針對不同的頻率，在不同并行度下，HI和LO配置的吞吐率最終會分別收斂到840 GBps和450 GBps.

至于功耗，除了直觀地觀察到功耗隨并行度和頻率增加外，我們還觀察到不同頻率之間的功耗差距會隨著并行度的變化而變化.對HI配置，當(dāng)并行度是16時，最大功耗(在2 GHz時)比最小功耗(在0.4 GHz時)高2.54倍，而當(dāng)并行度是64時，功耗差距只有1.26倍.這是由于DRAM在相對較小的并行度的情況下，不同頻率之間的功耗有一個較大的差距.

Fig. 15 The throughput and power of the shuffle operation圖15 shuffle操作的吞吐率和功耗

為了詳細(xì)說明功耗，圖13顯示了HI配置下的histogram操作的功耗分解.我們可以看到，隨著并行度的增加，DRAM的功耗所占比例(例如DRAM_RD)也隨之增加.然而，當(dāng)并行度大于32時，DRAM功耗所占的比例減小，因為內(nèi)存帶寬幾乎飽和，同時HASH和INC功耗顯著增加.在2 GHz下，并行度是512時，HASH和INC功耗甚至高于DRAM功耗.

Fig. 13 The power breakdown of the histogram operation圖13 histogram操作功耗分解

我們還在圖14中，以能量-延遲積(EDP)為標(biāo)準(zhǔn)，展示了在不同設(shè)計方案下的每個vault的能效.在所有的DRAM配置下，隨著并行度的增加，EDP并沒有顯示出單調(diào)下降的趨勢.特別值得注意的是，在并行度在32左右時，所有DRAM配置的EDP達(dá)到了最優(yōu)值.舉例來說，使用HI配置，在1.2 GHz操作頻率下，達(dá)到最優(yōu)的EDP需要64的并行度.一般來說，相比HI配置，MD和LO DRAM配置具有更好的能效(每個vault)，隨著并行度的增大變得尤為明顯.圖14還顯示了不同設(shè)計選擇下的面積.可以看出，隨著并行度的增加面積會顯著增加.在每個vault中每一個HPA的最大面積大約為1.4 mm2，這是因為HPA需要更多的處理單元.

Fig. 14 Energy-delay product (EDP) of different design options for the histogram operation圖14 不同設(shè)計下histogram操作的能量-延遲積

4.2.2 shuffle操作

圖15展示了使用HI和LO DRAM配置，在不同的頻率和并行度下shuffle操作的吞吐率和功耗.一般來說，吞吐率會隨著并行度和頻率的提高而增加，在HI和LO的配置下，它最終分別收斂到91 GBps和29 GBps.最大吞吐率主要受SCATTER階段的限制，在該階段中是以相對隨機的方式進行內(nèi)存訪問的.隨著并行度和頻率的增加，功耗也會隨之增長.在2 GHz下，在HI和LO配置中最大功耗分別達(dá)到了216 W和54 W.

圖16展示了shuffle操作下的功耗分解.當(dāng)并行度很小時，比如1～16，DRAM的靜態(tài)功耗占主要部分.隨著并行度的增加，HASH和SCATTER的功耗顯著增加，最終超過了DRAM的靜態(tài)功耗.

Fig. 16 The power breakdown of the shuffle operation圖16 shuffle操作的功耗分解

圖17展示了每個vault的shuffle操作能效(EDP)和面積.達(dá)到最優(yōu)EDP的并行度是在32～128之間.例如，在2 GHz下，并行度為32的EDP比并行度為512的EDP好1.77倍.在所有的這些配置中，獲得最優(yōu)EDP的配置為并行度=64、頻率=1.2 GHz和DRAM配置=LO.最優(yōu)配置所需要的面積為0.18 mm2(每vault).

Fig. 17 Energy-delay product (EDP) of different design options for the shuffle operation圖17 不同設(shè)計下shuffle操作的能量-延遲積

4.2.3 設(shè)計決策

要做出HPA的最優(yōu)設(shè)計決策，我們必須綜合考慮histogram和shuffle兩個操作的性能、功耗和面積.我們通過對比不同配置下這2個操作的總EDP決定最優(yōu)的HPA配置.我們得出結(jié)論是：當(dāng)輸入的大小是128 M時，HPA的最優(yōu)配置是并行度=16、頻率=2.0 GHz、DRAM配置=HI.相應(yīng)的面積只有1.78mm2，加速器的功耗(不含DRAM功耗)只有7.52 W.

5 軟件設(shè)計

軟件設(shè)計包括用于調(diào)用HPA(hash分區(qū)加速器)的編程接口和用于加速build和probe階段的SIMD指令.

5.1 HPA編程接口

我們采用的編程接口是在文獻(xiàn)[6]中提出的編程庫上進行搭建的.所使用的庫函數(shù)包括內(nèi)存管理庫函數(shù)malloc和free，以及加速器控制庫acc_plan(用于配置加速器)和acc_execute(用于調(diào)用已配置的加速器).我們對acc_plan函數(shù)進行擴展，使它支持2個新的操作：HIST和SHUF，分別用來控制HPA執(zhí)行histogram和shuffle操作.在這些庫函數(shù)的幫助下，程序員可以很容易地在程序中使用HPA.此外，我們使用的編程接口本質(zhì)上是一個順序編程模型，所以可以減輕異構(gòu)系統(tǒng)的編程負(fù)擔(dān).

然而，加速代碼(如histogram和shuffle操作)是一個并行執(zhí)行范式，其中每個工作線程都需要處理自己的數(shù)據(jù)分塊.為了縮小順序編程模和并行編程模型之間的差距，我們在每個工作線程調(diào)用HPA之前添加barrier操作，然后只有1個線程通過acc_plan和acc_execute調(diào)用HPA，同時所有其他線程都在等待HPA執(zhí)行(histogram或shuffle操作)完成.在HPA完成執(zhí)行之后，每個工作線程恢復(fù)各自的執(zhí)行流，進行后續(xù)操作.

5.2 針對build+probe階段的SIMD加速

近年來，為提高h(yuǎn)ash joins的執(zhí)行效率，針對SIMD和向量化有很好的研究.我們采用了在文獻(xiàn)[13,15]中提出的SIMD算法，在多核(例如Intel Haswell)和眾核(如Intel Xeon Phi)處理器上加速build和probe階段.

圖18展示了在支持512-bit SIMD的Xeon Phi處理器上用SIMD執(zhí)行build階段的基本思想.直觀來看，多個hash操作可以并行執(zhí)行(參考圖3中的行③).在圖18行④中，gather操作從元組中選擇鍵.在行⑤中，基于SIMD的hash操作(包括SIMD按位與和移位)并行地進行多個鍵的hash處理.在行⑥中，將hash處理的結(jié)果寫回extVector.extVector

① 單位為元組的個數(shù)，數(shù)據(jù)的總大小是0.5 GB～4 GB (256 M×8×2 B=4 GB)

中包含16個idx(參考圖3)，用于順序更新bucket數(shù)組.probe階段的SIMD執(zhí)行類似于build階段.

Fig. 18 The basic idea of 512-bit SIMD execution of the build phase
圖18 512-bit SIMD執(zhí)行build階段的基本思想

6 實 驗

在本節(jié)中，我們展示了混合加速系統(tǒng)的能效，并將其與支持SIMD的商用多眾核處理器進行比較.

6.1 評測方法

1) 評測基礎(chǔ)設(shè)施.我們采用了文獻(xiàn)[6]中提出的混合評價方法論來評估我們的系統(tǒng).這種評估方法的主要優(yōu)點是真正的執(zhí)行行為可以被如實地模擬.

2) 主機處理器.表5列出了用于評估的主處理器，其中Intel Haswell和Intel Xeon Phi處理器分別是商用多核和眾核處理器.我們在主機處理器上運行PRO算法，并測量不包括加速部分(partition階段的histogram和shuffle操作)程序的性能和功耗.我們還測量了使用主處理器把加速部分任務(wù)分派到HPA加速器的開銷(包括加速器控制帶來的開銷和刷新緩存以保證數(shù)據(jù)一致性帶來的開銷).

3) 加速器仿真.通過各種仿真工具對hash分區(qū)加速器(HPA)的性能、功耗和面積行評估.該加速器的性能是由一個內(nèi)部的、C-level、周期精準(zhǔn)的模擬器估計的.DRAM的訪存延遲是由一個周期精準(zhǔn)的3D堆疊DRAM模擬器獲得的[8].我們采用32 nm的庫和編譯器來評估HPA的功耗和面積.

4) Baseline.為了展現(xiàn)混合加速系統(tǒng)的優(yōu)勢，我們對比了Intel Haswell和Xeon Phi處理器和我們的系統(tǒng).如表5所示，它們的內(nèi)存帶寬的峰值分別為21.2 GBps和320 GBps.我們在這2個平臺上全面的測量了hash joins算法的性能和功耗.

5) HPA配置和輸入數(shù)據(jù)集.如第4節(jié)所探討的，HPA的最佳頻率和并行度分別為2.0 GHz和16.3D堆疊DRAM是HI配置，它包含16個vault，最大的內(nèi)部帶寬為860 GBps(如表4所示).關(guān)于輸入數(shù)據(jù)集，我們將輸入關(guān)系表的元組數(shù)目作為可調(diào)整的變量，從32 M～256 M①進行了測試.

Table 5 The Baseline Host Processors表5 基準(zhǔn)主處理器

6.2 實驗結(jié)果

我們用不同大小的輸入數(shù)據(jù)集，在性能、能耗和EDP這3個方面將我們提出的混合系統(tǒng)和Haswell和Xeon Phi處理器進行了比較，結(jié)果如圖19所示.與Haswell處理器相比，混合系統(tǒng)在性能、功耗和EDP上分別優(yōu)化了6.70，7.08和47.52倍.與Xeon Phi處理器相比，混合系統(tǒng)在性能、功耗和EDP上分別優(yōu)化了4.17，4.68和19.81倍.我們觀察到，Xeon Phi處理器的收益比Haswell處理器的收益要小.原因是在Xeon Phi上，build和probe階段執(zhí)行所占的比例比Haswell更大.

如圖20所示，針對hash partition操作，我們比較了HPA與基準(zhǔn)平臺的性能、能耗和EDP.平均而言，與Intel Haswell處理器相比，HPA的性能、功耗和EDP分別優(yōu)化了30，90和2 725倍.與Xeon Phi處理器相比，EDP優(yōu)化甚至超過了6 000倍.性能和能效的顯著提高主要來源于定制加速器和由3D堆疊DRAM提供的高內(nèi)存帶寬.

為了更詳細(xì)地分析實驗結(jié)果，我們在圖21中給出了Intel Haswell處理器的執(zhí)行過程分解.根據(jù)圖21(a)中執(zhí)行時間的分解，HPA只占整個執(zhí)行時間的19.2%.相比之下，加速前的partition階段的執(zhí)行時間大約是整個執(zhí)行時間的90%，這表明partition階段已經(jīng)被加速了大約30倍.此外，當(dāng)輸入數(shù)據(jù)集很小時(比如32 M)，HPA的調(diào)用成本是巨大的，占總執(zhí)行時間的8.6%.當(dāng)輸入數(shù)據(jù)的大小增加時，調(diào)用成本逐漸變得可以忽略，例如，當(dāng)輸入數(shù)據(jù)大小是256 M時，調(diào)用成本只是總執(zhí)行時間的1%.

Fig. 19 Overall comparison with the Intel Haswell and Xeon Phi processor圖19 與Intel Haswell和Xeon Phi處理器總體對比

Fig. 20 Comparison with the Intel Haswell and Xeon Phi processor for the hash partition operation圖20 與Intel Haswell和Xeon Phi處理器在partition操作上的對比

Fig. 21 Breakdown of execution time and energy on the hybrid system and Intel Haswell processor圖21 混合系統(tǒng)以及Intel Haswell處理器的執(zhí)行時間和功耗分解

在圖21(b)中，功耗的分解進一步證明了HPA的優(yōu)勢.平均來說，HPA功耗只占總功耗的6.2%.同時，在Haswell上實際計算的功耗遠(yuǎn)遠(yuǎn)高于調(diào)用HPA的功耗.平均而言，Haswell計算和調(diào)用HPA的功耗比率分別為92.7%和1.1%.

6.3 功耗和面積總結(jié)

我們在表6中展示了混合系統(tǒng)的功耗和面積，該系統(tǒng)由HPA，DRAM和主機處理器(Haswell)組成.就面積而言，HPA(由hash、histogram和shuffle unit組成)的總面積僅為Micron的Hybrid Memory Cube (HMC)總尺寸的2.6%.因此，HMC的邏輯層很容易容納HPA.此外，HPA的面積只占由DRAM和CPU組成的整個系統(tǒng)的0.72%.

在功耗方面，HMC只給3D堆疊DRAM增加了7.52 W的功耗，在DRAM中使用HPA的總功耗為28.43W.由于DRAM也被主機處理器(如Haswell)訪問，我們還測量了由Haswell處理器訪問引起的DRAM功耗，相應(yīng)的DRAM功耗是9.79 W.由于DRAM不能被HPA和Haswell同時訪問，所以DRAM的總功耗不會超過18.64 W.對于主要用來執(zhí)行build和probe階段Haswell處理器，測得其總功耗為89.75 W.

Table 6 Power and Area Consumption of the Entire System表6 整個系統(tǒng)的功耗和面積消耗

7 相關(guān)工作

在本節(jié)中，我們列出了針對數(shù)據(jù)庫操作、算法、應(yīng)用而使用新型硬件的相關(guān)工作.

1) SIMD擴展.在過去10年中，為了加速數(shù)據(jù)庫的原語，已經(jīng)廣泛部署SIMD擴展.Zhou等人在文獻(xiàn)[32]中首先用SIMD指令來加速基本的數(shù)據(jù)庫操作，如索引掃描和嵌套循環(huán)聯(lián)接.Willhalm等人在文獻(xiàn)[33]中使用向量處理單元在數(shù)據(jù)掃描中進行解壓縮.Schlegel等人在文獻(xiàn)[34]中使用SIMD支持在Xeon Phi處理器上實現(xiàn)了一個可擴展的頻繁項集挖掘算法.Polychroniou等人在文獻(xiàn)[14]中使用SIMD指令重寫了內(nèi)存數(shù)據(jù)庫操作，其中包含掃描、hash、篩選和排序.

2) FPGAs.已經(jīng)有很多用FPGA加速數(shù)據(jù)庫查詢操作的工作.比如IBM Netezza，它是一個結(jié)合了Xeon服務(wù)器和FPGAs的商用系統(tǒng)，可以提高數(shù)據(jù)庫查詢的性能.Sukhwani等人在文獻(xiàn)[35]中利用FPGA對傳統(tǒng)DBMS進行數(shù)據(jù)解壓和謂詞評價.Chung等人在文獻(xiàn)[36]中提出了一種框架，將查詢語言LINQ映射到硬件模板，該模板可以由FPGA或ASIC實現(xiàn).由ARM A9處理器和FPGA組成的SoC系統(tǒng)可以提高30.6倍的能效.

3) GPUs.圖處理單元也被廣泛用于加速通用數(shù)據(jù)查詢[37]和數(shù)據(jù)庫操作原語，如索引[38]、排序[39]和連接[40-41].

4) 自定義的邏輯單元.在數(shù)據(jù)庫領(lǐng)域自定義加速器也被廣泛地使用.Kocberber等人在文獻(xiàn)[42]中為hash索引查找建立了on-chip加速器.Wu等人在文獻(xiàn)[43]中首先提出了一種用于range partitioning的硬件加速器：HARP.為了充分利用HARP的計算能力，他們還提出了一個硬件-軟件流式框架，用于CPU和HARP之間的通信.與他們的工作相比，我們更關(guān)注hash分區(qū)，并且我們在最先進的hash joins(即PRO)中發(fā)現(xiàn)hash分區(qū)是內(nèi)存受限的.因此，將加速過程集成到DRAM中可以使hash分區(qū)獲得巨大的收益.為了實現(xiàn)這個目標(biāo)，我們設(shè)計了一個hash分區(qū)加速器(HPA)，它可以適應(yīng)3D堆疊DRAM架構(gòu).Wu等人在文獻(xiàn)[44]中進一步提出了Q100數(shù)據(jù)庫處理單元(DPU)，以有效地處理數(shù)據(jù)庫原語，如聚合、連接和排序.

隨著靠近數(shù)據(jù)的處理技術(shù)出現(xiàn)，也有一些將自定義邏輯集成到DRAM中進行數(shù)據(jù)庫處理的研究.Xi等人在文獻(xiàn)[45]中設(shè)計了JAFAR加速器，他們將選擇操作附加到DRAM中，獲得了9倍的加速.Seshadri等人在文獻(xiàn)[46]中提出在DRAM中實現(xiàn)位操作(AND和OR)，進而加速各種數(shù)據(jù)庫操作(例如索引).

8 總 結(jié)

盡管3D-die的堆疊技術(shù)使得計算單元可以集成到3D堆疊DRAM中，但由于其嚴(yán)格的面積、功耗、散熱的限制，使得我們在架構(gòu)設(shè)計時應(yīng)該謹(jǐn)慎地考慮如何在3D堆疊DRAM中加入最合適的邏輯單元.在本文中，我們以數(shù)據(jù)移動為驅(qū)動，對CPU和DRAM之間的加速任務(wù)進行劃分.基于這種方法，我們設(shè)計了一種混合加速系統(tǒng)，用于加速數(shù)據(jù)庫和大數(shù)據(jù)系統(tǒng)中的基本操作hash joins.該系統(tǒng)包含一個內(nèi)存端定制的hash分區(qū)加速器(HPA)和處理器端的SIMD單元.內(nèi)存端的加速器用于加速數(shù)據(jù)移動受限的執(zhí)行階段，而處理器端SIMD加速單元則用于加速數(shù)據(jù)移動開銷較低成本的執(zhí)行階段.實驗結(jié)果表明，該系統(tǒng)與Intel Haswell和Xeon Phi處理器相比，僅僅用7.52W額外的功耗，將能效分別提升了47.52和19.81倍.同時我們的設(shè)計方法可以很容易地被應(yīng)用到其他應(yīng)用程序的加速設(shè)計中.

[1]Putnam A,Caulfield A M, Chung E S, et al. A reconfigurable fabric for accelerating large-scale datacenter services[C] //Proc of the 41st Annual Int Symp on Computer Architecture. Los Alamitos, CA: IEEE Computer Society, 2014: 13-24

[2]Lim K, Meisner D, Saidi A G, et al. Thin servers with smart pipes: Designing SoC accelerators for Memcached[C] //Proc of the 40th Annual Int Symp on Computer Architecture. New York: ACM, 2013: 36-47

[3]Qadeer W, Hameed R, Shacham O, et al. Convolution engine: Balancing efficiency & flexibility in specialized computing[C] //Proc of the 40th Annual Int Symp on Computer Architecture. New York: ACM, 2013: 24-35

[4]Krishna A, Heil T, Lindberg N, et al. Hardware acceleration in the IBM PowerEN processor: Architecture and performance[C] //Proc of the 21st Int Conf on Parallel Architectures and Compilation Techniques. New York: ACM, 2012: 389-400

[5]Zhang D, Jayasena N, Lyashevsky A, et al. TOP-PIM: Throughput-oriented programmable processing in memory[C] //Proc of the 23rd Int Symp on High-performance Parallel and Distributed Computing. New York: ACM, 2014: 85-98

[6]Guo Q, Alachiotis N, Akin B, et al. 3D-stacked memory-side acceleration: Accelerator and system design[C] //Proc of the 2nd Workshop on Near-Data Processing in Conjunction with the 47th IEEE/ACM Int Symp on Microarchitecture. Workshop on Near-data Processing. Piscataway, NJ: IEEE, 2014

[7]Nair R, Antao S, Bertolli C, et al. Active memory cube: A processing-in-memory architecture for exascale systems [J]. IBM Journal of Research and Development, 2015, 59(2/3): No.17

[8]Akin B, Franchetti F, Hoe J C. Data reorganization in memory using 3D-stacked DRAM[C] //Proc of the 42nd Annual Int Symp on Computer Architecture. New York: ACM, 2015: 131-143

[9]Zaharia M, Chowdhury M, Das T, et al. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[J]. USENIX Conf on Networked Systems Design and Implementation, 2012, 70(2): 2-2

[10]Blanas S, Li Y, Patel J M. Design and evaluation of main memory hash join algorithms for multi-core CPUs[C] //Proc of the 2011 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2011: 37-48

[11]Teubner J, Alonso G, Balkesen C, et al. Main-memory hash joins on multi-core CPUs: Tuning to the underlying hardware[C] //Proc of the 2013 IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2013: 362-373

[12]He J, Lu M, He B. Revisiting co-processing for hash joins on the coupled CPU-GPU architecture [J]. VLDB Endowment, 2013, 6(10): 889-900

[13]Jha S, He B, Lu M, et al. Improving main memory hash joins on intel Xeon Phi processors: An experimental approach [J]. VLDB Endowment, 2015, 8(6): 642-653

[14]Polychroniou O, Raghavan A, Ross K A. Rethinking SIMD vectorization for in-memory databases[C] //Proc of the 2015 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2015: 1493-1508

[15]Balkesen C, Teubner J, Alonso G, et al. Main-memory hash joins on modern processor architectures [J]. IEEE Trans on Knowledge & Data Engineering, 2015, 27(7): 1754-1766

[16]Han Xixian, Yang donghua, Li jianzhong. DBCC-Join a novel cache-conscious disk-based join algorithm [J]. Chinese Journal of Computers, 2010, 33(8): 1501-1511 (in Chinese)(韓希先, 楊東華, 李建中. DBCC-Join：一種新的高速緩存敏感的磁盤連接算法[J]. 計算機學(xué)報, 2010, 33(8): 1501-1511)

[17]Manegold S, Boncz P, Kersten M. Optimizing main-memory join on modern hardware [J]. IEEE Trans on Knowledge & Data Engineering, 2002, 14(4): 709-730

[18]Balasubramonian R, Chang J, Manning T, et al. Near-data processing: Insights from a micro-46 workshop [J]. IEEE MICRO, 2014, 34(4): 36-42

[19]Elliott D, Snelgrove W, Stumm M. Computational RAM: A memory-SIMD hybrid and its application to DSP[C] //Proc of the IEEE Custom Integrated Circuits Conf. Piscataway, NJ: IEEE, 1992: 30.6.1-30.6.4

[20]Gokhale M, Holmes B, Iobst K. Processing in memory: The terasys massively parallel PIM array [J]. Computer, 1995, 28(4): 23-31

[21]Oskin M, Chong F T, Sherwood T. Active pages: A computation model for intelligent memory[C] //Proc of the Int Symp on Computer Architecture. Los Alamitos, CA: IEEE Computer Society, 1998: 192-203

[22]Loi G L, Agrawal B, Srivastava N, et al. A thermally-aware performance analysis of vertically integrated (3-D) processor-memory hierarchy[C] //Proc of the 43rd Annual Design Automation Conf. New York: ACM, 2006: 991-996

[23]Loh G H. 3D-stacked memory architectures for multi-core processors[C] //Proc of the 35th Annual Int Symp on Computer Architecture. Los Alamitos, CA: IEEE Computer Society, 2008: 453-464

[24]Woo D H, Seong N H, Lewis D, et al. An optimized 3D-stacked memory architecture by exploiting excessive, high-density TSV bandwidth[C] //Proc of the 16th IEEE Int Symp on High Performance Computer Architecture. Piscataway, NJ: IEEE, 2010: 1-12

[25]Kim D H, Athikulwongse K, Healy M, et al. 3D-maps: 3D massively parallel processor with stacked memory[C] //Proc of Solid-State Circuits Conf Digest of Technical Papers. ISSCC, 2012: 188-190

[26]Pugsley S H, Jestes J, Zhang H, et al. NDC: Analyzing the impact of 3D-stacked memory+logic devices on mapreduce workloads[C] //Proc of the Int Symp on Performance Analysis of Systems and Software. Piscataway, NJ: IEEE, 2014: 190-200

[27]Low T M, Guo Q, Franchetti F. Optimizing space time adaptive processing through accelerating memory-bounded operations[C] //Proc of IEEE High Performance Extreme Computing Conf. Piscataway, NJ: IEEE, 2015: 1-6

[28]H?hnel M, D?bel B, V?lp M, et al. Measuring energy consumption for short code paths using RAPL [J]. ACM Sigmetrics Performance Evaluation Review, 2012, 40(3): 13-17

[29]McCalpin J D. Memory bandwidth and machine balancein current high performance computers[N]. IEEE Technical Committee on Computer Architecture Newsletter, 1995: 19-25

[30]Kestor G, Gioiosa R, Kerbyson D, et al. Quantifying the energy cost of data movement in scientific applications[C] //Proc of IEEE Int Symp on Workload Characterization. Piscataway, NJ: IEEE, 2013: 56-65

[31]Pandiyan D, Wu C J. Quantifying the energy cost of data movement for emerging smart phone workloads on mobile platforms[C] //Proc of IEEE Int Symp on Workload Characterization. Piscataway, NJ: IEEE, 2014: 171-180

[32]Zhou J, Ross K A. Implementing database operations using SIMD instructions[C] //Proc of the 2002 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2002: 145-156

[33]Willhalm T, Popovici N, Boshmaf Y, et al. SIMD-scan: Ultra fast in-memory table scan using on-chip vector processing units [J]. VLDB Endowment, 2009, 2(1): 385-394

[34]Schlegel B, Karnagel T, Kiefer T, et al. Scalable frequent itemset mining on many-core processors[C] //Proc of the 9th Int Workshop on Data Management on New Hardware. New York: ACM, 2013: 3:1-3:8

[35]Sukhwani B, Min H, Thoennes M, et al. Database analytics acceleration using FPGAs[C] //Proc of the 21st Int Conf on Parallel Architectures and Compilation Techniques. New York: ACM, 2012: 411-420

[36]Chung E S, Davis J D, Lee J. Linqits: Big data on little clients[C] //Proc of the 40th Annual Int Symp on Computer Architecture. New York: ACM, 2013: 261-272

[37]Bakkum P, Skadron K. Accelerating SQL database operations on a GPU with CUDA[C] //Proc of the 3rd Workshop on General-Purpose Computation on Graphics Processing Units. New York: ACM, 2010: 94-103

[38]Kim C, Chhugani J, Satish N, et al. Fast: Fast architecture sensitive tree search on modern CPUs and GPUs[C] //Proc of the 2010 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2010: 339-350

[39]Satish N, Kim C, Chhugani J, et al. Fast sort on CPUs and GPUs: A case for bandwidth oblivious SIMD sort[C] //Proc of the 2010 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2010: 351-362

[40]Pirk H, Manegold S, Kersten M L. Accelerating foreign-key joins using asymmetric memory channels[C] //Proc of Int Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures. New York: ACM, 2011: 27-35

[41]Kaldewey T, Lohman G, Mueller R, et al. GPU join processing revisited[C] //Proc of the 8th Int Workshop on Data Management on New Hardware. New York: ACM, 2012: 55-62

[42]Kocberber O, Grot B, Picorel J, et al. Meet the walkers: Accelerating index traversals for in-memory databases[C] //Proc of the 46th Annual IEEE/ACM Int Symp on Microarchitecture. New York: ACM, 2013: 468-479

[43]Wu L, Barker R J, Kim M A, et al. Navigating big datawith high-throughput, energy-efficient data partitioning[C] //Proc of the 40th Annual Int Symp on Computer Architecture. New York: ACM, 2013: 249-260

[44]Wu L, Lottarini A, Paine T K, et al. Q100: The architecture and design of a database processing unit[C] //Proc of the 19th Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2014: 255-268

[45]Xi S L, Babarinsa O, Athanassoulis M, et al. Beyond the wall: Near-data processing for databases[C] //Proc of the Int Workshop on Data Management on New Hardware. New York: ACM, 2015: 2-2

[46]Seshadri V, Hsieh K, Boroumand A, et al. Fast bulk bitwise AND and OR in DRAM [J]. IEEE Computer Architecture Letters, 2015, 14(2): 127-131