Компьютерные технологии в науке и образовании

Лабораторная работа N3
Изучение технологий параллельного программирования

Срок сдачи: 09.06.2024 00:00:00 MSK (321 дн. назад)

Литература:

Материал лекции "Технологии параллельного программирования".

Видеозапись лекции 12.05.2020 (157 Мб)

"Высокопроизводительные вычисления на кластерах" (уч. пособ. Томского ГУ).

The GNU C Library: Гл. 26: процессы

POSIX Threads Programming

OpenMP Tutorial

OpenMPI v1.4.5 Documentation

TORQUE v.2.5 Guide

The GNU MP Bignum Library

OpenSSL cryptographic library

Введение

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

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

Изучаемые технологии:

Симметричные мультипроцессорные системы (SMP). Стандартные средства многозадачной ОС (fork или POSIX threads).
Симметричные мультипроцессорные системы (SMP). Интерфейс OpenMP.
Кластерные системы. Библиотека OpenMPI.

Варианты задач:

A. Обратить хэш MD5 (подобрать сообщение, порождающее заданный хэш).
B. Проверить, является ли заданное число простым.

Применение любой технологии параллельного программирования подразумевает процесс разработки параллельного алгоритма, т. е. как минимум:

декомпозицию задачи (оценку возможности распараллеливания);
проектирование коммуникаций между параллельными блоками;
планирование вычислений (распределение подзадач между процессорами).

Рассмотрим процесс разработки для следующей учебной задачи:

Обратить хэш MD5 (подобрать сообщение, порождающее заданный хэш).

Наиболее очевидное и надёжное (хотя и самое медленное) решение этой задачи — полный перебор. Для решения задач, требующих полного перебора возможны два варианта распараллеливания:

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

Для данной задачи второй подход более привлекателен, так как менее требователен к проектированию коммуникаций. Блок, первым нашедший решение задачи на своём подмножестве текстов, должен уведомить об этом остальные блоки.

Для разбиения всего множества текстов на подмножества для параллельных подзадач воспользуемся следующим принципом. Считая, что число процессоров (параллельных блоков) N меньше количества символов в наборе, из которого состоит текст, M, будем текст, начинающийся с k-го символа из набора, обрабатывать i-м блоком, где

k mod N = i.

Любой текст можно интерпретировать как N-значное число в системе счисления по основанию M, где N - длина текста, M - количество символов в наборе, из которого состоит текст, поэтому полный набор текстов длиной N символов содержит M^N вариантов. При тестировании алгоритма следует учитывать, что на имеющейся вычислительной технике для N = 4 перебор выполняется в среднем за несколько секунд, для N = 5 — за несколько минут, для N = 6 — за несколько часов, для N = 7 — за несколько дней и т. д. В ходе отладки целесообразно использовать N = 4, а при оценке эффективности — N = 5.

Декомпозиция задачи B решается аналогичным способом:

Проверить, является ли заданное число простым.

Легче всего распараллеливается алгоритм простого перебора делителей. Разным процессам, решающим задачу по данному алгоритму, назначаются разные множества делителей. Первый же процесс, нашедший какой-либо делитель заданного числа, может завершить выполнение всей задачи. То, что число является простым, фиксируется только в том случае, если ни один процесс не найдёт делителей.

SMP. Стандартные средства многозадачной ОС

Современные многозадачные ОС позволяют любой задаче порождать процессы или нити. Если задача работает на симметричной мультипроцессорной системе, эта возможность позволяет реализовать параллелизацию алгоритмов задачи.

В POSIX-совместимых ОС для манипулирования нитями используется библиотека POSIX Threads (pthread). Ознакомится с её возможностями можно по справочному руководству info libc в соответствующем разделе. Наиболее полезные функции, предоставляемые данной библиотекой: pthread_create, pthread_join и др. При компиляции программы, использующей эту библиотеку, следует указывать ключ -lpthread.

Для порождения процессов используется функция fork. После выполнения этой функции задача продолжается сразу в двух процессах: родительском и дочернем. Родительскому процессу эта функция возвращает PID дочернего процесса, а дочернему — ноль. При нехватке системных ресурсов функция завершится с ошибкой, вернув отрицательный результат. Порождённый дочерний процесс является точной копией родительского процесса (с несущественными исключениями). Для синхронизации процессов можно воспользоваться функциями wait, kill и т. п. Перечисленные функции являются базовыми и не требуют подключения дополнительных библиотек при обработке программы редактором связей.

Задание 1а

Модифицировать предоставленный алгоритм, используя параллельное выполнение блоков кода программы. Сравнить время работы однопроцессного варианта программы с модифицированным. Определить, как меняется время выполнения программы при варьировании числа параллельно работающих блоков.

Задание выполняется на SMP-системе. Рекомендуется распараллеливание при помощи процессов, но по желанию допускается также реализация на нитях.

Для оценки времени выполнения программы удобно использовать утилиту time. Например, команда time ls, кроме результата работы команды ls, выдаст также время её выполнения.

SMP. Интерфейс OpenMP

Интерфейс OpenMP при помощи директив компилятора и набора библиотечных функций предоставляет программисту средства распараллеливания программ. Ознакомиться с возможностями данного интерфейса можно по адресу: https://computing.llnl.gov/tutorials/openMP/ Для компилятора gcc при использовании интерфейса OpenMP следует использовать ключ -fopenmp.

Задание 1б

(Задание выполняется как обязательное студентами направления "ИВТ", остальным – по желанию).

Модифицировать предоставленный алгоритм, используя параллельное выполнение блоков кода программы при помощи директив OpenMP. Сравнить время работы однопроцессного варианта программы с модифицированным. Определить, как меняется время выполнения программы при варьировании числа параллельно работающих блоков.
Задание выполняется на SMP-системе.

Кластерные системы. Библиотека OpenMPI

Библиотека OpenMPI позволяет на основе обычных хостов примерно однородной конфигурации организовать распределённую вычислительную систему типа кластер. Копии программы, запущенные на разных хостах, синхронизуют свою работу и обмениваются сообщениями при помощи протокола MPI. Утилиты библиотеки OpenMPI обеспечивают прозрачный одновременный запуск приложения на нескольких хостах. Информация об используемой версии библиотеки доступна на сайте: http://www.open-mpi.org/doc/v1.2/. Для компиляции программы, использующей OpenMPI, используется утилита mpicc. Для запуска программы — утилита mpirun.

Задание 2

Модифицировать предоставленный алгоритм, используя параллельное выполнение блоков кода программы при помощи библиотеки OpenMPI. Сравнить время работы однопроцессного варианта программы с модифицированным. Определить, как меняется время выполнения программы при варьировании числа параллельно работающих блоков.

Задание выполняется на кластере "Лусидор".

Приложения

Образец реализации программы обращения хэша MD5 с использованием библиотеки OpenSSL.
Образец реализации программы определения простоты числа с использованием библиотеки GMP.

Реализации этих же алгоритмов на FreePascal (2.4+): crack_md5 и check_prime (для ознакомления).

Для сравнения производительности программ следует использовать:

Хэш текста, длина которого больше MAX_LEN (расчёт на 24 ядрах должен занимать не менее 20 с).
Число, не имеющее делителей, кроме 1 и себя (т. е. простое, не менее 10²⁰).

Варианты задания

ИВТ: Самостоятельно реализуют модифицированные параллельные алгоритмы для SMP, OpenMP, OpenMPI.

Приборостроение: Самостоятельно реализуют модифицированные параллельные алгоритмы для SMP и OpenMPI.

Энергетика/электроника: В работе используют готовые реализации параллельных алгоритмов для SMP и OpenMPI.

Форма сдачи

Программы и отчёт в формате PDF высылаются в архиве TAR+GZIP или ZIP на адрес электронной почты преподавателя.

В отчёте следует привести характеристики системы, на которой выполнялись программы (кластера "Лусидор").

По заданию 1 в отчете приводится:

Команды или сценарии для компиляции программ;
Текст сценариев запуска (для TORQUE) и команды заданий;

Протокол работы вида:

Дата	Кол-во процессов	Номер задания TORQUE	Хост (узел)	Время исполнения, с
23.04	1 1 1 2 2 2 4 4 4	56 ...	lucidor-cab4-n1 ...	581.92 ...

Итог расчетов: число простое / число непростое, делители: ...

По заданию 2 в отчете приводится:

Команды или сценарии для компиляции программ;
Текст сценариев запуска (для TORQUE) и команды заданий;