面向非规则数据的差别预取策略.docxVIP

面向非规则数据的差别预取策略 1 基于访存流模型的数据预取技术 由于处理器和存储设备之间的速度差，存储墙问题一直是制约处理器性能的重要因素。由于存储墙问题的存在，cpu的操作能力由于等待内存数据而浪费，因此现代计算机系统中强大的处理器性能难以充分利用。 数据预取技术是解决存储墙问题的重要研究领域之一.基于访存流模型的数据预取技术作为传统数据预取技术的扩展方案,是隐藏非规则数据访存延迟的常用实现方案.当前国内外基于访存流模型的数据预取技术的研究才刚刚起步,还存在很多不足之处:对存储空间划分区域后再构造时空局部性模型,容易把访存地址规律而间距大的访存行为划分为很多不同的访存区域,增加了模式及其识别的复杂度;对导致Cache访问失效的指令等同看待,只是部分地重构了访存流;对程序的所有Cache访问失效数据进行分析,一方面浪费了空间资源,另一方面有些随机的Cache访问失效会对主要关注数据造成不必要的干扰.因此,如何根据非规则计算的特性,基于访存流构建面向复杂数据结构的通用的、高效的预取模型,是本文研究的重点. 2 程序对地址序列的访问具有非连续局部性 高速缓存Cache和数据预取技术之所以起到隐藏访存延迟的作用是因为程序运行时对存储器数据的访问具有局部性特征,局部用到的数据存放在缓存中,提高了缓存命中率. 定义1 时间局部性(Temporal Locality).指程序在运行时刚刚被访问过的数据很快又被访问到.当程序需要访问的数据不在Cache中时,就把相应的内容从内存取到Cache行中,这样在下一次访问它时就不会发生缓存失效了. 定义2 空间局部性(Spatial Locality).指在访问内存中一块数据后的极短时间段内,内存中与其邻接的一块内容也会被访问到.如果在访问内存中的一个数据块时,顺带把与其邻接的数据块也取到Cache中,这样在不久访问邻接数据块时就不会发生缓存失效了. 定义3 连续局部性(Continuous Locality).时间局部性和空间局部性都是指运行程序在极短时间段内的数据访问局部性特征,因此,又称它们为连续局部性. 定义4 非连续局部性(Discontinuous Locality).指程序在运行时,由于函数被重复调用,存在被重复访问的数据访问序列.如果在该数据访问序列被重复访问之前,利用数据预取技术把该数据访问序列要访问的数据提前取到Cache中,这样在该数据访问序列被重复访问时就不会发生缓存失效了. 图1中显示的数据访问局部性特征示例说明了时间局部性、空间局部性和非连续局部性的区别.图1中,An表示的是访存地址,左边的地址序列Seq1={A1,A2,A7,A5,A3,A1,A2,A4,A6,A8}是程序运行过程中某一时间段的顺序访存流,右边的地址序列{A1,A2,A3,A4},{A5,A6}和{A7,A8}是该时间段内访问数据的几个连续存储空间.根据定义1, A1,A2是很短时间内被重复访问的数据地址,如果第一次访问A1,A2时发生了Cache失效,需要从内存中读取A1,A2的数据,则当下一次访问A1,A2的数据时,就可以直接从Cache而不需访问内存了.因此,程序对数据地址A1,A2的访问具有时间局部性特征.同样地,根据定义2, {A1,A2,A3,A4},{A5,A6}和{A7,A8}在内存中属于邻接的数据块,如果在访问其中一个数据块时(如A7)发生了Cache失效,需要从内存中读取数据(如A7),则当不久访问邻接数据块(如A8)时就不会发生缓存失效了.因此,程序对地址序列{A1,A2,A3,A4},{A5,A6}和{A7,A8}的访问具有空间局部性特征.最后,假如数据访问地址序列Seq1在程序运行过程中多次重复出现,当第一次访问Seq1时暂时把这个序列保存起来,则第二次访问Seq1时,利用数据预取技术提前把Seq1中的数据取回到Cache中,这样就避免了第二次访问Seq1的Cache失效.因此,程序对地址序列Seq1的访问具有非连续局部性特征. 3 差别化预取对象的选择 基于访存流模型的数据预取技术是隐藏非规则数据访存延迟的有效措施.然而,已有的基于访存流模型的数据预取技术不是忽略了访存流中的时间顺序,就是忽略了各访存指令访存行为间的差别,造成由过早预取行为引起的缓存污染或由过晚预取行为引起的无效预取.因此,建立能反映时间顺序和行为差别的访存流模型对数据预取的有效性来说至关重要. 为了保证差别预取策略的有效性,节约系统资源,本文选择位于程序关键执行路径上的,且其频繁缓存失效行为严重影响程序性能的热点循环作为差别预取对象.为了选择合适的差别预取对象,本文在应用差别预取策略前先使用动态剖析工具分析测试程序,并在频繁发生缓存失效行为的热点循环入口处做标记,当程序运行到标记处时启动差别预取策略. 3