任务分配是SoC设计与实现中的重要过程。它负责在满足系统约束的条件下, 将SoC应用功能的各个任务分配到SoC的各个处理器核上, 以使应用任务在SoC上高效运行。SoC任务分配方法决定了应用功能在SoC体系结构上的实现方式、系统性能与效率。因此, SoC任务分配度方法成为亟需研究的关键问题之一。
任务分配方法有双路分配和多路分配两种方式。双路分配主要研究由单个处理器和若干专用硬件模块所构成系统的任务分配方法, 多路分配主要研究由多个 (两个或更多) 处理器和若干专用硬件模块所构成系统的任务分配问题。
本项目针对传统任务分配方法的不足, 提出一种基于应用特征的启发式任务分配方法。该方法使用程序特征分析技术提取应用中的任务, 之后采用启发式任务分配规则, 实现任务在SoC上的分配。
1 相关研究
鉴于在SoC设计中的重要性, 任务分配工作得到了研究人员的广泛关注与研究。已有的SoC任务分配方法可以分为人工分配与自动分配两种。
人工分配方法依靠SoC设计人员进行任务分配。这种做法在传统的多处理器S o C设计中非常常见。该方法借助S o C设计人员的设计经验可以获得较好的效果。然而, 对于复杂的应用而言, S o C设计人员在进行人工任务分配时, 难以准确掌握并利用任务的特征信息, 无法实现处理任务的高效分配。
自动任务分配方法依靠自动化的算法或工具进行任务分配。典型的自动分配方法有: (1) 郭晓东等人[1]提出的使用遗传算法进行带约束的SoC任务分配方法; (2) Gang Wang和Wenrui Gong等人[2]提出的应用基本蚁群算法求解S o C任务分配问题的一般方法, 该方法综合运用局部和全局启发式信息, 通过蚂蚁间的协作, 进行有效的随机搜索, 以获取最优划分解; (3) Theerayod Wiangtong[3]面向细粒度可重构S o C实现了自动化的编译时划分与调度算法, 并进行了遗传算法、模拟退火和禁忌搜索的实验比较与分析。
然而, 上述自动分配方法却没有利用SoC设计人员的专家经验。某些任务分配经验, 例如:处理任务的核心函数应该分配到可重构处理器上, 这对于SoC设计人员是显而易见的, 却不容易通过自动化算法获得。因此, 如果能够充分利用SoC设计人员的设计经验, 可以提高处理任务的分配效率。另外, 可重构处理器具有强大的处理功能, 可以快速处理函数粒度的任务。在以函数粒度进行任务分配过程中, 问题规模与复杂性较小, 而采用复杂的自动化启发式寻优算法有些“大材小用”, 反而不利于提高任务分配效率。
针对上述不足, 本文提出一种基于程序特征的启发式任务分配方法。使用该方法时, 首先使用程序特征分析技术, 提取程序中的任务以及任务的运行时间, 之后使用基于SoC设计人员经验的启发式任务分配规则, 交互式的将处理任务分配到可重构SoC的各个处理器核上。
2 问题定义
可重构SoC任务分配问题在求解过程中, SoC系统的功能行为采用函数调用图描述。之所以采用函数调用图来描述SoC系统行为, 是因为在任务分配中的任务采用函数粒度。函数调用图的定义如下。
定义, 函数调用图:函数调用图G= (T, E) 由节点T、边E构成。其中, T是函数任务集, E⊆⊆ (T×T) 是有向边集, 表示函数任务之间的调用关系。
使用函数调用图的双着色模型来描述可重构SoC任务分配问题, 如图1所示。t0和tn是虚拟任务, 用于确保函数调用图中只有一个开始节点和一个结尾节点。分配到主控处理器上的任务用颜色c1表示, 分配到可重构处理器上的任务用颜色c2表示。
3 基于应用特征的启发式任务分配方法
3.1 任务分配粒度
任务分配的粒度采用函数粒度。之所以采用函数粒度, 是因为可重构处理器的处理能力足够大, 可以处理函数粒度的处理功能。相反, 如果粒度过小, 比如采用循环粒度或者基本块粒度, 会导致频繁的主控处理器与可重构处理器之间通信, 从而抵消一部分可重构处理器的处理性能。
3.2 任务分配过程
在任务分配过程中以程序特征分析结果为依据, 使用交互的启发式任务分配方法。任务分配分为以下四个过程。
第一步:生成处理程序的SUIF中间表示。基于SUIF编译框架, 对处理程序进行词法分析、语法分析和语义检查, 将C语言表示的处理程序转化成SUIF中间表示。
第二步:分析提取处理程序中的函数任务。基于处理程序的SUIF中间表示, 提取处理程序所包含的函数。
第三步:估算各个函数任务的计算时间。根据处理程序中各个函数任务所包含的SUIF指令条数, 估算各个函数任务的计算时间, 作为任务分配的依据。
第四步:根据启发规则进行任务分配。在第三步中已经得到各个函数任务的计算时间。根据计算时间与专家经验, 将各个函数任务分配到SoC各处理器上。根据计算时间的分配是指将运行比较耗时的任务分配到可重构处理器上加速, 根据专家经验的分配是指根据SoC设计人员的经验将某些关键任务分配到可重构处理器上加速。
3.3启发式规则
以密码处理为例, 在任务分配过程中, 根据专家经验设定启发式规则, 规则如下。
if某任务是密码处理的核心函数, 且该任务适合可重构处理器处理。
then将该任务分配到可重构处理器上。
if某任务不是密码处理的核心函数, 且该任务运行时间>所有任务的平均运行时间且该任务适合可重构处理器处理。
then将该任务分配到可重构处理器上。
其余情况都将任务分配至可重构处理器实验结果与分析。
以DES为例, 给出启发式规则:
4 实验结果
4.1 应用实例
任务分配的对象使用DES、AES和MD5算法。任务分配的目标体系结构采用可重构密码处理SoC体系结构。图2给出该SoC的体系结构。任务分配的目标为分别将DES、AES和MD5中各个函数分配到可重构密码处理SoC中的主控处理器或者可重构处理器上。
实验环境的主要参数如下: (1) 硬件配置:AMD Athlon 5800+, 2G内存。 (2) 操作系统:Red Hat Enterprise Linux AS 4.7 (kernel 2.69) 。 (3) 应用软件:Eclipse-x11-opensource-4.4.3, graphViz。 (4) 实现方法:java语言。
4.2 实验结果与分析
以D E S为例进行任务分配, 图3给出DES分配结果。图中的各个结点代表函数。函数之间的边代表各个函数之间的调用关系。各个结点的着色代表将其分配到不同的处理器上。其中浅色部分为分配到可重构处理器上运行的函数, 而深色部分为分配到主处理器上运行的函数。
5 结语
本文提出一种基于程序特征的启发式任务分配方法。该方法借助于程序特征分析结果与专家经验, 使用启发式任务分配规则, 能够有效地实现处理任务在可重构SoC上的分配。该方法对于应用在可重构SoC上的高效映射和实现具有一定的辅助支持作用。
摘要：本文提出了一种基于应用特征的启发式任务分配方法, 适用于对可重构SoC进行系统级任务划分。实验以可重构密码处理SoC为目标, 对密码处理任务进行任务划分, 实验结果验证了任务分配方法的有效性和实用性。
关键词：启发式,任务分配,SoC,设计与实现
参考文献
[1] 郭晓东, 刘积仁, 文晖.一种基于遗传算法的硬件/软件划分方法[J].计算机辅助设计与图形学学报, 2001, 13 (1) :24～27.
[2] Gang Wang, Wenrui Gong and RyanKastner, "System Level Partitioning forProgrammable Platforms Using the AntColony Optimization", In 13th Inter-national Workshop on Logic and Syn-thesis (IWLS'04) , 2004.
[3] T.Wiangtong, P.Cheung, W.Luk.Comparing Three Heuristic SearchMethods for Functional Partitioning inHardware-Software Codesign.Journalof Design Automation for EmbeddedSystems, 2002, 7 (6) :425～449.