（计算机科学与技术专业论文）面向rsoc的动态软硬件划分算法研究.pdf

硕l ：学位论文 摘要 以动态可重构技术为基础的可重构片上系统( r e c o n n g u r a b l es y s t e m o n - c h i p ， 简称r s o c ) 能够在系统运行时动态改变其内部部分逻辑功能，而不影响其他逻辑 的正常运行。因此，r s o c 系统能够在运行时根据系统资源情况动态选择任务的 不同实现方式一软件或者硬件实现方式，这在显著提高系统资源利用率的同时， 带来了一个新的问题一如何进行任务的软硬件动态划分( 即动态的软硬件划分 问题) ，其解决关键和难点是动态软硬件划分算法的设计。动态软硬件划分问题对 划分算法的求解质量和时间开销都提出了较高的要求，现有的动态软硬件划分算 法很难在这两方面做出权衡。本文针对现有动态软硬件划分算法的不足，主要做 了以下工作： 首先，提出一种自适应的动态软硬件划分技术。它的设计思想是通过量化待 划分问题的复杂度，动态调整软硬件划分算法的参数，以改变软硬件划分算法的 搜索方式。实验表明算法参数自适应调整策略提高了软硬件划分算法的搜索质量， 减小了其时间开销。 其次，提出了一种基于优先权的评价函数实现方法。在软硬件划分问题中， 评价函数被用来评价软硬件划分方案的优劣，其求解质量和时间开销对软硬件划 分算法产生很大影响。对比实验表明，本文的评价函数对软硬件划分方案做出了 较为正确的评价。 最后，提出一种新的软硬件划分算法：基于渐进式搜索空间平滑技术的离散 粒子群算法( s s s d p s o 算法) 。离散粒子群算法实现简单，运算速度快，局部寻 优能力强，但是全局寻优能力弱，算法很容易陷入局部最优。渐进式搜索空间平 滑技术通过拉平软硬件划分问题的搜索空间曲线，为离散粒子群算法创造一个良 好的搜索环境，有利于离散粒子群算法局部搜索能力的发挥。渐进式搜索空间平 滑技术在应用时的一个难点是平滑操作的实现策略，对此，本文提出了基于调整 任务软件执行时间的平滑操作实现方法。实验表明，本文所提出的s s s d p s o 算 法能提高软硬件划分的求解质量，且算法运行较稳定。 关键词：可重构片上系统；动态软硬件划分；自适应；渐进式搜索空间平滑技术； 离散粒子群算法 面向r s o c 的动态软硬仲划分算法研究 a b s t r a c t r s o ci sb a s e do nt h ed y n a m i cr e c o n 矗g u r a b l et e c h n o l o g yw h i c hc a nc h a n g ep a r t o fi t sf u n c t i o nw h i l er u n n i n g s ot h es y s t e mb a s e do nr s o cc a ns w i t c ht h et a s k s i m p l e m e n t a t i o n ，t h a ti st os a y ，t h et a s kr u n n i n gi nt h eh a r d w a r em a yb es w i t c h e dt o t h es o f t w a r e s ot h ed y n a m i ch a r d w a r es o f t w a r e p a r t i t i o n i n g i s r e q u i r e d ，a n di t r e q u i r e sab a l a n c eo fp e r f o r m a n c ea n dq u a l i t y i no r d e r t oa d d r e s st h ep r o b l e mo ft h e d y n a m i ch w s wp a r t i t i o n i n g ，t h i st h e s i sd o e st h ef o l l o w i n gw o r k a tf i r s t ，a na d a p t i v eh w s wp a r t i t i o n i n ga l g o r i t h mi sp r o p o s e d t h ed e s i g ni d e a i st h a ta tf i r s tw es h o u l dq u a n t i f yt h ec o m p l e x i t yo ft h es p e c i f i cp a r t i t i o n i n gp r o b l e m ， a n dt h e nt h ep a r a m e t e r so ft h ea l g o r i t h ma r ea d ju s t e da c c o r d i n gt ot h eq u a n t i t a t i v e v a l u e s t h ee x p e r i m e n t ss h o wt h a tt h ea d a p t i v ea d ju s t m e n tt e c h n o l o g yc a ne n h a n c e t h ep e r f o r m a n c eo ft h ep a r t i t i o n i n ga l g o r i t h m t h e n ，an e we v a l u a t i o nf u n c t i o nb a s e do nt h ep r i o r i t yi sp r o p o s e da c c o r d i n gt o t h ef e a t u r e so ft h eh w sw p a r t i t i o n i n g i nt h ef i l e do fh w s wp a r t i t i o n i n g ，t h ea i m o ft h ee v a l u a t i o nf u n c t i o ni st oe v a l u a t et h er e s u l to ft h ep a r t i t i o n i n g e x p e r i m e n t s s h o wt h a tt h i se v a l u a t i o nf u n c t i o nc a ng e tar e l a t i v ef a i re v a l u a t i o nr e s u l t a tl a s t ，an e wh w s wp a r t i t i o n i n ga l g o r i t h m ( s s s d p s o ) i sp r o p o s e d t h e d i s c r e t ep a r t i c l es w a r m ( d p s o ) c a nb ei m p l e m e n t e de a s i l ya n dh a st h ea d v a n t a g eo f h i g hl o c a ls e a r c h i n ga b i l i t y h o w e v e ri tw i l lb et r a p p e di nt h el o c a lo p t i m u mp o i n t s b e c a u s eo fi t sp o o rg l o b a l s e a r c h i n ga b i l i t y t h e s i t u a t i o nc a nb e i m p r o v e db y c o m b i n i n g t h ep r o g r e s s i v es e a r c hs p a c es m o o t h i n gt e c h n i q u e ( s s s ) s s sc a nc r e a t ea g o o ds e a r c h i n ge n v i r o n m e n tf o rt h ed p s ob ys m o o t h i n gt h es e a r c hs p a c eo ft h e p a r t i t i o n i n gp r o b l e m o n eo ft h ed i f f i c u l t i e so fa p p l y i n gt h es s si sh o w t os m o o t ht h e p r o b l e m ss e a r c hs p a c e i nt h i st h e s i s ，w er e a l i z eah i g h q u a l i t ys m o o t h i n gm e t h o d b a s e do nr e d u c i n gt h ed i f f e r e n c e sb e t w e e ne v e r yt w ot a s k s e x p e r i m e n t ss h o wt h a tt h e p r o p o s e da l g o r i t h m c a n i m p r o v et h eq u a l i t y a n d p e r f o r m a n c eo ft h eh w s w p a r t i t i o n i n g k e yw o r d s ：r e c o n f i g u r a b l es y s t e m - - o n - c h i p ；d y n a m i c h w s w p a r t i t i o n i n g ； s e l f - a d a p t i v e ；p r o g r e s s i v es e a r c h i n gs p a c es m o o t h i n g ；d p s o i i i 硕f ：学位论文 插图索引 图1 1 传统嵌入式设计一2 图1 2 软硬件协同设计过程3 图2 1 软硬件划分技术流程一7 图2 2 动态可重构系统1 0 图2 3 支持动态软硬件划分的软硬件协同设计流程1 1 图3 1 简单d a g 图示例1 6 图3 2 影响算法性能的情形一1 7 图3 3 计算局部最优点数目1 9 图3 4 复杂度计算公式曲线图2 0 图3 5 软硬件划分流程2 1 图3 6 划分方案实例2 2 图3 7 两种不同的调度方案一2 2 图3 8 评价函数的伪代码一2 4 图3 9 循环3 的伪代码2 5 图3 1 0 各评价函数的求解质量比较一2 7 图3 1 1 各算法的时间开销2 8 图4 1 局部搜索算法3 0 图4 2 搜索空间平滑技术31 图4 3 渐进式搜索空间平滑技术3 2 图4 4 平滑操作3 3 图4 5 抛物线形状3 4 图4 6 划分结果3 8 图4 7 粒子结构3 8 图4 8s s s d p s o 算法流程：4 0 图4 9 算法找到最优解的概率4 3 图4 1 0 节点数为5 0 时的求解结果4 4 图4 1 1 节点数为2 0 0 时的求解结果4 5 图4 1 2 算法运行时间比较一4 6 图4 13s s s d p s o 与s s s d p s o 的时问开销比较4 6 面向r s o c 的动态软硬件划分算汜：研究 附表索引 表3 1 复杂度计算结果2 0 表3 2 评价函数计算的目标函数值2 7 表3 3 评价函数的运行时间2 8 表4 1 各算法找到最优解的次数一4 2 表4 2 各算法找到最优解的概率4 2 表4 3 各算法平均运行时间4 5 v i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得 的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人 和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由 本人承担。 作者签名：张够 日期：岬年月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论 文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：粥银 导师签名： 羡瓠 日期：柳习年6 月6 目 日期： 。1 年6 月6 日 硕l j 学位论文 1 1 研究背景 第1 章绪论 1 1 1 嵌入式系统的发展趋势 嵌入式系统渗透到人类生活中的各个角落，它被广泛应用于通信，消费电子， 航空航天，医疗仪器等领域，因此，嵌入式系统对功耗、成本、安全、性能、体 积等有比较严格的要求。目前，嵌入式系统种类繁多，非常复杂，但都涉及到了 硬件和软件两个方面：硬件主要有处理器、协处理器、存储器、接口控制器和其 他专用电路等；软件主要包括有设备驱动、嵌入式操作系统、板级支持包、协议 栈和其他程序等乜1 。近年来，嵌入式系统设计发生了很大的变化，呈现出以下 几个趋势。 ( 1 ) 随着信息技术，特别是计算机技术和i c 设计技术的迅猛发展，嵌入式系 统的处理能力有了巨大的进步。硬件方面，集成电路的长远发展使得单块芯片尺 寸越来越小，集成度越来越高，功能越来越复杂强大，s o c 的出现掀起了一场微 电子设计领域的革命阳3 ；软件方面，随着硬件处理能力的提升，软件系统也越来 越复杂，嵌入式操作系统，应用于嵌入式平台的复杂协议、算法和应用程序等都 得到了飞速的发展，形成了包括嵌入式操作系统、中间平台软件在内的嵌入式软 件体系们。 ( 2 ) 产品更新速度加快，设计周期缩短。由于信息产业日新月异，技术创新 性和实效性要求更加严格，在商业运作几近苛刻的环境下，系统、高效、可靠的 设计方法具有极大的研究价值。 ( 3 ) 设计要求由单目标走向了多目标，如系统吞吐量、成本、体积、功耗等1 。 嵌入式系统对于芯片的体积、功耗、成本等各方面都有较严格的限制，如何平衡 这些要求，达到综合性能的最优化，成为值得研究的问题。 ( 4 ) 异构s o c 得到了越来越多的应用，在一块异构s o c 上同时有软件处理模 块和硬件实现模块。设计人员有两种基本的实现方法来完成所需的功能，即软件 和硬件。软件手段是指通过运行在嵌入式微处理上的程序实现系统功能，而硬件 手段是指通过专用集成电路实现系统功能。这两种手段在性能、成本、功耗等方 面各有优劣，所以设计人员需要考虑各约束条件，以达到成本和性能、功耗的最 佳平衡。 ( 5 ) 可重构配置架构和器件( 如f p g a ) 得到了越来越广泛的应用，同时带来 了一些新的设计问题，如本文所需考虑的动态软硬件划分问题。传统软硬件划分 面向r s o c 的动态软硬件划分算法研究 方法往往针对的是静态参数的系统模型，如何满足系统运行时动态环境下的各项 要求，成为了基于可重构平台的系统设计难题哺3 。 1 1 2 软硬件协同设计概述 嵌入式系统平台的发展引起了系统设计方法的变革。传统的系统设计方法一 般将系统的设计分为两个阶段：电路级硬件开发和系统级软件开发。硬件设计和 软件开发往往是相对独立运行的，分别由硬件设计人员和软件开发工程师来完成。 在整个设计过程中，通常采用硬件优先的原则首先进行硬件设计，然后在硬件设 计平台上进行软件设计，如图1 1 所示： 图1 1 传统嵌入式设计 由于硬件设计人员在硬件设计过程中缺乏对软件架构和实现机制的清晰了 解，硬件设计工作往往带有一定的局限性。在系统优化时由于设计空间的限制， 只能改善软件和硬件各自的性能，不能对系统进行综合优化，得到的最终设计方 案很难充分利用硬软件资源，难以适应现代复杂的系统设计任务。传统设计方法 的局限性已经成为限制现代嵌入式系统充分发挥性能的障碍之一，因此软硬件协 同设计技术是嵌入式系统设计的一个趋势。 对于软硬件协同设计，学术界还没有一个统一的定义，但是大部分学者认为 应该具备的特征主要有： ( 1 ) 在系统的层面上，必须有一个跨界面、统一的工具进行系统集成开发和 优化。 ( 2 ) 能够提供软硬件协同仿真的能力，并能进行软硬件协同验证聃。 软硬件协同设计是一种非常灵活的设计策略，软硬件协同设计技术强调软件 和硬件的设计丌发是一个并行和相互反馈的过程，它是指在系统目标要求的指导 下，通过综合分析系统软硬件功能及现有资源，最大限度地挖掘系统软硬件资源 之间的并发性，协同设计软硬件体系结构，使系统能够工作在最佳工作状态，以 硕i ：学位论文 获得满足综合性能指标的最佳解决方案，。 作为一种全新的设让思想，软硬件协同设计最主要的工作是协调软件和硬件 这两个既相互独立又相互依赖的部分阳1 。在设计过程的各个阶段，还要考虑系统 性能、成本、功耗等方面的权衡，合理的分配系统性能，并且利用计算机辅助设 计工具进行设计综合和功能仿真等。软硬件协同设计在一个更高的设计层次上增 大了设计覆盖的范围，提高了系统总体性能，并且能大大缩短系统设计周期。 软硬件协同设计过程一般分为系统描述、软硬件划分、软硬件部件及接口的 综合以及系统集成等步骤，其基本思路如图1 2 所示n 引。 图1 2 软硬件协同设计过程 ： 首先，系统设计人员通过一个抽象统一的模型对系统的各个功能模块及它们 之间的关系进行描述；然后，在这个基础上利用软硬件划分算法对整个系统进行 软硬件划分，将不同的功能模块映射到软件实现或者硬件实现；在完成软硬件划 分后，分别由软件开发人员和硬件开发人员完成软件模块、硬件模块、软硬件接 口模块；最后，系统设计人员对整个系统进行统一的协调仿真和综合实现。在整 个软硬件协同设计过程中，软硬件划分是决定系统性能的关键环节旧1 。 1 1 3 课题来源 本文课题背景为国家8 6 3 项目面向可重构片上系统的过程级动态软硬件划 分研究，该项目的目标体系结构为可重构片上系统( r s o c ) 。我们通过在r s o c 上配置i p 核来实现系统功能，其中，处理器i p 核( 如p o w e r p c ) 具有指令处理 能力，其他i p 核则相当于是硬件处理单元，这样就形成了一个同时拥有软硬件处 理能力的异构环境。基于r s o c 的系统设计要求开发人员必须同时理解系统的软 件结构和硬件底层原理，这对系统设计人员提出了很高的要求，且容易产生系统 一3 一 面向r s o c 的动态软硬件划分算法研究 b u g 。对此，该项目提出了建立面向可重构片上系统的透明编程模型，统一封装 和管理各种软硬件资源，为设计人员提供一个统一的软硬件过程描述方法，使得 可重构片上系统的开发对用户透明。然后在编程模型的基础上，不仅能够形成一 套全新的动态软硬件划分设计流程和方法，从理论上解决可重构片上系统开发对 用户不透明和自动化程度不高的问题，还能够实现一套软硬件协同函数库和完整 的可重构片上系统开发工具包，具备良好的实用价值。 要达到以上目的，有几个关键问题需要解决： ( 1 ) 需要建立一个透明编程模型，屏蔽底层技术实现细节，为用户提供一个 统一的函数接口，在操作系统和辅助硬件的支持下，用户可以如同访问一个普通 的软件函数一样去使用硬件资源。 ( 2 ) 需要解决过程级软硬件通信与同步问题，要求在保证过程语义正确性的 基础上，为微处理器上软件过程与可重构硬件上硬件过程提供并行运行支持。 ( 3 ) 可重构资源的管理，包括了i p 核的动态可重构配置，片上系统资源的监 控，硬件任务的调度、放置等问题。 ( 4 ) 动态软硬件划分算法的设计。全自动的软硬件协同设计工具要求软硬件 划分算法能够动态的根据系统运行时信息进行软硬件划分，这对算法的效率和时 间开销提出了较高的要求。 1 2 研究目标 软硬件划分是一个约束优化问题，属于n p 难题。传统的静态软硬件划分算 法只需要在系统设计阶段根据抽象的系统信息进行软硬件划分，并不考虑系统运 行时的准确的系统信息。本文的课题项目是面向可重构片上系统的软硬件协同设 计研究，它要求系统在运行时能够动态的对任务进行软硬件切换，也就是说，一 个在微处理器上运行的任务在下一次有可能会在硬件模块上运行。这就要求软硬 件划分算法能够根据系统运行情况进行决策，选择需要转换到软件或硬件的过程 ( 函数) 。因此，基于片上可重构系统的软硬件划分问题中，动态软硬件划分是一 个较优的选择，“动态”要求软硬件划分算法快速高效，能很好的支持面向动态可 重构系统的协同设计。本文的主要研究目标就是面向可重构片上系统，提出一个 满足其要求的动态软硬件划分算法。 1 3 主要工作 本文面向可重构片上系统的动态软硬件划分技术，对软硬件划分问题进行了 深入的研究，主要工作可分为三个方面： ( 1 ) 针对动态软硬件划分问题的特点，以d a g 图作为系统描述工具，提出自 硕l j 学佗论文 适应的动态软硬件划分技术。自适应的动态软硬件划分技术是指通过量化待划分 问题的复杂度，自适应调整软硬件划分算法的参数，以改变软硬件划分算法的搜 索方式。 ( 2 ) 软硬件划分算法在运行过程中会得到一些中间解( 即划分方案) ，每一个 中间解都通过评价函数对其质量进行评价，以指导划分算法的搜索方向。本文在 d a g 图的基础上，提出一种基于优先权的评价函数。 ( 3 ) 提出了一种新的软硬件划分算法：基于渐进式搜索空间平滑技术的离散 粒子群算法( s s s d p s o 算法) 。渐进式搜索空间平滑技术的应用难点是平滑操作 的实现策略，对此，提出了一种基于调整任务软件执行时间的平滑操作实现策略。 1 3 本文组织结构 本文余下部分的内容包括： 第2 章：软硬件划分技术概述。首先，详细介绍了软硬件划分技术及其三个 关键问题：系统描述、粒度选择和软硬件划分算法，并详细介绍和分析了国内外 相关研究；然后，介绍了最新的动态可重构技术以及面向r s o c 平台的动态软硬 件划分技术的基本原理和研究状况。 第3 章：针对面向r s o c 的动态软硬件划分问题的特点，以d a g 图作为软硬 件划分的系统描述工具，提出种自适应的动态软硬件划分技术。自适应的动态 软硬件划分技术能根据待划分问题的复杂度自适应调整软硬件划分算法参数。最 后，重点介绍了评价函数及其实现方法。 第4 章：提出了一种新的软硬件划分算法。首先，分别对渐进式搜索空间平 滑技术和离散粒子群算法做了介绍；然后，在此基础上提出了一种新的动态软硬 件划分算法：基于渐进式搜索空间平滑技术的离散粒子群算法( s s s d p s o 算法) ； 最后，介绍了s s s d p s o 算法自适应调整参数的方法。 面向r s o c 的动态软硬件划分算法研究 第2 章软硬件划分技术概述 2 1 传统静态软硬件划分技术 2 1 1 软硬件划分问题定义 软硬件划分是软硬件协同设计的核心环节，直接决定了设计结果的优劣。软 硬件划分的目的是在满足系统各约束条件的前提下决定系统的各个功能模块的实 现方式，即是采用硬件实现，还是软件实现，使得系统能达到既定的优化目标。 硬件实现是指利用目标体系结构中的硬件专用集成电路，各种i p 模块，硬件加速 器等硬件资源处理各个功能子功能模块，并确定它们之间的物理连接方式；软件 实现则是指利用目标体系结构中的微处理器以指令的方式处理系统的各子功能模 块。设有n 个待划分的子功能模块，共有2 n 种划分组合，在这些划分方案里有 一个方案是最优的，它不但能满足系统在成本、资源等方面的约束条件，而且能 使系统在性能、功耗等方面达到最优。软硬件划分的目的就是找到或尽量找到这 个最优的划分组合，因此软硬件划分是一个获取最优组合的系统优化问题，属于 典型的组合约束优化问题，属于n p 难问题n 。 软硬件划分问题可以用一个四元组来定义：领x ) ，g ( x ) ，x e x ，s 。火x ) 表示目 标函数，如系统时间性能等；9 0 ) 表示约束条件，如硬件面积等；x 表示问题的解 ( 即划分方案) ，划分方案的组合空间是有限的，所以x e x ，x 代表组合数；s 表 示任务参数集，s = ，s f 表示待划分任务的参数，聆表示任务数目。 软硬件划分的目标函数和约束函数一般与具体应用相关，如航天航空、军事 应用等领域要求系统具有良好的安全性、稳定性和抗干扰能力；消费电子等民用 领域要求成本低廉、功耗低；很多专业领域要求运算速度快等。设计人员在进行 系统设计时要根据应用的领域确定一个或多个优化目标，并以该目标为优化原则 指导系统设计。 传统的软硬件划分技术有一个成熟的流程。 s t e p l ：进行系统描述，将软硬件划分问题描述成一个统一的计算模型，这样 软硬件划分问题被抽象表示成一个数学问题。 s t e p 2 ：确定软硬件划分的粒度，即待划分任务的规模大小。 s t e p 3 ：软硬件划分算法获取目标函数火x ) 、约束条件9 0 ) 、任务参数集s 等 系统描述信息，计算出划分方案。 s t e p 4 ：系统根据划分方案将不同的功能子模块映射到不同的处理单元。 硕f 学位论文 整个传统软硬件划分流程均在系统设计阶段进行，在进行软硬件划分时，每 个待划分任务的参数s ，都是预先通过实验测定的，整个流程如图2 1 所示。 图2 1 软硬件划分技术流程 为了保证得到较优的划分方案，除了选择一个合适的软硬件划分算法，还需 要解决好系统描述、粒度选择这两个关键问题。 2 1 2 系统描述 系统描述是指通过将系统划分为互连的模块，每个模块都执行功能相对独立 的特定行为，并确定模块的互连关系和接口标准，完成系统的结构模型描述。这 时的描述并不涉及任何有关系统具体如何实现的细节，甚至不涉及哪些模块是硬 件，哪些模块是软件。软硬件划分是在系统描述的基础上进行的，因此它对最后 的设计结果起着非常重要的影响。嵌入式系统不论从结构到功能都千差万别，要 从中提取通用的系统描述模型，是比较困难的。因此在对实际系统进行描述的时 候，没有必要也不可能把所有的有关因素都考虑进去，应该根据问题的实质选择 矛盾的主要方面，力求在满足一定准确度的前提下，尽可能采用简洁的形式化模 型描述系统。目前常见的系统描述工具都被用来进行软硬件协同设计的系统描述。 文献 1 2 将系统功能集中到p e t r i 网的迁移上，从而将p e t r i 网直接作为划分 模型，并利用了p e t r i 网的不变量分析技术求出系统的关键路径作为系统性能评估 的依据。 文献 13 1 4 利用任务图作为系统描述工具，任务图的节点表示待划分的任 务，边表示任务之间的依赖关系。任务图的优点是形式简洁，有利于软硬件划分 算法的设计。 有限状态机常被用来描述控制系统，可以很方便的表示状态与状态之间的转 换，但是如果系统的节点数超过一个量时状态数就会呈指数级增长，出现状态爆 炸现象n 引。p o l i s 系统采用了抽象协同设计有限状态机，并在有限状态机中采用 面向r s o c 的动态软硬件划分算法研究 了抽象化的全局异步局部同步完成了系统的设计n 引。 数据控制流图可以方便的描述控制步、数据流和并发等概念，通常用于高层 次综合工具。牛亚问等人对层次化数据控制流图h c d f g 进行了扩充，通过引入 内存访问节点来表示程序中的并发结构，为软硬件划分提供了更加精确的信息 1 6 o c h o n l a m e t h 等人最先在软硬件协同设计中基于约束的设计方法引入u m l 语 言，给软硬件协同设计提供了一个良好的面向对象的设计方法n8 1 。文献 1 9 2 0 3 则进一步发展了u m l 语言在软硬件协同设计中的应用。 2 1 2 粒度选择 在软硬件划分问题中，每个待划分任务是作为一个整体参与划分，待划分任 务的大小叫做粒度。待划分任务可以是大规模的，例如整个i p 核，或者是一个函 数、过程等，这样的划分规模一般称为粗粒度；如果划分对象是程序语句，语句 块等较小的单位，则是细粒度。粗粒度和细粒度各有优劣，粒度的选择需要根据 系统设计要求来做出权衡。在粗粒度的情况下，划分对象个数少，可以显著提高 划分算法的速度，但是由于没有充分挖掘待划分任务的内部细节，不利于整个系 统的优化；在细粒度情况下，划分方案的质量得到了提高，但是划分对象的数目 会呈指数级增长，大大的增大了划分算法的搜索空间，使得划分算法的速度下降。 因此，必须根据目标硬件体系结构和整个系统的要求选择一个合适的粒度大小。 已有的粒度选择方法可以从总体上分为固定粒度和支持粒度变换两种方法。 固定粒度是在划分之前就选择好粒度的规模大小，它实现简单，速度快，目前绝 大多数的软硬件划分都是基于固定粒度。c o s y m a 系统采用了基本块作为划分对 象，其粒度级别为基本块级，也可以看成是细粒度的乜。p a ih c h o u 等人在c h i n o o k 系统中采用了粗粒度的固定粒度方法，成功应用于嵌入式系统的设计心2 j 。j m a d s e n 等在l y c o s 系统中把一个或几个基本块的组合作为划分对象，其粒度介 于基本块级和控制结构级之间瞳3 l 。 固定粒度的方法在整个软硬件协同设计中粒度的规模大小都是固定不变的， 这不适合基于i p 核的s o c 设计。由于在s o c 中采用了大量不同功能的i p 核，不 同i p 核的功能有可能会有交叉甚至包含的情况。比如i p 核a 用于实现h 2 6 4 视 频文件的解码，它包含了h 2 6 4 解码所需要的熵解码、反量化以及d c t 变换等多 种功能，而i p 核b 则专门用于d c t 变换。因此，对于基于i p 的s o c 设计，固 定粒度无法充分发掘不同i p 核配置的灵活性，对此，研究人员提出了支持粒度变 换方法。支持粒度变换主要有静态粒度变换和动态粒度变换两种方式。静态粒度 变换是在软硬件划分之前通过分析系统的特征形成一个粒度选择方案，该方案在 随后的整个软硬件划分过程中都保持不变。文献 2 4 通过分析待划分任务之间的 硕 ：学位论文 串行度，共同访问者数等因素决定是否将它们结群参与划分，是一种比较典型的 静态粒度变换方法。文献 2 5 则在初始阶段建立一个细粒度的粒度方案，然后通 过将不同任务划入一个集合参与划分，实际上和文献 2 4 中基于结群搜索的静态 粒度选择方法类似。静态粒度变换方法虽然比固定粒度有了很大进步，但是由于 它在软硬件划分之前就已经确立了粒度方案，在实际应用中系统的实际情况和预 测情况常会有一个误差，可能会导致粒度选择不符合软硬件划分的需要。1 9 9 6 年， j o r gh e n k e l 等人提出了动态粒度选择的思想，动态粒度变换能够在软硬件划分时 动态进行粒度变换心钊。2 0 0 5 年，吴强等人则发展了这种思想，提出了一种新的基 于层次化数据流图的粒度变换方法，他们通过以层次化节点为中介，进行合并和 展开操作来实现了粒度变换，同时在这个过程中满足一定的约束要求以保证变换 前后的系统在形式和功能上保持一致心7 1 。目前，支持粒度变换方法还处在研究阶 段，还很难得到实际应用。 总之，粒度选择的各种方法都有其优点和局限性，在进行软硬件划分之前， 设计人员应充分的利用系统的特性和应用需求，选择合适的粒度方案。 2 2 面向动态可重构系统的动态软硬件划分 2 2 1 动态可重构技术介绍 可重构技术是指在一个系统中，其软硬件功能模块能根据变化的数据流或控 制流对系统结构和算法进行重新配置，支持可重构技术的器件一般称为可重构器 件。在传统的处理运算器件中，微处理器只能实现软件指令，运算速度依赖于处 理器的主频且指令只能串行处理，速度有限；硬件a s i c 单元虽然运算快，但是 其功能固定，不够灵活。可重构器件鉴于两者之间，既有a s i c 的速度又具有微 处理器的灵活性。以f p g a 为例，当系统需求改变时，通过改变f p g a 的逻辑功 能就能实现新的需要。但是目前的可重构系统都是基于静态可重构技术，即可重 构器件只能被配置一次，其功能在系统运行过程中不能再改变，这会导致浪费系 统资源的情况出现。举一个极端的例子，当系统在运行过程中，不再需要可重构 器件提供的功能后，可重构器件实际上就被闲置，不再起作用。 为了充分发挥可重构器件的作用，x i l i n x 公司推出了支持动态可重构的f p g a 产品，该产品能够在不影响系统正常运行的前提下，在系统运行时自动对全部或 者局部的逻辑功能进行修改，且修改后的逻辑功能能够和未修改的部分一起正常 工作。动态可重构技术能够大大提高系统资源的利用效率，是可重构技术的发展 热点。动态可重构技术根据重构面积的不同分为全局重构和局部重构。全局重构 是指一次性对器件进行全部的重新配置，在配置过程中，必须专门安排一个存取 区域用于存放中间计算结果；部分重构则只对系统的部分区域进行重新配置，且 一9 一 面向r s o c 的动态软硬件划分算泣研究 在配置过程中其他区域不受影响，部分重构技术大大缩短了重构时间。总之，动 态可重构技术提高了系统的灵活性和资源利用率，但是也对传统的软硬件划分技 术提出了挑战，对此，研究人员提出了动态软硬件划分技术。 2 2 2 动态软硬件划分技术 因为可重构器件可配置资源的有限性，运行于动态可重构片上系统( r s o c ) 的i p 核有已被配置和没有配置两个状态。见图2 2 所示，在系统的某个时刻，i p 核a 和c 在f p g a 中被配置运行，i p 核b 由于资源限制没有被配置。 配置区 配置文件 存储区 l p 核ai p 核c l p 核b 图2 2 动态可重构系统 在图2 2 示例中，i p 核b 由于要等待可配置资源而处于挂起状态，而此时微 处理器没有指令运行，但是i p 核b 要实现的功能仍然只能由i p 核b 实现，而不 能由微处理器执行。在这种情况下，硬件处理资源( f p g a ) 处于紧张状态，而 软件处理资源( 微处理器) 则长期处于闲置状态，系统硬件资源没有被充分利用。 传统软硬件划分技术的划分结果是在系统初始化阶段就已经产生，在系统以 后的运行过程中不再改变。一个功能子模块一旦被划分到硬件实现，以后就只能 由硬件单元实现，也就是说软硬件划分方案是静态的，所以传统软硬件划分技术 又叫静态软硬件划分技术。动态可重构技术的出现使得系统的功能状态是动态变 化的，软硬件划分技术必须能实时的检测系统的状态，动态改变划分方案，这要 求软硬件划分技术具有处理动态问题的能力。 如图2 3 所示，支持动态软硬件划分的软硬件协同设计流程分为系统设计和 系统运行时两个阶段。在系统设计阶段，采用与传统软硬件划分技术相同的设计 流程；在系统运行阶段，由动态软硬件划分实时获得软硬件划分方案，直到系统 运行完毕。因此，软硬件划分算法需要运行多次，每次都能针对系统资源利用状 况对划分方案做出新的凋整，当然此时待划分任务集也可能发生了变化。 静态软硬件划分和动态软硬件划分对软硬件划分算法提出了不同的要求，其 原因主要有以下两点。 硕j ：学位论文 ( 1 ) 动态软硬件划分算法本身是作为一个软件任务运行在系统上，因此，它 要求运行稳定，时间开销不能太大。 ( 2 ) 静态软硬件划分的系统信息领x ) ，g o ) ，p 是可以预测的，而在系统运行阶 段时某些任务参数，如任务调用次数等很难准确预测，因此，动态软硬件划分算 法要能充分考虑系统运行时的各种情况。 阶段 系统运行阶段 图2 3 支持动态软硬件划分的软硬件协同设计流程 2 2 3 动态软硬件划分技术的研究状况 目前动态软硬件划分技术的研究并不是特别多，根据划分层次和粒度，可分 为两种思路。 第一种思路由g r e gs t i t t 等人在2 0 0 3 年设计自动化会议上提出，并在其后期 工作中不断发展心8 | 。其主要步骤为：1 利用专门的高速缓冲存储器记录软件程序 中循环执行的频度乜引；2 选择执行频度最高的循环，将其机器代码反汇编后提取 数据流图口0 1 ；3 在额外的微处理器上运行一个在线综合程序将数据流图综合为逻 辑电路，并配置到可编程器件上口引。该思路可以使设计人员无需考虑软硬件划 分，直接设计纯软件实现的应用系统，而由动态软硬件划分来决定实际的划分方 案，基准测试表明这一思路能有效提高系统性能，降低功耗乜引。因这种思路从底 层入手，直接对软件机器指令进行反汇编和在线综合，可以称之为指令级动态软 硬件划分方法。 第二种思路则是从高层着眼，把配置到可编程器件的硬件电路看作一种硬件 进( 线) 程，通过构建支持硬件进( 线) 程的操作系统，实现软硬件进( 线) 程 的相互迁移和切换，因此，可以称之为进( 线) 程级动态软硬件划分。文献 3 4 面向r s o c 的动态软硬件划分笄法研究 提出了一个面向可重构计算的实时操作系统，主要考虑提供配置控制接口。文献 3 5 提出一个面向可重构系统的操作系统的框架：o s 4 r s ；文献 3 6 详细讨论了 面向可重构系统的操作系统中硬件进程调度的在线布局问题；文献 3 7 设计了一 个称为b o r p h 的操作系统，利用u n i x 进程来表示硬件任务，并通过扩展u n i x 系统进程服务接口实现对硬件任务的支持；文献 3 8 提出采用p o s i x 标准的线程 模型描述软件和硬件任务，并通过增加相应硬件电路和操作系统服务实现对软件 和硬件线程运行及切换的支持。国内复旦大学的周博，邱卫东，彭澄廉研究了利 用软硬件多任务模型来降低软硬件进程迁移开销，并通过扩展“c o s i i 嵌入式操 作系统实现了一个原型系统口9 1 。 2 3 软硬件划分算法研究状况 无论是传统的静态软硬件划分技术还是动态软硬件划分技术都需要一个高效 稳定的软硬件划分算法。国内外学者在这个问题上进行了很多研究并提出了不少 有效的方法，这些方法各有自己的特点，总的来说可以分为以下几类。 1 规划类算法 软硬件划分问题可以归结为一组不等式组作为约束条件，几个函数表达式作 为目标函数的规划问题，据此，p v k n u d s e n 等提出的基于动态规划的软硬件划分 算法h 别；r a l f n i e m a n n 等提出了整数线性规划模型n ；b e n d e r 等建立了基于混合 整数线性规划的分布式系统软硬件划分算法等h 副。 规划类算法最主要的缺点是计算量太大，算法运行速度慢。例如整数规划算 法的缺点是计算复杂度高，内存开销大，在用整数线性规划方法求解时，其计算 时间与问题规模呈指数关系；动态规划算法则需要很大的存储空间，p v k n u d s e n 的算法在运行时需要维持一个节点和成本的规划表，其规模随节点的增加呈指数 上升。 ， 2 构造式算法 使用构造式算法进行软硬件划分的有：p o t k o n j a k 和r a b a e y 等人提出的类似 经典任务指派问题的a s i c 选择算法h3 i ；s r i n i v a s a n 和j h a 提出的具有容错性实时 分布式系统的软硬件划分算法等h 4 1 。 构造式算法的优点是通过构造一种能产生可行解的启发式规则，以找到最优 解或者近似最优解，求解效率较高。但是构造式算法最重要的问题是如何构造出 合适的启发式规则，而此规则的有效与否高度依赖具体的划分问题和设计者的经 验，当求解问题比较复杂时，难以构造出合适的规则。 3 启发式算法 a m i nf a r m a h i n i f a r a h a n i 和m e h d ik a m a l 等人利用离散粒子群算法进行软硬 件划分，他们首先构建一个任务图表示待划分任务集合，然后用每个粒子表示一 硕j j 学位论文 个划分方案，通过一个迭代公式，使得每个粒子都趋向于一个局部最优点，然后 在其中找到较优的划分结果n 驯。z o uy 和z h u a n gz 在基础调度块图( b s b ) 上利用 遗传算法解决了软硬件划分问题，算法在稳定性、运行效率和解质量等方面表现 良好h 引。p e t r ue l e s 于2 0 0 4 年将模拟退火算法与禁忌搜索相结合的软硬件划分应 用于软硬件划分引。吴强提出了一种搜索空间平滑技术与模拟退火相结合的算 法，算法表现良好h 利。熊志辉等提出遗传算法和蚂蚁算法动态融合的软硬件划分 h 引。利用了蚂蚁算法正反馈、高效、收敛快的