摘要：为实现局部性强弱分析的定量化,分析了进程工作集发生迁移时,现有工作集管理算法因未考虑局部性强弱因素而反复调整驻留集大小从而导致系统发生颠簸的现象,提出了采用采样周期内使用位求和结果和缺页次数作为指标的局部性强弱量化计算方法,并对该方法进行了算法设计和系统实施.结果表明,文中量化计算方法在不影响系统性能的情况下,减轻了系统进程切换时各进程工作集大小的波动,降低了系统资源需求,说明该算法是有效的.

摘要：当前的互联网流量模型正迅速从端到端通信发展为内容的传播共享.为了适应这种变化,学术界提出了内容中心网络(CCN)的未来网络架构.在内容中心网络中,终端主机根据内容的名字而不是内容所在主机的IP地址进行通信.内容路由器作为底层基础设施,承载着内容请求和内容响应的高速交换的任务.不同于IP路由器的无状态转发模型,内容路由器的数据平面因具备网络缓存功能而更加复杂.尽管网络缓存可以有效减轻网络拥塞,但这样的设计也将额外的状态附加到网络中间节点上,这在一定程度上破坏了网络设计中的"端到端"原则.这些额外状态给路由器的数据平面造成了性能负担,也使内容路由器数据包转发成为当下热门的研究课题.内容路由器包含转发信息库(FIB)、待定兴趣表(PIT)和内容缓存(CS)三个模块.针对基于名字的最长前缀匹配、名字路由表的状态爆炸、待定兴趣表的频繁更新等问题,目前大量研究工作围绕FIB和PIT开展性能优化.然而,尽管CS也存在潜在的性能问题,却较少有工作对其进行讨论.FIB、PIT和CS在内容路由器中以流水线的形式存在,而流水线的处理速度由最慢的流水段决定.因此,为了提高内容路由器的整体性能,有必要首先确定其性能瓶颈,然后进行针对性的优化.在该文中,为了避免盲目的性能优化,我们首先建立了基于开放排队网络的数学模型.通过定量分析,文章发现CS是整个路由器的性能瓶颈.目前,已有工作采用跳表作为CS的数据结构.然而由于其O(logn)的查找复杂度,经典跳表在处理高速网络流量时依然存在性能问题.受到网络流量中广泛存在的时间局部性和空间局部性的启发,我们提出了局部性原理跳表来提升CS的性能.在新的设计中,考虑到新到达的内容请求可能与之前到达的内容请求共享相同的名字前缀,且所请求的内容块通常处于邻近的存储空间,因此在查找跳表时可以直接从该前缀先前命中的跳表结点附近开始查找.这样可以避免每次都从跳表的头结点开始重复的查找,从而节省大量时间.实验结果表明,局部性原理跳表可以在x86处理器上实现1.796Mpps的单线程吞吐率,这是经典跳表查找速度的三倍.对于500B大小的数据包包长来说,CS的单线程吞吐率可以高达7.016Gbps.

摘要：已有的LRFU(Least Recency Frequency Used)自适应算法在实际应用中根据经验调整λ值,缺乏对访问局部性强弱的量化分析,因而其可适用的访问模式有限.该文首先建立基于K阶马尔可夫链(K→∞)的局部性定量分析模型,在访问过程中根据统计信息实时量化局部性特征.然后以此分析模型为基础设计自适应替换算法LA-LRFU(Locality-Aware LRFU),随着访问特征的变化动态调整参数λ.最后应用Trace仿真对算法进行测试.实验结果显示,针对多种访问模式,LA-LRFU均可显著提高Cache命中率;在由多种访问模式构成的具体访问过程中,LA-LRFU能比现有的各类LRFU自适应算法更合理地调整参数λ.

摘要：掌握Web网页信息变化的时间规律可以更有针对性的指导搜索引擎等Web应用系统更有效地进行搜集.本文旨在研究中国范围内Web网页变化的时间规律,针对网页变化的频率和间隔两项指标,随机选取数百万网页作为样本,设计试验在一个月内对上述两项指标进行考察.从结论中,我们发现网页变化的若干规律,并发现其中可能存在时间局部性规律.因此,我们引入了堆栈距离模型,在针对Web网页的变化特性和具体实验方法对其修正之后,再次设计实验对网页变化的时间局部性规律进行考察.结果表明,网页的变化存在明显的时间局部性.最后,介绍了这种时间局部性规律在网页搜集中的实际应用.

摘要：大规模并行应用程序的性能优化和并行化的关键瓶颈之一在于多核CPU中越来越深和越来越复杂的存储层次。文中系统地分析和总结了当前主要多核CPU和并行程序设计语言中的局部性设计方法,提出了两种局部性,即横向局部性和纵向局部性,从这两种局部性的视角深入分析了当前的主要并行程序设计语言的局部性设计机制,进一步总结对比了其优缺点,并指出了新一代并行程序设计语言应具有的特点,重点提出了新语言应同时综合考虑两种局部性支持的设计机制的研究观点。

摘要：简单介绍了Cache存储系统的工作原理以及它在提高系统性能方面的作用;由此引出了Cache存储系统设计的理论基础—访问局部性原理,并进一步讨论了访问局部性的强弱对Cache存储系统中的命中率以及存取有效性的影响。

摘要：网络访问流的局部性特征包括时间局部性和空间局部性,利用数学建模方法研究局部性特征对于缓存和预取系统的设计及性能提高具有重要的作用。通过分析和讨论,利用信息熵和变异系数建立了网络流量局部性特征新的度量方法,信息熵比Zipf定律更能反映访问流的时间局部性,变异系数则解决了访问流的相同文档间的空间局部性建模问题。实验和分析表明,这些参数能较好地描述网络访问流的局部性特征且易于使用。

摘要：在高速缓存参数无关的算法与数据结构的设计中,使用了许多技术,这些技术都是利用教据的时间和空间局部性,有效地使用计算机多级存储结构,进而提高算法与数据结构的效率。文中对若干利用局部性原理的高速缓存参数无关技术进行分析和总结。

摘要：讨论了访问局部性原理在Cache存储系统中的体系结构设计和优化策略中的应用.

摘要：近年来,基于调色板的图像重着色技术在图形设计、照片编辑和广告制作等领域广受关注并得到应用,还出现了一系列优化调色板提取和图像重着色效果的方法。但由于现有技术的编辑局部性,用户在调整局部区域时常常导致图像整体色调发生不可预知的变化。为此,提出了一种新颖的基于移动最小二乘的图像重着色算法,显著提升了颜色编辑的局部性和精准度。首先,采用改进的K-means聚类算法提取输入图像的调色板。然后,将图像及其调色板映射至RGB颜色空间,并将其视作三维点云和控制点。最后,将基于调色板的图像重着色任务转化为经典的点云变形问题。通过编辑调色板颜色精确控制图像的颜色变化,并借助移动最小二乘算法优秀的局部性实现局部控制。算法允许用户通过简单编辑,实时生成自然的、满足用户编辑意图的重着色结果。实验和用户调研结果表明,相较于已有算法,本文算法能得到更加自然、更符合用户预期的图像重着色效果。