Imperial College London
Alternate

ProfessorPaulKelly

Faculty of Engineering, Department of Computing

Professor of Software Technology
 
 
 
//

Contact

 

+44 (0)20 7594 8332p.kelly Website

 
 
//

Location

 

Level 3 (upstairs), William Penney Building, room 304William Penney LaboratorySouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@article{Krieger:2013:10.1109/IPDPSW.2013.68,
author = {Krieger, CD and Strout, MM and Olschanowsky, C and Stone, A and Guzik, S and Gao, X and Bertolli, C and Kelly, PHJ and Mudalige, G and Van, Straalen B and Williams, S},
doi = {10.1109/IPDPSW.2013.68},
journal = {Proceedings - IEEE 27th International Parallel and Distributed Processing Symposium Workshops and PhD Forum, IPDPSW 2013},
pages = {375--384},
title = {Loop chaining: A programming abstraction for balancing locality and parallelism},
url = {http://dx.doi.org/10.1109/IPDPSW.2013.68},
year = {2013}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - There is a significant, established code base in the scientific computing community. Some of these codes have been parallelized already but are now encountering scalability issues due to poor data locality, inefficient data distributions, or load imbalance. In this work, we introduce a new abstraction called loop chaining in which a sequence of parallel and/or reduction loops that explicitly share data are grouped together into a chain. Once specified, a chain of loops can be viewed as a set of iterations under a partial ordering. This partial ordering is dictated by data dependencies that, as part of the abstraction, are exposed, thereby avoiding inter-procedural program analysis. Thus a loop chain is a partially ordered set of iterations that makes scheduling and determining data distributions across loops possible for a compiler and/or run-time system. The flexibility of being able to schedule across loops enables better management of the data locality and parallelism tradeoff. In this paper, we define the loop chaining concept and present three case studies using loop chains in scientific codes: the sparse matrix Jacobi benchmark, a domain-specific library, OP2, used in full applications with unstructured grids, and a domain-specific library, Chombo, used in full applications with structured grids. Preliminary results for the Jacobi benchmark show that a loop chain enabled optimization, full sparse tiling, results in a speedup of as much as 2.68x over a parallelized, blocked implementation on a multicore system with 40 cores. © 2013 IEEE.
AU  - Krieger,CD
AU  - Strout,MM
AU  - Olschanowsky,C
AU  - Stone,A
AU  - Guzik,S
AU  - Gao,X
AU  - Bertolli,C
AU  - Kelly,PHJ
AU  - Mudalige,G
AU  - Van,Straalen B
AU  - Williams,S
DO  - 10.1109/IPDPSW.2013.68
EP  - 384
PY  - 2013///
SP  - 375
TI  - Loop chaining: A programming abstraction for balancing locality and parallelism
T2  - Proceedings - IEEE 27th International Parallel and Distributed Processing Symposium Workshops and PhD Forum, IPDPSW 2013
UR  - http://dx.doi.org/10.1109/IPDPSW.2013.68
ER  -
Download