Gerasim@Home

Материал из Википедии — свободной энциклопедии
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 23 января 2024 года; проверки требуют 4 правки.
Перейти к навигации Перейти к поиску
Gerasim@Home
Платформа BOINC
Объём загружаемого ПО 2 МБ
Объём загружаемых данных задания 1 КБ
Объём отправляемых данных задания 150 КБ
Объём места на диске 2 МБ
Используемый объём памяти 10 МБ
Графический интерфейс нет
Среднее время расчёта задания до 6 часов
Deadline 11 дней
Возможность использования GPU нет

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 года стартовала серия экспериментов с целью исследования возможности использования случайного перебора[англ.][5][6] с фиксированным числом итераций при построении разбиений.

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

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

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

Первая пара ортогональных диагональных латинских квадратов порядка 10, найденная в проекте

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

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

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

Приложение separator

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

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

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

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

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

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

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

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

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

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

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

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

Для каждой точки выбранного среза пространства параметров осуществляется построение выборки параллельных алгоритмов логического управления с псевдослучайной структурой, построение их разбиений указанным методом и оценка качества, что требует от нескольких минут (малые значения ) до нескольких часов (большие значения ) вычислительного времени. Полученные выборки числовых значений объёмом около 200 КБ каждая передаются на сервер проекта и ожидают последующей обработки. Общий объём полученных данных (без учёта избыточности) составил 235 ГБ, а вычислительные затраты — 51,6 экзафлоп (818 ГГц-лет). По сравнению с реализацией на двухъядерном процессоре Core 2 Duo с частотой 1,86 ГГц выигрыш во времени, полученный за счет параллельной обработки с использованием грид, составил 155 раз. Постобработка полученных результатов[32][33] заняла около суток вычислительного времени и заключалась в расчете средних значений параметров качества и вероятностей получения разбиения с минимальным значением выбранного показателя качества, в результате чего были получены искомые двумерные карты общим объёмом 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 (последовательность A274171 в OEIS и последовательность A274806 в 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 (последовательность 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)[52][53];
  • произведен подсчет числа центрально симметричных диагональных латинских квадратов порядка N<10 (последовательность A293777 в OEIS и последовательность A293778 в OEIS)[54][55];
  • произведено определение минимального и максимального числа трансверсалей в диагональных латинских квадратах порядка 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)[56];
  • произведена классификация комбинаторных структур, возникающих из диагональных латинских квадратов порядка 1—10 на множестве бинарного отношения ортогональности[49][57][58];
  • показано, что рекордная характеристика ортогональности 274[59] для псевдотройки попарно-ортогональных диагональных латинских квадратов порядка 10, найденная в ходе анализа плоскостной симметрии в ДЛК, не может быть улучшена как в данном классе симметрий, так и в классе чистых обобщенных симметрий и их окрестностей.
Комбинаторные структуры из диагональных латинских квадратов порядка 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 — скат
Псевдотройка попарно-ортогональных диагональных латинских квадратов порядка 10 с рекордной характеристикой ортогональности 274. Образующий её квадрат B является строчно-инверсным и горизонтально-симметричным.

См. также

[править | править код]

Примечания

[править | править код]
  1. ↑ 1 2 BOINCstats | Gerasim@Home — Credit overview (недоступная ссылка)
  2. ↑ Separator progress - Page 2 - Science - Forum Gerasim@home. Дата обращения: 30 января 2013. Архивировано из оригинала 4 февраля 2013 года.
  3. ↑ 1 2 Ватутин Э. И., Леонов М. Е. Использование смежной окрестности при жадном последовательном формировании блоков разбиения граф-схем параллельных алгоритмов // Известия высших учебных заведений. Приборостроение. 2013. Т. 56. № 6. С. 30-35. Дата обращения: 12 октября 2013. Архивировано 14 октября 2013 года.
  4. ↑ 1 2 О проекте Gerasim@home — Page 48 — Gerasim@home — Форум Boinc.ru (недоступная ссылка)
  5. ↑ 1 2 Ватутин Э. И., Колясников Д. В., Мартынов И. А., Титов В. С. Метод случайного перебора в задаче построения разбиений граф-схем параллельных алгоритмов // Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов. Барнаул: Барнаул, 2014. С. 115—125. Дата обращения: 13 августа 2014. Архивировано 14 августа 2014 года.
  6. ↑ 1 2 Ватутин Э. И., Колясников Д. В., Титов В. С. Анализ результатов применения метода случайного перебора в задаче поиска разбиений граф-схем параллельных алгоритмов // Известия Южного федерального университета. Технические науки. 2014. № 12 (161). С. 102—110. Дата обращения: 1 марта 2015. Архивировано 2 апреля 2015 года.
  7. ↑ 1 2 Ватутин Э. И., Мартынов И. А., Титов В. С. Способ обхода тупиков при решении задач дискретной оптимизации с ограничениями // Перспективные информационные технологии (ПИТ-2014). Самара: изд-во Самарского научного центра РАН. С. 313—317. Дата обращения: 16 февраля 2015. Архивировано 16 февраля 2015 года.
  8. ↑ Ватутин Э. И., Титов В. С. Параметрическая оптимизация алгоритма имитации отжига на примере решения задачи поиска кратчайшего пути в графе // Вестник Череповецкого государственного университета. № 6 (67). 2015. С. 13-16. Дата обращения: 28 ноября 2015. Архивировано 8 декабря 2015 года.
  9. ↑ О проекте Gerasim@home — Page 63 — Gerasim@home — Форум Boinc.ru. Дата обращения: 16 февраля 2015. Архивировано из оригинала 16 февраля 2015 года.
  10. ↑ Ватутин Э. И., Мартынов И. А., Титов В. С. Анализ результатов использования метода перебора с ограничением глубины в задаче поиска кратчайшего пути в графе // Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов (МППОС’15). Барнаул, 2015. С. 120—128. Дата обращения: 4 августа 2015. Архивировано 8 декабря 2015 года.
  11. ↑ 1 2 Ватутин Э. И., Титов В. С. Анализ результатов применения алгоритма муравьиной колонии в задаче поиска пути в графе при наличии ограничений // Известия Южного федерального университета. Технические науки. 2014. № 12 (161). С. 111—120. Дата обращения: 1 марта 2015. Архивировано 2 апреля 2015 года.
  12. ↑ 1 2 Ватутин Э. И., Титов В. С. Об одном подходе к использованию алгоритма муравьиной колонии при решении задач дискретной комбинаторной оптимизации // Интеллектуальные и информационные системы (Интеллект 2015). Тула, 2015. С. 8-13. Дата обращения: 11 декабря 2015. Архивировано 5 марта 2016 года.
  13. ↑ 1 2 Ватутин Э. И., Титов В. С. Исследование особенностей применения генетического алгоритма в задаче поиска кратчайшего пути в графе при наличии ограничений на плотность графа // Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов (МППОС — 2016). Барнаул: изд-во Алтайского государственного университета, 2016. С. 152—159. Дата обращения: 25 июня 2016. Архивировано 16 июня 2016 года.
  14. ↑ 1 2 Ватутин Э. И., Титов В. С. Особенности метаоптимизации алгоритма пчелиной колонии в задаче поиска кратчайшего пути в графе при наличии ограничений на плотность графа // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. № 2 (19). 2016. С. 52-65. Дата обращения: 7 августа 2016. Архивировано 20 августа 2016 года.
  15. ↑ Project News. Дата обращения: 25 июня 2016. Архивировано 17 июля 2016 года.
  16. ↑ О проекте Gerasim@home — Page 94 — Gerasim@home — Форум Boinc.ru. Дата обращения: 22 ноября 2016. Архивировано из оригинала 22 ноября 2016 года.
  17. ↑ О проекте Gerasim@home — Page 96 — Gerasim@home — Форум Boinc.ru. Дата обращения: 22 ноября 2016. Архивировано из оригинала 22 ноября 2016 года.
  18. ↑ Ватутин Э.И., Титов В.С. Исследование особенностей применения метода роя частиц в задачах дискретной оптимизации // Вестник компьютерных и информационных технологий. № 5 (167). 2018. С. 26–34. DOI: 0.14489/vkit.2018.05.pp.026–034. Дата обращения: 4 июня 2018. Архивировано 15 июля 2019 года.
  19. ↑ О проекте Gerasim@home - Page 98 - Gerasim@home - Форум Boinc.ru. Дата обращения: 14 марта 2017. Архивировано из оригинала 15 марта 2017 года.
  20. ↑ Поиск КФ ОДЛК в проекте Gerasim@home - Gerasim@home - Форум Boinc.ru. Дата обращения: 14 марта 2017. Архивировано из оригинала 15 марта 2017 года.
  21. ↑ 1 2 О проекте Gerasim@home - Page 103 - Gerasim@home - Форум Boinc.ru. Дата обращения: 16 июня 2017. Архивировано из оригинала 20 июня 2017 года.
  22. ↑ О проекте Gerasim@home - Page 106 - Gerasim@home - Форум Boinc.ru. Дата обращения: 29 октября 2017. Архивировано из оригинала 30 октября 2017 года.
  23. ↑ Ватутин Э.И., Кочемазов С.Е., Заикин О.С., Титов В.С. Исследование свойств симметричных диагональных латинских квадратов. Работа над ошибками // Интеллектуальные и информационные системы (Интеллект – 2017). Тула, 2017. С. 30–36. Дата обращения: 4 декабря 2017. Архивировано 5 декабря 2017 года.
  24. ↑ О проекте Gerasim@home - Page 117 - Gerasim@home - Форум Boinc.ru. Дата обращения: 20 декабря 2018. Архивировано из оригинала 20 декабря 2018 года.
  25. ↑ RakeSearch. Дата обращения: 5 июля 2023. Архивировано 5 июля 2023 года.
  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. ↑ Ватутин Э. И., Зотов И. В. Метод формирования субоптимальных разбиений параллельных управляющих алгоритмов // Параллельные вычисления и задачи управления (PACO’04). М.: ИПУ РАН, 2004. С. 884—917. Дата обращения: 13 мая 2012. Архивировано 29 марта 2014 года.
  32. ↑ evatutin — Расчеты и постобработка завершены!
  33. ↑ evatutin — Постобработка результатов анализа смежной жадной стратегии завершена!
  34. ↑ Ватутин Э. И., Дремов Е. Н., Мартынов И. А., Титов В. С. Метод взвешенного случайного перебора для решения задач дискретной комбинаторной оптимизации // Известия ВолГТУ. Серия: Электроника, измерительная техника, радиотехника и связь. № 10 (137). Вып. 9. 2014. c. 59-64. Дата обращения: 22 июля 2014. Архивировано 29 июля 2014 года.
  35. ↑ Vatutin E.I. Comparison of Decisions Quality of Heuristic Methods with Sequential Formation of the Decision in the Graph Shortest Path Problem // CEUR Workshop Proceedings. Proceedings of the Third International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC:FAST 2017). Vol. 1973. Technical University of Aachen, Germany, 2017. pp. 67–76. Дата обращения: 29 октября 2017. Архивировано 30 октября 2017 года.
  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. ↑ Vatutin E., Panishchev V., Gvozdeva S., Titov V. Comparison of Decisions Quality of Heuristic Methods Based on Modifying Operations in the Graph Shortest Path Problem // Problems of Information Technology. No. 1. 2020. pp. 3–15. DOI: 10.25045/jpit.v11.i1.01. Дата обращения: 16 января 2020. Архивировано 16 января 2020 года.
  38. ↑ Ватутин Э. И., Журавлев А. Д., Заикин О. С., Титов В. С. Особенности использования взвешивающих эвристик в задаче поиска диагональных латинских квадратов // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2015. № 3 (16). С. 18-30. Дата обращения: 22 ноября 2016. Архивировано 30 марта 2016 года.
  39. ↑ Vatutin E.I., Zaikin O.S., Zhuravlev A.D., Manzuk M.O., Kochemazov S.E., Titov V.S. Using grid systems for enumerating combinatorial objects on example of diagonal Latin squares // Distributed computing and grid-technologies in science and education (GRID’16): book of abstracts of the 7th international conference. Dubna: JINR, 2016. p. 114—115. Дата обращения: 22 ноября 2016. Архивировано 21 сентября 2017 года.
  40. ↑ Ватутин Э. И., Заикин О. С., Журавлев А. Д., Манзюк М. О., Кочемазов С. Е., Титов В. С. О влиянии порядка заполнения ячеек на темп генерации диагональных латинских квадратов // Информационно-измерительные диагностирующие и управляющие системы (Диагностика — 2016). Курск: изд-во ЮЗГУ, 2016. С. 33-39. Дата обращения: 22 ноября 2016. Архивировано 22 ноября 2016 года.
  41. ↑ Ватутин Э. И., Титов В. С., Заикин О. С., Кочемазов С. Е., Валяев С. Ю., Журавлев А. Д., Манзюк М. О. Использование грид-систем для подсчета комбинаторных объектов на примере диагональных латинских квадратов порядка 9 // Информационные технологии и математическое моделирование систем 2016. М.: изд-во Центра информационных технологий в проектировании РАН, 2016. С. 154—157. Дата обращения: 22 ноября 2016. Архивировано 22 ноября 2016 года.
  42. ↑ Ватутин Э. И., Журавлев А. Д., Заикин О. С., Титов В. С. Учёт алгоритмических особенностей задачи при генерации диагональных латинских квадратов // Известия ЮЗГУ. 2016. № 2 (65). C. 46-59. Дата обращения: 22 ноября 2016. Архивировано 21 сентября 2017 года.
  43. ↑ Vatutin E.I., Zaikin O.S., Zhuravlev A.D., Manzyuk M.O., Kochemazov S.E., Titov V.S. Using grid systems for enumerating combinatorial objects on example of diagonal Latin squares // CEUR Workshop proceedings. Selected Papers of the 7th International Conference Distributed Computing and Grid-technologies in Science and Education. 2017. Vol. 1787. pp. 486–490. urn:nbn:de:0074-1787-5. Дата обращения: 2 февраля 2017. Архивировано 2 февраля 2017 года.
  44. ↑ О проекте Gerasim@home — Page 94 — Gerasim@home — Форум Boinc.ru. Дата обращения: 22 ноября 2016. Архивировано из оригинала 22 ноября 2016 года.
  45. ↑ Vatutin E.I., Kochemazov S.E., Zaikin O.S. Applying volunteer and parallel computing for enumerating diagonal Latin squares of order 9 // Proc. of The Eleventh International Conference on Parallel Computational Technologies, Vol. 753 of Communications in Computer and Information Science, Springer, 2017, pp. 114–129. DOI: 10.1007/978-3-319-67035-5_9. Дата обращения: 9 октября 2017. Архивировано 9 октября 2017 года.
  46. ↑ Vatutin E.I., Kochemazov S.E., Zaikin O.S., Valyaev S.Yu. Enumerating the Transversals for Diagonal Latin Squares of Small Order // CEUR Workshop Proceedings. Proceedings of the Third International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC:FAST 2017). Vol. 1973. Technical University of Aachen, Germany, 2017. pp. 6–14. Дата обращения: 29 октября 2017. Архивировано 30 октября 2017 года.
  47. ↑ Ватутин Э.И., Заикин О.С., Кочемазов С.Е., Валяев С.Ю., Титов В.С. Оценка числа трансверсалей для диагональных латинских квадратов // Телекоммуникации. 2018. № 1. С. 12–21. Дата обращения: 6 февраля 2018. Архивировано 7 февраля 2018 года.
  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. ↑ 1 2 Vatutin E.I., Titov V.S., Zaikin O.S., Kochemazov S.E., Manzuk M.O., Nikitina N.N. Orthogonality-based classification of diagonal Latin squares of order 10 // CEUR Workshop Proceedings. Vol. 2267. Proceedings of the VIII International Conference "Distributed Computing and Grid-technologies in Science and Education" (GRID 2018). Dubna, JINR, 2018. pp. 282–287. Дата обращения: 5 января 2019. Архивировано 5 января 2019 года.
  50. ↑ Ватутин Э.И., Белышев А.Д., Кочемазов С.Е., Заикин О.С., Никитина Н.Н., Манзюк М.О. О полиномиальном сведении задач на базе латинских квадратов к задаче о точном покрытии // Оптико-электронные приборы и устройства в системах распознавания образов и обработки изображений (Распознавание – 2019). Курск: изд-во ЮЗГУ, 2019. С. 62–64. Дата обращения: 28 мая 2019. Архивировано 28 мая 2019 года.
  51. ↑ Vatutin E., Nikitina N., Belyshev A., Manzyuk M. On polynomial reduction of problems based on diagonal Latin squares to the exact cover problem // CEUR Workshop Proceedings. Proceedings of the Second International Conference Information, Computation, and Control Systems for Distributed Environments (ICCS-DE 2020). Vol. 2638. Technical University of Aachen, Germany, 2020. Дата обращения: 17 июля 2020. Архивировано 18 июля 2020 года.
  52. ↑ Vatutin E., Belyshev A., Kochemazov S., Zaikin O., Nikitina N. Enumeration of isotopy classes of diagonal Latin squares of small order using volunteer computing // Supercomputing Days Russia 2018. M.: Moscow State University, 2018. pp. 933–942. Дата обращения: 21 декабря 2018. Архивировано 21 декабря 2018 года.
  53. ↑ Vatutin E., Belyshev A., Kochemazov S., Zaikin O., Nikitina N. Enumeration of isotopy classes of diagonal Latin squares of small order using volunteer computing // Communications in Computer and Information Science. Vol. 965. Springer, 2018. pp. 578–586. DOI: 10.1007/978-3-030-05807-4_49. Дата обращения: 5 января 2019. Архивировано 5 января 2019 года.
  54. ↑ Ватутин Э.И., Кочемазов С.Е., Заикин О.С., Манзюк М.О., Никитина Н.Н., Титов В.С. О свойствах центральной симметрии диагональных латинских квадратов // Высокопроизводительные вычислительные системы и технологии. № 1 (8). 2018. С. 74–78. Дата обращения: 13 ноября 2018. Архивировано 14 ноября 2018 года.
  55. ↑ Vatutin E.I., Kochemazov S.E., Zaikin O.S., Manzuk M.O., Nikitina N.N., Titov V.S. Central Symmetry Properties for Diagonal Latin Squares // Problems of Information Technology. No. 2. 2019. pp. 3-8. DOI: 10.25045/jpit.v10.i2.01. Дата обращения: 15 октября 2019. Архивировано 15 октября 2019 года.
  56. ↑ Ватутин Э.И., Белышев А.Д. Определение числа самоортогональных (SODLS) и дважды самоортогональных диагональных латинских квадратов (DSODLS) порядков 1–10 // Высокопроизводительные вычислительные системы и технологии. Т. 4. № 1. 2020. С. 58–63. Дата обращения: 19 июля 2020. Архивировано 19 июля 2020 года.
  57. ↑ Ватутин Э.И., Титов В.С., Заикин О.С., Кочемазов С.Е., Манзюк М.О. Анализ комбинаторных структур на множестве отношения ортогональности диагональных латинских квадратов порядка 10 // Информационные технологии и математическое моделирование систем 2017. М.: ЦИТП РАН, 2017. С. 167–170. Дата обращения: 16 февраля 2018. Архивировано 16 февраля 2018 года.
  58. ↑ Vatutin E.I., Titov V.S., Zaikin O.S., Kochemazov S.E., Manzyuk M.O., Nikitina N.N. Orthogonality-based classification of diagonal Latin squares of order 10 // Distributed computing and grid-technologies in science and education (GRID’18): book of abstracts of the 8th international conference. Dubna: JINR, 2018. pp. 94–95. Дата обращения: 13 ноября 2018. Архивировано 13 ноября 2018 года.
  59. ↑ Zaikin O., Zhuravlev A., Kochemazov S., Vatutin E. On the Construction of Triples of Diagonal Latin Squares of Order 10 // Electronic Notes in Discrete Mathematics. Vol. 54C. 2016. pp. 307–312. DOI: 10.1016/j.endm.2016.09.053. Дата обращения: 28 мая 2019. Архивировано из оригинала 22 ноября 2016 года.

Ссылки

[править | править код]

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

Источник — https://ru.wikipedia.org/w/index.php?title=Gerasim@Home&oldid=139084160