Runtime, Speculative On-Stack Parallelization of For-Loops in Binary Programs

Abstract : Nowadays almost every device has parallel architecture, hence parallelization is almost always desirable. However, parallelizing legacy running programs is very challenging. That is due to the fact that usually source code is not available, and runtime parallelization, without program restarting is challenging. Also, detecting parallelizable code is difficult, due to possible dependencies and different execution paths that undecidable statically. Therefore, speculation is a typical approach whereby wrongly parallelized code is detected and rolled back at runtime. This paper considers utilizing processes to implement speculative parallelization using on-stack replacement, allowing for generally simple and portable design where forking a new process enters the speculative state, and killing a faulty process simply performs the roll back operation. While the cost of such operations are high, the approach is promising for cases where the parallel section is long and dependency issues are rare. Also, our proposed system performs speculative parallelization on binary code at runtime, without the need for source code, restarting the program or special hardware support. Initial experiments show about 2\times to 3\times speedup for speculative execution over serial one, when three fourth of loop iterations are parallelizable. Also, maximum measured speculation overhead over pure parallel execution is 5.8%.
Type de document :
Article dans une revue
IEEE Letters of the Computer Society, IEEE, 2018, pp.1-4. 〈10.1109/LOCS.2018.2872454〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01890719
Contributeur : Erven Rohou <>
Soumis le : mardi 9 octobre 2018 - 17:29:24
Dernière modification le : jeudi 15 novembre 2018 - 11:58:57

Fichier

binary_speculation_locs__Revis...
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Marwa Yusuf, Ahmed El-Mahdy, Erven Rohou. Runtime, Speculative On-Stack Parallelization of For-Loops in Binary Programs. IEEE Letters of the Computer Society, IEEE, 2018, pp.1-4. 〈10.1109/LOCS.2018.2872454〉. 〈hal-01890719〉

Partager

Métriques

Consultations de la notice

83

Téléchargements de fichiers

28