Распараллеливание рекуррентных циклов с предварительным вычислением суперпозиций

Как правило, именно циклы являются участками кода, вычисление которых занимает много времени. Поэтому, именно на них направляются особые усилия при ускорении программ, в частности, через распараллеливание.

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

В статье описывается алгоритм распараллеливания циклов, вычисляющих элементы рекуррентно заданной последовательности. Рекуррентные циклы, рассматриваемые в статье, непосредственно распараллелены быть не могут. С помощью вспомогательных преобразований иногда их можно привести к циклам, допускающим параллельное выполнение. Ранее автором статьи был опубликован другой алгоритм распараллеливания циклов, вычисляющих элементы рекурсивно заданной последовательности. В современных процессорах время выполнения арифметических операций оказывается на порядок меньше, чем считывание аргументов этих операций из оперативной памяти. В данной статье приводятся оценки сложности по обращению к памяти, для описываемого алгоритма. Представленный в статье параллельный алгоритм оказывается более эффективным по обращениям к памяти, чем алгоритм, описанный автором ранее.

Литература

1. Allen, R. Optimizing Compilers for Modern Architectures / R. Allen, K. Kennedy. - San Francisco; San Diego; New York; Boston; London; Sidney; Tokyo: Morgan Kaufmann Publishers, 2002.
2. Wolfe, M. High Performance Compilers for Parallel Computing / M. Wolfe. - Redwood City: Addison-Wesley Publishing Company, 1996.
3. Steinberg, O.B. Circular Shift of Loop Body-Programme Transformation, Promoting Parallelism / O.B. Steinberg // Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. - 2017. - Т. 10, № 3. - P. 120-132.
4. Штейнберг, Б.Я. Распараллеливание рекуррентных циклов с условными операторами / Б.Я. Штейнберг // Автоматика и телемеханика. - 1995. - № 6. - С. 176-184.
5. Штейнберг, О.Б. Распараллеливание рекуррентных циклов с нерегулярным вычислением суперпозиций / О.Б. Штейнберг // Известия ВУЗов. Северокавказский регион. Естественные науки. - 2009. - № 2. - С. 18-21.
6. Штейнберг, О.Б. Автоматическое распараллеливание рекуррентных циклов с проверкой устойчивости / О.Б. Штейнберг, С.Е. Суховерхов // Информационные технологии. - 2010. - № 1. - С. 40-45.
7. Штейнберг, О.Б. Распараллеливание циклов, допускающих рекуррентные зависимости: дис. ... канд. физ.-мат. наук / О.Б. Штейнберг. - М., 2014.
8. Штейнберг, Б.Я. Математические методы распараллеливания рекуррентных программных циклов на суперкомпьютеры с параллельной памятью / Б.Я. Штейнберг. - Ростов-на-Дону: Изд-во Ростовского ун-та, 2004.
9. Graham, R.L. Concrete Mathematics: a Foundation for Computer Science / R.L. Graham, D.E. Knuth, O. Patashnik. - New York: Addison-Welsey, 1994.
10. Самарский, А.А. Введение в численные методы / А.А. Самарский. - М.: Наука, 1997.
11. Graham, S.L. Getting Up to Speed: the Future of Supercomputing / S.L. Graham, M. Snir, C.A. Patterson. - Washington: National Academies Press, 2005.
12. Оптимизирующая распараллеливающая система. - URL: http://ops.rsu.ru (дата обращения 1.07.2020).
13. Оптимизирующий компилятор Pluto. - URL: http://pluto-compiler.sourcefofge.net (дата обращения 1.07.2020).
14. Компилятор ROSE. - URL: http://rosecompiler.org/ (дата обращения 1.07.2020).