|
- UID
- 872238
|
2.2 遗传算法
遗传算法的基本步骤是确定适应度函数，然后对问题进行编码和寻找最优解。下面给出解决块内规划问题算法第二步的基本步骤。第一步与第二步相似，本文省略。
(1)适应度函数是目标函数，即Latency。依据假设，如果页访问模式延迟时间是5个时钟周期，记为Delay(P)=5cycles，则行延迟Delay(R)=3cycles，列延迟Delay(C)=1cycles，适应度函数为：latency(cycles)=#P*5+#R*3+#C*1。
(2)解决的问题是内存变量的存放次序，由于字母的数目有限，所以可用十进制编码来表示变量(如把图1中abcdefgh编码为12345678）。
(3)杂交过程选择同一代中的某些位进行交换，不同代的交换容易产生非法个体， 所以在某代个体内部进行交换，可以提高算法的有效性。选取某代杂交的概率为Pc＝0.08。
(4)算法的终止是在某两代适应度函数之间相对误差小于0.001时，程序终止，并给出最优的内存规划方法。如果内存单元数目有p*q个，则取串中每q个为一行（分为一组），间隔n*(q-1)为一列，存放在内存中供程序使用。
2.3 实验结果
图像处理系统的处理对象是象素，处理过程中使用大量的内存，造成了嵌入式系统图像处理应用中的瓶颈。经过近几十年的发展，图像处理算法也有很多成熟的算法。可以把这些算法经过改造，使之适应嵌入式系统体积小、容量小的特点。本文算法的提出是针对使用大量内存，同时处理步骤相对简单的系统设计的。本文采用一些标准(benchmark)系统，提高嵌入式系统有限的内存资源的利用率。基于内存的规划算法，用几个内存访问序列验证内存规划对嵌入式系统性能的改变。实验中使用IFA(Image Flip Algorithm)、GSR(Gauss-Seidel formula)、CA(Compress Algorithm)、BIQUAD(Biquad_one_section)和FIR。后两个例子是为了验证非图像处理的系统使用本算法的情况，说明算法的应用具有一定的普遍意义。
表1和表2是用随机访问方法和本文的访问方法进行实验的结果。从表中可以看出，规划后的延迟时间都缩短了，另外还验证了规划内存方法的使用减少了嵌入式系统能耗。能耗的计算采用文献[2]中的算法，如图3（a）所示。 |
|
