多核环境下高效集合通信关键技术研究

随着高性能计算需求的日益增长,多核处理器在高性能计算中间得到了广泛的普及.为了保证高性能计算机系统的效率,需要保持计算和通信的平衡性,多核的广泛使用对通信系统的效率提出了更高的要求.集合通信作为通信系统中的重要组成部分,研究多核环境下的高效集合通信具有十分重要的意义.文中首先研究了多核对集合通信性能的影响,并根据多核处理器共享Cache以及内存竞争的特点,提出了层次化算法、限制并发、NUMA感知的优化方法和Cache友好的优化算法,并分别在MPI_Barrier、MPI_Bcast和MPI_Alltoall中进行了验证.实验结果表明优化方法能够有效地利用多核结构特点,降低竞争带来的影响,提高了多核环境下集合通信的性能和可扩展性.     

一种面向多核系统的并行计算任务分配方法

随着多核处理器的普及,目前的大规模并行处理系统普遍采用多核处理器,这对于资源管理和调度提出了更高的要求.提出了基于共享Cache资源划分的方法,建立了面向多核处理器支持Cache资源分配的进程调度模型,设计并实现了并行任务到多核处理器的映射算法,更好地解决了大规模资源管理系统中面向多核处理器的任务分配问题,降低了使用共享Cache的多个进程运行时的相互干扰,提升了应用程序性能.     

多核处理器Cache一致性协议关键技术研究

多核处理器规模的不断扩大和核间通信机制的日益复杂,使得Cache一致性维护变得更加困难。本文从多核处理器Cache一致性问题的产生背景出发,分析监听协议、目录协议、Token协议和Hammer协议的实现机制以及在多核环境中的优缺点,分别从一致性协议与片上互连结构协同设计、面向低功耗应用的协议优化策略、Cache一致性协议验证及容错机制等角度考虑,对未来多核处理器Cache一致性协议设计的发展趋势和技术挑战进行详细分析与讨论。     

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

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

面向低功耗的多核处理器Cache设计方法

针对多核处理器下的共享二级缓存(L2 Cache)提出了一种面向低功耗的Cache设计方案(LPD)。在LPD方案中,分别通过低功耗的共享Cache混合划分算法(LPHP)、可重构Cache算法(CRA)和基于Cache划分的路预测算法(WPP-L2)来达到降低Cache功耗的目的,同时保证系统的性能良好。在LPHP和CRA中,程序运行时动态地关闭Cache中空闲的Cache列,节省了对空闲列的访问功耗。在WPP-L2中,利用路预测技术在Cache访问前给出预测路信息,预测命中时则可用最短的访问延时和最少的访问功耗完成Cache访问;预测失效时,则结合Cache划分策略,降低由路预测失效导致的额外功耗开销。通过SPEC2000测试程序验证,与传统使用最近最少使用(LRU)替换策略的共享L2 Cache相比,本方案提出的三种算法虽然对程序执行时间稍有影响,但分别节省了20.5%、17%和64.6%的平均L2 Cache访问功耗,甚至还提高了系统吞吐率。实验表明,所提方法在保持系统性能的同时可以显著降低多核处理器的功耗。     

多核处理器中基于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伪共享问题,最后针对问题给出相应的解决方案,并以具体的实例验证了解决方案的可行性。     

基于多核的多线程程序优化研究

随着主流芯片厂商的大力推广,多核处理器已经变得越来越普及.以往串行化的程序设计方法在多核环境下已经不能充分利用多核CPU的资源.怎样高效地利用多核处理器的计算性能,已经成为软件开发者面临的新的课题.文中在传统的多线程编程基础上,根据Intel处理器的微架构(Microarchitecture)特点,以及Linux内核提供的CPU绑定技术,通过采用Cache优化和CPU亲和力(CPU affinity)优化,消除了多核环境下局部多线程Cache行竞争和伪共享,减少了线程的调度开销,提高了多线程程序的运行效率.     

面向多核处理器的共享Cache冲突预测模型

多核处理器的出现给实时系统的设计带来了新挑战,如并发任务通过共享Cache相互干扰的现象严重降低了实时系统的实时性,已有的Cache冲突评价模型没有针对多核处理器体系结构,多角度评价共享Cache对多个并发任务的影响.本文基于广泛应用的LRU Cache替换策略,根据任务的Cache静态复用距离,提出一种可以预测并发任务的Cache占用率、失效率和任务间冲突概率的Cache冲突预测模型.分析了在多核背景下共享Cache结构对实时性的影响.实验结果表明本模型不但功能比现有模型全面且精度更高.     

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

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

基于缓存估算模型的代码测试系统性能优化方法

为了解决代码测试系统测试C项目的时间开销较大这一问题,本文提出了一种基于缓存估算模型的性能优化方法。该方法向代码测试系统中引入了缓存技术,并且建立了缓存规模估算模型。不相似的C项目应用该模型计算出的缓存规模是不一样的。使用缓存规模估算模型后,代码测试系统文件缓存的规模能够随着C项目的改变而发生改变,具有动态变化的能力。缓存估算模型已在系统中实现,对4个开源C项目的测试结果表明：该优化方法能有效地提高代码测试系统测试C项目时的时间性能。     

H.264在ADSP-BF561上的实现与优化

研究了H.264编码关键技术的实现,并结合ADSP-BF561的特点提出了有效的优化方案,包括帧内帧间快速算法、存储空间分配、Cache应用、C和汇编语言优化等。测试结果表明,优化后的算法编码效率得到显著提高。     

图像灰度匹配在多核环境下的优化

随着计算机技术的不断发展,图像匹配已经成为图片处理的一个重要部分。在图像匹配中,图像的灰度匹配虽然具有匹配精度高的优点但却需要大量的计算时间,且计算时间随着使用模版的增大而大幅度增长。文章在多核的环境下使用内存优化与处理器亲和力优化方法来解决计算时间长的问题。实验结果表明,使用并行技术并结合内存优化与处理器优化方法可大幅度减少计算时间、提高缓存的命中率、避免乒乓效应的产生使并行程序的加速比与并行效率有所提高。     

代码Cache分组管理策略研究

代码Cache是动态优化系统的重要组成部分,利用代码Cache可以实现翻译代码的复用,利用软件管理代码Cache存储优化和代码翻译.代码Cache存储大小不等的超级块,超级块之间可能包含指向其它超级块的链接指针,因而会带来较高的替换开销.提出采用分组管理代码Cache的策略,该策略能够有效的平衡Cache管理的复杂性和Cache的失效率.     

DSPs实时视频处理中的Cache优化算法研究

在采用并行超长指令字结构的DSP芯片中，CPU处理速度与片外数据存取速度不匹配的问题，导致了CPU处理延时，限制了DSP系统性能的提升，针对这一问题，根据Cache的结构提出一种适宜于在DSPCPU上进行视频数据处理的数据排列新算法，并且将其成功地应用到基于Trimedia PNXl301的MPEG-4程序优化工作中，系统编码结果表明，该方法有效地减少了Cachemiss及片外数据存取的时间开销，在同等条件下，采用本算法后系统编码性能提高2帧／秒(CIF格式)左右。     

基于动态Cache策略优化Snort检测引擎性能研究

提出了一种动态Cache策略,将最近一段时间内经常用到的少量规则结点指针存储在一个Cache块中.当攻击密度上升到一定阈值时,在Snort检测引擎中动态加载Cache块,接下来捕获的每一个数据包都首先和Cache块中存储的指针所指向的规则结点进行匹配.当网络攻击密度降低到一定阈值时,在Snort检测引擎中动态卸载Cache块,避免攻击密度较低时二次匹配带来的额外开销.实验表明,动态Cache策略可以提高Snort检测引擎在高强度攻击下的检测效率,降低漏报率.     

循环Cache命中率分析方法的研究与实现

循环Cache命中率的分析是编译优化中的关键技术之一。CME(CacheMissEquation)作为描述一个精确描述程序循环中数组引用的Cache冲突情况的数学模型及其相关的理论为较精确地分析循环的Cache命中率奠定了理论基础。该文以CME理论为基础,从数理统计的角度对CME抽样分析作了理论上的说明,采用序贯抽样方法来进行CME的抽样分析,并对抽样检验过程中判断线性约束条件下丢番图方程是否存在整数解这一NP问题,结合一些整数计算的理论,给出了格测试的快速算法。     

WWW缓冲挖掘中基于粗糙集的用户模糊兴趣建模

如何有效充分地利用WWW缓冲中的信息,其关键是建立一个合适的用户兴趣模型和构造合适的兴趣挖掘算法。用户的兴趣是一个相对模糊的概念,简单兴趣模型通过（词条,权重）来刻画兴趣,但是它的表示粒度太小,不能贴切地描述用户的兴趣。文中在充分分析WWW缓冲模型的基础上提出了基于粗糙集的用户模糊兴趣概念。利用该方法可以对WWW缓冲中的网页文档和文档集合进行统一建模,这为利用用户历史兴趣信息和进行兴趣匹配提供了便利。     

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

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

基于指令Cache和寄存器压力的循环展开优化

循环展开是一种常用的编译优化技术,能够有效减少循环开销,提升指令级并行程度和数据局部性,提升循环的执行效能。然而,过度的循环展开会造成指令Cache溢出,增大寄存器压力,循环展开次数太少又会浪费潜在的性能提升机会,因此寻找恰当的展开因子是研究循环展开问题的核心。基于GCC开源编译器,面向循环展开问题开展深入的分析与研究,针对指令Cache和寄存器资源对循环展开的影响,提出了一种基于指令Cache和寄存器压力的循环展开因子计算方法,并在GCC编译器中实现了该计算方法。申威和海光平台上的实验结果显示,相较于目前GCC中存在的其它展开因子计算方法,所提出的方法可以获得更为有效的循环展开因子,提升了程序性能。在SPEC CPU 2006测试集上的平均性能分别提升了2.7%和3.1%,在NPB-3.3.1测试集上的分别为5.4%和6.1%。