Сколько раз петля должна быть без наматывания?

Question

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

Answer 1

Иногда имеет смысл даже , а не развернуть цикл (для процессоров Core2 и выше), потому что у них действительно есть «детектор петлевого потока» (они называют его LSD).Просто посмотрите его в Руководстве по оптимизации Intel.

Если код помещается в (очень маленькую) очередь, то процессору не нужно извлекать / декодировать инструкции из L1-Instruction-Cache, которыйможет дать некоторую производительность.

Answer 2

Эмпирическое правило заключается в том, что вы раскручиваетесь так, чтобы:

• операции выполняются на «естественных» границах 4,8,16,32 .. байт
• вы не оказываете чрезмерное давление на регистр (т. Е. Вы не начинаете манипулирование регистрами в памяти)
• вы не начинаете повторять одну и ту же последовательность команд снова и снова

По сути, вы развертываете до тех пор, пока можете использовать больше ресурсов, и останавливаетесь, когда больше не можете измерить какой-либо прирост производительности.

Answer 3

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

Answer 4

Я хотел бы добавить свой ответ, потому что, хотя ответ Торбьерна Гилбертинга хорош, он не полный IMO

Существуют различные улучшения из-за развертывания:

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

Уменьшить накладные расходы цикла , когда тело цикла мало, накладные расходы цикла (обычно приращение + сравнение + скачок ) потребляют значительное количествовремя.

total cost = N * (loop body + loop overhead)

при однократном развертывании вы получите

total cost = N/2 * (2 * loop body + loop overhead)  
           = N * loop body + N / 2 * loop overhead

, если издержки цикла невелики по сравнению с телом цикла, развертывание не даст вам никакой выгоды за счет увеличения размера кода.Пример: когда тело цикла имеет 10-кратное накладные расходы, развертывание дает в лучшем случае улучшение на 5%.

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

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