Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Communication-Free Alignment for Array References with Linear Subscripts in Three Loop Index Variables or Quadratic Subscripts

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

Bau et al. proposed an efficient and precise data alignment method to ascertain whether there is communication-free alignment of array reference function with linear subscripts in one loop index variable. Chu et al. presented an efficient and precise data alignment method to determine whether there is communication-free alignment of array reference function with linear subscripts in two loop index variables or quadratic subscripts (ai2+bi+d). However, for array reference function with linear subscripts in three loop index variables or quadratic subscripts (ai2+bi+cj+d), their methods cannot be applied. In this paper, we propose two new alignment functions for loop iteration space and array elements. The new alignment functions can be applied towards checking whether there is communication-free alignment of array reference function with linear subscripts in three loop index variables or quadratic subscripts. Experiments with benchmarks taken from Parallel loop and Vector loop showed that among the 7 nested loops tested, three of them had their data alignment improved by the method proposed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Jack Edmonds. Systems of distinct representative and linear algebra, Journal of Research of National Bureau of Standards, Sect. B, 71(4):241-245, 1967.

    Google Scholar 

  2. J. Dongarra, M. Furtney, S. Reinhardt, and J. Russell. Parallel loops-a test suite for parallelizing compilers: Description andexample results, Parallel Computing 17:1247-1255, 1991.

    Google Scholar 

  3. David Levine, David Callahan, and Jack Dongarra. A comparative study of automatic vectorizing compilers, Parallel Computing 17:1223-1244, 1991.

    Google Scholar 

  4. David Bau, Induprakas Kodukula, Vladimir Kotlyar, Keshav Pingali, and Paul Stodghill. Solving alignment using elementary linear algebra. In: Conference Record of the 7th Workshop on Languages and Compilers for Parallel Computing, pp. 46-60, August 1994.

  5. Michael Wolfe. High Performance Compilers for Parallel Computing. Addison-Wesley Publishing Company, Redwood City, 1996.

    Google Scholar 

  6. John L. Hennessy and David A. Patterson. Computer Architecture: A Quantitative Approach, Second Edition. Morgan Kaufmann Publishers, Inc. San Francisco, California, 1996.

    Google Scholar 

  7. Chih-Ping Chu, Weng-Long Chang, Iwen Chen, and Peng-Sheng Chen. Communication-free alignment for array references with linear subscripts in two loop index variables or quadratic subscripts. Proceedings of the Second IASTED International Conference on Parallel and Distributed Computing and Networks (PDCN'98), Australia, pp. 571-576.

  8. M. Kandemir, A. Choudhary, N. Shenoy, P. Banerjee, and J. Ramanujam. A hyper-plane based approach for optimizing spatial locality in loop nests. In Proc.12th ACM Int. Conf. Supercomputing, July 1998.

  9. M. Kandemir, J. Ramanujam, A. Choudhary, and P. Banerjee. A loop transformation algorithm based on explicit dada layout representation for optimizing locality. In Proc.11th International Workshop, LCPC'98, Chapel Hill, NC, USA, August 1998.

  10. A. W. Lam and M. S. Lam. Maximizing parallelism andminimizing synchronization with affine partitions. Parallel Computing, 24(3–4):445-475, 1998.

    Google Scholar 

  11. V. Boudet, F. Rastello, and Y. Robert. Alignment and distribution is NOT (always) NP-hard. Proceeding of 1998 International Conference on Parallel and Distributed Systems, 5(9):648-657, 1998.

    Google Scholar 

  12. M. Kandemir, A. Choudhary, N. Shenoy, P. Banerjee, and J. Ramanujam. A linear algebra framework for automatic determination of optimal data layouts. IEEE Transactions on Parallel and Distributed Systems, 21(12):115-135, 1999.

    Google Scholar 

  13. A. W. Lam, G. I. Cheong, and M. S. Lam. An affine partitioning algorithm to maximize parallelism and minimize communication. 13th ACM International Conference on Supercomputing, Rhodes, Greece, pp. 228-237, June 1999.

  14. K.-P. Shih, J.-P. Sheu, and C.-H. Huang. Statement-level communication-free partitioning techniques for parallelizing compilers. The Journal of Supercomputing, 15(3):243-269, 2000.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Management Information System, Kung Shan Technology University, Tainan, 701, Taiwan R.O.C

    Weng-Long Chang

  2. Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan, 701, Taiwan R.O.C.

    Chih-Ping Chu & Jia-Hwa Wu

Authors
  1. Weng-Long Chang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chih-Ping Chu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jia-Hwa Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chang, WL., Chu, CP. & Wu, JH. Communication-Free Alignment for Array References with Linear Subscripts in Three Loop Index Variables or Quadratic Subscripts. The Journal of Supercomputing 20, 67–83 (2001). https://doi.org/10.1023/A:1011144404437

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1011144404437

Search

Navigation