Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только... - Страница 93 - Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только... - Страница 93 - Форум

#921 · 17.04.2021, 18:56

А эта новая версия она включает в себя оптимизации для ускорения счёта? Если да, то примерно на какой процент ожидается ускорение?

#922 · 20.04.2021, 00:40

Цитата: evatutin от 20.04.2021, 00:40
Распределенный DLX (DDLX)

Не так давно в проекте была анонсирована (см. https://vk.com/wall162891802_1643) обработка интересных квадратов порядка 12, потенциально обладающих как большим числом трансверсалей, так и большим числом ОДЛК. Их обработка позволила существенно поднять нижнюю границу на максимальное число ОДЛК к одному ДЛК для порядка 12 (было — несколько десятков тысяч, стало — более 700 тысяч, на данный момент рекорд, см. анонс https://vk.com/wall162891802_1649). Однако обработка квадратов данного типа, кроме серии мелких недоработок в расчетном коде, выявила одну серьезную неприятность: их обработка может вестись десятками часов. До этого такое подозрение существовало, а тут проблема встала в полный рост. И виноват в этом DLX, для которого в данном случае получается слишком большая бинарная матрица для поиска покрытий, обработка которой и отнимает кучу времени (известный комбинаторный взрыв в данном случае происходит именно на этой размерности). Оптимизировать этот кусок кода не получится, т.к. он давно оптимизирован, а вот попробовать распараллелить можно...

Это не так просто, как может показаться на первый взгляд, т.к. DLX — довольно эффективный, но и в то же самое время довольно мудреный алгоритм, просто так "в лоб" на параллельно выполняемые куски его не разобьешь. Однако можно заметить, что большой квадрат состоит из отдельных ячеек (для порядка 12 их 12^2=144), а это значит, что их можно попробовать обрабатывать параллельно... Простейшей реализацией этой идеи является распараллеливание по первой строке квадрата, однако это даст только N (в нашем случае — 12) параллельно выполняемых подзадач. Для многоядерного CPU с 12 ядрами, идеально подходящего для решения данной задачи, это подойдет. При переходе на размерность N=13 правда придется искать на рынке 13-ядерник, задача не из легких, но надо же науку двигать вперед! Однако для грида с тысячами многоядерных CPU это слишком мало и необходима бОльшая степень параллелизма. Можно конечно же распараллелить по всем ячейкам квадрата, но это даст всего 144 параллельных независимых подзадачи, что тоже мало. На помощь приходит floating point арифметика, которую до этого в квадратных задачах мы не использовали, а зря... Если очень просто описать идею, то, например, в квадрате A

0 6 9 1 3 4 10 5 2 7 11 8
2 1 3 0 11 8 5 10 9 4 6 7
5 3 2 4 8 9 1 11 6 10 7 0
6 7 8 3 10 11 9 4 0 5 2 1
1 10 11 7 4 0 8 9 5 6 3 2
7 2 10 8 9 5 4 6 1 11 0 3
8 11 0 10 5 7 6 2 3 1 9 4
9 8 5 6 2 3 11 7 4 0 1 10
10 9 6 11 7 2 0 1 8 3 4 5
11 4 1 5 0 10 2 3 7 9 8 6
4 5 7 2 1 6 3 0 11 8 10 9
3 0 4 9 6 1 7 8 10 2 5 11

A[0][0] = 0, тут ничего не поделаешь. А вот A[0][1] = 6, что дает нам следующие разбиения:

0.1 + 5.9 = 6.0
0.2 + 5.8 = 6.0
...

0.1 + 0.1 + 5.8 = 6.0
0.1 + 0.2 + 5.7 = 6.0
...

ну и т.д., идея думаю ясна. Поступая аналогичным образом с другими ячейками обрабатываемого квадрата, можно фактически разбить его на floating point куски, которые можно по отдельности скормить DLX'у параллельно! Причем невооруженным глазом видно, что степень параллелизма будет существенно выше — как раз то, что нужно гриду. Данная идея была апробирована сперва на моей машине, а потом и в проекте Gerasim@Home (http://gerasim.boinc.ru), точнее — в подпроекте ODLS BS, новая версия расчетного модуля 1.3.6. В перспективе можно подумать над тем, что еще можно задействовать и отрицательные числа, например так

0 = -0.2 + 0.1 + 0.1

но это в перспективе, когда руки дойдут, пока и так неплохо работает...

При подобной обработке ДЛК на предмет наличия у них ОДЛК возникает несколько проблем.

1. Как подсунуть DLX'у с его хитрой динамической организацией данных в виде тора с кольцевыми ссылками единиц друг на друга дробление на подзадачи (поверьте, это оказалось непросто и получилось далеко не сразу).
2. Как обеспечить отсутствие дублей среди находимых покрытий в различных подзадачах (каждому покрытию взаимно однозначно соответствует ОДЛК).
3. Некоторые WU'шки не содержат покрытий (и, соответственно, ОДЛК), выполняются за 1-2 с и только мешаются под ногами, в то время как настоящие боевые WU'шки считаются по 10-20 минут. Как их отсечь?

Все проблемы удалось решить, получаемые числа ОДЛК для последовательной и распределенной реализаций совпадают, однако тестирование еще не завершено... Первая проблема решается поиском нужной единицы в составе тора и выполнении для нее соответствующей операции cover(), являющейся основой алгоритма DLX (тут для понимания деталей рекомендую оригинальную статью Д. Кнута, там есть картинки и псевдокод). Вторая проблема решается хитрым сбросом в ноль части строк в начале матрицы покрытия (но не всех подряд, тут тоже есть тонкость!). Третья проблема (по крайней мере частично, тестирование еще не завершено) решается путем отсечения части WU'шек выше t_max, где t_max — эмпирически определяемая граница, индивидуальная для каждого обрабатываемого ДЛК и скорее всего связанная с максимальным допустимым номером трансверсали, входящей в состав покрытий.

Теперь от теории к практике. В проект была добавлена серия WU'шек с именами wu_e1055_n12_ddlx_..., в составе которых был обработан квадрат

0 1 2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 7 9 11 0 8 6 10
9 0 1 10 2 6 5 8 11 7 4 3
11 10 5 7 9 3 0 2 1 6 8 4
3 8 7 0 6 10 11 9 5 4 2 1
10 9 8 2 7 11 3 5 4 0 1 6
4 5 9 6 1 2 8 10 3 11 0 7
5 3 6 1 0 8 7 4 9 10 11 2
6 11 4 5 3 9 2 0 10 1 7 8
2 6 10 8 11 1 4 3 7 5 9 0
7 4 11 9 8 0 10 1 6 2 3 5
8 7 0 11 10 4 1 6 2 3 5 9

Он имеет 1 ОДЛК и последовательным кодом обрабатывается за 40 секунд. Распределенная обработка в проекте велась исключительно ради тестирования, WU'шки были длительностью 1-2 с, искомый единственный ОДЛК был успешно найден, дублей зафиксировано не было. Сейчас выполняется задачка посложнее: ОДЛК ищутся для квадрата

0 1 2 3 4 5 6 7 8 9 10 11
1 2 0 4 5 3 8 6 7 11 9 10
10 9 11 7 6 8 3 5 4 0 2 1
2 3 4 5 0 1 10 11 6 7 8 9
11 10 9 8 7 6 5 4 3 2 1 0
9 8 7 6 11 10 1 0 5 4 3 2
6 11 10 9 8 7 4 3 2 1 0 5
8 7 6 11 10 9 2 1 0 5 4 3
5 0 1 2 3 4 7 8 9 10 11 6
7 6 8 10 9 11 0 2 1 3 5 4
4 5 3 1 2 0 11 9 10 8 6 7
3 4 5 0 1 2 9 10 11 6 7 8

который на настоящий момент держит рекорд по известному числу ОДЛК, равному 713258. Эту цифру необходимо получить по результатам расчетов в проекте, считаем и ждем... Последовательной реализации на это потребовалось 24 часа, посмотрим, за сколько управится параллельная распределенная, на данный момент обработка идет полным ходом, WU'шек длиннее 25 минут на моей машине пока не попалось.

Ну а дальше, если все будет работать корректно, расчет "тяжелых" ДЛК можно будет организовать достаточно просто и эффективно, никаких десятков часов без чекпоинтов не будет. Считаем...

Распределенный DLX (DDLX)

Не так давно в проекте была анонсирована (см. https://vk.com/wall162891802_1643) обработка интересных квадратов порядка 12, потенциально обладающих как большим числом трансверсалей, так и большим числом ОДЛК. Их обработка позволила существенно поднять нижнюю границу на максимальное число ОДЛК к одному ДЛК для порядка 12 (было — несколько десятков тысяч, стало — более 700 тысяч, на данный момент рекорд, см. анонс https://vk.com/wall162891802_1649). Однако обработка квадратов данного типа, кроме серии мелких недоработок в расчетном коде, выявила одну серьезную неприятность: их обработка может вестись десятками часов. До этого такое подозрение существовало, а тут проблема встала в полный рост. И виноват в этом DLX, для которого в данном случае получается слишком большая бинарная матрица для поиска покрытий, обработка которой и отнимает кучу времени (известный комбинаторный взрыв в данном случае происходит именно на этой размерности). Оптимизировать этот кусок кода не получится, т.к. он давно оптимизирован, а вот попробовать распараллелить можно...

Это не так просто, как может показаться на первый взгляд, т.к. DLX — довольно эффективный, но и в то же самое время довольно мудреный алгоритм, просто так "в лоб" на параллельно выполняемые куски его не разобьешь. Однако можно заметить, что большой квадрат состоит из отдельных ячеек (для порядка 12 их 12^2=144), а это значит, что их можно попробовать обрабатывать параллельно... Простейшей реализацией этой идеи является распараллеливание по первой строке квадрата, однако это даст только N (в нашем случае — 12) параллельно выполняемых подзадач. Для многоядерного CPU с 12 ядрами, идеально подходящего для решения данной задачи, это подойдет. При переходе на размерность N=13 правда придется искать на рынке 13-ядерник, задача не из легких, но надо же науку двигать вперед! Однако для грида с тысячами многоядерных CPU это слишком мало и необходима бОльшая степень параллелизма. Можно конечно же распараллелить по всем ячейкам квадрата, но это даст всего 144 параллельных независимых подзадачи, что тоже мало. На помощь приходит floating point арифметика, которую до этого в квадратных задачах мы не использовали, а зря... Если очень просто описать идею, то, например, в квадрате A

0 6 9 1 3 4 10 5 2 7 11 8
2 1 3 0 11 8 5 10 9 4 6 7
5 3 2 4 8 9 1 11 6 10 7 0
6 7 8 3 10 11 9 4 0 5 2 1
1 10 11 7 4 0 8 9 5 6 3 2
7 2 10 8 9 5 4 6 1 11 0 3
8 11 0 10 5 7 6 2 3 1 9 4
9 8 5 6 2 3 11 7 4 0 1 10
10 9 6 11 7 2 0 1 8 3 4 5
11 4 1 5 0 10 2 3 7 9 8 6
4 5 7 2 1 6 3 0 11 8 10 9
3 0 4 9 6 1 7 8 10 2 5 11

A[0][0] = 0, тут ничего не поделаешь. А вот A[0][1] = 6, что дает нам следующие разбиения:

0.1 + 5.9 = 6.0
0.2 + 5.8 = 6.0
...

0.1 + 0.1 + 5.8 = 6.0
0.1 + 0.2 + 5.7 = 6.0
...

ну и т.д., идея думаю ясна. Поступая аналогичным образом с другими ячейками обрабатываемого квадрата, можно фактически разбить его на floating point куски, которые можно по отдельности скормить DLX'у параллельно! Причем невооруженным глазом видно, что степень параллелизма будет существенно выше — как раз то, что нужно гриду. Данная идея была апробирована сперва на моей машине, а потом и в проекте Gerasim@Home (http://gerasim.boinc.ru), точнее — в подпроекте ODLS BS, новая версия расчетного модуля 1.3.6. В перспективе можно подумать над тем, что еще можно задействовать и отрицательные числа, например так

0 = -0.2 + 0.1 + 0.1

но это в перспективе, когда руки дойдут, пока и так неплохо работает...

При подобной обработке ДЛК на предмет наличия у них ОДЛК возникает несколько проблем.

1. Как подсунуть DLX'у с его хитрой динамической организацией данных в виде тора с кольцевыми ссылками единиц друг на друга дробление на подзадачи (поверьте, это оказалось непросто и получилось далеко не сразу).
2. Как обеспечить отсутствие дублей среди находимых покрытий в различных подзадачах (каждому покрытию взаимно однозначно соответствует ОДЛК).
3. Некоторые WU'шки не содержат покрытий (и, соответственно, ОДЛК), выполняются за 1-2 с и только мешаются под ногами, в то время как настоящие боевые WU'шки считаются по 10-20 минут. Как их отсечь?

Все проблемы удалось решить, получаемые числа ОДЛК для последовательной и распределенной реализаций совпадают, однако тестирование еще не завершено... Первая проблема решается поиском нужной единицы в составе тора и выполнении для нее соответствующей операции cover(), являющейся основой алгоритма DLX (тут для понимания деталей рекомендую оригинальную статью Д. Кнута, там есть картинки и псевдокод). Вторая проблема решается хитрым сбросом в ноль части строк в начале матрицы покрытия (но не всех подряд, тут тоже есть тонкость!). Третья проблема (по крайней мере частично, тестирование еще не завершено) решается путем отсечения части WU'шек выше t_max, где t_max — эмпирически определяемая граница, индивидуальная для каждого обрабатываемого ДЛК и скорее всего связанная с максимальным допустимым номером трансверсали, входящей в состав покрытий.

Теперь от теории к практике. В проект была добавлена серия WU'шек с именами wu_e1055_n12_ddlx_..., в составе которых был обработан квадрат

0 1 2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 7 9 11 0 8 6 10
9 0 1 10 2 6 5 8 11 7 4 3
11 10 5 7 9 3 0 2 1 6 8 4
3 8 7 0 6 10 11 9 5 4 2 1
10 9 8 2 7 11 3 5 4 0 1 6
4 5 9 6 1 2 8 10 3 11 0 7
5 3 6 1 0 8 7 4 9 10 11 2
6 11 4 5 3 9 2 0 10 1 7 8
2 6 10 8 11 1 4 3 7 5 9 0
7 4 11 9 8 0 10 1 6 2 3 5
8 7 0 11 10 4 1 6 2 3 5 9

Он имеет 1 ОДЛК и последовательным кодом обрабатывается за 40 секунд. Распределенная обработка в проекте велась исключительно ради тестирования, WU'шки были длительностью 1-2 с, искомый единственный ОДЛК был успешно найден, дублей зафиксировано не было. Сейчас выполняется задачка посложнее: ОДЛК ищутся для квадрата

0 1 2 3 4 5 6 7 8 9 10 11
1 2 0 4 5 3 8 6 7 11 9 10
10 9 11 7 6 8 3 5 4 0 2 1
2 3 4 5 0 1 10 11 6 7 8 9
11 10 9 8 7 6 5 4 3 2 1 0
9 8 7 6 11 10 1 0 5 4 3 2
6 11 10 9 8 7 4 3 2 1 0 5
8 7 6 11 10 9 2 1 0 5 4 3
5 0 1 2 3 4 7 8 9 10 11 6
7 6 8 10 9 11 0 2 1 3 5 4
4 5 3 1 2 0 11 9 10 8 6 7
3 4 5 0 1 2 9 10 11 6 7 8

который на настоящий момент держит рекорд по известному числу ОДЛК, равному 713258. Эту цифру необходимо получить по результатам расчетов в проекте, считаем и ждем... Последовательной реализации на это потребовалось 24 часа, посмотрим, за сколько управится параллельная распределенная, на данный момент обработка идет полным ходом, WU'шек длиннее 25 минут на моей машине пока не попалось.

Ну а дальше, если все будет работать корректно, расчет "тяжелых" ДЛК можно будет организовать достаточно просто и эффективно, никаких десятков часов без чекпоинтов не будет. Считаем...

#923 · 20.04.2021, 00:43

Цитата: Yura12 от 17.04.2021, 18:56

А эта новая версия она включает в себя оптимизации для ускорения счёта? Если да, то примерно на какой процент ожидается ускорение?

Оптимизации были сделаны Александром ранее, эта версия включает их в полном составе и должна решать проблему с редким и нестабильным подвисанием WU'шек.

Yura12 отреагировал на эту запись.

#924 · 20.04.2021, 01:07

У меня это в логах

4/20/2021 1:06:49 AM | Gerasim@home | [error] No app version found for app odls_bs platform windows_x86_64 ver 137 class ; discarding wu_e1055_n12_ddlx_sq1_t6342_11841162_0.wu

#925 · 20.04.2021, 10:09

Цитата: kotenok2000 от 20.04.2021, 01:07

У меня это в логах

4/20/2021 1:06:49 AM | Gerasim@home | [error] No app version found for app odls_bs platform windows_x86_64 ver 137 class ; discarding wu_e1055_n12_ddlx_sq1_t6342_11841162_0.wu

Я видел вчера эту ошибку. Подозреваю, что по какой-то причине криво добавилась версия 1.3.7. Передобавил ее же под номером 1.3.8 и все заработало. Первый раз сталкиваюсь с такой ошибкой на стороне сервера, возможно SerVal даст более подробный комментарий...

#926 · 20.04.2021, 10:10

У меня вчера утром на 1.3.7 версию антивирус Avira сделала ложное срабатывание.

#927 · 20.04.2021, 11:35

Цитата: Yura12 от 20.04.2021, 10:10

У меня вчера утром на 1.3.7 версию антивирус Avira сделала ложное срабатывание.

На какое конкретно приложение? Если на 'CanCPUCoreAssa', то со второй половины вчерашнего дня должно более не определяться, так как сие приложение было добавлено в исключения в антивирусные базы. Если другое - вышлите мне файл из карантина (обычно находится по пути 'C:\ProgramData\Avira\Antivirus\INFECTED' и имеет расширение '*.qua' на почту 'lestat.de.lionkur(at)gmail(dot)com', я попрошу его проверить в лаборатории.

#928 · 20.04.2021, 12:18

Да. Именно CanCPUCoreAssa

Я уже вчера делал запрос в Avira что это False Positive

#929 · 20.04.2021, 15:44

wu_e1054_n12_huge1_part9_539986_89702273_0.wu

wu_e1054_n12_huge1_part8_584614_40433103_0.wu

после 42-х часов просчета завершились ошибкой

#930 · 20.04.2021, 17:47

А у меня 2 задания висят уже 5 дней причём на мощном процессоре. Картинка приложена. Их отменять? Или подождать?