Gerasim@Home

Проект стартовал в тестовом режиме в феврале 2008 года[1], используя в качестве тестового расчетного модуля программу gsm для поиска простых чисел.

В июне 2010 года на кафедре вычислительной техники Юго-Западного государственного университета было разработано расчетное приложение separator, целью которого является построение разбиений параллельных граф-схем алгоритмов логического управления, получаемых различными эвристическими методами, с целью сравнения качества получаемых решений и выработки рекомендаций о границах целесообразности применения методов. Первая часть расчетов была завершена в сентябре 2011 г.

В январе 2013 года был начат эксперимент[2] по исследованию возможностей применения жадной стратегии синтеза разбиения с ограничением на выбор вершин из смежной окрестности текущего блока[3].

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

В июне 2014 года стартовала серия экспериментов с целью исследования возможности использования случайного перебора[5][6] с фиксированным числом итераций при построении разбиений.

В феврале 2015 года запущено продолжение серии экспериментов, целью которых является апробация применения эвристических методов применительно к решению задачи поиска кратчайшего пути в графе с использованием возвратной стратегии[7], а также методов имитации отжига[8], перебора с ограничением глубины[9][10], различных вариаций муравьиного алгоритма[11][12], генетического алгоритма[13] и алгоритма пчелиной колонии[14].

В июне 2016 года запущен вычислительный эксперимент, целью которого является подсчет числа диагональных латинских квадратов порядка 9 (последовательность A274171 в OEIS и последовательность A274806 в OEIS)[15].

В октябре 2016 в проекте был начат эксперимент, направленный на исследование эффективности методов случайных блужданий[16] и роя частиц[17][18] в задаче поиска кратчайшего пути в графе.

Первая пара ортогональных диагональных латинских квадратов порядка 10, найденная в проекте

В начале 2017 года в проекте был организован эксперимент, направленный на определение значений ряда комбинаторных характеристик диагональных латинских квадратов и их ортогональных пар (греко-латинских квадратов) порядка 8[19]. В марте 2017 стартовал эксперимент по получению случайных пар ортогональных диагональных латинских квадратов порядка 10 с целью формирования списка их уникальных канонических форм[20]. С 3 по 16 июня 2017 года в проекта осуществлялся подсчет числа симметричных диагональных латинских квадратов порядка 10[21]. 23 октября 2017 года в проекта запущен эксперимент, направленный на анализ симметричных в одной плоскости квадратов при построении пар ортогональных диагональных латинских квадратов[22][23].

В декабре 2018 года в проекте был начат эксперимент по изучению эффективности эвристических методов в задаче раскраски графов общего вида[24].

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

Необходимость в отыскании разбиения, (суб)оптимального по ряду показателей качества, возникает при проектировании систем логического управления, используемых для осуществления логического управления различными дискретными системами (цифровыми схемами, станками с ЧПУ, роботизированными сборочными линиями и т. д.). При проектировании подобных систем возникает ряд комбинаторных многокритериальных оптимизационных задач на дискретных структурах (графах), к которым и относится задача синтеза разбиения заданной граф-схемы алгоритма управления[25][26][27], в соответствии с которым должна работать разрабатываемая система логического управления. Отыскание точного решения (глобального оптимума) в большинстве практических случаев невозможно из-за того, что поставленная задача принадлежит к классу NP, поэтому на практике обычно ограничиваются применением эвристических методов, дающих решения неплохого качества за приемлемое время.

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

• число блоков разбиения ${\displaystyle H}$ — совпадает с числом контроллеров в составе системы логического управления, напрямую влияет на аппаратную сложность системы системы логического управления, её энергопотребление и массогабаритные характеристики;
• степени дублирования сигналов логических условий ${\displaystyle \gamma _{X}}$ и микроопераций ${\displaystyle \gamma _{Y}}$ — определяют оптимальность распределения вершин граф-схемы алгоритма по блокам разбиения, влияют на число дорожек, связывающих контроллеры на печатной плате или в составе интегральной микросхемы (в зависимости от выбранного способа реализации системы логического управления);
• сложность сети межблочных связей ${\displaystyle \alpha }$ — определяет необходимое число микрокоманд передачи управления между контроллерами, влияет на глубины некоторых очередей в составе коммуникационной подсистемы контроллера;
• интенсивность межблочных взаимодействий ${\displaystyle \delta }$ — определяет среднее число передач управления за время выполнения заданного управляющего алгоритма (межконтроллерный трафик передачи управления), влияет на быстродействие системы управления в целом.

Интегральная оценка качества разбиения ${\displaystyle J}$ рассчитывается как взвешенная сумма нормированных значений частных показателей качества.

При практической реализации системы логического управления приходится учитывать ограничения технологического характера, к которым в первую очередь относятся:

• число ножек на корпусе микросхемы для приема сигналов логических условий ${\displaystyle X_{max}}$ и выдачи сигналов микроопераций ${\displaystyle Y_{max}}$;
• объём памяти микрокоманд ${\displaystyle W_{max}}$ в составе контроллера.

Ограничение ${\displaystyle Y_{max}}$ не является критическим и может быть исключено из рассмотрения путём дублирования контроллеров, имеющих одинаковые входы и выпоняющих однотипные микропрограммы. С целью упрощения внутренней структуры контроллера накладывается дополнительное структурное ограничение на невозможность размещения параллельных вершин в составе одного блока разбиения (контроллера).

В качестве эвристических методов поиска разбиений в вычислительных экспериментах принимали участие:

• метод С. И. Баранова[28] и его модификации[3] — используют жадную стратегию последовательного формирования блоков разбиения;
• метод параллельно-последовательной декомпозиции[29][30] — использует ряд эквивалентных преобразований (разрыв циклов, объединение линейных участков граф-схемы алгоритма, классификация отношений между вершинами граф-схемы, построение множества сечений граф-схемы, построение блоков разбиения на основании анализа таблиц включений);
• метод случайного перебора[5][6] с заданным числом итераций.

Исследуемое пространство параметров и номера вычислительных экспериментов

Методы характеризуются существенно различной трудоемкостью реализации, временной и емкостной сложностью алгоритмов преобразований и качеством получаемых решений при различных значениях технологических ограничений. При проведении сравнения качества методов необходимо исследование различных областей пространства параметров ${\displaystyle \left(X_{max},W_{max},N\right)}$, где ${\displaystyle N}$ — число вершин в составе граф-схем алгоритмов, что является вычислительно сложной задачей. В процессе расчетов были проанализированы отдельные срезы пространства параметров, на основании чего было выявлено существенно различное поведение методов синтеза разбиений по мере усиления или ослабления значений технологических ограничений.

Средние значения показателей качества при различных значениях координат пространства параметров, полученные в одном из экспериментов

Вероятности получения минимального значения выбранного показателя качества методом С. И. Баранова при различных значениях координат пространства параметров, полученные в одном из экспериментов

Карты предпочтительного использования последовательных эвристических методов при синтезе разбиений в плоскости параметров ${\displaystyle (X_{max};N)}$

Для каждой точки выбранного среза пространства параметров осуществляется построение выборки параллельных алгоритмов логического управления с псевдослучайной структурой, построение их разбиений указанным методом и оценка качества, что требует от нескольких минут (малые значения ${\displaystyle N}$) до нескольких часов (большие значения ${\displaystyle N}$) вычислительного времени. Полученные выборки числовых значений объёмом около 200 КБ каждая передаются на сервер проекта и ожидают последующей обработки. Общий объём полученных данных (без учета избыточности) составил 235 ГБ, а вычислительные затраты — 51,6 экзафлоп (818 ГГц-лет). По сравнению с реализацией на двухъядерном процессоре Core 2 Duo с частотой 1,86 ГГц выигрыш во времени, полученный за счет параллельной обработки с использованием грид, составил 155 раз. Постобработка полученных результатов[31][32] заняла около суток вычислительного времени и заключалась в расчете средних значений параметров качества ${\displaystyle \gamma _{x}}$ и вероятностей ${\displaystyle \rho _{x}}$ получения разбиения с минимальным значением выбранного показателя качества, в результате чего были получены искомые двумерные карты общим объёмом 96 МБ, которые можно использовать для подробного анализа поведения методов в различных областях пространства параметров.

В марте 2014 года стартовала[4] очередная серия вычислительных экспериментов, отличительной особенностью которой является поддержка одновременного выполнения нескольких экспериментов. С целью тестирования методов решения дискретных оптимизационных задач был реализован соответствующий расчетный модуль, статически подключаемый к приложению spstarter.exe. Помимо приложения separator, вошедшего в состав нового расчетного модуля, реализована возможность анализа качества решений тестовой задачи нахождения кратчайшего пути в графе с использованием ряда подходов (алгоритм Дейкстры, жадный алгоритм, случайный перебор, взвешенный случайный перебор[33], их модификации с поддержкой комбинаторных возвратов[7], вариации алгоритма муравьиной колонии[11][12], метод имитации отжига, перебор с ограничением глубины или числа рассматриваемых ветвей дерева, генетический алгоритм[13], алгоритм пчелиной колонии[14], метод случайных блужданий и вариации метода роя частиц) с целью выявления их сильных и слабых сторон. Наилучшие результаты были в рассматриваемой задаче были продемонстрированы методом муравьиной колонии и генетическим алгоритмом[34][35], [36].

Асимптотическое поведение числа диагональных латинских квадратов (ДЛК) с ростом их размерности N до выполненных в проекте расчетов было неизвестно. В результате разработки высокоэффективного расчетного модуля, который использует ряд приемов алгоритмической и высокоуровневой оптимизации[37][38][39][40][41][42], удалось достичь темпа генерации в 6,6 млн. ДЛК/с, что позволило определить число ДЛК до N<10 (последовательность A274171 в OEIS и последовательность A274806 в OEIS). Для этого потребовалось 3 месяца расчетов на грид с реальной производительностью 2—5 TFLOP/s[43] и 3 месяца расчетов на вычислительном кластере «Академик В.М. Матросов» СО РАН с целью проверки и подтверждения полученного результата[44].

С использованием аналогичных алгоритмических принципов был осуществлен подсчет числа симметричных диагональных латинских квадратов порядка N<11[21] и определение минимального и максимального числа трансверсалей в диагональных латинских квадратах порядка N<9[45][46][47].

Кроме определения комбинаторных характеристик, в проекте производится поиск и коллекционирование канонических форм ортогональных диагональных латинских квадратов порядка 10 с целью классификации образуемых ими комбинаторных структур (графов на множестве бинарного отношения ортогональности)[48] и попыткой отыскания тройки попарно-ортогональных диагональных латинских квадратов, что является открытой математической проблемой. Наиболее эффективно поиск ортогональных квадратов общего вида осуществляется с использованием трансверсалей путем сведения исходной задачи к задаче о точном покрытии с последующем ее решением с использованием алгоритма танцующих связей в рамках метода Эйлера-Паркера[49][50]. По состоянию на июль 2020 г. коллекция включает более 10 млн. канонических форм ОДЛК порядка 10, найденных в проекте.

• получены границы областей применимости методов синтеза разбиений: область слабых ограничений для метода С. И. Баранова, область сильных ограничений для метода параллельно-последовательной декомпозиции (качественное преимущество);
• получены отношения степени оптимизации каждого из выбранных показателей качества к известному для него условному оптимуму, для каждого из методов показан проигрыш в процентах (количественное превосходство);
• получены границы областей нечувствительности, в которых ослабление ограничений не влияет на повышение качества решений, область нечувствительности имеет различную ширину для различных эвристических методов;
• сформулированы рекомендации для разработчиков аппаратной части мультиконтроллеров, структура логического мультиконтроллера с большим числом простых контроллеров является предпочтительной; показана диктуемая практикой необходимость работы в области сильных ограничений;
• произведен подсчет числа диагональных латинских квадратов порядка N<10 (последовательность A274171 в OEIS и последовательность A274806 в OEIS);
• произведен подсчет числа горизонтально симметричных диагональных латинских квадратов порядка N<11 (последовательность A287649 в OEIS и последовательность A292516 в OEIS);
• произведен подсчет числа дважды симметричных диагональных латинских квадратов порядка N<10 (последовательность A287650 в OEIS и последовательность A292517 в OEIS);
• произведен подсчет числа симметричных в одной плоскости диагональных латинских квадратов порядка N<9 (последовательность A296060 в OEIS и последовательность A296061 в OEIS);
• произведен подсчет числа редуцированных (первая строка квадратов упорядочена, например, по возрастанию) пар ортогональных диагональных латинских квадратов порядка N<8 (последовательность A287651 в OEIS);
• произведен подсчет максимально возможного числа диагональных латинских квадратов, ортогональных одному диагональному латинскому квадрату порядка N<9 (последовательность A287695 в OEIS);
• произведен подсчет числа и анализ свойств главных классов диагональных латинских квадратов порядка N<9 (последовательность A287764 в OEIS, последовательность A299783 в OEIS, последовательность A299784 в OEIS, последовательность A299785 в OEIS и последовательность A299787 в OEIS)[51][52];
• произведен подсчет числа центрально симметричных диагональных латинских квадратов порядка N<10 (последовательность A293777 в OEIS и последовательность A293778 в OEIS)[53][54];
• произведено определение минимального и максимального числа трансверсалей в диагональных латинских квадратах порядка N<9 (последовательность A287644 в OEIS, последовательность A287645 в OEIS, последовательность A287647 в OEIS и последовательность A287648 в OEIS);
• произведен подсчет числа пандиагональных латинских квадратов порядка N с фиксированной первой строкой (последовательность A123565 в OEIS);
• произведен подсчет числа ортогональных (ODLS), самоортогональных (SODLS), дважды самоортогональных (DSODLS) и расширенных самоортогональных (ESODLS) диагональных латинских квадратов порядка 1—10, а также нормализованных квадратов для того же типа ортогональности и их главных классов (последовательность A330391 в OEIS}, последовательность A329685 в OEIS, последовательность A333366 в OEIS, последовательность A309210 в OEIS)[55];
• произведена классификация комбинаторных структур, возникающих из диагональных латинских квадратов порядка 1—10 на множестве бинарного отношения ортогональности[56][57][48];
• показано, что рекордная характеристика ортогональности 274[58] для псевдотройки попарно-ортогональных диагональных латинских квадратов порядка 10, найденная в ходе анализа плоскостной симметрии в ДЛК, не может быть улучшена как в данном классе симметрий, так и в классе чистых обобщенных симметрий и их окрестностей.

Комбинаторные структуры из диагональных латинских квадратов порядка 10 на множестве бинарного отношения ортогональности: a — "пустышка" (ДЛК без ОДЛК), b — пара ОДЛК (1:1), c — линия-3 ("двушка", 1:2), d — "трешка" (1:3), e — четверка (1:4), f — пятерка (1:5), g — шестерка (1:6), h — семерка (1:7), i — восьмерка (1:8), j — ромб-3, k — ромб-4, l — цикл-4, m — "рыба", n — линия-4, o — линия-5, p — летательный аппарат, q — Дедал-10, r — крест, s — дерево, t — Дедал-8, u — Венера, v — ромб-5, w — десятка (1:10), x — робот, y — скат

Псевдотройка попарно-ортогональных диагональных латинских квадратов порядка 10 с рекордной характеристикой ортогональности 274. Образующий ее квадрат B является строчно-инверсным и горизонтально-симметричным.

• Официальный сайт проекта
• Твиттер проекта
• Ватутин Э. И., Титов В. С. Сравнение методов синтеза разбиений параллельных алгоритмов логического управления с использованием двухпараметрических диаграмм // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание — 2012). Курск: изд-во ЮЗГУ, 2012. С. 138—140.
• Ватутин Э. И., Титов В. С. Сравнение методов синтеза разбиений граф-схем параллельных алгоритмов с использованием двумерных диаграмм // Известия ЮЗГУ. № 3 (42). Курск: изд-во ЮЗГУ, 2012. С. 66—74.
• Пленарный доклад «Использование грид-вычислений на платформе BOINC для построения разбиений параллельных алгоритмов логического управления» (Курск, 2012) на YouTube
• Ватутин Э. И., Титов В. С. Использование добровольных распределенных вычислений на платформе BOINC для анализа качества разбиений граф-схем параллельных алгоритмов // Параллельные вычисления и задачи управления (PACO’12). М.: ИПУ РАН, 2012.
• Ватутин Э. И., Титов В. С. Структурно-параметрическая оптимизация систем логического управления с использованием добровольных распределенных вычислений // Известия ЮЗГУ. Серия «Управление, вычислительная техника, информатика. Медицинское приборостроение». № 2. Ч. 1. С. 12-17. ISSN 2223—1536.
• Ватутин Э.И. Сравнение эвристических методов синтеза разбиений граф-схем параллельных алгоритмов с использованием добровольных распределенных вычислений на платформе BOINC // BOINC:FAST'13. Петрозаводск, 2013. на YouTube
• Научно-популярное описание задачи построения разбиений
• Ватутин Э. И., Валяев С. Ю. Расчетный модуль для построения разбиений параллельных алгоритмов логического управления с использованием добровольных распределенных вычислений // Свидетельство о государственной регистрации программы для ЭВМ № 2013618013 от 28.08.13.
• Vatutin E.I., Titov V.S. Voluntary distributed computing for solving discrete combinatorial optimization problems using Gerasim@home project // Distributed computing and grid-technologies in science and education: book of abstracts of the 6th international conference. Dubna: JINR, 2014. PP. 60-61. ISBN 978-5-9530-0387-2.
• Ватутин Э. И., Валяев С. Ю., Дремов Е. Н., Мартынов И. А., Титов В. С. Расчетный модуль для тестирования комбинаторных оптимизационных алгоритмов в задаче поиска кратчайшего пути в графе с использованием добровольных распределенных вычислений // Свидетельство о государственной регистрации программы для ЭВМ № 2014619797 от 22.09.14.
• Ватутин Э. И., Титов В. С. Анализ областей качественного превосходства последовательных эвристических методов синтеза разбиений при проектировании логических мультиконтроллеров // Известия высших учебных заведений. Приборостроение. 2015. Т. 58. № 2. С. 115—122. DOI: 10.17586/0021-3454-2015-58-2-115-122.
• Результаты вычислительных экспериментов в графическом виде
• Пленарный доклад «Решение задач дискретной комбинаторной оптимизации с использованием грид-систем на добровольной основе» (Курск, 2015) на YouTube
• Vatutin E.I., Valyaev S.Yu., Titov V.S. Comparison of Sequential Methods for Getting Separations of Parallel Logic Control Algorithms Using Volunteer Computing // CEUR Workshop Proceedings. Proceedings of the Second International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC:FAST 2015). Vol. 1502. Technical University of Aachen, Germany, 2015. P. 37-51. urn: nbn: de:0074-1502-3.
• Ватутин Э. И., Валяев С. Ю., Титов В. С. Анализ результатов применения метода случайного перебора при построении разбиений граф-схем параллельных алгоритмов в зависимости от размерности задачи и силы ограничений // Перспективные информационные технологии (ПИТ 2016). Самара: изд-во Самарского научного центра РАН, 2016. С. 481—486.
• Подсчет числа диагональных латинских квадратов с использованием добровольных распределенных вычислений
• Результаты проекта в графической форме (по состоянию на август 2017)
• Перечень различных комбинаторных структур из ДЛК порядка 1-8
• Перечень различных комбинаторных структур из ДЛК порядка 10, найденных в проекте
• Ватутин Э.И., Кочемазов С.Е., Заикин О.С., Цитерров И.И. Оценка вероятности нахождения ортогональных диагональных латинских квадратов среди диагональных латинских квадратов общего вида // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание – 2018). Курск: изд-во ЮЗГУ, 2018. С. 72–74.

Обсуждение проекта в форумах:

• boinc.ru
• distributed.org.ua

• BOINC
• Добровольные вычисления
• Разбиение графа
• Граф-схема алгоритма
• Комбинаторная оптимизация
• Латинский квадрат
• Греко-латинский квадрат
• OEIS