Оптимізація паралельних алгоритмів з використанням моделі акторів

Abstract

Запропоновані методи та інструментальні засоби для оптимізації блочно-рекурсивних алгоритмів із використанням моделі акторів. Формалізовано модель розподілення і координації задач в обчислювальному кластера у вигляді асинхронних реактивних процесів із обміном повідомленнями представлених моделлю акторів та хореографією акторів. Створено систему декларативного задання алгоритмів які трансформуються у систему акторів. На основі пріоритетизації операцій блочно-рекурсивних алгоритмів запропоновано схему розташування даних у кластері для зменшення часу очікування та зменшення кількості обмінів із підвищенням паралелізму при високій швидкодії процесора і зниженій пропускній здатності мережі. Створено підтримку адаптивної зміни схеми розміщення даних між вузлами кластеру під час виконання для підвищення ефективності в рамках поточного навантаження кластеру. Створено систему автотюнінгу схем розташування акторів у кластері, що враховує статистику попередніх запусків для оптимізації. Використання хореографії без центрального координуючого елементу дозволяє позбутися жорсткої залежності між вузлами кластера, дає гнучкість розташування даних, покращує надійність за відсутності єдиної точки відмови, та дає можливість самовідновлення.

Предложены методы и инструментальные средства для оптимизации блочно-рекурсивных алгоритмов с использованием модели актеров Форматизирована модель распределения и координации задач в вычислительном кластере в виде асинхронных реактивных процессов с обменом сообщениями представленных моделью актеров и хореографией актеров. Создано систему декларативного задания алгоритмов, которые трансформируются в систему актеров. На основе приоритезации операций блочно-рекурсивных алгоритмов предложено схему расположения данных в кластере для уменьшения времени ожидания и уменьшения количества обменов с повышением параллелизма в ситуации высокой скорости процессора и сниженной пропускной способности сети. Создано систему поддержки адаптивной схемы размещения данных между узлами кластера во время исполнения для повышения эффективности в рамках текущей загрузки кластера. Создано систему автотьюнинга схем расположения актеров в кластере, которая использует статистику предыдущих запусков для оптимизации. Использование хореографии без центрального координирующего элемента позволяет избавится от жесткой зависимости между узлами кластера, дает гибкость расположения данных, улучшает надежность при отсутствии единой точки отказа, дает возможность самовосстановления.

Introduced methods and instrumentation tools for actor model applied to block recursive algorithms optimization. Created formal model of distribution and coordination of the tasks in computation cluster as asynchronous reactive processes with message-passing represented with an actor model and choreography of actors. Created declarative definitions of algorithms which compiles to the system of actors. Proposed scheme of data placement in a cluster using prioritization of block-recursive operations to reduce idling time, data movement, with increased parallelism in situation of high-speed processors and reduced network bandwidth. Implemented adaptive adjustment of the data placement in a cluster at run time to account for current cluster load. Created autotuning of the actor placement in а cluster which uses statistics of previous runs for optimization. Usage of choreography of actors allows to remove central coordinating element and to avoid hard dependencies between cluster nodes, which provides flexible data placement, improves fault tolerance with no single point of failure and allows to use self-healing