В ноябре 2012 года был дан старт конкурсу по параллельному программированию от компании Intel, и этому даже был посвящён отдельный пост на хабре. О конкурсе мы узнали от нашего преподавателя Евгения Калишенко. Он читает курс по «высокопроизводительным и параллельным вычислениям» в Санкт-Петербургском Академическом Университете и стал руководителем нашей команды.
Цель конкурса заключалась в том, чтобы в течение нескольких недель написать и оптимизировать решение одной алгоритмической задачи. Прежде чем описывать её условие, отметим несколько особенностей конкурса.
Особенности конкурса
Во-первых, тестирование решений проходило на компьютере с несколькими десятками ядер. Этим конкурс отличался от известных студенческих олимпиад формата ACM, на которых параллелить код бесполезно: временем выполнения считается суммарное затраченное ядрами время. Сам тип предложенной задачи был очень схож с задачами, предлагаемыми на этих олимпиадах.
Во-вторых, для задачи было дано референсное решение. Это код, который решает задачу гарантированно правильно, но очень медленно. Одной из возможных стратегий была оптимизация и распараллеливание этого решения. Можно было и полностью переписать алгоритм, но в этом случае требовалось сохранить его семантику. Правильность решения участника определялась простым diff'ом между ответами, данными конкурсным и референсным решениями на нескольких тестах. Забегая вперёд, скажу, что мы выбрали нечто среднее между этими двумя вариантами: код, ответственный за ввод и вывод результатов, мы позаимствовали из референсного решения, а алгоритм полностью переписали сами. Этим мы обезопасили себя от глупых ошибок, связанных с несоответствием формата вывода чисел с плавающей точкой, лишних пробелов и орфографических ошибок в выводе. Теперь о предложенной задаче.
Условие
Во входных файлах даны: список авиарейсов с указанием компаний, которые их организуют; список групп авиакомпаний, образующих «альянсы». Вывести в выходной файл нужно самые дешёвые маршруты, удовлетворяющие нескольким требованиям. «Легенда» такая: мы летим из родного города на конференцию, а потом возвращаемся обратно. При этом мы, возможно, хотим по дороге отдохнуть в одном из указанных городов, заглянув туда до или после посещения конференции. Есть ограничения на время нашего прибытия на конференцию, на время вылета оттуда и на желаемое время отдыха. Просчитать нужно лучший маршрут для каждого из городов, которые мы хотим посетить, а так же для того варианта, что отдыхать мы всё-таки не станем. Ещё одно условие: лететь подряд двумя рейсами одной авиакомпании получается на 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);
}
}
Однако, ещё нужно учесть, что наш путь должен обязательно пройти через конференцию и место отдыха. Давайте вначале решим задачу поиска кратчайшего пути в графе между двумя вершинами A и B и проходящего через вершину C. Это можно сделать так: скопируем граф G, получив две его копии G и G' (назовём их слоями). Соединим вершину C с вершиной C' (копией C) графа G'. После этого можно искать путь между вершинами А и B' — он гарантированно пройдет через С, так как других способов перепрыгнуть с одного слоя на другой просто нет.
Вы можете сказать, что проще просто найти путь от А до 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;
}
Третья существенная оптимизация была связана с чтением данных. Этот этап занимал гораздо большее время, чем этапы построения графа и поиска пути в нём, и мы использовали memory mapped IO — это быстро — и написали свой менеджер памяти, который умеет malloc, но не умеет free. Он просит у ОС огромный кусок памяти, после чего раздаёт его по частям нуждающимся в памяти функциям чтения строк.
Параллельность
Наше решение оказалось совершенно не параллельным. Любая попытка запустить хотя бы какие-нибудь подзадачи в несколько потоков приводила либо к замедлению, либо к неускорению, даже если эти подзадачи совершенно не использовали общих данных и не требовали блокировок. Мы убедили себя в том, что наше решение вычислительно нетрудоёмкое, но постоянно требует множества обращений к разным областям памяти, поэтому пропускная способность ОЗУ и была бутылочным горлышком. Так ли это, достоверно узнать мы не успели, так как последние дни ушли на оптимизацию более важных деталей. Хотя в выложенном ниже коде есть пара директив OpenMP, но даже их мы в последний момент перед отправкой финальной версии удалили.
Код
Код нашего решения представляет собой совершенно нечитаемую мешанину с макросами на С++, но мы всё-таки дадим на него ссылку. В подобных задачах это совершенно естественное состояние кода, но мы, конечно, не призываем писать в таком же стиле большие проекты.
Выводы.
Нам удалось занять третье место на этом конкурсе по России, а скорость нашего решения оказалась третьей по всей Европе. Файл с сотней мегабайт данных о рейсах обрабатывался нашей программой за несколько секунд. На финальную оценку влияла не только эта скорость, но и предоставленная документация, а так же социальная активность, направленная на прививание любви к оптимизациям в общем и популяризацию этого конкурса в частности. Как можно понять из нашего рассказа, мы не использовали никаких сложных оптимизаций, нам не пришлось подбирать ключи компиляции или бороться за каждый бит. Надеемся, что наш рассказ убедил вас в том, что отличной скорости работы кода можно достичь тщательной разработкой алгоритма и оптимизацией самых критических его частей, причём никакого фанатизма для этого не требуется.
Мы желаем всем интересных задач и эффективных решений!
P.S.
Весь список победителей — на сайте Intel.
Автор: krasko
