Gerasim@Home

Gerasim@Home
Платформа	BOINC
Объём загружаемого ПО	2 МБ
Объём загружаемых данных задания	1 КБ
Объём отправляемых данных задания	150 КБ
Объём места на диске	2 МБ
Используемый объём памяти	10 МБ
Графический интерфейс	нет
Среднее время расчёта задания	до 6 часов
Deadline	10 дней
Возможность использования GPU	нет

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 года^[1], используя в качестве тестового расчетного модуля программу gsm для поиска простых чисел. В июне 2010 года на кафедре вычислительной техники Юго-Западного государственного университета было разработано расчетное приложение separator, целью которого является построение разбиений параллельных граф-схем алгоритмов логического управления, получаемых различными эвристическими методами, с целью сравнения качества получаемых решений и выработки рекомендаций о границах целесообразности применения методов. Основная часть расчетов была завершена в сентябре 2011 г.

Приложение separator

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

1. ↑ ^{1 2} BOINCstats | Gerasim@Home — Credit overview
2. ↑ Зотов И. В., Титов В. С., Колосков В. А. [и др.] Организация и синтез микропрограммных мультимикроконтроллеров. Курск: изд-во «Курск», 1999. 368 с. ISBN 5-7277-0253-4
3. ↑ Ватутин Э. И., Зотов И. В., Титов В. С. [и др.] Комбинаторно-логические задачи синтеза разбиений параллельных алгоритмов логического управлени при проектировании логических мультиконтроллеров. Курск, изд-во КурскГТУ, 2010. 200 с. ISBN 978-5-7681-0523-5
4. ↑ Ватутин Э. И. Проектирование логических мультиконтроллеров. Синтез разбиений параллельных граф-схем алгоритмов. Saarbrucken: Lambert Academic Publishing, 2011 г. 292 с. ISBN 978-3-8433-1728-3
5. ↑ Баранов С. И., Журавина Л. Н., Песчанский В. А. Метод представления параллельных граф-схем алгоритмов совокупностями последовательных граф-схем // Автоматика и вычислительная техника. 1984. № 5. С. 74—81.
6. ↑ Зотов И. В., Колосков В. А., Титов В. С. Выбор оптимальных разбиений алгоритмов при проектировании микроконтроллерных сетей // Автоматика и вычислительная техника. 1997. № 5. С. 51—62.
7. ↑ Ватутин Э. И., Зотов И. В. Метод формирования субоптимальных разбиений параллельных управляющих алгоритмов // Параллельные вычисления и задачи управления (PACO’04). М.: ИПУ РАН, 2004. С. 884—917.

Ссылки

• Официальный сайт проекта
• Ватутин Э. И., Титов В. С. Сравнение методов синтеза разбиений параллельных алгоритмов логического управления с использованием двухпараметрических диаграмм // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание — 2012). Курск: изд-во ЮЗГУ, 2012. С. 138—140.
• Ватутин Э. И., Титов В. С. Сравнение методов синтеза разбиений граф-схем параллельных алгоритмов с использованием двумерных диаграмм // Известия ЮЗГУ. № 3 (42). Курск: изд-во ЮЗГУ, 2012. С. 66—74.
• Пленарный доклад «Использование грид-вычислений на платформе BOINC для построения разбиений параллельных алгоритмов логического управления» (Курск, 2012) на YouTube
• Ватутин Э. И., Титов В. С. Использование добровольных распределенных вычислений на платформе BOINC для анализа качества разбиений граф-схем параллельных алгоритмов // Параллельные вычисления и задачи управления (PACO’12). М.: ИПУ РАН, 2012.
• Ватутин Э.И., Титов В.С. Структурно-параметрическая оптимизация систем логического управления с использованием добровольных распределенных вычислений // Известия ЮЗГУ. Серия «Управление, вычислительная техника, информатика. Медицинское приборостроение». № 2. Ч. 1. С. 12–17. ISSN 2223-1536.

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

• boinc.ru
• distributed.org.ua

См. также

• BOINC
• Добровольные вычисления
• Разбиение графа
• Граф-схема алгоритма