遗传和禁忌搜索融合的可重构系统软硬件划分
来源:www.lunwenhot.com 作者:热点论文发表网 点击: 次
0 引言 在嵌入式系统的设计中，系统级设计阶段的软硬件划分过程至关重要，其主要任务是在满足各项约束的条件下，把系统功能划分到目标结构中的软件和硬件部分上，并为系统提供最佳的软硬件折衷方案。近年来，随着可重构硬件及其动态重构[1-2]能力的进步，使
0 引言
在嵌入式系统的设计中，系统级设计阶段的软硬件划分过程至关重要，其主要任务是在满足各项约束的条件下，把系统功能划分到目标结构中的软件和硬件部分上，并为系统提供最佳的软硬件折衷方案。近年来，随着可重构硬件及其动态重构[1-2]能力的进步，使得越来越多的嵌入式系统采用可重构系统结构。可重构硬件的动态重构能力使得硬件电路的功能可以根据程序的执行来选择，这种灵活性打破了硬件的传统应用模式，同时也使得传统的软硬件划分方法不再适用于可重构系统。可重构系统软硬件的划分必须考虑可重构硬件的动态部分重构及其重构延时等特征[3].
1 系统模型
动态可重构系统模型如图1 所示，主要由微处理器、配置控制器、可重构硬件（FPGA）、内存和配置文件存储器组成。为将微处理器核从FPGA 的配置任务中解脱出来，使二者能够真正并行地执行不同的计算任务，本文在系统中增加一个额外的配置控制器，负责对FPGA进行配置。当微处理器执行到一条硬件配置指令时，将相应数据传递给配置控制器，后者从配置存储器中取出相应配置数据信息，并下载到FPGA 上完成配置工作。微处理器和可重构硬件以共享内存方式通信，因此一条边相连的位于微处理器和可重构硬件上的两个任务，除数据传送时间之外，其通信时间还包括数据的读写时间。在此系统中对内存的大小没有限制，但可重构硬件中的CLB 资源是受限制的。任务在微处理器上串行执行，多个任务在可重构硬件上并行执行，微处理器和可重构硬件并行执行。
在动态可重构系统中，应用被描述为一个考虑动态部分重构和重构延迟[4]的有向无环图。首先将一个大规模应用分解成粒度大小合适并且具有约束关系的多个子任务图，无论在微处理器上还是在可重构硬件（FPGA）上任务的执行都是非抢占式的。根据各子任务之间的执行先后的约束关系，画出一个表示任务约束关系的有向无环图（DAG）。DAG 中的节点表示基本任务调度模块，任务图中的边表示任务间的通信及其先后关系，边的权重代表任务间的通信开销。每个基本任务调度模块都能从它的父节点接收数据，并将数据传给它的后继节点。
2 软硬件划分
软硬件之间的功能划分及其软硬件实现随着应用的不同而变化，问题的解决就是去发现由任务图描述的应用到微处理器和可重构硬件构成的可重构系统上的时间/空间映射，实质是一类全局优化问题[5].本文使用GA 与TS 的混合策略（GATA）对应用进行划分，以实现在时间约束下最小化系统代价的目的。
TS 的创始人Glover 对混合GA 与TS 的必要性和可行性进行了理论上的分析和论述，被公认为混合GA 与TS 的理论基础。在Glover 理论的基础上，通过对GA 和TS 的理解和分析，本文提出一种GA 与TS 的混合策略GATS[6],并将其应用在可重构嵌入式系统软硬件划分上。
针对GA 爬山能力差的缺陷，利用TS 爬山能力强的优点，使用TS 算法改进GA 的爬山能力，即把TS 作为GA 的变异算子TSM.GATS 综合了GA 具有多出发点和TS 的记忆功能和爬山能力强的特点，克服了GA 爬山能力差的弱点，并保持了GA 具有多出发点的优势。
首先给定初始参数（包括最大迭代次数max generation,群体规模popsize ,交换概率pc 和变异概率pm ）。利用GA算法，随机生成初始种群，并对种群编码，本文采用二进制编码。然后对个体进行选择、交叉等操作，当进行GA 算法变异这个环节的时候，调用TS算法。整个算法流程如图2（a）所示。其中，TS 做为变异算子是算法的核心。TS 的算法流程如图2（b）所示。如果随机生成的概率p < pm,则调用TS.禁忌搜索涉及到邻域（neighbor）、禁忌表（tbau list）、禁忌长度（tabu Length）、候选解（candidate）、特赦准则（aspirationcriterion）等概念。采用0-1 反位因子产生GATS 的变异算子中的邻域解，X0为满足特赦准则的最佳状态，X m为不在tabu list中的最优邻域解。
3 调度算法
调度的目的就是针对由遗传和禁忌搜索融合算法得到的划分结果，找到整个任务流图的最短时间的指派和任务执行顺序[7].目前大部分DAG 调度算法都是基于一种所谓的表调度技术。表调度算法有两个阶段，其一是确定各任务的优先级，其二是处理机选择阶段，从而选择合适处理机来运行当前优先级最高的就绪任务。其基本思想是：使用一个调度队列保存所有可以开始执行的任务，每当系统中有运算资源空闲时，就从调度队列中选择一个优先级最高的任务放到空闲的运算资源上开始执行。
3.1 计算调度优先级
调度算法的好坏，在很大程度上取决于如何定义每个任务的调度优先级。常用的标准包括尽早调度（ASAP）、尽可能晚调度（ALAP）等，但这些优先级经常受制于他们的静态性质，其值是在调度前计算的。在调度期间，静态计算的优先级不能准确地描述任务的动态性质。
因此，本文使用式：priority（ⅵ）=-（dyna_ASAP（ⅵ）+ALAP（ⅵ）） [8]给出的动态优先级。
其中dyna_ASAP 表示动态ASAP 启动时间，ALAP 的值保持不变，通过静态计算获得。在以逆邻接表表示的任务流图上，首先计算出其关键路径，然后出给每个任务节点的ASAP 和ALAP值，其中每个节点的ASAP 值取多条路径所获得的最大值，每个节点的ALAP 值取多条路径所获得的最小值，任务之间的通信时间已被分配到进行通信的源、目的任务上。大ASAP 值
