面向多任务嵌入式系统的片上便笺式存储器管理方法

摘要

本发明公开了面向多任务嵌入式系统的片上便笺式存储器管理方法，它的步骤为：对程序代码段进行预分析；对程序进行跟踪，得到其内存指令访问序列，从而获取内存代码块的访问次数和高速缓存Cache未命中信息，在高速缓存Cache访问时统计和记录内存代码块的时空冲突集；根据需要选择算法得到优化的SPM分配方案；生成代码布局分散加载文件，对程序代码段进行重新映射和布局，重新编译代码得到优化执行结果。通过综合考虑访问频率、缓存未命中频率以及任务间和任务内冲突，求得自己所需的最佳分配，使便签式存储器的利用率最大化，最终在保证程序实时性的前提下得到执行时间最优方案或者节能最优方案。

说明书

技术领域：

本发明属于嵌入式实时系统领域，尤其涉及一种面向多任务嵌入式系统的片上便笺式存储器管理方法。

背景技术：

在嵌入式系统的发展过程中，由于主存储器的发展速度一直比中央处理器速度慢很多，主存的低读取速度与高能量消耗导致其成为现在很多嵌入式系统性能与能耗的瓶颈，而片上存储器则弥补了这种日益增长的主存和中央处理器速度的差距。

在嵌入式系统中，片上存储器主要包括便笺式存储器（SPM,Scratch Pad Memory）和高速缓存（Cache）两种。便笺式存储器SPM和高速缓存Cache本质上都是一种静态随机存储器（SRAM,Static Random Access Memory），存取速度很快，接近于CPU速度。高速缓存Cache由系统硬件控制，对于系统软件和程序员透明，基于程序执行时的时间与空间局部性来提高系统性能。相比传统的Cache，便笺式存储器SPM是由软件控制，在实时系统设计中能提供更好的时间预测性，并且由于便笺式存储器SPM由软件控制不需要地址比较电路，所以体积较高速缓存Cache小、功耗较高速缓存Cache低、访问速度较高速缓存Cache快。现在许多嵌入式系统如ARM公司的ARM11、Cortex-R系列等处理器芯片上都同时集成了这两种片上存储器。

在最近十几年有许多关于便笺式存储器SPM相关架构设计与管理的研究，它们或者优化性能、或者优化能耗、或者优化最坏执行时间（WCET，Worst-case Execution Time）。这些研究一般通过编译期代码选取和重新布局，静态或者动态的改变便笺式存储器SPM中的内容达到优化目的。但是现在的研究主要集中在仅有便笺式存储器SPM的系统，对使用便笺式存储器SPM+高速缓存Cache（如图1）存储体系的多任务系统的研究相对较少。现在仅有的针对便笺式存储器SPM+高速缓存Cache存储体系的多任务系统的优化算法中，算法以函数为基本分配单位，只考虑单个函数放入SPM所得到的能耗减少，对于多任务系统中任务间冲突以及任务内函数间的冲突没有考虑，而这些任务间以及任务内的冲突对系统的性能和能耗有很大的影响。

通过对多个程序执行过程的跟踪研究，发现在许多程序中，访问频率高或者高速缓存Cache未命中频率高的函数不一定是造成任务间和任务内冲突最多的函数（如图2，其中访问频率最高的是A₀和B₁，未命中频率最高的是A₀，但造成任务间和任务内冲突最多的是B₀），现有技术往往没有把访问频率、Cache未命中频率以及任务间和任务内冲突都考虑进去，更没有充分利用SPM。

中国专利（申请号：201310042340.6，专利名称：面向嵌入式片上异构存储器的细粒度数据分配方法），这篇专利虽然利用线性规划方法来解决便签式存储器SPM中的数据分配问题，但是1）它是讨论便签式存储器SPM中数据分配的问题，而数据分配与代码分配有极大的差别，因为多任务系统中代码之间的相关性，不能以内存块为单位来进行分配，2）它是利用线性规划方法来解决SPM分配问题，但是由于变量以及约束条件非常多，使用线性规划方法其计算时间复杂度是指数级的会消耗非常多的时间，根本无法满足实时系统的要求。

发明内容：

本发明要解决的问题就是：（1）明确多任务系统中任务间以及任务内的冲突情况；（2）综合考虑访问频率、高速缓存Cache未命中频率以及任务间和任务内冲突情况，充分利用有限的便笺式存储器SPM空间，本发明通过提供一种面向多任务嵌入式系统的片上便笺式存储器管理方法，充分利用便笺式存储器SPM的优势来优化程序的代码段，提高系统性能，加快执行速度，减少系统能耗；通过对程序中指令进行细粒度分析，然后根据优化目的的不同综合考虑多种因素进行便笺式存储器SPM分配，以便使便笺式存储器SPM的利用率达到最大，最终使执行时间最小或者使能耗最小。

为实现上述目的，本发明采用如下技术方案：

一种面向多任务嵌入式系统的片上便笺式存储器管理方法，它的步骤为：

步骤（1）：对程序代码段进行预分析，获取各个任务的各个函数在内存中的首尾地址和函数大小，并对所有函数进行统一编号；

步骤（2）：在无便签式存储器SPM架构下对程序代码进行跟踪，得到其内存指令访问序列，从而获取内存代码块的访问次数和高速缓存Cache未命中次数，在高速缓存Cache访问时统计和记录内存代码块的时空冲突集；

步骤（3）：根据需要选择算法得到优化的便笺式存储器SPM分配方案：

如果对分析时间没有要求就选择线性规划算法，根据步骤（1）中各个函数的首尾地址、大小和步骤（2）中访问次数以及时空冲突集来得到针对执行时间或者能耗的便笺式存储器SPM优化分配方案，记录应该放入便签式存储器SPM的函数编号；

如果要求最少的分析时间就选择背包近似算法，根据步骤（1）中各个函数的首尾地址、大小、步骤（2）中的访问次数和高速缓存Cache未命中次数以及时空冲突集来得到针对执行时间或者能耗的便笺式存储器SPM优化分配方案，记录应该放入便签式存储器SPM的函数编号；

步骤（4）：生成代码布局分散加载文件，对程序代码段进行重新映射和布局，重新编译代码得到优化执行结果。

所述步骤（2）中，在无便签式存储器SPM架构下通过仿真器跟踪执行得到程序访问指令的序列，获取内存代码块的访问次数和高速缓存Cache未命中信息，统计每个内存块两次高速缓存Cache访问之间不重复的内存块序列，生成时空冲突集合TCS，时空冲突集合TCS在步骤（3）的两种方法中都要用到。

所述步骤（3）的线性规划方法中，由于每一个内存块miss减少分两种情况：

1）.因为本身所在的函数被选取到SPM中，miss全部消失；

2）.当自身所在的函数没被选取到SPM中但映射到同一Cache组的其他内存块所在的函数被选取到SPM，由此可能导致自身一些TCS中的块数小于Cache的路数；统计SPM分配后的各个内存块的miss次数miss′_i，然后根据不同的优化目标选择不同的目标函数：

如果需要优化执行时间，目标函数为：

$>\left(\begin{array}{c}{\mathrm{lat}}_{\mathrm{access}}=\underset{i=1}{\overset{V}{\Sigma }}\underset{m_j\in f_i}{\Sigma }({\mathrm{miss}}_j^{\prime }·{\mathrm{lat}}_m+({\mathrm{access}}_j·(1-x_{\mathrm{fn}\left(m_j\right)})-{\mathrm{miss}}_j^{\prime })·{\mathrm{lat}}_c\\ +x_{\mathrm{fn}\left(m_j\right)}·{\mathrm{access}}_j·{\mathrm{lat}}_s)\end{array}\right)$>

如果需要优化能耗，则目标函数为：

$>\left(\begin{array}{c}{E}_{\mathrm{access}}=\underset{i=1}{\overset{V}{\Sigma }}\underset{m_j\in f_i}{\Sigma }({\mathrm{miss}}_j^{\prime }·E_m+({\mathrm{access}}_j·(1-x_{\mathrm{fn}\left(m_j\right)})-{\mathrm{miss}}_j^{\prime })·E_c\\ +x_{\mathrm{fn}\left(m_j\right)}·{\mathrm{access}}_j·E_s)\end{array}\right)$>

所述步骤（3）的背包近似算法中，将内存块之间的冲突通过计算影响因子转化为各个任务的各个函数之间的冲突，然后就综合访问频率、Cache未命中频率以及任务冲突多方面因素来考虑将各个任务的各个函数中的任意一个函数放入SPM中得到的“收益”，然后利用近似背包算法来取得优化执行时间的分配或者优化能耗的分配。

所述步骤（4）中，根据步骤（3）中得到的优化分配结果生成程序优化脚本，所述程序优化脚本即分散加载文件，根据步骤（3）中记录的函数编号在程序优化脚本中把步骤（3）中所记录的函数编号对应的函数映射到SPM中，但在主存中仍保留一个备份，其他代码在主存中的位置不变，因此分配前后未分配到SPM中的代码映射的Cache组不变，就使步骤（2）中得到的针对无SPM架构程序执行跟踪结果是有效的。

本发明采用的方法与现有技术相比有如下优点：

（1）使用SPM+Cache架构。在无Cache的架构中，未分配到SPM中的代码访问延迟以及访问能耗太高，无法有效提高程序执行速度、降低系统能耗。在SPM+Cache的架构中，可以同时利用两者的优点，在充分利用SPM的同时，未分配到SPM中的代码可以利用Cache来提高速度降低能耗。

（2）在多任务系统下求取最优SPM分配方案，相比单任务系统多任务系统能更好的利用CPU，极大的提高CPU利用率。而在多任务系统下就需要在考虑任务内函数之间冲突影响的同时考虑任务间的冲突影响。

（3）针对代码求取最优SPM分配方案，与数据不同，代码有相关性不能随意分割放入SPM，需要把相关代码统一分配。本专利以函数为单位进行分配，若一个函数被分配到到SPM中，则属于这个函数的内存块都要被放入SPM。

（4）对Cache冲突情况进行细粒度分析。跟踪程序执行，利用时空冲突集记录Cache访问情况，可以把所有的Cache冲突记录起来，这样就可以更加充分的利用SPM进行代码分配。

（5）提出两种求取SPM分配方案的方法，可根据不同需求选择不同方法。

（6）把各个任务各个函数之间的冲突量化出来。把内存块的Cache冲突情况量化的表示成各个任务各个函数之间的冲突，这样在分配时就把一个函数作为一个单位来分配，极大地减少了计算量。

（7）提出一种多项式时间算法。在任务函数之间的冲突被量化后，也就可以综合考虑每个函数被放入SPM后对整体有多大的“收益”，然后就利用一种背包近似算法来得到SPM分配方案，极大地减少了计算时间。

附图说明：

图1具有Cache+SPM结构的系统架构；

图2一段指令Cache跟踪轨迹；

图3任务集指令Cache miss统计；

图4映射到相同Cache组的内存块在Cache中的冲突序列；

图5函数f₁被选取到SPM后的冲突序列；

图6程序代码优化过程流程图。

具体实施方式：

下面给出本发明的一个实例并结合附图对本发明做进一步地说明。

（1）对程序代码段进行预分析

通过分析反汇编文件，找出源程序的代码段，然后对程序代码段进行分析；分析代码段是统计多任务系统中每个任务的每个函数的首尾地址以及大小，并对多任务系统中的所有函数进行统一编号。对于一个任务集（包括任务bs和任务cnt）程序（如图3，X轴为函数编号，Y轴为Cache未命中的次数）获取到的代码段信息如下：

函数编号首地址函数大小14194624176241948008834194888488………………62421923236

（2）对程序代码段执行轨迹进行跟踪，建立Cache冲突集合

把源文件编译成二进制文件，在多任务仿真器中获取程序执行的跟踪信息。分析跟踪信息得到每个代码块的首地址、大小、访问次数、miss次数和时空冲突集合（TCS），TCS中包含一个内存块的两次访问之间映射到同一Cache组的不重复的内存块访问序列。如图4，m₀、m₁、m₂、m₃、m₄、m₅为映射到同一个Cache组的内存块，假设Cache为2路组相联的，则m₀的时空冲突集为$>{\mathrm{TCS}}_{m_0}\left[1\right]=\{m_1,m_2\}$>和$>{\mathrm{TCS}}_{m_0}\left[2\right]=\{m_2,m_3,m_4\}.$>

（3）利用优化算法得到优化的SPM分配方案

在这一步骤中，有线性规划方法和背包近似方法两种方法可用于得到优化的SPM分配方案。表格1列出在两种方法中使用的符号和解释。

表格1

1.在线性规划方法中，通过线性约束条件和目标函数，使用Cplex等整数线性规划求解工具来求出最优解。表格2列出整数线性规划中使用的符号和解释。

表格2

线性规划方法中的线性约束条件如下所示。

1）SPM容量。SPM的大小是确定的，被放入SPM的函数占用空间之和不能大于SPM的容量。

$>\underset{i=1}{\overset{V}{\Sigma }}({\mathrm{size}}_i·x_{f_i})\le {\mathrm{SIZE}}_{\mathrm{SPM}}$>

2）TCS再计算。对于一个给定的SPM分配，因为有一部分函数被放入到SPM，即这些函数所包含的内存块也被放入SPM，那么那些包含被放入SPM的内存块的TCS就不是有效的，需要重新计算。

$>y_{m_j}\left[k\right]=\underset{m_p\in {\mathrm{tcs}}_{m_j}\left[k\right]}{\Sigma }(1-x_{\mathrm{fn}\left(m_p\right)})$>

3）Cache miss统计。TCS再计算之后就可以统计Cache miss数目，如果内存块不在SPM中且其TCS中的块数小于Cache的路数（如图5，当函数f₁被选取到SPM中时，和中的块数少于2，所以内存块m₀会减少两次miss），这次访问就是Cache命中，否则就是Cache miss。

$>c_{m_j}\left[k\right]=\left(\begin{array}{cc}0,& y_{m_j}\left[k\right]<A\\ 1,& \mathrm{otherwise}\end{array}\right)$>

转化为线性表达式是：

$>y_{m_j}\left[k\right]+(1-c_{m_j}[k\left]\right)·U\ge A$>

$>y_{m_j}\left[k\right]-c_{m_j}\left[k\right]·U+1\le A$>

U是一个很大的数字。

但仅仅不能代表Cache miss，只有m_j所对应的函数不在SPM并且才能表示Cache miss。

$>{\mathrm{cm}}_{m_j}\left[k\right]=c_{m_j}\left[k\right]·(1-x_{\mathrm{fn}\left(m_j\right)})$>

不过当将上述等式合并起来时发现其中含有非线性的项令这一项等于z可转化为线性化表达式：

$>z\le 1-x_{\mathrm{fn}\left(m_j\right)}$>

$>z\le x_{\mathrm{fn}\left(m_p\right)}$>

$>1-x_{\mathrm{fn}\left(m_j\right)}-x_{\mathrm{fn}\left(m_p\right)}-z\le 0$>

最后就可以统计SPM分配后的Cache miss数目。

$>{\mathrm{miss}}_j^{\prime }=\underset{k=1}{\overset{\mathrm{acces}{s}_j}{\Sigma }}{\mathrm{cm}}_{m_j}\left[k\right]+(1-x_{\mathrm{fn}\left(m_j\right)})$>

其中这一项表示当内存块m_j所对应的的函数没有被放入SPM中时的强制性未命中。

利用以上约束条件便可以使存储系统访问延迟最小化。下面为目标函数，其中lat_access是经过SPM分配后的总存储访问延迟，lat_m、lat_c、lat_s分别为Cache未命中、Cache命中和SPM命中时的延迟。

$>\left(\begin{array}{c}{\mathrm{lat}}_{\mathrm{access}}=\underset{i=1}{\overset{V}{\Sigma }}\underset{m_j\in f_i}{\Sigma }({\mathrm{miss}}_j^{\prime }·{\mathrm{lat}}_m+({\mathrm{access}}_j·(1-x_{\mathrm{fn}\left(m_j\right)})-{\mathrm{miss}}_j^{\prime })·{\mathrm{lat}}_c\\ +x_{\mathrm{fn}\left(m_j\right)}·{\mathrm{access}}_j·{\mathrm{lat}}_s)\end{array}\right)$>

也可以利用这些线性约束来使存储能耗最小化。目标函数如下所示，其中E_access是经过SPM分配后的总存储访问延迟，E_m、E_c、E_s分别为Cache未命中、Cache命中和SPM命中时的能耗。

$>\left(\begin{array}{c}{E}_{\mathrm{access}}=\underset{i=1}{\overset{V}{\Sigma }}\underset{m_j\in f_i}{\Sigma }({\mathrm{miss}}_j^{\prime }·E_m+({\mathrm{access}}_j·(1-x_{\mathrm{fn}\left(m_j\right)})-{\mathrm{miss}}_j^{\prime })·E_c\\ +x_{\mathrm{fn}\left(m_j\right)}·{\mathrm{access}}_j·E_s)\end{array}\right)$>

2.在背包近似方法中，将内存块之间的冲突转化为任务函数之间的冲突，然后就可以综合考虑将一个函数放入SPM中得到的好处，然后利用近似背包算法来取得优化执行时间的分配或者优化能耗的分配。表格3列出背包近似方法中使用的符号和解释。

表格3

为将内存块之间的冲突转化为任务函数之间的冲突，需要将任务函数之间的冲突影响量化，为此提出了影响因子的概念。

影响因子。在一个给定的程序执行轨迹中，对于内存块m_j的第k次冲突miss，表示函数f_i造成内存块m_j冲突miss的影响因子。

$>\mathrm{in}{f}_{f_i,m_j}\left[k\right]=\frac{\left|\right\{m|m\in \mathrm{tc}{s}_{m_j}[k]^m\in f_i\}|}{\left|{\mathrm{tcs}}_{m_j}\right[k\left]\right|}$>

然后可以定义函数f_i造成函数f_j冲突miss的平均影响因子。

$>\mathrm{in}{f}_{f_i,f_j}=\frac{{\Sigma }_{\left|\mathrm{tc}{s}_m\right[k\left]\right|\ge A}\mathrm{in}{f}_{f_i,m}\left[k\right]}{N_{\mathrm{miss}}},\forall m\in f_i$>

在这里N_miss是函数f_j所包含的所有内存块的冲突miss数目。例如图4表示一段程序运行轨迹，函数f₀包括内存块m₀与m₁，函数f₁包括内存块m₂与m₃，函数f₂包括内存块m₄与m₅。内存块m₀的时空冲突集为$>{\mathrm{TCS}}_{m_0}\left[1\right]=\{m_1,m_2\}$>和$>{\mathrm{TCS}}_{m_0}\left[2\right]=\{m_2,m_3,m_4\},$>而内存块m₁的时空冲突集为对于$>{\mathrm{TCS}}_{m_0}\left[1\right],\mathrm{in}{f}_{f_1,m_0}\left[1\right]=1/2,{\inf }_{f_2,m_0}\left[1\right]=0;$>对$>{\mathrm{TCS}}_{m_0}\left[2\right],\mathrm{in}{f}_{f_1,m_0}\left[2\right]=2/3,$>$>{\inf }_{f_2,m_0}\left[2\right]=1/3.$>所以，

$>{\inf }_{f_1,f_0}=\frac{\mathrm{in}{f}_{f_1,f_0}\left[1\right]+\mathrm{in}{f}_{f_1,f_0}\left[2\right]}{2}=7/12$>

$>{\inf }_{f_2,f_0}=\frac{{\inf }_{f_2,f_0}\left[1\right]+\mathrm{in}{f}_{f_2,f_0}\left[2\right]}{2}=1/6$>

从就可以计算lat_inf_i。

$>\mathrm{lat}\_{\mathrm{sf}}_i=\underset{m_j\in f_i}{\Sigma }({\mathrm{access}}_j·({\mathrm{lat}}_c-{\mathrm{lat}}_s)+(\mathrm{conflic}{t}_j+1)·({\mathrm{lat}}_m-{\mathrm{lat}}_s))$>

$>\mathrm{lat}\_{\mathrm{cf}}_i=\underset{m_j\in f_i}{\Sigma }\mathrm{conflic}{t}_j·({\mathrm{lat}}_m-{\mathrm{lat}}_s)$>

$>\mathrm{lat}\_\mathrm{in}{f}_i=\underset{j=1,j\ne i}{\overset{V}{\Sigma }}({\mathrm{lat}\_\mathrm{cf}}_j·{\inf }_{f_i,f_j})$>

在得到lat_sf_i和lat_inf_i之后就可以计算lat_i。

lat_i=1at_sf_i+lat_inf_i

这样就知道每个函数被放入SPM后对整体有多大的“收益”，然后再利用背包近似算法来计算把那些函数放入SPM可得到最大收益，算法描述如下。

算法1

在这个算法中，先将所有函数按非增加的lat_i/size_i进行排序，其次选择一个函数集中函数数目不大于k并且函数集中所有函数容量之和不大于SPM容量的函数集，然后利用贪心策略选取剩下的函数直到SPM放不下，最后选取其中收益最大的分配方案。

将其中的访问延迟换成访问能耗，就可用于能耗优化。

（4）生成代码布局分散加载文件

分散加载文件是编译器在链接时使用的输入文件，用来指定代码段的加载区域和地址。经过步骤（3）之后，可以得到需要加载到SPM中函数的相对位置，在指定好SPM的初始位置和大小之后，很容易计算出函数在SPM中的相对位置，如果指定SPM的初始地址为0x20000000，举例如下：

变量名大小在SPM中的位置是否在SPM中（1，在；0，不在）117602880x20000000134880x200000581……………………

在分散加载文件中描述如下：

上述虽然结合附图对本发明的具体实施方式进行了描述，但并非对本发明保护范围的限制，所属领域技术人员应该明白，在本发明的技术方案的基础上，本领域技术人员不需要付出创造性劳动即可做出的各种修改或变形仍在本发明的保护范围以内。