среда, 14 января 2009 г.

Правила gpgpu

Года полтора назад когда я подбирал конфигурация нового компа, я остановился видеокарте на GeForce 8600GT. В результате моим первым мануалом по программированию видеокарт стала pdf-ка NVIDIA_CUDA_Programming_Guide_1.0. Позже я сравнив теоретическое максимальное быстродействие и цены на карты со сравнимым быстродействием я перекинулся в стан fanATIc-ов. Но осваивая ATI CTM – я нашёл много общего в способах оптимизации кернелов. Естественно ввиду того что у чипов отличается архитектура напрямую применять подходы предложенные nVidia нельзя. До появления 4ххх не было способа организовать coalesced global memory access на железе АДМ в случае если адресс памяти по которому обращается тред не был функцией от его номера (по причине отсутствия кеша в SIMD array). По той же причине не было возможности организовать синхронизацию тредов (кроме синхронизации через глобальную память в R670, которая увеличивала количество обращений к ОП пропорционально количеству тредов). А вот советы из статейки nVidia которые легко применяются на видеокартах ATI :
- Структурируйте ваше приложение таким образом чтобы максимально использовать паралеллизм. (я бы добавил : используйте подход «shared nothing» по максимуму)
– Постарайтесь уменьшить передачу данных с/на видеокарту. От себя : для GeForce 2xx и всех программируемых Radeon (поскольку возможно асинхронная передача данных – тоесть во время вычислений) можно маскировать задержки передачи данных на видеокарту если у вас один кернел вызывается многократно или несколько подряд.
– Для жирафов советуют coalesce global memory accesses, и судя по результатам теста  это одинаково полезно для всех видеокарт (рандом рид у всех одинаково медленный). Суть же в том что к памяти нужно обращятся последовательно. От себя – есть два способа: первый состоит в том что нужно так написать код что бы адресс ячейки памяти к которой должен обратится тред за параметрами должен быть функцией от номера треда, второй – из памяти читает только один тред и сразу записывает всё что прочитал в локальный кеш, что казалось бы тоже разумно если бы не падение производительности в результате того что остальные треды в это время простаивают, что в общем называется branch divergence и само по себе очень не хорошо. 
– Используйте локальную память, shared memory в CUDA и LDS в чипах AMD. Признаю совет банальный.
– Локальная память в чипах nVidia поделена на банки, и желательно устранить одновременное обращение на запись к одному банку от более чем 4-ёх тредов. Актуальноть для карт АМД следует выяснить.
– Не все инструкции одинаково полезны, часть инструкций реализовано программно с помощью нескольких более простых инструкции, в доке описано какими хаками выполнять те же действия, без дорогих инструкций, хаки работают не всегда. В описанном ранее тесте  можно посмотреть какие именно инструкции на каких картах тормозят.

– Постарайтесь ораганизовывать ветвления на уровне SIMD engine, тоесть что бы в каждом варпе все треды делали одну и ту же работу, для аргументами ветвлений должны быть номера варпов, но не тредов. Подобное получится не всегда. Придется выворачивать алгоритм. Напишу как-то как вывернул один алгоритм (распространения сигнала между слоями нейросети), для того что бы не использовать запись по произвольному адресу. В упоминавшемся уже тесте ветвления на жирафе были бесплатными, возможно авторы просто не смогли достичь необходимого эффекта, а возможно дело в разном количестве элементов в SIMD блоке.

Разные ссылки : 

http://www.gpgpu.org/s2007/slides/03-data-parallel-algorithms-and-data-structures.pdf

http://www.cs.unc.edu/~naga/parcomp07.pdf - Эффективное использование кеша

http://www.cs.unc.edu/~naga/sc06.pdf - Модели памяти

вторник, 13 января 2009 г.

Обработка баз данных там же)))

Моё знакомство с gpgpu началось с вот этой статьи. Выделили несколько ресурсоёмких, паралельных подзадач при обработке ДБ и сгрузили на видаху. Прирост быстродействия от использования жирафа 5900 вместо ксеона на 2.8 в раёне 5-20 раз, правда у них это всё было сделано только для реляционных сценариев. Мне больше интересны СУООБД или ещё лучше MAP/REDUCE. 


gpgpu на службе армии

Вы когда небудь слышали о Computer Generated Forces (CGFs)  ? это комьпьютерные системы позволяющие эмулировать обстановку на поле боя, поведение бойцов их решения и тактику .  Вот список подобных систем: Training, Exercise, Military 
Operations (TEMO); Advanced Concepts and 

Requirements (ACR); and Research, Development and Acquisition (RDA). А вот дока в которой описывается как в таких приложения использовать видеокарты. В ней описывается одна из подзадач свойственная таким приложениям - ответ на вопрос какие бойцы видят каких вражеских бойцов (LINE OF SIGHT по ихнему). Помоему подобное должно быть реализовано в современных играх, шутерах. В статье описывается предложеный автором алгоритм частично сгружающий эту задачу на видаху. К сожалению статья очень древняя и там описывается испольозание 4-ого жирафа, в результате данный подход к совеременным карточкам применим слабо, а если и применим - то уж явно лучше написать самому. Хотя задачка интересная. В терминаторе точно стоит CrossFireX)))) Что забавно одна из подобных систем так и называется CROSSFIRE: an IDE for operational training. Вот ещё один кладезь знаний, на этот раз на тему моделирования всех и вся.

Алгоритмы и структуры данных в gpgpu

Нашёл интересную статью о программировании видах. Ничего координально нового просто всё очень красиво, академично изложено. Новичкам в gpgpu советую. Наиболее важное : на архитектуру видеокарт наиболее природно ложатся функциональные примитивы Map & Reduce, а так же Sort & Search (которые описываются в другой доке которую я пока не нашёл). Нашёл целый кладезь подобных публикаций просто найдя личную страница автора одной из интересных док на эту тему. Так же всем кто интересуется этой темой советую перечитать все публикации SIGGRAPH 200x какие найдёте, более старые мало смысла просто. Вот за 2008 и за 2007, последний даже интересней как для меня.

Исчё один тест


Результат кракера-ломакера MD5 BursWF на 64 битной системе windows server 2008 enterprise, Pentium DC 2160, RadeonHD 4670 ( всё на референсных частотах).