Традиционные реализации очереди, формируемой в соответствии с приоритетами, работают достаточно эффективно, если число ядер не превышает восьми. Если же ядер больше, то производительность начинает снижаться
Источник: Christine Daniloff/MIT

С каждым новым поколением процессоров количество ядер растет, а перед разработчиками все острее встает вопрос, как лучше использовать параллельные мощности.

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

Разработанный в МТИ алгоритм SprayList позволяет многоядерным процессорам распределять нагрузку и избегать узких мест, сдерживающих производительность.

В случае успешного практического внедрения алгоритмы наподобие SprayList могли бы способствовать повышению эффективности новых многоядерных процессоров, таких как 18-ядерный серверный чип Intel E5 2600v3.

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

Когда более десяти лет тому назад в мире начали появляться первые двухъядерные и четырехъядерные процессоры, программисты решили отдать предпочтение простой и хорошо известной очереди с приоритетами — технологии, предусматривающей передачу очередной задачи следующему свободному ядру. Очередь формируется по принципу «первым пришел — первым вышел» (First In First Out, FIFO) и упорядочивается с учетом приоритетов, назначаемых заданиям.

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

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

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

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

Но при существенном увеличении числа ядер все эти недостатки компенсируются преимуществами более «свободного» стиля случайного распределения.

Для проверки эффективности алгоритма SprayList исследователи протестировали его на сервере Fujitsu RX600 S6, который был оснащен четырьмя десятиядерными процессорами Intel Xeon E7–4870 (Westmere EX), поддерживающими 80 аппаратных потоков. По сути, он имитировал работу 80-ядерного процессора.

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

«Пользователям, специально выбирающим очередь с приоритетами, нужно, чтобы задачи с высоким приоритетом выполнялись раньше, чем задачи с низким, — пояснил научный сотрудник МТИ Джастин Копински, вместе со своим товарищем Джерри Ли руководивший описанными работами. — Оказалось, что при достаточном уровне свободы мы соблюдаем ранее принятые правила — задачи с наивысшим, десятым приоритетом выполнялись раньше задач с первым приоритетом. Чисто случайное распределение привело бы к тому, что первыми, возможно, стали бы обрабатываться задачи с низким приоритетом».