基于改进模拟退火算法的软硬件划分

软硬件划分是嵌入式系统协同设计中的关键问题,已经被证明是一个NP问题。模拟退火算法是解决该问题常用的启发式算法,但是其存在收敛速度过慢的问题。通过改进算法的扰动模型和退火进度,提出一种新的代价函数计算方法来提高它的收敛速度。实验结果表明,相对于基于经典的模拟退火算法和已有改进的算法,新算法运行时间大大减少,并且增大了找到近似最优解的概率。     

基于全局和声搜索的模拟退火算法改进

本文针对传统的模拟退火算法存在收敛速度慢的问题,采用全局和声搜索算法对其进行了改进,即在保持模拟退火原有机制的基础上,使用一个函数随机产生模拟退火算法的初始解,采用全局和声搜索算法中产生候选解的方法产生新解。该方法的优点在于保留中间最优解并及时更新,从而既保证了优化质量又提高了算法的搜索效率。最后,采用benchmark测试函数进行仿真,仿真实验结果表明,该方法在收敛速度及优化质量上都优于传统的模拟退火及其它算法,值得进一步研究。     

基于改进遗传与模拟退火融合的RISP软硬件划分

软硬件划分是可重构指令集处理器在软硬件协同设计中的关键问题,通过对比遗传算法和经典模拟退火算法的优缺点,提出改进遗传算法的适应度函数,同时将Tsallis接受准则引入到经典模拟退火当中;其思路是用遗传算法的结果来制约模拟退火算法产生的随机状态,然后由模拟退火的接受准则以及产生的随机状态函数对遗传算法的种群进行更新,从而找到全局近似最优解;实验结果证明,改进算法与单一遗传算法以及经典模拟退火算法相比,其收敛速度和适应度更好,找到全局近似最优解的概率更大。     

模拟退火算法在全局查询优化中的应用

在分布式环境下,全局查询的代价函数空间形状包含了很多局部最小状态,需要多次局部最优化才可以找到全局最小状态。模拟退火算法是目前发展较快的智能优化算法,是一种以概率l收敛于全局最优解的全局优化算法。文中讨论了全局查询优化的过程以及模拟退火算法在全局查询优化中的应用,并对算法进行了一些改进。     

模拟退火算法在全局查询优化中的应用

在分布式环境下，全局查询的代价函数空间形状包含了很多局部最小状态，需要多次局部最优化才可以找到全局最小状态。模拟退火算法是目前发展较快的智能优化算法，是一种以概率l收敛于全局最优解的全局优化算法。文中讨论了全局查询优化的过程以及模拟退火算法在全局查询优化中的应用，并对算法进行了一些改进。     

基于云环境的高效任务调度算法

高效的任务调度是云服务提供商高效处理业务并降低运营成本的关键。针对云环境下的任务调度问题,提出一种贪心模拟退火的新型算法。首先,利用贪心算法求出局部最优解,并用它来初始化所提新型算法的当前最优解及模拟退火算法的初始解;然后,采用模拟退火算法来不断更新当前最优解。实验结果表明,与传统调度算法相比,所提算法能够更快地达到全局收敛,并得到更加稳定的寻优结果,提高了寻优的质量和效率;同时,该算法不仅减少了总任务时间开销,而且使虚拟机的平均资源利用率稳定在99%以上,负载也更加均衡。     

基于改进模拟退火的RISP软硬件划分

软硬件划分是可重构指令集处理器在软硬件协同设计中的关键问题.已经被证明是一个NP难问题;模拟退火在解决该类问题的算法中较为常用,但在任务数变大时,其收敛速度过慢且不一定能找到有效近似最优解,通过将cauchy分布引入扰动模型同时将其距离参数△y乘上一个系数,然后在已有代价函数的基础上提出一个更加有效的边界条件,最后将冷却进度表的算式乘上一个权值,以此加快算法的收敛速度;实验结果表明,和经典模拟退火算法相比,新算法的收敛速度明显提高,同时得到的解更接近最优解,其性能优势在任务数增大时尤为明显。     

贪心算法求解k-median问题

文章讨论了用贪心算法解k-m edian问题以及其试验结果。首先提出了一个解k-m edian问题的简单贪心算法,然后对求解质量和求解的近似性能比进行了探讨。主要讨论了公制空间和非公制空间初始解的产生,用贪心算法解k-m edian问题以及全局最优解的计算。试验结果表明:贪心算法解公制空间的k-m edian问题效果要好于解非公制空间的k-m edian问题;用贪心算法解公制空间和非公制空间k-m edian问题都能得到较好的结果。     

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

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

一种新的遗传模拟退火算法的软硬件划分方法

针对嵌入式系统软硬件划分问题,在分析遗传算法和模拟退火算法的主要优缺点的基础上,提出了一种新的小生境技术改进的遗传模拟退火算法（NGSA）,在遗传算法中融入模拟退火思想,同时引入小生境技术,保持群体的多样性;并采用Metropolis 法则形成新群体,改善群体的质量。实验结果证明该算法具有很强的爬山能力和全局搜索能力,与遗传算法（GA）和模拟退火算法（SA）相比适应度明显提高。     

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

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

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

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

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

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

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

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

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

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.     

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.     

嵌入式系统芯片中SM2算法软硬件协同设计与实现

针对现有的椭圆曲线算法系统级设计中开发周期长,以及不同模块的性能开销指标不明确等问题,提出一种基于电子系统级(ESL)设计的软硬件(HW/SW)协同设计方法.该方法通过分析SM2(ShangMi2)算法原理与实现方式,研究了不同的软硬件划分方案,并采用统一建模语言SystemC对硬件模块进行周期精确级建模.通过模块级与系统级两层验证比较软硬件模块执行周期数,得出最佳性能划分方式.最后结合算法控制流程图(CFG)与数据流程图(DFG)将ESL模型转化为寄存器传输级(RTL)模型进行逻辑综合与比较,得出在180 nm CMOS工艺,50 MHz频率下,当算法性能最佳时,点乘模块执行时间为20 ms,门数83 000,功耗约2.23 mW.实验结果表明所提系统级架构分析对基于椭圆曲线类加密芯片在性能、面积与功耗的评估优势明显且适用性强,基于此算法的嵌入式系统芯片(SoC)可根据性能与资源限制选择合适的结构并加以应用.     

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.