Распределенная диагонализация.В комбинаторике есть понятие т.н. "комбинаторного взрыва", когда с ростом размерности задачи ее вычислительная сложность резко возрастает и применение ряда методов, работавших до этого для малых размерностей, становится невозможным из-за необходимости огромных вычислительных затрат. На примере решаемых в настоящее время задач, связанных с построением спектров, данная ситуация для диагонализации и поквадратного обхода окрестностей начинает проявляться на размерности N=13. И если диагонализацию еще можно реализовать по частям (что и было сделано), то поквадратный обход для данной окрестности уже невозможен (приблизительная оценка необходимых вычислительных затрат — 80 лет в проекте), следовательно, мы пойдем другим путем :).
В решаемых в настоящее время задачах, связанных с построением спектров, диагонализация применяется совместно с анализом окрестностей и позволяет как увеличить мощность результирующего спектра, так и сдвинуть его верхнюю и нижнюю границы в ситуациях, когда спектр близок к пределу и просто обходом окрестностей границы уже не сдвигаются (это не единственное применение диагонализации, остальные пока оставим в стороне). Для размерности N=12 диагонализация уже выполнялась от нескольких часов до нескольких десятков часов на квадрат (для рекордсмена по числу трансверсалей — более недели в 1 поток на моей машине), для текущей размерности N=13 самые легкие квадраты будут диагонализироваться несколько часов, тяжелые — до нескольких месяцев, что неприемлимо. Поэтому, пользуясь свободным временем, в коде был реализован распределенный вариант диагонализатора, который давно созрел в голове и ждал, когда же его наконец реализуют... 🙂
В двух словах диагонализация выполняется следующим образом: из множества трансверсалей ЛК находятся подходящие пары трансверсалей, по которым производится ряд целенаправленных перестановок строк и столбцов исходного ЛК с целью получения результирующего ДЛК с интересными свойствами, что сильно быстрее (на много порядков) лобовой перестановки всех возможных пар строк и столбцов.
Далеко не все пары трансверсалей являются интересными, однако проверять необходимо все, при этом пары (T, T[j]) и (T[j], T) проверять дважды смысла нет, что при изображении соответствия трансверсалей в виде бинарной матрицы (0 — не подходят, 1 — подходят) приводит к необходимости обхода не всей матрицы, а ее половины — верхней или нижней треугольной подматрицы (для определенности обходится верхняя). В программировании это обычное дело, применяется очень часто в ряде алгоритмов, псевдокод выглядит примерно так:
for (int i = 0; i < NT; i++)
for (int j = i+1; j < NT; j++)...
Если код работает долго, значит его необходимо разбивать на куски и запускать их параллельно (в нашем случае — распределенно в проекте по принципу "1 кусок — 1 WU'шка"). Простейшим способом распараллеливания является разбиение по внешнему циклу (по i), однако здесь есть проблема: в таком случае в каждой WU'шке потребуется хранить полное множество трансверсалей (для порядка N=13 их уже бывает более миллиона, для бОльших порядков их будет сильно больше, см. [color=var(--color-primary-900)]https://oeis.org/A287644 (https://oeis.org/A287644)[/url]), что потребует минимум сотен МБ — единиц-десятков ГБ оперативной памяти на WU.[/font][/size][/color]
Более подходящей видится следующая стратегия: матрица разбивается на квадраты заданного размера K x K, одна WU'шка производит обработку одного квадрата (см. рис., на нем изображен один из самых легких ДЛК с 43 тыс. трансверсалей и разбиение на WU'шки по 20 тыс. x 20 тыс. трансверсалей в квадрате, всего 6 WU'шек). При этом возникает ряд нюансов, но они терпимые и легко реализуются в коде.
К ним относятся:
* необходимость построения разбиения на квадраты, некоторые из которых частично попадают под главную диагональ (на рисунке изображены оранжевым) — в составе соответствующих WU'шек необходима проверка и отсечение пар трансверсалей из нижней треугольной подматрицы (красные квадраты и прямоугольники обрабатываются полностью);
* наличие маленьких прямоугольников и квадратов по краям (им будут соответствовать более короткие WU'шки с рядом дополнительных проверок, чтобы не вылезти за пределы анализируемой области вправо и вниз);
* обходимость хранения множества трансверсалей по кускам (точнее, в два куска в диапазонах [x; x+K] и [y; y+K], (x,y) — координаты верхнего левого угла анализируемого квадрата/прямоугольника, диапазоны иногда могут пересекаться (в данной задаче — совпадать полностью, в перспективных задачах по эвристической работе со спектрами — частично пересекаться)).
Неоспоримым плюсом подхода является его универсальность: на квадраты можно разбить как легкие, так и тяжелые ДЛК, в последнем случае просто квадратов будет больше (для топового ДЛК порядка 13 — около 2500 при текущем разбиении), возможно управлять средним временем счета WU'шек и затратами памяти путем изменения размера квадрата K (критичным в данной задаче является именно время счета, которое в проекте не желательно делать как сильно маленьким (минуты и меньше), так и сильно большим (десятки часов), затраты памяти приемлемые).
Кроме описанного выше распараллеливание также сделано по парастрофическим преобразованиям (по 3 на ДЛК из 6 возможных, транспонирование исключено, т.к. оно дает ДЛК из того же главного класса и не интересно) и т.н. slice'ам для каждого из них (тоже 3, итого 9 комбинаций), в данном случае все тривиально в плане распараллеливания.
Вчера в проект была добавлена новая версия расчетного модуля с включенным рядом отладочных проверок и чуть более чем 10 тыс. WU'шек для 200 наиболее легких ДЛК с целью тестирования корректности кода и анализа затрат времени. В настоящее время выполняется досчет хвостов, после чего можно будет приступать к более подробному анализу, однако уже сейчас видно, что вроде все более-менее норм. Среднее время счета у меня на Core i7 4770 было в районе 7-8 минут, максимальное — около 20 минут для K=20000. В перспективе K будет немного увеличено, WU'шки немного потяжелеют и расчет будет запущен в боевом режиме. Досчитываем хвосты и считаем другие подпроекты...
PS. Применение распределенной диагонализации отнюдь не ограничивается рассмотренным выше экспериментом, который мы будем выполнять в ближайшие недели. В перспективе оно планируется к использованию как для сдвига верхних и нижних границ для некоторых оценок, так и в составе следующей серии эвристических алгоритмов расширения текущих спектров, когда текущая серия отработает и спектры перестанут меняться.
PPS. При организации подобного распределенного расчета в грид есть еще один нюанс, связанный с построением необходимого множества трансверсалей. Его можно однократно получить в процессе генерации WU'шек, а затем передать на клиент, а можно получить первым этапом при счете WU'шки. В данном эксперименте выбран первый вариант (на генерацию нужных трансверсалей теряем 1-2 секунды в каждой WU'шке, зато экономим несколько сотен КБ исходных данных WU'шки (а они сперва генерируются, потом хранятся в одной из таблиц БД на сервере проекта, затем передаются на клиент, копируются/мапятся в папку слота при старте расчета)). В перспективе с ростом размерности вполне вероятна ситуация, в которой получение нужных подмножеств трансверсалей подобным образом в каждой WU'шке станет неприемлемо долгим и придется перейти ко второму варианту...
Хотите принять участие в распределенных вычислениях, тогда, Вам сюда:
[color=var(--color-primary-900)]https://boinc.berkeley.edu/wiki/Simple_view (https://boinc.berkeley.edu/wiki/Simple_view)[/url][/font][/size][/color]
[color=var(--color-primary-900)]https://boinc.berkeley.edu/download_all.php (https://boinc.berkeley.edu/download_all.php)[/url][/font][/size][/color]
[color=var(--color-primary-900)]https://boinc.ru (https://boinc.ru/)[/url][/font][/size][/color]
Ссылка на git-хаб, где лежат исходники программы-клиента BOINC.
[color=var(--color-primary-900)]https://github.com/BOINC/boinc (https://github.com/BOINC/boinc)[/url][/font][/size][/color]