ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ СЕВЕРО-КАВКАЗСКИЙ РЕГИОН. 2017; 3: 76-80
http://dx.doi.org/10.17213/0321-2653-2017-3-76-80
ПРИМЕНЕНИЕ ПРЕОБРАЗОВАНИЯ ЦИКЛОВ «RETIMING» С ЦЕЛЬЮ УМЕНЬШЕНИЯ КОЛИЧЕСТВА ИСПОЛЬЗУЕМЫХ РЕГИСТРОВ
Штейнберг Олег Борисович – канд. физ.-мат. наук, ст. науч. сотрудник, Институт математики, механики и ком-пьютерных наук имени И.И. Воровича, Южный федеральный университет, г. Ростов-на-Дону, Россия. E-mail: olegsteinb@gmail.com
Ивлев Иван Анатольевич – студент, Институт математики, механики и компьютерных наук имени И.И. Воровича, Южный федеральный университет, г. Ростов-на-Дону,
Россия. E-mail: ivlev_1996@mail.ru
Аннотация
Рассматривается распараллеливающее преобразование программ «retiming». Это преобразование создавалось для того, чтобы увеличить степень распараллеливаемости программных циклов. Авторы данной работы предлагают его использовать для экономии используемых при вычислениях регистров. Преобразованием используется граф зависимостей по данным, вершинам и дугам которого присваиваются веса. Далее, исходя из полученных весов, строится результирующий код. В работе рассматривается область применения преобразования, а также вспомогательные преобразования, способные ее расширить. Данное преобразование может быть использовано оптимизирующими компиляторами. Авторами данной работы оно программно реализовано и добавлено в Оптимизирующую распараллеливающую систему (ОРС).
Ключевые слова: оптимизирующий компилятор; retiming; параллельные вычисления; преобразования циклов; граф зависимости по данным; регистры.
Полный текст: [in elibrary.ru]
Ссылки на литературу
- Duo Liu, Zili Shao, Meng Wang, Minyi Guo, Jingling Xue. Optimal Loop Parallelization for Maximizing Iteration-Level Parallelism // International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES'09) (Grenoble). 2009. P. 67 – 76
- Duo Liu, Yi Wang, Zili Shao, Minyi Guo, Jingling Xue. Optimally Maximizing Iteration-Level Loop Parallelism // International IEEE Trans. Parallel Distrib. Syst.: 2012, № 23(3), Р. 564 – 572
- Wolfe M. High Performance Compilers for Parallel Computing. Redwood city: Addison-Wesley Publishing Company, 1996. 570 p.
- Оптимизирующая распараллеливающая система. URL: http://ops.rsu.ru/about_OPS.html (дата обращения: 29.02.2017).
- Арапбаев Р.Н. Анализ зависимостей по данным: тесты на зависимость и стратегии тестирования: дис…. канд. физ.-мат. наук. Новосибирск: ИСИ СО РАН, 2008. 116 с.
- Бабичев А.В., Лебедев В.Г. Распараллеливание программных циклов // Программирование. 1983. № 5. С. 52 – 63.
- Шульженко А.М. Исследование информационных зависимостей программ для анализа распараллеливающих преобразований: дис….канд. техн. наук / РГУ. Ростов н/Д., 2006. 200 с.
- Штейнберг Б.Я. Математические методы распараллеливания рекуррентных программных циклов на суперкомпьютеры с параллельной памятью. Ростов н/Д.: Изд-во Рост. ун-та, 192 с.
- Allen R., Kennedy K. Optimizing Compilers for Modern Architectures. ‑ San Francisco; San Diego; New York; Boston; London; Sidney; Tokyo: Morgan Kaufmann Publishers, 2002. 790 p.
- Векторизация программ: теория, методы, реализация: сб. пер. статей. М.: Мир, 1991. С. 246 – 267.
- Штейнберг О.Б. Минимизация количества временных массивов в задаче разбиения циклов // Изв. вузов. Сев.-Кавк. регион. Естеств. науки. 2011. № 5. С. 31 – 35.
- Зыков А.А. Основы теории графов. М.: Вузовская книга, 2004. 662 с.
- Харари Ф. Теория графов. М.: Мир, 1973. 300 с.