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

J4 ›› 2015, Vol. 37 ›› Issue (04): 641-648.

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

朱峰军1，武继刚1, 2，史雯隽1，姜桂圆3

（1.天津工业大学计算机科学与软件学院，天津 300387；
2.中国科学院软件所计算机科学国家重点实验室，北京 100190；
3.天津大学计算机科学与技术学院，天津 300072）

收稿日期:2014-08-16 修回日期:2014-10-25 出版日期:2015-04-25 发布日期:2015-04-25
基金资助:
国家自然科学基金资助项目（61173032）；国家自然科学基金天元青年基金资助项目（11326211）

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

ZHU Fengjun1，WU Jigang1,2，SHI Wenjun1，JIANG Guiyuan3

(1.School of Computer Science and Software,Tianjin Polytechnic University, Tianjin 300387;
2.State Key Laboratory of Computer Science,Institute of Software,Chinese Academy of Sciences,Beijing 100190;
3.School of Computer Science and Technology,Tianjin University,Tianjin 300072,China)

Received:2014-08-16 Revised:2014-10-25 Online:2015-04-25 Published:2015-04-25

摘要/Abstract

摘要：

软硬件划分是软硬件协同设计的关键环节，划分的结果直接影响目标系统的设计质量。因此，对于一个给定的应用程序，为了使得目标系统快速执行且成本低廉，合理的划分策略十分重要。由于单个任务具有多种不同的硬件实现方式，与传统的单一硬件实现方式的软硬件划分问题相比，多选择的软硬件划分更能客观地反映现实应用。这导致问题的求解更具挑战性，它们已被证明是NP完全问题。基于多核处理器片上系统并针对任务图为二叉树的应用，建立了多选择软硬件划分问题的计算模型，并提出了解决该问题的动态规划算法。实验结果表明，当问题规模适中时，所提动态规划算法能够有效地获得精确解，并展示了算法的计算能力与硬件面积限制之间的关系。

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

Abstract:

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

Key words: multiple-choice hardware/software partitioning;multiprocessor system-on-chips;binary tree;dynamic programming algorithm

朱峰军1，武继刚1, 2，史雯隽1，姜桂圆3. 多选择软硬件划分问题的计算模型与动态规划算法[J]. J4, 2015, 37(04): 641-648.

ZHU Fengjun1，WU Jigang1,2，SHI Wenjun1，JIANG Guiyuan3. Computing model and dynamic programming algorithm for
multiple-choice hardware/software partitioning on MPSoC [J]. J4, 2015, 37(04): 641-648.

[1]	何志军,何洪英,黄旭. 改进十字链表的存储方法在短路电流计算中的应用[J]. 计算机工程与科学, 2017, 39(04): 648-655.
[2]	陈平华，陈传瑜. 基于满二叉树的二分K-means聚类并行推荐算法[J]. J4, 2015, 37(08): 1450-1457.
[3]	张红泰，刘宏立，刘述钢. 基于满二叉树的RA码交织器设计[J]. J4, 2015, 37(04): 699-703.
[4]	周艳聪1,2,董永峰2,崔晓欣2,杨阔1. 基于信息预处理的分组动态二进制防碰撞算法[J]. J4, 2014, 36(10): 2041-2046.
[5]	刘永霞1,张朝晖1,2,张艳敏1. 基于K-均值聚类及二叉树决策的图像去噪[J]. J4, 2013, 35(5): 118-123.
[6]	孙安玉,江贵平. 基于满二叉树分块策略的大规模数据场纹理映射体绘制算法[J]. J4, 2011, 33(3): 57-61.
[7]	左正康, 游珍, 薛锦云. 后序遍历二叉树非递归算法的推导及形式化证明[J]. J4, 2010, 32(3): 119-123.
[8]	喻波，赵国鸿，陈曙晖. 一种基于共享前缀的两级索引结构[J]. J4, 2010, 32(12): 113-116.
[9]	何昭青[1,2]. 一种高效的基于排序二叉树的数据流挖掘算法[J]. J4, 2008, 30(11): 151-154.
[10]	张燕[1] 贾焰[1] 黄晓斌[2]. 网格环境下一种可扩展的资源发现机制[J]. J4, 2007, 29(11): 124-126.
[11]	刘云生涂咏秋. 一种新型嵌入式浏览器解析布局器的实现[J]. J4, 2006, 28(9): 28-29.
[12]	文元桥[2] 周敬利[1] 余胜生[1]. 一种基于二叉树的快速穷举化搜索算法[J]. J4, 2005, 27(7): 67-68.
[13]	潘榕. 一个网络信息层次化的数学模型及其次优算法[J]. J4, 2005, 27(10): 10-12.
[14]	周培德. 交通道路网中任意两点之最短路径的快速算法[J]. J4, 2002, 24(4): 35-37.
[15]	邱英汉. 二叉树平面坐标网及其应用[J]. J4, 2000, 22(3): 36-40.