We present an algorithm based on dynamic programming to perform the HW/SW partitioning and scheduling of a given task graph for minimum latency subject to resource constraint. The major contribution of this paper is to consider the edge communication delays in the dynamic programming solution of the problem. The algorithm has a polynomial run time complexity on trees. We also introduce a pruning technique to reduce the runtime of the worst-case scenario of directed acyclic graphs (DAGs). The algorithm has been implemented and the results are reported. A very fast quality heuristic is also proposed and implemented to provide good solutions in negligible run time.
|Original language||English (US)|
|Title of host publication||Proceedings - Euromicro Symposium on Digital System Design, DSD 2003|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|Number of pages||8|
|ISBN (Electronic)||0769520030, 9780769520032|
|State||Published - 2003|
|Event||Euromicro Symposium on Digital System Design, DSD 2003 - Belek-Antalya, Turkey|
Duration: Sep 1 2003 → Sep 6 2003
|Name||Proceedings - Euromicro Symposium on Digital System Design, DSD 2003|
|Other||Euromicro Symposium on Digital System Design, DSD 2003|
|Period||9/1/03 → 9/6/03|
Bibliographical notePublisher Copyright:
© 2003 IEEE.