RakeSearch - ОДЛК, порождаемые перестановкой строк
Здравствуйте! 
В группе математических проектов, исследующих латинские и диагональные латинские квадраты - новый проект! В нём ищутся пары (и более интересные множества) ортогональных диагональных латинских квадратов, которые можно получать из одного из квадратов множества перестановкой его строк.
Более подробное описание вы можете увидеть в презентации к докладу, прочитанном на недавно завершившейся конференции BOINC::FAST'2017 (RU | EN).
Проект развёрнут на площадке Иститута прикладных математических исследований Карельского Научного Центра РАН, его младшим научным сотрудником - Натальей Никитиной, а при создании алгоритма поиска использовались идеи Олега Заикина, Эдуарда Ватутина, Алексея Журавлёва и Степана Кочемазова.
Появился проект ещё 11 августа (эта дата - 2017.08.11 - его настоящий День Рождения), но до начала сентября был в стадии проверки идеи и переноса приложения на инфраструктуру BOINC. Сейчас же в нём запущен целевой эксперимент - поиск на множестве диагональных латинских квадратов (ДЛК) ранга 9.
В настоящее время в проекте есть приложение только для платформ Linux x86 и x86-64, в случае появления приложения для Windows об этом, безусловно, будет сообщено. Приглашаем всех, кому интересно участие в решении подобной задачи, присоединиться к нашему проекту, расположенному по адресу http://rake.boincfast.ru/rakesearch/ .
Различные вопросы, связанные с ним или отчёты об ошибках - предлагаю задавать либо в этой (или, если до этого дойдёт - выделенной) ветке этого форума, либо в ветке в VK.
Присоединяйтесь!
P.S. Описание проекта перенесено с предыдущего форума.
Немного про заполнения и интересную ортогональную пару!
(копию/оригинал новости в VK вы можете найти здесь)
Ранее мы рассказавали о новом поиске R10 в рамках проекта RakeSearch, последовавшего за поиском "перестановочных" диагональных латинских квадратов 9 ранга (он же - поиск R9). Сейчас появился повод рассказать о некоторых его деталях!
На изображении ниже - матрица квадрата 10 ранга, клетки которой раскрашены в несколько цветов:
- серым цветом отмечена верхняя строка с зафиксированными значениями клеток - {0, 1, 2, ..., 9} (выходить за рамки квадратов с такой строкой (они же - нормализованные квадраты) - нет смысла, т.к. ненормализованных квадрат может быть сведён к нормализованному);
- красным цветом обозначены клетки главной и побочной диагоналей, не относящиеся к первой строке;
- оранжевым цветом обозначены клетки первой и второй строки которые вместе с диагоналями и первой (фиксированной) строкой заполняются ещё на этапе генерации workunit-а;
- зелёным цветом обозначаются клетки, заполняемые во время обработки задания на компьютере участника - вычислительный модуль, заполняя матрицу до конца, формирует всё новые и новые диагональные латинские квадраты и переставляя в них строки, пробует получить ортогональную пару из исходного (только что сформированного) ДЛК перестановкой его строк.
Как вы также можете видеть, все красные и оранжевые клетки пронумерованы в определённом порядке. Это порядок по которому они заполняются, при формировании комбинации для очередного workunit-а. При этом, клетки самой верхней, фиксированной строки - не пронумерованы потому, что они не меняются и какая бы не получилась комбинация в других клетаках - они в ней всегда присутствуют в одном и том же виде.
Интереса ради, мы можем посчитать - сколько же возможно комбинаций, которыми можно заполнить самую первую пронумерованную клетку, или первые две, или три... и так далее. Если получившиеся числа выписать в табличку вида {Число клеток, Число заполнений} то мы получим ряд, возрастающий почти всё время (но не всё время) и с темпом, менающимся от клетки к клетке. Для первых 28 клеток, пронумерованных на изображении он получается таким:
1 - 8
2 - 57
3 - 356
4 - 1909
5 - 8544
6 - 30637
7 - 82508
8 - 148329
9 - 133496
10 - 934472
11 - 5356527
12 - 26980186
13 - 117013695
14 - 424874652
15 - 1210593966
16 - 2603495520
17 - 3755155200
18 - 2723433984
19 - 17021462400
20 - 82230388428
21 - 341712006852
22 - 1187460703344
23 - 3329849282564
24 - 7024312609228
25 - 9908083279232
26 - 7996577754080
27 - 43965973715660
28 - 212963246290200
Первые ~18 строк этой таблицы (или членов ряда - кому как больше нравится) вычисляются очень быстро - на отдельно взятое число уходят доли секунды, секунды или минуты в один поток, на уже давно выпущенном процессоре Intel Core i5-3570K. Чтобы пойти дальше, надо произвести намного больше вычислений - к примеру, для получения 28 члена ряда потребовалось ~50 суток процессорного времени CPU с архитектурой Haswell.
Но это число - 212963246290200 - интересно и другим. Как говорилось в самом начале, на первом изображении показано заполнение матрицы квадрата при генерации workunit-ов. А это значит, что каждая коминация заполнения этих клеток - это отдельный workunit. А число комбинаций, которыми мы можем заполнить эти клетки, соответственно, это и есть число workunit-ов, которые мы могли бы сгенерировать, если бы решили выполнить поиск по всему пространству ДЛК 10 ранга! Или, 212 триллионов 963 миллиарда 246 миллионов 290 тысяч 200 workunit-ов! Конечно - это слишком много и поиск будет только частичным, по небольшой части от возможно пространства.
Но даже в рамках частичного поиска, можно наткнуться на что-нибудь интересное. И об этом - новость № 2!
В каждом результате, приходящем с компьютера участника проекта, записываются пары со степенью (или "характеристикой") ортогональности более 80. И в каждом результате таких находится как минимум несколько штук. По мере обработки результатов - накапливается статистика о том, сколько пар с той или иной степенью ортогональности было обнаружено. По итогам сентября (то есть, за июль, август и сентябрь вместе взятые) она выглядела следующим образом:
Degree 81: 3887427
Degree 82: 899172
Degree 83: 181014
Degree 84: 33997
Degree 85: 5254
Degree 86: 900
Degree 87: 94
Degree 88: 16
Degree 89: 0
Degree 90: 0
...
Degree 100: 0
Хорошо видно, что переходе к следующей степени ортогональности число найденных пар уменьшается где-то в 4-6 раз. Но при переходе от степени 86 к 87 - разница уже почти в 10 раз (возможно - это временное явление и при дальнейшем накоплении статистики - мы увидим что-то иное), а после степени 88 - уже нет ничего, хотя если бы тенденция соблюдалась, мы должны были бы увидеть от 1 до 3 пар со степенью ортогональности 89!
И вот прошла первая половина октября. Что мы видим в результатах за эти две недели? А вот что:
Degree 81: 1329684
Degree 82: 330656
Degree 83: 74528
Degree 84: 14608
Degree 85: 2624
Degree 86: 400
Degree 87: 47
Degree 88: 6
Degree 89: 0
Degree 90: 1
Degree 91: 0
...
Degree 100: 0
- всё почти тоже самое - даже разрыв между степенями 86 и 87 до карикатурности похож на общую статистику, также нет ни одной пары со степенью 89... но есть 1 пара с 90! К тому же, если мы прибавим число пар с ХО = 88 (ХО - это "характеристика ортогональности", она же - "степень") найденных в первой половине октября к общей статистики, то получим 6 + 16 = 22! А ведь примерно таким (т.е. где-то 25 к 1) и должно быть, судя по статистике, соотношение числа пар на двух ступенях, отстоящих друг от друга на 2 уровня - как в случае с ХО = 88 и ХО = 90! Вот только промежуточное звено с ХО = 89 "куда-то пропало"!
Что это? Какая-то закономерность? Случайность? Что-то ещё? Увидим!
Ну, а саму пару с ХО = 90 - вы можете увидеть на втором изображении. Вот она:
Нашли её - josef j из команды Russia Team и Thyler Durden@P3D из команды Planet 3DNow!, однако вычисления каждого участника приближали эту находку. А может быть, (кто знает?) - и чего-то ещё!
Спасибо за участие и поддержку!
RakeSearch - итоги октября
В "научных итогах" первой половины октября мы говорили о том, что несмотря на то, что было найдено уже "достаточное" число пар со степенью (или "характеристикой") ортогональности, равной 88, не было найдено ни одной пары со степенью 89. Зато обнаружилась пара с характеристикой 90! И задавались вопросом - Что это? Временное, случайное отклонение от обычной статистики? Или что-то ещё? И уже вторая половина октября ситуацию существенно изменила, так как статистика по находкам в ней выглядела так:
...
Degree 88: 6
Degree 89: 3
Degree 90: 0
...
"Недостающие пары" с характеристикой 89 - нашлись и, сразу 3 штуки. Причём, две из этих трёх пар - оказались в одном(!) workunit-е. И, к тому же, в обработке результатов каждого из двух workunit-ов, принял участие один и тот же участник! Правда вот в этом ничего удивительного нет, так как он лидирует в проекте и по Total Credit и по Recent Average Credit.
Итого - 3 пары, 2 workunit-а, 4 результата и три участника. Это были:
- whizbang из команды Ars Technica
- killik из команды Czech National Team
- Administrator {11320}
После второй половины месяца, статистика находок за весь октябрь стала выглядеть так:
Degree 81: 2651975
Degree 82: 645827
Degree 83: 142978
Degree 84: 27828
Degree 85: 4840
Degree 86: 718
Degree 87: 73
Degree 88: 12
Degree 89: 3
Degree 90: 1
Degree 91: 0
...
Degree 100: 0
А статистика за всё время поиска - вот так:
Degree 81: 6539402
Degree 82: 1544999
Degree 83: 323992
Degree 84: 61825
Degree 85: 10094
Degree 86: 1618
Degree 87: 167
Degree 88: 28
Degree 89: 3
Degree 90: 1
Degree 91: 0
...
Degree 100: 0
Посмотрим, что будет дальше! И спасибо за участие в проекте!
На страницу "О проекте" выложили слайды от доклада, сделанного на Russian Supercomputing Days'2019. В докладе говорилось не только о уже завершённом на тот момент поиске R9, но и о том, как проходили спринты Formula BOINC, работе по проекту вообще и даже была слегка затронута история распределённых вычислений.
На конференции Russian Supercomputing Days'2019, проходившей в Москве, 23 и 24 сентября, в рамках секции Грид-системы из персональных компьютеров был представлен доклад о нашем проекте и результатах поиска R9. А уже в середине декабря, дополненная и улучшенная статья - Start-up and the Results of the Volunteer Computing Project RakeSearch, была опубликована в рамках 1129 тома рецензируемого издания Communications in Computer and Information Science.
По существующим соглашениям, полный текст статьи, опубликованной в данном издании (впрочем, как и многих других) не может быть выложен в открытый доступ в течении некоторого времени. Поэтому ссылку на неё мы разместили на домашней странице участников, набравших Total Credit >= 5000 Cobblestones, добавив на странице раздел Publications (Статьи). Надеемся, что она расскажет о проекте что-нибудь ещё интересное.
Хоть поиск "перестановочных" ОДЛК уже давно завершён, добавлю для полноты, что результаты этого поиска можно увидеть на странице About RakeSearch Project. самые интересные из них, по мне, так это графы.