Algorithmic Aspects of Hardware/Software Partitioning: 1D Search   Algorithms

doi:10.1109/TC.2009.173

CORC > 北京大学 > 软件与微电子学院

	Algorithmic Aspects of Hardware/Software Partitioning: 1D Search Algorithms
	Jigang, Wu ; Srikanthan, Thambipillai ; Chen, Guang
刊名	ieee transactions on computers
	2010
关键词	Hardware/software partitioning heuristic algorithm complexity knapsack problem HARDWARE-SOFTWARE COSYNTHESIS NETWORK FLOW PROBLEMS SYSTEMS
DOI	10.1109/TC.2009.173
英文摘要	Hardware/software (HW/SW) partitioning is one of the key challenges in HW/SW codesign. This paper presents efficient algorithms for the HW/SW partitioning problem, which has been proved to be NP- hard. We reduce the HW/SW partitioning problem to a variation of knapsack problem that is approximately solved by searching 1D solution space, instead of searching 2D solution space in the latest work cited in this paper, to reduce time complexity. Three heuristic algorithms are proposed to determine suitable partitions to satisfy HW/SW partitioning constraints. We have shown that the time complexity for partitioning a graph with n nodes and m edges is significantly reduced from O(d(x) . d(y) . n(3)) to O(n log n + d . (n + m)), where d and d(x) . d(y) are the number of the fragments of the searched 1D solution space and the searched 2D solution space, respectively. The lower bound on the solution quality is also proposed based on the new computing model to show that it is comparable to that reported in the literature. Moreover, empirical results show that the proposed algorithms produce comparable and often better solutions when compared to the latest algorithm while reducing the time complexity significantly.; Computer Science, Hardware & Architecture; Engineering, Electrical & Electronic; SCI(E); EI; 6; ARTICLE; 4; 532-544; 59
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/244034]
专题	软件与微电子学院
推荐引用方式 GB/T 7714	Jigang, Wu,Srikanthan, Thambipillai,Chen, Guang. Algorithmic Aspects of Hardware/Software Partitioning: 1D Search Algorithms[J]. ieee transactions on computers,2010.
APA	Jigang, Wu,Srikanthan, Thambipillai,&Chen, Guang.(2010).Algorithmic Aspects of Hardware/Software Partitioning: 1D Search Algorithms.ieee transactions on computers.
MLA	Jigang, Wu,et al."Algorithmic Aspects of Hardware/Software Partitioning: 1D Search Algorithms".ieee transactions on computers (2010).