共查询到20条相似文献,搜索用时 10 毫秒
1.
2.
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. 相似文献
3.
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. 相似文献
4.
软硬件划分是软硬件协同设计的关键环节,划分的结果直接影响目标系统的设计质量。因此,对于一个给定的应用程序,为了使得目标系统快速执行且成本低廉,合理的划分策略十分重要。由于单个任务具有多种不同的硬件实现方式,与传统的单一硬件实现方式的软硬件划分问题相比,多选择的软硬件划分更能客观地反映现实应用。这导致问题的求解更具挑战性,它们已被证明是NP完全问题。基于多核处理器片上系统并针对任务图为二叉树的应用,建立了多选择软硬件划分问题的计算模型,并提出了解决该问题的动态规划算法。实验结果表明,当问题规模适中时,所提动态规划算法能够有效地获得精确解,并展示了算法的计算能力与硬件面积限制之间的关系。 相似文献
5.
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. 相似文献
6.
Jifeng He Dang Van Hung Geguang Pu Zongyan Qiu Wang Yi 《Formal Aspects of Computing》2005,17(4):443-460
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 相似文献
7.
在考虑动态部分重构及重构延时等特征的基础上,采用遗传算法及其与爬山算法的融合实现可重构系统软硬件任务的划分,并采用动态优先级调度算法进行划分结果的评价。实验表明,在可重构系统的资源约束等条件下,算法能够有效地实现应用任务图到可重构系统的时空映射。 相似文献
8.
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. 相似文献
9.
针对存在多种因素影响嵌入式系统综合性能的实际情况,详细分析了影响嵌入式系统性能的各项性能指标,提出了一种基于多性能指标评价的软硬件协同划分思想。利用SoC可重用的特性,将IP核复用及软件架构重用引入到软硬件划分算法当中。通过功能模块层的抽象,将复杂的嵌入式系统构成映射到数学上的DAG(Direct Acyclic Graph)之上。提出了性能指标优先级的概念,并通过在算法中加入对给定的参数数据预先处理及引入运筹学中分支定界的思想,优化了算法的求解,加快了算法的收敛速度,较之单纯的整个空间的条件遍历更优。 相似文献
10.
11.
针对嵌入式系统软硬件划分问题,在分析遗传算法和模拟退火算法的主要优缺点的基础上,提出了一种新的小生境技术改进的遗传模拟退火算法(NGSA),在遗传算法中融入模拟退火思想,同时引入小生境技术,保持群体的多样性;并采用Metropolis 法则形成新群体,改善群体的质量。实验结果证明该算法具有很强的爬山能力和全局搜索能力,与遗传算法(GA)和模拟退火算法(SA)相比适应度明显提高。 相似文献
12.
13.
软硬件划分作为可重构片上系统设计的重要技术手段,其结果直接影响到系统的性能。目前的软硬件划分大多只考虑从算法本身提高划分效果,忽略了划分结果的具体配置实现,导致划分效果很不理想。分析了预配置模型下的任务描述,给出了预配置调度优先级的计算方法,设计了一种预配置调度策略;针对软硬件划分与动态可重构的特点,提出并实现了一种结合预配置的软硬件划分算法,给出了一种评价软硬件划分方案优劣的方法。实验结果表明,该划分方法具有良好的划分效果。 相似文献
14.
软硬件划分是嵌入式系统软硬件协同设计中的关键技术之一,如何兼顾系统的性能和成本,达到两者的最佳结合,是软硬件划分的主要问题.针对单CPU多ASICs类型的目标结构,选取了遗传算法、禁忌搜索算法和模拟退火算法等全局优化算法进行系统的软硬件划分,并对3种算法的有效性进行了比较分析. 相似文献
15.
针对嵌入式系统中的单处理器和单ASIC体系结构,将软硬件划分问题抽象为MKP模型,通过扩展其边界的维数,引入二维的贪婪算法来解决软硬件划分问题。算法旨在满足硬件面积约束、功耗约束和存储空间需求约束的前提下使系统的运行时间最优,算法的时间复杂度降低到O(log n·log n)。算法基于代表功能块粒度的控制数据流图(CFG),摒弃了传统的面向软件或硬件的方法,给出了一种新的选择初始状态的方法,该方法将关键节点映射到软件,其余的用硬件实现,因缩小了算法的搜索空间,从而进一步提高了算法的运行速度。最后进行对比实验,实验结果证明该算法在运行时间和稳定性方面均优于遗传算法和模拟算法。 相似文献
16.
嵌入式系统软硬件划分方法探索 总被引:1,自引:0,他引:1
提出了克隆选择算法在软硬件划分中的应用,讨论了目标函数、系统约束、抗体编码、克隆选择和变异等问题的处理。实验结果表明该算法具有较快的收敛速度,并获得了近似最优解。 相似文献
17.
18.
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. 相似文献
19.
在目前全球倡导“低碳经济”的背景下,随着嵌入式系统大量而广泛的使用,嵌入式软件功耗已成为嵌入式系统设计的一个关键因素,而软/硬件划分是嵌入式软件功耗优化的一种重要方法。首先在性能约束条件下,建立以嵌入式软件功耗为目标的软/硬件双路划分模型;然后,提出了一种基于离散Hopfield神经网络(HNN)和禁忌搜索(TS)融合的求解算法,采用离散Hopfield算法作为主算法能较快地获得可行解,使用禁忌搜索算法“禁忌”当前解而转移到目标函数的其他极小点,从而可跳出局部最优解而快速趋于全局最优解;最后,仿真实验表明,与同类算法相比,该算法不但具有搜索速度上的优势,而且求得全局最优解的概率更高。 相似文献