Массивный и аппаратный параллелизм — горячие темы 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 имеет хорошую локальность: здесь хорошо разделённые единицы (исходные файлы) компилируются в объектные файлы, которые потом соединяет компоновщик.
