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

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

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

Приложение separator

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

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

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

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

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

• число ножек на корпусе микросхемы для приема сигналов логических условий и выдачи сигналов микроопераций ;
• объем памяти микрокоманд в составе контроллера.

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

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

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

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

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

Научные достижения

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

Примечания