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

С алгоритмами, которые используют распространенную структуру сведений, называемую очередью по приоритетам (priority queue), такая прямая пропорциональность сберегается примерно до восьми ядер, но с дальнейшим добавлением ядер рост быстродействия замедляется. Причина заключается в том, что к началу очереди, сформированной по приоритетности, одновременно пытаются обратиться многие ядра. Возникающие конфликты тормозят вычисления — иногда на многие порядки величины.

На февральском симпозиуме ACM по принципам и практике параллельного программирования, ученые из лаборатории CSAIL (Computer Science and Artificial Intelligence Laboratory) Массачусетского технологического института (MIT) расскажут о новом способе применения приоритетных очередей. В симуляциях алгоритмы с такой структурой сведений продолжали демонстрировать рост быстродействия с увеличением числа ядер до 80.

Для достижения этого аспиранты MIT Джастин Копински (Justin Kopinsky) и Джерри Ли (Jerry Li) ослабили требование, обязующее ядра выбирать элемент, стоящий в начале очереди. Если все первые элементы обязаны обрабатываться параллельно, распределение по ядрам способен выполняться случайным образом.

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

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

Для ликвидации подобных заторов, сотрудники MIT применили так называемый список пропусков (skip list), строящий иерархию связанных списков поверх основного. На каждом следующем уровне количество элементов списка снижается вдвое. Чтобы найти элемент в корневом списке, довольно следовать указателям верхнего списка пока не обнаружится промежуток, в котором находится нужный элемент, затем спуститься на уровень ниже и повторить процедуру, и так далее, пока не будет достигнут корневой список.

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