|
- UID
- 872238
|
同样，将相互访问频率较高的内存块，如三个数组A、B、C分别存放在不同的内存块，数组A和数组C是经常要进行元素间计算的，则把分别存储A和C的块放在相邻的位置上，这样，既可以减小地址总线的负担，也可以提高访问时间和减少访问次数。
2 规划算法
使系统内存访问延迟最小的内存规划应该从变量和要申请的内存块在内存中存储的相对位置的角度来寻找。其前提条件是变量和内存块的访问顺序已知，申请的块的信息也可以得到。根据嵌入式系统应用的特点，例如图像处理系统，经过对程序的预处理，这个条件可以满足。处理过程可分为二步：第一步进行块间的规划；第二步对块内变量进行规划。问题的描述如下。
在嵌入式系统中，设内存块大小为S，某段时间内内存块个数为T，块中每页的大小为p*q*w，其中p为行数，q为列数，w为每个字的位数。在某个应用中有N个变量{ni，i=1，……，N}，已知变量被访问的次序为njnknl……nm，则首先寻找块存储的相对位置，使得内存访问延迟函数Latency1最小(假设两个块相邻，访问需要1个时钟周期；相隔1个块，访问需要2个时钟周期；第i个块和第j个块间访问需要i－j个时钟访问延迟)：
Latency1={Sum|∑z*（i－j）/z，z=1....m} (1)
其中：z是访问顺序表中内存块的位置，如第3个位置（z＝3）访问的是bi，下一个位置存放的是bj，i和j是内存块访问顺序中相邻块标号，是块在内存中存储的相对位置，m是访问内存块的顺序排列长度。其次寻找N个变量在内存块内的存储相对位置的一种规划{nxnynz……nt}，使得内存访问延迟函数Latency2最小，块内规划目标函数为：
Min：Latency2=5*#P+3*#R+#C (2)
其中：＃P是规划中访问的页间转换的次数，＃R是行间转换的次数，＃C是列间转换的次数。N个变量的排列方法的数目共有N!种，要在如此多的情况下寻找某种最优的排列，这是NP问题。解决这类优化问题有很多方法，如模拟退火算法、演化算法等一些启发算法，也可以用曲线图划分问题（graph partitioning problem）的方法来解决此问题。本文采用了最近几年发展很快的遗传算法来解决此规划问题。遗传算法是解决NP问题的有效方法。本文的研究目的在于内存规划的意义，而不是遗传算法，所以采用经典遗传算法[8]，以此来验证内存规划的有效性。本文的算法可记为LBP（LBP-Layout of Block and Page）。
2.1 算法的前提条件
在解决问题之前，要给出解决问题的前提。
(1)对块内访问时，通常是先寻找页，再找到行，最后找列，则对页访问的耗时（一般称为内存访问延迟）大于对同页中的行，行访问耗时大于同行中的列。同时在相距较远的块间访问耗时大于相邻块间访问。
(2)减少内存访问中块和页的转换次数，可以减少延迟和节省能量。
(3)在页/行/列之间转换没有优先级，也就是从1～3页和从1～2页耗时是相同的。
(4)内存单元阵列是矩形，p和q代表内存块单元的行数和列数，w代表内存字的长度，则p*q*w代表了内存的大小。
(5)数据访问顺序是已知的。
(6)每个数据都分配给独立的内存单元，基本单元的大小与要分配的数据刚好匹配。
前面四个假设是解决问题的必要条件，而后面两条假设是为了简化解决的问题。如果没有特别的说明，这些假设在本文都是适用的。 |
|
