В ноябре 2012 года был запущен конкурс по параллельному программированию от Intel, этому даже был посвящен отдельный.
быстрый на хабе.
О конкурсе мы узнали от нашего преподавателя Евгения Калишенко.
Он читает хорошо по специальности «Высокопроизводительные и параллельные вычисления» в СПб Академическом Университете и стал лидером нашей команды.
Целью конкурса было написать и оптимизировать решение одной алгоритмической задачи за несколько недель.
Прежде чем описать его условия, отметим несколько особенностей конкурса.
Особенности конкурса
Сначала решения тестировались на компьютере с несколькими десятками ядер.Эти соревнования отличались от известных студенческих олимпиад формата ACM, где распараллеливать код бесполезно: время выполнения — это суммарное время, потраченное ядрами.
Тип предложенных задач был очень похож на задачи, предлагаемые на этих олимпиадах.
Во-вторых, было дано эталонное решение проблемы.
Это код, который решает проблему, гарантированно корректно, но очень медленно.
Одной из возможных стратегий была оптимизация и распараллеливание этого решения.
Можно было полностью переписать алгоритм, но в этом случае необходимо было сохранить его семантику.
Правильность решения участника определялась простой разницей между ответами конкурсного и эталонного решений по нескольким тестам.
Забегая вперед, скажу, что мы выбрали что-то среднее между этими двумя вариантами: код, отвечающий за ввод и вывод результатов, мы позаимствовали из эталонного решения, а алгоритм полностью переписали сами.
Таким образом мы защитили себя от глупых ошибок, связанных с несоответствием формата вывода чисел с плавающей запятой, лишними пробелами и орфографическими ошибками при выводе.
Теперь о предлагаемой задаче.
Состояние
Входные файлы содержат: список рейсов с указанием компаний, их организующих; список групп авиакомпаний, образующих «альянсы».Вам необходимо вывести в выходной файл самые дешевые маршруты, удовлетворяющие нескольким требованиям.
«Легенда» такая: мы летим из родного города на конференцию, а потом возвращаемся обратно.
В то же время мы, возможно, захотим по пути отдохнуть в одном из этих городов, побывав там до или после посещения конференции.
Существуют ограничения по времени нашего прибытия на конференцию, времени выезда оттуда и желаемому времени отдыха.
Нам необходимо рассчитать лучший маршрут для каждого из городов, которые мы хотим посетить, а также для того варианта, в котором мы все равно не отдохнем.
Еще одно условие: полет двумя рейсами подряд одной авиакомпании обходится на 30% дешевле, а полет двумя рейсами авиакомпании альянса — на 20% дешевле.
Кроме того, мы не хотим слишком долго ждать соединения, и максимальное время ожидания ограничено.
Эталонное решение начинает практически полный перебор всех возможных путей, и возможность его оптимизации сразу пропадает. Естественно, мне хотелось использовать на графах стандартные алгоритмы, но пришлось преодолеть несколько трудностей.
Основное из них заключалось в том, что алгоритм учитывает, что цена полета зависит от предыдущего и последующего.
Известные алгоритмы поиска кратчайшего пути (Дейкстра, Флойд, Беллман-Форд) требуют, чтобы веса ребер были постоянными.
Алгоритм
Для начала отметим, что делать города вершинами, а пролеты ребрами — плохая идея.Каждый рейс отправляется в определенное время, и надо учитывать, что вылететь из аэропорта мы сможем только после того, как приедем в него.
Поэтому вершины будут пролетами, а ребра соединят те из них, по которым можно пролететь последовательно.
Далее нужно учитывать скидки.
Разделим каждую вершину на пять.
Каждая из этих пяти вершин будет иметь так называемый «тип».
Если мы хотим лететь определенным рейсом, а до этого мы летали рейсом этой же авиакомпании, то договоримся, что наш путь проходит через вершину первого типа.
Если с этой начинается последовательность рейсов одной авиакомпании, то мы соглашаемся пройти через вершину второго типа.
Проделаем то же самое с альянсами, добавив еще два типа вершин.
Пятый тип будет соответствовать тому, что наша скидка на этот рейс равна нулю: предыдущий и следующий рейсы обслуживает компания, отличная от текущей и не состоящая с ней в альянсе.
Порядок нумерации в коде другой.
Перечисление типов вершин
Соединять вершины ребрами просто: для каждого города считаем все прилетающие и вылетающие рейсы.enum { FROM_ANY = 0, FROM_THIS = 1, FIRST_THIS = 2, FROM_ALLIANCE = 3, FIRST_ALLIANCE = 4 };
Для каждой пары рейсов мы определяем, сможем ли мы прилететь первыми и вылететь вторыми (учитывая, что у нас есть ограничение на время пересадки).
Если можем, то перебираем все типы вершин, соответствующие этим рейсам, и соединяем ребрами те, которые совпадают по типу.
Например, если авиакомпании, организовавшие эти рейсы, разные, то ребра не должны идти в вершину, соответствующую первому типу («предыдущий рейс был от той же компании»).
А вот в вершине второго типа («первый пролет в последовательности от одной компании») нужно просто добавить ребра, так как следующий пролет может быть каким угодно.
Тщательно перебираем 25 пар типов, понимаем, какие пары требуют подключения, а какие нет. Рассчитываем цену с учетом скидки для данного рейса и каждого типа, присваиваем ее ребрам, входящим в вершины, и граф почти готов.
Код, связывающий вершины для пары рейсов void wire_two_flights(Graph &g, Flight* f1, Flight* f2, int i1, int i2) {
#define P_B(t) push_back(make_pair(getCostWithDiscount(f2, t), i2 + t))
if(f1->company == f2->company) {
g[i1 + FIRST_THIS].
P_B(FROM_THIS); g[i1 + FROM_THIS].
P_B(FROM_THIS); g[i1 + FROM_ALLIANCE].
P_B(FROM_THIS); } else if(alliances[f1->company][f2->company]) { g[i1 + FIRST_ALLIANCE].
P_B(FROM_ALLIANCE); g[i1 + FIRST_ALLIANCE].
P_B(FIRST_THIS); g[i1 + FROM_ALLIANCE].
P_B(FROM_ALLIANCE); g[i1 + FROM_ALLIANCE].
P_B(FIRST_THIS); g[i1 + FROM_THIS].
P_B(FROM_ALLIANCE); g[i1 + FROM_THIS].
P_B(FIRST_THIS); } else { g[i1 + FROM_ANY].
P_B(FROM_ANY); g[i1 + FROM_ANY].
P_B(FIRST_THIS); g[i1 + FROM_ANY].
P_B(FIRST_ALLIANCE); g[i1 + FROM_ALLIANCE].
P_B(FROM_ANY); g[i1 + FROM_ALLIANCE].
P_B(FIRST_THIS); g[i1 + FROM_ALLIANCE].
P_B(FIRST_ALLIANCE); g[i1 + FROM_THIS].
P_B(FROM_ANY); g[i1 + FROM_THIS].
P_B(FIRST_THIS); g[i1 + FROM_THIS].
P_B(FIRST_ALLIANCE);
}
}
Однако нужно еще учитывать, что наш путь обязательно должен проходить через место конференции и отдыха.
Давайте сначала решим задачу нахождения кратчайшего пути в графе между двумя вершинами А и В и прохождения через вершину С.
Это можно сделать так: копируем граф G, получив две его копии G и G' (назовем их слои).
Соединим вершину C с вершиной C' (копией C) графа G'.
После этого можно искать путь между вершинами A и B' — он гарантированно проходит через C, поскольку других способов перепрыгнуть с одного слоя на другой просто нет. Вы можете сказать, что проще просто найти путь из A в C, а затем из C в B. Но наш подход можно обобщить на случай, когда путь должен проходить хотя бы через одну из многих вершин, полетов, которые могут занять нас на конференцию.
Кроме того, потребуется больше слоев, чтобы учесть место отдыха.
Также необходимо будет принять во внимание два возможных порядка посещения конференции и места отдыха.
Но это уже детали.
Главное, чтобы граф увеличился в результате таких операций не более чем в постоянный коэффициент. Добавив пару фиктивных вершин начала и конца пути и соединив их со всеми кандидатами на начало и конец путешествия, мы получаем готовый граф, на котором можно запустить алгоритм Дейкстры.
Для решения каждой из подзадач, соответствующих разным местам отдыха, будет отдельный граф, что увеличит стоимость его строительства.
Этот и другие факторы, замедляющие наш алгоритм, еще предстояло преодолеть.
Оптимизации
Как можно почувствовать, прочитав название конкурса, его условия и рекомендации от Intel, конкурс был посвящен именно оптимизации, а не умению найти асимптотически быстрое решение.Если вы изучали в университете теорию сложности или хотя бы базовые алгоритмы, вы можете вспомнить, как классно отбрасывают константы, а иногда даже логарифмы и полиномы при оценке эффективности алгоритмов (если задача сложная и существующие на данный момент решения экспоненциальны).
На практике иногда дела обстоят иначе.
Быстрый алгоритм — это только половина успеха.
Давайте упомянем лишь некоторые из использованных нами оптимизаций.
Во-первых, решена проблема с многократным копированием графа.
Граф хранился в виде списков смежности, и можно было подготовить «каркас», а затем добавлять в него ребра отдельно для каждой подзадачи (каждого города отдыха).
После решения следующей подзадачи ребра, добавленные при ее решении, были эффективно удалены из списков смежности, и граф был готов к новому использованию.
Во-вторых, оказалось, что встроенная функция получения абсолютного времени из его календарного представления (mktime) работает очень медленно, а время во входных данных было задано в календарном формате.
Триста тысяч обращений к такой функции — и время работы увеличивается на десять секунд. К счастью, время в течение одного месяца в календаре линейно.
Таким образом, можно кэшировать абсолютное значение первой секунды каждого месяца при первом запросе, после чего в течение этого месяца преобразование времени из одного формата в другой требует всего лишь нескольких арифметических операций.
Быстрое преобразование времени vector<time_t> tc(100000);
time_t get_time(int year, int month) {
size_t key = 13 * year + month;
if(key >= tc.size()){
tc.resize(key * 2);
}
if (tc[key] == 0) {
tm time;
time.tm_year = year - 1900;
time.tm_mon = month - 1;
time.tm_mday = 0;
time.tm_hour = time.tm_min = time.tm_sec = 0;
time_t res = mktime(&time);
tc[key] = res;
}
return tc[key];
}
time_t convert_to_timestamp(int day, int month, int year, int hour, int minute, int seconde) {
time_t res = get_time(year, month);
res += (day) * 60 * 60 * 24;
res += hour * 60 * 60;
res += minute * 60;
res += seconde;
return res;
}
Третья существенная оптимизация была связана с чтением данных.
Этот этап занял гораздо больше времени, чем этапы построения графа и поиска пути в нем, и мы использовали отображенный в память ввод-вывод — это быстро — и написали собственный менеджер памяти, который умеет malloc, но не может освобождать.
Он запрашивает у ОС огромный кусок памяти, а затем распределяет его по частям между функциями чтения строк, требующими памяти.
Параллелизм
Наше решение оказалось совершенно непоследовательным.Любая попытка запустить хотя бы некоторые подзадачи в нескольких потоках приводила либо к замедлению, либо к неускорению, даже если эти подзадачи не использовали какие-либо общие данные и не требовали блокировок.
Мы убедили себя, что наше решение было недорогим в вычислительном отношении, но постоянно требовало большого количества обращений к различным областям памяти, поэтому пропускная способность оперативной памяти была узким местом.
Так ли это, точно узнать мы не успели, так как последние дни были потрачены на оптимизацию более важных деталей.
Хотя в приведенном ниже коде есть пара директив OpenMP, мы удалили даже их в последний момент перед отправкой финальной версии.
Код
Код нашего решения представляет собой совершенно нечитаемую мешанину макросов C++, но мы все равно попробуем.связь .
В таких задачах это вполне естественное состояние кода, но мы, конечно, не призываем писать большие проекты в одном стиле.
Выводы.
Нам удалось занять третье место в этом соревновании в России, а скорость нашего решения стала третьей во всей Европе.
Файл с сотнями мегабайт полетных данных был обработан нашей программой за несколько секунд. На итоговую оценку повлияла не только такая скорость, но и предоставленная документация, а также социальная активность, направленная на привитие любви к оптимизации в целом и популяризацию этого конкурса в частности.
Как вы можете понять из нашего рассказа, мы не использовали никаких сложных оптимизаций, нам не приходилось подбирать ключи компиляции или бороться за каждый бит. Надеемся, наша история убедила вас в том, что отличной скорости кода можно добиться, тщательно разрабатывая алгоритм и оптимизируя его наиболее важные части, и для этого не требуется никакого фанатизма.
Желаем всем интересных задач и эффективных решений! P.S. Весь список победителей находится на Веб-сайт Intel .
Теги: #оптимизация кода #Ускорьте свой код #Параллельное программирование #Высокая производительность #Алгоритмы
-
Аудиофильский Ssd – Невероятное Реально?
19 Oct, 24 -
Создание Инцидента Через Бот Ms Teams
19 Oct, 24 -
Конец Проекта
19 Oct, 24 -
Google I/O 2016: Watchface 2.0 — Осложнения
19 Oct, 24 -
Винамп Знает Всё :)
19 Oct, 24 -
О Компонентах И Интерфейсах
19 Oct, 24 -
Концерт Форума «Классика» В Санкт-Петербурге
19 Oct, 24
