现代计算机体系架构带来的挑战

---数据处理算法优化

1.综述

各种数据处理，如排序、聚集、连接、索引等都是支持数据库操作的核心，各个操作也都有相应成熟的算法。如今多核计算机已经是发展的趋势，原先在单核上的经典算法并不能免费移植到现代计算机系统中，并获得高性能。因此如何改进算法，使其能够充分挖掘现代计算机体系架构的优势会是一个热点。相应的改进也可能改变人们之前的认识，如针对某种操作，以前可能以某一种算法为最优的，但到了多核计算机中，另一种算法可能更能挖掘计算机的处理能力。

随着多核处理器的研发、推广，多核体系架构下的数据处理受到国内外的广泛关注，包括卡内基梅隆大学、哥伦比亚大学、多伦多大学、IBM公司、甲骨文公司、Intel公司等许多著名大学、科研机构、商业公司，都展开了广泛而积极的研究，并有众多成果发表在SIGMOD,VLDB,ICDE,EDBT等国际顶级会议上。

已有的成果分别针对多核体系架构的特点，包括物理多线程，对算法进行优化，更重要的是设计多核敏感的数据结构和执行流程，优化CPU资源的利用率，如充分利用cache/TLB，SIMD并行等，提高各种算法的执行性能。

下图所示，是国内外在这方面的研究成果。

2.优化的三个方面

现代计算机体系架构相比较原来已经有了很大改变，这是算法优化的基础及动力。总结起来主要是三方面的改变：多核带来的线程级并行TLP，SIMD指令带来的数据级并行DLP，存储结构。

2.1线程级并行

    线程级并行（Thread Level parallelism，TLP）是指利用现代处理器的多核（multi-cores）特性，从物理上实现多条程序流并行执行。这在上一篇报告《并行编程》中已经详细阐述，主要包括多线程的操作系统模型，多线程的并行模式，多线程的编程技术。

    和算法相关的仅有并行模式，即怎么把一个任务划分成多个可以并行执行的子任务。很显然，在数据处理领域，天然地存在数据划分，即把整块数据划分成若干块，对每一块处理后，把结果整合起来。

    当然，具体的问题并不这么简单，需要考虑多线程间的同步、数据交互等，后面会以一个radix-sort（基数排序）的例子说明。

2.2数据级并行

    这里说的数据级并行（Data-Level-Parallelism），和线程级并行中按数据划分任务完全不是一个概念。现代处理器一般都带有SIMD指令，即单指令可以同时处理多条数据。如现在SSE的SIME指令长度为128bit，则若有4个32bit的连续存放的数据，要与另4个32bit的连续数据分别比较，则可以用一条SIMD指令完成，bitonic-sort其实就是利用这点，大大提高效率。

    今后CPU的SIMD指令的宽度将进一步增加，而且最新热门的GPU也以支持更高密度的数据处理闻名，未来设计SIMD敏感的算法至关重要。

 

2.3存储器吞吐率

    根据现代计算机体系架构的特点，设计存储器敏感的算法，来提高算法的执行性能，是非常重要的。这方面性能的提高，甚至可能弥补算法本身复杂度上的不足，后面会有例子说明这点。

首先要说明的，现在相对高端的机器上，内存已不再是问题，512G内存已经很常见，目前已经有上T量级的内存出现，所以所谓的Main-Memory-Database已经成为可能，即所有的数据都放在内存中运算，磁盘IO的开销已不复存在。

现在的瓶颈bottleneck在于内存的速率远远跟不上处理器的速率，处理器计算的速率非常快，但频繁地读取内存数据，使得CPU的计算资源无法得到充分发挥。在多核架构下更是如此，上一篇报告《并行编程》中同步一节讲述过，多核cpu架构下，为了保证内存的共享但不出错，硬件上使用了一个存储仲裁器的串行电路，而这其实更是大大减小的内存的吞吐率。处理器为了解决这一问题，引入了两个重要的部件：TLB和cache（片上高速缓存）。

 

TLB：其实也是一种cache，只不过它是页表的cache。在典型的x86架构下，简单的读取内存数据其实最起码要读两次内存。因为x86存储管理采用分页机制，页表放在内存中，并有CR3寄存器标示位置。每次寻址，由线性地址现在内存中找到相应的页表，从而获得物理基址，这是第一次读内存；然后再通过得到的物理地址，去读数据，这是第二次读。

这样做虽然为操作系统的设计带来了方便，但却严重影响了数据吞吐率，尤其是在现今memory已成为瓶颈的情况下。因此处理器在内部集成了TLB，用来存放常用页表项。如一款4核的处理器内部，每核独享32条一级TLB entity，4核共享256条二级TLB entity。那么每核常用的页表<64的情况下，几乎就不会发生TLB miss，从而大大提高存储器速率。

TLB是由软件控制的，操作系统可以决定何时刷新页表，如发生进程切换时或特权级变化时，一般都会刷新TLB。

 

Cache：TLB解决了页表问题，但真正读取数据仍要通过内存，为此处理器集成了cache，把常用的数据放在cache中，每次读取内存时，先在cache中找，找到了则成为cache命中，找不到则去内存中找，并把内容写到cache中。

如一款4核处理器，每核独享128K L1 cache和1024K L2 cache，4核共享4096K L3 cache。而cache的读写是以cache line为单位的，一般为64bit大小。即如上述的，把一个数据写入cache中，会把相邻的64bit都写入cache，所以提高数据局部性，即同时要用的数据尽量放在一起，可以大大提高存储访问速率。而相反，因为如果cache本已经满了，此时再写一个会将原来的一条cache line替换出去，所以若数据局部性不好，仅为一个BYTE就需替换整条cache line，而若这个数据又不是一直用（时间局部性也不好），那么它很快也要被替换出去，这样会大大降低存储访问速率。

Cache的工作模式主要有三种，数据回写(write-back):这是最高性能的模式,也是最典型的,在回写模式下,cache内容更改不需要每次都写回内存,直到一个新的 cache要刷新或软件要求刷新时,才写回内存。 写通过(write-through):这种模式比回写模式效率低,因为它每次强制将内容写回内存,以额外地保存cache的结果,在这种模式写耗时,而读和回写模一样快,这都为了内存与cache相一致而付出的代价。预取 (prefectching):一些cache允许处理器对cache line进行预取,以响应读请求,这样被读取的相邻内容也同时被读出来,如果读是随机的,将会使CPU变慢,预取一般与软件进行配合以达到最高性能。

Cache是有硬件控制的，写入写出cache都是硬件自动完成的，但要发挥出cache真正的优势，关键在软件设计上，设计精巧的（cache敏感的）数据结构、算法，才能利用cache，否则有了cache反而会降低效率。

    总结起来，优化主要有：

3.几个算法优化的例子

3.1基数排序（radix-sort）

    主要参考《Radix-Sort-For-Vector-Multiprocessors》一文，基数排序在《算法基础1》中已经讲过，这是一种non-comparison型的排序算法，以空间换时间，时间复杂度仅为O(n)，在memory已不再是问题的情况下，这种算法很常用。其基本思想如下图：

从低位开始，向高位，依次以每位上的数字归类（不是排序），最终就会得到结果。

    算法的关键在于归类，如以十进制为例，每次迭代应准备10个桶（bucket），分别记录该位（digit）为0-9的key值的个数。从而构造成一个直方图（Histogram），对该直方图做依次前缀和操作（prefix-sum）。然后根据得到的直方图，再次迭代所有数据，做如下操作：

ADDR = Bucket[Data-digit];        ADDR为该key值在新序列中的位置

R[ADDR] = Data;                把数据写入新序列相应的位置处

Bucket[Data-digit] = ADDR + 1;    为下一个有同样digit的key值安排位置

 

    按常规的数据划分的方法，把这个算法用在多核中，就不是那么自然，因为histogram必须是全局的，才能为每个key安排真确的位置。若维护一个全局的histogram，以同步互斥的方式让所有核来共享这个histogram，每次写histogram都要同步，显然会影响性能。

    为了能充分利用TLP，该文作者没有用全局histogram，而是为每个processor都准备了一个独有的histogram，每个核独自完成HISTOGRAM-KEYS操作，并安排一个同步障（barrier）进入SCAN-BUCKETS，即计算前缀后prefix-sum，如下

Bucket(i,j) = sum_k=0~p-1{sum_m=0~j-1(Bucket(k,m))} + sum_k=0~i-1(Bucket(k,j))

两部分组成，一是所有处理器中digit<j的key值数，一是该处理器之前的处理器中digit=j的key值数。

    注意这里计算是虽然用到了其它的bucket，但结果仍在本地bucket中，且计算完之后就与其它bucket无关了，每个processor可以独立以本地的bucket完成RANK-AND-PERMUTE。

    这样通过巧妙的设计中间数据，仅需两个不同障就可以利用TLP来解决。多核大部分时间内是不需要交互和同步的，这就大大提高了效率。

    这个实现方法（implementation）最大的问题在于，数据的局部性非常差，input序列中连续的数据，output时可能被映射到整个序列中去，这会造成严重的cache miss和memory latency。另一方面，它也很难利用SIMD数据级并行，应为只能保证输入输出一方是连续的。

3.2双调合并排序（bitonic-merge sort）

    主要参考《Efficient implementation of sorting on multi-cores SIMD CPU architectures》一文。 合并排序算法是一种常用的comparison-sort，其时间复杂度为理论上的极限N*logN。其基本思想是：每两个元素排序，两个二元序列合并merge成一个大的有序列，依次…直到合并出N元有序列。可以简单得到其需要logN次迭代iteration，每次迭代中，每个元素都要被比较依次，因此时间复杂度为NlogN。

    最简单的合并过程如下：两个序列从头开始，每两个元素比较，较小的元素写入output序列，且取该元素所在序列的下一个元素继续比较，依次…直到一个序列比较完了，另一个序列的剩余部分就可以直接merge到output序列尾了。

 

    双调合并排序借鉴这种合并方法，但不同的地方是每次不是比较两个元素，而是比较两组元素（SIMD宽度），得到较小的一组写入output序列，较大的一组和下一组比较（下一组的选择，只要比较两序列的头元素，取较小的那组），因为得到的较大一组的所有元素肯定是小于某一个序列中剩下的所有元素的，所以这种方法是可行的。

    为什么用这种方法？它可以充分利用SIMD指令。首先看一下，比较两组序列的一般方法，如下图所以，是比较两组4-element：

一组以升序排列，一组以降序排列，经过3级（log4 + 1）比较就可以得到最终的排序序列，那么再得到较大一组和较小一组就很简单了。至于为什么这样做就能得到正确序列，那是Batcher定理所阐述的内容，这里不细说了。

    可以看出的是，每一级的操作，都是将所有元素两两比较，得到MAX/MIN序列，再进行一些换位shuffle，进入下一级的比较。SIMD指令的关键就在于能在一个指令周期内完成一组数据的比较、shuffle操作，从而可以大大提高效率。用SIMD指令完成上图所示操作的代码如下：

    随着SIMD指令的宽度进一步提高，尤其是以GPU为代表的更高计算密度的新型处理器的进一步发展，这种方法的优越性将更加体现出来。

3.3哈希连接（Hash-Join）

    主要参考《Sort vs Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs》一文，连接Join操作是数据库中常用的操作，其意思就是找出两个序列R，S中所有key值相同的元组tuples。

    最笨的方法对R中任意一个元素，遍历S中的所有元素，找到相同的。这种方法效率很低，如R,S中都有n个元素，时间复杂度将为n²。

    另一个方法是Sort-Merge Join（排序合并连接），即对R,S分别先排好序，从序列头开始，比较两序列中的元素，若相等则输出，若某一方的key值偏小，则取该序列的下一个，直到遍历完整个序列。这样时间复杂度仅为n。不过排序算法消耗的时间会比较长，所以一般认为这种方法的瓶颈在排序上，效率不是很高。不过该文作者指出，随着计算密度、SIMD宽度进一步提高，一些合并排序算法的效率将会得到大幅提高，未来这种Join算法很可能再次占据主位。

    目前被认为最高效的算法即为Hash-Join。它借鉴hash方法的精髓，将两个序列的数据先归类，划分成很多数据量比较少的小类R₁,R₂…R_i和S₁,S₂…S_i。因为相同的元素必然处于相同的类中，所以只要比较R_i和S_i中的元素，虽然这是仍要用最笨的办法，但数据量较小，这是一种化整为零的方法，可以证明该方法的期望复杂度为n²/m（m为划分出的类数），近似为线性时间n。

 

    下面来看，如何针对memory来对该方法优化，主要是两个方面，cache和TLB。

    首先看比较R_i和S_i中的元素，该操作时存储的具体情况，S_i固定着，每次取R_i中的一个元素来和S_i中的所有元素比较。于是希望S_i的所有元素一直保留在cache中，而R_i则可以以cache line为单位依次被换入换出cache中。

    因此希望划分出的S_i的大小为cache的大小（略小一点点），若S中共有N_s个元素，cache中可以放k个元素，则S应被划分为N_s/k份。

    注意这里划分后，虽然各份的期望大小为cache，但数据不均匀（skew），会导致有些类很小，有些类则很大。所以在Join阶段，还需根据子类的大小，采取进一步的划分。总之就是要保证要被循环遍历的所有元素都尽量放在cache中。

 

    其次再看TLB。注意到划分时页表的使用情况。输入数据（连续的）需要一个页表（虽然input数据远不止一个页表4KB大小，但它同一时间只有一个，一个页读完后只需把该页从TLB替换出去，替换进来下一页即可，所以只要一个TLB entity），而输出为N_s/k份连续的子类，且同时需要，因此需要N_s/k个TLB entity。

    很显然，N_s足够大时，处理器中的TLB entity不能满足要求。因此该文作者提出一种分层次划分的方法。若TLB中有p个可用entity，则每层划分出p个子类，直到p^l = N_s/k。l即为所需划分的层次。

 

    值得注意的是，这种看似简单的优化，对算法运行性能的提高不是一点点，而是大幅的，必须重视。很多其它一些算法，由于没有这么良好的数据局部性，而无法进行这方面的优化，使得运行性能很低，如何改进这些算法以使得满足cache和TLB的运行要求也是一个热点。

4.小结

    针对现今的计算机体系架构，很多经典的算法都实现了多核的加速优化，但仍存在一些亟待解决的问题。主要是方面。

    1.对各种算法的进一步优化。已有的成果还有进一步优化的空间，这毕竟才是近几年的发展。尤其是复杂查询，如top-k、KNN、skyline等，面临着海量数据的挑战以及高响应速度的需求，需要进一步优化。

    2.与GPU的协同工作。GPU是今年来出现的又一种高效数据处理器，相比于CPU利用TPL来提升速率，GPU高密度的计算可以有效地实现SIMD的DLP。目前AMD、Intel都在整合CPU和GPU，实现两者的无缝连接，这将数据处理领域新的挑战。

    3.尝试建立多核算法优化的模型。当前学术界对各个算法的改进取得了可喜成果，但没有一个共同的模型做参考，只能是一种算法一种策略。另外，处理器仍为不断发展，cores数量、以及SIMD宽度都将会进一步增加，如何保证算法的可扩展性，是控制算法迁移成本的关键。

4.多核敏感的系统设计。数据处理领域的优化仅是一方面，尝试设计多核敏感的原型系统，才能更充分地利用多核处理器的计算资源，从而提高数据处理的效率，以及请求响应速度。