Изучение уровня параллелизма

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

Большое спасибо за любые очки!

Роберт

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

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

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

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

Тем не менее, есть несколько областей, где человек может помочь процессу.

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

float f, g, h, i; float j = f + g + h + i; 

вы, скорее всего, получите нулевой ILP, потому что написанный вами код оценивается как ((f + g) + h) + i : результат первого добавления используется как операнд для следующего, результат которого используется как операнд в окончательном дополнении. Никакие два дополнения не могут выполняться параллельно.

Если вы вместо этого напишите его как float j = (f + g) + (h + i) , CPU сможет выполнять f+g и h+i параллельно. Они не зависят друг от друга.

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

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

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

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

Когда нет зависимостей, CPU будет планировать выполнение операций параллельно. Итак, все, что вам нужно сделать, чтобы использовать ILP, – это разбить длинные сети зависимостей.

Конечно, это проще сказать, чем сделать … 🙂

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

Если я правильно прочитаю, вас не интересуют SIMD или streamи, просто получая оптимальный порядок нормальных инструкций CPU.

Первое, что нужно проверить, – это то, что ваш компилятор нацеливается на правильный подтип процессора. Компилятор обычно переупорядочивает инструкции для сокращения зависимостей от одной инструкции к другой, но для компилятора очень важно знать, какую версию процессора вы планируете. (в частности, более старый GCC иногда не может обнаружить последние процессоры, а затем оптимизирует для i386).

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

Наконец, для Intel cpu, собственный компилятор Intel C ++ утверждает, что это лучше всего. У них также есть профилировщик vTune, который специально может сообщить об эффективном использовании ALU в горячих точках вашей программы.

У вас есть основания полагать, что компилятор плохо справляется с раскрытием ILP? Если вы работаете на уровне алгоритма, то обычно нужно сосредоточиться на параллелизме данных и оптимизации более высокого порядка. Оптимизация для ILP была бы абсолютно последним шагом и полностью связана с тем, как работает компилятор. В общем случае, если вы можете устранить ложные зависимости данных, достойный компилятор должен сделать для вас все остальное.

Что-то вроде Acumems SlowSpotter может помочь (если вам действительно не нужно вручную оптимизировать ILP, в этом случае я не знаю хорошего инструмента, если компилятор не может выплюнуть для вас хороший отчет по оптимизации, IIRC Cray и SGI MIPS компиляторы могут создавать такие отчеты.).

Предыдущие ответы хороши. Кроме того, на сайте Intel есть чему поучиться, и если у вас есть бюджет, то стоит обратить внимание на инструменты Intel.
Статьи Intel по оптимизации