Gerasim@Home

Gerasim@Home — российский проект добровольных распределенных вычислений на платформе BOINC. Проект стартовал в тестовом режиме в феврале 2008 года. Отличительной особенностью серверной части проекта, разработанной С. Ю. Валяевым, является использование операционной системы Windows Server 2008 и связки Microsoft SQL Server с ASP.NET, в то время как стандартный набор приложений от разработчиков BOINC требует использования операционной системы Linux или Unix. По состоянию на 23 июля 2015 года в проекте приняли участие 1999 пользователей (890 компьютеров) из 62 стран, обеспечивая производительность 1—5 терафлопс. Участвовать в проекте может любой желающий, обладающий компьютером с выходом в Интернет, установив на него программу BOINC Manager.

История проекта

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

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

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

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

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

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

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

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

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

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

Приложение separator

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

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

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

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

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

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

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

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

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

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

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

Приложение spstarter

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

Определение асимптотического поведения комбинаторных характеристик комбинаторных структур на базе диагональных латинских квадратов

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

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

Кроме определения комбинаторных характеристик, в проекте производится поиск и коллекционирование канонических форм ортогональных диагональных латинских квадратов порядка 10 с целью классификации образуемых ими комбинаторных структур (графов на множестве бинарного отношения ортогональности) и попыткой отыскания тройки попарно-ортогональных диагональных латинских квадратов, что является открытой математической проблемой. Наиболее эффективно поиск ортогональных квадратов общего вида осуществляется с использованием трансверсалей путем сведения исходной задачи к задаче о точном покрытии с последующем ее решением с использованием алгоритма танцующих связей в рамках метода Эйлера-Паркера. По состоянию на июль 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);
• произведен подсчет числа центрально симметричных диагональных латинских квадратов порядка N<10 (последовательность A293777 в OEIS и последовательность A293778 в OEIS);
• произведено определение минимального и максимального числа трансверсалей в диагональных латинских квадратах порядка 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);
• произведена классификация комбинаторных структур, возникающих из диагональных латинских квадратов порядка 1—10 на множестве бинарного отношения ортогональности;
• показано, что рекордная характеристика ортогональности 274 для псевдотройки попарно-ортогональных диагональных латинских квадратов порядка 10, найденная в ходе анализа плоскостной симметрии в ДЛК, не может быть улучшена как в данном классе симметрий, так и в классе чистых обобщенных симметрий и их окрестностей.