Runtime On-Stack Parallelization of Dependence-Free For-Loops in Binary Programs

Abstract : With the multicore trend, the need for automatic parallelization is more pronounced, especially for legacy and proprietary code where no source code is available and/or the code is already running and restarting is not an option. In this paper, we engineer a mechanism for transforming at runtime a frequent for-loop with no data dependencies in a binary program into a parallel loop, using on-stack replacement. With our mechanism, there is no need for source code, debugging information or restarting the program. Also, the mechanism needs no static instrumentation or information. The mechanism is implemented using the Padrone binary modification system and pthreads, where the remaining iterations of the loop are executed in parallel. The mechanism keeps the running program state by extracting the targeted loop into a separate function and copying the current stack frame into the corresponding frames of the created threads. Initial study is conducted on a set of kernels from the Polybench workload. Experiments results show from 2x to 3.5x speedup from sequential to parallelized code on four cores, which is similar to source code level parallelization.
Document type :
Journal articles
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/hal-02061340
Contributor : Erven Rohou <>
Submitted on : Friday, March 8, 2019 - 9:19:56 AM
Last modification on : Thursday, July 18, 2019 - 9:46:04 PM
Long-term archiving on : Monday, June 10, 2019 - 3:48:33 PM

File

LOCS_binary_parallelization.pd...
Files produced by the author(s)

Identifiers

Citation

Marwa Yusuf, Ahmed El-Mahdy, Erven Rohou. Runtime On-Stack Parallelization of Dependence-Free For-Loops in Binary Programs. IEEE Letters of the Computer Society, IEEE, 2019, 2 (1), pp.1-4. ⟨10.1109/LOCS.2019.2896559⟩. ⟨hal-02061340⟩

Share

Metrics

Record views

51

Files downloads

73