Ant Colony Heuristic for Mapping and Scheduling Tasks and Communications on Heterogeneous Embedded Systems
- 20 May 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 29 (6), 911-924
- https://doi.org/10.1109/tcad.2010.2048354
Abstract
To exploit the power of modern heterogeneous multiprocessor embedded platforms on partitioned applications, the designer usually needs to efficiently map and schedule all the tasks and the communications of the application, respecting the constraints imposed by the target architecture. Since the problem is heavily constrained, common methods used to explore such design space usually fail, obtaining low-quality solutions. In this paper, we propose an ant colony optimization (ACO) heuristic that, given a model of the target architecture and the application, efficiently executes both scheduling and mapping to optimize the application performance. We compare our approach with several other heuristics, including simulated annealing, tabu search, and genetic algorithms, on the performance to reach the optimum value and on the potential to explore the design space. We show that our approach obtains better results than other heuristics by at least 16% on average, despite an overhead in execution time. Finally, we validate the approach by scheduling and mapping a JPEG encoder on a realistic target architecture.Keywords
This publication has 31 references indexed in Scilit:
- Genetic algorithms for hardware–software partitioning and optimal resource allocationJournal of Systems Architecture, 2007
- A performance study of multiprocessor task scheduling algorithmsThe Journal of Supercomputing, 2007
- Scheduling and mapping of conditional task graph for the synthesis of low power embedded systemsIEE Proceedings - Computers and Digital Techniques, 2003
- Ant colony optimization for resource-constrained project schedulingIEEE Transactions on Evolutionary Computation, 2002
- Resource-constrained project scheduling: Notation, classification, models, and methodsEuropean Journal of Operational Research, 1999
- MOGAC: a multiobjective genetic algorithm for hardware-software cosynthesis of distributed embedded systemsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998
- Ant system: optimization by a colony of cooperating agentsIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1996
- The hierarchical task graph as a universal intermediate representationInternational Journal of Parallel Programming, 1994
- Genetic Algorithms versus Tabu Search for Instruction SchedulingPublished by Springer Science and Business Media LLC ,1993
- On the complexity of scheduling problems for parallel/pipelined machinesInternational Conference on Acoustics, Speech, and Signal Processing (ICASSP), 1989