一个新的循环分块算法

循环分块是一种提高循环Cache命中率的循环变换技术，循环分块的大小是决定循环分块效率的关键因素，CME（cache miss equations)是一种精确分析程序中循环Cache命中率的数学模型，从CME理论模型出发，通过比较循环分块前后CME的变化，结合PADDING技术可以得出一个循环分块算法。实验表明，通过该算法计算出的块大小较之经典的LRW循环分块算法，在确保完全消除循环中数且引用数据访问Cache自冲突的同时，可以获得更大的分块，从而提高了循环分块的分块效率。     

编译器优化技术之Cache分块优化技术探讨

高速缓冲存储器（Cache）是高性能计算机的重要部件。循环分块是一种提高Cache命中率的技术,循环分块的大小是决定循环分块效率的关键因素。本文解释了cache失效的原因,并分析了如何有效地减少Cache的失效率。本文在分析处理器的特点的基础上,提出了“部分Cache局部性”[1]方法,实践表明,该方法有很好的优化效果,且易于实现。     

一种面向软件管理内存层次的简易数据分块方法

考虑到硬件管理Cache 多级存储结构在功耗和面积方面的开销过大,众核处理器倾向于采用软件管理的多级存储结构,这就需要软件规划好程序的数据在各级存储上的布局和传输.尝试了一种依赖程序原有循环结构和问题规模的简易数据自动分块方法,根据循环层内的数据访存范围进行相应的分块,避免数据复杂的依赖关系分析,使得该方法易于在编译器中实现.同时可根据需要进一步结合程序变换如循环交换、循环联合和循环分裂等方法得到更佳的分块参数.实验结果表明,在大多数问题规模下与一般分块方法的优化性能相当,但在某些特定问题规模下能够获得较高的优化性能.     

CME分析中的丢番图方程求解

1.引言循环的Cache不命中率分析是编译优化中的关键技术之一。CME(Cache Miss Equation)是美国Princeton大学的S.Ghosh博士提出的循环Cache不命中率分析的计算模型,它以循环中数组引用的重用向量分析为基础,根据Cache数据映射的规则用约束条件下丢番图方程对数组引用在不同重用向量上的Cache冲突情况进行精确的描述(一般为线性约束条件),明确了方程整数解的数目与Cache不命中次数之间的关系,为较为精确地分析循环的Cache不命中率奠定了基础。我们把通过CME来分析Cache不命中率的过     

分布式RAID中Cache模块的设计

针对分布式RAID的特殊架构，设计了基于总线侦听方法的Cache模块。该模块采用主存分块映射策略来解决总线侦听方法，由于共享网络总线对带宽要求太高，使用较少带宽、较少的数据操作，提高了分布式RAID的系统性能。对Cache模块设计进行了性能分析，对多处理机系统Cache一致性问题的解决方案进行了分析比较。     

面向WCET估计的Cache分析研究综述

实时系统时间分析的首要任务是估计程序的最坏情况执行时间(worst-case execution time,简称WCET).程序的WCET 通常受到硬件体系结构的影响,Cache则是其中最为突出的因素之一.对面向WCET计算的Cache分析研究进行了综述,介绍了经典Cache分析框架与Cache分析核心技术,并从循环结构分析、数据Cache分析、多级Cache分析、多核共享Cache分析、非LRU替换策略分析等角度介绍了Cache分析在不同维度上的研究问题与主要挑战,总结了现有技术的优缺点,展望了Cache分析研究的未来发展方向.     

指令Cache的替换策略

本文用理论分析和程序模拟的方法分析了指令Cache的替换策略和组织,用程序的循环模式研究了Cache的替换策略和组织,得出随机替换策略优于LRU和FIFO策略,在一定条件下,直接相联和组相联优于全相联映象算法,分析指令踪迹模拟结果表明,循环模式是Cache行为的较好的解释。     

一种面向多核处理器粗粒度的应用级Cache划分方法

Cache划分技术是解决共享Cache访问冲突的重要方法,但是已有的Cache划分技术具有开销高、Cache划分时机难以确定的缺点。本文提出了面向应用的Cache划分框架(ACP)。ACP的优点是能够使用程序员提供的应用最外层循环的边界信息,更好地获取应用的失效率信息,因此Cache划分算法具有更高的精度,从而降低了划分的频率,进而提高系统性能。实验结果表明,和传统的固定周期的Cache划分方向相比,ACP具有更好的性能。     

嵌入式处理器的Cache结构研究

针对嵌入式处理嚣结构的特点，探讨虚拟Cache的结构、性能及实施方法等进行，讨论了Cache的锁定来改进Cache的循环淘汰置换算法的可行性，并对基于ARM架构的嵌入式处理器的Cache结构特点作了介绍。     

面向局部性和并行优化的循环分块技术

循环分块是一种广泛用于改善数据局部性和开发并行性的程序变换优化技术.主要分为2类:固定分块技术和参数化分块技术,系统地总结了这2类技术,并分析了其优缺点.由于分块大小的选择会严重影响分块代码的性能,因此介绍分析了选择最优分块大小的各种方法.此外,总结了循环分块在多级分块、并行性开发和不完美嵌套循环等方面应用的各项技术.通过对循环分块技术当前研究现状的分析,得出如下结论:1)循环分块技术中的计算复杂度和生成代码效率问题还未得到完全解决,如何利用循环边界有效地约束迭代空间并提高数据局部性还需要更深入的研究;2)最优分块大小的选择依然是一个开放式难题,研究清楚分级存储架构中每级分块对性能的影响具有重要的意义;3)从循环分块的应用角度,如何有效地构建面向任意嵌套循环集的自动分块代码生成系统,同时充分利用深度共享存储资源和多核架构实现分块代码的高并行度,也是一个需要深入研究的问题.     

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

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

基于神经网络模型的stencil循环最优分块大小预测

stencil循环是科学与工程计算应用中最主要的计算核心之一。循环分块技术可有效改善stencil循环的数据局部性,提高计算并行度。分块的大小选择对stencil循环的性能影响很大,传统的分块大小选择方法通常在时间开销、人工成本、分块选择精度等方面存在短板,实用性较差。文中提出了一种基于人工神经网络的分块大小选择方法,用于预测三维Jacobi型stencil循环程序的最优分块。对来源于实际数值模拟软件中的11个stencil循环进行最优分块预测,实验结果显示,在单核串行和多核并行两种场景下,程序使用模型预测分块相比不分块的性能提升分别为2%和35%,与网格搜索方法的分块性能相当,但在线预测时间开销仅约为后者的1/30 000。此外,相比基于静态分析的Turbo-tiling方法,预测最优分块的实测性能平均提升了约9%。     

向量化友好的循环分块因子选择算法

具有病态规模的嵌套循环程序在进行循环分块时容易忽略分块因子对向量化的影响,导致非对齐数据访问,降低分块后循环代码的性能。提出了一种向量化友好的循环分块因子选择算法VEC-TSS。该算法对可向量化循环层以向量化收益分析确定分块因子,对其他循环层通过以局部性收益和并行粒度确定分块因子。实验结果表明,针对具有病态规模的循环程序,VEC-TSS算法与另外两种分块因子选择算法相比可以获得更好的程序加速比,同时具有良好的可扩展性。     

基于纹理数组的大规模地形绘制算法

将Shader Model 4.0引入的纹理数组技术同顶点纹理拾取技术、瓦片块四叉树算法和地形分块技术等相结合,提出了一种基于GPU的大规模地形绘制方法。将整个大规模地形数据分割成地形块,按照金字塔模型保存在CPU内存里,将地形中潜在的可见部分以纹理数组形式驻留在GPU Cache里;在CPU上发送瓦片块四叉树平面网格,利用存储在GPU Cache里的高程值生成相应的地形;GPU Cache随着视点运动而连续更新。实验证明该方法充分利用了现代GPU的特性,适合于大规模地形的漫游。     

嵌入式移动数据库客户端列Cache方案研究

在嵌入式环境中，有效利用客户机端Cache的空间，可以大大降低系统功耗和提高系统的性能。从体系结构级的角度，介绍了一种适应数据广播环境的移动数据库客户机端Cache管理方案——列Cache，并探讨了一种改进的替换和预取策略——带锁的循环淘汰PIX算法，分析了其可行性，试验证明了这种方案的有效性。     

嵌入式应用中加速图像投影变换的Cache包围盒方法

本文提出Cache包围盒方法,用于提高嵌入式应用中图像投影变换的速度。该方法首先对目标图像分块,分别计算各块目标图像在原始图像上对应的像素点集合,进而找到能包围这些像素点的最小矩形包围盒(称为Cache包围盒)。然后,在投影变换时,通过直接存储器访问(DMA)方式依次将目标图像块及其在原始图像上的Cache包围盒图像块放入快速片内存储器中,避免直接从慢速的片外存储器读写图像数据,以提高投影变换速度。实验表明,采用Cache包围盒方法比不采用该方法可提高三倍的图像投影变换速度。Cache包围盒方法的思想同样适用于其他嵌入式应用中对非线性、不连续地址但又具有较好曲线相邻特性的大数据量读写场合,具有良好的可推广性。     

分块K

本文讨论了分块K-循环Toeplitz系统,导出分块K-循环Toeplitz矩阵求逆的一种快速付氏变换算法,其算法复杂性为O(mnlog2 mn).     

片上多核Cache资源管理机制研究

随着片上多核成为处理器发展的主流和片上Cache资源的持续增长,Cache资源的管理已成为片上多核的关键问题。介绍了片上多核Cache资源管理的研究进展,依据研究内容将Cache资源的管理分为Cache划分和Cache共享两类。对Cache划分,探讨了其主要组成部分和一般形式,分析和比较了典型的片上多核Cache划分机制。对Cache共享,给出了其主要研究内容,并介绍和比较了几种主流的片上多核Cache共享机制。通过分析,认为软硬件协同管理的页划分应是未来片上多核Cache划分机制的研究重点;而片上多核Cache共享机制的研究则应从目标应用的Cache行为特征着手。     

面向规则DOACROSS循环的流水并行代码自动生成

发掘DOACROSS 循环中蕴含的并行性,选择合适的策略将其并行执行,对提升程序的并行性能非常重要.流水并行方式是规则DOACROSS 循环并行的重要方式.自动生成性能良好的流水并行代码是一项困难的工作,并行编译器对程序自动并行时常常对DOACROSS 循环作保守处理,损失了DOACROSS 循环包含的并行性,限制了程序的并行性能.针对上述问题,设计了一种选择计算划分循环层和循环分块层的启发式算法,给出了一个基于流水并行代价模型的循环分块大小计算公式,并使用计数信号量进行并行线程之间的同步,实现了基于OpenMP 的规则DOACROSS 循环流水并行代码的自动生成.通过对有限差分松弛法（finite difference relaxation,简称FDR）的波前（wavefront）循环和时域有限差分法（finite difference time domain,简称FDTD）中典型循环以及程序Poisson,LU 和Jacobi 的测试,算法自动生成的流水并行代码能够在多核处理器上获得明显的性能提升,使用的流水分块大小计算公式能够较为精确地计算出循环流水并行时的最佳分块大小.自动生成的流水并行代码与基于手工选择的最优分块大小的流水并行代码相比,加速比达到手工选择加速比的89%.     

一个由编译器控制的Cache替换策略

由于Cache拓染问题,传统的仅由硬件控制的Cache替换箫略不能得到令人满意的Cache利用率。为解决该问题,EPIC引入了Cache提示以辅助控制Cache替换。文章提出了一个由编译器辅助挖制的Cache替换策略：最优Cache划分（OCP）。OCP Cache替换策略简化了Cache行为和Cache失效分析方法。实验结果表明,OCP Cache替换箫略能有效地降低Cache失效率。