Нормализованный цикл

В информатике ( нормализованный цикл иногда называемый циклом с хорошим поведением) — это цикл, в котором переменная цикла начинается с 0 (или любой константы) и увеличивается на единицу на каждой итерации, пока не будет выполнено условие выхода. Нормализованные циклы очень важны для теории компиляторов и анализа зависимостей циклов , поскольку они упрощают анализ зависимости данных . ^{[ нужна ссылка ]}^{[ 1 ]}

Хорошо управляемые циклы

Хорошо управляемый цикл обычно имеет вид:

for ( i = 0; i < MAX; i++ )
  a[i] = b[i] + 5;

Поскольку приращение является унитарным и постоянным, очень легко увидеть, что если и a, и b больше MAX, этот цикл никогда не получит доступ к памяти за пределами выделенного диапазона.

Ненормализованные циклы

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

Простой пример, где он не начинается с начала и увеличивается более чем на единицу:

// Example 1
for ( i = 7; i < MAX; i+=3 )
  a[i] = b[i] + 5;

Более сложный пример с дополнительным условием выхода:

// Example 2
for ( i = 7; i < MAX || i > MIN; i+=3 )
  a[i] = b[i] + 5;

Циклы также могут вести себя непредсказуемо во время компиляции, когда условие выхода зависит от содержимого изменяемых данных:

// Example 3
for ( i = 7; i < MAX && a[i]; i+=3 )
  a[i] = b[i] + 5;

Или даже динамические вычисления посредством вызовов функций:

// Example 4
for ( i = start(); i < max(); i+=increment() )
  a[i] = b[i] + 5;

Обратные циклы также очень просты и могут быть легко нормализованы:

// Example 5
for ( i = MAX; i > 0; i-- )
  a[i] = b[i] + 5;

Преобразование в нормализованный цикл

Если ненормализованный объект не имеет динамического поведения, его обычно очень легко преобразовать в нормализованный. Например, первый пример (Пример 1) выше можно легко преобразовать в:

// Example 1 -> normalized
for ( i = 0; i < (MAX-7)/3; i++ )
  a[i*3+7] = b[i*3+7] + 5;

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

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

Обратный цикл (Пример 5) также легко нормализовать:

// Example 5 -> normalized
for ( i = 0; i < MAX; i++ )
  a[MAX-i] = b[MAX-i] + 5;

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

Невозможные преобразования

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

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

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

См. также

Ссылки

^ «Нормированные петли гистерезиса» .

[1] «Нормированные петли гистерезиса» .

[ 1 ]