Nested-Loops Tiling for Parallelization and Locality Optimization

Authors

  • Saeed Parsa Department of Computer Engineering, Iran University of Science and Technology
  • Mohammad Hamzei Department of Computer Engineering, Iran University of Science and Technology

Keywords:

Nested loops parallelization, loop tiling, data locality, parallel\break computing

Abstract

Data locality improvement and nested loops parallelization are two complementary and competing approaches for optimizing loop nests that constitute a large portion of computation times in scientific and engineering programs. While there are effective methods for each one of these, prior studies have paid less attention to address these two simultaneously. This paper proposes a unified approach that integrates these two techniques to obtain an appropriate locality conscious loop transformation to partition the loop iteration space into outer parallel tiled loops. The approach is based on the polyhedral model to achieve a multidimensional affine scheduling as a transformation that result the largest groups of tilable loops with maximum coarse grain parallelism, as far as possible. Furthermore, tiles will be scheduled on processor cores to exploit maximum data reuse through scheduling tiles with high volume of data sharing on the same core consecutively or on different cores with shared cache at around the same time.

Downloads

Download data is not yet available.

Author Biographies

Saeed Parsa, Department of Computer Engineering, Iran University of Science and Technology

Saeed Parsa received his B.Sc. in Mathematics and Computer Science from Sharif University of Technology, Iran, his M.Sc. degree in computer science from the University of Salford in England, and his Ph.D. in computer science from the University of Salford, England. He is an associate professor of Computer Science at the Iran University of Science and Technology. His research interests include reverse engineering and parallel and distributed computing.

Mohammad Hamzei, Department of Computer Engineering, Iran University of Science and Technology

Mohammad Hamzei received his B.Sc. degree from Razi University, Iran, and his M.S. degree from Iran University of Science and Technology, in 2007 and 2009, respectively, all in Computer Engineering. He is currently working towards the PhD degree in the Department of Computer Engineering, Iran University of science and technology. His research interests are in the areas of parallel and distributed processing, compiler optimization for high performance computing and parallel programming models design and implementation.

Downloads

Published

2017-07-06

How to Cite

Parsa, S., & Hamzei, M. (2017). Nested-Loops Tiling for Parallelization and Locality Optimization. COMPUTING AND INFORMATICS, 36(3), 566–596. Retrieved from http://www.cai.sk/ojs/index.php/cai/article/view/2017_3_566