GPGPU *

Аннотация

В данной статье хочу рассказать как можно эффективно распараллелить алгоритм BFS — поиск в ширину в графе с использованием графических ускорителей. В статье будет приведен подробный анализ полученного алгоритма. Вычисления выполнялись на одном GPU GTX Titan архитектуры Kepler.

Введение

В последнее время все большую роль играют графические ускорители (GPU) в не графических вычислениях. Потребность их использования обусловлена их относительно высокой производительностью и более низкой стоимостью. Как известно, на GPU хорошо решаются задачи на структурных сетках, где параллелизм так или иначе легко выделяется. Но есть задачи, которые требуют больших мощностей и используют неструктурные сетки. Примером такой задачи является Single Shortest Source Path problem (SSSP) – задача поиска кратчайших путей от заданной вершины до всех остальных во взвешенном графе. Решение данной задачи рассмотрено мной в этой статье. Вторым примером задачи на неструктурных сетках является задача Breadth First Search (BFS) — поиска в ширину в неориентированном графе. Данная задача является основной в ряде алгоритмов на графах. Также она немного проще, чем поиск кратчайшего пути. На данный момент алгоритм BFS используется как основной тест для рейтинга Graph500. Далее рассмотрим, как можно использовать идеи решения задачи SSSP в задаче BFS. Про архитектуру GPU компании Nvidia и об упомянутых алгоритмах уже много написано, поэтому в этой статье я не стану дополнительно писать про это. Так же, надеюсь, что понятия warp, cuda блок, SMX, и прочие базовые вещи, связанные с CUDA читателю знакомы.

Аннотация

В данной статье хочу рассказать как можно эффективно распараллелить алгоритм SSSP — поиска кратчайшего пути в графе с использованием графических ускорителей. В качестве графического ускорителя будет рассмотрена карта GTX Titan архитектуры Kepler.

Введение

В последнее время все большую роль играют графические ускорители (GPU) в не графических вычислениях. Потребность их использования обусловлена их относительно высокой производительностью и более низкой стоимостью. Как известно, на GPU хорошо решаются задачи на структурных сетках, где параллелизм так или иначе легко выделяется. Но есть задачи, которые требуют больших мощностей и используют неструктурные сетки. Примером такой задачи является Single Shortest Source Path problem (SSSP) – задача поиска кратчайших путей от заданной вершины до всех остальных во взвешенном графе. Для решения данной задачи на CPU существует, по крайней мере, два известных алгоритма: алгоритм Дейсктры и алгоритм Форда-Беллмана. Так же существуют параллельные реализации алгоритма Дейстры и Форда-Беллмана на GPU. Вот основные статьи, в которых описаны решения данной задачи:

Предисловие

Доброго времени суток! Сегодня решил поделиться с Вами сокровенным — одним из своих любимых велосипедов.

Начну издалека — довольно долго я работал на одном радиозаводе в Челябинске, и был у нас (вообще и сейчас есть, просто я уже не там) один мега-проект: оптико-электронный модуль для охраны физических объектов. Это такая здоровая штука на поворотной установке, с тремя камерами на все случаи жизни (цветная — дневная, ЧБ светочувствительная — для сумерек, и тепловизор — для ночного наблюдения). Берётся такой модуль, ставится на вышку высотой метров 50 — и можно днём и ночью держать под наблюдением территорию в радиусе 4-5 километров. Подробности писать не стану, не о том пост. Кому интересно — сами найдут.

Разумеется, интересных задачек по обработке изображений было много. Об одной из таких я и хочу рассказать. А именно — как использовать массивно-парралельные вычисления для компенсации дрожания камеры в реальном времени, или почему SURF подходит не всегда. Добро пожаловать под кат.

Введение

Я описываю результаты применения способов оптимизации вычислений на CUDA при моделировании плазмы. Вычисления производятся с использованием Java-привязки к CUDA (JCUDA) [1] на GT630 (Kepler). Моделирование происходит как решение задачи Коши — задание значений параметров в начальный момент времени, затем приращение времени и перерасчет всех уравнений, и т.д. многократно. Вычисления происходят в двойной точности (double). Правильность полученных результатов подтверждена вычислениями на CPU без JCUDA.

Не так уж и давно стало популярным использовать видеокарты для вычислений. В один прекрасный день, несколько лет назад и я взглянул на новую, тогда, технологию CUDA. В руках была хорошая карточка по тем временам GTX8800, да и задачки для распараллеливания тоже были.
Кто работал с GPU, знает про объединение запросов, конфликт банков и как с этим бороться, а если не работал, то можно найти несколько полезных статей по основам программирования на CUDA[1]. Карта GTX8800, в некотором смысле, была хороша тем, что была одной из первых и поддерживала только первые версии CUDA, поэтому на ней было четко заметно, когда есть конфликты банков или запросы в глобальную память не объединяются, потому что время в этом случае увеличивалось в разы. Все это помогало лучше понять все правила работы с картой и писать нормальный код.
В новые модели добавляют все больше и больше функциональности, что облегчает и ускорят разработку. Появились атомарные операции, кеш, динамический параллелизм и т.д.
В посте я расскажу про пространственно-временную фильтрацию изображений и реализацию для compute capability = 1.0, и как можно ускорить получившийся результат за счет новых возможностей.
Временная фильтрация может пригодиться при наблюдении за спутниками или в прочих ситуациях фильтрации, когда требуется точное подавление фона.

Многие из новейших суперкомпьютеров основаны на аппаратных ускорителях вычислений (accelerator). включая две самые быстрые системы согласно TOP500 от 11/2013. Ускорители распространяются так же и на обычных PC и даже появляются в портативных устройствах, что ещё больше способствовует росту интереса к программированию ускорителей.

Такое широкое применение ускорителей является результатом их высокой производительности, энергоэффективности и низкой стоимости. Например, если сравнить Xeon E5-2687W и GTX 680, выпущенные в марте 2012, мы увидим, что GTX 680 в четыре раза дешевле, имеет в 8 раз большую производительность операций одинарной точности и в 4 раза большую пропускную способность памяти, а так же обеспечивает более 30 раз большую производительность в пересчёте на доллар и в 6 раз большую производительность на ватт. Исходя из таких сравнительных результатов, ускорители должны бы использоваться везде и всегда. Почему же этого не происходит?

Давным давно, в 2008 году, когда я работал над своей диссертацией меня заинтересовала тема применения сверточных нейронных сетей для задач распознавания изображений. На тот момент они еще не были так популярны как сейчас и попытка найти готовые библиотеки ни к чему не привела — нашлась только реализация на Lush (языке созданном автором сверточных сетей, Яном ЛеКуном). Тогда я подумал, что можно было бы их реализовать на Матлабе используя Neural Network Toolbox. Но столкнулся с невозможностью реализации разделяемых весов в рамках этого тулбокса. И тогда было принято решение написать собственную реализацию.

Несколько дней назад состоялся релиз CUDA 5.5. К сожалению, основное число нововведений и удобностей касается владельцев видеокарт с Compute Capability 3.5.

Но есть кое-что, что подойдет всем пользователям основных дистрибутивов Linux — появились репозитории!

Полный список можно посмотреть в Release Notes [pdf]. Под катом список того, что мне показалось наиболее интересным.

Всем привет! Я решил рассказать вам о том, как оптимизировал алгоритм майнинга лайткоинов. А представлю я свой рассказ в форме дневника.

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

При этом большинство ну хотя бы минимально сложных и функциональных систем (во всяком случае, из тех, что встречались лично мне за 8 лет работы в банковской сфере), как правило, гетерогенны — состоят из множества функциональных блоков, как пёстро сшитое лоскутное одеяло, где каждый лоскуток выполняется разным приложением, зачастую даже на различных аппаратных платформах. Почему? Да просто это рационально и удобно. Каждый продукт хорош в своей области. Например, экономисты любят использовать Ms Excel для анализа и визуализации данных. Но мало кому в голову придёт использовать эту программу для обучения серьёзных искусственных нейросетей или решения дифференциальных уравнений в реальном времени — для этого зачастую приобретаются (или уже приобретены компанией) мощные универсальные пакеты, предлагающие гибкий API, или под заказ пишутся отдельные модули. Вот и получается, что результат считать выгоднее в том же Matlab, хранить в таблицах СУБД Oracle (запущенной на кластере Linux), а отчёт показывать пользователям в приложении Excel, работающем как OLE server на Windows. Причём связаны все эти компоненты одним из универсальных языков программирования.

Как выбрать оптимальную среду реализации для конкретной задачи?

Недавно я опубликовал статью о распределенном рендеринге на GPU — поступили некоторые вопросы и предложения. Поэтому считаю нужным рассказать о теме более развернуто (и с картинками, а то без картинок статьи практически не читают), тем самым привлечь к этой теме больше читателей.
Думаю, этим вопросом заинтересуются обладатели мощных вычислительных систем: майнеры, геймеры, админы других мощных вычислительных систем.

Многие обладатели мощного железа задумывались над тем, а нельзя ли подзаработать на мощности своей железки, пока она стоит бестолку?


Красота моя бестоковая!

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

Но, наряду с хранением информации, будет не менее полезным для нас сервис облачно-распределенных вычислений, и в частности, рендеринга.

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

Итак, что такое «рендеринг»? Рендеринг — это вычислительный процесс, в ходе которого, мы получаем красивую картинку по 3д модели с помощью программы «рендера».
Что такое «распределенный»? Это когда хранение или вычисление данных распределяют между множеством компьютеров или серверов, объединенными одной сетью (см. распределенные вычисления).
Распределенный рендеринг — вычислительный процесс, по созданию изображений, распределенный между компьютерами. Вычисления также могут на себя брать облака.

Всем доброго дня,

Надеюсь, при прочтении этого блока в своём ридере, моя картинка вас не напугала. Но сегодня, я хочу описать применение взаимодействия технологии CUDA с OpenGL на примере моего небольшого pet-примера, первую версию которого я описывал в статье ранее. Тех, кому интересен раздел, известный под английским названием CUDA and OpenGL interoperability,

Данная статья написана с целью продемонстрировать как с помощью технологии CUDA можно смоделировать простое взаимодействие заряженых частиц (см. Закон Кулона). Для вывода статической картинки я использовал библиотеку freeglut.
Как пишут частенько на Хабре:

Здравствуй, Хабр!

Несколько лет назад в прикладных целях я реализовал обычный Force-based визуализатор графов.

На меня произвело впечатление, как простые итеративные преобразования могут производить субъективно сложные и интересные вычисления, формируя нетривиальные визуально-кинетические модели.

Со временем возникло несколько идей, что интересного можно смоделировать.

Вот что получилось с одной из них (в кадре мелкие объекты, смотреть в HD):

Как создать рендерер, который бы работал даже на компьютере вашей бабушки? Изначально перед нами стояла немного другая задача — создать unbiased рендер для всех моделей GPU: NVidia, ATI, Intel.
Хотя идея такого рендера для всех видеокарт витала в воздухе давно, до качественной реализации, тем более на Direct3D, дело не доходило. В своей работе мы пришли к весьма дикой связке и дальше расскажем, что нас к ней привело и как она работает.

При использовании средств параллельных вычислений весьма вероятно может сложиться ситуация, когда алгоритм содержит два таких последовательных этапа: i) каждый j-ый поток сохраняет некоторый промежуточный результат вычисления в j-ой ячейке памяти, а, затем, ii) этот поток должен использовать результаты одного или более «соседних» потоков. Очевидно, что необходимо организовать в коде программы некий барьер по времени, который каждым потоком преодолевается уже после того, как все сохранят свои промежуточные результаты в соответствующих ячейках памяти (этап (i)). В противном случае, какой-то поток может перейти к этапу (ii), пока какие-то другие потоки еще не завершили этап (i). Как это ни прискорбно, но создатели CUDA посчитали, что такой специальный встроенный механизм синхронизации любого числа потоков на одном GPU не нужен. Так как же можно бороться с этой напастью? Хотя Google, судя по подсказкам, и знаком с данным вопросом, но готового удовлетворительного рецепта под свою задачу найти не удалось, а на пути к достижению желаемого результата для новичка (которым я и являюсь) имеются некоторые подводные камни.

Вступление

Недавно, почитав различных статей и презентаций про GPGPU, я решил тоже попробовать для себя программирование под видеокарты. Фактически, выбор технологий в этой области не велик — сейчас живы и развиваются только CUDA (проприетарный стандарт nVidia) и OpenCL (свободный стандарт, работает на GPU от ATI, nVidia, а также на центральных процессорах). В связи с тем, что мой ноутбук располагает видеокартой ATI (Mobility Radeon 5650 HD), то выбор и вовсе свёлся к одному варианту — OpenCL. В этой статье речь пойдёт о процессе изучения OpenCL с нуля, а также о том, что из этого получилось.

На Github выложен исходный код компилятора Rootbeer, с помощью которого можно почти любой Java-код запустить на графическом процессоре, а также легко разделить Java-программу на фрагменты для CPU/GPU.

Компилятор опубликован под лицензией MIT, он прошёл тщательное тестирование и вполне пригоден для использования. По словам автора, это самый продвинутый транслятор байткода Java на платформу CUDA. Судя по всему, OpenCL тоже поддерживается.

Автор программы — преподаватель Сиракузского университета Фил Пратт-Желига (Phil Pratt-Szeliga).

В последнее время параллельные вычисления прочно входят в жизнь, в частности, с использованием GPU.

Здесь было много статей на эту тему, поэтому ограничусь лишь поверхностным описанием технологии. GPGPU — использование графических процессоров для задач общего назначения, т.е. не связанных напрямую с рендерингом. Пример — библиотека Nvidia PhysX для расчёта физики в некоторых современных играх. Эта технология выгодна тем, что GPU хороши на параллельном выполнении с множеством потоков. Правда, потоков должно быть много, иначе производительность сильно упадет. Ещё из-за особенностей работы с памятью приходится несколько хитрить с передачей данных из оперативной памяти в видеопамять. Известные реализации: CUDA (Nvidia, только для видеокарт), OpenCL (Khronos Group, для гетерогенных систем) и AMD FireStream. Здесь будет обсуждаться только OpenCL.

Итак, приступим к практике. В качестве языка основной программы выберем Python. Он, конечно, не очень быстр сам по себе, зато отлично работает как «клей» — во многих применениях основной расчёт идёт в OpenCL, а код на Python только «подносит патроны». Существует отличная библиотека PyOpenCL, которой и будем пользоваться.