Circular Shift of Loop Body - Programme Transformation, Promoting Parallelism

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

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

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

Литература

1. Allen, R. Optimizing Compilers for Modern Architectures / R. Allen, K. Kennedy. - San Francisco; San Diego; N.Y.; Boston; London; Sidney; Tokyo: Morgan Kaufmann Publishers, 2002. - 790 p.
2. Wolfe, M. High Performance Compilers for Parallel Computing / M. Wolfe. - Redwood City: Addison-Wesley Publishing Company, 1996. - 570 p.
3. Штейнберг, Б.Я. Математические методы распараллеливания рекуррентных программных циклов на суперкомпьютеры с параллельной памятью / Б.Я. Штейнберг. - Ростов-на-Дону: Изд-во Ростовского ун-та, 2004. - 192 с.
4. Duo Liu. Optimal Loop Parallelization for Maximizing Iteration-Level Parallelism / Duo Liu, Zili Shao, Meng Wang, Minyi Guo, Jingling Xue // Proceedings of International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES 09). - N.Y.: ACM, 2009. - P. 67-76.
5. Штейнберг, О.Б. Распараллеливание рекуррентных циклов с нерегулярным вычислением суперпозиций / О.Б. Штейнберг // Известия вузов. Северо-Кавказский регион. Естественные науки. - 2009. - № 2. - С. 18-21.
6. Duo Liu. Optimally Maximizing Iteration-Level Loop Parallelism / Duo Liu, Yi Wang, Zili Shao, Minyi Guo, Jingling Xue // IEEE Transactions on Parallel and Distributed Systems. - 2012. - V. 23, № 3. - P. 564-572.
7. Штейнберг, О.Б. Автоматическое распараллеливание рекуррентных циклов с проверкой устойчивости / О.Б. Штейнберг, С.Е. Суховерхов // Информационные технологии. - 2010. - № 1. - C. 40-45.
8. Muchnick, S.S. Advanced Compiler Design and Implementation / S.S. Muchnick. - San Francisco: Morgan Kauffman, 1997. - 856 p.
9. Aho, A.V. Compilers: Principles, Techniques, and Tools / A.V. Aho, M.S. Lam, R. Sethi, J.D. Ullman. - London: Pearson Education, 2007. - 1014 p.
10. Евстигнеев, В.А. Векторизация программ / В.А. Евстигнеев, С.В. Спрогис // Векторизация программ: теория, методы, реализация. - М.: Мир, 1991. - С. 246-267.
11. Шульженко, А.М. Исследование информационных зависимостей программ для анализа распараллеливающих преобразований: дис. ... канд. техн. наук / А.М. Шульженко. - Ростов-на-Дону, 2006.
12. Штейнберг, О.Б. Распараллеливание циклов, допускающих рекуррентные зависимости: дис. ... канд. физ.-мат. наук / О.Б. Штейнберг. - Москва, 2014.
13. Штейнберг, О.Б. Минимизация количества временных массивов в задаче разбиения циклов / О.Б. Штейнберг // Известия высших учебных заведений. Северо-Кавказский регион. Естественные науки. - 2011. - № 5. - С. 31-35.
14. Feautrier, P. Array Expansion / P. Feautrier // Proceedings of the 2nd International Conference on Supercomputing. - N.Y.: ACM, 1988. - P. 429-441.