A comparison of heuristic algorithms for custom instruction selection

Abstract : Extensible processors with custom function units (CFU) that implement parts of the application code can make good trade-off between performance and flexibility. In general, deciding profitable parts of the application source code that run on CFU involves two crucial steps: subgraph enumeration and subgraph selection. In this paper, we focus on the subgraph selection problem, which has been widely recognized as a computationally difficult problem. We have formally proved that the upper bound of the number of feasible solutions for the subgraph selection problem is 3n/3, where n is the number of subgraph candidates. We have adapted and compared five popular heuristic algorithms: simulated annealing (SA), tabu search (TS), genetic algorithm (GA), particle swarm optimization (PSO) and ant colony optimization (ACO), for the subgraph selection problem with the objective of minimising execution time under non-overlapping constraint and acyclicity constraint. The results show that the standard SA algorithm can produce the best results while taking the least amount of time among the five standard heuristics. In addition, we have introduced an adaptive local optimum searching strategy in ACO and PSO to further improve the quality of results.
Type de document :
Article dans une revue
Microprocessors and Microsystems: Embedded Hardware Design (MICPRO), Elsevier, 2016, 45 (A), pp.11. 〈http://www.sciencedirect.com/science/journal/01419331〉
Liste complète des métadonnées

Littérature citée [38 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01354991
Contributeur : Emmanuel Casseau <>
Soumis le : lundi 24 octobre 2016 - 23:25:13
Dernière modification le : mercredi 11 avril 2018 - 02:00:07

Fichier

JSTS_2nde_soumission_v2.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas de modifications 4.0 International License

Identifiants

  • HAL Id : hal-01354991, version 1

Citation

Shanshan Wang, Chenglong Xiao, Wanjun Liu, Emmanuel Casseau. A comparison of heuristic algorithms for custom instruction selection. Microprocessors and Microsystems: Embedded Hardware Design (MICPRO), Elsevier, 2016, 45 (A), pp.11. 〈http://www.sciencedirect.com/science/journal/01419331〉. 〈hal-01354991〉

Partager

Métriques

Consultations de la notice

651

Téléchargements de fichiers

135