ПАРАЛЛЕЛЬНЫЕ ВЕРСИИ РЕАЛИЗАЦИИ МНОГОМЕРНЫХ ЦИКЛОВ
Аннотация
Формулируются и доказываются условия, при выполнении которых параллельные версии алгоритмов, заданных вложенными циклами, можно получить незначительной модификацией исходного последовательного алгоритма. Исследуются загруженность процессоров и задача выбора зерна вычислений.
Об авторах
Н. А. Лиходед
Институт математики НАН Беларуси
Беларусь
Беларусь
А. А. Толстиков
Белорусский государственный университет
Беларусь
Беларусь
Список литературы
1. Воеводин, В.В. Параллельные вычисления / В.В. Воеводин, Вл.В. Воеводин. – СПб.: БХВ-Петербург, 2002. – 608 с.
2. Воеводин В.В. Вычислительная математика и структура алгоритмов / В.В. Воеводин // МГУ [Электронный ресурс] – 2006. – Режим доступа: http://parallel.ru/info/parallel/voevodin/. – Дата доступа: 26.12.2007.
3. Darte, A. Mathematical tools for loop transformations: from systems of uniform recurrence equations to the polytope model / A. Darte // Algorithms for Parallel Processing, IMA Volumes in Mathematics and its Applications. – 1999. – Vol. 105. – P. 147–183.
4. Feautrier, P. Some efficient solutions to the affine scheduling problem. Part 2 / P. Feautrier // Int. J. of Parallel Programming. – 1992. – Vol. 21, № 6. – P 389–420.
5. Lim, A.W. Maximizing parallelism and minimizing synchronization with affine partitions / A.W. Lim, M.S. Lam // Parallel Computing. – 1998. – Vol. 24, № 3, 4. – P. 445–475.
6. Adutskevich, E.V. Affine transformations of loop nests for parallel execution and distribution of data over processors / E.V. Adutskevich, S.V. Bakhanovich, N.A. Likhoded. – Минск, 2005. – 10 с. – (Препринт / НАН Беларуси, Ин-т математики; № 3 (574)).
7. (Pen)-Ultimate Tiling? / P. Boulet [еt al.] // Integration, The VLSI J. – 1994. – Vol. 17. – P. 33–51.
8. Hodzic, E. On-Time Optimal Supernode Shape / E. Hodzic, W. Shang // IEEE Transactions on Parallel and Distributed Systems. – 2002. – Vol. 13, № 12. – P. 1220–1223.
9. Xue, J. Time-minimal tiling when rise is larger than zero / J. Xue, W. Cai // Parallel Computing. – 2002. – Vol. 28, № 5. – P. 915–939.
10. Баханович, С.В. Отображение алгоритмов на вычислительные системы с распределенной памятью: оптимизация тайлинга для одно- и двумерных топологий / С.В. Баханович, П.И. Соболевский // Весцi НАН Беларусi. Сер. фiз.-мат. навук. – 2006. – № 2. – С. 106–112.
Рецензия
Для цитирования:
Лиходед Н.А., Толстиков А.А. ПАРАЛЛЕЛЬНЫЕ ВЕРСИИ РЕАЛИЗАЦИИ МНОГОМЕРНЫХ ЦИКЛОВ. Информатика. 2008;(2(18)):129-136.
Просмотров: 427
Послать статью по эл. почте 