Применение алгоритмических скелетов для проектирования параллельных алгоритмов акторного типа - Vostokin, Sergey Vladimirovich; Bobyleva, Irina Vladimirovna (Современные информационные технологии и ИТ-образование, 2020)
В работе предлагается метод проектирования параллельных алгоритмов. Цель метода – обеспечение точности описания алгоритмов без зависимости от языка программирования и архитектуры параллельной вычислительной системы, используя понятную программисту алгоритмическую форму описания. Цель достигнута путем адаптации алгоритмических скелетов Коула для представления структуры и модели акторов Хьюитта для представления семантики параллельных алгоритмов. Идея метода изложена на примере проектирования параллельного алгоритма сортировки. В исходном алгоритме выделяется код, определяющий порядок вызова блоков сравнения и перестановки элементов сортируемой последовательности. Метод распараллеливания для этого кода применим при распараллеливании семейства последовательных алгоритмов с различными блоками сравнения и перестановки. Проектирование заключается в записи алгоритма в такой последовательной форме, для которой известен метод распараллеливания. Данная последовательная форма алгоритма может быть достаточно общей, независимо выполняется сортировка или другие вычисления. Для этого форма последовательного алгоритма приводится в соответствие с некоторой абстрактной моделью параллельных вычислений. В качестве такой модели нами предложена алгоритмическая интерпретация модели акторов. Представлен подробный пример применения метода. На основе алгоритмической интерпретации модели акторов описан параллельный вычислительный процесс алгоритма сортировки. Алгоритмическая интерпретация модели акторов отличает метод от функциональных и объектно-ориентированных интерпретаций. Метод базируется на фундаментальном понятии последовательного алгоритма, что обеспечивает свободу выбора программной реализации, не требует примитивов синхронизации и коммуникации. Для проектирования используется один базовый скелет для всех алгоритмов вместо системы скелетов в методе Коула. Особенности метода обеспечивают его применимость при проектировании алгоритмов многозадачных вычислений и алгоритмов управления потоками работ. Наш опыт применения метода подтверждает эффективность разработанных на его основе программ для широкого класса параллельных архитектур от одиночных мультипроцессорных до гибридных облачных систем.