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

Computing model and dynamic programming algorithm for multiple-choice hardware/software partitioning on MPSoC

作　　者：朱峰军 武继刚[1,2] 史雯隽 姜桂圆[3] 

机构地区：[1]天津工业大学计算机科学与软件学院,天津300387 [2]中国科学院软件所计算机科学国家重点实验室,北京100190 [3]天津大学计算机科学与技术学院,天津300072

出　　处：《计算机工程与科学》2015年第4期641-648,共8页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(61173032);国家自然科学基金天元青年基金资助项目(11326211)

摘　　要：软硬件划分是软硬件协同设计的关键环节,划分的结果直接影响目标系统的设计质量。因此,对于一个给定的应用程序,为了使得目标系统快速执行且成本低廉,合理的划分策略十分重要。由于单个任务具有多种不同的硬件实现方式,与传统的单一硬件实现方式的软硬件划分问题相比,多选择的软硬件划分更能客观地反映现实应用。这导致问题的求解更具挑战性,它们已被证明是NP完全问题。基于多核处理器片上系统并针对任务图为二叉树的应用,建立了多选择软硬件划分问题的计算模型,并提出了解决该问题的动态规划算法。实验结果表明,当问题规模适中时,所提动态规划算法能够有效地获得精确解,并展示了算法的计算能力与硬件面积限制之间的关系。Hardware/software （HW/SW） partitioning is one of the most crucial steps in hardware/ software co-design,as the solution of partitioning directly affects the quality of the target system. For a given application,it is quite necessary to find a reasonable partitioning in order to obtain a target system which is of low cost but can be fast executed. In system design, one task has different implementation manners in hardware according to the different hardware areas. Thus,the multiple-choice HW/SW parti- tioning is more realistic than the traditional HW/SW partitioning which considers only a single implementation manner in hardware. It is also more challenging to solve the multiple-choice HW/SW partitioning problem. The two types of partitioning problems both have been proved to be NP-complete. For the multiple-choice HW/SW partitioning problem on Multiprocessor System-on-Chips （MPSoC）,we present a computing model on MPSoC for the input control-flow graph with a binary tree. A dynamic programming algorithm is also proposed to solve this problem. Extensive simulation results show that the proposed algorithm can provide the exact solution for the problems with certain scale. It also shows the relationship between the algorithm performance and the constraints of hardware area.

关 键 词：多选择软硬件划分 多核处理器片上系统 二叉树 动态规划算法 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]