Оценка локальности параллельных алгоритмов, реализуемых на графических процессорах
Автор: Лиходед Н.А., Полещук М.А.
Рубрика: Информатика, вычислительная техника и управление
Статья в выпуске: 3 т.5, 2016 года.
Бесплатный доступ
Исследуется задача получения блоков операций и потоков операций параллельного алгоритма, приводящих к меньшему числу обращений к глобальной памяти и к эффективному использованию параллельными потоками вычислений кэшей и разделяемой памяти графического процессора. Сформулированы и доказаны утверждения, позволяющие оценить объем коммуникационных операций, порождаемых альтернативными вариантами задания размеров блоков вычислений, а также минимизировать число промахов кэша за счет использования временной и пространственной локальности данных с учетом размера и длины строк кэша. Исследования конструктивны и допускают программную реализацию для практического использования.
Параллельные вычисления, графический процессор, минимизация объема коммуникационных операций, временная локальность, пространственная локальность
Короткий адрес: https://sciup.org/147160603
IDR: 147160603 | DOI: 10.14529/cmse160307
Список литературы Оценка локальности параллельных алгоритмов, реализуемых на графических процессорах
- Лиходед Н.А. Полещук М.А. Метод ранжирования параметров размера блоков вычислений параллельного алгоритма//Доклады НАН Беларуси. 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.
