胡九川，范东睿，程建聪，严龙，叶笑春，李灵枝，万良易，钟海斌

（1.北京交通大学计算机科学与技术学院，北京 100044；2.中国科学院计算技术研究所，北京 100080）

1 引言

计算机存储程序原理决定了即将被执行的指令或被处理的数据必须分批次地调入处理器，在容量十分有限的处理器片上缓存内中转停留，而暂时不能调入的大量指令和数据停留在内存乃至硬盘中，等候调遣进入处理器参与运算实现程序运行；同样，被执行过的指令或处理过的数据也很可能在处理器片上缓存内中转停留，然后回到内存或硬盘。所以，将那些在时间和空间上具有紧密关联关系的指令与数据以群组为单位预先放置于紧邻处理器核的片上缓存的顶端，形成及时局部性环境[1-5]。这样的环境有利于缩短处理器内核的访存时延，提高内核的访存命中率。但是，对指令和数据在片上缓存与内存之间往返迁移的特点和规律缺乏应有的研究和分析。本文将运用数学方法研究指令和数据在处理器片上的迁移，初步探索其特点和规律，以最大限度保持指令和数据之间的时间和空间联系，该方向的研究具有重要的理论和实践指导意义。

根据存储程序原理，指令和数据之间的时空关联关系来源于程序执行逻辑的内在规定。抽象地看，以指令执行顺序、数据安置顺序为基本构件形成的逻辑复合体构成了计算机程序，这个逻辑复合体隐含着指令之间、数据之间不可割舍的时空联系。……