Применение алгоритмических скелетов для проектирования параллельных алгоритмов акторного типа
Authors: Востокин С.В. , Бобылева И.В. 
Published: December 2024

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

The paper proposes a method for writing parallel algorithms. Our goal was to make a detailed description of concurrency while carrying no dependencies in programming language or underlying parallel architecture. We also wanted the description to be algorithmic, so simple for the programmer. The goal was achieved by adapting Cole's algorithmic skeletons to represent the structure and Hewitt’s actor model to represent the semantics of parallel algorithms. We used a sorting algorithm to show the idea of the method. To get parallel sorting, one should parallelize the code that controls the order of comparison-swap operations. It is obvious, that the parallelization will be the same for algorithms with different comparison-swap operations. The design method consists in writing algorithms in a form with known parallelization. Consequently, the form of an algorithm presents concurrency. For a more general form than in the sorting example, we used an algorithmic interpretation of the actor model. Based on the algorithmic interpretation of the actor model, we described a parallel computational process of the sorting algorithm. The algorithmic interpretation of the actor model distinguishes our method from functional and object-oriented approaches. It also makes code portable, and does not require synchronization and communication primitives. Only one skeleton is used instead of the skeleton system in Cole's method. The features of the method ensure its applicability in the design of many-task and workflow applications. The method confirms its efficiency for a wide class of parallel architectures ranges from single multiprocessor to hybrid cloud systems.