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.

Ссылки

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

См. также

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.