Пары (и более интересные множества) ортогональных диагональных латинских квадратов
Пары (и более интересные множества) ортогональных диагональных латинских квадратов
Здравствуйте!
7 сентября 2017 г.
В группе математических проектов, исследующих латинские и диагональные латинские квадраты - новый проект! В нём ищутся пары (и более интересные множества) ортогональных диагональных латинских квадратов, которые можно получать из одного из квадратов множества перестановкой его строк.
Более подробное описание вы можете увидеть в презентации к докладу, прочитанном на недавно завершившейся конференции BOINC::FAST'2017 (RU | EN).
Проект развёрнут на площадке Иститута прикладных математических исследований Карельского Научного Центра РАН, его младшим научным сотрудником - Натальей Никитиной, а при создании алгоритма поиска использовались идеи Олега Заикина, Эдуарда Ватутина, Алексея Журавлёва и Степана Кочемазова.
Появился проект ещё 11 августа (эта дата - его настоящий День Рождения), но до начала сентября был в стадии проверки идеи и переноса приложения на инфраструктуру BOINC. Сейчас же в нём запущен целевой эксперимент - поиск на множестве диагональных латинских квадратов (ДЛК) ранга 9.
В настоящее время в проекте есть приложение только для платформ Linux x86 и x86-64, в случае появления приложения для Windows об этом, безусловно, будет сообщено. Приглашаем всех, кому интересно участие в решении подобной задачи, присоединиться к нашему проекту, расположенному по адресу http://rake.boincfast.ru/rakesearch/ .
Различные вопросы, связанные с ним или отчёты об ошибках - предлагаю задавать либо в этой (или, если до этого дойдёт - выделенной) ветке этого форума, либо в ветке в VK.
Присоединяйтесь!
Немного о времени расчёта задания, контрольных точках и об отображении процента выполнения.
Оценка доли выполненных вычислений - приблизительная и расчёт задания может завершится как до постепенного достижения рубежа в 100%, так и после него. В случае некоторых заданий, процент выполнения может доходить до 150% и даже 200%, но в большистве случаев - должен либо не доходить до 100%, либо немного превышать его.
Контрольные точки - есть. Есть и возможность "ручного перезапуска задания", которое не должно требоваться (всё должно работать само) но может пригодиться в ситуации сбоя при формировании файла контрольной точки (checkpoint-а). Чтобы сделать такой "ручной сброс" нужно
1) Найти необходимый slot в котором выполняется задание;
2) Остановить BOINC;
3) Зайти в соответствующий каталог slots/n и удалить файл checkpoint.txt - перед удалением можно посмотреть на его размер - если он пустой, то что-то пошло не так и его лучше удалить, чтобы перезапустить расчёт. Если же он не пустой, то скорее всего расчёт идёт нормально.
Сейчас время выполнения одного задания на ядре процессора уровня Intel Core i5 составляет около 10 часов, но может быть как больше, так и меньше.
У проекта появился нормальный адрес: http://rake.boincfast.ru/rakesearch/. Также в настройках проекта поставили опцию, о которой написал Progger - <prefer_primary_platform>1</prefer_primary_platform>, так что теперь на 64-битные компьютеры должна загружаться 64-битная версия.
Утверждать, что эти пары ОДЛК никогда и никто не видел - было бы наверное глупо - прямо в стиле проблемы чайника Рассела.
Но и задача проекта - не открыть какие-то отдельные пары, а получив набор таких ОДЛК, изучить их свойства на этапе постобработки.
24 ноября 2017
Немного дополнительной информации о научной компоненте проекта...
Ранее, в слайдах рассказывалось о том, что:
1. В ДЛК до 7 ранга, все ОДЛК являются "перестановочными";
2. В множестве квадратов 7 ранга появляется некоторое разнообразие - квадраты бьются на 2 множества - есть четвёрка(и) взаимно ортогональных диагональных латинских квадратов (ВОДЛК, "с точностью до канонизации" ), а есть просто пары ОДЛК, которым не ортогональны другие квадраты и они "не перестановочные".
Естественно, что возник вопрос и о том, а что будет дальше? Параллельно возник и ещё один - а могут ли помимо ситуаций, когда одному ДЛК ортогонально несколько других (1), или ситуаций, когда некоторое множество ОДЛК - взаимно ортогонально(2), быть другие конструкции? Назовём (1) - звездой, а (2) - сетью, или полным графом. А могут ли быть неполные графы? Циклы? Насколько большими они могут быть? Нам это было неизвестно.
И, конечно же - как искать? Простой перебор всех ДЛК с поиском ОДЛК к ним известными нам методами - пока слишком долго. Но что если перестановочные ДЛК являются своеобразными маркерами этих самых множеств? Кто знает? А ведь сделать перестановку строк - быстро! Так и родилась идея "Поиска граблением" - пробегаясь очень быстро по множеству ДЛК (по сравнению с полным поиском), пытаться словно граблями выдергивать из общего моря квадратов "перестановочные ДЛК", в надежде на то, что они станут ключом к более интересным структурам.
И мы их нашли! На множестве ДЛК 8 ранга всплыла конструкция из 12 "перестановочных" ДЛК отношение ортогональности в котором было неполным и довольно интересным графом, а уже дальнейший поиск ОДЛК к этим квадратам, показал, что с одной стороны, одному из них ортогональны 824 других ДЛК (и это - пока рекорд для всех с рангом ДЛК <= 10!), а с другой - полный размер структуры из ортогональных квадратов - намного больше чем первоначальная находка. В дальнейшем Эдуард Ватутин не только проверил этот квадрат, по и получил ещё более важный результат, показав, что 824 - это максимальное число ОДЛК для 8 ранга.
На этом, в марте-апреле 2016 года, исследования надолго (где-то на 1.5 года) приостановились, потому что на полный анализ структуры из ОДЛК 8 ранга времени так не хватило, а обработка ДЛК 9 ранга - задача намного более ресурсоёмкая. Но после того, как Наталия Никитина из Карельского Научного Центра РАН заинтересовалась задачей и облекла её в форму BOINC-проекта (для чего потребовалось проделать немало работы!) - поиск пошёл дальше! Одновременно благодаря большим алгоритмическим наработкам группы Эдуарда, citerra, Олега, Степана, ..., появилась возможность проводить дополнительный анализ найденных в проекте ОДЛК. И, возможно, мы нашли нечто не менее интересное и масштабное. Возможно, что размер найденной структуры (выводы пока не окончательные) - составляет более 60 000 ОДЛК!
На рисунке - его центральная часть при низкой степени детализации.
Быть может, продолжение следует...
7 января 2018
(http://rake.boincfast.ru/rakesearch/forum_thread.php?id=50)
Уважаемые участники!
За 5 месяцев своей жизни проект значительно вырос и за это мы хотим сказать большое спасибо всем его участникам! На сегодняшний день в нём было обработано более 1.2 миллионов заданий (из ~23.3 миллионов), что дало нам несколько тысяч результатов с "перестановочными" ортогональными диагональными латинскими квадратами и открывает путь к интересному поиску структур из этих квадратов и квадратов, ортогональных им (подобных ранее найденному "Ожерелью" ). Мы автоматизировали целый ряд задач, которые обязательно необходимо выполнять для того, чтобы проект оставался работоспособным, но потреблявшие очень много времени и, теперь сможем приступить к более глубокой обрабаботке найденных результатов.
Также мы столкнулись с тем, что текущий формат публикации результатов (в виде простой HTML-страницы с перечнем пар ОДЛК) (http://rake.boincfast.ru/rakesearch/odls_results.php) не позволяет в полной мере отразить их смысл, из-за чего, после опубликования последней части результатов, полученных в декабре, мы начнём разработку другого интерфейса для их просмотра, поиска и фильтрации. Разумеется, традиция поздравления участников, нашедших ОДЛК - останется, как и выдача значков за это. И, конечно же, после завершения постобработки все результаты будут опубликованы - как минимум в "сыром" формате.
Ещё одна важная тема - оптимизация приложения по умолчанию. Мы планируем реализовать в нём оптимизации Daniel-я, но после того, как запустим постобработку результатов, так как уже сейчас любой участник может его скачать и запустить - по ссылкам из соответствующей ветки. (http://rake.boincfast.ru/rakesearch/forum_thread.php?id=39)
Надеемся, что этот "отчёт о состоянии проекта" сделает его работу более понятной и прозрачной. Большое спасибо всем участникам и удачных вычислений!
Новости от 2018.01.16 - Текущие (предварительные) результаты (http://rake.boincfast.ru/rakesearch/graphs.html) проекта RakeSearch в виде графов.
Уважаемые участники проекта!
Мы приступили к обработке данных, полученных в рамках проекта и теперь публикуем первую часть предварительных результатов в виде графов. Как мы уже писали, научная цель проекта состоит в выявлении подмножеств ортогональных диагональных латинских квадратов ранга 9, образующих связанные структуры. Одним из лучших способов представления подобного множества является граф, каждая вершина которого соответствует одному квадрату, а ребро между ними - обозначает, что квадраты, соответствующие этим вершинам - ортогональны. Такие графы интересны для изучения ОДЛК с фундаментальными или прикладными целями.
При помощи алгоритма, используемого в RakeSearch, мы не можем обнаружить всё множество квадратов сразу (поскольку ищутся только те ортогональные квадраты, которые могут быть получены перестановкой строк). Но значительно более простой (по сравнению с полным поиском) и быстрый алгоритм позволяет обнаруживать отдельные вершины этих графов, подхватывая их ( "Rake" ), словно драгоценные камни среди травы. А уже найдя их - мы восстанавливаем и весь граф.
На данный момент мы обнаружили 18 типов подобных графов. Первым - было "Ожерелье". Графы как минимум многих типов встречаются неоднократно - например больше всего из обнаруженных графов представляли из себя обычную пару квадратов, либо какую-то очень простую фигуру. Выражаем большую благодарность Эдуарду Ватутину и Степану Кочемазову за идеи и работу, использующуюся нами в обработке результатов проекта. Визуализация графов была выполнена в программе Gephi.
Надеемся, что такая форма представления результатов, будет вам интересна!
Удачи и быстрых расчётов!
Новости проекта от 2018.04.17. Граф.
Уважаемые участники проекта!
Мы представляем несколько следующих типов графов из ОДЛК, открытых в проекте RakeSearch. Далее мы будем использовать обозначение "m/n" говорящее, что описываемые граф "выращен" из пары под номером n из канонического результата к workunit-у m)
Первый из них - R9_000034562/01 - состоит 10 вершин и 20 рёбер.
Наращивание мощности серверной инфраструктуры!
Дорогие друзья!
Мы поздравляем всех со стартом 9-го BOINC Pentathlon-а! Но кроме этого у нас есть и ещё один повод для хорошего настроения - вчерашний upgrade сервера, на котором работает виртуальная машина нашего проекта. Добавим немного железа в новости!
1. Планки памяти и процессор для их установки в сервер:
2. Сервер с виртуальной машиной нашего проекта (в центре, второй сверху):
3. Серверный шкаф (много пространства - ещё свободно, но в нижней части вы можете видеть самое настоящее шасси с лезвиями - это вычислительный кластер от компании T-Платформы):
4. Сам сервер. Мы столкнулись с тем, что на сокете отсутствовал радиатор (некоторые серверы поставляются сразу со всеми необходимыми радиаторами, а некоторые - нет) и, поэтому, вчера была завершена первая часть "плана по upgrade-у" - RAM сервера была заменена на новые планки, в 2 раза большими по объёму. После того, как будет найден и радиатор для второго процессора, в сервер будет добавлена и его исходная RAM, если материнская плата позволит собрать такую конфигурацию. В противном случае вынутые планки памяти будут просто установлены в другой сервер. После установки новых планок памяти и, расширения RAM, доступной виртуальной машине проекта, мы смогли увеличить кэши, используемые MySQL для обработки и временного хранения строк. Надеемся, что это сделает работу сервера проекта быстрее, более плавной и предсказуемой.
Новости на выходные, или 5 новых типов графов!
(Новость непосредственно на сайте проекта)
Дорогие друзья!
Представляем вам ещё 5 типов графов из ОДЛК 9 ранга, найденных в рамках проекта RakeSearch. (http://rake.boincfast.ru/rakesearch/forum_thread.php?id=80)
Первый из них [R9_000040159/01] похож на цветок. Многие из квадратов этого графа ортогональны 2 квадратам, помещённым в центре этого "цветка" и при прорисовке рёбер и получается подобная фигура из "лепестков". Чтобы вырастить этот цветочек необходимо 32 вершины и 62 ребра.
Конечно, в этих фигурах "рыб, цветов и спутников" - нет какого либо особого смысла - они просто поднимают настроение, а используя другой метод раскладки графа, мы могли бы получить и совершенно другие формы. Но человеческое создание, нацеленное на распознавание знакомых объектов в линиях и пятнах - всё равно увидело бы в них какую-то знакомую фигуру.
И, конечно же, мы поздравляем Daniel из BOINC@Poland (или [B@P] Daniel) с первым местом по Total Credit!
Подводим итоги мая!
Май закончился и началось лето! Во второй половине мая было получено 1213 результатов с "перестановочными ОДЛК". Все участники, компьютеры которых нашли подобные результаты, получились бейджик с вербой и могут посмотреть их по ссылке Results with ODLS pairs со страницы учётной записи. Мы благодарны всем участниками проекта и поздравляем наиболее удачливых кранчеров второй половины мая 2018:
CoolAtchOk (Russia Team) и vanos0512 (BOINC@Taiwan),
KWSN-SpongeBob SquarePants (The Knights Who Say Ni!) и arkiss,
Shmya-2 (Crystal Dream) и Ralfy (BOINC Confederation),
Oleg (Russia Team) и [B@P] Daniel (BOINC@Poland),
Skivelitis2 (BOINCstats) и Thyler Durden@P3D (Planet 3DNow!),
Soderstromm (Gridcoin) и Sergey Zhi (Russia Team),
Natalia (Crystal Dream) и hoarfrost (Crystal Dream),
Steve Dodd (The Planetary Society) и bcavnaugh (Crunching@EVGA),
Международная база наблюдений комет (Karelia) и Andreas64,
http://vk.com/boin (Karelia) и Conan (Cobar Spiders),
[AF>Libristes]cguillem (L'Alliance Francophone) и Hartmut 53,
LeChat51X (L'Alliance Francophone) и JonS (UK BOINC Team),
hoppisaur (Ars Technica) и Astronomy.Karelia (Karelia),
ReaDy (Astronomy.Ru Forum) и Птицы Петрозаводска (Karelia),
KPX (Czech National Team) и Beyond (Ars Technica),
Stephen Uitti (Project Blue Book) и gingavasalata (Hrvatska),
LCB001 (Hardware Canucks) и gaballus (BOINC@Poland),
vaughan (AMD Users) и KR Center (Karelia),
Philip (OZ Crunchers) и saiz (Team China),
owensse (The Planetary Society) и lydy1993 (Team China),
[AF>Amis des Lapins] Phil1966 (L'Alliance Francophone) и adams,
pututu ([H]ardOCP) и PDW (OcUK - Overclockers UK),
Vincent Dark (Team China) и Pete Broad (BOINC Synergy),
citerra (Russia Team) и Rhodan71 (L'Alliance Francophone),
mmonnin (Overclock.net) и Aleksander Parkitny (BOINC@Poland),
boceli (Czech National Team) и zzuupp (TeAm AnandTech),
respawner (Rechenkraft.net) и Jacob Rumbolt (Canadian Circuitry),
Death (Ukraine) и Kalomel (BOINC@Poland),
Landjunge (Planet 3DNow!) и Gibson Praise (Picard),
Stimpy (Rechenkraft.net) и Michael H.W. Weber (Rechenkraft.net),
XSmeagolX (SETI.Germany) и joe carnivore (Planet 3DNow!),
Daniel (BOINC@AUSTRALIA) и Egon olsen (Meisterkuehler.de Team),
fix и [AF>Libristes]MortelKni (L'Alliance Francophone),
igos и [AF>Kirass>MPF] Nafrayou (L'Alliance Francophone),
the-who (Team China) и xAznboyzx (BOINCstats),
ext2097 (SETIKAH@KOREA) и GLeeM (TeAm AnandTech),
ClaudiusD (Rechenkraft.net) и ID4 (SETI.Germany),
[AF>Amis des Lapins] Ceclo (L'Alliance Francophone) и MorAlex,
okuzonosb (Team China) и phoenicis ([H]ardOCP),
HK-Steve (Crunching@EVGA) и Scoope (Rechenkraft.net),
[DPC] hansR (Dutch Power Cows) и nenym (Czech National Team),
herby44 (Planet 3DNow!) и vinn@[CNT] (Czech National Team),
crashtech (TeAm AnandTech) и Shaman (Czech National Team),
Karelian Center for Gender Studies (Karelia) и Kodeks IT (Karelia),
[SG-2W]Kurzer (SETI.Germany) и JagDoc (Planet 3DNow!),
Odicin (BOINC Confederation) и k4m1k4z3 (Overclock.net),
spinner@ и [AF] Skinny06 (L'Alliance Francophone),
BritishBob (Overclock.net) и sergamena (Russia Team),
Dmitriy Otroschenko (Ukraine) и entigy (Team England (Boinc)),
meadoel (BOINCstats) и declis (Rechenkraft.net),
kashi (BOINC@AUSTRALIA) и DuanJiaming (Team China),
purplecfh (SETI.USA) и polarbeardj (Crunching@EVGA),
Crunch3r (BOINC United) и ale4316 (Ukraine),
jondi_hanluc (OcUK - Overclockers UK) и zioriga (BOINC.Italy),
firstomega (Rechenkraft.net) и ShmyaCluster (Crystal Dream),
EG (SETI.USA) и Cocagne (L'Alliance Francophone),
pah (L'Alliance Francophone) и forest (Czech National Team),
sorcrosc (BOINC.Italy) и [SG-FC]shka (SETI.Germany),
[AF>Libristes] Elorak (L'Alliance Francophone) и WTBroughton,
Gusek (Russia Team) и Rudy Toody (TeAm AnandTech),
Chipotle (Ars Technica) и Dan Sargent (SETI.USA),
n3Ro (Meisterkuehler.de Team) и Yi-Ming Wang (Team China),
Jeff17 (BOINCstats) и Matthias Lehmkuhl (SETI.Germany),
Giero (BOINC@Poland) и RFGuy_KCCO ([H]ardOCP),
glennpat (XtremeSystems) и MajkPascal (BOINC@Poland),
europe64 (europe64) и Cruncher Pete (BlackOps),
Viktor Svantner (Czech National Team) и Pushok (Russia Team),
whowhere (AUGE@BOINC) и DoctorNow (BOINC@Heidelberg),
StyM (XtremeSystems) и Wabi CZ (Czech National Team),
[AF>Kirass>MPF] Kikiphil (L'Alliance Francophone).
Новости "одной строкой":
Выложили ещё одну партию из 5 типов графов, обнаруженных в проекте - New graphs from 2018-06-14
Выложена очередная партия результатов с найденными "перестановочными парами" ОДЛК
Вычислительная мощность проекта - вновь возросла, за сутки сейчас перемалывается около 32 тысяч workunit-ов и это очень здорово! Метрика производительности уже несколько дней - возле 37 TFLOPS, сейчас "Current GigaFLOPS: 36955.95", что, пусть она и в некоторой степени условная - не может не радовать.
Отредактировано пользователем 15 июня 2018 г. 15:51:52(UTC) |
Новые графы от 2018.06.30!
Уважаемые участники!
На странице предварительных результатов опубликованы следующие 6 типов графов из ОДЛК наденные в проекте RakeSearch.
[R9_000091371/01] - 12 вершин и 21 ребра. Небольшой граф в виде симметричной фигуры. Ещё один "спутник"? (А раз маленький - кубосат? ) Или что-то ещё? Что вы думаете?
Большое спасибо за участие в проекте!
Ещё немного новостей проекта. 25 июля 2018 г
Как, возможно, вы помните, ранее мы upgrade-или сервер, на котором расположена виртуальная машина с проектом. После - удалось достать ещё 2 радиатора и CPU с HDD, которые также пошли в дело. Наращивание RAM позволило перейти к поиску настроек кэшей MySQL, которые позволили бы базе быстрее обрабатывать запросы. Сначала мы увеличили несколько из них и обработка запросов стала побыстрее, но в моменты пиковых нагрузок со стороны соседей по серверу или чистки базы от старых workunit-ов и result-ов - производительность иногда очень сильно падала. Вчера утром нарастили ещё один из кэшей и это изменение, насколько вижу - дало очень хороший результат - чистка базы стала проходить в разы быстрее, а запросы от процессов BOINC-сервера - вообще почти никогда не пересекаются.
Теперь, с одной стороны, будет меньше времени уходить на техническое обслуживание базы, а с другой - теперь сервер сможет обрабатывать намного больше запросов!
Ну и получен ещё некоторый опыт в управлении всем этим хозяйством.
