Настройка 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++ со сложением и вычитанием»

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

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

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

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

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

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

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

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

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

Реализация поиска в ширину на графе;
Реализация поиска в глубину на графе;
Реализация топологической сортировки и поиска компонент сильной связности;

Реализация обычного алгоритма Флойда-Уоршелла нужна мне для того, чтобы запрограммировать параллельное вычисление этой задачи с помощью библиотеки MPI. Отчет о результатах распараллеливания я напишу уже совсем скоро(я очень на это надеюсь). А сейчас поговорим о стандартном алгоритме Флойда-Уоршелла.

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

Как я упомянул, алгоритм предназначен для нахождения кратчайших путей между всеми вершинами в графе. По сути он представляет собой простой перебор всех путей и выбор из них наименьшего. Перебор осуществляется по так называемой «матрице смежности» размера NxN, где N — количество вершин графа.

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

Реализация преобразования string to int на C/C++

Доброго времени суток! Такие функции, как stoi, atoi, atol, soul, stof, to_string и некоторые другие появились в стандарте C++11 и уже стали привычными. Особенно для пользователей Visual Studio версии 13 года и старше. Но бывают исключительные случаи, когда под рукой нет такого крутого инструмента, а только блокнот и старенький gcc. Либо инструмент есть, но он упорно отказывается работать с C++11.

Именно с такой проблемой я недавно столкнулся. Мне позарез нужно было конвертировать строку в целое число, а мой Eclipse даже через 2 часа шаманствования с бубном так и не стал дружить с функцией stoi. Было принято волевое решение написать свою реализацию преобразования string to int. Я остановился на реализации преобразования целых десятичных положительных и отрицательных чисел, этого вполне хватило.

Функция преобразования string  to int на C/C++

читать далее «Реализация преобразования string to int на C/C++»