Применение алгоритмических скелетов для проектирования параллельных алгоритмов акторного типа

  • Sergey Vladimirovich Vostokin Самарский национальный исследовательский университет им. академика С.П. Королева http://orcid.org/0000-0001-8106-6893
  • Irina Vladimirovna Bobyleva Самарский национальный исследовательский университет им. академика С.П. Королева; Акционерное общество "Ракетно-космический центр "Прогресс" http://orcid.org/0000-0001-5660-3503

Аннотация

В работе предлагается метод проектирования параллельных алгоритмов. Цель метода – обеспечение точности описания алгоритмов без зависимости от языка программирования и архитектуры параллельной вычислительной системы, используя понятную программисту алгоритмическую форму описания. Цель достигнута путем адаптации алгоритмических скелетов Коула для представления структуры и модели акторов Хьюитта для представления семантики параллельных алгоритмов.
Идея метода изложена на примере проектирования параллельного алгоритма сортировки. В исходном алгоритме выделяется код, определяющий порядок вызова блоков сравнения и перестановки элементов сортируемой последовательности. Метод распараллеливания для этого кода применим при распараллеливании семейства последовательных алгоритмов с различными блоками сравнения и перестановки. Проектирование заключается в записи алгоритма в такой последовательной форме, для которой известен метод распараллеливания. Данная последовательная форма алгоритма может быть достаточно общей, независимо выполняется сортировка или другие вычисления. Для этого форма последовательного алгоритма приводится в соответствие с некоторой абстрактной моделью параллельных вычислений. В качестве такой модели нами предложена алгоритмическая интерпретация модели акторов. Представлен подробный пример применения метода. На основе алгоритмической интерпретации модели акторов описан параллельный вычислительный процесс алгоритма сортировки.
Алгоритмическая интерпретация модели акторов отличает метод от функциональных и объектно-ориентированных интерпретаций. Метод базируется на фундаментальном понятии последовательного алгоритма, что обеспечивает свободу выбора программной реализации, не требует примитивов синхронизации и коммуникации. Для проектирования используется один базовый скелет для всех алгоритмов вместо системы скелетов в методе Коула.
Особенности метода обеспечивают его применимость при проектировании алгоритмов многозадачных вычислений и алгоритмов управления потоками работ. Наш опыт применения метода подтверждает эффективность разработанных на его основе программ для широкого класса параллельных архитектур от одиночных мультипроцессорных до гибридных облачных систем.

Сведения об авторах

Sergey Vladimirovich Vostokin, Самарский национальный исследовательский университет им. академика С.П. Королева

профессор кафедры информационных систем и технологий, Институт информатики, математики и электроники, доктор технических наук, доцент

Irina Vladimirovna Bobyleva, Самарский национальный исследовательский университет им. академика С.П. Королева; Акционерное общество "Ракетно-космический центр "Прогресс"

аспирант кафедры информационных систем и технологий, Институт информатики, математики и электроники; инженер-программист

Опубликована
2020-05-25
Как цитировать
VOSTOKIN, Sergey Vladimirovich; BOBYLEVA, Irina Vladimirovna. Применение алгоритмических скелетов для проектирования параллельных алгоритмов акторного типа. Международный научный журнал «Современные информационные технологии и ИТ-образование», [S.l.], v. 16, n. 1, may 2020. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/617>. Дата доступа: 09 aug. 2020
Раздел
Параллельное и распределенное программирование, грид-технологии