Русская Википедия:Gerasim@Home

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Много внутренних ссылок Шаблон:Карточка программы для добровольных вычислений

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

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

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

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

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

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

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

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

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

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

Файл:Gerasim@Home First ODLS 10.png
Первая пара ортогональных диагональных латинских квадратов порядка 10, найденная в проекте

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

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

С 2022 года расчеты, связанные с исследованием свойств диагональных латинских квадратов, перенесены в проект добровольных распределенных вычислений RakeSearch[25].

Приложение separator

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

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

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

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

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

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

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

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

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

  • метод С. И. Баранова[29] и его модификации[3] — используют жадную стратегию последовательного формирования блоков разбиения;
  • метод параллельно-последовательной декомпозиции[30][31] — использует ряд эквивалентных преобразований (разрыв циклов, объединение линейных участков граф-схемы алгоритма, классификация отношений между вершинами граф-схемы, построение множества сечений граф-схемы, построение блоков разбиения на основании анализа таблиц включений);
  • Шаблон:Нп1[5][6] с заданным числом итераций.
Файл:Gerasim@home params space.png
Исследуемое пространство параметров и номера вычислительных экспериментов

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

Файл:Gerasim@home ll exp4 b gamma.png
Средние значения показателей качества при различных значениях координат пространства параметров, полученные в одном из экспериментов
Файл:Gerasim@home ll exp4 b rho.png
Вероятности получения минимального значения выбранного показателя качества методом С. И. Баранова при различных значениях координат пространства параметров, полученные в одном из экспериментов
Файл:Gerasim@home pm.png
Карты предпочтительного использования последовательных эвристических методов при синтезе разбиений в плоскости параметров <math>(X_{max}; N)</math>

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

Приложение spstarter

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

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

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

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

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

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

  • получены границы областей применимости методов синтеза разбиений: область слабых ограничений для метода С. И. Баранова, область сильных ограничений для метода параллельно-последовательной декомпозиции (качественное преимущество);
  • получены отношения степени оптимизации каждого из выбранных показателей качества к известному для него условному оптимуму, для каждого из методов показан проигрыш в процентах (количественное превосходство);
  • получены границы областей нечувствительности, в которых ослабление ограничений не влияет на повышение качества решений, область нечувствительности имеет различную ширину для различных эвристических методов;
  • сформулированы рекомендации для разработчиков аппаратной части мультиконтроллеров, структура логического мультиконтроллера с большим числом простых контроллеров является предпочтительной; показана диктуемая практикой необходимость работы в области сильных ограничений;
  • произведен подсчет числа диагональных латинских квадратов порядка N<10 (Шаблон:OEIS и Шаблон:OEIS);
  • произведен подсчет числа горизонтально симметричных диагональных латинских квадратов порядка N<11 (Шаблон:OEIS и Шаблон:OEIS);
  • произведен подсчет числа дважды симметричных диагональных латинских квадратов порядка N<10 (Шаблон:OEIS и Шаблон:OEIS);
  • произведен подсчет числа симметричных в одной плоскости диагональных латинских квадратов порядка N<9 (Шаблон:OEIS и Шаблон:OEIS);
  • произведен подсчет числа редуцированных (первая строка квадратов упорядочена, например, по возрастанию) пар ортогональных диагональных латинских квадратов порядка N<8 (Шаблон:OEIS);
  • произведен подсчет максимально возможного числа диагональных латинских квадратов, ортогональных одному диагональному латинскому квадрату порядка N<9 (Шаблон:OEIS);
  • произведен подсчет числа и анализ свойств главных классов диагональных латинских квадратов порядка N<9 (Шаблон:OEIS, Шаблон:OEIS, Шаблон:OEIS, Шаблон:OEIS и Шаблон:OEIS)[52][53];
  • произведен подсчет числа центрально симметричных диагональных латинских квадратов порядка N<10 (Шаблон:OEIS и Шаблон:OEIS)[54][55];
  • произведено определение минимального и максимального числа трансверсалей в диагональных латинских квадратах порядка N<9 (Шаблон:OEIS, Шаблон:OEIS, Шаблон:OEIS и Шаблон:OEIS);
  • произведен подсчет числа пандиагональных латинских квадратов порядка N с фиксированной первой строкой (Шаблон:OEIS);
  • произведен подсчет числа ортогональных (ODLS), самоортогональных (SODLS), дважды самоортогональных (DSODLS) и расширенных самоортогональных (ESODLS) диагональных латинских квадратов порядка 1—10, а также нормализованных квадратов для того же типа ортогональности и их главных классов (Шаблон:OEIS}, Шаблон:OEIS, Шаблон:OEIS, Шаблон:OEIS)[56];
  • произведена классификация комбинаторных структур, возникающих из диагональных латинских квадратов порядка 1—10 на множестве бинарного отношения ортогональности[57][58][49];
  • показано, что рекордная характеристика ортогональности 274[59] для псевдотройки попарно-ортогональных диагональных латинских квадратов порядка 10, найденная в ходе анализа плоскостной симметрии в ДЛК, не может быть улучшена как в данном классе симметрий, так и в классе чистых обобщенных симметрий и их окрестностей.
Файл:ODLS10-comb-structs.png
Комбинаторные структуры из диагональных латинских квадратов порядка 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 — скат
Файл:Dls10 oc274 record.png
Псевдотройка попарно-ортогональных диагональных латинских квадратов порядка 10 с рекордной характеристикой ортогональности 274. Образующий ее квадрат B является строчно-инверсным и горизонтально-симметричным.

Примечания

Шаблон:Примечания

Ссылки

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

См. также

Шаблон:Добровольные вычисления

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ 1,0 1,1 BOINCstats | Gerasim@Home — Credit overviewШаблон:Недоступная ссылка
  2. ↑ Шаблон:Cite web
  3. ↑ 3,0 3,1 Шаблон:Cite web
  4. ↑ 4,0 4,1 О проекте Gerasim@home — Page 48 — Gerasim@home — Форум Boinc.ruШаблон:Недоступная ссылка
  5. ↑ 5,0 5,1 Шаблон:Cite web
  6. ↑ 6,0 6,1 Шаблон:Cite web
  7. ↑ 7,0 7,1 Шаблон:Cite web
  8. ↑ Шаблон:Cite web
  9. ↑ Шаблон:Cite web
  10. ↑ Шаблон:Cite web
  11. ↑ 11,0 11,1 Шаблон:Cite web
  12. ↑ 12,0 12,1 Шаблон:Cite web
  13. ↑ 13,0 13,1 Шаблон:Cite web
  14. ↑ 14,0 14,1 Шаблон:Cite web
  15. ↑ Шаблон:Cite web
  16. ↑ Шаблон:Cite web
  17. ↑ Шаблон:Cite web
  18. ↑ Шаблон:Cite web
  19. ↑ Шаблон:Cite web
  20. ↑ Шаблон:Cite web
  21. ↑ 21,0 21,1 Шаблон:Cite web
  22. ↑ Шаблон:Cite web
  23. ↑ Шаблон:Cite web
  24. ↑ Шаблон:Cite web
  25. ↑ RakeSearch
  26. ↑ Зотов И. В., Титов В. С., Колосков В. А. [и др.] Организация и синтез микропрограммных мультимикроконтроллеров. Курск: изд-во «Курск», 1999. 368 с. ISBN 5-7277-0253-4
  27. ↑ Ватутин Э. И., Зотов И. В., Титов В. С. [и др.] Комбинаторно-логические задачи синтеза разбиений параллельных алгоритмов логического управления при проектировании логических мультиконтроллеров. Курск, изд-во КурскГТУ, 2010. 200 с. ISBN 978-5-7681-0523-5
  28. ↑ Ватутин Э. И. Проектирование логических мультиконтроллеров. Синтез разбиений параллельных граф-схем алгоритмов. Saarbrucken: Lambert Academic Publishing, 2011 г. 292 с. ISBN 978-3-8433-1728-3
  29. ↑ Баранов С. И., Журавина Л. Н., Песчанский В. А. Метод представления параллельных граф-схем алгоритмов совокупностями последовательных граф-схем // Автоматика и вычислительная техника. 1984. № 5. С. 74—81.
  30. ↑ Зотов И. В., Колосков В. А., Титов В. С. Выбор оптимальных разбиений алгоритмов при проектировании микроконтроллерных сетей // Автоматика и вычислительная техника. 1997. № 5. С. 51—62.
  31. ↑ Шаблон:Cite web
  32. ↑ evatutin — Расчеты и постобработка завершены!
  33. ↑ evatutin — Постобработка результатов анализа смежной жадной стратегии завершена!
  34. ↑ Шаблон:Cite web
  35. ↑ Шаблон:Cite web
  36. ↑ 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.
  37. ↑ Шаблон:Cite web
  38. ↑ Шаблон:Cite web
  39. ↑ Шаблон:Cite web
  40. ↑ Шаблон:Cite web
  41. ↑ Шаблон:Cite web
  42. ↑ Шаблон:Cite web
  43. ↑ Шаблон:Cite web
  44. ↑ Шаблон:Cite web
  45. ↑ Шаблон:Cite web
  46. ↑ Шаблон:Cite web
  47. ↑ Шаблон:Cite web
  48. ↑ Vatutin E.I., Zaikin O.S., Kochemazov S.E., Valyaev S.Y. Using Volunteer Computing to Study Some Features of Diagonal Latin Squares // Open Engineering. Vol. 7. Iss. 1. 2017. pp. 453–460. DOI: 10.1515/eng-2017-0052.
  49. ↑ 49,0 49,1 Шаблон:Cite web
  50. ↑ Шаблон:Cite web
  51. ↑ Шаблон:Cite web
  52. ↑ Шаблон:Cite web
  53. ↑ Шаблон:Cite web
  54. ↑ Шаблон:Cite web
  55. ↑ Шаблон:Cite web
  56. ↑ Шаблон:Cite web
  57. ↑ Шаблон:Cite web
  58. ↑ Шаблон:Cite web
  59. ↑ Шаблон:Cite web
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Gerasim@Home&oldid=8661237