cache profiling信息指导的软件流水

软件流水是一种重要的指令调度技术,它通过同时执行来自不同循环迭代的指令来加快循环的执行时间.随着处理器速度和访存速度差距越拉越大,访存指令尤其是cache miss的访存指令日益成为系统性能提高的瓶颈.由于这些指令的延迟不是固定的,如何在软件流水中预测并掩盖这些访存指令的延迟是非常重要的.与前人预测访存延迟的方法不同,引入cache profiling技术,通过动态收集到profile信息来预测访存延迟,并进行适当的调度.当增加模调度循环中的访存指令的延迟时,启动间隔也会随之增大,导致性能不会随之上升.CSMS算法和FLMS算法在尽量不增大启动间隔的情况下,改变访存指令的延迟.改进了CSMS算法和FLMS算法,根据cache profiling的信息来改变访存延迟,所以比前人的方法更为准确.实验表明,新方法可以有效地提高程序性能,对SPEC2000测试程序平均性能提高1%左右,个别例子的性能改进高达11%.     

模调度中的数据猜测方法

软件流水是一种重要的指令调度技术，通过重叠地执行不同的循环体来提高指令级并行性。模调度是一类重要的软件流水调度算法，保守的相关性分析可能会引入较多的模糊相关，这阻碍了模调度生成高效的调度结果。数据猜测能克服保守的相关性分析带来的调度限制，开发潜在的并行性。本文提出了模调度中的一种数据猜测方法，在开放源代码编译器ORC上实现了该方法，并用SPEC2000基准程序进行了测试，实验结果表明，该方法收到了较好的效果。     

模调度与DFA结合的技术及其在gcc上的实现

循环是程序中的热代码,而软件流水是一种细粒度的循环优化方法,它通过将循环中不同迭代之间的操作并行执行,最大程度地开发指令级并行。模调度是一种效果很好的软件流水算法。论文以gcc3.3为基础,提出了模调度与DFA结合的软件流水方法,及其工程实现,实验数据表明,优化效果明显。     

摆动模调度中的寄存器溢出技术及其在GCC中的实现

软件流水是一种通过发掘循环的不同迭代的不同部分的指令间并行性,使这些指令并行执行,从而提高循环的执行效率的优化技术.但该技术在提高指令并行性的同时也增加了寄存器压力,而寄存器溢出技术正是解决寄存器压力的有效方法.摆动模调度是一种在进行近似最优化调度的同时尽力减小寄存器压力的软件流水算法,该算法已经作为一个新的优化遍出现在GCC的最新版本中.本文以GCC为平台,论述了摆动模调度中的寄存器溢出技术及其工程实现,从而使摆动模调度算法进一步增强了对寄存器压力的处理能力.     

利用循环分割和循环展开避免Cache代价

存储系统与处理器之间的速度差距逐渐变大,为此,cache使用了分级机制,但这也带来了额外的存储延迟(cache代价).提出一种利用循环分割和循环展开相结合避免cache代价的PCPLPU(prevent cache penalty by loop partition-unrolling)算法.实验结果表明,PCPLPU算法能够有效避免循环代价,提高程序性能.     

软件流水中隐藏存储延迟的方法

软件流水是一种重要的指令调度技术,它通过同时执行来自不同循环体的指令来加快循环的执行速度.随着处理机运行速度的逐渐提高,存储访问延迟成为性能提高的瓶颈.为了减轻存储系统影响,软件流水结合了一些存储优化技术,通过隐藏存储延迟来提高性能.提出了一种延迟可预测的模调度算法(foresighted latencymodulo scheduling,简称FLMS),它根据循环的特点来确定load指令延迟.实验结果表明,FLMS算法减少了阻塞时间,提高了程序性能.     

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

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

SMS软件流水调度算法的设计与实现

循环是程序中的热代码,对循环进行有效的优化可以显著缩短程序的执行时间。软件流水是一种开发循环体指令级并行的细粒度循环优化技术,它通过调度循环中连续迭代之间的指令使其并行执行,从而提高了循环的执行效率。实验数据表明,用Cerngoop程序包进行测试,循环优化效果明显。     

程序的cache使用效率分析

评价程序的存储效率是提高用户程序性能的重要手段。该文首先提出了程序的装入因子的概念,并据此分析了矩阵乘法;其次,根据时间局部化原则,提出了一种“最小时间差方法”,该方法可以有效地减少cacheline的装入数目;最后,为了评价程序的存储延迟,提出了程序数据相关性的概念,据此给出了计算装入因子的公式,用于分析程序的存储效率。这样就可以用big-O模型来表达程序的时间复杂性,并用装入因子来表达程序的存储访问复杂性。     

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

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

Cache Aware Pre-Runtime Scheduling

We present a novel pre-runtime scheduling method for uniprocessors which precisely takes the effects of task switching on the processor cache into consideration. Tasks are modelled as a sequence of non preemptable segments with precedence constraints. The cache behavior of each task segment is statically determined by abstract interpretation. For the sake of efficiency, the scheduling algorithm uses a heuristically guided search strategy. Each time a new task segment is added to a partial schedule, its worst case execution time is calculated based on the cache state at the end of the preceding partial schedule.     

基于超块的统一分簇与模调度

超长指令字处理器为了提高指令集并行(ILP)往往采用多个功能单元,从而需要多端口的寄存器文件提供支持.但是寄存器文件会随着端口的增多变得更复杂,频率难以提升,成为系统的瓶颈.分簇是解决这一问题的有效手段.分簇在不影响处理器ILP的前提下减少了每簇寄存器文件的端口数目,但对编译器提出了挑战,编译器必须将指令和操作数在簇间进行合理分配才能得到较好的指令级并行.针对分簇超长指令字结构提出了一种基于超块的统一分簇与模调度编译方法.使用超块技术可以增大调度范围以获得更好的ILP,并且可以处理含有控制流的循环体,增加了模调度的适用范围.超块中指令的分簇与模调度则是统一进行的,这将比分阶段进行有更好的优化效果,因为统一进行是从全局的角度寻求优化而非寻求各个阶段局部优化.在YHFT-DSP/700编译器中的实验结果表明,与ITSS算法相比,该算法可以达到较好的优化效果.     

支持内存数据库索引缓存优化的CST树的设计与实现

针对目前内存数据库中索引缓存失配的问题,在分析了现有内存数据库索引结构基础上,提出了一种缓存敏感T树（CST树）的索引数据结构,详细数据结构描述和操作算法也已给出。通过CST树的缓存次数分析和进行查询、插入等操作性能测试,结果表明CST树能有效减少缓存敏感次数,并且在数据量较小时,CST树的插入、删除速度比T树略慢,而查询速度比T树要快。在数据量较大时,CST树的插入、删除、查询效率都比T树要高。     

一种新颖的软件可控Cache优化方法

由于Cache污染问题,传统的仅由硬件控制的Cache替换策略不能得到令人满意的Cache利用率。随着软件可控Cache机制的出现,编译器开始可以直接控制Cache替换,改善Cache行为。本文证明了一个Cache提示优化定理,并依该定理提出了一个由编译器辅助控制的Cache替换策略:最优Cache划分(OCP)。OCPCache替换策略简化了Cache行为和Cache失效分析方法。实验结果表明OCPCache替换策略能有效地降低Cache失效率。     

基于缓存竞争优化的Linux进程调度策略

分析Linux经典内核版本2.6.22的进程调度算法,利用性能监测单元的监测信息,给出3个性能指标CMR、CRR、OCIP对进程的缓存竞争性强弱进行刻画,以此为依据,采用轮询算法优化Linux下的进程调度顺序,尽量避免在CPU上同时运行多个缓存竞争力强的进程,减小系统因缓存竞争产生的性能损耗.在benchmark上的测试结果表明,该方法能够提升系统在中、高负载下运行时的性能,在高负载下运行时的性能提升比例可达6％左右.