21日上午，来自新加坡国立大学的何丙胜副教授为我们带来了《Big Data onFurther Haradware》系列报告的第二场。本次报告内容包括三个研究工作，分别为：
1. 《Deployment of hash tables on many-core architectures with die-stacked High Bandwidth Memory》；
2. 《Many-core needs fine-grained scheduling: A case study of query processing on Intel Xeon Phi processors》；
3. 《Revisiting the Design of Data Stream Processing Systems on Multi-Core Processors》。
报告伊始，何老师分享了高带宽的多核架构下实现哈希表的实现（《Deployment of hash tableson many-core architectures with die-stacked High Bandwidth Memory》）的工作。这项工作主要面向新硬件下的混合内存环境，结合DRAM和HBM（High Bandwidth Memory）来提高哈希连接的性能。何老师由浅入深地介绍了Intel第二代MIC架构Xeon Phi融合处理器Knights Landing（KNL）的特性，KNL是为高度并行工作负载设计的处理器，并首次实现了内存与高速互连技术的集成。相比Knights Corner协处理器（KNC），KNL消除了对PCI-E的依赖，在不同物理核之间的直接通讯带宽为700GB/s。KNL最大支持72个CPU物理核，16GB的HBM片上高速内存，384GB的DDR4系统内存。HBM与DDR4形成了鲜明的对比：CPU与HBM的通讯带宽为100GB/s，但是与DDR4只有30GB/s的带宽；HBM大小只有16GB，但是DDR4可以达到384GB。也就是说，HBM具有容量小带宽大的特点，而DDR4具有容量大带宽小的特点。进一步的，对于随机内存访问，HBM的带宽略高于主存，要想最大化利用带宽需要结合主存和HBM。
在关系型数据库中，哈希表是一个重要的和具有挑战性的数据结构，也是一个很好的研究对象：
在存储形式上可以采用链地址法、开放地址法，后者以数组形式存放，支持快速访问，适合高带宽的硬件；
如何处理哈希冲突是个挑战；
如何访问哈希表也存在问题，如何高效地执行单个插入、一组插入、查询是个问题。
在此背景下，在KNL这种多核处理器下高效地实现哈希表更是一个值得研究的问题。解决这个问题需要最大化利用内存资源以及最小化负载倾斜。但是，要达到以上目标面临多个挑战：
希表的内存访问很难预测，可能发生在任何核心和NUMA节点之间；
现有的支持NUMA的优化只考虑一种类型的内存；
现有的面向NUMA的优化不考虑线程级的工作负载不平衡。
针对这些挑战，何老师团队提出了解决方案：
首先估计内存访问的代价，内存访问代价按照Join代价估计相同的策略来估计，通过采样的方式估计内存访问代价；
根据计算的内存访问代价切分哈希表Build（构建）和Probe（探测）所在的物理核。通过实验对比了单纯使用DDR4、使用HBM作为Cache、传统NUMA和本文的优化（HSHJ）四种方法的性能，可以看出HSHJ性能更优，并且负载更加均衡。
然后，何老师以Intel Xeon Phi处理器上的查询处理为例介绍了多核下的细粒度的调度优化（《Many-core needs fine-grained scheduling: A case study of query processing on Intel Xeon Phi processors》）的工作。何老师以数据库中的复杂的操作符Scan、Sort和Hash Join为例，分析了这些操作符在多核处理器上受到内存阻塞的困扰，同时Sort、Hash Join操作符内存带宽利用率很低。
解决上述问题的一个基本的想法是对有资源需求的操作符进行并发执行，更好的利用硬件资源。所以，需要将复杂的操作符进行拆分和深入分析：将每个阶段区分为计算密集型和内存密集型；在每个核心的超线程中，混合这些阶段以增加总体IPC。但是，随之而来的是两方面的挑战：
操作符拆分在运行时引起额外开销，这是由于相同操作符分解的阶段具有依赖关系，必须以串行方式执行，同时在运行时，它们之间存在潜在的上下文切换开销；
寻找良好的并发执行的匹配需要时间，在处理多个查询时，搜索空间可能非常大。
何老师随后给出了解决方案：
每个操作符看作由几个SIMD部分组成；
一个完整的运算符被定义为部分的DAG，每个部分是一个顶点，
运算符的分解转化为图问题，将具有相似资源需求的顶点合并在一起。原来的多个操作符的问题转化为了更多的并发执行阶段，通过实验可以看出这种优化带来了更高的性能。
最后，何老师分享了在多核处理器上重新设计数据流处理系统（《Revisiting the Design of Data Stream Processing Systems on Multi-Core Processors》）的工作。CPU已经进化了好几代，总的来看有三个趋势：晶体管仍在迅速增长、逻辑核心的数量也在快速增加、其他指标在放缓，我们目前正处在一个多核的时代。另一方面，与CPU相比，内存的变化没有那么显著，导致它们之间的性能差异很大。但是随着CPU核心数量的增长，内核之间争夺同一块内存的竞争越来越激烈，并且限制了机器能够支持的CPU内核数量。因此，NUMA硬件架构将多个CPU添加到同一块板中，每个CPU都有自己的本地内存，以减少CPU内核之间的潜在冲突。CPU物理核之间的通信由其他通道支持。NUMA将性能问题引入到数据管理系统中。即使是一个CPU物理核也变得越来越复杂。具体来说，更多的CPU内核被放在同一个芯片上，芯片上的缓存层次结构变得越来越大、越来越深、越来越复杂。越来越复杂的硬件对软件优化提出了挑战。从软件来看，处理实时数据流的需求越来越大，市面上已经存在许多数据流处理系统（DSP）如Apache Storm、Twitter Heron和Apache Flink等。最近的DSP系统主要目标是使用一组服务器进行水平扩展，但是很少关注在单个机器上优化性能。它们主要围绕一些关键的设计，包括a）带有消息传递的流水线处理、b）按需数据并行处理和c）基于JVM的实现。何老师的研究团队主要关注可扩展架构设计的这三个方面。接下来何老师分享了这三个方面的设计原则，目标首先是希望区分DSP系统的设计共性，并了解这些设计如何与现代处理器交互；其次，希望开发一些硬件和软件方法来解决瓶颈问题。所以，何老师小组设计了一个涵盖广泛应用的基准测试，然后对两种最先进的DSP系统进行了详细的分析研究，对发现的问题设计了优化技术来提高系统性能。
何老师对于基准测试的设计总结了四条经验：
Relevance，即目标相关性，这项工作中主要体现DSP作为主要部件的性能；
Protability，即可移植性，能够在不同环境下运行；
Scalability，即可扩展性，即能够设置CPU核心数、数据集大小和查询负载；
Simplicity，即简单易用。
通过这一套基准测试系统，文章对比了Storm系统与Flink系统的差异，得出了两个重要的发现：
在同一函数的两个连续调用之间有较大的指令占用空间，会导致明显的L1 cache不命中；
当前系统的消息传递设计忽略了NUMA的影响，并导致严重的性能下降，这是由于大量的远程内存访问开销造成的。
何老师团队考虑优化以上问题，他们通过对非阻塞的元组批处理来减少指令缓存丢失，通过面向NUMA的执行器设计减少远程内存访问。实验表明，优化后Storm性能提升了3.2倍。
撰稿人：段惠超
排版：寿暖瑜
