olg2002

Marathon 68 -- BeautifulCrossword

Идея поучаствовать в четырехнедельном марафоне заманчива, но для этого, во-первых, нужны четыре недели, а во-вторых, в первом раунде не будет 50-ти лучших марафонцев, и в чем тогда смысл. Короче, чтобы пропустить первый раунд TCO, решил принять участие в последнем марафоне, который давал возможность обновить свой рейтинг и выполнить условие активности за последние шесть месяцев. Результат: обновил и выполнил. Уроки на будущее: тщательно проверять дату окончания марафона; даже если марафон проходной,  не оставлять все на последний день. Состояние, когда видишь пустую страницу там, где должна была быть ссылка Submit, словами, наверное, передать можно, но нужен талант. 36-место, -82, желтые штаны.

2011 TCO Round 2 -- QualityPolygons

Отличная задача! Простое и понятное условие (вопросов на форуме практически не было), вся геометрия в целых числах (никаких уплывающих запятых), глубина (это когда новые грабли обнаруживаются только на второй неделе). Идея, стоящая упоминания: поскольку необходимо было часто для произвольной вычисленной точки находить ближайшую из заданного множества, а также всех ее соседей, была реализована дискретная диаграмма Вороного. При инициализации для каждой точки заданного пространства 700х700 методом динамического программирования была вычислена ближайшая исходная точка, и для каждой исходной точки в том же процессе были определены все соседи. Две структуры данных позволяли быстро находить (x,y) -> point -> neighbors[]. Новшество марафона: искусственное выделение двух областей параметров; в первой возможен полный (или близко к тому) перебор, во второй без эвристик делать нечего. Результат: 25-е место, +25.

2011 TCO Round 3 -- StringCompression

Случилось страшное: все четыре области параметров позволяли достигать оптимального (или по-крайней мере очень к нему близкого) результата. Это грозило тем, что за две недели количество претендентов на первое место заметно превысило бы 12, проходящих в финал. Трудно сказать, насколько правильным было решение изменить правила через пять дней после начала марафона, но проблему с парой десятков первых мест TC, конечно, решил.  В результате пришлось решать две разные задачи: восстановление зашумленной строки и сжатие практически белого шума. Главный результат для меня - удалось применить алгоритм восстановления с итеративной нормализацией. Теперь, когда есть практический опыт его (алгоритма) применения, будем искать возможности его (опыта) расширения. Предварительный результат. 18-е место с очень малыми шансами на улучшение. Update: 15 место, +41, красные штаны. Всего 1% отделял от 12-го места, было за что бороться.

Есть n бутылок с молоком. Ровно в двух бутылках примешан яд, который действует через 24 часа. Имеются лабораторные крысы, с помощью которых за эти 24 часа нужно определить, в каких бутылках яд. Как обойтись минимальным количеством крыс?
При том, что вопрос об оптимальном количестве может оказаться сравнимым по сложности с вопросом об оптимальной сортировке сравнениями, хотелось бы найти алгоритм, лучше O(n).
( Далее...Collapse )

Презентация Нейла Гантера (Neil Gunther, Performance Dynamics).

Пусть время исполнения программы на N процессорах равно:

T(N) = A + B/N + C*(N-1)

где A - время исполнения последовательной (непараллелизуемой) части программы;
B - время исполнения идеально параллелизуемой части программы;
C - время взаймодействия одного процессора с другим, необходимое для организации вычислительного процесса (координация управления и обмен данными).
Очевидно, что T(1) = A + B.

Ускорение на N процессорах:

C(N) = T(1)/T(N) = ( A + B ) / ( A + B/N + C*(N-1) ) =
N*(A+B) / ( A*N + B + C*N*(N-1) ) = N / ( 1 + (N-1)*A/(A+B) + N*(N-1)*C/(A+B) )= N / ( 1 + a*(N-1) +b*N*(N-1) )

Нейл называет параметр "a" (alpha) - "the contention parameter", параметр "b" (beta) - "a measure of the coherency delay", а всю модель - "The Universal Scalability Law".

Эта модель, безусловно, - шаг вперед по сравнению с убогим "законом Амдала", к которому она сводится при C=0 (b=0). Однако попытка заменить его под именем "всеобщего закона" претендует на большее, чем может выдержать. Введение члена описывающего стоимость коммуникации не меняет изначальной ущербности чрезмерного упрощения представления программы как состоящей из двух частей: не поддающейся распараллеливанию совсем и идеально параллелизуемой. Это представление, похоже, идет из практики OpenMP, когда вычислительные программы можно было распараллеливать на уровне циклов. Если между итерациями цикла нет зависимостей, то теоретически его можно распараллелить хоть до одной итерации на процессор. В то же время весь код между циклами - это участок последовательного исполнения программы, не получающего никакого ускорения от наличия дополнительных процессоров.

Нейл справедливо заметил, что если в системе идет конкуренция за ресурс, то это приводит к увеличению параметра "a". Но вывод, что этот параметр отвечает за конкуренцию (contention, queueing), оказался неверным обобщением. Дело в том, что есть по крайней мере две других важных причины, по которым параметр "a" может расти: простой (idling) и накладные расходы (overhead). Первое происходит тогда, когда количество задач меньше количества исполнителей и часть их вынуждена простаивать в ожидании работы (очень похоже на ожидание освобождения ресурса, но причина, как видим, совсем иная). Второе есть следствие того, что для организации параллельных вычислений приходится тратить те же самые ресурсы, которые необходимы для собственно вычислений - в первую очередь время процессора. Если нужно, чтобы десять человек быстро вырыли длинную канаву, одного человека приходится делать управляющим, который будет организовывать процесс, говоря кому где копать, и следя за тем, чтобы никто не простаивал без работы, - это и есть накладной расход.
Я предложил Нейлу более общий термин для интерпретации параметра "a" - "lack of parallelism" (недостаток параллелизма), к которому сводятся все три обозначенные причины.

Следующее критическое замечание есть следствие упрощенной модели Амдала. В реальных системах ускорение работы программы может носить качественно иной характер, нежели описываемый моделью Амдала, и в первую очередь из-за наличия зависимостей между подзадачами (типичный пример - qsort или те же числа Фибоначчи). В результате параметр "a" не сможет быть выражен константой, и его изменчивость вынуждено отразится на параметре "b", отвечающем за коммуникацию. Нейл подтвердил, что у него был случай, когда модель имела a=0 и b>0, при этом в исследуемой системе отсутствовала какая-либо коммуникация, которую, согласно модели, нужно было оптимизировать с целью уменьшения "b". Я указал на модель "критического пути" (critical path) как более точную для многих параллельных задач.

Не мой год. Если второй раз 50-е место, то это уже не случайность.
Были все условия, были неплохие идеи, но в сильное решение это как-то не материализовалось.
Наверное, сильно увело в сторону соображение, что на простых графах можно получить настолько много очков, что остальные случаи не будут играть решающей роли. Более того, в определенный момент я был уверен, что вся борьба за эти простые случаи и происходит. Теперь ясно, что это было не так.
Пара идей, которые позволили получить ~2600 на одном тесте (на локальной машине, правда, которая существенно быстрее TC сервера):

1. Определим ранг вершины графа в результате следующей процедуры:
Все вершины, связанные только одним ребром, получают ранг 1 и удаляются из графа. Этот шаг повторяется, пока не закончатся все вершины ранга 1. Теперь все вершины, связанные двумя ребрами, получают ранг 2 и удаляются из графа. Этот шаг повторяется с небольшим изменением в том, что если в результате удаления вершин какая-то вершина останется с количеством ребер меньше двух, она все-равно получает ранг 2. И так далее для ранга 3,4,... пока не закончатся все вершины.
Когда мы ищем возможное соответствие вершины из H (subgraph) вершине из G, мы можем не брать во внимание все вершины меньшего ранга независимо от количества ребер. Например, если вершина из H имеет ранг 2 (входит в какой-то цикл H), то можно отбросить все вершины G ранга 1 (которые заведомо не входят ни в какой цикл).

2. Поскольку мы решаем задачу изоморфизма для индуцированного подграфа, то на каждом шаге поиска соответствия вершины из H нас интересуют только те кандидаты из G, которые сохраняют как существующие соединения, так и их отсутствие. Задача быстрого определения такого подмножества решается следующим образом. Изначально каждой вершине G присваивается уникальный хеш-код (я использовал G[i].hash = 3^i mod 2^32). Во время поиска изоморфизма для вершин из H и G подсчитываются текущие значения mark: каждый раз, когда мы устанавливаем соответствие между вершиной u из H и вершиной v из G, мы добавляем v.hash ко всем текущим значениям mark соседей как u так и v (если мы удаляем соответствие мы производим вычитание). В результате если мы ищем соответствие новой вершине из H, то искать его нужно в подмножестве вершин G с таким же текущим значением mark (разумеется, можно не проверять все множество G, а взять только соседей вершины, уже поставленной в соответствие какому-либо соседу из H).
Эта техника работает для всех графов и очень эффективно. Теоретически существует вероятность того, что произойдет ложное срабатывание: сумма совпадает при неверном количестве соседей. Это означает, что для некоторого подмножества соседей сумма hash значений равна 0 - достаточно очевидно, что такая вероятность очень мала. Кроме того этой вероятностью легко управлять: если бы я хоть раз за все время тестирования обнаружил, что получаю неверное соответствие, я бы просто увеличил размер hash до 64 бит.

Экспромт (на тему H.Longfellow):

I've got an algorithm
With a thing or two to beat'em
But a frightening thought makes me worried:
That when it is fast,
It is very fast indeed,
But when it is slow it is horrid.

UPDATE: 42-е место, -60. В качестве утешительного приза - максимальный абсолютный результат: 1855; следующий - у Psyho, занявшего первое место: 1396.

Задача минимум для второго раунда, естественным образом, - пройти в третий раунд. Пятьдесят какое-то место (pathetic) с хорошей вероятностью это обеспечивает.
Задача максимум - не потерять рейтинг, приложив минимальные усилия. Тут произошел полный провал. И усилия были затрачены не минимальные, и результат ожидается плачевный. Отчеты о других решениях указывают на то, что проигрыш оказался в скорости. На это уже намекал тот факт, что локальные результаты на похожей машине были существенно лучше чем на сервере (количество итераций было в среднем в два раза больше), но почему-то все усилия были направлены на улучшение основного алгоритма, а как гласит народная мудрость, алгоритмические ухищрения в конечном счете не выдерживают конкуренции с brute force ("против лома нет приема").

UPD: 51-е место, -36. Утешает факт, что, благодаря venco (и паре японцев), Россия вернула себе первое место:

Top Ranked Marathon Match Countries
Rank	Name	Member Count	Rating
1	Russian Federation	126	2076.39
2	Japan	98	2065.96
3	United States	205	2057.11
4	Poland	53	1933.19
5	China	109	1889.28

Мне было интересно попробовать Go для параллельного программирования и этот тест дал такую возможность. Goroutines и channels - концепции, которые легко освоить после некоторого известного опыта. Задача, как было показано на примере Java, легко параллелизуется: произвольное количество независимых подзадач с редукцией. Я тем не менее был несколько удивлен тому, насколько громоздко это было сделано в Go: fannkuch-parallel.go. Кроме того, параллельное решение еще и тратило в полтора раза больше ресурсов (процессорное время), чем последовательное (sequential). Впрочем, все оказалось не так печально, и мое параллельное решение ненамного сложнее предыдущего на Java. Отличие - в использовании goroutines: основная функция запускается как goroutine и первым делом она "рекурсивно" запускает себя (создает новую подзадачу) с новым параметром для следующего диапазона индексов, которые нужно обработать. Каждая подзадача возвращает свой результат через общий channel, чтение из которого с редукцией частных результатов производит main. Теоретически такое решение масштабируется хуже, чем "обход бинарного дерева", но на практике, как всегда, дело обстоит несколько иначе. Примечательно, что процессорное время практически одинаково для одного и четырех процессоров. Ускорение на четырех процессорах - 3.98.

Дополнительное замечание по поводу того, почему Go настолько медленный на этом тесте. Как и Java, Go производит проверку индекса при обращении к массиву. Главный цикл содержит обмен значениями между a[i] и a[j] - это четыре обращения (два чтения и две записи). Java оптимизирует код так, что на четыре обращения - всего две проверки индекса. Go "честно" отрабатывает все четыре проверки.

Усилия не пропали даром и привели к появлению нового теста: fannkuch-redux.
Кроме максимального количества переворачиваний теперь нужно еще посчитать контрольную сумму, которая зависит от порядка генерации перестановок и количества переворачиваний для каждой из n! перестановок. Сумма ассоциативна, то есть позволяет просто реализовать параллельные вычисления, и легковесна, так что практически все время по-прежнему тратится на основной алгоритм. Ождается, что от многих "оптимизаций", которыми грешили лидеры предыдущего варианта, теперь придется отказаться. Было сделано несколько итераций, прежде чем конкретный вид контрольной суммы был принят. Мне больше всего нравилась: checkSum ^= permIndex + flipsCount;, но оказывается есть языки, испытывающие трудности с битовыми операциями (Lua). Окончательный выбор пал на checkSum += permIndex%2 == 0 ? flipsCount : -flipsCount;.
Мое решение теперь идет как Java-server.

Пока идет переписка с администратором ресурса о том, как починить benchmark, я ради демонстрации текущей проблемы и придания большего веса своим аргументам подал новую версию своего решения, которое теперь на 25% быстрее бывшего лидера g++ (на локальной машине). Это лидерство было во многом обеспечено тем фактом, что g++ генерировал не n! всех возможных перестановок, а заметно меньше: (n-2)*(n-1)! (другие решения ограничивались перебором (n-1)*(n-1)! перестановок). Одна оптимизация состояла в отбрасывании всех перестановок, в которых элемент n остается на своем месте. Действительно, перестановки с максимальным flip count среди них быть не может. Делалось это простым способом: создавалось n-1 тредов; i-му треду давалась начальная перестановка, в которой элемент n был переставлен с элементом i; каждый тред далее перебирал (n-1)! перестановок первых n-1 элементов. Другая оптимизация заключалась в том, что в каждом треде пропускались первые (n-2)! перестановок, в которых n-1 элемент оставался на своем месте. Опять же, в силу общего соображения, приведенного ниже, такая оптимизация безопасна. Один случай, правда, требует особого рассмотрения: n-1 тред, начальная перестановка которого (1 2 3 .. n n-1). Почему и в этом случае безопасно отбросить первые (n-2)! перестановки? Потому что любая перестановка вида (... n n-1) с точки зрения flip count эквивалентна перестановке из первых n-2 элементов, поскольку последние два элемента никогда не могут быть сдвинуты с места flip-операцией.

Теперь я вижу, что моя идея может быть сформулирована как обобщение предыдущих рассуждений, хотя я пришел к ней независимо от приведенного анализа. Заключается она в следующем: поскольку flip-операция всегда ставит первый элемент текущей перестановки на свое место, перестановка с максимальным flip count не может иметь p[i] == i. Другая формулировка: если в перестановке p[i] == i для некоторого i, то можно построить новую перестановку обратной flip-операцией, чей flip count следовательно будет на единицу больше, чем у текущей.

Итак, когда мы перебираем перестановки, как только мы обнаруживаем, что p[i] == i для некоторого i, у нас появляется шанс ускорить алгоритм, пропустив все последующие перестановки первых i-1 элементов, - сразу прокрутить i-ый элемент на следующую позицию.
Мне сильно не хотелось жертвовать элегантностью решения, и поэтому не все возможности, которые дает эта идея, были использованы. В результате:
- оптимизационный код состоит из семи строк в одном месте и еще одной строки в другом, которые легко можно исключить без необходимости перестраивать решение;
- сохранен заданный порядок генерации перестановок (неочевидный - многие решения используют его только для печати первых 30 перестановок, а в основном алгоритме используют другой порядок);
- для параллельной реализации сохранена гибкость в определении размера одной подзадачи (решение сбалансировано и оптимизировано по количеству подзадач);
- печать первых 30 перестановок - часть основного алгоритма, а не вынесенный код.

Разумеется, если C/C++ реализует тот же алгоритм, status quo будет восстановлен, но я ожидаю, что разница в скорости будет в пределах нормальных 20%.

UPD: Новое решение принято как Java6-server#5. Это лучшее решение на всех четырех платформах (0.8 от g++). К сожалению оно помещено в "interesting alternative" programs, а g++ оставлено в основном списке, хотя разница между ними, как было показано выше, количественная, а не качественная.

Мне уже рассказывали про language shootout, но в этот раз я независимо вышел на этот сайт, хотя и не помню, что именно вызвало мой интерес. Посмотрев на flawed benchmarks и убедившись в том, насколько несовершенно сравнение языков программирования, я тем не менее решил попробовать улучшить шансы Java, особенно там, где она уж совсем не виновата: плохо сбалансированное параллельное решение для fannkuch.
Сначала я попытался выжать, что можно, из последовательной реализации алгоритма, который "нельзя менять", но, как показывают другие примеры, можно существенно ускорять, особенно, если это делать незаметно. Локальные результаты демонстрировали заметное преимущество над другими Java программами (Java6-server и Java6-server#4), однако последующее тестирование на сервере этого не показало. У меня нет под рукой похожей машины, тем более с Ubuntu, так что пока все спишем на разницу между Intel и AMD.
Мой подход для распараллеливания очень прост: разбить задачу на большое количество независимых подзадач (tasks), размер которых можно было бы варьировать с тем, чтобы минимизировать дисбаланс (load imbalance), не платя за это слишком большими накладными расходами (overhead). Разумеется, такая возможность закладывалась уже в проектирование последовательного решения. Ошибка плохо сбалансированного текущего решения (Java6-server) заключалась именно в том, что параллелизм был добавлен к уже готовой последовательной программе, которая проектировалась без учета будущего распараллеливания. В результате были реализованы крупные подзадачи, что привело к заметному дисбалансу.
Мое решение было принято и обозначено как Java6-server#2. На данный момент это лучшее параллельное Java решение как для 32, так и для 64 бит. Я еще недостаточно тестировал его именно в параллельном режиме и не пробовал пару алгоритмических штучек, которыми пользуются другие решения, поэтому скорее всего будет следующая версия.

Слайды лекций Джона (John Mellor-Crummey) по курсу "Параллельные вычисления" в Rice University.