Increase parallel granularity and data locality by unimodular metrics

Guo Kai Ma, Xin Rang Wang, Peng Wang, Bin Yu Zang, Chuan Qi Zhu

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

We discusses a loop transformation method which would increase the granularity of the loop body and improve the data locality of the transformed loop. By analyzing the dependence vector set of the given nested double-loop, we could merge several nodes in the iteration space, which have same outer loop variable value and different inner loop variable value into one node in the folded iteration space, while preserving the parallelism of inner loop at the same time. Thus, we increased the granularity of the parallel loop body. Furthermore, we discussed how to find a unimodular metrics to transform the given iteration space with the given dependence into an iteration space in which iteration nodes could be merged using our methods given above. We also present a method to preserve the locality of the original loop while doing our loop transformation and iteration space folding. Our method discussed in this article is the generalization of the wavefront method. Compared with the wavefront method, our method can achieve higher performance due to larger granularity and better data locality. We apply our method to ygx, a program of the IAPCM Benchmark, to evaluate the effect of the technique. The experiment data show that our method can spare the execution time by 22% compared with the wavefront method when the program is parallel processed by 4 CPU's on SGI origin 200 system which is a typical 4 CPU's SMP architecture.

Original languageEnglish
Pages (from-to)516-523
Number of pages8
JournalJisuanji Xuebao/Chinese Journal of Computers
Volume27
Issue number4
StatePublished - Apr 2004
Externally publishedYes

Keywords

  • Data locality
  • Iteration space folding
  • Loop transformation
  • Parallelizing compiler
  • Unimodular metrics
  • Wavefront method

Fingerprint

Dive into the research topics of 'Increase parallel granularity and data locality by unimodular metrics'. Together they form a unique fingerprint.

Cite this