An Inspector-Executor Algorithm for Irregular Assignment Parallelization

View/ Open
Use this link to cite
http://hdl.handle.net/2183/22436Collections
- Investigación (FIC) [1636]
Metadata
Show full item recordTitle
An Inspector-Executor Algorithm for Irregular Assignment ParallelizationDate
2004Citation
Arenaz M., Touriño J., Doallo R. (2004) An Inspector-Executor Algorithm for Irregular Assignment Parallelization. In: Cao J., Yang L.T., Guo M., Lau F. (eds) Parallel and Distributed Processing and Applications. ISPA 2004. Lecture Notes in Computer Science, vol 3358. Springer, Berlin, Heidelberg
Abstract
[Abstract] A loop with irregular assignment computations contains loop-carried output data dependences that can only be detected at run-time. In this paper, a load-balanced method based on the inspector-executor model is proposed to parallelize this loop pattern. The basic idea lies in splitting the iteration space of the sequential loop into sets of conflict-free iterations that can be executed concurrently on different processors. As will be demonstrated, this method outperforms existing techniques. Irregular access patterns with different load-balancing and reusability properties are considered in the experiments.
Keywords
Sequential loop
Algorithm
Algorithm
Description
This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science. The final authenticated version is available online at: https://doi.org/10.1007/978-3-540-30566-8_4
Editor version
ISSN
0302-9743
1611-3349
1611-3349
ISBN
978-3-540-24128-7 978-3-540-30566-8