GPGPU *

Привет, хабрапользователь! После небольшого перерыва можно опять браться за трехмерную графику. В этот раз мы поговорим о таком алгоритме глобального затенения, как Normal-oriented Hemisphere SSAO. Интересно? Под кат!

Привет всем. Я уже однажды писал про Distance Field и приводил реализацию «эвристическим» кодом, дающую неплохую скорость: «Честный glow и скорость».

Зачем он нужен?

DField можно применять:

• Для значительного повышения качества шрифтов
• Для эффектов например горения контура. Один из эффектов я приводил в своей предыдущей статье
• Для эффекта «metaballs» но в 2д и для любых сложных шейпов. (возможно я когда-нибудь приведу пример реализации этого эффекта)
• А в данный момент DField мне нужен для качественного сглаживания углов и удаления мелких деталей.

И если в первых двух случаях мы можем заранее вычислить DField, то для других эффектов нам нужно просчитывать его в реальном времени.
В статье будет рассмотрен наиболее популярный, я бы сказал классический Chamfer distance (CDA) с кучей картинок, объясняющих принцип его работы, а так же рассмотрен двухпроходный алгоритм на GPU.
Оба алгоритма реализованы в демонстрационных программах на FPC.

Недавно на хабре была статья про проект OpenWorm. Проект использует OpenCL для расчета гидродинамики сглаженных частиц как на CPU, так и на GPU. Среди исследователей/разработчиков есть наши соотечественники Андрей Пальянов и Сергей Хайрулин из сибирского отделения Российской академии наук.

Под катом география комьюнити OpenWorm, а так же рейтинг популярности разработки на OpenCL по странам и ссылки на примеры для версии стандарта 2.0

Содержание

Часть 1: Введение.
Часть 2: Аппаратное обеспечение GPU и шаблоны параллельной коммуникации.
Часть 3: Фундаментальные алгоритмы GPU: свертка (reduce), сканирование (scan) и гистограмма (histogram).
Часть 4: Фундаментальные алгоритмы GPU: уплотнение (compact), сегментированное сканирование (segmented scan), сортировка. Практическое применение некоторых алгоритмов.
Часть 5: Оптимизация GPU программ.
Часть 6: Примеры параллелизации последовательных алгоритмов.
Часть 7: Дополнительные темы параллельного программирования, динамический параллелизм.

Еще одна статья о CUDA — зачем?

На Хабре было уже немало хороших статей по CUDA — раз, два и другие. Однако, поиск комбинации «CUDA scan» выдал всего 2 статьи никак не связанные с, собственно, алгоритмом scan на GPU — а это один из самых базовых алгоритмов. Поэтому, вдохновившись только что просмотренным курсом на Udacity — Intro to Parallel Programming, я и решился написать более полную серию статей о CUDA. Сразу скажу, что серия будет основываться именно на этом курсе, и если у вас есть время — намного полезнее будет пройти его.

Незамеченной на хабре прошла новость о появлении OpenCL 2.0 драйверов от AMD и Intel.

Многим кажется, что подобный API просто очередной маркетинговый buzzword. Отчасти это так, потому что почти все современные аппаратные продукты выходят с пунктом «OpenCL» в списке поддерживаемых технологий и рекламе: последние CPU, GPU, APU (CPU+GPU), FPGA, CPU+FPGA. И многим из области разработки enterprise ПО хочется откреститься от этих «модных» названий, но и это скоро станет невозможно стараниями Oracle и AMD.

Массовый параллелизм аппаратного обеспечения уже давно присутствует в серверах, пресональных компьютерах, телефонах и планшетах, специализированных аппаратных ускорителях. OpenCL в области FPGA рассматривается как способ упростить, удешевить и популяризовать разработку. При этом использование преимуществ, предоставляемых аппаратурой, пока требует от программиста использовать таких API как OpenCL, CUDA, OpenMP. Но появляются попытки скрыть эту сложность от прикладных программистов, например Project Sumatra и ScalaCL.

Привет, хабр! Закончилось лето, деревья роняют свои листья на холодную землю, в Новосибирске идет первый снег, а я в это время хочу рассказать небольшую историю о настройке платформы для перебора паролей WPA/WPA2 на базе устаревшей на сегодняшний день видеокарты RADEON HD4890.

Привет, Хабр. Подумал, кому-нибудь пригодится параллельная сортировка с относительно простой реализацией и высокой производительностью на платформе CUDA. Таковой является сортировка методом пузырька. Под катом приведено объяснение и код, который может пригодиться (а может и нет… ). Сразу скажу, что представленная прога является бенчмарком по сравнению производительности на GPU и CPU. Если тебе не жалко, читатель, то скомпилируй ее, пожалуйста, и положи результаты расчета в комменты этой статьи. Это не для науки. Просто интересно =)

Одним замечательным летним вечером, я в пылу спора имел глупость заметить, что можно написать быстро работающее решето Эратосфена на CUDA. N = 1000000000 (девять нулей) как цель. And the legend has begun…

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

#include <iostream>
#include <math.h>

using namespace std;

int main()
{
	double number = 1000000000;
	bool* a = new bool[int(number/2)];
	int i,j,result;

	for (i=0; i<number/2; i++)
		a[i] = true;

	for (i=3; i<=floor(sqrt(number)); i+=2)
		if (a[i/2])
			for (j=i*i; j<=number; j+=i*2)
				a[j/2]=false;

	result = 0;
	for (i=0; i<number/2; i++)
		if (a[i]) result++;

	cout << result << endl;

	delete[] a;

	return 0;
}

Однопоточный немного оптимизированный код, который работает на 14-15 секунд на Core i3 330M и затрачивает большое количество памяти. С него и начнем.

Введение

Здравствуйте, дорогие читатели.

В данном посте я постараюсь рассмотреть особенности выделения памяти для объектов OpenCL.

OpenCL является кросс-платформенным стандартом гетерогенных вычислений. Не секрет, что на нём пишут программы тогда, когда от них требуется скорость выполнения. Как правило, подобный код нуждается во всесторонней оптимизации. Всякий GPGPU-разработчик знает, что операции с памятью зачастую являются самым слабым звеном в скорости работы программы. Так как в природе существует великое множество аппаратных платформ, поддерживающих OpenCL, то вопрос организации объектов памяти зачастую становится головной болью. То, что хорошо работает на Nvidia Tesla, оснащённых локальной памятью и соединённых широкой шиной с глобальной, отказывается показывать приемлемую производительность на SoC, имеющих совершенно иную архитектуру.

Об особенностях выделения памяти для систем с общей памятью CPU и GPU и пойдёт речь в данном посте. Использование типов памяти Image оставим в стороне и сосредоточимся на наиболее общеупотребительном типе Buffer. В качестве стандарта будем рассматривать версию 1.1, как наиболее распространённую. В начале проведём краткий теоретический курс, а затем рассмотрим несколько примеров.

Аннотация

В данной статье хочу рассказать как можно эффективно распараллелить алгоритм 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. Причём связаны все эти компоненты одним из универсальных языков программирования.

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