Skip to Main content Skip to Navigation
Conference papers

Approximate Data Dependence Profiling based on Abstract Interval and Congruent Domains

Abstract : Although parallel processing is mainstream, existing programs are often serial, and usually re-engineering cost is high. Data dependence profiling allows for automatically assessing parallelisation potential; Yet, data dependence profiling is notoriously slow and requires large memory, as it generally requires keeping track of each memory access. This paper considers employing a simple abstract single-trace analysis method using simple interval and congruent modulo domains to track dependencies at lower time and memory costs. The method gathers and abstracts the set of all memory reference addresses for each static memory access instruction. This method removes the need for keeping a large shadow memory and only requires a single pair-wise analysis pass to detect dependencies among memory instructions through simple intersection operations. Moreover, the combination of interval and congruent domains improves precision when compared with only using an interval domain representation, mainly when the data is not accessed in a dense access pattern. We further improve precision through partitioning memory space into blocks, where references in each block abstracted independently. An initial performance study is conducted on SPEC CPU-2006 benchmark programs and polyhedral benchmark suite. Results show that the method reduces execution time overhead by 1.4x for polyhedral and 10.7x for SPEC2006 on average; and significantly reduces memory by 109780x and 6981x for polyhedral and SPEC2006 respectively; the method has an average precision of 99.05% and 61.37% for polyhedral and SPEC respectively. Using memory partitioning resulted in improving mean precision to be 82.25% and decreasing memory reduction to be 47x for SPEC2006 suite.
Document type :
Conference papers
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-02914569
Contributor : Erven Rohou <>
Submitted on : Wednesday, August 12, 2020 - 9:04:32 AM
Last modification on : Thursday, January 7, 2021 - 4:39:05 PM
Long-term archiving on: : Monday, November 30, 2020 - 6:35:02 PM

File

ARCS2020_Abbas.pdf
Files produced by the author(s)

Identifiers

Citation

Mostafa Abbas, Rasha Omar, Ahmed El-Mahdy, Erven Rohou. Approximate Data Dependence Profiling based on Abstract Interval and Congruent Domains. ARCS 2020 - 33rd International Conference on Architecture of Computing Systems, May 2020, Aachen (virtual), Germany. pp.3-16, ⟨10.1007/978-3-030-52794-5_1⟩. ⟨hal-02914569⟩

Share

Metrics

Record views

77

Files downloads

210