程序局部性的量化分析

给出与平台无关的局部性量化方法,从空间局部性和时间局部性2个角度,量化SPEC2000测试基准程序,以及这些程序的数据段、代码段和堆栈段。时间和空间局部性组成的二维局部性分布直观地展示了基准测试程序的局部性。实验结果表明,程序数据局部性主要由堆段的局部性决定,堆段的局部性最差,栈的局部性最优。     

基于线性表出的非奇异循环变换局部性优化方法

开发程序的局部性是当今并行编译优化研究的重点之一,而程序变换是开发程序时间局部性和空间局部性的重要手段之一．该文提出了一种新的利用非奇异循环变换来优化程序局部性的局部性优化方法,即基于线性表出的循环变换．该方法利用一组最少的线性无关向量组来线性表出数组访问的下标表达式,并据此构造非奇异变换矩阵来优化数组访问的时间局部性和空间局部性．该方法能充分开发数组访问的时间局部性,能简便地确定是否能对数组访问进行时间局部性或空间局部性优化,并能对给定的嵌套循环同时进行时间局部性和空间局部性优化．实验结果表明了该文所提出的基于线性表出的非奇异循环变换局部性优化方法是有效的．     

基于局部性分析数据预取在GCC上的实现

微处理器与DRAM之间速度差异越来越大,系统优化需要更多积极有效的方法来减少或隐藏访存延迟.数据预取是隐藏访存延迟的一种有效方法,本文在GCC编译器上实现了一种基于精确局部性分析的数据预取优化算法.对spec2000和NPB2.3的测试结果显示,实施了该优化的GCC平均性能比原来提高了9%.     

基于数据流分析的工作流模型局部性研究

由于模型化简的方法存在着通用性的限制,工作流模型中控制流和数据流相结合的冲突检测通常要在整个模型范围内进行,模型维护的复杂性高。首先通过分析工作流模型中存在的时序依赖和数据依赖关系,以及二者应该满足的一致性,揭示出工作流模型的拓扑结构中存在着局部性。基于工作流模型的局部性原理提出活动的稳定子图,以及工作流模型重构后的局部区域求解方法,并对方法给予证明。最后的对比分析表明,工作流模型的拓扑结构发生变化时,控制流和数据流的一致性完全可以在局部范围内验证和维护,进而提高了模型维护的效率。     

基于局部性和分区磁盘的文件定位优化

计算机虚拟存储体系结构中磁盘文件访问存在局部性,大量访问集中在少数文件上。针对该问题,研究分区盘技术,提出一种动态文件定位优化方法,通过动态采样统计,将访问次数集中的文件定位在使用分区盘技术且数据传输率较高的磁盘区域中。理论分析及实验结果表明,该方法可以提高系统整体的I/O性能。     

FORALL实现过程中的局部性优化

FORALL结构是FORTRAN 95的一种语法,在编译器中高效地实现FORALL结构是一项富有挑战性的工作,局部性优化对其高效实现尤其重要。本文介绍作者在G95编译器中实现FOR ALL结构时用到的两种局部性优化方法--临时空间合并和嵌套循环排序。实验结果表明,局部性优化对提高FORALL结构的性能非常有效。对某类FORALL结构,与Intel的EFC 编译器相比,我们的实现方法能提高30％的性能。     

基于投影分层技术的嵌套循环空间局部性优化方法

从数据访问轨迹入手,探讨了利用数据变换来改善数据访问局部性的本质,提出了一种新的优化数据访问的投影分层技术以及基于它的数据变换框架．该框架主要利用投影技术来优化数据访问的空间局部性,并同时利用数据分层技术来解决因投影而带来的数据重叠问题．该数据变换框架不仅能处理仿射数组下标,而且还能处理许多非仿射的更复杂的数组下标,同时它还能简单直接地确定数据元素的最优存储布局以及优化数据访问的数据变换短阵,并能使访问间距尽量小．实验结果表明它是有效的．     

基于横向局部性的多核计算模型

片内多核已成为延长摩尔定律的方式,并行算法设计、编程模型、编译器和运行时系统都需要利用计算模型进行分析。现有多核模型对线程间共享缓存等资源的竞争已有较精确的模型,但是对于线程间数据共享考虑较少。提出线程间共享缓存的横向局部性和任务共享率概念,基于此扩展串行存储层次模型RAM(h),提出考虑任务共享率的多核并行计算模型MRAM(h)。     

面向MPF的自动并行过程中的迭代划分和数组访问局部性分析

并行编程一般分为数据并行和消息传递两种模式。比较而言,消息传递的应用更为广泛。面向消息传递FORTRAN（MPF）的自动并行工具能很大程度上缓减用户编程的压力,并具有很好的实用价值。迭代划分和局部性分析是自动并行中的重要部分。本文介绍从串行FORTRAN程序自动转换成MPF的自动并行工具FAX中的迭代划分、数组访问局部性分析及通信优化分析。     

基于网络数据流局部性的连接管理优化方法

根据高速网络环境下连接管理的性能需求,提出一种连接管理优化方法,即将MTF启发法应用于连接表。网络数据流的局部性特点表现为,属于同一个连接的一组数据包可能在短时间内集中到达。基于此,应用MTF启发法优化连接表的查找操作,形成MTF连接表。给出优化后的连接管理算法流程。借助实际高速网络数据流,对MTF连接表优化方法进行性能评估。实验结果表明,MTF连接表的查找性能明显优于传统的排序连接表。     

流处理器结构上数据并行类应用的开发和评估

流处理器体系结构是一种针对流应用中固有的计算和数据流动特点提出的一种新型的处理器体系结构,它结合了向量和超长指令字体系结构的特点,能有效地加速流应用的执行,而它的适用领域一直是当前国际上的热点讨论问题.本文从数据并行应用4个不同领域--数字信号处理、科学计算、网络和安全、以及多媒体处理选取了4个典型应用,详细剖析了这些应用在流体系结构上的流并行程序设计过程,归纳出数据并行类应用的流化步骤和方法,通过实验对这类应用在流体系结构上的适用性做出评估.     

基于时序结构图的视频流描述方法

通过对视频流的分解可以获得基于关键帧集的视频流表示,但这种表示方法不能反映出视频流中隐藏的故事发展关系,为揭示这种关系,提出了一种视频流的快速聚类算法,用于对视频流分解单元进行相关性分析,该算法通过检测视频镜头间的相似性和连续性,实现把来自同一摄像机的视频镜头归并入同一视频类,并帱此得到而且为矿山频流的快速浏览和检索提供了新的思路。     

基于混沌序列的多峰函数微粒群寻优算法

基于混沌序列的多峰函数微粒群寻优算法的目标就是找到多峰函数的所有局部优化峰值。在分析微粒群优化算法中各个参数对微粒运动影响的基础上,对微粒群算法进行改造,让微粒运动从初始位置沿优化函数曲线向优化峰值方向爬行,直至找到所在区域的局部优化峰值;要想求得尽可能多的局部优化峰值,就要求微粒群中微粒的初始位置分布具有随机性和遍历性,为此采用混沌序列设置微粒初始位置;为使每一个局部最优值点都可能有微粒群中的微粒经过,采用变步长的迭代计算;为防止优化函数曲线的某些局部峰附近没有微粒分布,从而漏掉该局部峰值,对计算进行重复,直至两轮求得的优化函数的局部峰值之差小于给定阈值。仿真结果表明,该算法具有很好的局部寻优特性,计算过程简捷,寻优效果良好,可有效地应用于多峰函数的局部寻优并求取全局最优值。     

基于蚁群算法的产品拆卸序列规划方法

拆卸是回收的前提,为了得到最大的回收效益,对拆卸序列进行规划,得到最优的拆卸序列.根据拆卸的特点构建适合计算和优化的产品拆卸混合图模型,该模型描述了零部件之间的连接关系和优先关系.然后通过几何推理方法产生所有可行的拆卸序列,建立目标函数并构建适合拆卸序列规划的蚁群算法:设计了满足连接关系和优先关系的可拆卸零件搜索空间,得到最优或接近最优的拆卸序列.最后通过实例验证了该方法的实用性和可行性.     

一种基于重用距离预测与流检测的高速缓存替换算法

传统的缓存替换算法由于不能适应应用程序的流式访问行为而导致缓存性能不佳.设计基于周期检测的预测方法,分析程序访存重用距离的规律性和流式访问的复杂性,提出用重用距离预测能同时适应简单流和复杂流访问模式的RDP算法.RDP的基本思想是预测重用距离并动态维护重用距离计数,动态调整缓存数据的替换顺序,通过流采样缩减存储开销.实验结果表明,RDP算法能够很好地适应程序中多样化的流访问模式,其总体性能优于LRU算法和DIP算法,在32MB缓存上比传统LRU算法平均减少了27.5%的缓存缺失.     

面向X10的数据流程序编译优化算法

数据流编程作为一种编程模式已被广泛应用到各个领域.然而,多核体系结构的不同使得数据流程序在不同平台上移植困难.X10作为一种新型并行编程语言,为不同的多核体系结构提供了统一的并行计算环境.如何利用X10语言的特性来提高数据流程序的效率已成为目前研究工作的一大难点.本文设计并实现了一个面向X10的编译优化系统,该系统确立了三种优化算法:针对X10语言的代码生成优化减少了生成的X10代码量;针对同步数据流图的任务划分优化在负载均衡的基础上,避免了死锁的产生,同时减少了通信开销;针对底层硬件资源的通信优化在机器间通信、机器内部线程间通信、线程内部通信方面进行了区分和优化,减少了通信开销.实验结果表明,设计的三种编译优化算法都获得了较大的性能提升.     

基于隐马尔可夫模型和免疫粒子群优化的多序列比对算法

序列的多重比对是生物序列分析研究中的一个重要内容．基于免疫系统的疫苗接种和受体编辑模型,结合粒子群优化方法提出了一种免疫粒子群优化算法,将该算法用于隐马尔可夫模型的学习过程,进而构建了一种基于隐马尔可夫模型和免疫粒子群优化的多序列比对算法,从BAliBASE比对数据库中选取了一些比对例子进行了模拟计算,并与Baum-Welch算法进行了比较．结果表明,所提出的方法不仅提高了比对的准确程度,而且缩减了比对所花费的时间。     

基于混沌序列的自适应进化规划算法

针对进化规划在进化搜索过程中存在较多非法个体这一问题,提出一种新的自适应进化规划算法.该算法根据混沌序列的特性,将混沌序列引入到进化规划的变异算子中.理论分析和实验表明,与基于Guassian变异的进化规划相比,该算法不仅具有良好的快速收敛性和鲁棒性,而且能够有效地消除非法解,计算简单、容易实现.     

基于蚁群优化算法的目标拆卸序列规划

为了能够以较高的效率求解出产品中目标零件的拆卸方案,基于产品中零件间的拆卸优先约束关系,提出并建立目标零件的拆卸层次信息图模型,将目标零件的拆卸序列规划问题转化为对该图模型中具备最优值的路径的搜索和寻优问题.同时,提出一种改进蚁群优化算法,以实现对目标零件拆卸层次信息图的构建和对拆卸方案的搜索与寻优.最后通过实例验证了该方法的可行性和计算效率.