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

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

Срок сдачи: 11.06.2017 00:00:00 MSK (104 дн. назад)
Литература:

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

k mod N = i.

Любой текст можно интерпретировать как N-значное число в системе счисления по основанию M, где N - длина текста, M - количество символов в наборе, из которого состоит текст, поэтому полный набор текстов длиной N символов содержит MN вариантов. При тестировании алгоритма следует учитывать, что на имеющейся вычислительной технике для 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. Сравнить время работы однопроцессного варианта программы с модифицированным. Определить, как меняется время выполнения программы при варьировании числа параллельно работающих блоков.

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


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

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

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


Форма сдачи

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

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

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

  1. Команды или сценарии для компиляции программ;
  2. Текст сценариев запуска (для TORQUE) и команды заданий;
  3. Протокол работы вида:
    ДатаКол-во процессовНомер задания TORQUEХост (узел)Время исполнения, с
    23.041
    1
    1
    2
    2
    2
    4
    4
    4
    56
    ...
    lucidor-cab4-n1
    ...
    581.92
    ...
  4. Итог расчетов: число простое / число непростое, делители: ...

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

  1. Команды или сценарии для компиляции программ;
  2. Текст сценариев запуска (для TORQUE) и команды заданий;
  3. Протокол работы вида:
    ДатаКол-во процессовНомер задания TORQUEХост (узел)Время исполнения, с
    23.041
    1
    1
    2
    2
    2
    4
    4
    4
    8
    8
    8
    12
    12
    12
    16
    16
    16
    20
    20
    20
    24
    24
    24
    65
    ...
    lucidor-cab4-n1
    ...
    582.71
    ...
  4. По полученным данным следует оценить параметр f (доля последовательных вычислений) из закона Амдала для вашей программы (провести стат. обработку, оценить погрешность). Построить график зависимости S (ускорение) или T (время выполнения) от количества процессов p для экспериментальных данных и полученной модели.


Альтернативное задание

Найдите разложение чисел (программа B) на два целочиселенных делителя, по вариантам:


"Стоимость" наиболее популярных недочётов: