Circular Shift of Loop Body - Programme Transformation, Promoting Parallelism

O. B. Steinberg

doi:10.14529/mmp170310

Авторы

O. B. Steinberg Южный федеральный университет

DOI:

https://doi.org/10.14529/mmp170310

Ключевые слова:

параллельные вычисления, преобразования программ, граф информационных связей, растягивание скаляров, разбиение цикла

Аннотация

В статье рассматривается преобразование программ, выполняющее круговой сдвиг операторов тела цикла. Его можно использовать для векторизации или распараллеливания. Это становится возможным благодаря тому, что при изменении порядка следования операторов тела цикла некоторые дуги, идущие снизу вверх, превращаются в дуги, идущие сверху вниз. Также иногда циклически порожденные дуги зависимости заменяются на циклически независимые. Следует отметить, что при выполнении кругового сдвига число итераций цикла уменьшается на единицу. Преобразование может применяться как независимо, так и совместно с другими преобразованиями, способствующими распараллеливанию. Такими преобразованиями могут являться: 'подстановка вперед', 'растягивание скаляров', 'приватизация', 'экспансия массивов' и другие. Возможности применения рассматриваемого в статье преобразования распространяются как на ручное распараллеливание, так и на добавление его в распараллеливающий (оптимизирующий) компилятор. При этом ограничение на циклы, применение преобразования к которым будет приводить к эквивалентному коду, сводится к циклам, для которых эквивалентной является раскрутка. Таким образом, они могут содержать вложенные циклы, условные операторы и другие операторы языка программирования.

Биография автора

O. B. Steinberg, Южный федеральный университет

кандидат физико-математических наук

Библиографические ссылки

Allen R., Kennedy K. Optimizing Compilers for Modern Architectures. San Francisco, San Diego, N.Y., Boston, London, Sidney, Tokyo, Morgan Kaufmann Publishers, 2002. 790 p.

Wolfe M. High Performance Compilers for Parallel Computing. Redwood City, AddisonWesley Publishing Company, 1996. 570 p.

Steinberg B.J. Matematicheskie metody rasparallelivaniya rekurrentnykh programnykh tsiklov na superkompyutery s parallel'noy pamyatyu [Parallelizing Recurrent Program Cycles with

Irregular Superposition Computation]. Rostov-on-Don, Rostov University Publishing House, 2004. 192 p.

Duo Liu, Zili Shao, Meng Wang, Minyi Guo, Jingling Xue. Optimal Loop Parallelization for Maximizing Iteration-Level Parallelism. Proceedings of International Conference on

Compilers, Architecture, and Synthesis for Embedded Systems (CASES 09). N.Y., ACM, 2009, pp. 67-76. DOI: 10.1145/1629395.1629407

Steinberg O.B. [Parallelizing Recurrent Program Cycles with Irregular Superposition

Computation]. Izvestiya vuzov. Severo-Kavkazskii region. Natural Science, 2009, no. 2, pp. 18-21. (in Russian)

Duo Liu, Yi Wang, Zili Shao, Minyi Guo, Jingling Xue. Optimally Maximizing Iteration-Level Loop Parallelism. IEEE Transactions on Parallel and Distributed Systems, 2012, vol. 23, no. 3, pp. 564-572. DOI: 10.1109/TPDS.2011.171

Steinberg O.B., Sukhoverkhov S.E. [Recurrent Program Loops with Stability Check]. Information Technologies, 2010, no. 1, pp. 40-45. (in Russian)

Muchnick S.S. Advanced Compiler Design and Implementation. San Francisco, Morgan Kauffman, 1997. 856 p.

Aho A.V., Lam M.S., Sethi R., Ullman J.D. Compilers: Principles, Techniques, and Tools. London, Pearson Education, 2007. 1014 p.

Evstigneev V.A., Sprogis S.V. [Vectorizing Programmes]. Vektorizatsiya programm: teoriya,

metody, realizatsiya [Vectorizing Programmes: Theory, Methods, Implementation]. Moscow, Mir, 1991, pp. 246-267. (in Russian)

Shulzhenko A.M. Issledovanie informatsionnykh zavisimostey programm dlya analiza rasparallelivayushchikh preobrazovaniy [Researching Information Dependences of Programs

for Analyzing Transformations Used for Parallelizing. The Dissertation for Scientic Degree

of the Candidate of Technology]. Rostov-on-Don, 2006, 200 p.

Steinberg O.B. Rasparallelivanie tsiklov, dopuskayushchikh rekurrentnye zavisimosti

[Parallelizing Loops Allowing Recurrent Dependences. The Dissertation for Scientic Degree

of the Candidate of Physics and Mathematical Science]. Institute for System Programming

of the Russian Academy of Sciences, Moscow, 2014.

Steinberg O.B. [Minimizing the Number of Temporary Arrays in Loop Distribution Problem].

Izvestiya vuzov. Severo-Kavkazskii region. Natural Science, 2011, no. 5, pp. 31-35. (in Russian)

Feautrier P. Array Expansion. Proceedings of the 2nd International Conference on Supercomputing, N.Y., ACM, 1988, pp. 429-441. DOI: 10.1145/55364.55406