«Автоматическое отображение Фортран-программ на графический процессор»

5.4 О построенной оценке эффективности

Описанная модель оценки времени выполнения программы не может учесть часть факторов, влияющих на результат. Прежде всего, алгоритм работы компилятора неизвестен, поэтому сложно оценить реальное число генерируемых транзакций в глобальную память для обработки одного обращения. Также неизвестными остаются оптимизации на уровне кода, которые осуществил компилятор программы – изменение порядка инструкций, возможное построение оптимального дерева вычислений, векторизация. Более того, использование предиктора предполагается в ситуации, когда код в представлении CUDA не был сгенерирован.

Планировщики инструкций не гарантируют определённого порядка исполнения блоков и варпов в блоке. В модели сделано предположение о том, что все варпы и блоки равноправны между собой.

Аналогичное можно сказать и про обработку запросов на осуществление транзакций – алгоритм работы, используемый в контроллере памяти неизвестен; предполагается, что контроллер обслуживает поступающие запросы в порядке очереди, равноправно и независимо.

Также неизвестен алгоритм работы кэш-памяти. Влияние кэша заметно на программах, где доминируют задержки обмена с глобальной памятью (случай MWP <= CWP). В данном исследовании был осуществлён прогноз запуска в двух режимах – без использования кэш памяти и с как можно более эффективным её использованием.

В задачах, где задержки на обращение к памяти играют большую роль – эти два случая представляют собой оценку сверху и снизу времени исполнения функции-ядра. Без использования кэш-памяти в архитектуре Fermi размер транзакции уменьшается до 32-х байт [6], таким образом увеличивая их количество. Эта ситуация моделируется в предикторе. Такой режим предпочтителен, когда в программе осуществляется доступ в разрозненные куски памяти или все нити обращаются к одной и той же ячейке. Обычно в вычислительных задачах работают с секциями массивов, организуя выровненный доступ. Таким образом прогноз без использования кэша характеризует оценку сверху. С другой стороны, предположение о максимальном использовании кэша оценивает работу функции снизу, т.к. есть определённое количество обменов с глобальной памятью и вычислений, которые не могут быть проигнорированы. Использование кэш-памяти при запуске программы в DVM-системе можно только ограничить по размеру, т.е. кэш используется при каждом запуске. Поэтому результаты реальных запусков располагаются между этим двумя прогнозами. Для уточнения вычисляется корректирующий коэффициент. Он может быть вычислен, как медиана отклонения отношений прогнозов, упоминавшихся выше. Такой подход возможен в том случае, когда в наличии нет графического ускорителя. Если графический ускоритель есть, то можно воспользоваться соотношением попаданий/промахов в кэш, измеренных на модельной программе. Таким образом узнаём в среднем долю использования кэша. При построении прогноза пересчитываем соотношение обращений в память и обращений в кэш с учётом коэффициента.

Итоговый коэффициент № 1 – 0,68822.

Итоговый коэффициент № 2 – 0,72224.

6 Полученные результаты

Для проведения тестов использовался графический ускоритель Tesla C2050, используемый в гибридном вычислительном кластере К-100. Ускоритель имеет архитектуру Fermi (compute_capability 2.0).

Предиктор выделил в программе 26 функций ядер, для каждого было построено три прогноза: с учётом влияния кэша, без учёта влияния кэша и предлагаемая линейная комбинация приведённых выше прогнозов.

В четырёх циклах, время вычисления которых оказалось наибольшим, основной вклад вносят обращения к памяти, поскольку производится невыровненный доступ к массивам. Очевидно, предиктор сгенерировал больше транзакций к глобальной памяти, чем есть на самом деле. Это произошло из-за разбиения транзакций по 32 байта, а также из-за того, что в прогнозе ничего не попадало в кэш: все обращения к массивам считались обращениями к глобальной памяти. Сильное расхождение прогноза и результатов запуска на цикле loop_174 нельзя объяснить с точки зрения анализа кода исходной программы: циклы loop_161 и loop_191 обладают аналогичной структурой. Для них расхождение меньше.

Прогноз с учётом кэша, построенный с использованием коррекктирующего коэффициента. Расхождение между прогнозом и запуском на основных циклах составило 24,27%.

Пример вычислительно трудной задачи. Влияние кэша невелико. Расхождение между графиком прогноза и запуска объясняется неизвестным алгоритмом распределения регистров. В условиях запуска (с размерами блоков по умолчанию) максимальное количество регистров на одну нить, которое может позволить себе каждый варп, составляет 63 штуки. При реальном запуске количество регистров различается у разных варпов, в циклах, занимающих самое большое время (имеющих достаточное количество обменов с памятью и хорошую вычислительную интенсивность), это количество достигается. Предиктор прогнозирует данное число порядка 80 – 90. Поскольку регистров не хватает, предиктор обрабатывает эту ситуацию, как лишние обращения к глобальной памяти.

Заключение

В данной дипломной работе реализован модуль предиктор, который по коду последовательной программы и результатам работы эксперта DVMH строит возможное отображение программы на графический ускоритель, оценивает время выполнения данного отображения и его эффективность.

В процессе выполнения работы:

1. 
   Изучен подход по отображению параллельных программ на графические ускорители, который применяется в системе DVM
   
2. 
   Изучены спецификации выполнения программ на графических ускорителях архитектуры Fermi
   
3. 
   Реализован программный модуль, который учитывает возможности графического ускорителя данной архитектуры.
   
4. 
   В модуле учтены документированные особенности выполнения программ на графическом ускорителе, для прочих были сделаны эмпирические предположения.
   

Программный модуль написан на языке Си++. Текст программы составляет 3282 строки.

Литература

1. 
   Коновалов Н.А., Крюков В.А., Погребцов А.А., Поддерюгина Н.В., Сазанов Ю.Л. Параллельное программирование в системе DVM. Языки Fortran-DVM и C-DVM // Труды Международной конференции "Параллельные вычисления и задачи управления" (PACO’2001) Москва, 2-4 октября 2001 г., 140-154 с.
   
2. 
   «DVMH-система», ИПМ им. Келдыша РАН, Москва, Россия
   

[HTML] (http://www.keldysh.ru/dvm/dvmhtm1107/rus/dvmh.html)

3. 
   High Performance Fortran Forum. High Performance Fortran Language Specification, version 2.0, January 1997.
   

[HTML] (http://hpff.rice.edu/versions/hpf2/index.htm)

4. 
   OpenMP Application Program Interface. Version 3.1. July 2011.
   

[PDF] (http://www.openmp.org/mp-documents/OpenMP3.1.pdf)

5. 
   Бахтин В.А., Катаев Н.А., Клинов М.С., Крюков В.А., Поддерюгина Н.В., Притула М.Н. Автоматическое распараллеливание Фортран-программ на кластер с графическими ускорителями // Труды международной научной конференции “Параллельные вычислительные технологии (ПаВТ’2012)” (Новосибирск, 26 – 30 марта 2012 г.) – Челябинск: Издательский центр ЮУрГУ, 2012, c. 373-379
   
6. 
   Боресков А.В., Харламов А.А., Марковский Н.Д., Микушин Н.Д., Мортиков Е.В., Мыльцев А.А., Сахарных Н.А., Фролов В.А. Параллельные вычисления на GPU. Архитектура и программная модель CUDA. М: Издательство Московского университета, 2012. 324 с.
   
7. 
   Крюков В.А. Разработка параллельных программ для вычислительных кластеров и сетей. // Информационные технологии и вычислительные системы. № 1-2, 2003 г., стр. 42-61.
   
8. 
   Куприк И.В. Система автоматизации распараллеливания. Предсказание времени выполнения программ на графическом процессоре (дипломная работа). Москва, Россия, 2012
   
9. 
   Ken Kennedy, Charles Koelbel, Hans Zima, The Rise and Fall of High Performance Fortran: An Historical Object Lesson, Proceedings of the third ACM SIGPLAN conference on History of programming languages 2007, San Diego, California, June 09 - 10, 2007
   
10. 
    Sunpyo Hong, Hyesoon Kim, An Analytical Model for a GPU Architecture with Memory-level and Thread-level Parallelism Awareness. Extended Technical report, Georgia Institute of Technology, USA, 2009
    
11. 
    Kishore Kothapalli, Rishabh Mukherjee, Suhail Rehman, Suryakant Patidar, P. J. Narayanan, Kannan Srinathan, A Performance Prediction Model for the CUDA GPGPU Platform, International Institute of Information Technology, Hyderabad, India, 2010
    
12. 
    NVIDIA CUDA C Programming Guide, NVIDIA Corporation, 2012
    
13. 
    Бахтин В.А., Бородич И.Г., Катаев Н.А., Клинов М.С., Ковалева Н.В., Крюков В.А., Поддерюгина Н.В. Диалог с программистом в системе автоматизации распараллеливания САПФОР // Вестник Нижегородского университета им. Н.И. Лобачевского, серия “Информационные технологии”. – Н. Новгород: Изд-во ННГУ, 2012, №5 (2). – C. 242-245.
    

жүктеу/скачать 1.18 Mb.

Достарыңызбен бөлісу: