RakeSearch

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

RakeSearch — российский проект добровольных распределенных вычислений на платформе BOINC. Проект стартовал в октябре 2017 года[1]. По состоянию на 6 июля 2023 года в проекте приняли участие 2225 пользователей (11549 компьютеров), обеспечивая производительность до 10 терафлопс. Участвовать в проекте может любой желающий, обладающий компьютером с выходом в Интернет, установив на него программу BOINC Manager. Основной научной целью проекта является исследование свойств диагональных латинских квадратов (ДЛК) и решение связанных с ними комбинаторных задач.

История проекта[править | править код]

Пример строчно-перестановочной пары ОДЛК порядка 9

Проект стартовал в октябре 2017 года[1], используя в качестве расчетного модуля программу для поиска пар строчно-перестановочных ортогональных диагональных латинских квадратов (ОДЛК) порядка 9. Расчет был завершен в июле 2019 года, его итогом стал исчерпывающий список пар ОДЛК указанного типа и образуемое ими множество комбинаторных структур[2]. Отличительной особенностью данного поиска является то, что при подобном подходе находятся не все возможные ОДЛК, а только их частный вид (подмножество расширенных самоотрогональных латинских квадратов, сокр. ESOLS), но при этом не требуется использование трансверсалей и алгоритма DLX, что позволяет сократить вычислительные затраты на несколько порядков[3].

В сентябре 2020 года в проекте был запущен эксперимент, связанный с построением исчерпывающего списка канонических форм ОДЛК порядка 9[4]. В рамках разработанного расчетного модуля производилось построение классов эквивалентности X-образных диагональных заполнений (т.н. линеек), далее в каждом из них производился поиск сильно нормализованных канонических форм ДЛК, каждая из которых входит в точности в один из главных классов ДЛК, а уже для них производилась проверка на наличие ортогональных ДЛК с использованием трансверсалей и алгоритма DLX. Расчет выполнялся совместно с проектом Gerasim@Home и был завершен в декабре 2020 года. Указанный подход позволил сократить вычислительные затраты приблизительно на три порядка по сравнению с проверкой всех нормализованных ДЛК и осуществить требуемые расчеты за разумное время.

Графическое представление спектров числа трансверсалей в ДЛК порядков 1-13

В настоящее время в проекте производятся расчеты, связанные с построением спектров числовых характеристик ДЛК[5][6][7][8][9].

Научные достижения[править | править код]

  • получен исчерпывающий список канонических форм ОДЛК порядка 9 (последовательность A305570 в OEIS, член a(9)) и соответствующий ему список комбинаторных структур[2].
  • получено множество наиболее сильных из известных на данный момент нижних и верхних ограничений на максимальные и минимальные значения числовых характеристик ДЛК и ОДЛК (например, последовательность A287647 в OEIS) и соответствующих им спектров (например, последовательность A344105 в OEIS).

Примечания[править | править код]

  1. ↑ 1 2 Please solve Captcha. Дата обращения: 5 июля 2023. Архивировано 5 июля 2023 года.
  2. ↑ 1 2 Источник. Дата обращения: 5 июля 2023. Архивировано 5 июля 2023 года.
  3. ↑ Manzyuk M., Nikitina N., Vatutin E. Start-up and the Results of the Volunteer Computing Project RakeSearch // Communications in Computer and Information Science book series. Vol. 1129. Springer, 2019. pp. 725–734. DOI: 10.1007/978-3-030-36592-9_59. Дата обращения: 5 июля 2023. Архивировано 5 июля 2023 года.
  4. ↑ Источник. Дата обращения: 5 июля 2023. Архивировано 5 июля 2023 года.
  5. ↑ Ватутин Э.И., Никитина Н.Н., Манзюк М.О., Альбертьян А.М., Курочкин И.И. О построении спектров быстровычислимых числовых характеристик диагональных латинских квадратов малого порядка // Интеллектуальные и информационные системы (Интеллект – 2021). Тула, 2021. С. 7–17. Дата обращения: 15 января 2024. Архивировано 5 марта 2023 года.
  6. ↑ Ватутин Э.И., Титов В.С., Пыхтин А.И., Крипачев А.В., Никитина Н.Н., Манзюк М.О., Альбертьян А.М., Курочкин И.И. Оценка мощностей спектров быстровычислимых числовых характеристик диагональных латинских квадратов порядков N>9 // Наука и образование в развитии промышленной, социальной и экономической сфер регионов России. Муром, 2022. С. 314–315. Дата обращения: 15 января 2024. Архивировано 5 марта 2023 года.
  7. ↑ Ватутин Э.И., Титов В.С., Пыхтин А.И., Крипачев А.В., Никитина Н.Н., Манзюк М.О., Альбертьян А.М., Курочкин И.И. Эвристический метод построения аппроксимаций спектров числовых характеристик диагональных латинских квадратов // Интеллектуальные информационные системы: тенденции, проблемы, перспективы (ИИС – 2022). Курск: изд-во ЮЗГУ, 2022. С. 35–41. Дата обращения: 15 января 2024. Архивировано 5 марта 2023 года.
  8. ↑ Ватутин Э.И., Никитина Н.Н., Манзюк М.О. и др. Методы построения спектров быстровычислимых числовых характеристик диагональных латинских квадратов // Облачные и распределенные вычислительные системы в электронном управлении (ОРВСЭУ – 2022) в рамках Национального суперкомпьютерного форума (НСКФ – 2022). Переславль-Залесский, 2023. С. 19–23. Дата обращения: 15 января 2024. Архивировано 15 января 2024 года.
  9. ↑ Vatutin E., Belyshev A., Nikitina N., Manzuk M. et al. Diagonalization and Canonization of Latin Squares // Lecture Notes in Computer Science. Vol. 14389. Springer, Cham., 2023. pp. 48–61. DOI: 10.1007/978-3-031-49435-2_4.

Ссылки[править | править код]

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

См. также[править | править код]

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