Runtime, Speculative On-Stack Parallelization of For-Loops in Binary Programs
IEEE Letters of the Computer Society • 2018
Publication Information
Authors
Marwa Yusuf, Ahmed El-Mahdy, Erven Rohou
Keywords
Compilers; Runtime; Optimization; Parallelization; Binary; Pthreads; On-Stack Replacement; Speculation.
Journal
IEEE Letters of the Computer Society
Publisher
IEEE
Volume
1
Issue
1
Pages
13-16
publication.type
International
Paper Link
Open Link
Supplementary Materials
Not Available
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 2x to 3x 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%.
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 2x to 3x 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%.
Staff Members - Benha University