Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free QP test: a dependence test for quadratic array subscripts

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)
      • 33. Shi, G.Y., Qian, W.Y., Pang, L.P.: ‘Optimization methods’ (Higher Education Press, 2007, 1st edn.) (in Chinese).
    2. 2)
      • 45. Wang, E.F.: ‘Linear algebra’ (Tsinghua University Press, 2007, 1st edn.) (in Chinese).
    3. 3)
      • 34. Mohammad, R.H.: ‘jSymbolic analysis for parallelizing compilers’ (Springer Publisher, 1995, 1st edn.).
    4. 4)
      • 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.
    5. 5)
      • 1. Allen, R., Kennedy, K.: ‘Optimizing compilers for modern architectures: a dependence-based approach’ (Morgan Kaufmann Publisher, 2001, 2nd edn.2002).
    6. 6)
      • 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.
    7. 7)
      • 33. Shi, G.Y., Qian, W.Y., Pang, L.P.: ‘Optimization methods’ (Higher Education Press, 2007, 1st edn.) (in Chinese).
    8. 8)
      • 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).
    9. 9)
      • 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).
    10. 10)
      • 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.
    11. 11)
      • 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.
    12. 12)
      • 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).
    13. 13)
      • 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).
    14. 14)
      • 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).
    15. 15)
      • 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.
    16. 16)
      • 27. Lotfi, S., Parsa, S.: ‘Parallel loop generation and scheduling’, J. Supercomput., 2009, 50, (3), pp. 289306 (doi: 10.1007/s11227-008-0262-5).
    17. 17)
      • 3. Wolfe, M.J.: ‘High performance compilers for parallel computing’ (Addison-Wesley Press, 1995, 1st edn.).
    18. 18)
      • 5. Banerjee, U.: ‘Dependence analysis (Loop transformations for restructuring compilers)’ (Springer Publisher, 1996, 1st edn.).
    19. 19)
      • 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.
    20. 20)
      • 45. Wang, E.F.: ‘Linear algebra’ (Tsinghua University Press, 2007, 1st edn.) (in Chinese).
    21. 21)
      • 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.
    22. 22)
      • 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).
    23. 23)
      • 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.
    24. 24)
      • 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).
    25. 25)
      • 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).
    26. 26)
      • 31. Zima, H., Chapman, B.: ‘Supercompilers for parallel and vector computers’ (ACM Press, 1991, 1st edn.).
    27. 27)
      • 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).
    28. 28)
      • 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).
    29. 29)
      • 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).
    30. 30)
      • 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).
    31. 31)
      • 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).
    32. 32)
      • 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).
    33. 33)
      • 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).
    34. 34)
      • 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).
    35. 35)
      • 4. Banerjee, U., Eigenmann, R., Nicolau, A., Padua, D.A.: ‘Automatic program parallelization’. Proc. IEEE, Santa Clara, CA, USA, February 1993, pp. 211243.
    36. 36)
      • 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.
    37. 37)
      • 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).
    38. 38)
      • 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.
    39. 39)
      • 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).
    40. 40)
      • 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).
    41. 41)
      • 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).
    42. 42)
      • 49. Smith, B.T., Boyle, J.M., Dongarra, J.J., et al: ‘Matrix eigensystem routines-eispack guide’ (Springer Publisher, 1988, 1st edn.).
    43. 43)
      • 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).
    44. 44)
      • 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.
    45. 45)
      • 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.
    46. 46)
      • 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).
    47. 47)
      • 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).
    48. 48)
      • 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.
    49. 49)
      • 28. Pugh, W.: ‘Definitions of dependence distance’, ACM Lett. Program. Lang. Syst., 1992, 1, (3), pp. 261265 (doi: 10.1145/151640.151645).
    50. 50)
      • 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.
    51. 51)
      • 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).
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