О проекте Gerasim@home
На днях, проект Gerasim@Home пополнился новыми wu-шками и расчетными модулями. Всего добавлено чуть более 1,2 млн. WU. Цель нового эксперимента - анализ асимптотического поведения в задаче формирования диагональных латинских квадратов заданного порядка.
"Итак пару слов о научной составляющей текущего запуска, как всегда буду краток smile. В комбинаторике есть 3 основные типа задач: на оптимальность/субоптимальность (найти наилучшее решение, например, по стоимости или другому показателю), на существование (найти неочевидное решение в условиях, когда неизвестно, есть ли решения вообще, либо доказать, что их нет) и на пересчет (посчитать число объектов с заданными свойствами).
До этого в Gerasim@Home'е мы в основном считали задачи первого направления (разбиения, поиск путей), и надеюсь будем считать еще, но позже. Поиск пар, троек и т.п. ортогональных латинских квадратов (то, что решается в SAT@Home) — задачи второго направления. А теперь мы попробуем поковырять третье. Если вы следите за нашими публикациями, то наверняка заметили, что с недавних пор у нас сложился клуб любителей квадратов (или комбинаторики и программирования) в составе группы широко известных в узких кругах лиц (как минимум Nauchnik, Alexone, hoarfrost, citerra и Степан, ник на данном форуме не помню).
Задачи, связанные с латинскими квадратами, мне кажутся интересными, многие из них требуют огромных вычислительных ресурсов, во многих находят применение как алгоритмические трюки, так и приемы микроархитектурной оптимизации (например, оптимизация обработки условий, PGO-компиляция и пр.), что в совокупности позволяет снизить затраты вычислительного времени на ряд экспериментов.
Чтобы планировать эксперименты, например, с целью доказательства или опровержения ряда гипотез (допустим, о существоваии тройки попарно ортогональных ДЛК порядка 10, чем занимается Nauchnik) необходимо знать некоторые характеристики комбинаторных объектов (например, сколько существует квадратов, у скольки из них есть ортогональные пары и т.п.) и их поведение с ростом размерности задачи (например, для задачи о ладьях асипмтотика известна — N!, а для латинских квадратов известны лишь аналитические ограничения сверху и снизу). Если они известны, можно делать некоторые оценки (например, сколько вычислительного времени потребуется, чтобы доказать, что тройки ОДЛК не существует), если нет, можно ошибиться на несколько порядков (например, планировать считать год, а в итоге посчитать за 1000 лет при тех же аппаратных возможностях).
Например, Пьер Ферма совсем немного не дожил до открытия свойств элиптических кривых и доказательства его великой теоремы smile, в "квадратных" задачах хотелось бы дожить. В данном эксперименте мы попытаемся посчитать одну из таких характеристик. По началу мне вообще подобное представлялось невозможным, т.к. число ДЛК и связанных с ними комбинаторных объектов просто огромно (например, для размерности N=8 ДЛК всего то 300286741708800, а ЛК еще больше — 108776032459082956800, что является тематикой одного из моих выступлений в Дубне менее чем через месяц).
Однако путем применения ряда оптимизаций оказывается, что не так уж и страшен черт, если у нас есть грид smile, да и находить искомые квадраты можно с использованием эвристических подходов, о чем недавно была статья...
Теперь ближе к науке... В ходе разработки кода расчетного модуля оказалось, что очень важным оказывается не просто работоспособность кода, но и его скоростные характеристики (далее будем характеризовать их темпом получения интересующих решений). Т.е. написать код на древнем Turbo Pascal'е или интерпретируемом Visual Basic'е или C# конечно можно, но об эффективности при этом можно забыть...
В текущей задаче в самом начале изысканий указанный темп был менее 1 решения в секунду и было подозрение, что "сложить квадрат" — не такая уж и тривиальная задачка, даже для моих муравьев smile (для сравнения можете прикинуть, какой темп в задаче поиска пар ОДЛК в SAT@Home, если за пару лет на грид из тысяч процессоров найдено всего несколько десятков решений — задача еще более вычислительно сложная, но и к ней подход найти можно, но это немного в сторону и к Nauchnik'у smile ). После ряда манипуляций, подробно описанных в статье
Ватутин Э.И., Журавлев А.Д., Заикин О.С., Титов В.С. Особенности использования взвешивающих эвристик в задаче поиска диагональных латинских квадратов // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2015. № 3 (16). С. 18–30.
