文章基本信息

标题：Knapsack Model and Algorithm for Hardware/Software Partitioning Problem
本地全文：下载
作者：Ray, Abhijit ; Jigang, Wu ; Srikanthan, Thambipillai 等
期刊名称：COMPUTING AND INFORMATICS
印刷版ISSN：1335-9150
出版年度：2004
卷号：23
期号：5-6
页码：557-569
语种：English
出版社：COMPUTING AND INFORMATICS
摘要：Efficient hardware/software partitioning is crucial towards realizing optimal solutions for constraint driven embedded systems. The size of the total solution space is typically quite large for this problem. In this paper, we show that the knapsack model could be employed for the rapid identification of hardware components that provide for time efficient implementations. In particular, we propose a method to split the problem into standard 0-1 knapsack problems in order to leverage on the classical approaches. The proposed method relies on the tight lower and upper bounds for each of these knapsack problems for the rapid elimination of the sub-problems, which are guaranteed not to give optimal results. Experimental results show that, for problem sizes ranging from 30 to 3000, the optimal solution of the whole problem can be obtained by solving only 1 sub-problem except for one case where it required the solution of 3 sub-problems.
关键词：Hardware/software partitioning; embedded systems; algorithm; knapsack problem