Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
В проекте RakeSearch завершена обработка очередных (49-го и 50-го) интересных ДЛК порядка 12
0 1 2 3 4 5 6 7 8 9 10 11
1 2 0 4 5 3 8 6 7 11 9 10
3 4 5 0 1 2 9 10 11 6 7 8
11 10 9 8 7 6 5 4 3 2 1 0
10 9 11 7 6 8 3 5 4 0 2 1
6 8 7 9 11 10 1 0 2 4 3 5
4 5 3 1 2 0 11 9 10 8 6 7
9 11 10 6 8 7 4 3 5 1 0 2
7 6 8 10 9 11 0 2 1 3 5 4
5 3 4 2 0 1 10 11 9 7 8 6
8 7 6 11 10 9 2 1 0 5 4 3
2 0 1 5 3 4 7 8 6 10 11 9
и
0 1 2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 0 8 10 11 7 6 9
9 7 10 6 8 11 1 5 2 4 0 3
2 3 4 5 0 1 11 6 9 10 8 7
7 10 6 8 11 9 2 0 3 5 1 4
10 6 8 11 9 7 3 1 4 0 2 5
6 8 11 9 7 10 4 2 5 1 3 0
3 4 5 0 1 2 9 8 7 6 11 10
5 0 1 2 3 4 10 9 6 11 7 8
11 9 7 10 6 8 0 4 1 3 5 2
4 5 0 1 2 3 7 11 10 8 9 6
8 11 9 7 10 6 5 3 0 2 4 1
у которых соответственно 25280 и 25288 диагональных трансверсалей и 487895876 и 468979501 ОДЛК, что позволяет им занять 38-е и 41-е места в соответствующем спектре, который на данный момент включает в своем составе 5846 элементов и доступен тут:
https://evatutin.narod.ru/spectra/spectrum_dls_odls_n12_xxxx_known_items.txt
Загруженные файлы:
А какие перспективы на будущее, - примерно сколько лет планируется вести исследования в RakeSearch?
Также не забываем, что под новый год по проекту будет соревнование https://www.boincstats.com/stats/challenge/team/chat/1126
Случайная распределенная диагонализация спектров
Итак, мы подошли к завершающему этапу построения спектров диагональных трансверсалей (в первую очередь) и трансверсалей общего вида (если повезет) для ДЛК порядка 14. На данном этапе ранее в течение чуть более чем года расчетов были выполнены эксперименты с различными специальными типами ДЛК, построением опорных спектров от них с их последующим расширением. На данный момент возможности данных экспериментов себя исчерпали и необходимо двигаться далее другими способами. Для меньших размерностей задачи 10 <= N <= 13 далее мы выполняли тотальную диагонализацию квадратов в составе полученных интегральных спектров, что обеспечило прибавку в несколько десятков процентов к мощностям спектров. Начиная с порядка N=12 некоторые квадраты (например, топовые с 198144 трансверсалями) диагонализировались в однопоточном режиме до недели, что потребовало разработки распределенной версии диагонализатора с целью ее запуска в проекте RakeSearch. Диагонализация квадратов спектров для порядка N=13 с ее использованием оказалась вычислительно сложной и растянулась аж на полгода расчетов в проекте. Для текущего обрабатываемого порядка N=14 по оценкам тотальная диагонализация будет выполняться около 70 лет, что неприемлимо и вынуждает искать путь к ее упрощению (эвристики добрались и до этого преобразования). В настоящий момент в хронологическом порядке было сделано следующее.
1. Был тотально продиагонализирован топовый по числу трансверсалей ДЛК (несколько недель расчетов в проекте RakeSearch) — установлено наиболее сильное из известных нижнее ограничение на максимальное значение числа трансвералей.
2. Была тотально продиагонализирована младшая часть спектра числа диагональных трансверсалей (младшие и самые легкие 10 тыс. ДЛК из 297 тыс., около месяца расчетов в проекта RakeSearch) — установлено наиболее сильное из известных верхнее ограничение на минимальное значение числа трансвералей.
Остальную (среднюю) часть спектра будем диагонализировать эвристически, по частям. Для этого был немного поправлен соответствующий код расчетника и следом был организован соответствующий вычислительный эксперимент. При его выполнении ДЛК из средней части спектра выбирался случайно, далее случайно выбиралась квадратная область в двумерной плоскости с номерами трансверсалей, в ее составе находились подходящие пары трансверсалей, непосредственно диагонализацией устанавливались на диагонали формируемого ДЛК с последующей попыткой получением нового значения в формируемый спектр. Результаты короткого недельного эксперимента показали, что стратегия выбрана верно и спектр числа диагональных трансверсалей удалось расширить с 282142 до 294941 элемента (тотальная диагонализация младшей части спектра) и затем до 297125 элементов (первая попытка случайной диагонализации средней части спектра, преобразование работает, как и ранее!). Однако при выполнении случайной диагонализации вскрылась еще одна сложность: с ростом порядка N растет еще и размер файлов спектров в байтах (как за счет роста мощности, так и за счет увеличения числа ячеек в подтверждающих квадратах). Результатом выполнения первого пристрелочного запуска оказалось 18 ГБ данных для постобработки. Не то, чтобы это невозможно, постобработка была выполнена, но работать с таким объемом данных как минимум долго и неудобно, в особенности с учетом того, то большинство значений спектра ранее уже были получены, в настоящее время не представляют интереса и просто отбрасываются (они могут пригодиться в будущем в составе других экспериментов со случайным блужданием спектров, но это в будущем). Отбрасывать повторные значения можно и на клиенте после выполнения основной части кода расчетного модуля, но тогда при старте каждой WU'шки расчетнику придется передавать текущий спектр, который весит около 60 МБ, что тоже реализуемо (в BOINC'е есть всякие soft link'и например), но не очень эффективно. Вместо этого на клиент теперь передается обрезанная версия спектра (множество значений без подтверждающих квадратов) объемом около 2 МБ, с ее использованием производится необходимый расчет, а уже известные значения отбрасываются на клиенте без передачи на сервер проекта. В настоящее время первая пристрелочная фаза эксперимента завершена (на обработку 10 тыс. WU'шек потребовалось около 3 суток расчетов в проекте), в ближайшее время приступим к анализу полученных результатов, от которых ожидается как существенно меньший объем результирующих данных, так и новые значения в спектре...
Ну и в заключение напомню, что целью текущего эксперимента является расширение мощностей спектров трансверсалей. Указанные спектры имеют полосатую структуру (см. рис.), сплошные участки нами почти выбраны (но не полностью, там вполне могут сидеть отдельные еще не найденные квадраты), а белые полосы ("запрещенные зоны") то ли в принципе не содержат ДЛК по какой-то причине, то ли просто тип живущих там квадратов достаточно редок и попадание хотя бы одним квадратом в данную область может привести к ее последующему полному заполнению квадратами из его окрестности. А вдруг нам повезет и в рамках запрещенных зон живут квадратные полупроводники? 
Будем искать и анализировать результаты...
Цитата: Yura12 от 04.12.2024, 14:00
А какие перспективы на будущее, - примерно сколько лет планируется вести исследования в RakeSearch?
Также не забываем, что под новый год по проекту будет соревнование https://www.boincstats.com/stats/challenge/team/chat/1126
1 — пока мне и коллегам не надоест, в ближайшее время прекращать расчет не планируем :).
2 — соревнования — это хорошо, быстрее посчитаем текущие эксперименты!
Первый же анализ результатов нового эксперимента в полной мере подтвердил его целесообразность! Немного статистики:
* обсчитанное число WU'шек — 10 тыс. (средняя длительность счета ~1 час, приемлимо, более мелкое дробление не требуется)
* общее время расчета в проекте (включая хвосты) — 3 дня
* из 10 тыс. WU'шек 318 (3,18%) дали новые значения в спектр, с течением времени данный процент будет уменьшаться
* 318 WU'шек с новыми результатами (каждая из них это какой-то один ДЛК в спектре) дали +7098 новых значений в спектр, дальше будут работать замыкания окрестностями
* объем трафика результатов расчета — 2,5 МБ в архиве (4,8 МБ в распакованном виде), с предыдущими 8/18 ГБ ни в какое сравнение не идет
А насколько реально сейчас, в данных условиях, реализовать данный алгоритм расчётов на каком нибудь FPGA / ПЛИС чтобы их один раз запрограммировать и часть работы перевести на них?
Цитата: Yura12 от 05.12.2024, 05:27А насколько реально сейчас, в данных условиях, реализовать данный алгоритм расчётов на каком нибудь FPGA / ПЛИС чтобы их один раз запрограммировать и часть работы перевести на них?
Это большая работа, сейчас я не готов давать какие-либо оценки.
У вас под руками есть ПЛИСы, на которых можно считать?
В проекте RakeSearch завершена обработка очередного (51-го) интересного ДЛК порядка 12
0 1 2 3 4 5 6 7 8 9 10 11
1 2 0 4 7 6 10 3 11 8 5 9
5 6 10 11 9 0 1 8 7 4 2 3
6 10 5 9 8 1 2 11 3 7 0 4
8 11 9 5 6 7 3 10 2 1 4 0
9 8 11 10 5 4 7 6 1 0 3 2
7 3 4 0 1 8 11 2 10 6 9 5
4 7 3 2 0 9 8 1 6 5 11 10
3 4 7 1 2 11 9 0 5 10 8 6
10 5 6 8 11 2 0 9 4 3 1 7
11 9 8 6 10 3 4 5 0 2 7 1
2 0 1 7 3 10 5 4 9 11 6 8
у которого 25274 диагональных трансверсали и 509396858 ОДЛК, что позволяет ему занять 34-е место в соответствующем спектре, который на данный момент включает в своем составе 5850 элементов и доступен тут:
https://evatutin.narod.ru/spectra/spectrum_dls_odls_n12_xxxx_known_items.txt
Загруженные файлы:
Цитата: evatutin от 05.12.2024, 22:51Цитата: Yura12 от 05.12.2024, 05:27А насколько реально сейчас, в данных условиях, реализовать данный алгоритм расчётов на каком нибудь FPGA / ПЛИС чтобы их один раз запрограммировать и часть работы перевести на них?
Это большая работа, сейчас я не готов давать какие-либо оценки.
У вас под руками есть ПЛИСы, на которых можно считать?
Нет, у меня их нет.
Вопрос задавался как оценка перспектив на будущее.