Инструкция-Уровень-Параллелизм Разведка - PullRequest
9 голосов
/ 22 февраля 2010

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

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

Роберт

Ответы [ 5 ]

10 голосов
/ 22 февраля 2010

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

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

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

5 голосов
/ 22 февраля 2010

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

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

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

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

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

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

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

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

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

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

Когда нет никаких зависимостей, ЦПУ будет планировать операции для параллельного выполнения. Поэтому все, что вам нужно сделать, чтобы использовать ILP, это разорвать длинные цепочки зависимостей.

Конечно, легче сказать, чем сделать ...:)

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

3 голосов
/ 22 февраля 2010

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

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

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

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

1 голос
/ 22 февраля 2010

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

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

0 голосов
/ 22 февраля 2010

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...