Почему векторизация в целом быстрее, чем циклы?

Векторизация (как обычно используется этот термин) относится к операции SIMD (одна инструкция, несколько данных).

По сути, это означает, что одна инструкция выполняет одну и ту же операцию над несколькими операндами параллельно. Например, чтобы умножить вектор размера N на скаляр, назовем M количеством операндов этого размера, с которыми он может работать одновременно. Если это так, то количество инструкций, которые ему нужно выполнить, составляет приблизительно N / M, где (с чисто скалярными операциями) ему придется выполнить N операций.

Например, текущий набор инструкций Intel AVX 2 использует 256-битные регистры. Они могут использоваться для хранения (и обработки) набора из 4 операндов по 64 бита каждый или 8 операндов по 32 бита каждый.

Итак, предполагая, что вы имеете дело с 32-битными действительными числами одинарной точности, это означает, что одна инструкция может выполнять 8 операций (умножения, в вашем случае) одновременно, поэтому (по крайней мере, теоретически) вы можете завершить N умножений, используя только инструкции умножения N / 8. По крайней мере, теоретически это должно позволить операции завершиться примерно в 8 раз быстрее, чем позволяет выполнение одной инструкции за раз.

Конечно, точная выгода зависит от того, сколько операндов вы поддерживаете на инструкцию. Первые попытки Intel поддерживали только 64-битные регистры, поэтому для одновременной работы с 8 элементами эти элементы могли быть только 8 битами каждый. В настоящее время они поддерживают 256-битные регистры, и они объявили о поддержке 512-битных (и, возможно, они даже поставили это в несколько высокопроизводительных процессоров, но не в обычных потребительских процессорах, по крайней мере, пока). Хорошее использование этой возможности тоже может оказаться, мягко говоря, нетривиальным. Планирование инструкций, чтобы у вас было N операндов в наличии и в нужных местах в нужное время, не обязательно является легкой задачей (вообще).

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

Однако имейте в виду, что векторизация - это не единственный способ, с помощью которого ЦП может выполнять операции параллельно. Также существует возможность параллелизма на уровне команд, который позволяет одному ЦП (или одному ядру ЦП) выполнять более одной инструкции за раз. Большинство современных ЦП включают оборудование для (теоретически) выполнения до 4 инструкций за такт ¹, если инструкции представляют собой сочетание загрузки, сохранения и ALU. Они могут регулярно выполнять в среднем около 2 инструкций за такт или больше в хорошо настроенных циклах, когда память не является узким местом.

Затем, конечно, есть многопоточность - выполнение нескольких потоков инструкций на (по крайней мере, логически) отдельных процессорах / ядрах.

Итак, современный ЦП может иметь, скажем, 4 ядра, каждое из которых может выполнять 2 векторного умножения за такт, и каждая из этих инструкций может работать с 8 операндами. Так что, по крайней мере теоретически, он может выполнять 4 * 2 * 8 = 64 операции за такт.

Некоторые инструкции имеют лучшую или худшую пропускную способность. Например, FP добавляет пропускную способность ниже, чем FMA или умножает на Intel до Skylake (1 вектор на такт вместо 2). Но логическая логика, такая как AND или XOR, имеет 3 вектора на тактовую пропускную способность; не требуется много транзисторов для создания исполнительного блока AND / XOR / OR, поэтому процессоры копируют их. Узкие места на общей ширине конвейера (интерфейс, который декодирует и выдает в некорректную часть ядра) являются обычными при использовании инструкций с высокой пропускной способностью, а не узкими местами на конкретном исполнительном блоке.

1. Но со временем у процессоров появляется больше доступных ресурсов, поэтому это число растет.

Векторизация имеет два основных преимущества.

1. Основное преимущество заключается в том, что оборудование, разработанное для поддержки векторных инструкций, обычно имеет оборудование, способное выполнять несколько операций ALU параллельно при использовании векторных инструкций. Например, если вы попросите его выполнить 16 сложений с помощью 16-элементной векторной инструкции, у него может быть 16 сумматоров, которые могут выполнять все добавления одновременно, параллельно. Единственный способ получить доступ ко всем этим сумматорам ¹ - это векторизация. С помощью скалярных инструкций вы просто получите 1 одинокий сумматор.

2. Обычно использование векторных инструкций позволяет сэкономить на накладных расходах. Вы загружаете и храните данные большими порциями (до 512 бит за раз на некоторых последних процессорах Intel), и каждая итерация цикла выполняет больше работы, поэтому накладные расходы цикла обычно ниже в относительном смысле ², и вам нужно меньше инструкций для выполнения той же работы, чтобы снизить нагрузку на процессор и т. д.

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

¹ Или по крайней мере 15 из 16, возможно, один также используется для выполнения скалярных операций.

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

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

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

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