多选择软硬件划分问题的启发式算法比较

软硬件协同设计作为嵌入式系统开发的重要技术,随着嵌入式系统的广泛应用变得越来越重要。软硬件划分是软硬件协同设计的关键环节,是经典的组合优化问题,已被证明是NP完全问题。对于一个给定的任务而言,由于在硬件实现中存在并行执行的潜力,具有不同面积的硬件可以提供不同的执行速度。这样,一个任务根据可利用的硬件面积可以有多种硬件实现方式。现有的软硬件划分方法通常仅仅考虑单一的硬件实现方式,却忽略了多种选择的硬件实现方式。对于多选择的软硬件划分问题,分别使用模拟退火算法和遗传算法,提出了可行性的解决方案。并与禁忌搜索算法进行比较,寻找多选择软硬件划分问题的相对较好的启发式算法。实验结果表明,在求得的解的质量方面,禁忌搜索算法相比于其他两种算法而言是最好的;在获得较好解的速度方面,模拟退火算法和遗传算法要比禁忌搜索算法快得多。     

支持过程级动态软硬件划分的RSoC设计与实现

目前,可重构计算平台所支持的动态软硬件划分粒度多处于线程级或指令级,但线程级划分开销太大,而指令级划分又过于复杂,因此很难被用于实际应用之中。本文设计并实现了一种支持过程级动态软硬件划分的可重构片上系统(RSoC),提出了一种过程级硬件透明编程模型,给出了过程级的硬件封装方案;在分析软硬件过程根本区别的基础上,针对硬件过程开发了专门的管理模块,并利用部分动态重构等技术,实现了硬件过程的动态配置。实验表明该系统能够较好的支持过程级的动态软硬件划分,实现了节省资源、简化设计,提高性能等目的。     

搜索空间平滑技术在软硬件划分中的应用

软硬件划分问题是软硬件协同设计的重要问题之一,它涉及到系统建模,划分算法和划分方案评价等问题,其中划分算法设计是关键点。以提高系统时间性能为目标,利用任务流图构造系统模型,在其上实现了基于优先权的评价函数,提出了搜索空间平滑技术与离散粒子群算法相结合的软硬件划分算法,并且解决了两者的融合问题,并能根据系统信息动态适应调整算法参数。实验结果表明,算法时间开销稳定,求解质量较高。     

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

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

基于混沌PSO的动态可重构系统软硬件划分

软硬件划分是动态可重构系统软硬件协同设计中的关键技术之一,如何兼顾划分效率和划分效果,达到两者的最佳结合是软硬件划分的主要问题.在考虑动态部分重构及重构延时等特征的基础上,提出一种微粒群优化算法与混沌优化算法相结合的混沌微粒群软硬件划分方法.该算法使用基于实数编码的微粒群优化算法执行全局搜索,再根据搜索结果采用混沌优化算法执行局部搜索,具有较强的全局搜索和跳出局部最优的能力.仿真实验表明,该算法比标准微粒群算法和遗传算法具有更好的有效性和快速性,能够有效地实现应用任务图到可重构系统的时空映射.     

基于权重可变免疫算法的动态可重构任务划分

基于FFGA的动态可重构系统能够在系统运行期间通过动态调整硬件资源来适应应用问题,从而满足嵌入式系统对性能、灵活性和成本越来越严格的要求.系统可动态加载配置文件的特点给系统软硬件任务的划分带来了新的问题.在充分考虑动态可重构系统特点的基础上,通过动态改变目标函数权重系数来适应可重构的变化,并运用于免疫算法对系统软硬件任务进行划分.实验结果表明,提出的划分方法除了能更贴近实际的系统外还具有较高的性能.     

基于改进0-1动态规划的软硬件划分算法研究*

软硬件划分已被证明是NP完全问题,大多数研究主要集中在寻找各种快速的近似算法,常见的有爬山法、遗传算法、模拟退火、禁忌搜索等.这些算法大多只能处理小规模问题,而且是单纯从算法角度来研究软硬件划分问题,并没有考虑系统成本.以软硬件协同函数库为统一抽象模型,将系统执行时间、系统成本以及硬件面积等因素融入到0-1动态规划算法...     

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

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

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

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

SOC软硬件划分系统中的关键算法

设计并实现了SOC软硬件划分系统,搭建了软硬件协同设计的平台并描述了软硬件协同设计的流程。运用多目标遗传算法对目标系统的价格、功耗、速度进行优化,采用了基于Pareto支配的适应值赋值、精英保持和密度计算截断操作的方法进行多目标寻优。针对单任务图描述多CPU系统结构的不足,提出采用多任务图来描述的方法,并提出了MTLS性能评估算法,验证系统软硬件划分的优劣。在对比实验中将NSGA2算法运用到本系统中,结果证明论文的多目标寻优算法获得的非支配解80%比NSGA2的非支配解优。     

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完全问题。将一类软硬件划分问题看作变异的0-1背包问题,在求解背包问题的算法基础上构造出软硬件划分问题的优质启发解。此外,采用禁忌搜索(Tabu Search)算法对求得的启发解进行改进,在软件开销和通信开销满足一定约束的条件下,使得硬件开销尽可能小。实验结果证明,所提算法对当前最新算法的改进最大可达到28%。     

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 %.     

A Novel Hardware/Software Partitioning Method Based on Position Disturbed Particle Swarm Optimization with Invasive Weed Optimization

With the development of the design complexity in embedded systems, hardware/software (HW/SW) partitioning becomes a challenging optimization problem in HW/SW co-design. A novel HW/SW partitioning method based on position disturbed particle swarm optimization with invasive weed optimization (PDPSO-IWO) is presented in this paper. It is found by biologists that the ground squirrels produce alarm calls which warn their peers to move away when there is potential predatory threat. Here, we present PDPSO algorithm, in each iteration of which the squirrel behavior of escaping from the global worst particle can be simulated to increase population diversity and avoid local optimum. We also present new initialization and reproduction strategies to improve IWO algorithm for searching a better position, with which the global best position can be updated. Then the search accuracy and the solution quality can be enhanced. PDPSO and improved IWO are synthesized into one single PDPSO-IWO algorithm, which can keep both searching diversification and searching intensification. Furthermore, a hybrid NodeRank (HNodeRank) algorithm is proposed to initialize the population of PDPSO-IWO, and the solution quality can be enhanced further. Since the HW/SW communication cost computing is the most time-consuming process for HW/SW partitioning algorithm, we adopt the GPU parallel technique to accelerate the computing. In this way, the runtime of PDPSO-IWO for large-scale HW/SW partitioning problem can be reduced efficiently. Finally, multiple experiments on benchmarks from state-of-the-art publications and large-scale HW/SW partitioning demonstrate that the proposed algorithm can achieve higher performance than other algorithms.     

基于MPSoC并行调度的矩阵乘法加速算法研究

矩阵乘法是数值分析以及图形图像处理算法的基础,通用的矩阵乘法加速器设计一直是嵌入式系统设计的研究热点。但矩阵乘法由于计算复杂度高,处理效率低,常常成为嵌入式系统运算速度的瓶颈。为了在嵌入式领域更好地使用矩阵乘法,提出了基于MPSoC(MultiProcessor System-on-Chip)的软硬件协同加速的架构。在MPSoC的架构下,一方面,设计了面向硬件约束的矩阵分块方法,从而实现了通用的矩阵乘法加速器系统;另一方面,通过利用MPSoC下的多核架构,提出了相应的任务划分和负载平衡调度算法,提高了并行效率和整体系统加速比。实验结果表明,所提架构及算法实现了通用的矩阵乘法计算,并且通过软硬件协同设计实现的多核并行调度算法与传统单核设计相比在计算效率方面得到了显著的提高。     

An efficient GPU-based parallel tabu search algorithm for hardware/software co-design

Hardware/software partitioning is an essential step in hardware/software co-design. For large size problems, it is difficult to consider both solution quality and time. This paper presents an efficient GPU-based parallel tabu search algorithm (GPTS) for HW/SW partitioning. A single GPU kernel of compacting neighborhood is proposed to reduce the amount of GPU global memory accesses theoretically. A kernel fusion strategy is further proposed to reduce the amount of GPU global memory accesses of GPTS. To further minimize the transfer overhead of GPTS between CPU and GPU, an optimized transfer strategy for GPU-based tabu evaluation is proposed, which considers that all the candidates do not satisfy the given constraint. Experiments show that GPTS outperforms state-of-the-art work of tabu search and is competitive with other methods for HW/SW partitioning. The proposed parallelization is significant when considering the ordinary GPU platform.     

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.     

Parallel Programming of Multi-processor SoC: A HW–SW Interface Perspective

For the design of classic computers the parallel programming concept is used to abstract HW/SW interfaces during high level specification of application software. The software is then adapted to existing multiprocessor platforms using a low level software layer that implements the programming model. Unlike classic computers, the design of heterogeneous MPSoC includes also building the processors and other kind of hardware components required to execute the software. In this case, the programming model hides both hardware and software refinements. This paper deals with parallel programming models to abstract both hardware and software interfaces in the case of heterogeneous MPSoC design. Different abstraction levels will be needed. For the long term, the use of higher level programming models will open new vistas for optimization and architecture exploration like CPU/RTOS tradeoffs.     

基于贪心算法和模拟退火算法的软硬件划分

软硬件划分是嵌入式系统设计过程中一个关键环节,已经被证明是一个NP问题。针对目前算法在进行大任务集下的软硬件划分时计算复杂度高、不能快速收敛,且找到的全局最优解的质量不佳等问题,提出一种基于贪心算法和模拟退火算法相融合的软硬件划分方法。首先将软硬件划分问题规约为变异的0-1背包问题,在求解背包问题的算法基础上用贪心算法构造出初始划分解;然后,对代价函数的解空间进行合理的区域划分,并基于划分的区间设计新的代价函数,采用改进的模拟退火算法对初始划分进行全局寻优。实验结果表明,与目前已有的类似改进算法相比,新算法在任务划分质量和算法运行时间两个方面的提升率最大可达到8%和17%左右,具有高效性和实用性。