Accelerating Data Dependence Profiling Through Abstract Interpretation of Loop Instructions
Data dependence analysis is a must-do operation for parallelisation since it reveals the safe parallelisable regions of serial codes. Generally, it relies on dynamic analysis, which incurs substantial execution time and memory space overheads. As a result, there have been many efforts in the literat...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2022-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9738611/ |
| _version_ | 1819174721020755968 |
|---|---|
| author | Mostafa Abbas Mostafa I. Soliman Sherif I. Rabia Keiji Kimura Ahmed El-Mahdy |
| author_facet | Mostafa Abbas Mostafa I. Soliman Sherif I. Rabia Keiji Kimura Ahmed El-Mahdy |
| author_sort | Mostafa Abbas |
| collection | DOAJ |
| description | Data dependence analysis is a must-do operation for parallelisation since it reveals the safe parallelisable regions of serial codes. Generally, it relies on dynamic analysis, which incurs substantial execution time and memory space overheads. As a result, there have been many efforts in the literature to strike a balance between accuracy and runtime overhead. The approaches generally rely on random instruction sampling, parallelising analysis, as well as filtering statically determined dependencies and independencies. This paper considers an alternate approach of conducting static analysis at runtime, exploiting available states just before executing loops, potentially improving precision. In particular, the paper adopts abstract interpretation using interval, congruent, and bisector domains for detecting memory data dependencies in binary programs at runtime. Abstract interpretation has the advantage of being associated with the execution semantics, making it more natural to model binary instruction execution. The profiler is implemented on top of the Pin framework and evaluated using the Polyhedral, NPB, and SPEC 2006 benchmarks suites. Results show a mean accuracy of 90.4% with an average <inline-formula> <tex-math notation="LaTeX">$16.3 \times$ </tex-math></inline-formula> speedup in time in comparison with related work, making it a promising approach. |
| first_indexed | 2024-12-22T20:43:28Z |
| format | Article |
| id | doaj.art-c4c5791943904dbba85ca6c20a23c1b4 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-22T20:43:28Z |
| publishDate | 2022-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-c4c5791943904dbba85ca6c20a23c1b42022-12-21T18:13:17ZengIEEEIEEE Access2169-35362022-01-0110316263164010.1109/ACCESS.2022.31607299738611Accelerating Data Dependence Profiling Through Abstract Interpretation of Loop InstructionsMostafa Abbas0https://orcid.org/0000-0001-6781-5384Mostafa I. Soliman1Sherif I. Rabia2https://orcid.org/0000-0003-1471-8841Keiji Kimura3https://orcid.org/0000-0003-2325-4866Ahmed El-Mahdy4https://orcid.org/0000-0001-9736-1352Department of Computer Science and Engineering, Egypt–Japan University of Science and Technology, New Borg El-Arab City, EgyptDepartment of Computer Science and Engineering, Egypt–Japan University of Science and Technology, New Borg El-Arab City, EgyptDepartment of Computer Science and Engineering, Egypt–Japan University of Science and Technology, New Borg El-Arab City, EgyptDepartment of Computer Science and Engineering, Waseda University, Tokyo, JapanDepartment of Computer Science and Engineering, Egypt–Japan University of Science and Technology, New Borg El-Arab City, EgyptData dependence analysis is a must-do operation for parallelisation since it reveals the safe parallelisable regions of serial codes. Generally, it relies on dynamic analysis, which incurs substantial execution time and memory space overheads. As a result, there have been many efforts in the literature to strike a balance between accuracy and runtime overhead. The approaches generally rely on random instruction sampling, parallelising analysis, as well as filtering statically determined dependencies and independencies. This paper considers an alternate approach of conducting static analysis at runtime, exploiting available states just before executing loops, potentially improving precision. In particular, the paper adopts abstract interpretation using interval, congruent, and bisector domains for detecting memory data dependencies in binary programs at runtime. Abstract interpretation has the advantage of being associated with the execution semantics, making it more natural to model binary instruction execution. The profiler is implemented on top of the Pin framework and evaluated using the Polyhedral, NPB, and SPEC 2006 benchmarks suites. Results show a mean accuracy of 90.4% with an average <inline-formula> <tex-math notation="LaTeX">$16.3 \times$ </tex-math></inline-formula> speedup in time in comparison with related work, making it a promising approach.https://ieeexplore.ieee.org/document/9738611/Abstract interpretationdata dependence profilingdynamic binary analysisinterval domaincongruent domainbisector domain |
| spellingShingle | Mostafa Abbas Mostafa I. Soliman Sherif I. Rabia Keiji Kimura Ahmed El-Mahdy Accelerating Data Dependence Profiling Through Abstract Interpretation of Loop Instructions IEEE Access Abstract interpretation data dependence profiling dynamic binary analysis interval domain congruent domain bisector domain |
| title | Accelerating Data Dependence Profiling Through Abstract Interpretation of Loop Instructions |
| title_full | Accelerating Data Dependence Profiling Through Abstract Interpretation of Loop Instructions |
| title_fullStr | Accelerating Data Dependence Profiling Through Abstract Interpretation of Loop Instructions |
| title_full_unstemmed | Accelerating Data Dependence Profiling Through Abstract Interpretation of Loop Instructions |
| title_short | Accelerating Data Dependence Profiling Through Abstract Interpretation of Loop Instructions |
| title_sort | accelerating data dependence profiling through abstract interpretation of loop instructions |
| topic | Abstract interpretation data dependence profiling dynamic binary analysis interval domain congruent domain bisector domain |
| url | https://ieeexplore.ieee.org/document/9738611/ |
| work_keys_str_mv | AT mostafaabbas acceleratingdatadependenceprofilingthroughabstractinterpretationofloopinstructions AT mostafaisoliman acceleratingdatadependenceprofilingthroughabstractinterpretationofloopinstructions AT sherifirabia acceleratingdatadependenceprofilingthroughabstractinterpretationofloopinstructions AT keijikimura acceleratingdatadependenceprofilingthroughabstractinterpretationofloopinstructions AT ahmedelmahdy acceleratingdatadependenceprofilingthroughabstractinterpretationofloopinstructions |