Exploiting locality in the run-time parallelization of irregular loops

Use this link to cite
http://hdl.handle.net/2183/23357Collections
- Investigación (FIC) [1632]
Metadata
Show full item recordTitle
Exploiting locality in the run-time parallelization of irregular loopsDate
2002-12-10Citation
M. J. Martin, D. E. Singh, J. Tourino and F. F. Rivera, "Exploiting locality in the run-time parallelization of irregular loops," Proceedings International Conference on Parallel Processing, Vancouver, BC, Canada, 2002, pp. 27-34.
Abstract
[Abstract] The goal of this work is the efficient parallel execution of loops with indirect array accesses, in order to be embedded in a parallelizing compiler framework. In this kind of loop pattern, dependences can not always be determined at compile-time as, in many cases, they involve input data that are only known at run-time and/or the access pattern is too complex to be analyzed In this paper we propose runtime strategies for the parallelization of these loops. Our approaches focus not only on extracting parallelism among iterations of the loop, but also on exploiting data access locality to improve memory hierarchy behavior and, thus, the overall program speedup. Two strategies are proposed one based on graph partitioning techniques and other based on a block-cyclic distribution. Experimental results show that both strategies are complementary and the choice of the best alternative depends on some features of the loop pattern.
Keywords
Runtime
Parallel processing
Data mining
Computer science
Pattern analysis
Sparse matrices
Fluid flow
Fluid dynamics
Finite element method
Degradation
Parallel processing
Data mining
Computer science
Pattern analysis
Sparse matrices
Fluid flow
Fluid dynamics
Finite element method
Degradation
Description
This is a post-peer-review, pre-copyedit version of an article published. The final authenticated version is available online at: http://dx.doi.org/10.1109/ICPP.2002.1040856
Editor version
ISSN
0190-3918
ISBN
0-7695-1677-7