Массивный и аппаратный параллелизм — горячие темы 21 века. Для этого есть несколько приятных причин и одна довольно печальная.
Две приятные причины: комбинация отличной работы GPU в играх и при этом их неожиданное побочное использования в глубоком обучении ИИ, поскольку там на аппаратном уровне реализован массивный параллелизм. Печальная причина в том, что скорость однопроцессорных систем с 2006 года упёрлась в законы физики. Нынешние проблемы с утечкой и тепловым пробоем резко ограничивают увеличение тактовой частоты, а классическое снижение напряжения теперь натыкается на серьёзные проблемы с квантовым шумом.
Конкурируя за внимание публики, производители процессоров пытаются впихнуть в каждый чип всё больше процессорных ядер, рекламируя теоретическую общую производительность. Также быстро растут усилия на конвейеризацию и спекулятивные методы выполнения, которые применяют многопоточность под капотом, чтобы видимый программисту одиночный процессор быстрее обрабатывал инструкции.
Неудобная правда заключается в том, что многие из наших менее гламурных вычислительных задач просто не могут очень хорошо использовать видимую многопоточность. На это есть разные причины, которые несут разные последствия для программиста, и тут много путаницы. В этой статье хочу несколько прояснить ситуацию.
Во-первых, нужно чётко понимать, где лучше всего работает аппаратный параллелизм и почему. Посмотрим на вычисления для графики, нейронных сетей, обработки сигналов и биткоин-майнинга. Прослеживается закономерность: алгоритмы распараллеливания лучше всего работают на оборудовании, которое (а) специально разработано для их выполнения; (б) не может делать ничего другого!
Мы также видим, что входные данные для наиболее успешных параллельных алгоритмов (сортировка, сопоставление строк, быстрое преобразование Фурье, матричные операции, обратное квантование изображений и т. д.) выглядят довольно похоже. Как правило, у них метрическая структура и подразумевается различие между «ближними» и «дальними» данными, что позволяет разрезать их на части, поскольку связь между дальними элементами незначительна.
В терминах прошлой статьи о семантической локальности можно сказать, что параллельные методы применимы главным образом там, где у данных хорошая локальность. И они лучше всего работают на оборудовании с поддержкой только «ближних» связей, как систолическая матрица в сердце GPU.
С другой стороны, очень сложно написать программное обеспечение, которое эффективно производит такой раздел для входных данных с плохой локальностью на компьютерах общего назначения (архитектура фон Неймана).
В итоге можем сформулировать простую эвристику: Шансы на применение параллельных вычислений обратно пропорциональны степени неприводимой семантической нелокальности во входных данных.
Другим ограничением параллельных вычислений является то, что некоторые важные алгоритмы вообще не поддаются распараллеливанию — даже теоретически. Когда я впервые рассуждал на эту тему в блоге, то придумал термин «больной алгоритм», где SICK расшифровывается как «Serial, Intrinscally – Cope, Kiddo!». Среди значительных примеров: алгоритм Дейкстры нахождения кратчайшего пути; обнаружение циклов в ориентированных графах (с применением в солверах 3-SAT); поиск в глубину; вычисление n-го члена в криптографической цепочке хэшей; оптимизация сетевого потока… и это далеко не полный список.
Здесь тоже играет роль плохая локальность входных данных, особенно в контекстах графа и древовидной структуры. Криптографические цепочки хэшей невозможно распараллелить, потому что записи вычисляются в строгом порядке — это действительно важное правило для защиты цепочки от подделки.
И тут вступает блокировка: вы ничего не можете распараллелить, пока работает SICK-алгоритм.
Мы не закончили. Есть ещё как минимум два класса препятствий, причём весьма распространённые.
Во-первых, нет нужных инструментов. Большинство языков не поддерживают ничего, кроме мьютекса и семафоров. Это удобно, примитивы легко реализовать, но такая ситуация вызывает ужасные взрывы сложности в голове: практически невозможно осмыслить масштаб более четырёх взаимодействующих блокировок.
Если повезёт, вы получите более сговорчивый набор примитивов, такие как каналы Go (aka Communicating Sequential Processes) или систему владения/отправки/синхронизации в Rust. Но на самом деле мы не знаем, какой «правильный» язык примитивов для реализации параллелизма на фон-неймановской архитектуре. Возможно, даже нет одного правильного набора примитивов. Возможно, два или три различных набора подходят для разных проблемных областей, но они несоизмеримы как единица и квадратный корень из двух. На сегодняшний день в 2018 году никто толком не знает.
И последнее, но не менее важное ограничение — человеческий мозг. Даже на чётком алгоритме с хорошей локальностью данных и эффективными инструментами параллельное программирование просто трудное для людей, даже если алгоритм применяется довольно просто. Наш мозг не очень хорошо моделирует простейшие пространства состояний чисто последовательных программ, а тем более параллельных.
Мы знаем это, потому что существует множество реальных доказательств, что отладка параллельного кода более чем трудна. Этому мешают состояния гонки, дедлоки, самоустраняемые блокировки, коварные повреждения данных из-за слегка небезопасного порядка инструкций.
Думаю, что понимание этих ограничений становится более важным после краха закона масштабирования Деннарда. Из-за всех этих узких мест в программировании на части многоядерных систем всегда будет работать софт, не способный загрузить оборудование на 100% вычислительной мощности. Если посмотреть с другой стороны, у нас избыточное железо для текущих заданий. Сколько денег и усилий мы тратим впустую?
Производители процессоров хотят, чтобы вы переоценивали функциональные преимущества шикарных новых чипов с ещё большим количеством ядер. Как ещё им добыть денег для покрытия гигантских расходов на производство, при этом остаться в прибыли? Маркетинг прилагает все усилия, чтобы вы никогда не задавались вопросом, на каких задачах такая многопоточность действительно выгодна.
Честно говоря, такие задачи есть. Серверы в дата-центрах, обрабатывающие сотни тысяч параллельных транзакций в секунду, вероятно, достаточно хорошо распределяют нагрузку по ядрам. Смартфоны или встроенные системы тоже — в обоих случаях прикладываются значительные усилия для минимизации себестоимости и энергопотребления, что мешает вводить в строй избыточную мощность.
Но для обычных пользователей настольных компьютеров и ноутбуков? Меня терзают смутные сомнения. Здесь трудно понять ситуацию, потому что реальный рост производительности идёт от других факторов, таких как переход от HDD к SSD. Подобные достижения легко принять за эффект ускорения CPU, если не провести тщательное профилирование.
Вот основания для таких подозрений:
Среди моих читателей много людей, которые наверняка смогут разумно прокомментировать эту гипотезу. Интересно посмотреть, что они скажут.
UPDATE. Комментатор на G+ указал одну интересную пользу от многоядерных процессоров: они очень быстро компилируют код. Исходный код языков вроде C имеет хорошую локальность: здесь хорошо разделённые единицы (исходные файлы) компилируются в объектные файлы, которые потом соединяет компоновщик.
Две приятные причины: комбинация отличной работы GPU в играх и при этом их неожиданное побочное использования в глубоком обучении ИИ, поскольку там на аппаратном уровне реализован массивный параллелизм. Печальная причина в том, что скорость однопроцессорных систем с 2006 года упёрлась в законы физики. Нынешние проблемы с утечкой и тепловым пробоем резко ограничивают увеличение тактовой частоты, а классическое снижение напряжения теперь натыкается на серьёзные проблемы с квантовым шумом.
Конкурируя за внимание публики, производители процессоров пытаются впихнуть в каждый чип всё больше процессорных ядер, рекламируя теоретическую общую производительность. Также быстро растут усилия на конвейеризацию и спекулятивные методы выполнения, которые применяют многопоточность под капотом, чтобы видимый программисту одиночный процессор быстрее обрабатывал инструкции.
Неудобная правда заключается в том, что многие из наших менее гламурных вычислительных задач просто не могут очень хорошо использовать видимую многопоточность. На это есть разные причины, которые несут разные последствия для программиста, и тут много путаницы. В этой статье хочу несколько прояснить ситуацию.
Во-первых, нужно чётко понимать, где лучше всего работает аппаратный параллелизм и почему. Посмотрим на вычисления для графики, нейронных сетей, обработки сигналов и биткоин-майнинга. Прослеживается закономерность: алгоритмы распараллеливания лучше всего работают на оборудовании, которое (а) специально разработано для их выполнения; (б) не может делать ничего другого!
Мы также видим, что входные данные для наиболее успешных параллельных алгоритмов (сортировка, сопоставление строк, быстрое преобразование Фурье, матричные операции, обратное квантование изображений и т. д.) выглядят довольно похоже. Как правило, у них метрическая структура и подразумевается различие между «ближними» и «дальними» данными, что позволяет разрезать их на части, поскольку связь между дальними элементами незначительна.
В терминах прошлой статьи о семантической локальности можно сказать, что параллельные методы применимы главным образом там, где у данных хорошая локальность. И они лучше всего работают на оборудовании с поддержкой только «ближних» связей, как систолическая матрица в сердце GPU.
С другой стороны, очень сложно написать программное обеспечение, которое эффективно производит такой раздел для входных данных с плохой локальностью на компьютерах общего назначения (архитектура фон Неймана).
В итоге можем сформулировать простую эвристику: Шансы на применение параллельных вычислений обратно пропорциональны степени неприводимой семантической нелокальности во входных данных.
Другим ограничением параллельных вычислений является то, что некоторые важные алгоритмы вообще не поддаются распараллеливанию — даже теоретически. Когда я впервые рассуждал на эту тему в блоге, то придумал термин «больной алгоритм», где SICK расшифровывается как «Serial, Intrinscally – Cope, Kiddo!». Среди значительных примеров: алгоритм Дейкстры нахождения кратчайшего пути; обнаружение циклов в ориентированных графах (с применением в солверах 3-SAT); поиск в глубину; вычисление n-го члена в криптографической цепочке хэшей; оптимизация сетевого потока… и это далеко не полный список.
Здесь тоже играет роль плохая локальность входных данных, особенно в контекстах графа и древовидной структуры. Криптографические цепочки хэшей невозможно распараллелить, потому что записи вычисляются в строгом порядке — это действительно важное правило для защиты цепочки от подделки.
И тут вступает блокировка: вы ничего не можете распараллелить, пока работает SICK-алгоритм.
Мы не закончили. Есть ещё как минимум два класса препятствий, причём весьма распространённые.
Во-первых, нет нужных инструментов. Большинство языков не поддерживают ничего, кроме мьютекса и семафоров. Это удобно, примитивы легко реализовать, но такая ситуация вызывает ужасные взрывы сложности в голове: практически невозможно осмыслить масштаб более четырёх взаимодействующих блокировок.
Если повезёт, вы получите более сговорчивый набор примитивов, такие как каналы Go (aka Communicating Sequential Processes) или систему владения/отправки/синхронизации в Rust. Но на самом деле мы не знаем, какой «правильный» язык примитивов для реализации параллелизма на фон-неймановской архитектуре. Возможно, даже нет одного правильного набора примитивов. Возможно, два или три различных набора подходят для разных проблемных областей, но они несоизмеримы как единица и квадратный корень из двух. На сегодняшний день в 2018 году никто толком не знает.
И последнее, но не менее важное ограничение — человеческий мозг. Даже на чётком алгоритме с хорошей локальностью данных и эффективными инструментами параллельное программирование просто трудное для людей, даже если алгоритм применяется довольно просто. Наш мозг не очень хорошо моделирует простейшие пространства состояний чисто последовательных программ, а тем более параллельных.
Мы знаем это, потому что существует множество реальных доказательств, что отладка параллельного кода более чем трудна. Этому мешают состояния гонки, дедлоки, самоустраняемые блокировки, коварные повреждения данных из-за слегка небезопасного порядка инструкций.
Думаю, что понимание этих ограничений становится более важным после краха закона масштабирования Деннарда. Из-за всех этих узких мест в программировании на части многоядерных систем всегда будет работать софт, не способный загрузить оборудование на 100% вычислительной мощности. Если посмотреть с другой стороны, у нас избыточное железо для текущих заданий. Сколько денег и усилий мы тратим впустую?
Производители процессоров хотят, чтобы вы переоценивали функциональные преимущества шикарных новых чипов с ещё большим количеством ядер. Как ещё им добыть денег для покрытия гигантских расходов на производство, при этом остаться в прибыли? Маркетинг прилагает все усилия, чтобы вы никогда не задавались вопросом, на каких задачах такая многопоточность действительно выгодна.
Честно говоря, такие задачи есть. Серверы в дата-центрах, обрабатывающие сотни тысяч параллельных транзакций в секунду, вероятно, достаточно хорошо распределяют нагрузку по ядрам. Смартфоны или встроенные системы тоже — в обоих случаях прикладываются значительные усилия для минимизации себестоимости и энергопотребления, что мешает вводить в строй избыточную мощность.
Но для обычных пользователей настольных компьютеров и ноутбуков? Меня терзают смутные сомнения. Здесь трудно понять ситуацию, потому что реальный рост производительности идёт от других факторов, таких как переход от HDD к SSD. Подобные достижения легко принять за эффект ускорения CPU, если не провести тщательное профилирование.
Вот основания для таких подозрений:
- Серьёзные параллельные вычисления на настольных/портативных компьютерах происходят только на GPU.
- Больше чем два ядра в процессоре обычно бесполезны. Операционные системы могут распределять потоки приложений, но типичный софт не способен использовать параллелизм, а большинству пользователей редко удаётся одновременно запускать большое количество разных приложений, потребляющих много ресурсов CPU, чтобы полностью загрузить своё оборудование.
- Следовательно, большинство четырёхъядерных систем основную часть времени не делают ничего, кроме выработки тепла.
Среди моих читателей много людей, которые наверняка смогут разумно прокомментировать эту гипотезу. Интересно посмотреть, что они скажут.
UPDATE. Комментатор на G+ указал одну интересную пользу от многоядерных процессоров: они очень быстро компилируют код. Исходный код языков вроде C имеет хорошую локальность: здесь хорошо разделённые единицы (исходные файлы) компилируются в объектные файлы, которые потом соединяет компоновщик.
