基于约束紧迫度和反向调节算法的硬/软件划分

硬／软件协同设计的关键问题之一是硬／软件划分，本文提出了基于约束紧迫度和反向调节算法的硬／软件划分方法，在约束紧迫度算法中，首先根据时间紧迫度来决定节点是映射到硬件还是映射到软件，然后根据硬／软件面积的紧迫度选择节点的执行时间／面积，反向调节算法则是通过节点之间存在的松驰时间来对系统进行进一步的优化，实验表明，该算法在总体性能上要优于文献[18]中提出的MIBS算法。     

异构环境下基干松弛标记法的任务调度

提出了一种基于松弛标记法的任务调度算法（Relaxation labeling based task scheduling,RLBTS）,将任务映射到异构资源（处理器计算能力和链路的通信能力不同）上．松弛标记法善于处理大量的约束条件,其核心思想是结点的标签分配通常受该结点的邻居结点某些属性的影响．依据邻居约束关系,可以逐渐排除不相关因素,迅速缩小搜索空间．该算法统筹兼顾了任务执行的计算需求和通信需求问题,实验结果表明对于通信和计算需求都很高的任务和通信密集型任务,RLBTS不失为一种有效的调度算法．     

周期性实时任务LLF调度算法改进

为减少松弛度计算和系统调度次数,对周期性实时任务的最低松弛度优先(LLF)调度算法进行了改进。在系统处理过程中引入最低松弛度优先队列,当任务松弛度相同时,开始截止时刻早的任务靠近队首。在任务控制块(TCB)中引入预执行时间,任务被调度以后,如果没有更为紧迫的任务到达,任务执行到预执行时间结束才退出处理器。Matlab仿真试验表明,改进算法有效减少了周期性实时任务的松弛度计算次数和系统调度次数,提高了处理器的利用率。     

基于构件技术的元计算环境框架的任务分配与调度

本文从软件复用的角度对元计算环境进行了研究，提出了一个基于构件技术的元计算环境框架MefBC，并重点给出了基于此框架任务的分配与调度．在一般的元计算中，任务结点在其所有前驱结点执行结束后才能进行分配调度．本文则采用了动态调度方案，任务结点是根据其前驱结点的执行情况来分配调度到下一个计算结点的，并且任务结点的分配调度在其一前驱结点执行完毕时就开始，以实现计算跟通信的最大重叠，提高系统效率．     

无线传感器网络中一种有效的分布式簇划分算法

提出了一种快速有效的分布式簇划分算法，为每个节点设定一个初始时间，最先到期的节点成为簇头。考虑到簇头选举的合理性，时间衰减与节点连通度相关，并辅以随机化的方法消除时间同步对算法的影响。通过仿真验证该簇划分算法的有效性，并定量分析了通信半径与平均簇头个数的关系。     

一种基于单CPU单ASIC结构的软硬件划分算法

软硬件划分是软硬件协同设计中的关键问题之一。本文针对单CPU单ASIC结构嵌入式系统，提出了一种基于数据流图的划分算法。实验结果表明，该算法可以有效地解决软硬件划分问题，效率较高，对固定时间约束下硬件面积最小划分问题具有一定的实际意义。     

异构环境下基于松弛标记法的任务调度

提出了一种基于松弛标记法的任务调度算法(Relaxation labeling based task scheduling,RLBTS),将任务映射到异构资源(处理器计算能力和链路的通信能力不同)上.松弛标记法善于处理大量的约束条件,其核心思想是结点的标签分配通常受该结点的邻居结点某些属性的影响.依据邻居约束关系,可以逐渐排除不相关因素,迅速缩小搜索空间.该算法统筹兼顾了任务执行的计算需求和通信需求问题,实验结果表明对于通信和计算需求都很高的任务和通信密集型任务,RLBTS不失为一种有效的调度算法.     

上下文敏感的纵向传播算法

通过基于包含的指针分析在线优化技术中的纵向传播方法,改进基于调用图上下文敏感指针分析的环消除技术,提出一种上下文敏感的纵向传播算法。初始化约束图,在约束图中进行环探测及其合并,执行差异传播并循环处理复杂约束,直到一次调用纵向传播例程后图中所有结点指向集不变为止,从而得到图中各结点到其指向集的映射。应用CIL工具的实验结果表明,该算法能有效地对源程序进行上下文敏感的指针分析,与环消除技术相比,在分析大规模程序时具有更高的时间效率。     

带时间和资源约束的实例化过程模型验证方法

软件过程的性能是由软件过程模型和软件过程实例化两方面因素决定,如果对软件过程进行了不恰当的实例化,会导致成本超支、进度延期、甚至项目失败．已有的过程描述法不足以分析实例化过程模型,由于没有考虑实例化阶段的时间资源约束,语法结构正确的过程模型并不能保证过程执行的正确性．提出一种带时间和资源约束的实例化过程模型验证方法,为目前已有的s-TRISO／ML建模语言增加时间和资源约束属性,然后提出了从s-TRISO／ML模型转换成时间自动机的转换方法和实现算法,利用已有的分析工具Uppaal对转换得到的时间自动机的性质进行验证,得到一个合理的实例化模型,从而为真实的开发流程提供指导．     

考虑通信成本和硬件碎片利用的簇划分算法

针对面积约束下的可重构硬件任务划分问题,提出一种通信成本和硬件碎片利用的簇划分算法.根据簇划分算法的思想,在某一硬件面积的约束下,从待调度的就绪队列中节点依次划入到当前块,在划分过程中,若遇到不满足要求的节点就跳过,并继续搜索可划入到当前块且没有增加块间边数的节点.每划入一个节点就更新其后继的入度,如果入度为0且满足要求,将其直接划入;否则动态考查其前驱,如果前驱所需的面积满足规定的阈值,则将该节点后继和前驱一并划入到当前块.通过充分考虑节点权值、节点间的依赖度、层次小的节点优先划入等因素构造响应比函数,以动态地调整就绪列表节点的调度次序.实验结果表明,与簇划分算法和簇层次敏感划分算法相比,文中算法在划分块间非原始I/O次数、划分块数等方面均获得了较好的改进;在减少块间通信成本方面,该算法具有合理性和可行性.     

嵌入式系统的软硬件划分

嵌入式系统软硬件协同设计中的关键步骤之一是软硬件划分。现有的许多软硬件划分方法都试图捕获太多有关划分问题和目标结构的细节，可扩展性差。本文提出了一种简化的软硬件划分问题模型，这种简化模型能分别对不同的划分问题进行形式化定义。在此模型的基础上，本文给出了基于ILP的算法和遗传算法。实验结果表明，我们的遗传算法能有效地解决千万个节点规模的划分问题，并获得近似最优解。     

Algorithmic aspects for multiple-choice hardware/software partitioning

Hardware–software partitioning (HW/SW) divides an application into software and hardware. It is one of the crucial steps in embedded system design. For a given task, hardware with different areas may provide different execution speeds due to the potential of parallel execution in hardware implementation. Thus, one task may have multiple-choice in hardware implementation according to the available hardware areas. Existing HW/SW partitioning approaches typically consider only a single implementation manner in hardware, overlooking the multiple-choice of hardware implementations. This paper presents a computing model to cater for the HW/SW partitioning problems with the multiple-choice implementation in hardware. An efficient heuristic algorithm is proposed to rapidly generate approximate solution, that is further refined by a tabu search algorithm also customized in this paper. Moreover, a dynamic programming algorithm is proposed for the exact solution of the relatively small problems. Extensive simulation results show that the approximate solutions are very close to the exact ones, and they can be refined by tabu search to the solutions with the error no more than 1.5% for all cases considered in this paper.     

多选择软硬件划分问题的计算模型与动态规划算法

软硬件划分是软硬件协同设计的关键环节,划分的结果直接影响目标系统的设计质量。因此,对于一个给定的应用程序,为了使得目标系统快速执行且成本低廉,合理的划分策略十分重要。由于单个任务具有多种不同的硬件实现方式,与传统的单一硬件实现方式的软硬件划分问题相比,多选择的软硬件划分更能客观地反映现实应用。这导致问题的求解更具挑战性,它们已被证明是NP完全问题。基于多核处理器片上系统并针对任务图为二叉树的应用,建立了多选择软硬件划分问题的计算模型,并提出了解决该问题的动态规划算法。实验结果表明,当问题规模适中时,所提动态规划算法能够有效地获得精确解,并展示了算法的计算能力与硬件面积限制之间的关系。     

一种基于动态需求边界的混合关键级作业调度算法

把具有不同重要性的功能集成到一个共享平台上的混合关键级系统,是当前嵌入式系统发展的主要趋势之一.已有的混合关键级调度理论为了保证高关键级作业的完成,大多不支持关键级向下切换,在系统进入高关键级后直接放弃低关键级作业的执行,这对系统中作业集的整体完成率有负面影响.为了应对这一问题,把需求边界分析理论扩展到混合关键级作业系统中,提出了作业的动态需求边界函数,以矢量的形式记录系统在运行时需求边界函数的动态变化,并相应地提出了作业的混合关键级松弛时间与系统关键级松弛时间的概念.在此基础上,提出了一种基于动态需求边界的混合关键级作业调度算法CSDDB （criticality switch based on dynamical demand boundary）.该算法选择具有最小松弛时间的关键级作为执行关键级,在保证高关键级作业可调度的情况下,充分利用系统资源,尽可能地满足低关键级作业的执行.应用随机生成的任务集进行仿真实验,结果表明,与已有算法相比,CSDDB在系统关键级的保证与作业集整体完成率方面比现有算法有10%以上的提升.     

多核片上系统的高效软硬件划分及调度算法

软硬件划分与调度是软硬件协同设计的关键环节,是经典的组合优化问题。本文针对调度与软硬件划分问题提出一种高效的启发式算法。调度算法根据任务的出度及软件计算时间对任务赋予不同的优先级,出度越大,优先级越高,出度相同的情况下,软件计算时间越大,优先级越高。划分算法首先寻找关键路径,然后将关键路径上具有最高受益面积比的任务交由硬件去实现。每次迭代更新当前关键路径的调度长度及剩余硬件面积。继续循环,直到剩余的硬件面积不再满足关键路径上的任何一个软件任务所需的硬件面积的要求为止,这样使得硬件面积的使用率比较高。实验表明,该算法对已有算法的改进可达到38%。     

可重构系统中软硬任务划分方法研究

软硬件任务划分是可重构系统开发过程中的重要设计步骤,其划分结果直接影响到可重构系统的性能。目前的软硬件任务划分技术大多只考虑了对应用程序或算法的划分结果,忽略了FPGA在配置和通信时的开销,从而导致实际应用效果不理想。介绍了一种基于性能评估的软硬件任务划分方法,即通过对FPGA计算开销、配置开销、通信开销的预评估测试,结合改进的模拟退火算法得出可重构系统中的软硬任务划分结果。实验结果表明,该划分方法具有较好的划分效果和算法收敛速度。     

基于免疫算法的嵌入式系统软硬件划分方法

软硬件划分是嵌入式系统协同设计的关键问题之一。提出了一种划分模型，并通过改进的免疫算法解决了在多约束条件下软硬件划分的优化问题。在该免疫算法中，引入了免疫算子，通过从以往经验中提取疫苗，在生成子代过程中注入疫苗，使划分算法得到了优化。实验表明该算法具有较快的收敛速度，并且在总体性能上优于传统遗传算法。     

基于划分算法的SaaS寻址中断软件生成策略

针对软件即服务(SaaS)软件生成时所面临的Web服务和表述性状态转移(REST)接口难识别的问题,提出一种基于划分算法的SaaS软件生成方法。该方法采用划分算法将云计算系统中的各SaaS的功能进行划分,将各功能定义成一个节点,并定义各节点属性和计算各节点的相似度,以实现划分分类,从而提高功能搜索效率。在此基础上,根据需求变化实现功能寻址中断完成新的SaaS软件生成。最后通过在Amazon下的一个SaaS销售软件生成为例进行分析表明,该方法有效且可行。     

Finding optimal hardware/software partitions

Most previous approaches to hardware/software partitioning considered heuristic solutions. In contrast, this paper presents an exact algorithm for the problem based on branch-and-bound. Several techniques are investigated to speed up the algorithm, including bounds based on linear programming, a custom inference engine to make the most out of the inferred information, advanced necessary conditions for partial solutions, and different heuristics to obtain high-quality initial solutions. It is demonstrated with empirical measurements that the resulting algorithm can solve highly complex partitioning problems in reasonable time. Moreover, it is about ten times faster than a previous exact algorithm based on integer linear programming. The presented methods can also be useful in other related optimization problems.     

软硬件协同设计方法的研究

论述了嵌入式系统软硬件协同设计的一般方法，结合CORSAIR、COOL和POLIS 3种有代表性的软硬件协同设计系统，对系统描述、软硬件划分、软硬件协同综合等几个主要设计步骤进行了研究与分析，并提出了新的思路和方法。