Структурно-параметрическое согласование метаэвристических алгоритмов глобальной оптимизации с архитектурой графических процессорных устройств тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Селиверстов Евгений Юрьевич

• Селиверстов Евгений Юрьевич
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Селиверстов Евгений Юрьевич

устройств

1.6. Выводы по Главе

Глава 2. Разработка математических моделей графических процессорных устройств и метаэвристического алгоритма

глобальной оптимизации

2.1. Модель графического процессорного устройства

2.1.1. Архитектура графического процессорного устройства

2.1.2. Архитектура вычислительной системы на основе графических процессорных устройств

2.1.3. Графовая структурная модель

2.1.4. Графовая коммуникационная модель

2.1.5. Модель памяти

2.1.6. Свойства моделей

2.2. Математическая модель метаэвристического параллельного алгоритма

2.2.1. Типы моделей параллельных алгоритмов

2.2.2. Модели метаэвристических алгоритмов

2.2.3. Иерархическая модель параллельного алгоритма

2.2.4. Математическая модель последовательного метаэври-стического алгоритма

2.2.5. К-итерационные графы

2.2.6. Математическая модель параллельного алгоритма

2.2.7. Параметризация модели алгоритма

2.3. Примеры параллельных моделей некоторых алгоритмов

2.4. Выводы по Главе

Глава 3. Разработка методов и алгоритмов решения задачи структурно-параметрического согласования метаэвристических алгоритмов глобальной оптимизации с архитектурой

графических процессорных устройств

3.1. Задача согласования

3.1.1. Отображения графа на граф и их ограничения

3.1.2. Отображение параллельного алгоритма на вычислительную систему

3.1.3. Примеры отображений

3.1.4. Критерий оптимальности задачи согласования

3.1.5. Формальная постановка задачи согласования

3.2. Иерархический метод согласования

3.2.1. Схема иерархического метода решения задачи согласования

3.2.2. Метод параметрического согласования последовательного алгоритма

3.2.3. Метод структурного согласования параллельного алгоритма

3.2.4. Метод поиска оптимального отображения

3.3. Алгоритмы решения задачи согласования

3.3.1. Схема алгоритма решения задачи согласования

3.3.2. Алгоритм построения отображения

3.3.3. Построение ограничивающей функции отображения

3.3.4. Алгоритм поиска вершинных отображений единичных рангов

3.3.5. Алгоритм поиска вершинных отображений неединичных рангов

3.3.6. Алгоритм вычисления значения критерия оптимальности задачи согласования отображения

3.3.7. Алгоритм перехода между отображениями

3.4. Выводы по Главе

Глава 4. Программная реализация разработанных методов и

алгоритмов и исследование их эффективности

4.1. Синтез программы оптимизации

4.1.1. Программная модель СИЭЛ

4.1.2. Аннотированный программный код

4.1.3. Переменные программных функций

4.1.4. Программные функции операций

4.1.5. Программные функции коммуникаций

4.2. Архитектура программной системы

4.2.1. Модули программной системы

4.2.2. Библиотеки программной системы

4.2.3. Модуль синтаксического разбора

4.2.4. Модуль синтеза моделей вычислительной системы

4.2.5. Модуль синтеза программы оптимизации

4.2.6. Модуль сборки

4.2.7. Модуль исполнения

4.2.8. Модуль согласования

4.2.9. Модуль оценки

4.3. Исследование эффективности алгоритма согласования

4.3.1. Тестовые алгоритмы оптимизации

4.3.2. Математическое описание алгоритма роя частиц

4.3.3. Экспериментальное тестирование программной системы

4.3.4. Эксперимент по изучению скорости сходимости

4.3.5. Эксперимент по изучению параллельной эффективности

4.3.6. Эксперимент по сравнению индикаторов эффективности

4.3.7. Эксперимент по изучению ускорения

4.3.8. Практическая задача

4.4. Выводы по Главе

Общие выводы и заключение

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

Приложение

Список сокращений и условных обозначений Сокращения

BSP (bulk synchronous parallelism) блочно-синхронный параллелизм CUDA (compute unified device architecture) программно-аппаратная архитектура параллельных вычислений DAG (directed acyclic graph) направленный ациклический граф DRAM (dynamic random access memory) динамическая память с произвольным доступом FPU устройство вычислений с плавающей точкой

GPGPU (general purpose computing on graphics processing units) вычисления общего назначения на графических процессорах

MIMD (multiple instruction, multiple data) класс вычислительных систем «множественный поток инструкций, множественный поток данных» PSO (particle swarm optimization) алгоритм оптимизации роем частиц SIMD (single instruction, multiple data) класс вычислительных систем «одиночный поток инструкций, множественный поток данных»

SIMT (single instruction, multiple threads) модель параллельных вычислений «одна инструкция, много потоков» UML (unified modelling language) унифицированный язык моделирования

ГПО глобальная параметрическая оптимизация ГПУ графическое процессорное устройство

МЭГО-алгоритм метаэвристический алгоритм глобальной оптимизации ОДУ обыкновенное дифференциальное уравнение ПВС параллельная вычислительная система ЦПУ графическое процессорное устройство

Обозначения

СОММБ

ВР Вх Еа

Г1(С,Н)

^ (Т,Т) Рт (Т)

риыз

САР

с(м)

СА+

СА,

Ч

кс

кФ

Х(С,Н) Ьтр

МА • м

Ш1П

N3 Хт

Р /

Р

Ф(Х)

Ф

а

множество программных функций коммуникаций коэффициент вариации величины X

область допустимых значений вектора свободных параметров Р область допустимых значений вектора варьируемых параметров X эффективность параллельной реализации алгоритма реберное отображение графа С на Н

аппроксимированный критерий параллельной эффективности

критерий оптимальности задачи согласования АОт

множество программных функций операций

граф параллельного алгоритма АР

^-итерационный граф алгоритма

раскрытый граф алгоритма

граф последовательного алгоритма А3

история отображений

коэффициент числа испытаний

коэффициент улучшения

вершинное отображение графа С на Н

область допустимых Т-отображений

класс базовых алгоритмов метаэвристической оптимизации символ многокритериальной оптимизации

стандартный параллельный свободной параметр числа островов стандартный параллельный свободной параметр длительности фазы вычислений (сезона) вектор свободных параметров

фиксированное значение вектора свободных параметров

целевая функция базовой задачи оптимизации

средний достигаемый экстремум базовой задачи оптимизации

Ф(Р,Т) векторный критерий оптимальности

достигнутое значение экстремума целевой функции базового алгоритма

га скорость сходимости параллельного алгоритма

Б(С,Н) ограничивающая функция отображения /

гамильтонов путь в ^-итерационном графе алгоритма Т отображение графа алгоритма на граф системы (Т-отображение)

Т фиксированное значение отображения с предыдущей итерации

X вектор варьируемых параметров базовой задачи

Введение диссертации (часть автореферата) на тему «Структурно-параметрическое согласование метаэвристических алгоритмов глобальной оптимизации с архитектурой графических процессорных устройств»

Введение

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

Сложные задачи оптимизации решают при помощи метаэвристических алгоритмов оптимизации, обладающих свободными параметрами, которые влияют на показатели сходимости и эффективности этих алгоритмов. Среди современных высокопроизводительных вычислительных систем выделяют класс систем на основе графических процессоров (ГПУ), хорошо подходящий для параллельных метаэвристических алгоритмов. Возникает важная задача согласования алгоритма оптимизации с вычислительной системой, позволяющая определить оптимальные значения параметров алгоритма, при которых минимизируется время его выполнения на заданной вычислительной системе при сохранении показателей сходимости алгоритма. Методы установки параметров для метаэвристических алгоритмов позволяют решать задачу согласования для непрерывных и целочисленных параметров алгоритма.

Методы решения задачи глобальной безусловной оптимизации разделяют на детерминированные методы, стохастические методы и метаэвристические методы [1]. По строгости поиска методы глобальной оптимизации можно разделить на следующие классы.

• Неполные методы основаны на эвристиках, не гарантирующих обнаружение глобального экстремума.

• Асимптотически полные методы обеспечивают достижение экстремума при бесконечно большом времени поиска. Невозможно определить, был ли достигнут экстремум после заданного числа итераций.

• Полные и строгие методы отличаются от асимптотически полных методов возможностью определения факта достижения экстремума с заданной погрешностью.

Детерминированные методы обычно относят к группам полных методов, тогда как стохастические методы принадлежат к группам неполных и асимптотически полных методов оптимизации [2]. Среди детерминированных методов можно выделить такие известные, как сеточный метод, метод ветвей и границ [3]. Главным достоинством полных методов является гарантия нахождения глобального экстремума за конечное время. Это определяет конечность соответствующих алгоритмов. Сложность и количество вычислений при этом могут быть очень велики. Для сложных задач оптимизации, характеризующихся высокой размерностью или невозможностью декомпозиции пространства поиска, применение детерминированных методов оптимизации является затруднительным.

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

1) эволюционные методы;

2) поведенческие методы.

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

(эвристике), зависящей в общем случае от задачи. Эвристика используется для целенаправленного выбора и осуществления следующего шага метода. Метаэври-стические методы позволяют комбинировать эвристики для решения широкого класса задач. Метаэвристические методы оптимизации показывают хорошую эффективность при решении сложных технических задач, отличающихся высокой размерностью и нетривиальной целевой функцией, решение которых детерминированными методами не приводит к достижению экстремума [4]. Важным отличием метаэвристических алгоритмов являются слабые требования к виду целевой функции, ее дифференцируемости и выпуклости, что позволяет использовать эти методы при решении широкого класса задач.

Эволюционные методы — это группа метаэвристических методов, основывающаяся на принципах эволюции природных систем. Методы используют терминологию генетики и базируются на процедурах мутации, репродукции, селекции. Среди эволюционных методов выделяют четыре основных: генетический алгоритм, эволюционная стратегия, генетическое программирование, эволюционное программирование. Применительно к задачам глобальной оптимизации эволюционные методы имеют преимущества в возможности обмена информацией о локальных экстремумах и покидания областей притяжения локальных экстремумов. Поведенческие методы решения задачи глобальной безусловной оптимизации основаны на моделировании коллективного поведения самоорганизующихся живых или неживых систем, состоящих из простых агентов. Ключевыми идеями поведенческих методов являются децентрализован-ность, взаимодействие агентов, простота поведения агентов. Часто поведенческие методы называют методами роевого интеллекта (swarm intelligence) [1]. Распространенными поведенческими методы глобальной оптимизации являются метод роя частиц, метод колонии муравьев. В методе оптимизации роем частиц [5] агентами являются частицы в пространстве параметров задачи оптимизации. Частицы характеризуются вектором положения и скорости и меняют их на каждой итерации, основываясь на наилучшем достигнутом данной частицей

экстремуме и на информации о наиболее успешных частицах в рое. Вместе эволюционные и поведенческие алгоритмы образуют область эволюционных вычислений (evolutionary computation) [1]. Эволюционные вычисления определяют как класс оптимизационных алгоритмов, вдохновленных биологической эволюцией и поведением живых существ и основанных на вычислительной модели эволюционных процессов.

В последнее время особое внимание уделяется параллельным методам оптимизации. Разработан ряд параллельных моделей для эволюционных и поведенческих методов [6,7]. Основные применяемые параллельные модели — иерархическая, диффузная и островная. Модели в основном ориентированы на параллельные MIMD-системы и кластеры. Подход к распределению вычислительной нагрузки в иерархической модели заключается в вычислении целевых функций для каждой частицы или множества частиц на выделенных процессорах и консолидации результатов на мастер-процессоре. К таким реализациям применима динамическая балансировка загрузки. Преимуществом является возможность простой реализации на произвольных мультикомпьютерах, а недостатком — высокие накладные расходы на коммуникации при большом диаметре коммуникационной сети. Островные и диффузные модели [8] используют параллелизм данных и ориентированы на реализацию на MIMD-системах. В островных моделях общую популяцию разделяют на непересекающиеся «острова» (субпопуляции). Каждый из островов независимо выполняет оптимизацию векторов этой субпопуляции, а затем обменивается частицами с наилучшими результатами после некоторого числа итераций. Модель имеет малые коммуникационные расходы, но может недостаточно эффективно использовать информацию о всей популяции.

Целью диссертационной работы является разработка и исследование эффективности математических моделей, методов и алгоритмов структурно-

параметрического согласования параллельных МЭГО-алгоритмов с архитектурой ГПУ.

Задачи исследования.

1) Обзор методов согласования МЭГО-алгоритмов с архитектурой ГПУ.

2) Разработка математических моделей МЭГО-алгоритма и ГПУ.

3) Разработка и исследование эффективности методов и алгоритмов решения задачи структурно-параметрического согласования МЭГО-алгоритмов с архитектурой ГПУ.

4) Разработка экспериментальной программной системы, реализующей предложенные математические модели, методы и алгоритмы.

5) Исследование эффективности разработанного математического и программного обеспечения при решении тестовых и практически значимых задач.

Актуальность темы исследования. Задачи глобальной оптимизации возникают во многих областях науки и техники. Важным классом алгоритмов оптимизации для решения этих задач являются метаэвристические алгоритмы глобальной оптимизации (МЭГО-алгоритмы), например, алгоритм роя частиц. В силу высокой вычислительной сложности современных задач глобальной оптимизации актуальным является применение параллельных вычислительных систем для решения этих задач. Перспективным классом таких систем выступают графические процессорные устройства (ГПУ), отличительной особенностью которых является иерархическая структура вычислительных устройств и памяти. Следствием этого является актуальность разработки математического и программного обеспечения для эффективного распараллеливания МЭГО-алго-ритмов на ГПУ.

Отличительной особенностью МЭГО-алгоритмов является наличие в них свободных параметров. Значения свободных параметров параллельного МЭГО-алгоритма могут оказывать существенное влияние на его эффективность, например, на скорость сходимости и вероятность локализации глобального экстремума.

Задача отыскания оптимальных значений структурных и свободных параметров параллельного МЭГО-алгоритма называется задачей структурно-параметрического согласования этого алгоритма с архитектурой данной параллельной вычислительной системы (ПВС). Для решения данной задачи необходимо решать задачу «оптимального» отображения полученного параллельного МЭГО-алгоритма на архитектуру ПВС для каждой из рассматриваемых структур и значений его свободных параметров.

Исследования разных аспектов структурно-параметрического согласования МЭГО-алгоритмов с архитектурой ПВС проводят ведущие специалисты K. De Jong, D. Fogel, P. Angeline, R. Smith, T. Back, J. Dongarra, F. Song, S. Chen, В. Воеводин, А. Карпенко, М. Посыпкин. Существующие методы решения задачи согласования ориентированы в основном на классические архитектуры ПВС. Для ГПУ слабо развиты методы автоматического синтеза программы оптимизации, учитывающие особенности архитектуры ГПУ и обеспечивающие высокую параллельную эффективность оптимизации.

Научная новизна исследования определяется следующими результатами.

1) Предложена математическая модель параллельного метаэвристиче-ского алгоритма глобальной оптимизации (МЭГО-алгоритма), отличающаяся использованием графовых моделей последовательного и параллельного МЭГО-алгоритмов, что позволяет формализовать информационную структуру параллельного МЭГО-алгоритма и выделить операции и коммуникации между ними в графе потока управления этого алгоритма.

2) Предложена математическая модель графического процессорного устройства (ГПУ), состоящая из графовой структурной модели, графовой коммуникационной модели и модели памяти ГПУ. Отличительной особенностью модели является формализация особенностей архитектуры ГПУ, что позволяет синтезировать программы оптимизации с высокой параллельной эффективностью.

3) На основании предложенных математических моделей формализована задача структурно-параметрического согласования МЭГО-алгоритма с архи-

тектурой ГПУ, отличающаяся использованием графовых отображений модели этого алгоритма на модель ГПУ и ограничивающих функций отображения, что позволяет сформировать множество допустимых отображений МЭГО-алгоритма на архитектуру ГПУ и повысить эффективность решения задачи согласования.

4) Предложены иерархический метод и алгоритм согласования МЭГО-алгоритма с архитектурой ГПУ для решения задачи структурно-параметрической оптимизации векторного критерия оптимальности. Отличительной особенностью метода и алгоритма является совместное выполнение программы базового МЭГО-алгоритма и программы, реализующей предложенные алгоритмы структурного и параметрического согласования этого алгоритма с архитектурой ГПУ, что позволяет осуществлять динамическую адаптацию структурных и свободных параметров для МЭГО-алгоритма и поиск оптимального отображения этого алгоритма на архитектуру ГПУ.

5) Предложена структура программной системы глобальной оптимизации, реализующей предложенное математическое обеспечение и осуществляющей решение базовой задачи оптимизации при помощи расширения языка программирования С++, позволяющего связывать его синтаксические конструкции с графовой моделью МЭГО-алгоритма. Предложен алгоритм автоматического синтеза программы оптимизации, отличительной особенностью которого является построение программы оптимизации на основе этого языка и графов МЭГО-алгоритма.

Основные положения, выносимые на защиту.

1) Предложена математическая модель параллельного МЭГО-алгоритма и математическая модель ГПУ, учитывающие особенности рассматриваемого класса параллельных алгоритмов и архитектуры ГПУ.

2) Предложен иерархический метод и алгоритм согласования МЭГО-алго-ритма с архитектурой ГПУ для решения задачи структурно-параметрической оптимизации векторного критерия оптимальности, отличающиеся совместным

выполнением программы базового МЭГО-алгоритма и программы, реализующей предложенные алгоритмы, что позволяет осуществлять динамическую адаптацию структурных параметров, свободных параметров и отображения для МЭГО-алгоритма.

3) Предложена структура программной системы, реализующей предложенные математические модели, методы и алгоритмы, и осуществляющей автоматический синтез параллельной программы оптимизации на графовых моделей МЭГО-алгоритма и ГПУ, а также производящей решение базовой задачи оптимизации.

Соответствие паспорту научной специальности. Содержание работы соответствует паспорту научной специальности 2.3.5 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей (технические науки): п.2 «Языки программирования и системы программирования, семантика программ», п.3 «Модели, методы, архитектуры, алгоритмы, языки и программные инструменты организации взаимодействия программ и программных систем», п.8 «Модели и методы создания программ и программных систем для параллельной и распределенной обработки данных, языки и инструментальные средства параллельного программирования».

Объектом исследования является системное программное обеспечение

ГПУ.

Предметом исследования является задача структурно-параметрического согласования параллельных МЭГО-алгоритмов с архитектурой ГПУ.

Методы исследования. При разработке математических моделей, методов, алгоритмов и программного обеспечения использовались методы теории графов, теории вероятностей, теории параллельных вычислений и языков программирования, методы нелинейного программирования, многокритериальной оптимизации, дискретной оптимизации. Использованы численные методы реше-

ния систем обыкновенных дифференциальных уравнений и систем линейных уравнений.

Теоретическая и практическая значимость. Разработаны математические модели, методы и алгоритмы согласования МЭГО-алгоритма с архитектурой ГПУ, позволяющие повысить эффективность решения базовой задачи оптимизации.

Предложена структура программной системы, реализующей предложенные математические модели, методы и алгоритмы. Основой системы является подсистема синтеза и исполнения параллельной программы, позволяющая синтезировать параллельную программу, оптимальную для данного ГПУ, а также решить с помощью этой программы исходную (базовую) задачу оптимизации. Использование программной системы позволило ускорить решение тестовых задач глобальной оптимизации от 3 до 8 раз и повысить точность определения их экстремумов до 50 раз.

С использованием разработанного математического и программного обеспечения решена практическая обратная параметрическая задача химической кинетики, основанная на результатах экспериментальных исследований реакции каталитического гидроалюминирования олефинов Институтом нефтехимии и катализа (ИНК) РАН.

Достоверность полученных в диссертации научных результатов обеспечивается строгостью используемого математического аппарата и подтверждается вычислительными экспериментами на широком классе тестовых задач.

Публикации. Основные результаты диссертации опубликованы в 16 научных работах в журналах и сборниках трудов конференций, из них 3 работы — в рецензируемых журналах, рекомендованных ВАК РФ, 2 работы —в сборниках, индексируемых в Scopus и Web of Science. Основные результаты опубликованы в работах [9-25].

Апробация работы. Основные результаты и положения диссертационной работы представлены на международном симпозиуме «Интеллектуальные системы» (Санкт-Петербург, 2018); международной научной конференции «Параллельные Вычислительные Технологии» (Челябинск, 2013); всероссийских суперкомпьютерных конференциях «Научный сервис в сети Интернет» (Абрау-Дюрсо, 2009, 2011—2013); международной молодежной конференции «Наукоемкие технологии и интеллектуальные системы» (Москва, 2011, 2012); международной научной конференции «Системы компьютерной математики и их приложения» (Смоленск, 2017).

Внедрение результатов работы. Результаты диссертационной работы использованы в учебном процессе кафедры САПР МГТУ им. Н.Э. Баумана, а также при решении задач химической кинетики, исследуемых Лабораторией математической химии Института нефтехимии и катализа РАН.

Основные результаты и положения диссертационной работы представлены на международном симпозиуме «Интеллектуальные системы» (Санкт-Петербург, 2018); международной научной конференции «Параллельные Вычислительные Технологии» (Челябинск, 2013); всероссийских суперкомпьютерных конференциях «Научный сервис в сети Интернет» (Абрау-Дюрсо, 2009, 2011— 2013); международной молодежной конференции «Наукоемкие технологии и интеллектуальные системы» (Москва, 2011, 2012); международной научной конференции «Системы компьютерной математики и их приложения» (Смоленск, 2017). Результаты диссертационной работы использованы в учебном процессе кафедры САПР МГТУ им. Н.Э. Баумана, а также при решении задач химической кинетики, исследуемых Лабораторией математической химии Института нефтехимии и катализа РАН.

Объем и структура диссертации. Диссертация состоит из введения, четырех глав, основных выводов по работе, одного приложения, заключения, биб-

лиографии и списка литературы из 250 наименований. Объем работы составляет 220 страниц, включая 38 рисунков и 6 таблиц.

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

В первой главе рассмотрена базовая задача глобальной параметрической оптимизации, приведен обзор основных классов последовательных и параллельных МЭГО-алгоритмов, применяемых моделей параллелизма, методов установки свободных параметров этих алгоритмов. Представлены параллельные вычислительные системы на основе ГПУ. Выполнен обзор методов согласования параллельных МЭГО-алгоритмов с архитектурой ПВС. Рассмотрены особенности архитектуры ГПУ, важные с точки зрения решения задачи согласования. Сформулированы основные требования к методам и алгоритмам решения этой задачи.

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

Третья глава посвящена разработке методов и алгоритмов согласования базового МЭГО-алгоритма с архитектурой ГПУ. В главе представлена формализация задачи структурно-параметрического согласования, дана постановка задачи структурно-параметрического согласования, изложены предложенные в диссертации методы и алгоритмы решения этой задачи.

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

тивности системы, а также результаты ее применения для решения тестовых и практических задач глобальной оптимизации.

Благодарности. Автор выражает глубокую признательность научному руководителю Карпенко А.П.

Глава 1. Задача структурно-параметрического согласования и обзор

методов ее решения

В данной главе рассматриваем задачу глобальной параметрической оптимизации. Приводим обзор основных классов последовательных и параллельных метаэвристических алгоритмов глобальной оптимизации, применяемых моделей параллелизма, методов установки параметров метаэвристических алгоритмов — настройки и адаптации параметров. Представляем параллельные вычислительные системы на основе графических процессоров, хорошо подходящие для реализации алгоритмов с островной моделью параллелизма. Анализируем методы согласования и планирования параллельных метаэвристических алгоритмов с вычислительной системой.

1.1. Постановка задачи глобальной оптимизации

Называем исходную задачу глобальной оптимизации базовой задачей оптимизации. Метаэвристический алгоритм, используемый для решения базовой задачи, называем базовым алгоритмом оптимизации.

Определим базовую задачу оптимизации следующим образом:

тш Ф(Х) = Ф(Х*) , (1.1)

а етх

где Ф(Х) — целевая функция задачи; X* — оптимальное значение вектора варьируемых параметров базовой задачи, Бх С К — область допустимых значений вектора X.

В англоязычной литературе термины «метод» и «алгоритм» слабо различаются (в частности, методы и алгоритмы оптимизации общепринято называть алгоритмами оптимизации), поэтому, понимая разницу между этими терминами, придерживаемся термина «алгоритм».

1.2. Параллельные и последовательные метаэвристические алгоритмы оптимизации

Метаэвристические алгоритмы являются относительно новым и быстро развивающимся классом алгоритмов. Метаэвристические алгоритмы представляют собой итерационные алгоритмы, основанные на сочетании и управлении подчиненными эвристиками для направленного исследования пространства поиска [26,27]. Под эвристиками понимают алгоритмы получения приближенного решения заданной задачи оптимизации за меньшее время, чем при решении точным алгоритмом. Метаэвристические алгоритмы способны отыскать решение, близкое к оптимальному, без априорных знаний о свойствах целевой функции и пространства поиска и поэтому применимы для решения широкого класса задач оптимизации высокой размерности и вычислительной сложности.

Эти алгоритмы разделяют на:

1) эволюционные алгоритмы (evolutionary algorithms);

2) поведенческие алгоритмы или алгоритмы роевого интеллекта (swarm intelligence) [1].

1.2.1. Эволюционные алгоритмы оптимизации

Выделяют следующие общие принципы построения эволюционных алгоритмов [28]. Процесс решения задачи представляют как процесс обучения группы индивидов, каждый из которых кодирует отдельное решение. Каждому индивиду назначают функцию пригодности (fitness function, фитнесс-функцию). Других индивидов получают при помощи операций мутации и рекомбинации из существующих индивидов. Выбор новой популяции осуществляют с учетом пригодности индивидов и операций селекции. Различные операторы эволюционных алгоритмов далее называем эволюционными операторами.

Эволюционные алгоритмы включают в себя несколько видов [29].

• Генетический алгоритм (genetic algorithm) предложен в 1975 г. Холлан-дом (Holland).

• Генетическое программирование (genetic programming) в современном состоянии описано Коза (Koza).

• Эволюционное программирование (evolutionary programming) развито для непрерывной оптимизации Фогелем (Fogel).

• Эволюционная стратегия (evolution strategy) разработана Рехенбергом (Rechenberg).

Данная классификация является общепринятой, однако не единственной. Энгельбрехт (Engelbrecht) [30] относит к эволюционным вычислениям алгоритмы дифференциальной эволюции, культурные алгоритмы и алгоритмы коэволюции, а генетическое программирование — к генетическим алгоритмам.

Наиболее распространенными эволюционными алгоритмами для непрерывной оптимизации являются генетический алгоритм и эволюционная стратегия.

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

Эволюционные стратегии отличаются использованием мутации как основного эволюционного оператора [30]. Операторы рекомбинации выбирают нового индивида либо из двух родительских индивидов, либо из всей популяции. Операторы селекции осуществляют выбор новой (дочерней) популяции из родительской.

Список литературы диссертационного исследования кандидат наук Селиверстов Евгений Юрьевич, 2024 год

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

1. Burke E., Kendall G. Search methodologies: introductory tutorials in optimization and decision support techniques. 2nd ed. Springer, 2014.

2. Larson J., Menickelly M., Wild S. M. Derivative-free optimization methods // Acta Numerica. 2019. Vol. 28. P. 287-404.

3. Rao S. S. Engineering optimization: theory and practice. John Wiley & Sons, 2019.

4. Карпенко А. П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновлённые природой. 2-е изд. МГТУ им. Н.Э. Баумана, 2016.

5. Kennedy J., Eberhart R. Particle swarm optimization //In Proceedings of IEEE International conference on Neural Networks. 1995. P. 1942-1948.

6. Belal M., El-Ghazawi T. Parallel Models for Particle Swarm Optimizers // IJICIS. 2004. Vol. 1. P. 100-111.

7. Cheng J. R., Gen M. Accelerating genetic algorithms with GPU computing: A selective overview // Computers & Industrial Engineering. 2019. Vol. 128. P. 514-525.

8. Izzo D., Rucinski M., Ampatzis C. Parallel global optimisation meta-heuristics using an asynchronous island-model // Evolutionary Computation, 2009. CEC'09. IEEE Congress on / IEEE. 2009.

P. 2301-2308.

9. Карпенко А. П., Селиверстов Е. Ю. Обзор методов роя частиц для задачи глобальной оптимизации // Наука и образование: Электронное научное издание. 2009. № 3. С. 1-26.

10. Карпенко А. П., Селиверстов Е. Ю. Глобальная оптимизация методом роя частиц. Обзор // Информационные технологии. 2010. № 2. С. 25-34.

11. Карпенко А. П., Селиверстов Е. Ю. Глобальная оптимизация методом роя частиц на графических процессорах // Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность: Труды Всероссийской суперкомпьютерной конференции. Издательство МГУ. 2009. С. 188-191.

12. Карпенко А. П., Селиверстов Е. Ю. Исследование влияния свободных параметров параллельного метода оптимизации роем частиц на его эффективность // 12-ая международная молодежная конференция «Наукоемкие технологии и интеллектуальные системы». МГТУ им. Н. Э. Баумана. 2010. С. 53-56.

13. Карпенко А. П., Селиверстов Е. Ю. Глобальная безусловная оптимизация роем частиц на графических процессорах архитектуры CUDA // Наука и образование: Электронное научное издание. 2010. № 4. С. 1-18. http://technomag.edu.ru/doc/142202.html (дата обращения: 01.03.11),

14. Карпенко А. П., Селиверстов Е. Ю. Исследование эффективности параллельных методов роя частиц для архитектур графических процессоров // Труды XV Байкальской международной школы-семинара «Методы оптимизации и их приложения». 2011. Т. 4. С. 134-139.

15. Карпенко А. П., Селиверстов Е. Ю. Применение метода роя частиц для задач проектирования буровых растворов // 13-ая международная молодежная конференция «Наукоемкие технологии и интеллектуальные системы». МГТУ им. Н. Э. Баумана. 2011. С. 82-85.

16. Параллельный метод роя частиц в обратных кинетических задачах / Селиверстов Е. Ю. [и др.] // Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность: Труды Всероссийской суперкомпьютерной конференции. Издательство МГУ. 2011. С. 244-248.

17. Воробьева Е. Ю., Карпенко А. П., Cеливерстов Е. Ю. Ко-гибридизация алгоритмов роя частиц // Наука и образование: Электронное научное издание. 2012. № 4. С. 1-20. http://technomag.edu.ru/doc/355729.html (дата обращения: 16.12.15),

18. Макроскопическое исследование реакции циклоалюминирования олефинов / Селиверстов Е. Ю. [и др.] // Научный сервис в сети Интернет: поиск новых решений: Труды Всероссийской суперкомпьютерной конференции. Издательство МГУ. 2012. С. 177-184.

19. Параллелизм в структурной и параметрической идентификации кинетических моделей химических реакций / Селиверстов Е. Ю. [и др.] // Научный сервис в сети Интернет: все грани параллелизма: Труды Всероссийской суперкомпьютерной конференции. Издательство МГУ. 2013. С. 268-273.

20. Программная система Complex-Macro для структурной и параметрической идентификации кинетических моделей химических реакций / Губайдуллин И. М., Карпенко А. П., Селиверстов Е. Ю. и

Тихонова М. В. // Труды международной научной конференции «Параллельные Вычислительные Технологии 2013». Издательский центр ЮУрГУ. 2013. С. 590. стендовый доклад.

21. Селиверстов Е. Ю. Обзор методов решения задачи планирования параллельных алгоритмов // Инженерный вестник. Электронный научно-технический журнал. 2014. Т. 12. С. 541-555. http://ainjournal.ru/doc/746179.html (дата обращения: 12.06.15),

22. Селиверстов Е. Ю. Графовые модели графического процессора // Системы компьютерной математики и их приложения: Материалы XVIII Международной научной конференции. Издательство СмолГУ. 2017.

С. 117-119.

23. Seliverstov E., Karpenko A. Hierarchical Model of Parallel Metaheuristic Optimization Algorithms // Procedia Computer Science. 2019. Vol. 150. С. 441-449. Proceedings of the 13th International Symposium Intelligent Systems 2018.

24. Селиверстов Е. Ю. Структурное согласование алгоритмов глобальной оптимизации с архитектурой графических процессоров // Вестник МГТУ

им. Н.Э. Баумана. Сер. Приборостроение. 2022. № 2. С. 42-59.

25. Селиверстов Е. Ю. Иерархический метод установки параметров параллельных популяционных метаэвристических алгоритмов оптимизации // Сибирский журнал индустриальной математики. 2022. Т. 25, № 4. С. 164-178.

26. A survey on new generation metaheuristic algorithms / Dokeroglu T., Sevinc E., Kucukyilmaz T., and Cosar E. // Computers & Industrial Engineering. 2019. Vol. 137. P. 106040.

27. De Jong K. A. Evolutionary computation: a unified approach. Cambridge, MA : Springer, 2006.

28. Simon D. Evolutionary Optimization Algorithms. Wiley, 2013.

29. Back T., Fogel D., Michalewicz Z. Evolutionary Computation 1: Basic algorithms and operators. CRC press, 2018.

30. Engelbrecht A. Computational intelligence: an introduction. Wiley, 2007.

31. Дивеев А. И., Константинов С. В. Эволюционные алгоритмы для решения задачи оптимального управления // Вестник Российского университета дружбы народов. Серия: Инженерные исследования. 2017. Т. 18, № 2.

С. 254-265.

32. Dorigo M., Blum C. Ant colony optimization theory: A survey // Theoretical Computer Science. 2005. Vol. 344, N. 2. P. 243-278.

33. Shehab M., Khader A. T., Al-Betar M. A. A survey on applications and variants of the cuckoo search algorithm // Applied Soft Computing. 2017. Vol. 61. P. 1041-1059.

34. Tamura K., Yasuda K. Spiral Optimization Algorithm Using Periodic Descent Directions // SICE Journal of Control, Measurement, and System Integration. 2016. Vol. 9, N. 3. P. 134-143.

35. Zhang Y., Wang S., Ji G. A Comprehensive Survey on Particle Swarm Optimization Algorithm and Its Applications // Mathematical Problems in Engineering. 2015. P. 1-38.

36. Parsopoulos K. E., Vrahatis M. N. Recent approaches to global optimization problems through Particle Swarm Optimization // Natural Computing. 2002. Vol. 1. P. 235-306.

http://dl.acm.org/citation.cfm?id=599705.599706.

37. Ryser-Welch P., Miller J. F. A review of hyper-heuristic frameworks // Proceedings of the evo20 workshop, AISB. 2014. Vol. 2014.

38. Harada T., Alba E. Parallel genetic algorithms: a useful survey // ACM Computing Surveys (CSUR). 2020. Vol. 53, N. 4. P. 1-39.

39. He H., Sykora O., Salagean A. Various island-based parallel genetic algorithms for the 2-page drawing problem // Proceedings of the 24th IASTED international conference on Parallel and distributed computing and networks. Anaheim, CA, USA : ACTA Press. 2006. PDCN'06. P. 316-323.

40. Sudholt D. Parallel Evolutionary Algorithms // Springer Handbook of Computational Intelligence / ed. by Kacprzyk J., Pedrycz W. Berlin, Heidelberg : Springer Berlin Heidelberg, 2015. P. 929-959.

ISBN: 978-3-662-43505-2.

https://doi.org/10.1007/978-3-662-43505-2_46.

41. A new cooperative evolutionary multi-swarm optimizer algorithm based on CUDA architecture applied to engineering optimization / Souza D. L., Teixeira O. N., Monteiro D. C., and Oliveira R. C. L. d. // Combinations of Intelligent Methods and Applications. Springer, 2013. P. 95-115.

42. Tan Y., Ding K. A survey on GPU-based implementation of swarm intelligence algorithms // IEEE transactions on cybernetics. 2015. Vol. 46, N. 9. P. 2028-2041.

43. Calazan R. M., Nedjah N., Macedo Mourelle L. d. Three alternatives for parallel GPU-based implementations of high performance particle swarm optimization // International work-conference on artificial neural networks / Springer. 2013. P. 241-252.

44. Franz W., Thulasiraman P., Thulasiram R. K. Optimization of an OpenCL-based multi-swarm PSO algorithm on an APU // International Conference on Parallel Processing and Applied Mathematics / Springer. 2013. P. 140-150.

45. Nedjah N., Moraes Calazan R. d., Macedo Mourelle L. d. A fine-grained parallel particle swarm optimization on many-core and multi-core architectures // International Conference on Parallel Computing Technologies / Springer. 2017. P. 215-224.

46. GPU parallelization strategies for metaheuristics: a survey / Essaid M., Idoumghar L., Lepagnot J., and Brevilliers M. // International Journal of Parallel, Emergent and Distributed Systems. 2019. Vol. 34, N. 5. P. 497-522.

47. Scott E. O., De Jong K. A. Understanding Simple Asynchronous Evolutionary Algorithms // Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII. New York, NY, USA : Association for Computing Machinery. 2015. FOGA '15. P. 85-98. https://doi.org/10.1145/2725494.2725509.

48. Angelo J. S., Augusto D. A., Barbosa H. J. Strategies for Parallel Ant Colony Optimization on Graphics Processing Units // Ant colony optimization-techniques and applications. 2013. P. 63-83.

49. Hussain M. M., Hattori H., Fujimoto N. A CUDA Implementation of the Standard Particle Swarm Optimization // 2016 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC). 2016. P. 219-226.

50. Kromer P., Platos J., Snaisel V. Nature-inspired meta-heuristics on modern GPUs: state of the art and brief survey of selected algorithms // International Journal of Parallel Programming. 2014. Vol. 42, N. 5.

P. 681-709.

51. Alba E., Luque G., Nesmachnow S. Parallel metaheuristics: recent advances and new trends // International Transactions in Operational Research. 2013.

Vol. 20, N. 1. P. 1-48.

52. Enhancing data parallelism for ant colony optimization on GPUs / Cecilia J. M., Garcia J. M., Nisbet A., Amos M., and Ujaldon M. // Journal of Parallel and Distributed Computing. 2013. Vol. 73, N. 1. P. 42-51.

53. Wu D., Gao H. Study on asynchronous update mechanism in Particle Swarm Optimization // 2014 14th International Symposium on Communications and Information Technologies (ISCIT) / IEEE. 2014. P. 90-93.

54. Rauber T., Riinger G. Parallel programming: For multicore and cluster systems. Springer Science & Business, 2013.

55. Park S., Suh Y., Lee J. FedPSO: federated learning using particle swarm optimization to reduce communication costs // Sensors. 2021. Vol. 21, N. 2. P. 600.

56. Сахаров М. Методика проектирования программ для решения задач глобальной параметрической оптимизации на слабосвязанных вычислительных системах : дис. ... канд. наук ; Москва. 2020. С. 123.

57. El-Abd M. Hybrid cooperative co-evolution for large scale optimization // 2014 IEEE Symposium on Swarm Intelligence. 2014. P. 1-6.

58. A parallel cooperative hybrid method based on ant colony optimization and 3-Opt algorithm for solving traveling salesman problem / Giilcu §., Mahi M., Baykan O. K., and Kodaz H. // Soft Computing. 2018. Vol. 22, N. 5.

P. 1669-1685.

59. A Survey on Cooperative Co-Evolutionary Algorithms / Ma X., Li X., Zhang Q., Tang K., Liang Z., Xie W., and Zhu Z. // IEEE Transactions on Evolutionary Computation. 2019. Vol. 23, N. 3. P. 421-441.

60. De Jong K. Parameter Setting in EAs: a 30 Year Perspective // Parameter Setting in Evolutionary Algorithms / ed. by Lobo F. G., Lima C. F., Michalewicz Z. Springerpringer Verlag, 2007. Vol. 54 of Studies in Computational Intelligence. P. 1-18.

61. Angeline P. Adaptive and self-adaptive evolutionary computations // Computational Intelligence: A Dynamic Systems Perspective / Citeseer. IEEE Press. 1995. P. 152-163.

62. Eiben A., Hinterding R., Michalewicz Z. Parameter control in evolutionary algorithms // Evolutionary Computation, IEEE Transactions on. 1999. Vol. 3, N. 2. P. 124-141.

63. Kramer O. Self-Adaptation // Self-Adaptive Heuristics for Evolutionary Computation. Springer, 2008. P. 29-47.

64. Smith J., Fogarty T. Operator and parameter adaptation in genetic algorithms // Soft Computing-A Fusion of Foundations, Methodologies and Applications. 1997. Vol. 1, N. 2. P. 81-87.

65. Nagireddy V., Parwekar P., Mishra T. K. Velocity adaptation based PSO for localization in wireless sensor networks // Evolutionary Intelligence. 2021. Vol. 14, N. 2. P. 243-251.

66. Bratton D., Kennedy J. Defining a standard for particle swarm optimization // Swarm Intelligence Symposium, 2007. SIS 2007. IEEE / IEEE. 2007. P. 120-127.

67. Meyer-Nieberg S., H.-G. B. Self-Adaptation in Evolutionary Algorithms // Parameter Setting in Evolutionary Algorithms / ed. by Lobo F., Lima C., Michalewicz Z. Springer Berlin Heidelberg, 2007. Vol. 54 of Studies in Computational Intelligence. P. 47-76.

68. A survey on algorithm adaptation in evolutionary computation / Zhang J., Chen W.-N., Zhan Z.-H., Yu W.-J., Li Y.-L., Chen N., and Zhou Q. // Frontiers of Electrical and Electronic Engineering. 2012. Vol. 7, N. 1.

P. 16-31.

69. Fogel L. J., Angeline P. J., Fogel D. B. An evolutionary programming approach to self-adaptation on finite state machines // Evolutionary Programming. 1995. P. 355-365.

70. Kennedy J., Mendes R. Population structure and particle swarm performance // CEC '02: Proceedings of the Evolutionary Computation on 2002. CEC '02. Proceedings of the 2002 Congress. Washington, DC, USA : IEEE Computer Society. 2002. P. 1671-1676.

71. An adaptive particle swarm optimization method based on clustering / Liang X., Li W., Zhang Y., and Zhou M. // Soft Computing. 2015. Vol. 19. P. 431-448.

72. Parameter control in evolutionary algorithms / Eiben A., Michalewicz Z., Schoenauer M., and Smith J. // Parameter Setting in Evolutionary Algorithms / ed. by Lobo F., Lima C., Michalewicz Z. Springer Berlin Heidelberg, 2007. Vol. 54 of Studies in Computational Intelligence. P. 19-46.

73. Агасиев Т. Автоматизация настройки алгоритмов параметрической оптимизации проектных решений для серийных задач высокой вычислительной сложности : дис. ... канд. наук ; Москва. 2021. С. 163.

74. Parameter adaptation in ant colony optimization / Stiitzle T., Lopez-Ibanez M., Pellegrini P., Maur M., de Oca M. M., Birattari M., and Dorigo M. // Autonomous Search. Springer, 2012. P. 191-215.

75. Huang C., Li Y., Yao X. A survey of automatic parameter tuning methods for metaheuristics // IEEE transactions on evolutionary computation. 2019. Vol. 24, N. 2. P. 201-216.

76. Hinterding R., Michalewicz Z., Peachey T. C. Self-adaptive genetic algorithm for numeric functions // Parallel Problem Solving from Nature—PPSN IV. Springer, 1996. P. 420-429.

77. Smit S., Eiben A. Comparing Parameter Tuning Methods for Evolutionary Algorithms // Proceedings of the 2009 IEEE Congress on Evolutionary Computation. IEEE Press. 2009. P. 399-406.

78. Krejca M. S., Witt C. Theory of estimation-of-distribution algorithms // Theory of Evolutionary Computation. Springer, 2020. P. 405-442.

79. Montero E., Riff M.-C., Neveu B. A beginner's guide to tuning methods // Applied Soft Computing. 2014. Vol. 17. P. 39-51.

80. Eiben A. E., Smit S. K. Parameter Tuning for Configuring and Analyzing Evolutionary Algorithms // Swarm and Evolutionary Computation. 2011. Vol. 1. P. 19-31.

81. Algorithm runtime prediction: Methods & evaluation / Hutter F., Xu L., Hoos H. H., and Leyton-Brown K. // Artificial Intelligence. 2014. Vol. 206. P. 79-111. https:

//www.sciencedirect.com/science/article/pii/S0004370213001082.

82. Kaltenecker C. Comparison of analytical and empirical performance models: A case study on multigrid systems // Masterthesis, University of Passau, Germany. 2016. P. 10.

83. Michalewicz Z., Schmidt M. Parameter Control in Practice // Parameter Setting in Evolutionary Algorithms / ed. by Lobo F., Lima C., Michalewicz Z. Springer Berlin Heidelberg, 2007. Vol. 54 of Studies in Computational Intelligence. P. 277-294. http://dx.doi.org/10.1007/978-3-540-69432-8_14.

84. Weinberg R., Berkus M. Computer simulation of a living cell: Part I // International journal of bio-medical computing. 1971. Vol. 2, N. 2.

P. 95-120.

85. Konstantinov S., Khamidova U., Sofronova E. A novel hybrid method of global optimization based on the grey wolf optimizer and the bees algorithm // Procedia Computer Science. 2019. Vol. 150. P. 471-477.

86. A survey on cooperative co-evolutionary algorithms / Ma X., Li X., Zhang Q., Tang K., Liang Z., Xie W., and Zhu Z. // IEEE Transactions on Evolutionary Computation. 2018. Vol. 23, N. 3. P. 421-441.

87. Particle swarm optimization: Hybridization perspectives and experimental illustrations / Thangaraj R., Pant M., Abraham A., and Bouvry P. // Applied Mathematics and Computation. 2011. Vol. 217, N. 12. P. 5208 -

5226. http://dx.doi.org/10.1016/j.amc.2010.12.053.

88. Pedersen M. Tuning & simplifying heuristical optimization : Ph.D. thesis ; PhD thesis, School of Engineering Sciences, University of Southampton, England. 2010. P. 205.

89. Rechenberg I. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-holzbog, Stuttgart, 1994.

90. Evolution strategies for continuous optimization: A survey of the state-of-the-art / Li Z., Lin X., Zhang Q., and Liu H. // Swarm and Evolutionary Computation. 2020. Vol. 56. P. 100694.

91. A comparative study of large-scale variants of CMA-ES / Varelas K., Auger A., Brockhoff D., Hansen N., ElHara O. A., Semet Y., Kassab R., and Barbaresco F. // International conference on parallel problem solving from nature / Springer. 2018. P. 3-15.

_ / _

92. Karafotias G., Hoogendoorn M., Eiben A. E. Parameter control in evolutionary algorithms: Trends and challenges // IEEE Transactions on Evolutionary Computation. 2014. Vol. 19, N. 2. P. 167-187.

93. Kirk D., Wen-mei W. Programming massively parallel processors: a hands-on approach. 2nd ed. Morgan Kaufmann, 2013.

94. Martin C. Multicore processors: challenges, opportunities, emerging trends // Proc. Embedded World Conference. 2014. Vol. 2014. P. 1-9.

95. Atachiants R., Doherty G., Gregg D. Parallel performance problems on shared-memory multicore systems: taxonomy and observation // IEEE Transactions on Software Engineering. 2016. Vol. 42, N. 8. P. 764-785.

96. Vajda A. Programming many-core chips. Springer, 2011.

97. llana S., Xhafa F. Programming Multicore and Many-core Computing Systems. John Wiley & Sons, Inc., 2017.

98. A Survey of GPGPU Parallel Processing Architecture Performance Optimization / Jia S., Tian Z., Ma Y., Sun C., Zhang Y., and Zhang Y. // 2021 IEEE/ACIS 20th International Fall Conference on Computer and

Information Science (ICIS Fall). 2021. P. 75-82.

99. Chrysos G. Intel Xeon Phi coprocessor (codename Knights Corner) // Hot Chips: A Symposium on High Performance Chips. 2012. P. 1-31.

100. Rahman R. Intel Xeon Phi Coprocessor Architecture and Tools: The Guide for Application Developers. 1st ed. Apress, 2013.

101. A scalability analysis of many cores and on-chip mesh networks on the tile-gx platform / Liu Y., Sasaki H., Kato S., and Edahiro M. // 2016 IEEE 10th International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSOC) / IEEE. 2016. P. 46-52.

102. Xu Z., Lin J., Matsuoka S. Benchmarking sw26010 many-core processor // 2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) / IEEE. 2017. P. 743-752.

103. Возможности многоядерных процессоров MALT в задачах обработки изображений / Михеев Н. Г., Антонюк В. А., Елизаров С. Г. и Лукьянченко Г. А. // Вычислительные методы и программирование. 2020. Т. 21, № 2. С. 187-195.

104. TrueNorth: Accelerating from zero to 64 million neurons in 10 years / DeBole M. V., Taba B., Amir A., Akopyan F., Andreopoulos A., Risk W. P., Kusnitz J., Otero C. O., Nayak T. K., Appuswamy R., et al. // Computer. 2019. Vol. 52, N. 5. P. 20-29.

105. Evans J. Nvidia Grace // 2022 IEEE Hot Chips 34 Symposium (HCS). 2022. P. 1-20.

106. Brodtkorb A. R., Hagen T. R., S^tra M. L. Graphics processing unit (GPU) programming strategies and trends in GPU computing // Journal of Parallel and Distributed Computing. 2013. Vol. 73, N. 1. P. 4-13.

107. Dally W. J., Keckler S. W., Kirk D. B. Evolution of the Graphics Processing Unit (GPU) // IEEE Micro. 2021. Vol. 41, N. 6. P. 42-51.

108. Revisiting ILP designs for throughput-oriented GPGPU architecture / Xiang P., Yang Y., Mantor M., Rubin N., and Zhou H. // 2015 15th

IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing / IEEE. 2015. P. 121-130.

109. AMD Graphics Cores Next (GCN) architecture : Rep. / AMD ; executor: AMD : 2012. P. 1-18.

110. Cheng J., Grossman M., McKercher T. Professional CUDA C Programming. 1st ed. Wrox Press Ltd., 2014.

111. Heterogeneous computing with OpenCL 2.0 / Kaeli D. R., Mistry P., Schaa D., and Zhang D. P. Morgan Kaufmann, 2015.

112. The OpenACC Application Programming Interface : Rep. / OpenACC Working Group : 2020. https://www.openacc.org/sites/default/ files/inline-images/Specification/OpenACC-3.1-final.pdf.

113. Kwok Y.-K. Efficient Algorithms for Scheduling and Mapping of Parallel Programs onto Parallel Architectures : Ph. D. thesis ; The Hong Kong University of Science and Technology. 1994. P. 120.

114. Тарков М. Вложение структур параллельных программ в структуры живучих распределенных вычислительных систем // Автометрия. 2003. Т. 39, № 3. С. 84-96.

115. Курносов М. Алгоритмы вложения параллельных программ в иерархические распределённые вычислительные системы // Вестник СибГУТИ. 2009. № 2. С. 1-25.

116. Воеводин В. Об отображение проблем вычислительной математики на архитектуру вычислительных систем // Вычислительные методы и программирование. 2000. Т. 1. С. 37-44.

117. Воеводин B. В., Воеводин Вл. В. Параллельные вычисления. БХВ-Петербург, 2002.

118. Сластен Л. Методы и средства отображения параллельных алгоритмов задач в многопроцессорную вычислительную систему со структурно-процедурной реализацией вычислений : дис. ... канд. наук ; Таганрог. 2005. С. 214.

119. Марчук Г., Котов В. Проблемы вычислительной техники и фундаментальные исследования // Автоматика и вычислительная техника. 1979. № 2. С. 3-14.

120. Карпенко А. Параметрическое согласование вычислительных алгоритмов с архитектурой многопроцессорных систем // Наука и образование: Электронное научное издание. 2006. № 9. С. 1-29.

121. Mapping on multi/many-core systems: survey of current and emerging trends / Singh A. K., Shafique M., Kumar A., and Henkel J. // 2013 50th ACM/EDAC/IEEE Design Automation Conference (DAC) / IEEE. 2013. P. 1-10.

122. Sinnen O. Task scheduling for parallel systems. Wiley-Interscience, 2007.

123. Foster I. Designing and building parallel programs. Addison-Wesley Reading, 1995. http://www.mcs.anl.gov/~itf/dbpp/.

124. Sarkar V. Partitioning and scheduling parallel programs for multiprocessors. MIT press, 1989.

125. Arunarani A., Manjula D., Sugumaran V. Task scheduling techniques in cloud computing: A literature survey // Future Generation Computer Systems. 2019. Vol. 91. P. 407-415.

126. Energy-aware scheduling on multicore heterogeneous grid computing systems / Nesmachnow S., Dorronsoro B., Pecero J. E., and Bouvry P. // Journal of grid computing. 2013. Vol. 11, N. 4. P. 653-680.

127. Recent advances in graph partitioning / Buluc A., Meyerhenke H., Safro I., Sanders P., and Schulz C. // Algorithm engineering. 2016. P. 117-158.

128. Yoosefi A., Naji H. R. A clustering algorithm for communication-aware scheduling of task graphs on multi-core reconfigurable systems // IEEE Transactions on Parallel and Distributed Systems. 2017. Vol. 28, N. 10. P. 2718-2732.

129. Singh K., Alam M., Sharma S. K. A survey of static scheduling algorithm for distributed computing system // International Journal of Computer

Applications. 2015. Vol. 129, N. 2. P. 25-30.

130. Hendrickson B., Kolda T. Graph partitioning models for parallel computing // Parallel computing. 2000. Vol. 26, N. 12. P. 1519-1534.

131. Hypergraph partitioning for multiple communication cost metrics: Model and methods / Deveci M., Kaya K., Ucar B., and Catalyiirek U. V. // Journal of Parallel and Distributed Computing. 2015. Vol. 77. P. 69-83.

132. El-Rewini H., Ali H., Lewis T. Task scheduling in multiprocessing systems // Computer. 1995. Vol. 28, N. 12. P. 27-37.

133. Chen S., Eshaghian M., Wu Y. Mapping arbitrary non-uniform task graphs onto arbitrary non-uniform system graphs // Proceedings of the International Conference on Parallel Processing / Citeseer. 1995. Vol. 2.

P. 191-195.

134. Chen S., Eshaghian M. M. A fast recursive mapping algorithm // Concurrency: Practice and Experience. 1995. Vol. 7, N. 5. P. 391-409.

135. El-Rewini H., Ali H. H. On considering communication in scheduling task graphs on parallel processors // Parallel Algorithm and Applicatio. 1994. Vol. 3, N. 3-4. P. 177-191.

136. Introduction to Parallel Computing (2nd Edition) / Grama A., Karypis G., Kumar V., and Gupta A. 2 ed. Addison Wesley, 2003.

137. Bokhari S. On the mapping problem // Computers, IEEE Transactions on. 1981. Vol. 100, N. 3. P. 207-214.

138. Tran T. T., Araujo A., Beck J. C. Decomposition methods for the parallel machine scheduling problem with setups // INFORMS Journal on Computing. 2016. Vol. 28, N. 1. P. 83-95.

139. Chaudhary V., Aggarwal J. A generalized scheme for mapping parallel algorithms // Parallel and Distributed Systems, IEEE Transactions on. 1993. Vol. 4, N. 3. P. 328-346.

140. A hybrid ILP-CP model for mapping Directed Acyclic Task Graphs to multicore architectures / Emeretlis A., Theodoridis G., Alefragis P., and

Voros N. // 2014 IEEE International Parallel & Distributed Processing Symposium Workshops / IEEE. 2014. P. 176-182.

141. Lai C.-M., Yeh W.-C., Huang Y.-C. Entropic simplified swarm optimization for the task assignment problem // Applied Soft Computing. 2017. Vol. 58. P. 115-127.

142. Scheduling strategies for master-slave tasking on heterogeneous processor platforms / Banino C., Beaumont O., Carter L., Ferrante J., Legrand A., and Robert Y. // Parallel and Distributed Systems, IEEE Transactions on. 2004. Vol. 15, N. 4. P. 319-330.

143. Chen J., John L. K. Efficient program scheduling for heterogeneous multi-core processors // Proceedings of the 46th Annual Design Automation Conference / ACM. 2009. P. 927-930.

144. Parallel scheduling of multiple SDF graphs onto heterogeneous processors / Jeong D., Kim J., Oldja M.-L., and Ha S. // IEEE Access. 2021. Vol. 9.

P. 20493-20507.

145. Galvez J. J., Jain N., Kale L. V. Automatic topology mapping of diverse large-scale parallel applications // Proceedings of the International Conference on Supercomputing. 2017. P. 1-10.

146. Kalyur S., Nagaraja G. ParaCite: auto-parallelization of a sequential program using the program dependence graph // 2016 International conference on computation system and information technology for sustainable solutions (CSITSS) / IEEE. 2016. P. 7-12.

147. DAGuE: A generic distributed DAG engine for high performance computing / Bosilca G., Bouteiller A., Danalis A., Herault T., Lemarinier P., and Dongarra J. // Parallel Computing. 2012. Vol. 38, N. 1. P. 37-51.

148. Berman F., Snyder L. On mapping parallel algorithms into parallel architectures // Journal of Parallel and Distributed Computing. 1987. Vol. 4, N. 5. P. 439-458.

149. Lee S., Aggarwal J. A mapping strategy for parallel processing // Computers, IEEE Transactions on. 1987. Vol. 100, N. 4. P. 433-442.

150. Воеводин В. Методы анализа локальности данных в задаче эффективного отображения программ и алгоритмов на архитектуру вычислительных систем : дис. ... канд. наук ; МГУ им. Ломоносова. 2011. С. 144.

151. Тянь Б., Посыпкин М. А., Сигал И. Х. Балансировка нагрузки на основе оценок алгоритмической сложности подзадач // Информационные технологии и вычислительные системы. 2015. № 1. С. 10-18.

152. PTG: an abstraction for unhindered parallelism / Danalis A., Bosilca G., Bouteiller A., Herault T., and Dongarra J. // 2014 Fourth International Workshop on Domain-Specific Languages and High-Level Frameworks for High Performance Computing / IEEE. 2014. P. 21-30.

153. Song F., YarKhan A., Dongarra J. Dynamic task scheduling for linear algebra algorithms on distributed-memory multicore systems // High Performance Computing Networking, Storage and Analysis, Proceedings of the Conference on / IEEE. 2009. P. 1-11.

154. Thibault S. On runtime systems for task-based programming on heterogeneous platforms : Ph.D. thesis ; Universite de Bordeaux. 2018. P. 138.

155. Scheduling DAG-Structured Computations / Xin Y., Prasanna C., Rajasekaran S., Fiondella L., Ahmed M., and Ammar R. // Multicore Computing: Algorithms, Architectures, and Applications. CRC Press, 2014. P. 205-240.

156. Orr M., Sinnen O. Optimal task scheduling for partially heterogeneous systems // Parallel Computing. 2021. Vol. 107. P. 102815.

157. A meta-scheduler for the Par-monad / Foltzer A., Kulkarni A., Swords R., Sasidharan S., Jiang E., and Newton R. R. // ICFP '12: Proceedings of the 17th ACM SIGPLAN international conference on Functional programming. 2012. P. 1-12.

158. Rogers T. G., O'Connor M., Aamodt T. M. Divergence-aware warp scheduling // Proceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture. 2013. P. 99-110.

159. Access pattern-aware cache management for improving data utilization in GPU / Koo G., Oh Y., Ro W. W., and Annavaram M. // Proceedings of the 44th Annual International Symposium on Computer Architecture. 2017.

P. 307-319.

160. Thread-level priority assignment in global multiprocessor scheduling for DAG tasks / Lee J., Chwa H. S., Lee J., and Shin I. // Journal of Systems and Software. 2016. Vol. 113. P. 246-256.

161. OpenMP task scheduling strategies for multicore NUMA systems / Olivier S. L., Porterfield A. K., Wheeler K. B., Spiegel M., and Prins J. F. // The International Journal of High Performance Computing Applications. 2012. Vol. 26, N. 2. P. 110-124.

162. Hierarchical dag scheduling for hybrid distributed systems / Wu W., Bouteiller A., Bosilca G., Faverge M., and Dongarra J. // 2015 IEEE International Parallel and Distributed Processing Symposium / IEEE. 2015. P. 156-165.

163. Hierarchical place trees: A portable abstraction for task parallelism and data movement / Yan Y., Zhao J., Guo Y., and Sarkar V. // Languages and Compilers for Parallel Computing. 2010. P. 172-187.

164. Song F., Moore S., Dongarra J. Analytical modeling for affinitybased thread scheduling on multicore platforms // University of Tennessee, Computer Science Tech. Rep. UT-CS-08-626. 2008. P. 1-10.

165. Memory aware load balance strategy on a parallel branch-and-bound application / Silva J. M., Boeres C., Drummond L. M., and Pessoa A. A. // Concurrency and Computation: Practice and Experience. 2015. Vol. 27,

N. 5. P. 1122-1144.

166. Declarative tuning for locality in parallel programs / Chatterjee S., Vrvilo N., Budimlic Z., Knobe K., and Sarkar V. // 2016 45th International Conference on Parallel Processing (ICPP) / IEEE. 2016. P. 452-457.

167. Integrating asynchronous task parallelism with MPI / Chatterjee S., Tasirlar S., Budimlic Z., Cave V., Chabbi M., Grossman M., Sarkar V., and Yan Y. // 2013 IEEE 27th International Symposium on Parallel and Distributed Processing / IEEE. 2013. P. 712-725.

168. Yang T., Deng Q., Sun L. Building real-time parallel task systems on multi-cores: A hierarchical scheduling approach // Journal of Systems Architecture. 2019. Vol. 92. P. 1-11.

169. Zhang P., Gao Y., Qiu M. A data-oriented method for scheduling dependent tasks on high-density multi-GPU systems // 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conference on Embedded Software and Systems / IEEE. 2015. P. 694-699.

170. A Hierarchical Task Scheduler for Heterogeneous Computing / Miniskar N. R., Liu F., Young A. R., Chakraborty D., and Vetter J. S. // International Conference on High Performance Computing / Springer. 2021. P. 57-76.

171. Ghane M., Chandrasekaran S., Cheung M. S. Towards a portable hierarchical view of distributed shared memory systems: challenges and solutions // Proceedings of the Eleventh International Workshop on Programming Models and Applications for Multicores and Manycores. 2020. P. 1-10.

172. Heterogeneous System Architecture: A Technical Review : Rep. / AMD ; executor: Kyriazis G. : 2012. P. 1-10.

173. The HPC-DAG Task Model for Heterogeneous Real-Time Systems / Houssam-Eddine Z., Capodieci N., Cavicchioli R., Lipari G., and Bertogna M. // IEEE Transactions on Computers. 2021. Vol. 70, N. 10.

P. 1747-1761.

174. Mittal S., Vetter J. S. A survey of CPU-GPU heterogeneous computing techniques // ACM Computing Surveys (CSUR). 2015. Vol. 47, N. 4. P. 1-35.

175. Grewe D., Wang Z., O'Boyle M. F. Portable mapping of data parallel programs to OpenCL for heterogeneous systems // Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization (CGO) / IEEE. 2013. P. 1-10.

176. Gregg C., Brantley J., Hazelwood K. Contention-aware scheduling of parallel code for heterogeneous systems // 2nd USENIX Workshop on Hot Topics in Parallelism, HotPar, Berkeley, CA. 2010. P. 1-6.

177. Dynamic Scheduling on Heterogeneous Multicores / Edun A., Vazquez R., Gordon-Ross A., and Stitt G. // 2019 Design, Automation Test in Europe Conference Exhibition (DATE). 2019. P. 1685-1690.

178. Emani M. K. Adaptive parallelism mapping in dynamic environments using machine learning : Ph.D. thesis ; University of Edinburgh. 2015. P. 179.

179. Criticality-aware dynamic task scheduling for heterogeneous architectures / Chronaki K., Rico A., Badia R. M., Ayguade E., Labarta J., and

Valero M. // Proceedings of the 29th ACM on International Conference on Supercomputing. 2015. P. 329-338.

180. Composing multiple StarPU applications over heterogeneous machines: a supervised approach / Hugo A., Guermouche A., Wacrenier P.-A., and Namyst R. // The International journal of high performance computing applications. 2014. Vol. 28, N. 3. P. 285-300.

181. StarPU: A unified platform for task scheduling on heterogeneous multicore architectures / Augonnet C., Thibault S., Namyst R., and Wacrenier P. // Concurrency and Computation: Practice and Experience. 2011. Vol. 23, N. 2. P. 187-198.

182. Memory-aware task scheduling with communication overhead minimization for streaming applications on bus-based multiprocessor system-on-chips / Wang Y., Shao Z., Chan H. C., Liu D., and Guan Y. // IEEE transactions on parallel and distributed systems. 2013. Vol. 25, N. 7. P. 1797-1807.

183. Analyzing Machine Learning Workloads Using a Detailed GPU Simulator / Lew J., Shah D. A., Pati S., Cattell S., Zhang M., Sandhupatla A., Ng C., Goli N., Sinclair M. D., Rogers T. G., and Aamodt T. M. // 2019 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). 2019. P. 151-152.

184. Energy-aware scheduling for real-time systems: A survey / Bambagini M., Marinoni M., Aydin H., and Buttazzo G. // ACM Transactions on Embedded Computing Systems (TECS). 2016. Vol. 15, N. 1. P. 1-34.

185. Kocot B., Czarnul P., Proficz J. Energy-Aware Scheduling for High-Performance Computing Systems: A Survey // Energies. 2023. Vol. 16, N. 2. https://www.mdpi.com/1996-1073/16/2/890.

186. Sinnen O., Sousa L. A., Sandnes F. E. Toward a realistic task scheduling model // Parallel and Distributed Systems, IEEE Transactions on. 2006. Vol. 17, N. 3. P. 263-275.

187. Contention-aware reliability efficient scheduling on heterogeneous computing systems / Zhang L., Li K., Zheng W., and Li K. // IEEE Transactions on Sustainable Computing. 2017. Vol. 3, N. 3. P. 182-194.

188. Coordinated static and dynamic cache bypassing for GPUs / Xie X., Liang Y., Wang Y., Sun G., and Wang T. // 2015 IEEE 21st International Symposium on High Performance Computer Architecture (HPCA) / IEEE. 2015. P. 76-88.

189. Modeling and analysis of performances for concurrent multithread applications on multicore and graphics processing unit systems / Cerotti D., Gribaudo M., Iacono M., and Piazzolla P. // Concurrency and Computation: Practice and Experience. 2016. Vol. 28, N. 2. P. 438-452.

190. Blagodurov S., Zhuravlev S., Fedorova A. Contention-aware scheduling on multicore systems // ACM Transactions on Computer Systems (TOCS). 2010. Vol. 28, N. 4. P. 1-45.

191. Kiani M., Rajabzadeh A. Efficient cache performance modeling in GPUs using reuse distance analysis // ACM Transactions on Architecture and Code Optimization (TACO). 2018. Vol. 15, N. 4. P. 1-24.

192. Chen X. E., Aamodt T. M. A First-Order Fine-Grained Multithreaded Throughput Model // IEEE International Symposium on High Performance Computer Architecture (HPCA 2009). 2009. P. 329-340. http://dx.doi.org/10.1109/HPCA.2009.4798270.

193. Притула М. Отображение DVMH-программ на кластеры с графическими процессорами : дис. ... канд. наук ; Москва. 2013. С. 105.

194. Mei X., Chu X. Dissecting GPU memory hierarchy through microbenchmarking // IEEE Transactions on Parallel and Distributed Systems. 2016. Vol. 28, N. 1. P. 72-86.

195. Hong S., Kim H. An analytical model for a GPU architecture with memory-level and thread-level parallelism awareness // Proceedings of the 36th annual international symposium on Computer architecture. New York, NY, USA : ACM. 2009. ISCA '09. P. 152-163. http://doi.acm.org/10.1145/1555754.1555775.

196. E-OSched: a load balancing scheduler for heterogeneous multicores / Khalid Y. N., Aleem M., Prodan R., Iqbal M. A., and Islam M. A. // The Journal of Supercomputing. 2018. Vol. 74, N. 10. P. 5399-5431.

197. Lee S.-Y., Arunkumar A., Wu C.-J. CAWA: Coordinated warp scheduling and cache prioritization for critical warp acceleration of GPGPU workloads // ACM SIGARCH Computer Architecture News. 2015. Vol. 43, N. 3S. P. 515-527.

198. Cache coherence for GPU architectures / Singh I., Shriraman A., Fung W. W., O'Connor M., and Aamodt T. M. // 2013 IEEE 19th

International Symposium on High Performance Computer Architecture (HPCA) / IEEE. 2013. P. 578-590.

199. MDM: The GPU Memory Divergence Model / Wang L., Jahre M., Adileho A., and Eeckhout L. // 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO) / IEEE. 2020. P. 1009-1021.

200. Lai J. Throughput-oriented analytical models for performance estimation on programmable hardware accelerators : Ph.D. thesis ; Universite Rennes 1. 2013. P. 118.

201. The landscape of GPGPU performance modeling tools / Madougou S., Varbanescu A., de Laat C., and van Nieuwpoort R. // Parallel Computing. 2016. Vol. 56. P. 18-33.

202. Schaa D., Kaeli D. Exploring the multiple-GPU design space // Parallel & Distributed Processing, 2009. IPDPS 2009. IEEE International Symposium on / IEEE. 2009. P. 1-12.

203. Task scheduling optimization in cloud computing based on heuristic algorithm / Guo L., Zhao S., Shen S., and Jiang C. // Journal of networks. 2012. Vol. 7, N. 3. P. 547-553.

204. A parallel local search in CPU/GPU for scheduling independent tasks on large heterogeneous computing systems / Iturriaga S., Nesmachnow S., Luna F., and Alba E. // The Journal of Supercomputing. 2015. Vol. 71, N. 2. P. 648-672.

205. Shobaki G., Kerbow A., Mekhanoshin S. Optimizing occupancy and ILP on the GPU using a combinatorial approach // Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization. 2020. P. 133-144.

206. Zhang Y., Owens J. A quantitative performance analysis model for GPU architectures // High Performance Computer Architecture (HPCA), 2011 IEEE 17th International Symposium on / IEEE. 2011. P. 382-393.

207. Meta-programming and Auto-tuning in the Search for High Performance GPU Code / Vollmer M., Svensson B. J., Holk E., and Newton R. R. // Proceedings of the 4th ACM SIGPLAN Workshop on Functional High-Performance Computing. 2015. P. 1-11.

208. Falch T. L., Elster A. C. Machine learning based auto-tuning for enhanced OpenCL performance portability // 2015 IEEE International Parallel and Distributed Processing Symposium Workshop / IEEE. 2015. P. 1231-1240.

209. van Werkhoven B. Kernel Tuner: A search-optimizing GPU code auto-tuner // Future Generation Computer Systems. 2019. Vol. 90. P. 347-358.

210. Evaluating execution time predictions on GPU kernels using an analytical model and machine learning techniques / Amaris M., Camargo R., Cordeiro D., Goldman A., and Trystram D. // Journal of Parallel and Distributed Computing. 2023. Vol. 171. P. 66-78.

211. Jordan M. I., Mitchell T. M. Machine learning: Trends, perspectives, and prospects // Science. 2015. Vol. 349, N. 6245. P. 255-260.

212. Chandrashekhar B., Sanjay H., Lakshmi H. Prediction Model for Scheduling an Irregular Graph Algorithms on CPU-GPU Hybrid Cluster Framework // 2020 International Conference on Inventive Computation Technologies (ICICT). 2020. P. 584-589.

213. Accel-Sim: An extensible simulation framework for validated GPU modeling / Khairy M., Shen Z., Aamodt T. M., and Rogers T. G. // 2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA) / IEEE. 2020. P. 473-486.

214. PPT-GPU: Scalable gpu performance modeling / Arafa Y.,

Badawy A.-H. A., Chennupati G., Santhi N., and Eidenbenz S. // IEEE Computer Architecture Letters. 2019. Vol. 18, N. 1. P. 55-58.

215. Qadri M. Y., Sangwine S. J. Multicore Technology: Architecture, Reconfiguration, and Modeling. CRC Press, 2013.

216. Eyerman S., Eeckhout L. The Benefit of SMT in the Multi-Core Era: Flexibility towards Degrees of Thread-Level Parallelism // SIGPLAN Not. 2014. Vol. 49, N. 4. P. 591-606.

217. Nestmann M. Building a consistent taxonomy for parallel programming models // INFORMATIK 2017. 2017. P. 2402-2412.

218. Li Y., Zhang Z. Parallel computing: review and perspective // 2018 5th International Conference on Information Science and Control Engineering (ICISCE) / IEEE. 2018. P. 365-369.

219. MapReduce parallel programming model: a state-of-the-art survey / Li R., Hu H., Li H., Wu Y., and Yang J. // International Journal of Parallel Programming. 2016. Vol. 44, N. 4. P. 832-866.

220. A survey and comparative study of hard and soft real-time dynamic resource allocation strategies for multi-/many-core systems / Singh A. K., Dziurzanski P., Mendis H. R., and Indrusiak L. S. // ACM Computing Surveys (CSUR). 2017. Vol. 50, N. 2. P. 1-40.

221. A survey of high-level parallel programming models / Belikov E., Deligiannis P., Totoo P., Aljabri M., and Loidl H.-W. // Heriot-Watt University, Edinburgh, UK. 2013. Vol. 1, N. 2. P. 1-46.

222. Partitioned global address space languages / De Wael M., Marr S.,

De Fraine B., Van Cutsem T., and De Meuter W. // ACM Computing Surveys (CSUR). 2015. Vol. 47, N. 4. P. 1-27.

223. Valiant L. G. A bridging model for parallel computation // Commun. ACM. 1990. Vol. 33. P. 103-111.

224. Skillicorn D. B., Talia D. Models and Languages for Parallel Computation // ACM Comput. Surv. 1998. Vol. 30, N. 2. P. 123-169.

225. LogP: Towards a realistic model of parallel computation / Culler D., Karp R., Patterson D., Sahay A., Schauser K. E., Santos E., Subramonian R., and Von Eicken T. // ACM Sigplan Notices / ACM. 1993. Vol. 28. P. 1-12.

226. Navarro C. A., Hitschfeld-Kahler N., Mateu L. A survey on parallel computing and its applications in data-parallel problems using GPU architectures // Communications in Computational Physics. 2014. Vol. 15, N. 2. P. 285-329.

227. On modelling parallel programmes for static mapping: A comparative study / Koohi S. Z., Hamid N. A. W. A., Othman M., and Ibragimov G. // Pertanika J. Sci. Technol. 2018. Vol. 26, N. 2. P. 523-543.

228. PaRSEC: Exploiting Heterogeneity to Enhance Scalability / Bosilca G., Bouteiller A., Danalis A., Faverge M., Herault T., and Dongarra J. J. // Computing in Science Engineering. 2013. Vol. 15, N. 6. P. 36-45.

229. Raidl G. R. A unified view on hybrid metaheuristics // International workshop on hybrid metaheuristics / Springer. 2006. P. 1-12.

230. Jordan J., Helwig S., Wanka R. Social interaction in particle swarm optimization, the ranked FIPS, and adaptive multi-swarms // GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation. New York, NY, USA : ACM. 2008. P. 49-56. http://doi.acm.org/10.1145/1389095.1389103.

231. Nocedal J., Wright S. Numerical optimization. 2nd ed. New York : Springer Science & Business Media, 2006.

232. De los Reyes J. C. Numerical PDE-constrained optimization. Springer, 2015.

233. Mendes R., Kennedy J., Neves J. The fully informed particle swarm: Simpler, maybe better // IEEE Transactions on Evolutionary Computation. 2004. Vol. 8. P. 204-210.

234. Gross J. L., Yellen J., Anderson M. Graph theory and its applications. Chapman and Hall/CRC, 2018.

235. Ullmann J. R. An algorithm for subgraph isomorphism // Journal of the ACM (JACM). 1976. Vol. 23, N. 1. P. 31-42.

236. Ullmann J. R. Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism // Journal of Experimental Algorithmics (JEA). 2010.

Vol. 15. P. 1-6.

237. Messmer B. T., Bunke H. Subgraph isomorphism in polynomial time. Universität Bern. Institut für Informatik und Angewandte Mathematik, 1995.

238. Messmer B. T., Bunke H. Efficient subgraph isomorphism detection: A decomposition approach // IEEE transactions on knowledge and data engineering. 2000. Vol. 12, N. 2. P. 307-323.

239. Nvidia Ampere GA102 GPU architecture. 2020. https://www.nvidia.com/content/PDF/

nvidia-ampere-ga-102-gpu-architecture-whitepaper-v2.pdf (online; accessed: 2021-09-10).

240. Hu Y., Shi L. Visualizing large graphs // WIREs Computational Statistics. 2015. Vol. 7, N. 2. P. 115-136.

241. Benchmark functions for the CEC 2013 special session and competition on large-scale global optimization : Rep. / Evolutionary Computation and Machine Learning Group ; executor: Li X., Tang K., Omidvar M. N. et al. RMIT University, Melbourne : 2013. P. 1-23.

242. Антух А. Э. Исследование канонического метода роя частиц (PSO) для топологий типа «клика» и «кластер» // Электронное научно-техническое издание «Наука и образование». 2009. № 6. С. 1-14. http://technomag.edu.ru/doc/127975.html.

243. Clerc M. Particle swarm optimization. London : Wiley-ISTE, 2006.

244. Cleghorn C. W., Engelbrecht A. Fully informed particle swarm optimizer: Convergence analysis // 2015 IEEE Congress on Evolutionary Computation (CEC). 2015. P. 164-170.

245. Optimization Using Particle Swarm with Near Neighbor Interactions / Veeramachaneni K., Peram T., Mohan C., and Osadciw L. A. // Lecture Notes Computer Science. Springer Verlag. 2003. P. 110-121.

246. Rezaee Jordehi A., Jasni J. Parameter selection in particle swarm optimisation: a survey // Journal of Experimental & Theoretical Artificial Intelligence. 2013. Vol. 25, N. 4. P. 527-542.

247. Parsopoulos K. E., Vrahatis M. N. UPSO: A unified particle swarm optimization scheme // International Conference of Computational Methods in Sciences and Engineering 2004 (ICCMSE 2004) / CRC Press. 2019.

P. 868-873.

248. Patwal R. S., Narang N., Garg H. A novel TVAC-PSO based mutation strategies algorithm for generation scheduling of pumped storage hydrothermal system incorporating solar units // Energy. 2018. Vol. 142. P. 822-837.

249. Bonyadi M. R., Michalewicz Z. Analysis of Stability, Local Convergence, and Transformation Sensitivity of a Variant of the Particle Swarm Optimization Algorithm // IEEE Transactions on Evolutionary Computation. 2016. Vol. 20, N. 3. P. 370-385.

250. Sengupta S., Basak S., Peters R. A. Particle Swarm Optimization: A survey of historical and recent developments with hybridization perspectives // Machine Learning and Knowledge Extraction. 2018. Vol. 1, N. 1.

P. 157-191.

Приложение

П.1. Тестовые функции и начальные параметры

Тестовые функции для экспериментального тестирования программной системы:

1) функция Экли (Аск1еу) (Рис. П.1)

f (х) = — 20exp ( -0.2

exp

(

.2

En

i=1 Хг

1

n Y^¿=1 cos 2%Xi

+ 20 + e

Начальные значения параметров выбираем случайным образом в диапазоне [-Хтах,Хтах]^ где Xтах = 32,0. Мультимодальная функция с глобальным минимумом /т1П = 0 в 0П. Пороговое значение Ф^п = 32.

Рис. П.1.

Функция Экли

2) функция Химмельблау (Himmelblau) (Рис. П.2)

](х) = (х2 + у - 11)2 + (х + у2 - 7)2 Размер Хтах = 100. Мультимодальная. Пороговое значение Ф^п = 100.

1

Рис. П.2.

Функция Химмельблау

3) функция Растригина (Rastrigin) (Рис. П.3)

f (х) = J2(x* - 10 cos 2пхг + 10)

i=i

Размер Xmax = 6,0. Мультимодальная функция с глобальным минимумом /min = 0,0 в 0п. Пороговое значение Ф^ы = 6.

Рис. П.3.

Функция Растригина

4) функция Розенброка (Rosenbrock) (Рис. П.4)

п—1

f (20 = ^(100(^+1 - X?)? + (Xi - 1)2)

i=1

Размер Xmax = 10. Мультимодальная функция с глобальным минимумом в 0Г /min = 0. Пороговое значение Ф^п = 10.

Рис. П.4.

Функция Розенброка

5) функция Шекеля (Shekel) (Рис. П.5)

f (*) = Е -

1

г=1 + EJ=1 (хз - аji)

Размер Xmax = 100. Мультимодальная функция с пороговым значением Ф^п = 32.

Функция Шекеля

6) функция Сфера (Sphere)

f(x) = XX

i=i

п

Размер Xтах = 100. Унимодальная функция с глобальным минимумом /тш = 0 в 0П. Пороговое значение Ф^п = 100. 7) функция Гриванка (Спешапк)

1 х > о т г / Xi

fix) = 1 + V х22 — TT cos( ) J( ) 4000 4? * (vT+г

г=1 г=1

Размер Xmax = 600. Мультимодальная функция с глобальным минимумом /min = 0 в 0П. Пороговое значение Ф^п = 100. 8) функция Швефеля (Schwefel)

п l i

f(x) = X (^XJ i=1 \j=1

Размер Xmax = 100. Мультимодальная функция с глобальным минимумом /min = 0 в 0П. Пороговое значение Ф^п = 100.