Gerasim@Home — российский проект добровольных распределенных вычислений на платформе BOINC. Проект стартовал в тестовом режиме в феврале 2008 годаBOINCstats | Gerasim@Home — Credit overview. Отличительной особенностью серверной части проекта, разработанной С. Ю. Валяевым, является использование операционной системы 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 года начата новая серия экспериментов, целью которой является апробация применения эвристических методов применительно к решению известных задач теории графов на примере задачи поиска кратчайшего пути в графе и для поиска разбиенийО проекте Gerasim@home — Page 48 — Gerasim@home — Форум Boinc.ru.
В июне 2014 года стартовала серия экспериментов с целью исследования возможности использования случайного перебора с фиксированным числом итераций при построении разбиений.
В феврале 2015 года запущено продолжение серии экспериментов, целью которых является апробация применения эвристических методов применительно к решению задачи поиска кратчайшего пути в графе с использованием возвратной стратегии, а также методов имитации отжига, перебора с ограничением глубины, различных вариаций муравьиного алгоритма, генетического алгоритма и алгоритма пчелиной колонии.
В июне 2016 года запущен вычислительный эксперимент, целью которого является подсчет числа диагональных латинских квадратов порядка 9 ( и ).
В октябре 2016 в проекте был начат эксперимент, направленный на исследование эффективности методов случайных блужданий и роя частиц в задаче поиска кратчайшего пути в графе.
В начале 2017 года в проекте был организован эксперимент, направленный на определение значений ряда комбинаторных характеристик диагональных латинских квадратов и их ортогональных пар (греко-латинских квадратов) порядка 8. В марте 2017 стартовал эксперимент по получению случайных пар ортогональных диагональных латинских квадратов порядка 10 с целью формирования списка их уникальных канонических форм. С 3 по 16 июня 2017 года в проекта осуществлялся подсчет числа симметричных диагональных латинских квадратов порядка 10. 23 октября 2017 года в проекта запущен эксперимент, направленный на анализ симметричных в одной плоскости квадратов при построении пар ортогональных диагональных латинских квадратов.
В декабре 2018 года в проекте был начат эксперимент по изучению эффективности эвристических методов в задаче раскраски графов общего вида.
С 2022 года расчеты, связанные с исследованием свойств диагональных латинских квадратов, перенесены в проект добровольных распределенных вычислений RakeSearch.
Приложение separator
Необходимость в отыскании разбиения, (суб)оптимального по ряду показателей качества, возникает при проектировании систем логического управления, используемых для осуществления логического управления различными дискретными системами (цифровыми схемами, станками с ЧПУ, роботизированными сборочными линиями и т. д.). При проектировании подобных систем возникает ряд комбинаторных многокритериальных оптимизационных задач на дискретных структурах (графах), к которым и относится задача синтеза разбиения заданной граф-схемы алгоритма управленияЗотов И. В., Титов В. С., Колосков В. А. [и др.] Организация и синтез микропрограммных мультимикроконтроллеров. Курск: изд-во «Курск», 1999. 368 с. ISBN 5-7277-0253-4Ватутин Э. И., Зотов И. В., Титов В. С. [и др.] Комбинаторно-логические задачи синтеза разбиений параллельных алгоритмов логического управления при проектировании логических мультиконтроллеров. Курск, изд-во КурскГТУ, 2010. 200 с. ISBN 978-5-7681-0523-5Ватутин Э. И. Проектирование логических мультиконтроллеров. Синтез разбиений параллельных граф-схем алгоритмов. Saarbrucken: Lambert Academic Publishing, 2011 г. 292 с. ISBN 978-3-8433-1728-3, в соответствии с которым должна работать разрабатываемая система логического управления. Отыскание точного решения (глобального оптимума) в большинстве практических случаев невозможно из-за того, что поставленная задача принадлежит к классу NP, поэтому на практике обычно ограничиваются применением эвристических методов, дающих решения неплохого качества за приемлемое время.
Качество найденного решения оценивается как степень минимизации частных показателей качества, к которым относятся: число блоков разбиения — совпадает с числом контроллеров в составе системы логического управления, напрямую влияет на аппаратную сложность системы системы логического управления, её энергопотребление и массогабаритные характеристики; степени дублирования сигналов логических условий и микроопераций — определяют оптимальность распределения вершин граф-схемы алгоритма по блокам разбиения, влияют на число дорожек, связывающих контроллеры на печатной плате или в составе интегральной микросхемы (в зависимости от выбранного способа реализации системы логического управления); сложность сети межблочных связей — определяет необходимое число микрокоманд передачи управления между контроллерами, влияет на глубины некоторых очередей в составе коммуникационной подсистемы контроллера; интенсивность межблочных взаимодействий — определяет среднее число передач управления за время выполнения заданного управляющего алгоритма (межконтроллерный трафик передачи управления), влияет на быстродействие системы управления в целом. Интегральная оценка качества разбиения рассчитывается как взвешенная сумма нормированных значений частных показателей качества.
При практической реализации системы логического управления приходится учитывать ограничения технологического характера, к которым в первую очередь относятся: число ножек на корпусе микросхемы для приема сигналов логических условий и выдачи сигналов микроопераций ; объём памяти микрокоманд в составе контроллера. Ограничение не является критическим и может быть исключено из рассмотрения путём дублирования контроллеров, имеющих одинаковые входы и выполняющих однотипные микропрограммы. С целью упрощения внутренней структуры контроллера накладывается дополнительное структурное ограничение на невозможность размещения параллельных вершин в составе одного блока разбиения (контроллера).
В качестве эвристических методов поиска разбиений в вычислительных экспериментах принимали участие: метод С. И. БарановаБаранов С. И., Журавина Л. Н., Песчанский В. А. Метод представления параллельных граф-схем алгоритмов совокупностями последовательных граф-схем // Автоматика и вычислительная техника. 1984. № 5. С. 74—81. и его модификации — используют жадную стратегию последовательного формирования блоков разбиения; метод параллельно-последовательной декомпозицииЗотов И. В., Колосков В. А., Титов В. С. Выбор оптимальных разбиений алгоритмов при проектировании микроконтроллерных сетей // Автоматика и вычислительная техника. 1997. № 5. С. 51—62. — использует ряд эквивалентных преобразований (разрыв циклов, объединение линейных участков граф-схемы алгоритма, классификация отношений между вершинами граф-схемы, построение множества сечений граф-схемы, построение блоков разбиения на основании анализа таблиц включений); метод случайного перебора с заданным числом итераций.
Методы характеризуются существенно различной трудоемкостью реализации, временной и емкостной сложностью алгоритмов преобразований и качеством получаемых решений при различных значениях технологических ограничений. При проведении сравнения качества методов необходимо исследование различных областей пространства параметров , где — число вершин в составе граф-схем алгоритмов, что является вычислительно сложной задачей. В процессе расчетов были проанализированы отдельные срезы пространства параметров, на основании чего было выявлено существенно различное поведение методов синтеза разбиений по мере усиления или ослабления значений технологических ограничений.
Для каждой точки выбранного среза пространства параметров осуществляется построение выборки параллельных алгоритмов логического управления с псевдослучайной структурой, построение их разбиений указанным методом и оценка качества, что требует от нескольких минут (малые значения ) до нескольких часов (большие значения ) вычислительного времени. Полученные выборки числовых значений объёмом около 200 КБ каждая передаются на сервер проекта и ожидают последующей обработки. Общий объём полученных данных (без учёта избыточности) составил 235 ГБ, а вычислительные затраты — 51,6 экзафлоп (818 ГГц-лет). По сравнению с реализацией на двухъядерном процессоре Core 2 Duo с частотой 1,86 ГГц выигрыш во времени, полученный за счет параллельной обработки с использованием грид, составил 155 раз. Постобработка полученных результатов заняла около суток вычислительного времени и заключалась в расчете средних значений параметров качества и вероятностей получения разбиения с минимальным значением выбранного показателя качества, в результате чего были получены искомые двумерные карты общим объёмом 96 МБ, которые можно использовать для подробного анализа поведения методов в различных областях пространства параметров.
Приложение spstarter В марте 2014 года стартовала очередная серия вычислительных экспериментов, отличительной особенностью которой является поддержка одновременного выполнения нескольких экспериментов. С целью тестирования методов решения дискретных оптимизационных задач был реализован соответствующий расчетный модуль, статически подключаемый к приложению spstarter.exe. Помимо приложения separator, вошедшего в состав нового расчетного модуля, реализована возможность анализа качества решений тестовой задачи нахождения кратчайшего пути в графе с использованием ряда подходов (алгоритм Дейкстры, жадный алгоритм, случайный перебор, взвешенный случайный перебор, их модификации с поддержкой комбинаторных возвратов, вариации алгоритма муравьиной колонии, метод имитации отжига, перебор с ограничением глубины или числа рассматриваемых ветвей дерева, генетический алгоритм, алгоритм пчелиной колонии, метод случайных блужданий и вариации метода роя частиц) с целью выявления их сильных и слабых сторон. Наилучшие результаты были в рассматриваемой задаче были продемонстрированы методом муравьиной колонии и генетическим алгоритмомVatutin E.I. Comparison of Decisions Quality of Heuristic Methods with Limited Depth-First Search Techniques in the Graph Shortest Path Problem // Open Engineering. Vol. 7. Iss. 1. 2017. pp. 428—434. DOI: 10.1515/eng-2017-0041.,.
Определение асимптотического поведения комбинаторных характеристик комбинаторных структур на базе диагональных латинских квадратов