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

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

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