Современные высокопроизводительные компьютеры

Рассмотрим следующий цикл:
for (i=1; i<=100; i=i+1) {
A[i+1] = A[i] + C[i]; /* S1 */
B[i+1] = B[i] + A[i+1];} /*S2*/
}
Предположим, что A, B и C представляют собой отдельные, неперекрывающиеся массивы. (На практике иногда массивы могут быть теми же самыми или перекрываться. Поскольку массивы могут передаваться в качестве параметров некоторой процедуре, которая содержит этот цикл, определение того, перекрываются ли массивы или они совпадают, требует изощренного, межпроцедурного анализа программы). Какие зависимости по данным имеют место между операторами этого цикла?
Имеются две различных зависимости:
S1 использует значение, вычисляемое оператором S1 на более ранней итерации, поскольку итерация i вычисляет A[i+1], которое считывается в итерации i+1. То же самое справедливо для оператора S2 для B[i] и B[i+1].
S2 использует значение A[i+1], вычисляемое оператором S1 в той же самой итерации.
Эти две зависимости отличаются друг от друга и имеют различный эффект. Чтобы увидеть, чем они отличаются, предположим, что в каждый момент времени существует только одна из этих зависимостей. Рассмотрим зависимость оператора S1 от более ранней итерации S1. Эта зависимость (loop-carried dependence) означает, что между различными итерациями цикла существует зависимость по данным. Более того, поскольку оператор S1 зависит от самого себя, последовательные итерации оператора S1 должны выполняться упорядочено.
Вторая зависимость (S2 зависит от S1) не передается от итерации к итерации. Таким образом, если бы это была единственная зависимость, несколько итераций цикла могли бы выполняться параллельно, при условии, что каждая пара операторов в итерации поддерживается в заданном порядке.
Имеется третий тип зависимостей по данным, который возникает в циклах, как показано в следующем примере.
Рассмотрим цикл:
for (i=1; i<=100; i=i+1) {
A[i] = A[i] + B[i]; /* S1 */
B[i+1] = C[i] + D[i]; /* S2 */
}
Оператор S1 использует значение, которое присваивается оператором S2 в предыдущей итерации, так что имеет место зависимость между S2 и S1 между итерациями.