Оценка локальности параллельных алгоритмов, реализуемых на графических процессорах

Николай Александрович Лиходед, Максим Александрович Полещук

Аннотация


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

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


параллельные вычисления, графический процессор, минимизация объема коммуникационных операций, временная локальность, пространственная локальность

Полный текст:

PDF

Литература


Лиходед, Н.А. Метод ранжирования параметров размера блоков вычислений параллельного алгоритма / Лиходед Н.А., Полещук М.А. // Доклады НАН Беларуси. — 2015. — Т. 59, № 4. — С. 25–33.

Kandemir, M. A compiler based approach for dynamically managing scratch-pad memories in embedded systems / M. Kandemir, J. Ramanujam, M. Irwin, V. Narayanan, I. Kadayif, A. Parikh // IEEE Transactions on Computer-Aided Design. — 2004. — Vol. 23, No. 2. — P. 243–260.

Baskaran, M. Automatic data movement and computation mapping for multi-level parallel architectures with explicitly managed memories / M. Baskaran, U. Bondhugula, S. Krishnamoorthy, J. Ramanujam, A. Rountev, P. Sadayappan // Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming. Salt Lake City, USA, February 20 – 23, 2008.

Воеводин, Вл.В. Спасительная локальность суперкомпьютеров / В.В. Воеводин, Вад.В. Воеводин // Открытые системы. — 2013, — № 9. — С. 12–15.

Воеводин, В.В. Параллельные вычисления / В.В. Воеводин, В.Вл. Воеводин — Санкт-Петербург: БХВ-Петербург, 2002. — 608 с.

Xue, J. Time-minimal tiling when rise is larger than zero / J. Xue, W. Cai // Parallel Computing. — 2002. — Vol. 28, No. 5. — P. 915–939.

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 Theory and Practice of Software. Paphos, Cyprus, March 20 – 28, 2010.

Bondhugula, U. Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model / U. Bondhugula, M. Baskaran, S. Krishnamoorthy, J. Ramanujam, A. Rountev, P. Sadayappan // Lecture notes in computer science. — 2008. — No. 4959. — P. 132–146.

Venkataraman, G. A blocked all-pairs shortest-paths algorithm / G. Venkataraman, S. Sahni, S. Mukhopadhyaya // J. Exp. Algorithmics. — 2003. — Vol. 8. — P. 2.2.

Katz, G.J. All-pairs shortest-paths for large graphs on the GPU / G.J. Katz, J. Kider // Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware. Sarajevo, Bosnia and Herzegovina: Eurographics Association. 2008. P. 47 – 55.

Lund, B.D. A multi-stage cuda kernel for floyd-warshall / B.D. Lund, J.W. Smith // CoRR abs/1001.4108. 2010.




DOI: http://dx.doi.org/10.14529/cmse160307