多核处理器中基于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%左右.     

面向多线程多道程序的加权共享Cache划分

并行应用在共享Cache结构的多核处理器执行时,会因为对共享Cache的冲突访问而产生性能下降和执行时间不确定的现象.共享Cache划分技术可以把共享Cache互斥地分配给多个进程使用,是解决该问题的有效方法.由于线程间的数据共享,线程数目不同的应用对共享Cache的利用率不同,但传统的以失效率最低为目标的共享Cache划分算法(例如UCP)没有区分应用线程数目的不同.文中设计了一种面向多线程多道程序的加权共享Cache划分框架(Weighted Cache Partitioning,WCP),包括面向应用的失效率监控器和加权Cache划分算法.失效率监控器以进程为单位动态监控在不同的Cache容量下应用的失效率;而加权Cache划分算法扩展了传统的失效率最优的Cache划分算法,根据应用线程数目的不同在进行Cache划分时给应用赋予不同的权值,以使具有更多线程的应用获得更多的共享Cache,从而提高系统的整体性能.实验结果表明:加权Cache划分算法虽然失效率有所增高,但却改进了IPC吞吐率、加权加速比和公平性.在由科学和工程计算应用组成的多道程序测试用例中,WCP-1的IPC吞吐率比以失效率最低为目标函数的共享Cache划分算法最高高出10.8%,平均高出5.5%.     

基于共享Cache多核处理器的Hash连接优化

针对目前主流的多核处理器,研究了基于共享缓存多核处理器环境下的数据库Hash连接优化.首先提出基于Radix-Join算法的Hash连接多线程执行框架,通过实例分析了影响多线程Radix-Join算法性能的因素.在此基础上,优化了Hash连接多线程执行框架中的各种线程及其访问共享Cache的性能,优化了聚集连接时Hash连接算法的内存访问,并分析了多线程聚集划分的加速比.基于开源数据库INGRES和EaseDB,实现了所提出的连接多线程执行框架,在实验中测试了多线程Hash连接框架的性能.实验结果表明,该算法可以有效解决Hash连接执行时共享Cache在多线程条件下的访问冲突和处理器负载均衡问题,极大地提高了Hash连接性能.     

一种多核Cache低功耗动态混合划分算法研究

随着片上集成核数的增多,片上Cache的面积也越来越大,同时消耗的能耗也越来越多.因此,面向低功耗的Cache划分方法不可避免地成为了Cache划分中需要考虑的一个重点.然而,目前的Cache划分算法主要是面向公平性、性能或者QoS的,很少考虑到功耗问题.面向低功耗的混合划分方法(LPHP)利用程序运行的局部性原理,将在L2 Cache中访问差异度较大的线程作为一个划分单位,通过私有和共享两种资源分配方式相结合来实施Cache划分,从而实现在运行同一个应用时,使用更少的Cache列,关闭剩余列,达到降低系统功耗的目的.LPHP通过减少在使用的Cache列来达到降低功耗的目的,符合当前多核发展低功耗的趋势.     

ARP:同时多线程处理器中共享Cache自适应运行时划分机制

同时多线程是一种延迟容忍的体系结构,采用共享的二级Cache,在每个周期内可以执行多个线程的多条指令,这就会增加对存储层次的压力,文中主要研究了SMT处理器中多个并发执行的线程之间共享Cache的划分问题,尤其是Cache共享中的公平性问题以及它和吞吐量之间的关系,传统的LRU策略会根据线程的需要隐式地划分共享Cache,给具有较高需求的线程分配较多的Cache空间,对Cache的管理具有不公平性,从而会引起线程饿死、优先级反转等问题,实现了一种自适应、运行时划分机制(ARP)来管理共享Cache.ARP采用公平性作为划分的度量,并且使用动态划分算法来优化公平性,该算法具有易于实现,所需剖析较少的特点,硬件上使用经典的监控器来收集每个线程的栈距离信息,其存储开销不到0.25%.实验结果显示,与基于LRU的Cache划分相比,ARP可以将一个2路SMT处理器的公平性提高2.26倍,而将吞吐量平均提高14.75%.     

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

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

片上多核处理器共享Cache划分的公平性研究

公平性是一个关键的优化问题,当系统缺乏公平时,会出现线程饿死和优先级反转等问题.以公平性优化作为研究目标,分析当前共享Cache划分公平性的评价标准,找出了其评价参数和划分策略的不足,提出了一种新的共享Cache划分方案.通过提出一个新的多线程公平性评价指标并改进了已有的公平划分策略,从而提高多线程运行的公平性.实验结果表明,该共享Cache划分方案显著提高了系统公平性,并且系统吞吐量也有提高.     

CMP中Cache私有方式下副本容量的动态控制

CMP中二级Cache多采用分布式结构,其中有两种基本管理方式:共享方式和私有方式。共享方式能最大程度利用二级Cache容量空间但却有高的平均访问延迟;私有方式能提供低访问延迟,但由于数据块副本的存在减少了Cache有效容量,因而增加了Cache缺失率。本文提出了基于私有方式的副本动态控制策略,能根据实际应用程序的执行程序情况动态控制副本数据块的数量,从而提高二级Cache性能。     

一种新型共享Cache动态划分机制

综合效用最优划分共享Cache方法和传统LRU方法的优点,提出一种新的动态划分共享Cache方法。该方法可消除不同线程在共享Cache中的相互影响,当多核并行执行的程序均对共享Cache中占有的路数敏感时,可解决采用效用最优划分方法时的性能下降问题。经SPEC CPU2000测试表明,该方法与传统LRU和效用最优划分方法相比,系统整体性能平均分别提高20.28%和14.37%。     

一种片上众核结构共享Cache动态隐式隔离机制研究

访存带宽是限制众核处理器件能提升的关键,将片上最后一级Cache设计为所有处理器核共享是必要的.在共享Cache中隔离放置冲突的数据,是提高共享Cache性能的关键.文中提出了缓存块链接的硬件方法,用于隔离共享Cache中不同线程之间的数据.文中基于时钟精准的片上众核结构模拟器,使用Splash2程序组和生物信息学中的仟务,对所提机制进行了评估.实验结果表明,与传统共享Cache相比,使用缓存块链接机制时,使得共享Cache的冲突性缺失率降低约20%,而使得IPC平均提高了约10%.     

基于分布式合作cache的私有cache划分方法

当片上多处理器系统上运行多个不同程序时,如何给这些不同的应用程序分配适当的cache空间成为一个难题。Cache划分就是解决这一难题的有效方法,目前大部分的划分方法都是针对最后一级共享cache设计的。私有cache划分(private cache partitioning,PCP)方法采用一个分布式一致性引擎(DCE)把多个私有cache组织在一起,最后通过硬件信息提取单元获得多个程序在不同cache路上的命中分布情况,用于指导划分算法的执行,最后由每个DCE根据划分算法运行的结果对cache空间进行划分。实验结果表明PCP方法降低了失效率,提高了程序执行性能。     

Heterogeneous-aware cache partitioning: Improving the fairness of shared storage cache

In this paper, we investigate the problem of fair storage cache allocation among multiple competing applications with diversified access rates. Commonly used cache replacement policies like LRU and most LRU variants are inherently unfair in cache allocation for heterogeneous applications. They implicitly give more cache to the applications that has high access rate and less cache to the applications of slow access rate. However, applications of fast access rate do not always gain higher performance from the additional cache blocks. In contrast, the slow application suffer poor performance with a reduced cache size. It is beneficial in terms of both performance and fairness to allocate cache blocks by their utility.In this paper, we propose a partition-based cache management algorithm for a shared cache. The goal of our algorithm is to find an allocation such that all heterogeneous applications can achieve a specified fairness degree as least performance degradation as possible. To achieve this goal, we present an adaptive partition framework, which partitions the shared cache among competing applications and dynamically adjusts the partition size based on predicted utility on both fairness and performance. We implement our algorithm in a storage simulator and evaluate the fairness and performance with various workloads. Experimental results show that, compared with LRU, our algorithm achieves large improvement in fairness and slightly in performance.     

片上多核处理器共享资源分配与调度策略研究综述

对于片上多核处理器,如何在多线程间公平有效地分配调度有限的共享资源是一个很重要的问题.随着处理器核规模的增长,多线程对于系统中有限的共享资源的争夺将愈发激烈,由此导致的对于系统性能的影响也将更加显著.为了缓解乃至解决这一问题,除了增加可用共享资源外,一个能够公平有效地在多线程间分配共享资源的调度算法也至关重要.在各类共享资源中,对于系统性能有着最大影响的是共享缓存和动态随机存储器(dynamic random-access memory, DRAM)系统.对于共享缓存,可以通过缓存分区来降低由于线程间的争夺所带来的影响;对于DRAM系统,可以采取适当的调度算法来调节各个线程发出的访存请求的服务优先级,从而改善系统性能.首先分别以系统吞吐量和公平性为优化目标介绍了一系列对共享缓存的分区调度算法,并针对缓存分区粒度过大的问题给出了相关解决方案.然后从利用线程的访存行为特征和借鉴网络路由算法等多个角度介绍了DRAM的调度算法.研究了从全局出发的联合调度算法,以解决针对不同共享资源的调度算法间相互矛盾的问题.最后从不同角度对于今后的研究进行了展望.     

On modeling contention for shared caches in multi-core processors with techniques from ecology

Multi-core x86_64 processors introduced an important change in architecture, a shared last level cache. Historically, each processor has had access to a large private cache that seamlessly and transparently (to end users) interfaced with main memory. Previously, processes or threads only had to compete for memory bandwidth, but now they are competing for actual space. Competition for space and environmental resources is a problem studied in other scientific domains. This paper introduces methods from ecology to model multi-core cache usage with the competitive Lotka–Volterra equations. A model is presented and validated for characterizing the interaction of cores through shared caching, and for predicting the degree to which different workloads will interfere with each others’ execution from cache contention.     

多核处理器面向低功耗的共享Cache划分方案

随着多核处理器的发展,片上Cache的容量随之增大,其功耗占整个芯片功耗的比率也越来越大。如何减少Cache的功耗,已成为当今Cache设计的一个热点。本文研究了面向低功耗的多核处理器共享Cache的划分技术(LP-CP)。文中提出了Cache划分框架,通过在处理器中加入失效率监控器来动态地收集程序的失效率,然后使用面向低功耗的共享Cache划分算法,计算性能损耗阈值范围内的共享Cache划分策略。我们在一个共享L2 Cache的双核处理器系统中,使用多道程序测试集测试了面向低功耗的Cache划分:在性能损耗阈值为1%和3%的情况中,系统的Cache关闭率分别达到了20.8%和36.9%。     

Dynamic Partitioning of Shared Cache Memory

This paper proposes dynamic cache partitioning amongst simultaneously executing processes/threads. We present a general partitioning scheme that can be applied to set-associative caches.Since memory reference characteristics of processes/threads can change over time, our method collects the cache miss characteristics of processes/threads at run-time. Also, the workload is determined at run-time by the operating system scheduler. Our scheme combines the information, and partitions the cache amongst the executing processes/threads. Partition sizes are varied dynamically to reduce the total number of misses.The partitioning scheme has been evaluated using a processor simulator modeling a two-processor CMP system. The results show that the scheme can improve the total IPC significantly over the standard least recently used (LRU) replacement policy. In a certain case, partitioning doubles the total IPC over standard LRU. Our results show that smart cache management and scheduling is essential to achieve high performance with shared cache memory.     

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.     

Lightweight dynamic partitioning for last-level cache of multicore processor on real system

With rapid development of multi/many-core processors, contention in shared cache becomes more and more serious that restricts performance improvement of parallel programs. Recent researches have employed page coloring mechanism to realize cache partitioning on real system and to reduce contentions in shared cache. However, page coloring-based cache partitioning has some side effects, one is page coloring restricts memory space that an application can allocate, from which may lead to memory pressure, another is changing cache partition dynamically needs massive page copying which will incur large overhead. To make page coloring-based cache partition more practical, this paper proposes a malloc allocator-based dynamic cache partitioning mechanism with page coloring. Memory allocated by our malloc allocator can be dynamically partitioned among different applications according to partitioning policy. Only coloring the dynamically allocated pages can remit memory pressure and reduce page copying overhead led by re-coloring compared to all-page coloring. To further alleviate the overhead, we introduce minimum distance page copying strategy and lazy flush strategy. We conduct experiments on real system to evaluate these strategies and results show that they work well for reducing cache misses and re-coloring overhead.     

A phase adaptive cache hierarchy for SMT processors

Resizable caches can trade-off capacity for access speed to dynamically match the needs of the workload. In single-threaded cores, resizable caches have demonstrated their ability to improve processor performance by adapting to the phases of the running application. In Simultaneous Multi-Threaded (SMT) cores, the caching needs can vary greatly across the number of threads and their characteristics, thus, offering even more opportunities to dynamically adjust cache resources to the workload.In this paper, we demonstrate that the preferred control methodology for data cache reconfiguring in a SMT core changes as the number of running threads increases. In workloads with one or two threads, the resizable cache control algorithm should optimize for cache miss behavior because misses typically form the critical path. In contrast, with several independent threads running, we show that optimizing for cache hit behavior has more impact, since large SMT workloads have other threads to run during a cache miss. Moreover, we demonstrate that these seemingly diametrically opposed policies are closely related mathematically; the former minimizes the arithmetic mean cache access time (which we will call AMAT), while the latter minimizes its harmonic mean. We introduce an algorithm (HAMAT) that smoothly and naturally adjusts between the two strategies with the degree of multi-threading.We extend a previously proposed Globally Asynchronous, Locally Synchronous (GALS) processor core with SMT support and dynamically resizable caches. We show that the HAMAT algorithm significantly outperforms the AMAT algorithm on four-thread workloads while matching its performance on one and two thread workloads. Moreover, HAMAT achieves overall performance improvements of 18.7%, 10.1%, and 14.2% on one, two, and four thread workloads, respectively, over the best fixed-configuration cache design.