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.     

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

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

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.     

Low-complex dynamic programming algorithm for hardware/software partitioning

A low-complex algorithm is proposed for the hardware/software partitioning. The proposed algorithm employs dynamic programming principles while accounting for communication delays. It is shown that the time complexity of the latest algorithm has been reduced from O(n²⋅A) to O(n⋅A), without increase in space complexity, for n code fragments and hardware area A.     

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

Dataflow computer extension towards real-time processing

This paper presents an extended architecture and a scheduling algorithm for a dataflow computer aimed at real-time processing. From the real-time processing point of view, current dataflow computers have several problems which stem from their hardware mechanisms for scheduling instructions based on data synchronization. This mechanism extracts as many eligible instructions as possible for execution of a program, then executes them in parallel. Hence, the computation in a dataflow computer is generally difficult to interrupt and schedule using software. To realize a controllable dataflow computation, two basic mechanisms are introduced for serializing concurrent processes and interrupting the execution of a process. A parallel and distributed algorithm for the scheduler is presented, with these two mechanisms, which controls and decides state transitions and execution order of the processes based on priority and execution depth, while still maintaining the number of the running state processes at a preferred value. To gear the scheduler algorithm to meet one of the requirements for real-time processing, such as time-constrained computing, a data-parallel algorithm for selection of the user-process with the current highest priority in O (x log _x n) time is proposed, where n is the number of priority levels.     

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

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

在两个级别上对嵌入式系统应用进行硬件/软件划分

利用源代码级别的高级信息和二进制级别上性能准确估计的特点,在两个级别上对嵌入式系统进行硬件/软件划分,它支持动态划分,对用户透明;给出了系统划分模型,使用执行时间最少的增益函数启发下一步动作的启发算法。从实验结果可以看出,用较少的硬件面积基本不影响执行时间,特别地,在一些例子中执行时间还会有所提高。     

多级别嵌入式系统硬件/软件划分方法

对嵌入式系统应用中硬件/软件划分方法的研究是基于源代码级别或者二进制级别,可以利用在两个级别上的各自特点分别进行求解,利用了源代码级别的高级信息和二进制级别上性能准确估计的特点,先进行功能划分再进行二进制性能估算根据估计得到性能来动态划分应用。文章基于Petir网给出了系统划分模型,使用执行时间最少的增益函数启发下一步动作。算法可以用较少的硬件面积,提高执行时间。     

基于距离不等式的K-medoids聚类算法

本文研究加速K-medoids聚类算法,首先以PAM（Partitioning Around Medoids）、TPAM（Triangular Inequality Elimination Criteria PAM）算法为基础,给出两个加速引理,并基于中心点之间距离不等式提出两个新加速定理.同时,以O（n+K²）额外内存空间开销辅助引理、定理的结合而提出加速SPAM（Speed Up PAM）聚类算法,使得K-medoids聚类算法复杂度由O（K（n-K）²）降低至O（（n-K）²）.在实际及人工模拟数据集上的实验结果表明,相对PAM、TPAM、FKMEDOIDS（Fast K-medoids）等参考算法均有改进,运行时间比PAM至少提升0.828倍.