多核处理器中基于Radix-Join的嵌套循环连接优化

针对目前主流的多核处理器,研究了基于共享Cache多核处理器的数据库Nested Loop Join(NINLJ)优化.针对无索引情况下的NLJ,提出了基于Radix-NL-Join算法的NLJ多线程执行框架.从减少Cache访问冲突和提高Cache命中率两个方面优化了NINLJ多线程执行框架中的聚集划分和聚集连接线程.主要贡献如下:1.针对多线程访问共享Cache容易出现共享Cache访问冲突的问题,优化了聚集划分阶段的多线程聚集划分线程的启动时机;2.针对聚集连接阶段,聚集连接线程Cache访问性能不佳,利用聚集连接线程顺序访问聚集的优势,采用预取线程提高聚集连接线程的性能;3.在实验中,基于开源数据库EaseDB实现了上述多线程执行框架,测试了多线程NLJ的性能.实验结果表明,提出的NLJ多线程执行框架,可以充分利用多核处理器的计算资源,并有效地解决共享Cache在多线程条件下的Cache访问冲突问题,大大提高了NLJ的性能,相对于未采用Cache优化的多线程Radix-NL-Join算法,其性能提升了26%左右.     

多核处理器中支持频繁访问的B~+-Tree

针对传统B+-Tree自顶向下访问模式的缺点,提出了支持频繁访问的FAB+-Tree(Frequent Access B+-Tree)。在B+-Tree的基础上增加了Hash辅助索引,使得访问B+-Tree时直接定位到叶结点,并利用基于内存的直接访问表及位矢量列表提高更新性能。同时基于共享Cache多核处理器,提出了基于流水线的FAB+-Tree多线程访问模块,并优化了该模块的共享Cache访问性能。在实验中,基于开源数据库INGRES实现了FAB+-Tree和多线程访问模块,实验结果表明B+-Tree的访问性能得到显著提高。     

基于共享cache多核处理器的数据库内存排序优化

针对目前主流的多核处理器,提出了共享cache敏感的数据库排序多线程执行框架(sharedcache sensitive multithreaded sorting framework,SCS-MSF).首先分析了多线程QuickSort排序在共享cache多核处理器中执行时面临的性能瓶颈,在此基础上针对SCS-MSF每个处理阶段的数据访问特点,提出了各自的多线程并行执行模式,并通过各种优化策略改善线程执行时的cache性能,特别是减少多线程访问共享cache时的访问冲突问题,以提高线程的cache性能.在实验中,基于内存数据库EaseDB实现了SCS-MSF.实验结果表明SCS-MSF具有良好cache访问性能,从而提高了多线程执行的效率,而且性能稳定,数据库排序性能得到了较大提高.     

基于Supersonic的并行分组聚集

针对在分析型联机分析处理(OLAP)应用中频繁出现的数据密集型操作符——分组聚集耗时较多的问题,提出Cache友好的分组聚集算法对该操作进行性能优化。首先,为充分发挥列存储在数据密集型计算方面的优势,采用基于开源的列存储查询执行引擎Supersonic,并在此之上设计Cache友好的分组聚集算法;其次,为加速查询的执行,使用并行技术,将单线程的分组聚集算法改为多线程并行的分组聚集算法。基于Supersonic设计并实现4种并行分组聚集算法:无共享Hash表并行分组聚集(NSHPGA)算法、表锁共享Hash表并行分组聚集(TLSHPGA)算法、桶锁共享Hash表并行分组聚集(BLSHPGA)算法、节点锁共享Hash表并行分组聚集(NLSHPGA)算法,且在不同的分组势集、不同的线程数的情况下,针对上述4种算法做了多组实验。通过对比3种不同粒度的共享Hash表并行分组聚集算法的加速比,得出NLSHPGA算法在加速比和并发度两方面表现最好,部分查询可达到10倍加速比;通过比较NSHPGA算法和NLSHPGA算法的加速比、Cache miss内存使用等情况,得出NLSHPGA算法在分组势集大于8时,加速比超过NSHPGA算法,并且Cache miss更低,使用的内存更少。     

一种高效的移动对象连续多范围查询处理框架

针对连续多范围查询处理,结合多核多线程技术和大容量内存技术,通过将移动对象和查询放在内存中处理,提出了一种基于多线程的连续多范围查询处理框架.该框架基于多核处理器平台采用多线程技术周期性地处理查询和移动对象的更新,并周期性地计算多范围查询的结果.提出了基于移动对象数据均匀划分的多线程连续多范围查询处理算法,该算法以为查询建立的格网索引为基础.给出了该索引的构建思想和更新算法.考虑到基于内存的算法受Cache访问性能影响,提出了基于空间填充曲线的移动对象存储优化方法.实验证明,基于多核平台的多线程处理能够高效地处理连续多范围查询,同时通过移动对象存储优化能够提高算法运行中Cache访问命中率,进而提高算法性能.     

同时多线程处理器上的Cache性能分析与优化

同时多线程(SMT)是一种延迟容忍的体系结构,它在每个周期内可以执行多个线程的多条指令.在SMT处理器上,对于片上共享存储这个复杂的结构资源,至今还没有很好的共享和冲突解决方案.本文着重研究了在多个并发执行的线程间划分共享Cache所存在的问题,指出基于LRU策略的传统Cache会根据需要隐式地划分共享Cache,这在某些情况下会导致全局性能的下降.针对这一问题并且考虑到SMT处理器上对Cache访问带宽的需求,本文提出采用一种多模块多体的Cache结构设计方案.并且在一个修改过的SMT模拟器上对该设计方案进行了性能评价.实验结果显示,相比于基于LRU策略的传统Cache,这一结构可以将一个4路SMT处理器的IPC提高9%.     

基于多核处理器的VTD-XML节点查询执行性能优化

针对目前主流的多核处理器,研究了基于VTD-XML的节点查询执行性能优化,即基于预读策略从多线程并发执行和提高线程内存访问性能两个方面优化XML节点查询的性能。实验结果表明,提出的多线程XML文档解析框架可以充分利用多核处理器的计算资源,并有效地提高线程的内存访问性能,大大提高了XML节点查询的性能。     

基于多核处理器的VTD-XML节点查询执行性能优化

针对目前主流的多核处理器,研究了基于VTD-XML的节点查询执行性能优化,即基于预读策略从多线程并发执行和提高线程内存访问性能两个方面优化XML节点查询的性能。实验结果表明,提出的多线程XML文档解析框架可以充分利用多核处理器的计算资源,并有效地提高线程的内存访问性能,大大提高了XML节点查询的性能。     

面向多线程程序基于效用的Cache优化策略

为了提供高速的数据访问,多核处理器常使用Cache划分机制来分配二级Cache资源,但传统的共享Cache划分算法大多是面向多道程序的,忽略了多线程负载中共享和私有数据访问模式的差别,使得共享数据的使用效率降低.提出了一种面向多线程程序的Cache管理机制UPP,它通过监控Cache中共享、私有数据的效用信息,为每个线程以及共享数据分配Cache空间,使得各个线程以及共享数据的边际效用最大化,从而提高负载的整体性能.另外,UPP还考虑了程序中数据的使用频率以及临近性信息,通过提升、动态插入策略过滤低重用数据,从而使得高频数据块留在Cache中.通过实验表明,其性能相对于基于LRU的纯共享Cache结构和基于公平的静态Cache划分结构均有提升.     

一种适应GPU的混合访问缓存索引框架

散列表（hash table）作为一类根据关键码值（key value）提供高效数据访问的数据索引结构,其广泛应用于各类计算机应用中,尤其是在对性能要求极高的系统软件、数据库以及高性能计算领域.在网络、云计算和物联网服务方面,以散列表为核心结构已经成为缓存系统的重要系统组件.然而,随着大规模数据量的大幅度增加,以多核CPU为核心设计散列表结构的系统已经逐渐出现性能瓶颈,亟需进一步改进散列表的高性能和可扩展性.随着通用图形处理器（graphic processing unit,简称GPU）的日益普及以及硬件计算能力和并发性能的大幅度提升,各类以并行计算为核心的系统软件任务在GPU上进行了优化设计并得到可观的性能提升.由于存在稀疏性和随机性,采用现有散列表的并行结构直接在GPU上应用势必会带来高频次的内存访问和频繁的总线数据传输,影响了散列表在GPU上的性能发挥.重点分析了缓存系统中散列表索引的内存访问、命中率与索引开销,提出并设计了一种适应GPU的混合访问缓存索引框架CCHT（cache cuckoo hash table）,提供了两种适应不同命中率和索引开销要求的缓存策略,允许写入与查询操作并发执行,最大程度地利用了GPU硬件的计算性能与并发特性,减少了内存访问与总线传输.通过在GPU硬件上的实现与实验验证,CCHT在保证缓存命中率的同时,性能优于其他用于缓存索引的散列表.     

Hybrid Access Cache Indexing Framework Adapted to GPU

Hash tables, as a type of data indexing structure that provides efficient data access based on key values, are widely used in various computer applications, especially in system software, databases, and high-performance computing field that requires extremely high performance. In network, cloud computing and IoT services, hash tables have become the core system components of cache systems. However, with the large-scale increase in the amount of large-scale data, performance bottlenecks have gradually emerged in systems designed with a multi-core CPU as the core of the hash table structure. There is an urgent need to further improve the high performance and scalability of the hash tables. With the increasing popularity of general-purpose Graphic Processing Units (GPUs) and the substantial improvement of hardware computing capabilities and concurrency performance, various types of system software tasks with parallel computing as the core have been optimized on the GPU and have achieved considerable performance promotion. Due to the sparseness and randomness, using the existing parallel structure of the hash tables directly on the GPUs will inevitably bring high-frequency memory access and frequent bus data transmission, which affects the performance of the hash tables on the GPUs. This study focuses on the analysis of memory access, hit ratio, and index overhead of hash table indexes in the cache system. A hybrid access cache indexing framework CCHT (Cache Cuckoo Hash Table) adapted to GPU is proposed and provided. The cache strategy suitable to different requirements of hit ratios and index overheads allows concurrent execution of write and query operations, maximizing the use of the computing performance and concurrency characteristics of GPU hardware, reducing memory access and bus transferring overhead. Through GPU hardware implementation and experimental verification, CCHT has better performance than other cache indexing hash tables while ensuring cache hit ratios.     

MapReduce框架下一种负载均衡的Top-k连接查询算法

针对传统Top-k连接查询算法在处理海量数据时的时效问题,提出一种基于MapReduce框架的负载均衡的并行Top-k连接查询算法(P-TKJ)。使用直方图形式来存储数据,有助于提高CPU的利用率。同时融入了提前终止策略和磁盘数据的选择性访问,以便提高对HDFS数据访问的性能。另外,提出了一种基于最长处理时间优先(LPT)算法的负载均衡策略来均衡Reduce任务,以此设计出高效的并行Top-k连接算法。一个集群实验结果表明,该方法能够有效缩短算法的执行时间。     

基于向量引用Platform-Oblivious内存连接优化技术

以MapD为代表的图分析数据库系统通过GPU、Phi等新型众核处理器来支持高性能分析处理,在面向复杂数据模式时连接操作仍然是重要的性能瓶颈.近年来,异构处理器逐渐成为高性能计算的主流平台,内存连接性能的研究从多核CPU平台扩展到新兴的众核处理器,但众多的研究成果并未系统地揭示连接算法性能、连接数据集大小、硬件架构之间的内在联系,难以为未来异构处理器平台的数据库提供连接平台优化选择策略.本文以面向多核CPU、Xeon Phi、GPU处理器平台的内存连接优化技术为目标,通过优化内存哈希表设计,实现以向量映射替代哈希映射操作,消除哈希代价对内存连接算法的影响,从而更加准确地测量内存连接算法在多核CPU的cache大小、Xeon Phi的cache大小、Xeon Phi的并发多线程、GPU的SIMT（单指令多线程）机制等硬件相关因素影响下的性能特征.实验结果表明,缓存与并发多线程机制是提高内存连接算法性能的重要影响因素.缓存机制对于满足cache大小的连接操作具有性能优势,而GPU的并发多线程机制则在较大表的连接操作中具有较高的性能,Xeon Phi则在满足其L2 cache大小的连接操作中具有最高性能.实验结果揭示了内存连接操作性能与异构处理器硬件特性的联系,为未来异构处理器平台内存数据库查询优化器提供了优化策略.     

Modeling and Stack Simulation of CMP Cache Capacity and Accessibility

Performance trade-offs between fast data access by local data replication and cache capacity maximization by global data sharing have been extensively studied for many-core Chip Multiprocessors (CMPs). Costly simulations over a wide spectrum of the design space are generally required to gain insight for a sound design. To lower the cost, we develop an abstract model for understanding the performance impact of data replication on CMP caches. To overcome the lack of real-time interactions among multiple cores in the model, we further develop an efficient single-pass stack simulation to study the performance of CMP cache organizations with various degrees of data replication. The global stack logically incorporates a shared stack and per-core private stacks; shared/private reuse (stack) distances can be collected in a single-pass simulation. With the reuse distances, one can calculate the performance of CMP cache organizations with various degrees of data replication. We verify both the model and the stack simulation against execution-driven simulations with commercial multithreaded workloads. The results show that the abstract model provides accurate information about performance trade-offs of data replication. The stack simulation accurately predicts the performance of various cache organizations with 2-9 percent error margins using only about 8 percent of the simulation time.     

Parallel Multithreaded Satisfiability Solver: Design and Implementation

We describe the design and implementation of a highly optimized, multithreaded algorithm for the propositional satisfiability problem. The algorithm is based on the Davis-Putnam-Logemann-Loveland sequential algorithm, but includes many of the optimization techniques introduced in recent years. We provide experimental results for the execution of the parallel algorithm on a variety of multiprocessor machines with shared memory architecture. In particular, the detrimental effect of parallel execution on the performance of processor cache is studied.     

面向多核CPU和GPU平台的数据库星形连接优化

针对联机分析处理（OLAP）中事实表与多个维表之间的星形连接执行代价较高的问题,提出了一种在先进的多核中央处理器（CPU）和图形处理器（GPU）上的星形连接优化方法。首先,对于多核CPU和GPU平台的星形连接中的物化代价问题,提出了基于向量索引的CPU和GPU平台上的向量化星形连接算法;然后,通过面向CPU cache和GPU shared memory大小的向量划分来提出基于向量粒度的星形连接操作,从而优化星形连接中向量索引的物化代价;最后,提出了基于压缩向量的星形连接算法,将定长向量索引压缩为变长的二元向量索引,从而在低选择率时提高cache内向量索引的存储访问效率。实验结果表明,在CPU平台上向量化星形连接算法相对于常规的行式或列式连接性能提升了40%以上,在GPU平台上向量化星形连接算法相对于常规星形连接算法性能提升超过了15%;与当前主流的内存数据库和GPU数据库相比,优化的星形连接算法性能相对于最优内存数据库Hyper性能提升了130%,相对于最优的GPU数据库OmniSci性能提升了80%。可见基于向量索引的向量化星形连接优化技术有效地提高了多表连接性能,与传统优化技术相比,基于向量索引的向量化处理提高了较小cache上的数据存储访问效率,压缩向量进一步提升了向量索引在cache内的访问效率。     

Chip Multithreaded Consistency Model

Multithreaded technique is the developing trend of high performance processor. Memory consistency model is essential to the correctness, performance and complexity of multithreaded processor. The chip multithreaded consistency model adapting to multithreaded processor is proposed in this paper. The restriction imposed on memory event ordering by chip multithreaded consistency is presented and formalized. With the idea of critical cycle built by Wei-Wu Hu, we prove that the proposed chip multithreaded consistency model satisfies the criterion of correct execution of sequential consistency model. Chip multithreaded consistency model provides a way of achieving high performance compared with sequential consistency model and easures the compatibility of software that the execution result in multithreaded processor is the same as the execution result in uniprocessor. The implementation strategy of chip multithreaded consistency model in Godson-2 SMT processor is also proposed. Godson-2 SMT processor supports chip multithreaded consistency model correctly by exception scheme based on the sequential memory access queue of each thread.