Locality Research (Chinese)

重用距离分析及应用

概观

计算机系统研究的一大主题是性能,性能优化的通常手段是对重复行为进行优化。   我们研究的主要问题是数据的重复使用,我们先确定一个复杂的程序中数据的使用是否存在规律,如果存在,是否可以被测量,分析,并最终改善。我们研究的目的是探索数据使用的性能极限。

现代计算机除极少数外都依赖高速缓存对数据作快速存取,随着计算机速度和并行度的提高,高速缓存的效率越来越多地决定了系统的运行速度,成本和能源使用。 高速缓存的使用取决于程序局部性,也就是数据重用模式。 应用程序有大量和多样的数据重用,例如,一个天文模拟程序的时间步之间​​重用天体数据,一个编译器的优化步之间重用程序表达式,或一个象棋程序每步计算之间重用棋盘布局。 然而,局部性是一个难以捉摸的概念。一个程序通常对数以百万计的内存单元进行每秒数十亿次的访问。局部性研究的挑战在于理解和控制数据使用的宏观规律。

传统的局部性分析有三种方式。其一,由编译器分析循环嵌套,但不能有效处理动态控制流和数据间接引用。其二是程序刨析分析(或称轨迹分析),但不能预测程序在其他输入下的数据分配和使用。其三是运行时分析,但迫于实时要求,不能涵盖过多数据和数据使用。 在过去的十多年里,有关重用距离的研究对以上的困难给予了新的解决办法。

重用距离测量两个同数据访问之间的数据量,它是欧氏距离的一种,它结合了数据访问的频率,时间,和空间的信息。每个数据使用有一个重用距离,它们的总分布就像一个时序信号的频谱,构成了对整体行为的宏观描述。重用距离测量相当于程序行为的傅立叶变换,之后的结果可以用于行为分解和统计建模。

重用距离测量 (ASPLOS'13, TOPLAS'09, POPL'07, PLDI'03)

在1970年,Mattson等人定义了堆栈距离的概念,这一概念在之后的几十年的高速缓存设计开发中得到广泛应用。重用距离是堆栈距离的一种,即LRU堆栈距离或使用LRU(最近最久未使用)替换策略的堆栈的距离。 Mattson等人的堆栈算法。需要O(NM)的时间和O(M)的空间代价,其中M是数据总量,N是总数据使用次数。 从1970到2000的30年间,不断有工作提高重用距离的测量效率。1981年,奥尔肯(Olken)放弃堆栈而使用搜索树,将时间复杂度降低为O(NlogM)。 Sugumar和亚伯拉罕在1994年用splay树创造了当时最快的实现。 他们的模拟器,猎豹(Cheetah),得到了广泛的使用。 在2003年,我们给出了一个快速的近似算法,这一算法保证测量距离的相对准确性,例如99%,其准确性也可以是99.9%,或任意地接近100%。近似算法将搜索树的空间复杂度从O(M)降为O(log M),总时间复杂度从O(NlogM)降为O(N loglogM),这实际上是一个线性的时间代价。 在实验中,即使重用距离高达1亿个数据,99%准确度的近似测量保持了几乎恒定的速度。 如果用物理距离做比喻。 老的方法可以测几万几十万公里的距离,新的方法可以测光年长度的距离。 它的空前的效率,使我们能够分析大量数据的密集使用。

在2012年,俄勒冈州立大学和中科院计算所的研究人员将近似算法并行于机群和GPU。在2013年,我们推导出一个高阶局部性理论,并用它获得了接近实时的重用距离测量速度。

程序总体局部性模型 ( PLDI'03 , LACSI'03 , PACT'03 

程序行为随输入不同而变化,但是它的变化常常有一定规律。我们用总体局部性模型来捕捉行为变化的宏观规律,并预测在其它某输入或所有输入下的行为。这个思路就好像一个天文学家观察夜空,通过测量一颗恒星不同时刻的位置,而建立恒星轨道的数学模型。 

我们的测量使用重用距离。正如前面提到的,重用距离具有独特的性能。 对于宏观分析,长的重用距离可以显示程序的长期行为。同一程序在不同输入下可能使用不同数据,或同一数据在不同存贮位置。重用距离允许我们比较不同的程序运行之间的相互关系。 此外,重用距离最大不超过数据总大小。因此,重用距离的变化只能是输入大小的线性或亚线性函数,减少我们的建模的数学难度。 我们的实验结果表明,该方法适用于多样的程序。即使不同程序输入下的数据大小,访问频率,平均重用距离相异数百倍,预测准确度超过94%。这一思路在工业界和学术界的研究中有许多应用。 在后面的,独立的研究,赖斯大学研究组取得了类似的预测精度,论文发表于2004年SIGMetrics 。密歇根理工大学卡尔和王振林的研究组 使用我们的工具,在2005年发表了对每一个指令建模的技术,可以准确地预测指令级的局部性。

我们的后续工作探讨了局部性问题的其它维度,尤其是对总体局部性进行了时间轴和空间轴的分解。 

数据的动态局部性周期( JPDC'07, ASPLOS'04 )

程序优化通常在编程时或编译时进行,但是它们不能对特定输入下的独有的重复行为作有效优化。动态局部性分析通过动态预测程序的周期性行为,帮助硬件和软件做自适应优化。我们的技术首先对程序某一输入做轨迹分析,在这一步我们将重用距离作为一个数字信号,使用信号处理中的小波分析寻找基本周期时段和这些时段的边界,再通过CFG文法压缩找到复合周期的嵌套结构。然后,我们对程序代码进行周期标定。 当分析过的程序再运行时,程序自身就可以预报下一时段将重复那一周期,我们就可以在前面时段进行测量,在后面时段进行优化。 适合时段分析的程序,包括通常使用的物理,工程和生物模拟程序。 它们的行为随输入变化,但在每一运行中,它们的行为重复或变化缓慢。 与现有的方法相比,我们的周期分析能找到较大粒度级(宏观)动态规律。 我们用这一分析于自适应优化,包括硬件高速缓存大小调整和软件内存重映射,通过这些应用我们评估周期预测的好处,发现它能显著提高优化程度,而且也比手工周期标定更有效。

数据布局的局部性结构 ( POPL'06,PLDI'04 

在处理器的存储器层次结构中,不同层次使用不同大小的数据块,比如缓存块64字节,内存页4K字节,磁盘区512K字节。数据布局成为一个编程的基本问题。我们开发研究了数据布局的局部性结构。首先是时近性的定义和理论基础,其次是基于重用距离的时近性分析。如果一组数据总被同时使用,我们说它们具有时近性,而且它们属于同一个时近性组。计算所研究组称时近性为数据亲近性。我们证明得出,时近性给出了一个分层分组的数据关系。 在最上层,所有的数据属于同一个时近性组,该组的时近性最弱。 在最低层,每个数据元素属于独自的时近性组,具有最强的时近性。 在中间层次,数据属于不同大小和程度强弱的时近性组。这个分组如同人员建制,好比一个公司将雇员根据工种技能由上到下从部局分配直到科室。时近性的概念从计算序列中的前后使用推导出数据集合里的远近布局,从时间规律建立空间关系。这个理论虽然独特,但需要实践检验。

程序通常有大量的数据对象,例如在一个空间模拟程序的空间点,或搜索树的树节点。 每个对象都有一组属性。 在Fortran 77程序中,对象的属性存储在分别的数组中。 在C或JAVA程序中,对象的属性存储在一个结构中。 这两个方案对程序的访问模式和局部性不敏感。 更好的方法是时近性对属性分组,改造数据布局。 这个改造叫结构分裂。 我们的研究表明,基于时近性概念的方法优于程序员,编译器,频率分析,统计聚类的方法。

一个复杂但有效的布局方法是层层分解,这一解法被用于不同领域,包括矩阵计算,Cholesky分解,小波变换,N体模拟,和搜索树。层层分解之所以有效,是因为它可以同时优化所有存贮层次的数据块。但是,过去的方法只适于具体的计算领域,通过时近性理论和技术,我们得到一个通用的解法。

复杂的内存层次结构使编程越来越难。 自动数据布局是NP-难并不可逼近。 不过,基于重用距离的理论和技术,我们的工作将程序的局部性分析和优化建立在一个科学的基础上。

Groups: