METHOD OF RANKING TILES SIZE PARAMETERS OF а PARALLEL ALGORITHM
Abstract
A method for obtaining tiles of operations of a parallel algorithm is developed. Propositions for ranking tiles size parameters are stated and proved. Statements to assess the amount of communication operations generated by the partition of the set of iterations are stated and proved.
About the Authors
N. A. LIKHODED
Belаrusian State University, Minsk
Belarus
Belarus
M. A. PALIASHCHUK
Belаrusian State University, Minsk
Belarus
Belarus
References
1. Baskaran, M. Automatic C-to-CUDA code generation for affine programs / M. Baskaran, J. Ramanujam, P. Sadayappan // Proceedings of the Compiler Construction, 19th International Conference. Part of the Joint European Conferences on
2. Theory and Practice of Software. – Paphos, Cyprus, March 2010.
3. Xue, J. Time-minimal tiling when rise is larger than zero / J. Xue, W. Cai // Parallel Computing. – 2002. – Vol. 28, N 5. – P. 915–939.
4. Kim, D. G. Parameterized tiling for imperfectly nested loops / D. G. Kim, S. Rajopadhye // Technical Report CS-09-101, Colorado State University, Department of Computer Science, February 2009. – 21 p.
5. Automatic parallelization of tiled loop nests with enhanced fine-grained parallelism on GPUs / P. Di [et al.] // 41st International Conference on Parallel Processing. – Pittsburgh, PA, USA, September 2012. IEEE Computer Society, 2012. – P. 350–359.
6. Bandishti, V. Tiling stencil computations to maximize parallelism / V. Bandishti, I. Pananilath, U. Bondhugula // Proceedings of Supercomputing. – Los Alamitos, CA, USA. IEEE Computer Society Press, 2012. – P. 40:1–40:11.
7. Воеводин, В. В. Параллельные вычисления / В. В. Воеводин, Вл. В. Воеводин. – СПб.: БХВ-Петербург, 2002. – 608 с.
8. Feautrier, P. Some efficient solutions to the affine scheduling problem. Part 1 / P. Feautrier // International J. of Parallel Programming. – 1992. – Vol. 21, N 5. – P. 313–348.
9. Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model / U. Bondhugula [et al.] // Lecture notes in computer science. – 2008. – N 4959. – P. 132–146.
10. Лиходед, Н. А. Оценка объема коммуникационных операций параллельного зернистого алгоритма / Н. А. Лиходед, М. А. Полещук // Междунар. конгресс по информатике: информационные системы и технологии CSIST’2013, 4–7 ноября 2013 г., Минск, Беларусь. Бел. гос. ун-т. – Минск, 2013. – С. 377–381.
11. Лиходед, Н. А. Характеристика локальности параллельных реализаций многомерных циклов / Н. А. Лиходед // Докл. НАН Беларуси. – 2010. – Т. 54, № 1. – С. 26–32.
12. Адуцкевич, Е. В. К распараллеливанию последовательных программ: распределение массивов между процессорами и структуризация коммуникаций / Е. В. Адуцкевич, Н. А. Лиходед, А. О. Сикорский // Кибернетика и системный анализ. – 2012. – Т. 48, № 1. – С. 144–163.
Review
Views: 808
Email this article 