Цикл с нулевыми издержками
 | Эта статья нуждается в дополнительных цитатах для проверки . ( ноябрь 2020 г. ) |
 | Эта статья может быть слишком технической для понимания большинства читателей . ( Август 2020 г. ) |
Цикл с нулевыми издержками — это особенность некоторых процессора наборов инструкций , аппаратное обеспечение которых может автоматически повторять тело цикла , вместо того, чтобы требовать для этого программных инструкций, которые занимают циклы (и, следовательно, время). для этого [1] [2] Циклы с нулевыми издержками распространены в процессорах цифровых сигналов и некоторых наборах команд CISC .
Фон
[ редактировать ]Во многих наборах команд цикл должен быть реализован с использованием инструкций для увеличения или уменьшения счетчика, проверки того, достигнут ли конец цикла, и, если нет, перехода к началу цикла, чтобы его можно было повторить. Хотя обычно это занимает всего лишь около 3–16 байтов пространства для каждого цикла, даже этот небольшой объем может быть значительным в зависимости от размера кэшей ЦП . Более важно то, что для выполнения каждой из этих инструкций требуется время, время, которое не тратится на полезную работу.
Накладные расходы такого цикла очевидны по сравнению с полностью развернутым циклом , в котором тело цикла дублируется ровно столько раз, сколько оно будет выполнено. В этом случае на инструкции по повторению тела цикла не тратится ни пространство, ни время выполнения. Однако дублирование, вызванное развертыванием цикла, может значительно увеличить размер кода, а больший размер может даже повлиять на время выполнения из-за промахов в кэше . (По этой причине циклы обычно разворачиваются лишь частично, например, преобразуются в цикл, который выполняет работу четырех итераций за один шаг перед повторением. Это уравновешивает преимущества развертывания с накладными расходами на повторение цикла.) Более того, полностью развернуть цикл возможно только для ограниченного числа циклов: тех, число итераций которых известно во время компиляции .
Например, следующий код C можно скомпилировать и оптимизировать в следующий ассемблерный код x86:
| C-код | Сборка |
|---|---|
unsigned int array[100];
unsigned int i;
for (i = 0; i < 100; i++) {
array[i] = i;
}
|
; Set up number of loop iterations.
; Note that the compiler has reversed the loop
; so that it counts backwards from 99 to 0,
; rather than up from 0 to 99.
mov eax, 99
.LABEL:
; array[i] = i
mov DWORD PTR array[0+eax*4], eax
; Decrement i
sub eax, 1
; Check i >= 0. If true, repeat the loop.
jnb .LABEL
|
Выполнение
[ редактировать ]Процессоры с нулевыми циклическими затратами имеют машинные инструкции и регистры для автоматического повторения одной или нескольких инструкций. В зависимости от доступных инструкций они могут подходить только для циклов, управляемых счетом («циклы for»), в которых количество итераций может быть рассчитано заранее, или только для циклов, управляемых по условию («циклы while»), таких как операции в строках с нулевым завершением .
Примеры
[ редактировать ]ПОС
[ редактировать ]В PIC наборе инструкций REPEAT и DO инструкции реализуют циклы с нулевыми издержками. [1] REPEAT повторяет только одну инструкцию, в то время как DO повторяет указанное количество следующих инструкций.
Черноперый
[ редактировать ]Blackfin предлагает два цикла с нулевыми издержками. [3] Циклы могут быть вложенными; если оба аппаратных цикла настроены с одним и тем же адресом «конца цикла», цикл 1 будет вести себя как внутренний цикл и повторяться, а цикл 0 будет вести себя как внешний цикл и повторяться только в том случае, если цикл 1 не будет повторяться.
Управление контурами осуществляется с помощью LTx и LBx регистры ( x либо от 0 до 1), чтобы установить верхнюю и нижнюю часть цикла — то есть первую и последнюю выполняемые инструкции, которые могут быть одинаковыми для цикла только с одной инструкцией — и LCx для количества циклов. Цикл повторяется, если LCx не равно нулю в конце цикла, и в этом случае LCx уменьшается.
Регистры цикла можно установить вручную, но обычно на загрузку регистров уходит 6 байт, а на настройку загружаемых значений — 8–16 байт. Более распространенным является использование инструкции настройки цикла (представленной в ассемблере как LOOP с псевдоинструкцией LOOP_BEGIN и LOOP_END, или в одну строку, как LSETUP), который опционально инициализирует LCx и наборы LTx и LBx до желаемых значений. Для этого требуется всего 4–6 байт, но можно установить только LTx и LBx в пределах ограниченного диапазона относительно того, где находится инструкция настройки контура.
P0 = array + 396;
R0 = 100;
LC0 = R0;
LOOP my_loop LC0; // sets LT0 and LB0
LOOP_BEGIN my_loop; // pseudo-instruction; generates a label used to compute LT0
// LC0 cannot be written directly to memory,
// so we must use a temporary register.
R0 += -1; // equally fast and small would be R0 = LC0
[P0--] = R0;
LOOP_END my_loop; // pseudo-instruction; generates a label used to compute LB0
х86
[ редактировать ]Язык ассемблера x86 REP префиксы реализуют циклы с нулевыми издержками для нескольких инструкций (а именно MOVS/STOS/CMPS/LODS/SCAS). [4] В зависимости от префикса и инструкции, инструкция будет повторяться несколько раз с (E)CX удерживая счетчик повторений, или до тех пор, пока не будет найдено совпадение (или несовпадение) с AL/AX/EAX или с DS:[(E)SI]. Это можно использовать для реализации некоторых типов поиска и операций над строками, завершающимися нулем .
Ссылки
[ редактировать ]- ^ Перейти обратно: а б «Ноль накладных петель» . Проверено 18 августа 2020 г.
- ^ «Понимание расширенных функций процессора способствует эффективному кодированию» (PDF) . Аналоговые устройства . Проверено 18 августа 2020 г.
- ^ «Справочник по программированию процессоров Blackfin, версия 2.2» (PDF) . Аналоговые устройства. Февраль 2013 года . Проверено 18 августа 2020 г.
- ^ «REP/REPE/REPZ/REPNE/REPNZ: Префикс операции повтора строки (Справочник по набору инструкций x86)» . c9x.me . Проверено 18 августа 2020 г.