Новая "структура данных" для работы на многоядерных чипах

Каждый студент в области информатики проходит курс по структуре данных, которая описывает различные способы организации данных в памяти компьютера. Каждая из структур данных имеет свои преимущества: одни хороши для быстрого восстановления, другие – для эффективного поиска, третьи – для быстрых вставок и удалений, и так далее.

Сегодня производители оборудования делают компьютерные чипы быстрее, наделяя их большим количеством ядер, или блоков обработки. В то время как некоторые структуры данных хорошо приспособлены к многоядерной архитектуре, то другие – нет. В принципе, удвоение количества ядер должно удвоить эффективность вычислений. Для алгоритмов, которые используют общую структуру данных под названием очередь с приоритетами, это было верно приблизительно до восьми ядер, но дальнейшее увеличение их количества на самом деле вызывает падение производительности.

На симпозиуме Ассоциации вычислительной техники «О принципах и практике параллельного программирования», состоявшегося в феврале, исследователи из Лаборатории информатики и искусственного интеллекта Массачусетского технологического института описали новый способ реализации приоритетных очередей, который позволяет им не отставать от прогресса в области многоядерных процессоров. При моделировании алгоритмы, использующие их структуру данных, продолжали демонстрировать улучшение производительности при добавлении новых ядер, в общей сложности, до 80 единиц.

Структура данных для очереди с приоритетами – это, как следует из названия, последовательности элементов данных в соответствии с приоритетами, назначенными им при записи в память. В любой момент времени только элемент с наивысшим приоритетом может быть восстановлен. Приоритетные очереди занимают центральное место в стандартных алгоритмах для нахождения кратчайшего пути через сеть, для моделирования события, и они используются для целого ряда других приложений, начиная от сжатия данных до сетевого планирования.

В многоядерных системах, однако, возникают конфликты, когда несколько ядер пытаются получить доступ к первому элементу приоритетной очереди одновременно. Проблема усугубляется в связи с использованием современными чипами кэш-памяти – высокоскоростных банков памяти, где ядра хранят локальные копии часто используемых данных.

«Как вы читаете фронт очереди, все первые элементы очереди будут в кэше, - говорит Джастин Копинский (Justin Kopinsky), аспирант MIT в области электротехники и компьютерных наук и один из соавторов новой статьи. - Все ядра пытаются записать первый элемент в свой кэш, а затем его обработать, но потом какое-то ядро пишет на него, и это делает несостоятельными кэш для всех остальных. И это может снизить производительность на порядок, может быть, на несколько порядков».

Чтобы избежать этой проблемы, Копинский, аспирант Джерри Ли (Jerry Li), их руководитель, профессор вычислительной техники и информатики Нир Шавит (Nir Shavit) и Дэн Элистар (Dan Alistarh) из Microsoft Research ослабили требования для каждого ядра получать доступ к первому элементу в очереди. Если элементы во фронтальной части очереди могут быть обработаны параллельно, – что должно быть так или иначе в случае многоядерных вычислений, – они просто могут назначаться ядрам в случайном порядке.

Но ядро должно знать, где найти назначенный ему элемент данных, что сложнее, чем кажется. Структуры данных, как правило, просты для операций вставки и удаления, что связано с простотой адресации. Вы могли бы, например, назначить каждой позиции в очереди свой собственный адрес памяти: для нахождения пятого элемента нужно просто обратиться по пятому адресу.

Но затем, если вы хотите вставить новый элемент между, скажем, четвертым и пятым элементом, вам придется скопировать последний элемент в очереди в первой пустой адрес, затем скопировать предпоследний в адрес элемента, который освободился, и так далее, до тех пор, пока не освободится пятый адрес. Приоритетные очереди постоянно обновляются, поэтому такой подход является крайне непрактичным.

Альтернативой является использование того, что известно как связанный список. Каждый элемент связанного списка состоит из элемента данных и указателя на адрес памяти следующего элемента. Вставка нового элемента между элементами четыре и пять тогда просто сводится к обновлению двух указателей.

Единственный способ найти конкретный элемент в связанном списке, однако, начать с первого элемента и продвигаться по последовательности указателей. Это представляет проблему, если несколько ядер пытаются изменить элементы данных одновременно. Скажем, какому-то ядру был назначен элемент пять. Ядро обращается к началу списка и начинает его просматривать сверху вниз. Но другое ядро уже в процессе изменения элемента три, так что первое ядро должно стоять и ждать, пока это не сделано.

Исследователи из MIT преодолели этот тип затора, предложив другую структуру данных, называемую список пропуска (skip list). Список пропуска начинается со связанного списка и строит иерархию связанных списков на его вершине. Скажем, только половина элементов в корневом списке включена в список одного уровня вверх по иерархии. Только половина элементов во втором уровне, включена в третий и так далее.

Список пропуска был разработан, чтобы сделать продвижение по связанному списку более эффективным. Чтобы найти данный элемент в корневом списке, нужно следовать по указателям через верхний список, пока не определите разрыв, затем перейти вниз на один слой и повторить процесс.

Но алгоритм исследователей из MIT стартует дальше внизу по иерархии; как далеко внизу, зависит от того, сколько ядер пытается получить доступ к корневому списку. Каждое ядро перемещается на некоторое случайное число шагов и прыжков вниз на следующий уровень иерархии. Этот процесс повторяется до тех пор, пока ядро не достигнет корневого списка. Коллизии все еще могут случаться, особенно, когда ядро модифицирует элемент данных, который появляется на нескольких уровнях иерархии, но они происходят намного реже.

Общая "структура данных", обновленная таким образом, что она будет работать с многоядерными чипами