Вычисление глобального индекса нити в CUDA

Доброго времени суток! Я уже несколько раз затрагивал тему параллельных вычислений, но все время это были вычисления на старом добром центральном процессоре. А сейчас я вкратце расскажу о технологии CUDA от фирмы NVIDIA, которая расшифровывается как Compute Unified Device Architecture, и служит для того, чтобы выполнять параллельные вычисления на процессоре графического устройства, а именно — видеокарточки NVIDIA.

Grid, Block и Thread в CUDA

Для того, чтобы эффективно программировать с помощью технологии CUDA, в первую очередь нужно освоиться и научиться свободно оперировать основными понятиями вычислительной модели. Их три: грид(grid), блок(block) и нить(thread), последний еще называют потоком, это синонимы.

Grid является самым верхним уровнем абстракции в модели, он трехмерный и состоит из блоков. Например, в гриде размером 2x2x2 содержится 8 блоков. В свою очередь, каждый блок содержит в себе трехмерный массив нитей(threads), которые и являются непосредственными исполнителями вычислений. К примеру, если каждый из 8 блоков содержит 2x2x1 нитей, то всего на устройстве будет 32 рабочих потока, готовых приступить к любым вычислениям, причем работать они будут параллельно.

читать далее «Вычисление глобального индекса нити в CUDA»

Основные директивы OpenMP с примерами

Доброго времени суток, друзья! Как вы могли заметить, я иногда балуюсь с параллельным программированием посредством OpenMP. На данный момент готова заметка о том, как установить и настроить omp в Clion. А из реализаций есть параллельное умножение матриц. Я посчитал, что самое время собрать небольшую шпаргалку по наиболее часто используемым директивам и их параметрам, чтобы можно было сюда заглянуть и освежить их в памяти. Постараюсь на каждую директиву добавить по небольшому, чисто символическому синтаксическому примеру.

Не секрет, что OpenMP доступен на языках C/C++ и Fortran(даже слышал, что и на Java есть), но я буду писать примеры только для C/C++, уж не сердитесь, теория для них все равно одинаковая. Предлагаю ни секунды не терять и приступать к делу.

Общий синтаксис вызова директив OpenMP

Любые дополнительные директивы вызываются с помощью стандартной директивы #pragma, и OpenMP не исключение. Следовательно, для того, чтобы обратиться к директиве нужно написать #pragma omp, и назвать искомую директиву. Справедлива следующая конструкция вызова.

#pragma omp директива [опция1, опция2, ...]

Где «директива» — имя директивы, а опции являются необязательным для вызова, их у разных директив может быть разное количество, о них я тоже вкратце расскажу.

читать далее «Основные директивы OpenMP с примерами»

Параллельное умножение матриц с помощью OpenMP

Доброго времени суток всем. Недавно я опубликовал коротенькую инструкцию по настройке OpenMP в CLion, а сейчас пришло время для реализаций параллельных алгоритмов. Первым на очереди стоит простенький алгоритм перемножения матриц, он очень хорошо подходит для распараллеливания, потому что состоит из трех вложенных циклов.

Вряд ли кто-нибудь сможет лучше описать алгоритм умножения матриц, чем статья на википедии. Поэтому прикрепляю скриншот и сразу перехожу к реализации.

Алгоритм умножения матриц

Реализация алгоритма умножения матриц на C/C++

Пусть матрица хранится в двумерном массиве int **matrix, и доступ к элементам осуществляется двойным индексом matrix[i][j]. Для начала произведем простенькую проверку на то, что матрицы согласованы, после этого можно выделить память и выполнить умножение по формуле.

читать далее «Параллельное умножение матриц с помощью OpenMP»

Настройка OpenMP в CLion и пример программы

Доброго времени суток! Продолжаем рассматривать варианты параллельного исполнения программ. Я уже рассказывал про библиотеку MPI, которая позволяет создавать несколько параллельно исполняемых процессов в системе. Рассказал о базовой установке MPI, интеграции его в CLion и даже поделился своей реализацией алгоритма Флойда-Уоршелла.

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

А в этой статье я расскажу о потоках(Threads). Потоки создаются внутри процесса, они имеют доступ к стеку своего процесса, могут читать и писать в область памяти процесса. Благодаря этому увеличивается эффективность параллельных алгоритмов, уменьшаются затраты ресурсов на пересылку данных. Кроме того, упрощается программирование алгоритмов, проще следить за синхронизацией данных и прочее.

Что такое OpenMP

Признанным открытым стандартном параллельного программирования на языках C/C++ и Fortran является OpenMP. Он включает в себя множество директив препроцессора, библиотечных функций и переменных окружения для реализации многопоточных программ. Более подробную информацию вы сможете найти на вики и прочих источниках, а я перейду непосредственно к настройке.

читать далее «Настройка OpenMP в CLion и пример программы»

Реализация параллельного алгоритма Флойда-Уоршелла

Доброго времени суток! Буквально пару дней назад я опубликовал реализацию линейного алгоритма Флойда-Уоршелла поиска кротчайших путей между всеми вершинами взвешенного графа. В той статье я обещал разобраться и реализовать параллельный алгоритм Флойда-Уоршелла, прошло несколько дней и родилась эта статья.

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

В качестве инструмента будет использована уже знакомая библиотека MPICH(установка библиотеки).

Схема параллельного алгоритма Флойда-Уоршелла

В оригинальном линейном алгоритме единственная операция это нахождение минимума, как справедливо замечено в крохах источников, что я находил, ее нет смысла распараллеливать. Вся сложность алгоритма(О^3) заключается в полном переборе «матрицы смежности». Напомню, что я так называю матрицу размера NxN, в которой на пересечении i-й строки и j-го столбца стоит вес ребра из i-ой вершины в j-ую.

читать далее «Реализация параллельного алгоритма Флойда-Уоршелла»