An Inspector-Executor Algorithm for Irregular Assignment Parallelization
Use this link to citehttp://hdl.handle.net/2183/22436
MetadataShow full item record
TitleAn Inspector-Executor Algorithm for Irregular Assignment Parallelization
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] 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.
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