`

СПЕЦІАЛЬНІ
ПАРТНЕРИ
ПРОЕКТУ

Чи використовує ваша компанія ChatGPT в роботі?

BEST CIO

Определение наиболее профессиональных ИТ-управленцев, лидеров и экспертов в своих отраслях

Человек года

Кто внес наибольший вклад в развитие украинского ИТ-рынка.

Продукт года

Награды «Продукт года» еженедельника «Компьютерное обозрение» за наиболее выдающиеся ИТ-товары

 

В MIT разработана схема эффективного распараллеливания общих алгоритмов

0 
 

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

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

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

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

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

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

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

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

Ready, set, buy! Посібник для початківців - як придбати Copilot для Microsoft 365

0 
 

Напечатать Отправить другу

Читайте также

 

Ukraine

 

  •  Home  •  Ринок  •  IТ-директор  •  CloudComputing  •  Hard  •  Soft  •  Мережі  •  Безпека  •  Наука  •  IoT