Русская Википедия:RakeSearch
Шаблон:Карточка программы для добровольных вычислений
RakeSearch — российский проект добровольных распределенных вычислений на платформе BOINC. Проект стартовал в октябре 2017 года[1]. По состоянию на 6 июля 2023 года в проекте приняли участие 2225 пользователей (11549 компьютеров), обеспечивая производительность до 10 терафлопс. Участвовать в проекте может любой желающий, обладающий компьютером с выходом в Интернет, установив на него программу BOINC Manager. Основной научной целью проекта является исследование свойств диагональных латинских квадратов (ДЛК) и решение связанных с ними комбинаторных задач.
История проекта
Проект стартовал в октябре 2017 года[1], используя в качестве расчетного модуля программу для поиска пар строчно-перестановочных ортогональных диагональных латинских квадратов (ОДЛК) порядка 9. Расчет был завершен в июле 2019 года, его итогом стал исчерпывающий список пар ОДЛК указанного типа и образуемое ими множество комбинаторных структур[2]. Отличительной особенностью данного поиска является то, что при подобном подходе находятся не все возможные ОДЛК, а только их частный вид (подмножество расширенных самоотрогональных латинских квадратов, сокр. ESOLS), но при этом не требуется использование трансверсалей и алгоритма DLX, что позволяет сократить вычислительные затраты на несколько порядков[3].
В сентябре 2020 года в проекте был запущен эксперимент, связанный с построением исчерпывающего списка канонических форм ОДЛК порядка 9[4]. В рамках разработанного расчетного модуля производилось построение классов эквивалентности X-образных диагональных заполнений (т.н. линеек), далее в каждом из них производился поиск сильно нормализованных канонических форм ДЛК, каждая из которых входит в точности в один из главных классов ДЛК, а уже для них производилась проверка на наличие ортогональных ДЛК с использованием трансверсалей и алгоритма DLX. Расчет выполнялся совместно с проектом Gerasim@Home и был завершен в декабре 2020 года. Указанный подход позволил сократить вычислительные затраты приблизительно на три порядка по сравнению с проверкой всех нормализованных ДЛК и осуществить требуемые расчеты за разумное время.
В настоящее время в проекте производятся расчеты, связанные с построением спектров числовых характеристик ДЛК.
Научные достижения
- получен исчерпывающий список канонических форм ОДЛК порядка 9 (Шаблон:OEIS, член a(9)) и соответствующий ему список комбинаторных структур[2].
- получено множество наиболее сильных из известных на данный момент нижних и верхних ограничений на максимальные и минимальные значения числовых характеристик ДЛК и ОДЛК (например, Шаблон:OEIS) и соответствующих им спектров (например, Шаблон:OEIS).
Примечания
Ссылки
Обсуждение проекта в форумах:
См. также
- BOINC
- Добровольные вычисления
- Комбинаторная оптимизация
- Латинский квадрат
- Греко-латинский квадрат
- OEIS
Шаблон:Добровольные вычисления
- ↑ 1,0 1,1 Please solve Captcha
- ↑ 2,0 2,1 http://evatutin.narod.ru/all_n9_structs_descr_rus.html
- ↑ 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.
- ↑ http://evatutin.narod.ru/evatutin_odls_9.zip
