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

Разработанный в МТИ алгоритм 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 при подсчете числа операций, выполненных за одну секунду, продолжает демонстрировать линейный рост.

На самом деле SprayList выбирает задачи не вполне в случайном порядке, а формирует некую разновидность очереди с приоритетами, называемую «список пропусков» (skip list). Задачам присваиваются различные уровни приоритетов, и высокоприоритетные элементы очереди обрабатываются раньше низкоприоритетных.

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

В реализации проекта Копинскому и Ли помогали их наставник, профессор МТИ Нир Шавит и бывший студент Шавита, а ныне сотрудник Microsoft Research Дэн Алистар.

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