One-dimensional Search Algorithms for Hardware/Software Partitioning
- 1 May 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 149-158
Abstract
Hardware/software (HW/SW) partitioning is one of the key challenges in HW/SW co-design. This paper presents a new formulation to handle the HW/SW partitioning problem, which has been proved to be NP-hard. The proposed formulation transforms the partitioning problem into an extended 0-1 knapsack problem that is approximately solved in this paper by scanning a one-dimensional search space, instead of scanning a two-dimensional search space as presented in the literature cited in this paper. Two heuristic algorithms are proposed to explore the feasible partitions to meet the given constraints. The time complexity of the latest heuristic algorithm is significantly reduced from O(d x ldr d y ldr n 3 ) to O(n log n + d ldr (n + m)) for the given graphs with n nodes and m edges, where d x ldr d y is the number of the fragments of the scanned two-dimensional search space, and d is that of the scanned one-dimensional search space. Empirical results show that the proposed algorithms run extremely fast and still produce better or similar solutions in comparison with the latest algorithm.Keywords
This publication has 29 references indexed in Scilit:
- Algorithmic aspects of hardware/software partitioningACM Transactions on Design Automation of Electronic Systems, 2005
- A Constructive Approach to Hardware/Software PartitioningFormal Methods in System Design, 2004
- Hardware software partitioning with integrated hardware design space exploration2002
- Clustering for improved system-level functional partitioning2002
- An approach to automated hardware/software partitioning using a flexible granularity that is driven by high-level estimation techniquesIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2001
- MOGAC: a multiobjective genetic algorithm for hardware-software cosynthesis of distributed embedded systemsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998
- On Implementing the Push—Relabel Method for the Maximum Flow ProblemAlgorithmica, 1997
- System Level Hardware/Software Partitioning Based on Simulated Annealing and Tabu SearchDesign Automation for Embedded Systems, 1997
- Hardware-software cosynthesis for digital systemsIEEE Design & Test of Computers, 1993
- A new approach to the maximum-flow problemJournal of the ACM, 1988