Виталий Аксенов - Конкурентные приоритетные очереди и их применение

Приоритетная очередь являются одной из фундаментальных структур данных. Например, она являются базовым блоком в алгоритмах поиска кратчайшего пути и планировщиках с приоритетами. Чтобы ускорить эти алгоритмы, хочется использовать параллелизацию, а значит хочется иметь многопоточную версию приоритетной очереди. К сожалению, не всё так просто, так как есть явное узкое место — операция extractMin. Теория говорит, что невозможно избавиться от него и одновременно давать чёткие гарантии на операцию. Что же тогда делать? В этом докладе мы рассмотрим идеи, которые позволяют ускорить конкурентную приоритетную очередь. Затем, мы выясним, что очередь с точными гарантиями на самом деле не всегда нужна, и, как следствие, можно ослабить требования. Как итог, мы получим быструю очередь MultiQueue, основную идею которой (choice of 2) можно использовать в других областях, например, машинном обучении. Ключевые слова: многопоточность, структуры данных, приоритетная очередь. Выступает: Виталий Аксенов, доцент ИТМО, руководитель совместной лаборатории ИТМО и ВК по распределённым вычислениям и магистерской программы «Программирование и Искусственный Интеллект». Член программных комитетов SmartData и Sysconf, соорганизатор международной школы SPTDC. --- Вопросы и комментарии — в Telegram-чате сообщества NoML: Презентация и материалы всех мероприятий — в базе знаний: Анонсы новых мероприятий и другая полезная информация — в канале сообщества NoML: