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.     

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完全问题。基于多核处理器片上系统并针对任务图为二叉树的应用,建立了多选择软硬件划分问题的计算模型,并提出了解决该问题的动态规划算法。实验结果表明,当问题规模适中时,所提动态规划算法能够有效地获得精确解,并展示了算法的计算能力与硬件面积限制之间的关系。     

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.     

Exploring optimal solution to hardware/software partitioning for synchronous model

Computer aided hardware/software partitioning is one of the key challenges in hardware/software co-design. This paper describes a new approach to hardware/software partitioning for a synchronous communication model including multiple hardware devices. We transform the partitioning into a reachability problem of timed automata. By means of an optimal reachability algorithm, the optimal solution can be obtained with limited resources in hardware. To relax the initial condition of the partitioning for optimization, two algorithms are designed to explore the dependency relations among processes in the sequential specification. Moreover, we propose a scheduling algorithm to improve the synchronous communication efficiency further after partitioning stage. Some experiments are conducted with the model checker UPPAAL to show our approach is both effective and efficient. Jifeng He: On leave from East China Normal University. The work is partially supported by the 973 project 2002CB312001 of the ministry of science and technology, and the 211 project of the ministry of Education of China. Partially Supported by National Natural Science Foundation of China (No.60173003) Received November 2004 Revised July 2005 Accepted August 2005 by Eerke A. Boiten, John Derrick, Graeme Smith and Ian Hayes     

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

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

An Algebraic Hardware/Software Partitioning Algorithm

Hardware and software co-design is a design technique which delivers computer systems comprising hardware and software components.A critical phase of the co-design process is to decompose a program into hardware and software .This paper proposes an algebraic partitioning algorithm whose correctness is verified in program algebra.The authors inroduce a program analysis phase before program partitioning and deveop a collection of syntax-based splitting rules.The former provides the information for moving operations from software to hardware and reducing the interaction between compoents,and th latter supports a compositional approach to program partitioning.     

基于多性能指标的SoC软硬件划分方法研究

针对存在多种因素影响嵌入式系统综合性能的实际情况,详细分析了影响嵌入式系统性能的各项性能指标,提出了一种基于多性能指标评价的软硬件协同划分思想。利用SoC可重用的特性,将IP核复用及软件架构重用引入到软硬件划分算法当中。通过功能模块层的抽象,将复杂的嵌入式系统构成映射到数学上的DAG（Direct Acyclic Graph）之上。提出了性能指标优先级的概念,并通过在算法中加入对给定的参数数据预先处理及引入运筹学中分支定界的思想,优化了算法的求解,加快了算法的收敛速度,较之单纯的整个空间的条件遍历更优。     

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

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

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

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

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

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

三种软硬件划分算法的比较分析

软硬件划分是嵌入式系统软硬件协同设计中的关键技术之一,如何兼顾系统的性能和成本,达到两者的最佳结合,是软硬件划分的主要问题.针对单CPU多ASICs类型的目标结构,选取了遗传算法、禁忌搜索算法和模拟退火算法等全局优化算法进行系统的软硬件划分,并对3种算法的有效性进行了比较分析.     

改进的二维增强贪婪软硬件划分算法

针对嵌入式系统中的单处理器和单ASIC体系结构,将软硬件划分问题抽象为MKP模型,通过扩展其边界的维数,引入二维的贪婪算法来解决软硬件划分问题。算法旨在满足硬件面积约束、功耗约束和存储空间需求约束的前提下使系统的运行时间最优,算法的时间复杂度降低到O（log n·log n）。算法基于代表功能块粒度的控制数据流图（CFG）,摒弃了传统的面向软件或硬件的方法,给出了一种新的选择初始状态的方法,该方法将关键节点映射到软件,其余的用硬件实现,因缩小了算法的搜索空间,从而进一步提高了算法的运行速度。最后进行对比实验,实验结果证明该算法在运行时间和稳定性方面均优于遗传算法和模拟算法。     

嵌入式系统软硬件划分方法探索

提出了克隆选择算法在软硬件划分中的应用,讨论了目标函数、系统约束、抗体编码、克隆选择和变异等问题的处理。实验结果表明该算法具有较快的收敛速度,并获得了近似最优解。     

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

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

Acceleration of software algorithms using hardware/software co-design techniques

Currently there is significant interest in the design and implementation of embedded systems where the hardware and software subsystems are developed concurrently in order to meet design constraints. We present a development environment for general-purpose systems, where the objective is to accelerate the performance of software-based applications, which are specified by C programs. Such programs may be partitioned into hardware and software subsystems — a speed-critical region of the software is implemented in an FPGA in order to provide the performance acceleration. We also discuss two versions of the underlying system hardware architecture. Practical examples are given to illustrate our approach.     

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

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

基于自适应蚁群算法的软硬件划分

为了更好地解决软硬件双路划分问题,提出一种自适应蚁群算法．基本思想是：对状态转移概率与信息素挥发因子,采取自适应调节策略．保证了算法前期蚁群的随机性较大,可以充分全局搜索;算法后期蚁群的随机性降低,以使算法在较短的时间内收敛．对不同节点的控制数据流图进行仿真实验,表明在同等条件下,相对于改进模拟退火、改进禁忌搜索、改进蚁群算法以及ＤＣＧ３Ａ 方法,所提出算法的命中率与收敛时间结果均更优．节点规模越大,优势尤其明显．