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

发布时间：2018-01-03 21:24

本文关键词：多选择软硬件划分问题的计算模型与动态规划算法　出处：《计算机工程与科学》2015年04期 　论文类型：期刊论文

【摘要】：软硬件划分是软硬件协同设计的关键环节,划分的结果直接影响目标系统的设计质量。因此,对于一个给定的应用程序,为了使得目标系统快速执行且成本低廉,合理的划分策略十分重要。由于单个任务具有多种不同的硬件实现方式,与传统的单一硬件实现方式的软硬件划分问题相比,多选择的软硬件划分更能客观地反映现实应用。这导致问题的求解更具挑战性,它们已被证明是NP完全问题。基于多核处理器片上系统并针对任务图为二叉树的应用,建立了多选择软硬件划分问题的计算模型,并提出了解决该问题的动态规划算法。实验结果表明,当问题规模适中时,所提动态规划算法能够有效地获得精确解,并展示了算法的计算能力与硬件面积限制之间的关系。
[Abstract]:Hardware and software partitioning is the key link of hardware / software co-design. The result of partition directly affects the design quality of the target system. Therefore, for a given application program. In order to make the target system execute quickly and the cost is low, a reasonable partition strategy is very important, because a single task has many different hardware implementation methods. Compared with the hardware / software partition problem of the traditional single hardware implementation, the multi-choice hardware / software partition can objectively reflect the practical application, which makes the solution of the problem more challenging. They have been proved to be NP-complete problems. Based on the multi-core processor on-chip system and the application of task graph as binary tree, the computing model of multi-choice hardware and software partition problem is established. A dynamic programming algorithm is proposed to solve the problem. The experimental results show that the proposed dynamic programming algorithm can effectively obtain the exact solution when the scale of the problem is moderate. The relationship between the computational power of the algorithm and the hardware area limit is also shown.
【作者单位】：天津工业大学计算机科学与软件学院;中国科学院软件所计算机科学国家重点实验室;天津大学计算机科学与技术学院;
【基金】：国家自然科学基金资助项目(61173032);国家自然科学基金天元青年基金资助项目(11326211)
【分类号】：TP332;O221.3
【正文快照】： 1引言随着信息化、智能化、网络化的发展,嵌入式系统技术也获得了广阔的发展空间。嵌入式系统被广泛地应用于军事、家用、工业、商业、办公、医疗等社会各个方面,表现出非常广阔的应用前景。作为嵌入式系统开发的重要技术,软硬件协同设计目前已在嵌入式系统设计中得到广泛的应

【参考文献】