Телефон: 8-800-350-22-65
WhatsApp: 8-800-350-22-65
Telegram: sibac
Прием заявок круглосуточно
График работы офиса: с 9.00 до 18.00 Нск (5.00 - 14.00 Мск)

Статья опубликована в рамках: LVII Международной научно-практической конференции «Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ» (Россия, г. Новосибирск, 28 сентября 2017 г.)

Наука: Информационные технологии

Скачать книгу(-и): Сборник статей конференции

Библиографическое описание:
Сахибназарова В.Б. РЕАЛИЗАЦИЯ АЛГОРИТМА СОРТИРОВКИ СЛИЯНИЕМ ПРИ ПОМОЩИ АКТОРНОЙ МОДЕЛИ ВЫЧИСЛЕНИЙ // Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ: сб. ст. по мат. LVII междунар. студ. науч.-практ. конф. № 9(56). URL: https://sibac.info/archive/technic/9(56).pdf (дата обращения: 29.03.2024)
Проголосовать за статью
Конференция завершена
Эта статья набрала 0 голосов
Дипломы участников
У данной статьи нет
дипломов

РЕАЛИЗАЦИЯ АЛГОРИТМА СОРТИРОВКИ СЛИЯНИЕМ ПРИ ПОМОЩИ АКТОРНОЙ МОДЕЛИ ВЫЧИСЛЕНИЙ

Сахибназарова Виктория Бахтиёровна

студент 2 курса магистратуры, факультет информатики СНИУ им. академика С.П. Королева,

РФ, г. Самара

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

Модель акторов представляет собой математическую модель параллельных вычислений, которая трактует понятие «актор» как универсальный примитив параллельного численного расчёта: в ответ на получаемые сообщения актор может принимать локальные решения, создавать новые акторы, посылать свои сообщения, а также устанавливать, как следует реагировать на последующие сообщения. Модель акторов возникла в 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, использование акторной модели при решении данной задачи приводит к увеличению времени вычислений в реальных условиях, несмотря на хорошие показатели алгоритма в теории. Это происходит из-за того, что на большой глубине рекурсии (при сортировке массивов небольшого размера), гораздо быстрее сделать сортировку любым непараллельным способом, чем производить затраты на передачу данных между акторами, создание сообщений. Также из-за физических ограничений при сортировке двух половин массива могут возникать неявные зависимости, что не позволяет рассчитывать на абсолютно одновременную сортировку двух половин.

 

Список литературы:

  1. Модель акторов [Электронный ресурс]: https://ru.wikipedia.org/wiki/Модель_акторов/
  2. Востокин С.В. Templet: язык разметки для параллельного программирования. СГАУ им. академика С.П. Королёва, Самара, 2014.
Проголосовать за статью
Конференция завершена
Эта статья набрала 0 голосов
Дипломы участников
У данной статьи нет
дипломов

Оставить комментарий

Форма обратной связи о взаимодействии с сайтом
CAPTCHA
Этот вопрос задается для того, чтобы выяснить, являетесь ли Вы человеком или представляете из себя автоматическую спам-рассылку.