Cost minimization while satisfying hard/soft timing constraints for heterogeneous embedded systems
Top Cited Papers
- 1 March 2009
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Design Automation of Electronic Systems
- Vol. 14 (2), 1-30
- https://doi.org/10.1145/1497561.1497568
Abstract
In high-level synthesis for real-time embedded systems using heterogeneous functional units (FUs), it is critical to select the best FU type for each task. However, some tasks may not have fixed execution times. This article models each varied execution time as a probabilistic random variable and solves heterogeneous assignment with probability (HAP) problem. The solution of the HAP problem assigns a proper FU type to each task such that the total cost is minimized while the timing constraint is satisfied with a guaranteed confidence probability. The solutions to the HAP problem are useful for both hard real-time and soft real-time systems. Optimal algorithms are proposed to find the optimal solutions for the HAP problem when the input is a tree or a simple path. Two other algorithms, one is optimal and the other is near-optimal heuristic, are proposed to solve the general problem. The experiments show that our algorithms can effectively reduce the total cost while satisfying timing constraints with guaranteed confidence probabilities. For example, our algorithms achieve an average reduction of 33.0% on total cost with 0.90 confidence probability satisfying timing constraints compared with the previous work using worst-case scenario.Keywords
Funding Information
- Division of Information and Intelligent Systems (IIS-0513669)
- National Science Foundation (CCR-0309461)
- National Natural Science Foundation of China (60728206)
- Research Grants Council, University Grants Committee, Hong Kong (B-Q60B)
This publication has 26 references indexed in Scilit:
- The master-slave paradigm with heterogeneous processorsIEEE Transactions on Parallel and Distributed Systems, 2003
- Probabilistic loop scheduling for applications with uncertain execution timeIEEE Transactions on Computers, 2000
- Allocation of periodic task modules with precedence and deadline constraints in distributed real-time systemsIEEE Transactions on Computers, 1997
- High-level DSP synthesis using concurrent transformations, scheduling, and allocationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1995
- Global optimization approach for architectural synthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993
- On the circuit implementation problemIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993
- Task allocation for maximizing reliability of distributed computer systemsIEEE Transactions on Computers, 1992
- Static rate-optimal scheduling of iterative data-flow programs via optimum unfoldingIEEE Transactions on Computers, 1991
- Architecture-driven synthesis techniques for VLSI implementation of DSP algorithmsProceedings of the IEEE, 1990
- The high-level synthesis of digital systemsProceedings of the IEEE, 1990