嵌入式系统的软硬件划分

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

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

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

A hardware/software partitioning algorithm based on artificial immune principles

Hardware/software codesign is the main approach to designing the embedded systems. One of the primary steps of the hardware/software codesign is the hardware/software partitioning. A good partitioning scheme is a tradeoff of some constraints, such as power, size, performance, and so on. Inspired by both negative selection model and evolutionary mechanism of the biological immune system, an evolutionary negative selection algorithm for hardware/software partitioning, namely ENSA-HSP, is proposed in this paper. This ENSA-HSP algorithm is proved to be convergent, and its ability to escape from the local optimum is also analyzed. The experimental results demonstrate that ENSA-HSP is more efficient than traditional evolutionary algorithm.     

Efficient heuristic and tabu search for hardware/software partitioning

Hardware/software (HW/SW) partitioning is a crucial step in HW/SW codesign that determines which components of the system are implemented on hardware and which ones on software. It has been proved that the HW/SW partitioning problem is NP-hard. In this paper, we present two approaches for HW/SW partitioning that aims to minimize the hardware cost while taking into account software and communication constraints. The first is a heuristic approach that treats the HW/SW partitioning problem as an extended 0–1 knapsack problem. In the second approach, tabu search is used to further improve the solution obtained from the proposed heuristic algorithm. Experimental results show that the proposed algorithms outperform a recently reported work by up to 28 %.     

Issues in distributed timed model checking

In this work we present Zeus, a distributed timed model checker that evolves from the TCTL model checker Kronos [13] and that currently can handle backwards computation of reachability properties [2] over timed automata [3].Zeus was developed following a software architecture-centric approach. Its conceptual architecture was conceived to be sufficiently modular to house several features such as a priori graph partitioning, synchronous and asynchronous computation, communication piggybacking, delayed messaging, and dead-time utilization.Surprisingly enough, early experiments pinpointed the difficulties of getting speedups using asynchronous versions and showed interesting results on the synchronous counterpart, although being intuitively less attractive.     

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

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

基于Token选取的OpenStack单一平面网络建模方法

CPN形式化建模适合为包含大量并发、通信、同步共享行为的软硬件系统建立形式模型,并完成系统功能和性能等方面的行为分析。在传统的CPN建模中,token的选取采用穷举法,由此造成生成的token数量较多、CPN模型生成的状态空间相当庞大甚至状态空间爆炸等问题。针对上述问题,提出将符号执行与CPN建模相结合,并在CPN模型的执行过程中采用一种基于token选取的方法,进而得到CPN模型的状态可达图。通过对OpenStack云平台支持创建的单一平面网络进行CPN建模,针对传统方法和所提方法生成的状态空间,分析了其规模的变化,验证了所提方法的有效性。     

约束驱动与松弛时间消除相结合的硬/软件划分算法

硬/软件划分是硬/软件协同设计的关键问题之一．在分析了已经被提出的硬/软件划分算法中存在的问题之后，提出了一种基于约束驱动和松弛时间消除相结合的硬/软件划分算法．首先是获取结点面积—时间(A—T)曲线的方法，然后比较时间约束紧迫度与阈值的大小，决定结点是用硬件还是软件执行．硬/软件面积的约束紧迫度决定硬/软件执行面积，通过A—T曲线找出对应的执行时间．最后，消除结点之间存在的松弛时间进一步优化设计．     

New Model and Algorithm for Hardware/Software Partitioning

This paper focuses on the algorithmic aspects for the hardware/software （HW/SW） partitioning which searches a reasonable composition of hardware and software components which not only satisfies the constraint of hardware area but also optimizes the execution time. The computational model is extended so that all possible types of communications can be taken into account for the HW/SW partitioning. Also, a new dynamic programming algorithm is proposed on the basis of the computational model, in which source data, rather than speedup in previous work, of basic scheduling blocks are directly utilized to calculate the optimal solution. The proposed algorithm runs in O（n·A） for n code fragments and the available hardware area A. Simulation results show that the proposed algorithm solves the HW/SW partitioning without increase in running time, compared with the algorithm cited in the literature.     

嵌入式系统软硬件自动划分方法研究

软硬件划分一直是嵌入式系统软硬件协同设计中的难点,如果离开具体系统,单纯的软硬件划分,其性能很难评估。本文提出基于系统体系结构,应用遗传算法来进行多目标优化的软硬件自动划分方法。在具体设计中,使用数据流图对系统建模,采用邻接表进行个体编码,定义交叉、变异操作,同时引入小生境技术,保持解的多样性。该方法为嵌入式系统软硬件自动划分提供一种新思路。     

基于Hopfield神经网络和禁忌搜索的软/硬件功耗划分

在目前全球倡导“低碳经济”的背景下,随着嵌入式系统大量而广泛的使用,嵌入式软件功耗已成为嵌入式系统设计的一个关键因素,而软/硬件划分是嵌入式软件功耗优化的一种重要方法。首先在性能约束条件下,建立以嵌入式软件功耗为目标的软/硬件双路划分模型;然后,提出了一种基于离散Hopfield神经网络(HNN)和禁忌搜索(TS)融合的求解算法,采用离散Hopfield算法作为主算法能较快地获得可行解,使用禁忌搜索算法“禁忌”当前解而转移到目标函数的其他极小点,从而可跳出局部最优解而快速趋于全局最优解;最后,仿真实验表明,与同类算法相比,该算法不但具有搜索速度上的优势,而且求得全局最优解的概率更高。     

面向RSoC的过程级动态软硬件划分

软硬件划分作为可重构片上系统设计的重要技术手段,其结果直接影响到系统的性能。目前的软硬件划分大多只考虑从算法本身提高划分效果,忽略了划分结果的具体配置实现,导致划分效果很不理想。分析了预配置模型下的任务描述,给出了预配置调度优先级的计算方法,设计了一种预配置调度策略;针对软硬件划分与动态可重构的特点,提出并实现了一种结合预配置的软硬件划分算法,给出了一种评价软硬件划分方案优劣的方法。实验结果表明,该划分方法具有良好的划分效果。     

具有初始信息素的蚂蚁寻优软硬件划分算法

面向基于平台的系统芯片设计,提出具有初始信息素的蚂蚁寻优软硬件划分算法AOwIP．基本思想是：①利用基于平台的设计方法中已有参考设计的软硬件划分结果作为初始划分解,进行适当变换后生成初始信息素分布．②在所生成初始信息素分布的基础上,利用蚂蚁算法正反馈、高效收敛的优势寻求最优划分解．该算法利用基于平台的设计方法强调系统重用的优势,克服蚂蚁算法在求解软硬件划分问题时缺乏初始信息素的不足．实验表明,AOwIP算法有效提高了蚂蚁算法的最优解搜索效率．     

高效软硬件划分算法及其提升技术

软硬件划分是软硬件协同设计的关键环节,它决定系统中哪些组件由软件实现,哪些由硬件实现。软硬件划分问题已被证明是NP完全问题。将一类软硬件划分问题看作变异的0-1背包问题,在求解背包问题的算法基础上构造出软硬件划分问题的优质启发解。此外,采用禁忌搜索(Tabu Search)算法对求得的启发解进行改进,在软件开销和通信开销满足一定约束的条件下,使得硬件开销尽可能小。实验结果证明,所提算法对当前最新算法的改进最大可达到28%。     

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

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

基于遗传算法的可重构系统软硬件划分

在考虑动态部分重构及重构延时等特征的基础上,采用遗传算法及其与爬山算法的融合实现可重构系统软硬件任务的划分,并采用动态优先级调度算法进行划分结果的评价。实验表明,在可重构系统的资源约束等条件下,算法能够有效地实现应用任务图到可重构系统的时空映射。     

基于路径的软硬件划分算法

软硬件划分是嵌入式系统中的一个关键问题。本文给出了一种贪心算法来搜索问题的最优解。本算法未考虑相邻任务之间的通讯开销。实验结果表明，任务数目的多少对加速比影响不大，影响加速比的关键因素就是硬件的有效面积。     

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

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

Algorithmic aspects of area-efficient hardware/software partitioning

Area efficiency is one of the major considerations in constraint aware hardware/software partitioning process. This paper focuses on the algorithmic aspects for hardware/software partitioning with the objective of minimizing area utilization under the constraints of execution time and power consumption. An efficient heuristic algorithm running in O(n log n) is proposed by extending the method devised for solving the 0-1 knapsack problem. Also, an exact algorithm based on dynamic programming is proposed to produce the optimal solution for small-sized problems. Simulation results show that the proposed heuristic algorithm yields very good approximate solutions while dramatically reducing the execution time.     

一种基于遗传算法的硬件／软件划分方法

文中采用相邻块通信划分模型及由单处理器和专用硬件构件组成的目标结构,解决了硬件约束条件下系统执行速度的优化问题,与贪心算法相比,该方法可在合理的时间内为嵌入式系统寻找到满意的解决方案。