Этот пост связан с постом «Слабо загрузить 40 ядер?», ранее опубликованном на хабре и приглашавшем всех желающих принять участие в "конкурсе по параллельному программированию", проводимом компанией Intel, и является отчетом, написанным одним из участников.
Несмотря на то, что предложенное мною решение является корректным и, на мой взгляд, очень быстрым, мне удалось занять лишь 30-е место из 70-и. Попробуем разобраться в причинах поражения, и дать советы — что делать, чтобы побеждать в подобных конкурсах.
В двух словах о задаче:
Между европейским и российским конкурсами было маленькое, но очень существенное различие, а именно — способ задания входных данных. В европейском матрица с входными данными считывалась из файла и содержала произвольные данные. В российском же матрица заполнялась случайными данными, полученными с помощью генератора случайных чисел.
Вы скажете, между случайными и произвольными данными нет никакой разницы? Ошибаетесь, здесь и завязывается основная интрига. Дело в том, что для в качестве генератора случайных чисел было предписано использовать линейный конгруэнтный генератор
причем, по условиям конкурса, параметры генератора 0 < a,b,m <= 20000 и матрица заполняется построчно, слева направо. Особенностью конкретного ГСЧ является короткий период, так что последовательность Xi повторяется максимум через m чисел, а зачастую, при «неудачном» выборе a и b — и вообще через несколько чисел. Таким образом, где в европейском конкурсе матрицы имели вид
в нашем —
т.е. короткий период начинал повторяться снова и снова и данные, которыми заполняется матрица, теоретически случайные, практически имели определенную структуру. Так, например, учитывая диапазоны параметров, в самой большой матрице 20000 x 20000 повторялась каждая строка.
Здесь возникает первый выбор, сделав который, я сразу похоронил свои шансы на выигрыш — не использовать в решении тот факт, что данные совсем не произвольные. Отсюда следует
Совет №1. Всегда используйте олимпиадный подход к решению задачи.
Олимпиадным стилем программирования называется такой, который нацелен только на одно — чтобы задача прошла тесты жюри. В противоположность этому, промышленный стиль подразумевает, что программа корректно решает целый диапазон задач, имеющий практическое применение.
Размышляя об этом теперь, становится очевидно, что как только был назначен алгоритм генерации, задача конкурса стала звучать так:
Написать программу для поиска подматрицы с максимальной суммой в матрице целых чисел, заполненной определенным образом.
Это совсем другая задача, она потеряла всякую промышленную составляющую, потому, что алгоритм, выигрышный в таких условиях, никак не обобщается, и не применим ни к каким реальным данным.
Однако в начале конкурса я рассуждал по-другому, вроде бы
1. Конкурс: «по параллельному программированию».
2. Девиз конкурса: «загрузить 40 ядер», дан доступ к 40-ядерной машине.
3. Из описания задачи: «цель, которая стоит перед вами — максимально ускорить вычисления за счет использования „умных“ алгоритмов и параллелизации».
4. Есть точно такой же европейский конкурс, только промышленный, без специфики генерации.
и списал возникший перекос задачи на недосмотр жюри. В тот момент, когда я принял решение решать задачу промышленным стилем, в общем виде, конкурс был проигран, и призам было сказано «до свидания».
Среди победителей нет ни одного промышленного решения.
Совет №2. Не бойтесь больших тестов — их не будет.
Именно тесты большого размера позволяют выявить различия между решениями, использующими различные алгоритмы. На больших тестах выявляется оптимальность распараллеливания. В конце концов, какие-то решения могут просто не уложиться по времени.
По условиям данного конкурса, максимальный размер матрицы составляет 20000 x 20000, т.е. 4*10^8 чисел. Это весьма серьезный размер, такая матрица занимает 1.5 гигабайта памяти и для обсчета алгоритмом кубической сложности требует 8*10^12 операций.
Не бойтесь, таких тестов не будет. Максимальный тест, использованный организаторами, имеет размер 5000 x 5000, т.е. 1/16 от максимально возможного, занимает 100 мегабайт памяти и требует 1.25*10^11 операций, т.е. 1/64 от максимально возможного.
Совет №3. Не уделяйте излишнего внимания программе, используйте все способы набрать очки.
Когда правила начисления баллов неизвестны, не делайте никаких предположений. Вот, например, прочтя исходную постановку конкурса
до 150 за скорость программы, до 25 за текст описания работы и до 25 за публикацию в блоге или на форуме организатора.
я, слегка усмехнувшись (очки за треп на форуме — ха !), предпочел, разумеется, бороться за 150 баллов, которые можно набрать за скорость программы. Большая ошибка!
Что оказалось в итоге —
1. 60 из 70 участников получили меньше 35 баллов за саму программу! Победитель получил 100, а далее 80, 70, 50, 60 и 30, 30, 20, 20,…
2. Все участники получили по 25 баллов за описание.
3. Участники, опубликовавшие статью в блоге, получили 25 баллов. Не опубликовавшие получили 0.
Получается, что вклад программы в баллы составлял порядка 1/3, причем можно было получить за статью в блоге больше, чем за решение.
Вот, например, лучшее по сумме баллов промышленное решение принадлежит команде R2_D2, занимает 7-е место, набирает 32+25+25 баллов и работает медленнее, чем, например, мое решение, 28-е место, 33+25+1 баллов. При этом разнице по скорости вычислений в разы соответствует разница в оценке в 1 балл (33 против 32).
Мораль:
Это конкурс, вы не на работе. Не надо додумывать лишнего и решать, что правильно, а что — нет. Ваша задача — любой ценой набрать баллы.
Всем удачи!
Несмотря на то, что предложенное мною решение является корректным и, на мой взгляд, очень быстрым, мне удалось занять лишь 30-е место из 70-и. Попробуем разобраться в причинах поражения, и дать советы — что делать, чтобы побеждать в подобных конкурсах.
В двух словах о задаче:
- Написать программу для поиска в матрице целых чисел подматрицы с максимальной суммой.
- Максимальный размер матрицы: 20000 x 20000.
- Начисление баллов: до 150 за скорость программы, до 25 за текст описания работы и до 25 за публикацию в блоге или на форуме организатора.
Между европейским и российским конкурсами было маленькое, но очень существенное различие, а именно — способ задания входных данных. В европейском матрица с входными данными считывалась из файла и содержала произвольные данные. В российском же матрица заполнялась случайными данными, полученными с помощью генератора случайных чисел.
Вы скажете, между случайными и произвольными данными нет никакой разницы? Ошибаетесь, здесь и завязывается основная интрига. Дело в том, что для в качестве генератора случайных чисел было предписано использовать линейный конгруэнтный генератор
Xi+1 = (a*Xi + b) mod mпричем, по условиям конкурса, параметры генератора 0 < a,b,m <= 20000 и матрица заполняется построчно, слева направо. Особенностью конкретного ГСЧ является короткий период, так что последовательность Xi повторяется максимум через m чисел, а зачастую, при «неудачном» выборе a и b — и вообще через несколько чисел. Таким образом, где в европейском конкурсе матрицы имели вид
9 9 2 0 2
4 7 9 8 2
9 6 5 1 3
2 5 7 0 7
4 6 0 3 6
в нашем —
3 7 5 1 3
7 5 1 3 7
5 1 3 7 5
1 3 7 5 1
3 7 5 1 3
т.е. короткий период начинал повторяться снова и снова и данные, которыми заполняется матрица, теоретически случайные, практически имели определенную структуру. Так, например, учитывая диапазоны параметров, в самой большой матрице 20000 x 20000 повторялась каждая строка.
Здесь возникает первый выбор, сделав который, я сразу похоронил свои шансы на выигрыш — не использовать в решении тот факт, что данные совсем не произвольные. Отсюда следует
Совет №1. Всегда используйте олимпиадный подход к решению задачи.
Олимпиадным стилем программирования называется такой, который нацелен только на одно — чтобы задача прошла тесты жюри. В противоположность этому, промышленный стиль подразумевает, что программа корректно решает целый диапазон задач, имеющий практическое применение.
Размышляя об этом теперь, становится очевидно, что как только был назначен алгоритм генерации, задача конкурса стала звучать так:
Написать программу для поиска подматрицы с максимальной суммой в матрице целых чисел, заполненной определенным образом.
Это совсем другая задача, она потеряла всякую промышленную составляющую, потому, что алгоритм, выигрышный в таких условиях, никак не обобщается, и не применим ни к каким реальным данным.
Однако в начале конкурса я рассуждал по-другому, вроде бы
1. Конкурс: «по параллельному программированию».
2. Девиз конкурса: «загрузить 40 ядер», дан доступ к 40-ядерной машине.
3. Из описания задачи: «цель, которая стоит перед вами — максимально ускорить вычисления за счет использования „умных“ алгоритмов и параллелизации».
4. Есть точно такой же европейский конкурс, только промышленный, без специфики генерации.
и списал возникший перекос задачи на недосмотр жюри. В тот момент, когда я принял решение решать задачу промышленным стилем, в общем виде, конкурс был проигран, и призам было сказано «до свидания».
Среди победителей нет ни одного промышленного решения.
Совет №2. Не бойтесь больших тестов — их не будет.
Именно тесты большого размера позволяют выявить различия между решениями, использующими различные алгоритмы. На больших тестах выявляется оптимальность распараллеливания. В конце концов, какие-то решения могут просто не уложиться по времени.
По условиям данного конкурса, максимальный размер матрицы составляет 20000 x 20000, т.е. 4*10^8 чисел. Это весьма серьезный размер, такая матрица занимает 1.5 гигабайта памяти и для обсчета алгоритмом кубической сложности требует 8*10^12 операций.
Не бойтесь, таких тестов не будет. Максимальный тест, использованный организаторами, имеет размер 5000 x 5000, т.е. 1/16 от максимально возможного, занимает 100 мегабайт памяти и требует 1.25*10^11 операций, т.е. 1/64 от максимально возможного.
Совет №3. Не уделяйте излишнего внимания программе, используйте все способы набрать очки.
Когда правила начисления баллов неизвестны, не делайте никаких предположений. Вот, например, прочтя исходную постановку конкурса
до 150 за скорость программы, до 25 за текст описания работы и до 25 за публикацию в блоге или на форуме организатора.
я, слегка усмехнувшись (очки за треп на форуме — ха !), предпочел, разумеется, бороться за 150 баллов, которые можно набрать за скорость программы. Большая ошибка!
Что оказалось в итоге —
1. 60 из 70 участников получили меньше 35 баллов за саму программу! Победитель получил 100, а далее 80, 70, 50, 60 и 30, 30, 20, 20,…
2. Все участники получили по 25 баллов за описание.
3. Участники, опубликовавшие статью в блоге, получили 25 баллов. Не опубликовавшие получили 0.
Получается, что вклад программы в баллы составлял порядка 1/3, причем можно было получить за статью в блоге больше, чем за решение.
Вот, например, лучшее по сумме баллов промышленное решение принадлежит команде R2_D2, занимает 7-е место, набирает 32+25+25 баллов и работает медленнее, чем, например, мое решение, 28-е место, 33+25+1 баллов. При этом разнице по скорости вычислений в разы соответствует разница в оценке в 1 балл (33 против 32).
Мораль:
Это конкурс, вы не на работе. Не надо додумывать лишнего и решать, что правильно, а что — нет. Ваша задача — любой ценой набрать баллы.
Всем удачи!