Статья опубликована в рамках: LVII Международной научно-практической конференции «Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ» (Россия, г. Новосибирск, 28 сентября 2017 г.)
Наука: Информационные технологии
Скачать книгу(-и): Сборник статей конференции
дипломов
РЕАЛИЗАЦИЯ АЛГОРИТМА СОРТИРОВКИ СЛИЯНИЕМ ПРИ ПОМОЩИ АКТОРНОЙ МОДЕЛИ ВЫЧИСЛЕНИЙ
В данной работе алгоритм сортировки слиянием реализуется при помощи использования акторов, позволяющих объединять два отсортированных потока чисел в один отсортированный поток.
Модель акторов представляет собой математическую модель параллельных вычислений, которая трактует понятие «актор» как универсальный примитив параллельного численного расчёта: в ответ на получаемые сообщения актор может принимать локальные решения, создавать новые акторы, посылать свои сообщения, а также устанавливать, как следует реагировать на последующие сообщения. Модель акторов возникла в 1973 году, использовалась как основа для понимания исчисления процессов и как теоретическая база для ряда практических реализаций параллельных систем. Основная задача параллельных вычислений — облегчить пользователям доступ к удаленным ресурсам и обеспечить их совместное использование, регулируя этот процесс.
Актор является вычислительной сущностью, которая в ответ на полученное сообщение может одновременно: отправить конечное число сообщений другим акторам; создать конечное число новых акторов; выбрать поведение, которое будет использоваться при обработке следующего полученного сообщения. Не предполагается существования определенной последовательности вышеописанных действий и все они могут выполняться параллельно [1].
MPI (Message Passing Interface) – программный интерфейс для передачи информации, который позволяет обмениваться сообщениями между процессами, выполняющими одну задачу. MPI является наиболее распространённым стандартом интерфейса обмена данными в параллельном программировании, существуют его реализации для большого числа компьютерных платформ. Стандарт MPI ориентирован на системы с распределенной памятью, когда затраты на передачу данных велики [2].
Для сортировки массива используется актор worker, у которого может быть два дочерних worker'a, для сортировки левой и правой частей соответственно.
У worker'a есть метод sort, которому передается сообщение с размером массива и данными. Должна произойти сортировка, и у сообщения вызван метод send для обратной передачи результата.
Sort работает следующим образом: если на сортировку был передан массив размера 1, то он уже отсортирован, и нужно просто вызвать send у входного сообщения. Иначе происходит разделение массива на 2 части, и происходит отправка сообщения в sort дочерних worker'ов, результат их работы будет получен текущем worker'ом в методах left_sorted,right_sorted. В каждом из них происходит проверка access противоположного потомка, и если результат положительный, то происходит слияние двух массивов и отправка методом send тому, кто вызвал метод sort.
В Таблице 1 представлено время выполнения программы (в секундах) для различного количества элементов в сортируемом массиве, в зависимости от использования акторной модели (ta) и различных директив. На Рисунке 1 представлена графическая интерпретация Таблицы 1.
Таблица 1.
Зависимость времени выполнения от размера сортируемого массива
|
|
100 |
1000 |
10000 |
100000 |
|
t |
0 |
0,001 |
0,01 |
0,097 |
|
ta |
0,003 |
0,025 |
0,282 |
3,962 |
|
ta + SERIAL_EXECUTION |
0,013 |
0,13 |
1,304 |
12,295 |
|
ta + PARALLEL_EXECUTION |
0,016 |
0,057 |
0,426 |
3,787 |
|
ta + USE_OPENMP |
0,004 |
0,03 |
0,286 |
3,96 |
Рисунок 1 - Зависимость времени выполнения от размера сортируемого массива
В Таблицах 2 и 3 представлены данные статистики по эффективности параллельного алгоритма где Т1 – время выполнения последовательного алгоритма, Тр – время выполнения параллельной версии программы, Pmax – максимальное количество процессов, Smax – максимальное ускорение параллельного алгоритма, Sp – ускорение системы по закону Амдала.
Таблица 2.
Статистика эффективности параллельного алгоритма
|
100 |
1000 |
10000 |
|
|
T1 |
199 |
1999 |
19999 |
|
Tp |
8 |
11 |
15 |
|
Pmax |
72 |
976 |
8192 |
|
Smax |
24,875 |
181,727 |
1333,27 |
|
Sp |
3,70395 |
3,94692 |
3,99248 |
Рисунок 2. Статистика эффективности параллельного алгоритма
Таблица 3.
Статистика эффективности параллельного алгоритма для длины массива кратной двум
|
|
8 |
64 |
128 |
256 |
512 |
1024 |
2048 |
4096 |
8192 |
|
T1 |
15 |
127 |
255 |
511 |
1023 |
2047 |
4095 |
8191 |
16183 |
|
Tp |
4 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
|
Pmax |
8 |
64 |
128 |
256 |
512 |
1024 |
2048 |
4096 |
7992 |
|
Smax |
3,5 |
18,143 |
31,875 |
56,778 |
102,3 |
186,091 |
341,25 |
630,077 |
1155,93 |
|
Sp |
2,692 |
3,571 |
3,734 |
3,841 |
3,908 |
3,948 |
3,971 |
3,984 |
3,991 |
Рисунок 3. Статистика эффективности параллельного алгоритма (для длинны массива, кратной двум)
Как видно из результатов таблицы 1, использование акторной модели при решении данной задачи приводит к увеличению времени вычислений в реальных условиях, несмотря на хорошие показатели алгоритма в теории. Это происходит из-за того, что на большой глубине рекурсии (при сортировке массивов небольшого размера), гораздо быстрее сделать сортировку любым непараллельным способом, чем производить затраты на передачу данных между акторами, создание сообщений. Также из-за физических ограничений при сортировке двух половин массива могут возникать неявные зависимости, что не позволяет рассчитывать на абсолютно одновременную сортировку двух половин.
Список литературы:
- Модель акторов [Электронный ресурс]: https://ru.wikipedia.org/wiki/Модель_акторов/
- Востокин С.В. Templet: язык разметки для параллельного программирования. СГАУ им. академика С.П. Королёва, Самара, 2014.
дипломов
Оставить комментарий