Optimal Functional-Unit Assignment for Heterogeneous Systems Under Timing Constraint
Authors:
- 1 March 2017
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 28 (9) , 2567-2580
Abstract
In high-level synthesis for real-time systems, it typically employs heterogeneous functional-unit types to achieve high-performance and low-cost designs. In the design phase, it is critical to determine which functional-unit type to be mapped for each operation in a given application such that the total cost is minimized while the deadline can be met. For a path or tree structured application, existing approaches can obtain the minimum-cost assignment, called “optimal assignment”, under which the resultant system satisfies a given timing constraint. However, it is still an open question whether there exist efficient algorithms to obtain the optimal assignment for the directed acyclic graph (DAG), or more generally, the data-flow graph with cycles (cyclic DFG). For DAGs, by analyzing the property of the problem, this paper designs an efficient algorithm to obtain the optimal assignments. For cyclic DFGs, we approach this problem with the combination of retiming technique to thoroughly explore the design space. We formulate a Mixed Integer Linear Programming (MILP) model to give the optimal solution. But because of the high degree of its time complexity, we devise a practical algorithm to obtain near-optimal solutions within a minute. Experimental results show the effectiveness of our algorithms. Specifically, compared with existing techniques, we can achieve 25.70 and 30.23 percent reductions in total cost on DAGs and cyclic DFGs, respectively.Keywords
Funding Information
- National 863 Program (2015AA015304)
- NSFC (61472052)
- Chongqing Research Program (cstc2014yykfB40007)
This publication has 33 references indexed in Scilit:
- Overhead-aware energy optimization for real-time streaming applications on multiprocessor System-on-ChipACM Transactions on Design Automation of Electronic Systems, 2011
- Cost minimization while satisfying hard/soft timing constraints for heterogeneous embedded systemsACM Transactions on Design Automation of Electronic Systems, 2009
- Task allocation for maximizing reliability of distributed systems: A simulated annealing approachJournal of Parallel and Distributed Computing, 2006
- A hybrid particle swarm optimization algorithm for optimal task assignment in distributed systemsComputer Standards & Interfaces, 2006
- Hybrid meta-heuristics algorithms for task assignment in heterogeneous computing systemsComputers & Operations Research, 2006
- Particle swarm optimization for task assignment problemMicroprocessors and Microsystems, 2002
- Rotation scheduling: a loop pipelining algorithmIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1997
- Scheduling data-flow graphs via retiming and unfoldingIEEE Transactions on Parallel and Distributed Systems, 1997
- On the circuit implementation problemIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993
- Retiming synchronous circuitryAlgorithmica, 1991