http://iet.metastore.ingenta.com
1887

QP test: a dependence test for quadratic array subscripts

QP test: a dependence test for quadratic array subscripts

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Software — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Traditional dependence tests detect dependences with linear array subscripts, but only give passive results to those with non-linear expressions. It may result in a multitude of pseudo-dependences. To maximise the parallelism of applications and improve an optimising compiler's ability of detecting dependences between program statements, it is necessary to develop a non-linear dependence test to eliminate these pseudo-dependences. This study presents a new non-linear dependence test by analysing the optimal solution of the quadratic subscripts with the index bounds constraints. The authors prove that the non-linear dependences caused by subscripts, which can be written in the form of quadratic programming model, are able to be detected, and introduce a non-linear dependence testing algorithm based on quadratic programming. The effectiveness of this algorithm is verified. The authors developed a prototype implementation of the test with the Open64 compiler and evaluated it using some real world applications from Perfect Club benchmarks and Spec2006 benchmark suites. The experimental results indicate that, compared to existing testing methods, the quadratic programming (QP) test is more efficient for quadratic cases.

References

    1. 1)
      • 1. Allen, R., Kennedy, K.: ‘Optimizing compilers for modern architectures: a dependence-based approach’ (Morgan Kaufmann Publisher, 2001, 2nd edn.2002).
    2. 2)
      • 2. Shen, Z.Y., Li, Z.Y., Yew, P.C.: ‘An empirical on array subscripts and data dependencies’. Proc. Int. Conf. Parallel Processing, Pennsylvania, PA, USA, August 1989, pp. 145152.
    3. 3)
      • 3. Wolfe, M.J.: ‘High performance compilers for parallel computing’ (Addison-Wesley Press, 1995, 1st edn.).
    4. 4)
      • 4. Banerjee, U., Eigenmann, R., Nicolau, A., Padua, D.A.: ‘Automatic program parallelization’. Proc. IEEE, Santa Clara, CA, USA, February 1993, pp. 211243.
    5. 5)
      • 5. Banerjee, U.: ‘Dependence analysis (Loop transformations for restructuring compilers)’ (Springer Publisher, 1996, 1st edn.).
    6. 6)
      • 6. Goff, G., Kennedy, K., Tseng, C.W.: ‘Practical dependence testing’. Proc. ACM SIGPLAN Conf. Programming Language Design and Implementation, Toronto, Ontario, Canada, June 1991, pp. 1529.
    7. 7)
      • 7. Pugh, W.: ‘The Omega Test: a fast and practical integer programming algorithm for dependence analysis’, Commun. ACM, 1992, 35, (8), pp. 102114 (doi: 10.1145/135226.135233).
    8. 8)
      • 8. Dantzig, G.B., Eaves, B.C.: ‘Fourier-Motzkin elimination and its dual’, J. Comb. Theory B, 1973, 14, (3), pp. 288297 (doi: 10.1016/0097-3165(73)90004-6).
    9. 9)
      • 9. Kong, X., Klappholz, D., Psarris, K.: ‘The I test: an improved dependence test for automatic parallelization and vectorization’, IEEE Trans. Parallel Distrib. Syst., 1991, 2, (3), pp. 342349 (doi: 10.1109/71.86109).
    10. 10)
      • 10. Wolfe, M., Tseng, C.W.: ‘The power test for data dependence’, IEEE Trans. Parallel Distrib. Syst., 1992, 3, (5), pp. 591601 (doi: 10.1109/71.159042).
    11. 11)
      • 11. Psarris, K., Kong, X., Klappholz, D.: ‘The direction vector I test’, IEEE Trans. Parallel Distrib. Syst., 1993, 4, (11), pp. 12801290 (doi: 10.1109/71.250105).
    12. 12)
      • 12. Chang, W.L., Chu, C.P.: ‘The generalized direction vector I test’, Parallel Comput., 2001, 27, (11), pp. 11171144 (doi: 10.1016/S0167-8191(01)00086-2).
    13. 13)
      • 13. Huang, T.C., Chu, C.P.: ‘Data dependence analysis for array references’, J. Syst. Softw., 2000, 52, (1), pp. 5565 (doi: 10.1016/S0164-1212(99)00132-6).
    14. 14)
      • 14. Huang, T.C., Chu, C.P.: ‘Dependence analysis with direction vector for array references’, Comput. Electr. Eng., 2001, 27, (5), pp. 375393 (doi: 10.1016/S0045-7906(00)00035-5).
    15. 15)
      • 15. Kyriakopoulos, K., Psarris, K.: ‘Data dependence analysis techniques for increased accuracy and extracted parallelism’, Int. J. Parallel Program., 2004, 32, (4), pp. 317359 (doi: 10.1023/B:IJPP.0000035817.01263.d0).
    16. 16)
      • 16. Psarris, K., Kyriakopoulos, K.: ‘An experimental evaluation of data dependence analysis techniques’, IEEE Trans. Parallel Distrib. Syst., 2004, 15, (3), pp. 196213 (doi: 10.1109/TPDS.2004.1264806).
    17. 17)
      • 17. Huang, T.C., Yang, C.M.: ‘An exact data dependence analysis for array reference: the IR test’. Proc. Int. Conf. High Performance Computers, Ottawa, Canada, December 1996, pp. 124.
    18. 18)
      • 18. Li, Z., Yew, P.C., Zhu, C.Q.: ‘Data dependence analysis on multi-dimensional array references’. Proc. Int. Conf. Supercomputing, Heraklion, Crete, Greece, June 1989, pp. 215224.
    19. 19)
      • 19. Li, Z., Yew, P.C., Zhu, C.Q.: ‘An efficient and extract data dependence analysis for parallelizing compilers’, IEEE Trans. Parallel Distrib. Syst., 1990, 1, (1), pp. 2634 (doi: 10.1109/71.80122).
    20. 20)
      • 20. Maydan, D.E., Hennessy, J.L., Lam, M.S.: ‘Efficient and exact data dependence analysis’. Proc. ACM SIGPLAN Conf. Programming Language Design and Implementation, Toronto, Ontario, Canada, June 1991, pp. 114.
    21. 21)
      • 21. Petersen, P.M., Padua, D.A.: ‘Static and dynamic evaluation of data dependence analysis techniques’, IEEE Trans. Parallel Dstrib. Syst., 1996, 7, (11), pp. 11211132 (doi: 10.1109/71.544354).
    22. 22)
      • 22. Subhlok, J., Kennedy, K.: ‘Integer programming for array subscript analysis’, IEEE Trans. Parallel Distrib. Syst., 1995, 6, (6), pp. 662668 (doi: 10.1109/71.388048).
    23. 23)
      • 23. Colohan, B.C., Ailamaki, A., Steffan, J.G., Mowry, C.: ‘CMP support for large and dependent speculative threads’, IEEE Trans. Parallel Distrib. Syst., 2007, 18, (8), pp. 10411054 (doi: 10.1109/TPDS.2007.1081).
    24. 24)
      • 24. Blume, W., Eigenman, R., Hoeflinger, J., et al: ‘Automatic detection of parallelism: a great challenge for high-performance computing’, IEEE Parallel Distrib. Technol., 1994, 2, (3), pp. 3747 (doi: 10.1109/M-PDT.1994.329796).
    25. 25)
      • 25. Bulić, P., Dobravec, T.: ‘An approximate method for filtering out data dependencies with a sufficiently large distance between memory references’, J. Supercomput., 2011, 56, (2), pp. 226244 (doi: 10.1007/s11227-009-0364-8).
    26. 26)
      • 26. Guo, M.Y., Chang, W.L., Jiang, B., Huang, S.C., Tsai, S.T., Ho, M.: ‘Communication-free data alignment for arrays with exponential references in parallelizing compilers for scalable parallel systems’, J. Supercomput., 2012, 60, (1), pp. 430 (doi: 10.1007/s11227-009-0280-y).
    27. 27)
      • 27. Lotfi, S., Parsa, S.: ‘Parallel loop generation and scheduling’, J. Supercomput., 2009, 50, (3), pp. 289306 (doi: 10.1007/s11227-008-0262-5).
    28. 28)
      • 28. Pugh, W.: ‘Definitions of dependence distance’, ACM Lett. Program. Lang. Syst., 1992, 1, (3), pp. 261265 (doi: 10.1145/151640.151645).
    29. 29)
      • 29. Psarris, K.: ‘‘Program analysis techniques for transforming programs for parallel execution’, Parallel Comput., 2002, 28, (3), pp. 455469 (doi: 10.1016/S0167-8191(01)00132-6).
    30. 30)
      • 30. Wolfe, M., Banerjee, U.: ‘Data dependence and its application to parallel processing’, Int. J. Parallel Program., 1987, 16, (2), pp. 137178 (doi: 10.1007/BF01379099).
    31. 31)
      • 31. Zima, H., Chapman, B.: ‘Supercompilers for parallel and vector computers’ (ACM Press, 1991, 1st edn.).
    32. 32)
      • 32. Zhao, J., Zhao, R.C., Han, L.: ‘ A nonlinear array subscripts dependence test’. Proc. Int. Conf. High Performance Computing and Communication, Liverpool, UK, June 2012, pp. 764771.
    33. 33)
      • 33. Shi, G.Y., Qian, W.Y., Pang, L.P.: ‘Optimization methods’ (Higher Education Press, 2007, 1st edn.) (in Chinese).
    34. 34)
      • 34. Mohammad, R.H.: ‘jSymbolic analysis for parallelizing compilers’ (Springer Publisher, 1995, 1st edn.).
    35. 35)
      • 35. Blume, W., Eigenmann, R.: ‘Non-linear and symbolic data dependence testing’, IEEE Trans. Parallel Distrib. Syst., 1998, 9, (12), pp. 11801194 (doi: 10.1109/71.737695).
    36. 36)
      • 36. Engelen, R.A.van,  Birch, J., Shou, Y., Gallivan, K.A.: ‘A unified framework for nonlinear dependence testing and symbolic analysis’. Proc. Int. Conf. Supercomputing, Saint-Malo, France, June 2004, pp. 106115.
    37. 37)
      • 37. Wu, J.H., Chu, C.P.: ‘An exact data dependence test for quadratic expressions’, Inf. Sci., 2007, 177, (23), pp. 53165328 (doi: 10.1016/j.ins.2007.06.006).
    38. 38)
      • 38. Zhou, J., Zeng, G.H.: ‘A general data dependence analysis for parallelizing compilers’, J. Supercomput., 2008, 45, (2), pp. 236252 (doi: 10.1007/s11227-007-0168-7).
    39. 39)
      • 39. Hummel, J., Hendren, L.J., Nicolau, A.: ‘A general data dependence test for dynamic, pointer-based data structures’. Proc. ACM SIGPLAN Conf. Programming Language Design and Implementation, Orlando, Florida, USA , June 1994, pp. 218229.
    40. 40)
      • 40. Chen, T., Lin, J., Dai, X.R., Hsu, W.C., Yew, P.C.: ‘data dependence profiling for speculative optimizations’. Proc. Int. Conf. Compiler Construction, Barcelona, Spain, April 2004, pp. 5772.
    41. 41)
      • 41. Moseley, T., Shye, A., Reddi, V.J., Grunwald, D., Peri, R.: ‘Shadow profiling hiding instrumentation costs with parallelism’. Proc. IEEE/ACM Int. Sympo. Code Generation and Optimization, San Jose, CA, USA, April 2007, pp. 198208.
    42. 42)
      • 42. Yu, H.T., Li, Z.Y.: ‘Fast loop-level data dependence profiling’. Proc. Int. Conf. Supercomputing, San Servolo Island, Venice, Italy, June 2012, pp. 3746.
    43. 43)
      • 43. Kim, M.J., Kim, H., Luk, C.K.: ‘SD3: a scalable approach to dynamic data-dependence profiling’. Proc. IEEE/ACM Int. Symp. Microarchitecture, Atlanta, Georgia, USA, December 2010, pp. 535546.
    44. 44)
      • 44. Vanka, R., Tuck, J.: ‘Efficient and accurate data dependence profiling using software signatures’. Proc. IEEE/ACM Int. Sympo. Code Generation and Optimization, San Jose, CA, USA, April 2012, pp. 168195.
    45. 45)
      • 45. Wang, E.F.: ‘Linear algebra’ (Tsinghua University Press, 2007, 1st edn.) (in Chinese).
    46. 46)
      • 46. Padua, D.A., Eigenmann, R., Hoeflinger, J., et al: ‘Polaris: a new-generation parallelizing compiler for MPPs’. CSRD Report No. 1306, Center for Supercomputing Research and Development University of Illinois at Urbana-Champaign, 1993.
    47. 47)
      • 47. Blume, W., Eigenmann, R.: ‘Performance analysis of parallelizing compilers on the perfect benchmarks program’, IEEE Trans. Parallel Distrib. Syst., 1992, 3, (6), pp. 643656 (doi: 10.1109/71.180621).
    48. 48)
      • 48. Dongar, J., Furtney, M., Reinhardt, S.: ‘Parallel loops: a test suite for parallel compilers: description and example results’, Parallel Comput., 1991, 17, (10–11), pp. 12471255 (doi: 10.1016/S0167-8191(05)80036-5).
    49. 49)
      • 49. Smith, B.T., Boyle, J.M., Dongarra, J.J., et al: ‘Matrix eigensystem routines-eispack guide’ (Springer Publisher, 1988, 1st edn.).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-sen.2012.0142
Loading

Related content

content/journals/10.1049/iet-sen.2012.0142
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address