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

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

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

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

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

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

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

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

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

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

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

Что такое OpenMP

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

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

Реализация больших чисел на C/C++ со сложением и вычитанием

Доброго времени суток и светлого неба над головой, дорогие друзья! Ни для кого из вас не секрет, что ограничение максимального и минимального значения целого числа, хоть и разнится на разных архитектурах, но существует. Например, для целого числа типа int диапазон его значений равен от –2147483647 – 1 до 2147483647. Казалось бы, 2 миллиарда в каждую сторону это целая гора, но как только вы займетесь настоящей криптографией, либо машинным обучением, теорией вероятностей или еще более крутой математикой, вы поймете, что это чертовски мало. Именно в таком случае на помощь приходят, так называемые, большие числа.

Идея большого числа в том, чтобы вылезти за рамки ограничений стандартных типов данных, оперировать бесконечно большими числами, размер которых будет ограничен только вычислительной мощностью «машины». Как этого достичь? Самый логичный способ заключается в том, чтобы записывать число в строку и конвертировать специальным образом в согласованный массив чисел стандартного типа.

Например, как можно хранить число 123456789123456789, в int оно не поместится. тогда мы поместим его в массив int`ов, mas[0] = 123456, mas[1] = 789123, mas[2] = 456789, напишем специальные алгоритмы, которые будут корректно складывать, вычитать, умножать и делить такие числа.

Как раз о таких алгоритмах инициализации, сложения и вычитания больших чисел я сейчас расскажу, поехали!

читать далее «Реализация больших чисел на C/C++ со сложением и вычитанием»

Как сделать кнопку «наверх» для сайта

Приветствую вас, друзья мои. Сейчас я освящу наверное один из самых популярных вопросов в области «быстрых рецептов» на html/css/js. А именно — создание кнопки «наверх», которая так часто встречается на самых различных ресурсах. И как обычно, пишу я это не просто так, а исходя из своего личного опыта, ибо вы можете заметить у меня такую кнопку в нижней правой части экрана.

Создание кнопки, как и любого активного элемента на веб-странице, делится на три основные части. Необходимо написать html код самой кнопки, навести марафет с помощью css стилей и оживить кнопку с помощью js кода. О каждом этапе в подробностях, поехали!

HTML код кнопки «наверх»

Начать логичнее всего непосредственно с самой кнопки. Существует огромное количество вариантов, но я расскажу о самом визуально красивом способе нарисовать стрелочку на веб-странице — с помощью набора иконок Font Awesome.

читать далее «Как сделать кнопку «наверх» для сайта»

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

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

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

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

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

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

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