Оценка локальности параллельных алгоритмов, реализуемых на графических процессорах
Автор: Лиходед Н.А., Полещук М.А.
Рубрика: Информатика, вычислительная техника и управление
Статья в выпуске: 3 т.5, 2016 года.
Бесплатный доступ
Исследуется задача получения блоков операций и потоков операций параллельного алгоритма, приводящих к меньшему числу обращений к глобальной памяти и к эффективному использованию параллельными потоками вычислений кэшей и разделяемой памяти графического процессора. Сформулированы и доказаны утверждения, позволяющие оценить объем коммуникационных операций, порождаемых альтернативными вариантами задания размеров блоков вычислений, а также минимизировать число промахов кэша за счет использования временной и пространственной локальности данных с учетом размера и длины строк кэша. Исследования конструктивны и допускают программную реализацию для практического использования.
Параллельные вычисления, графический процессор, минимизация объема коммуникационных операций, временная локальность, пространственная локальность
Короткий адрес: https://sciup.org/147160603
IDR: 147160603 | УДК: 519.67 | DOI: 10.14529/cmse160307
Estimate of locality of parallel algorithms implemented on GPUs
The problem of obtaining blocks of operations and threads of parallel algorithm resulting in a smaller number of accesses to global memory and resulting in the efficient use of caches and shared memory graphics processor is investigated. We formulated and proved statements to assess the volume of communication transactions generated by alternative sizing of blocks, as well as to minimize the number of cache misses due to the use of temporal and spatial locality of data. The research is constructive and allows software implementation for practical use.
Список литературы Оценка локальности параллельных алгоритмов, реализуемых на графических процессорах
- Лиходед Н.А. Полещук М.А. Метод ранжирования параметров размера блоков вычислений параллельного алгоритма//Доклады НАН Беларуси. 2015. Т. 59, № 4. С. 25-33.
- Kandemir M., Ramanujam J., Irwin M., Narayanan V., Kadayif I., Parikh A. A compiler based approach for dynamically managing scratch-pad memories in embedded systems//IEEE Transactions on Computer-Aided Design. 2004. Vol. 23, No. 2. P. 243-260.
- Baskaran M., Bondhugula U., Krishnamoorthy S., Ramanujam J., Rountev A., Sadayappan P. Automatic data movement and computation mapping for multi-level parallel architectures with explicitly managed memories//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., Cai W. Time-minimal tiling when rise is larger than zero//Parallel Computing. 2002. Vol. 28, No. 5. P. 915-939.
- Baskaran M., Ramanujam J., Sadayappan P. Automatic C-to-CUDA code generation for affine programs//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., Baskaran M., Krishnamoorthy S., Ramanujam J., Rountev A., Sadayappan P. Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model//Lecture notes in computer science. 2008. No. 4959. P. 132-146.
- Venkataraman G., Sahni S., Mukhopadhyaya S. A blocked all-pairs shortest-paths algorithm//J. Exp. Algorithmics. 2003. Vol. 8. P. 2.2.
- Katz G.J., Kider J. All-pairs shortest-paths for large graphs on the GPU//Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware. Sarajevo, Bosnia and Herzegovina: Eurographics Association. 2008. P. 47-55.
- Lund B.D., Smith J.W. A multi-stage cuda kernel for floyd-warshall//CoRR abs/1001.4108. 2010.
