АЛГОРИТМ ПОИСКА ПАРАЛЛЕЛЬНОСТИ БЕЗ СИНХРОНИЗАЦИЙ ВО ВЛОЖЕННОСТЯХ ЦИКЛОВ |
2 | |
2012 |
научная статья | 004.272 | ||
203-209 | автоматическое распараллеливание, вложенность циклов, CUDA, GPU, SIMD |
Предлагается алгоритм поиска параллельности во вложенностях циклов с учетом того, что в качестве целевой архитектуры выступают графические процессоры NVIDIA. Задача алгоритма заключается в выделении максимального количества независимых потоков в исходной вложенности. Результаты работы алгоритма могут быть использованы как входная информация для существующих методов генерации SIMD-кода. |
1 . 1. NVIDIA Corporation. NVIDIA CUDA C programming guide. November, 2010. Version 3.2. 2 . Brodtkorb A., Dyken C. State-of-the-art in heterogeneous computing // Scientific Programming journal. Amsterdam: IOS Press, 2010. V. 18. P. 1-33. 3 . Штейнберг Б.Я. Математические методы распараллеливания рекуррентных циклов для суперкомпьютеров с параллельной памятью. Ростов-на-Дону: Издательство Ростовского университета, 2004. 192 с. 4 . Арапбаев Р.Н., Евстигнеев В.А., Осмонов Р.А. Анализ зависимостей: основные тесты на зависимость по данным // Сибирский журн. вычислительной математики. Новосибирск, 2007. Т. 10. С. 247-265. 5 . Касьянов В.Н., Мирзуитова И.Л. Реструктурирующие преобразования: алгоритмы распараллеливания циклов // Программные средства и математические основы информатики. Новосибирск: Институт систем информатики им. А.П. Ершова СО РАН, 2004. С. 142-188. 6 . Gautam G., Radjopadhye S. The Z-polyhedra model // Proceedings of the 12-th ACM SIGPLAN symposium on principles and practice of parallel programming. N.Y.: ACM, 2007. P. 237-248. 7 . Ахо А., Лам М., Сети Р. Компиляторы. Принципы, технологии и инструментарий. 2-е изд. М.: Вильямс, 2008. 1184 с. 8 . Pouchet L., Bastoul C. Iterative optimization in the polyhedral model: part 1, one-dimensional time // Proceedings of the International Symposium on Code Generation and Optimization, CGO'07. Washington: IEEE Computer Society, 2007. P. 144-156. 9 . Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2004. 608 с. 10 . Lim A., Lam M. Maximizing parallelism and minimizing synchronization with affine transform // Proceedings of the 24-th ACM SIGPLAN-SIGACT. N.Y.: ACM, 1997. P. 215-227. 11 . Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация (комбинаторная теория многогранников). М.: Наука, 1981. 344 с. 12 . Feautrier P. Some efficient solutions to the affine scheduling problem. One-dimensional time // International Journal of Parallel Programming. Norwell: Kluwer Academic Publishers, 1992. V. 21. P. 313-348. 13 . Беклемишев Д.В. Курс аналитической геометрии и линейной алгебры. 10-е изд. М.: Физматлит, 2005. 304 с. 14 . Курош А.Г. Курс высшей алгебры. СПб.: Лань, 2004. 432 с. 15 . http://www.cs.umd.edu/projects/omega/ (дата обращения: 10.01.2012) 16 . Pugh W. The Omega test: a fast and practical integer programming algorithm for dependence analysis // Proceedings of the 1991 ACM/IEEE conference on Supercomputing. N.Y.: ACM, 1991. P. 4-13. |