Библиотека параллельных алгоритмов ParaLib
Библиотека параллельных алгоритмов ParaLib содержит краткие описания последовательных и параллельных алгоритмов решения ряда типовых задач вычислительной математики, а также примеры их реализаций с использованием различных технологий параллельного программирования. Для демонстрации работоспособности алгоритмов разработано визуальное приложение, используя которое можно выполнить эксперименты для оценки производительности имеющихся реализаций.
В текущей версии библиотеки рассмотрены следующие задачи:
- умножение матриц;
- умножение матрицы на вектор;
- сортировка массива данных;
- решение системы линейных уравнений;
- поиск всех кратчайших путей в графе;
- решение задачи Дирихле для дифференциального уравнения в частных производных.
Для всех задач представлены реализации последовательных алгоритмов и по крайней мере одна реализация параллельного алгоритма. При подготовке параллельных реализаций использовались различные языки и технологии параллельного программирования:
- технология параллельного программирования для систем с общей памятью OpenMP;
- технология параллельного программирования для систем с распределенной памятью MPI;
- язык параллельного программирования Chapel (Cascade High Productivity Language);
- язык параллельного программирования CoArray Fortran.
Наличие конкретных реализаций в текущей версии ParaLib описывается в Таблице 1, но библиотека позволяет легко добавлять дополнительные задачи и пользовательские реализации.
Таблица 1. Реализации методов и алгоритмов, содержащиеся в ParaLib.
| Задача | Метод | Технология | |||
| Chapel | OpenMP | CoArray Fortran | MPI | ||
| Умножение матриц | последовательный | + | + | + | — |
| параллельный | + | + | + | + | |
| Умножение матрицы на вектор | базовый параллельный алгоритм | — | + | — | + |
| последовательный | — | + | — | — | |
| Сортировка массива данных | последовательный | — | + | — | — |
| базовый параллельный алгоритм | — | + | — | + | |
| Решение системы линейных уравнений | базовый параллельный алгоритм | — | + | — | + |
| последовательный | — | + | — | — | |
| Поиск всех кратчайших путей в графе | последовательный алгоритм Флойда | — | + | — | — |
| базовый параллельный алгоритм Флойда | — | + | — | + | |
| Решение задачи Дирихле для СДУ | базовый параллельный алгоритм Гаусса-Зейделя | — | + | — | + |
| последовательный алгоритм Гаусса-Зейделя | — | + | — | — | |
Визуальное приложение, входящее в состав библиотеки позволяет выполнять эксперименты для сравнительной оценки производительности имеющихся реализаций. С его помощью можно:
- выбрать вычислительную задачу, для которой имеются реализованные алгоритмы решения,
- выбрать последовательный/параллельный метод для решения выбранной задачи;
- выбрать язык/технологию параллельного программирования для решения выбранной задачи;
- задать параметры задачи;
- определить число используемых процессоров;
- выполнить эксперимент, в ходе которого будет выполнен запуск решения выбранной задачи;
- накапливать и анализировать результаты выполненных экспериментов.
Общий вид приложения:
Выполнение экспериментов может осуществляться на локальном компьютере или на вычислительной системе с распределенной памятью.
Все реализации выполнены для операционной системы Windows 7/Windows 8.
Библиотека ParaLib носит учебно-исследовательский характер и может быть использована в ходе обучения специалистов различным аспектам параллельного программирования. Имеющиеся реализации могут использоваться в качестве образцов при разработке параллельных программ с использованием различных языков и технологий параллельного программирования.