Главная » Хабрахабр » [Перевод] Пессимизм насчёт многопоточности

[Перевод] Пессимизм насчёт многопоточности

Массивный и аппаратный параллелизм — горячие темы 21 века. Для этого есть несколько приятных причин и одна довольно печальная.

Печальная причина в том, что скорость однопроцессорных систем с 2006 года упёрлась в законы физики. Две приятные причины: комбинация отличной работы GPU в играх и при этом их неожиданное побочное использования в глубоком обучении ИИ, поскольку там на аппаратном уровне реализован массивный параллелизм. Нынешние проблемы с утечкой и тепловым пробоем резко ограничивают увеличение тактовой частоты, а классическое снижение напряжения теперь натыкается на серьёзные проблемы с квантовым шумом.

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

Посмотрим на вычисления для графики, нейронных сетей, обработки сигналов и биткоин-майнинга. Во-первых, нужно чётко понимать, где лучше всего работает аппаратный параллелизм и почему. Прослеживается закономерность: алгоритмы распараллеливания лучше всего работают на оборудовании, которое (а) специально разработано для их выполнения; (б) не может делать ничего другого!

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

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

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

В итоге можем сформулировать простую эвристику: Шансы на применение параллельных вычислений обратно пропорциональны степени неприводимой семантической нелокальности во входных данных.

Когда я впервые рассуждал на эту тему в блоге, то придумал термин «больной алгоритм», где SICK расшифровывается как «Serial, Intrinscally – Cope, Kiddo!». Другим ограничением параллельных вычислений является то, что некоторые важные алгоритмы вообще не поддаются распараллеливанию — даже теоретически. Среди значительных примеров: алгоритм Дейкстры нахождения кратчайшего пути; обнаружение циклов в ориентированных графах (с применением в солверах 3-SAT); поиск в глубину; вычисление n-го члена в криптографической цепочке хэшей; оптимизация сетевого потока… и это далеко не полный список.

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

И тут вступает блокировка: вы ничего не можете распараллелить, пока работает SICK-алгоритм.

Есть ещё как минимум два класса препятствий, причём весьма распространённые. Мы не закончили.

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

Но на самом деле мы не знаем, какой «правильный» язык примитивов для реализации параллелизма на фон-неймановской архитектуре. Если повезёт, вы получите более сговорчивый набор примитивов, такие как каналы Go (aka Communicating Sequential Processes) или систему владения/отправки/синхронизации в Rust. Возможно, два или три различных набора подходят для разных проблемных областей, но они несоизмеримы как единица и квадратный корень из двух. Возможно, даже нет одного правильного набора примитивов. На сегодняшний день в 2018 году никто толком не знает.

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

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

Из-за всех этих узких мест в программировании на части многоядерных систем всегда будет работать софт, не способный загрузить оборудование на 100% вычислительной мощности. Думаю, что понимание этих ограничений становится более важным после краха закона масштабирования Деннарда. Сколько денег и усилий мы тратим впустую? Если посмотреть с другой стороны, у нас избыточное железо для текущих заданий.

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

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

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

Вот основания для таких подозрений:

  1. Серьёзные параллельные вычисления на настольных/портативных компьютерах происходят только на GPU.
  2. Больше чем два ядра в процессоре обычно бесполезны. Операционные системы могут распределять потоки приложений, но типичный софт не способен использовать параллелизм, а большинству пользователей редко удаётся одновременно запускать большое количество разных приложений, потребляющих много ресурсов CPU, чтобы полностью загрузить своё оборудование.
  3. Следовательно, большинство четырёхъядерных систем основную часть времени не делают ничего, кроме выработки тепла.

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

Комментатор на G+ указал одну интересную пользу от многоядерных процессоров: они очень быстро компилируют код. UPDATE. Исходный код языков вроде C имеет хорошую локальность: здесь хорошо разделённые единицы (исходные файлы) компилируются в объектные файлы, которые потом соединяет компоновщик.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Как провалить внедрение CRM-системы?

Одной моей коллеге очень хотелось иметь iPhone 4S. Тогда это был просто верх понта. Получив премию, она отказалась от отпуска и купила его — белый, приятно увесистый, зависть всей коммерческой службы. Через некоторое время она начала жаловаться, что, мол, не ...

Проверка FreeRDP с помощью анализатора PVS-Studio

FreeRDP – свободная реализация клиента Remote Desktop Protocol (RDP), протокола, реализующего удаленное управление компьютером, разработанного компанией Microsoft. Проект поддерживает множество платформ, среди которых Windows, Linux, macOS и даже iOS с Android. Этот проект выбран первым в рамках цикла статей, посвященных ...