Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
В продолжение к предыдущему посту, проанализируем, какие структуры длин циклов вообще встречаются среди ESODLS CMS кроме уже известных по 1-КФным находкам (однушки, линии-4 и циклы-4). Мультимножества длин циклов для ESODLS CMS:
N=1
0: {1:1} <-— тривиальная схема
N=2
0: {1:4} <-— тривиальная схема
1: {1:2, 2:1} <-— каноническая схема
2: {2:2}
3: {4:1}
N=3
0: {1:9} <-— тривиальная схема
1: {1:3, 2:3} <-— каноническая схема
2: {1:1, 4:2}
3: {1:1, 2:4}
N=4
0: {1:16} <-— тривиальная схема
1: {1:4, 2:6} <-— каноническая схема
2: {2:8}
3: {4:4}
N=5
0: {1:25} <-— тривиальная схема
1: {1:5, 2:10} <-— каноническая схема
2: {1:1, 4:6}
3: {1:1, 2:12}
4: {1:9, 2:8}
N=6
0: {1:36} <-— тривиальная схема
1: {1:6, 2:15} <-— каноническая схема
2: {2:18}
3: {4:9}
4: {1:4, 2:16}
5: {3:12}
6: {3:2, 6:5}
7: {6:6}
8: {12:3}
9: {1:16, 2:10}
10: {1:8, 2:14}
11: {1:4, 4:8}
12: {1:2, 2:1, 4:8}
13: {2:2, 4:8}
14: {1:4, 2:6, 4:5}
N=7
0: {1:49} <-— тривиальная схема
1: {1:7, 2:21} <-— каноническая схема
2: {1:1, 4:12}
3: {1:9, 2:20}
4: {1:3, 2:23}
5: {1:1, 3:16}
6: {1:1, 3:2, 6:7}
7: {1:1, 12:4}
8: {1:25, 2:12}
9: {1:15, 2:17}
10: {1:1, 2:24}
11: {1:1, 6:8}
12: {1:9, 4:10}
13: {1:3, 2:3, 4:10}
14: {1:5, 2:10, 4:6}
15: {1:1, 2:4, 4:10}
N=8
0: {1:64} <-— тривиальная схема
1: {1:8, 2:28} <-— каноническая схема
2: {2:32}
3: {4:16}
4: {1:16, 2:24}
5: {1:4, 3:20}
6: {1:2, 2:1, 3:2, 6:9}
7: {2:2, 6:10}
8: {4:1, 12:5}
9: {1:36, 2:14}
10: {1:12, 2:26}
11: {1:4, 2:30}
12: {2:2, 3:12, 6:4}
13: {2:2, 3:4, 6:8}
14: {8:8}
15: {1:4, 6:10}
16: {2:8, 4:12}
17: {1:4, 2:6, 4:12}
18: {1:16, 4:12}
N=9
0: {1:81} <-— тривиальная схема
1: {1:9, 2:36} <-— каноническая схема
2: {1:1, 4:20}
3: {1:25, 2:28}
4: {1:5, 2:38}
5: {1:9, 3:24}
6: {1:3, 2:3, 3:2, 6:11}
7: {1:1, 4:2, 12:6}
8: {1:1, 2:40}
9: {1:49, 2:16}
10: {1:21, 2:30}
11: {1:1, 2:4, 3:16, 6:4}
12: {1:3, 2:3, 3:6, 6:9}
13: {1:1, 8:10}
14: {1:9, 6:12}
15: {1:1, 2:12, 4:14}
16: {1:5, 2:10, 4:14}
17: {1:25, 4:14}
18: {1:1, 2:4, 6:12}
19: {1:9, 2:8, 4:14}
N=10
0: {1:100} <-— тривиальная схема
1: {1:10, 2:45} <-— каноническая схема
2: {2:50}
3: {4:25} <-— схема, соответствующая 1-КФным циклам-4
4: {1:36, 2:32}
5: {1:16, 3:28}
6: {1:4, 2:6, 3:2, 6:13}
7: {2:8, 6:14}
8: {4:4, 12:7}
9: {1:4, 4:24}
10: {1:2, 2:1, 4:24}
11: {2:2, 4:24}
12: {5:20}
13: {5:2, 10:9}
14: {10:10}
15: {20:5}
16: {1:4, 2:48}
17: {2:8, 3:12, 6:8}
18: {1:64, 2:18}
19: {1:16, 2:42}
20: {1:8, 2:46}
21: {1:4, 2:6, 3:20, 6:4}
22: {1:4, 2:6, 3:4, 6:12}
23: {1:4, 8:12}
24: {1:2, 2:1, 8:12}
25: {2:2, 8:12}
26: {4:1, 8:12}
27: {1:16, 6:14}
28: {2:8, 3:8, 6:10}
29: {3:12, 4:4, 12:4}
30: {3:2, 4:4, 6:5, 12:4}
31: {4:4, 6:6, 12:4}
32: {1:4, 2:6, 12:7}
33: {1:4, 2:16, 4:16}
34: {1:6, 2:15, 4:16}
35: {2:18, 4:16}
36: {1:4, 2:6, 4:21}
37: {1:36, 4:16}
38: {1:24, 2:38}
39: {1:4, 2:6, 6:14}
40: {1:16, 2:10, 4:16}
41: {1:8, 2:14, 4:16}
42: {1:8, 2:28, 4:9}
Как видно, разновидностей схем довольно много. Всем ли из них соответствуют ESODLS? Будем проверять...
Результаты поиска КФ ОДЛК в проекте Gerasim@Home за месяц:
ONCE (A):1
1 CFs - 32022 (+2)
LINE3 (B):1 - 59179, where:
2 CFs - 18735
3 CFs - 40444 (+1948)
LINE3 (B):2 - 38957, where:
2 CFs - 18735
3 CFs - 20222 (+974)
LINE4 (C):1 - 99, where:
2 CFs - 3
4 CFs - 96 (+4)
LINE4 (C):2 - 99, where:
2 CFs - 3
4 CFs - 96 (+4)
LINE5 (D):1 - 17, where:
3 CFs - 17
LINE5 (D):2 - 34, where:
3 CFs - 34
LOOP4 (E):2 - 2240, where:
1 CFs - 2
2 CFs - 138
3 CFs - 1464
4 CFs - 636
1TO3 (F):1 - 333, where:
4 CFs - 333 (+3)
1TO3 (F):3 - 111, where:
4 CFs - 111 (+1)
1TO4 (G):1 - 1282, where:
3 CFs - 882
5 CFs - 400 (+8)
1TO4 (G):4 - 541, where:
3 CFs - 441
5 CFs - 100 (+2)
1TO5 (k):1 - 10, where:
6 CFs - 10
1TO5 (k):5 - 2, where:
6 CFs - 2
1TO6 (H):1 - 42, where:
4 CFs - 24
7 CFs - 18
1TO6 (H):6 - 11, where:
4 CFs - 8
7 CFs - 3
1TO7 (h):1 - 7, where:
8 CFs - 7
1TO7 (h):7 - 1, where:
8 CFs - 1
1TO8 (I):1 - 48, where:
5 CFs - 32
9 CFs - 16
1TO8 (I):8 - 10, where:
5 CFs - 8
9 CFs - 2
RHOMBUS3 (J):2 - 9, where:
5 CFs - 9
RHOMBUS3 (J):3 - 6, where:
5 CFs - 6
RHOMBUS4 (K):2 - 73, where:
3 CFs - 2
4 CFs - 23
5 CFs - 32
6 CFs - 16
RHOMBUS4 (K):4 - 34, where:
3 CFs - 1
4 CFs - 17
5 CFs - 8
6 CFs - 8
FISH (N):1 - 7, where:
4 CFs - 1
6 CFs - 6
FISH (N):2 - 11, where:
4 CFs - 2
6 CFs - 9
FISH (N):4 - 4, where:
4 CFs - 1
6 CFs - 3
TREE1 (V):1 - 2, where:
4 CFs - 2
TREE1 (V):2 - 1, where:
4 CFs - 1
TREE1 (V):3 - 1, where:
4 CFs - 1
CROSS (X):1 - 16, where:
6 CFs - 16
CROSS (X):2 - 4, where:
6 CFs - 4
CROSS (X):4 - 4, where:
6 CFs - 4
DAEDALUS10 (i):1 - 6, where:
12 CFs - 6
DAEDALUS10 (i):2 - 4, where:
12 CFs - 4
DAEDALUS10 (i):4 - 1, where:
12 CFs - 1
DAEDALUS10 (i):10 - 1, where:
12 CFs - 1
FLYER (j):1 - 2, where:
8 CFs - 2
FLYER (j):2 - 3, where:
8 CFs - 3
FLYER (j):4 - 3, where:
8 CFs - 3
VENUS (l):1 - 1, where:
5 CFs - 1
VENUS (l):2 - 3, where:
5 CFs - 3
VENUS (l):4 - 1, where:
5 CFs - 1
DAEDALUS8 (m):1 - 2, where:
6 CFs - 2
DAEDALUS8 (m):2 - 2, where:
6 CFs - 2
DAEDALUS8 (m):4 - 1, where:
6 CFs - 1
DAEDALUS8 (m):8 - 1, where:
6 CFs - 1
RHOMBUS5 (n):2 - 4, where:
5 CFs - 4
RHOMBUS5 (n):5 - 1, where:
5 CFs - 1
1TO10 (o):1 - 5, where:
6 CFs - 5
1TO10 (o):10 - 1, where:
6 CFs - 1
ROBOT (p):1 - 4, where:
5 CFs - 4
ROBOT (p):2 - 4, where:
5 CFs - 4
ROBOT (p):4 - 2, where:
5 CFs - 2
STINGRAY (q):1 - 1, where:
5 CFs - 1
STINGRAY (q):2 - 3, where:
5 CFs - 3
STINGRAY (q):3 - 1, where:
5 CFs - 1
Окрестности обобщенных симметрий: пройдено 354 (+26) из 903 (39,2%, +2,9%).
Поиск ESODLS:
* exp405 — найдено 4 новых КФ из 6 (4/6);
* exp406 — 4/11;
* exp407 — 2/10
* exp408 — 2/8.
В основной подпроект проекта добавлена новая версия расчетного модуля 3.0.6, в ней ряд изменений.
1. Поправлен код для старых WU'шек, которые не могли досчитаться (спасибо yura12 за ряд замечаний по этому поводу, наконец-то дошли руки).
2. Для экспериментов exp43 (поиск по линейкам) и exp405...exp408 (поиск ESODLS) добавлены постобработчики с использованием простых преобразований.
3. Самое главное на мой взгляд: в код построения ESODLS внесен ряд изменений, связанных с вариацией порядка рассмотрения ячеек заполняемого ДЛК. Для размерности N=8, на которой проводилось тестирование, время на получение одного решения (одной КФ ESODLS) сокращается с 4.1 с до 0.248 с (в 16 раз). Если для размерности N=10 соотношение будем тем же самым, выход интересных КФов ESODLS должен прилично возрасти с текущей цифры ~ 2 новых КФ в месяц. Ждем и надеемся...
Так а ведь приложение Test separator осталось не обновлённым! http://gerasim.boinc.ru/users/viewApps.aspx
А как раз те серии, которые не могли досчитаться 276, 277, 279 они относятся ведь не к основному приложению, а как раз к Test separator !
Так что и его тоже надо менять.
Для произвольных CMS ESODLS был реализован расчетный полнопереборный код, который интегрирован в состав расчетного модуля версии 3.0.7, добавленного в основной подпроект проекта. В нем, в отличие от прошлой версии экспериментов с ESODLS, производится формирование всех CMS ESODLS (не только канонических, как ранее), ну а далее для выбранной схемы производится поиск соответствующих ей ESODLS. Первые WU'шки этой серии экспериментов имеют имя *_e674_*, время счета — 20 минут, кворум — 1, дедлайн — 7 дней. Интересно, найдется ли что-то новенькое от неканонических схем...
На самом деле счёт одного задания приложением 3.0.7 не 20, а 40 минут!!!
У меня 18 - 21 минута на задание. Мобильный I5 3360 частота 2.7 .
Плохие новости. На одном из компьютеров прямо на рабочем столе появилось 2 окна с ошибкой. Скриншот приложен.
Вот этот компьютер: http://gerasim.boinc.ru/users/viewHostResults.aspx?hostid=46609
Если такие ошибки полезут с других программ, служб - у Вас проблема с оперативной памятью. Ключевое слово ЕСЛИ.