3.2 Слабая зависимость операций
Слабая
зависимость представляет собой
реализацию цепочки сильных зависимостей.
Оператор Sj
называется слабо зависимым от оператора
Si,
если (Si
Sj):
1. Либо Si → Sj.
2. Либо:
Имеется непустая совокупность операторов Sk1, Sk2, Sk3,…, Skl
(ik1 k2 k3… kl< j), такая что
C(Sp) R(Sg) 0
( p= i, k1, k2, …, kl; g= k1, k2, k3,…, kl, j; p <g), т.е. переменные, полученные в качестве результирующих в операции Sp (изменяемые переменные) могут быть использованы (упомянуты) в операциях Sg до операции Sj и результаты операции Sg используются в операции Sj.
Нет таких операторов (операций) Sr (p< r< g), таких что
C(Sp)C(Sr)0 и C(Sp)C(Sr) R(Sg)
(обозначения для p и g аналогично выше приведенным) – т.е. переменные, изменяемые как в Sp, так и в Sr не могут быть использованы (упомянуты) в операторе Sg; если переменная, измененная в операторе (операции) Si, изменяется в промежуточной операции Sr, то она не может быть используемой в операции Sj. Переменные, изменяемые в Si, используются при вычислении результатов в промежуточном операторе, результаты этого промежуточного оператора не должны изменяться до оператора Sj.
Примеры сильной и слабой зависимостей (изображены на рис.1):
Рисунок 1 – Примеры сильной и слабой зависимостей
3.3 Слабая независимость операций
Операторы
Si
и Sj
слабо независимы (Si
Sj),
если:
a). Либо C(Si)R(Si) = 0;
C(Sj)R(Si) = 0, т.е. изменяемые в операции Si переменные не упоминаются (не используются) в операции Sj. Указанные выражения комментируют отсутствие информационной зависимости оператора Sj от оператора Si , а также отсутствие конкуренции за значение переменных между этими операторами.
б). И нет пустой совокупности операций Sk1, Sk2, Sk3,…, Skl, что имело бы место условие слабой зависимости между операторами.
в).
(Sp)
R
(Sq)
0
(Sp’)
R
(Sq’)
0, где
p = { i, k1, k2, …, kl};
g= {k1, k2, k3, …, kl, j};
p’ = { i, k1, k2, …, kl};
g’= {k1, k2, k3, …, kl, j};
г). Либо имеется операция (оператор) Sk такой, что
C(Si)=C(Sk), (2)
где i<k<j и Sk слабо независим от Si.
Промежуточный оператор переопределяет множество результатов, полученных в операторе Si, поэтому Sj является независимым от Si информационно.
3.4 Сильная независимость операций
Операторы
Si
и Sj
сильно независимы (
),
если либо
а). Если выполняется условие
C(Si) V(Sj) = 0; C(Sj) V(Si) = 0,
Выражения определяют отсутствие конкуренционных зависимостей между операторами Sj и Si.
б). Если есть хотя бы один оператор Sk, i< k< j, что имеет место условие (2) и Sk сильно независим от Si. В противном случае операции Si и Sj сильно зависимы.
в). Не существует такой промежуточной совокупности операторов Sk1, Sk2, Sk3,…, Skl, для которых выполнялось бы условие слабой зависимости:
C(Sp) R(Sg) 0
( p= i, k1, k2, …, kl; g= k1, k2, k3,…, kl, j; p <g),
Таким образом, сильная независимость гарантирует безразличное по отношению к порядку следования выполнение программы. То есть результат выполнения программы Р не зависит от порядка выполнения операторов Si и Sj.
Слабая независимость между операторами допускает наличие конкуренции за значение, тогда для безразличного характера выполнения оператора необходимо, чтобы оператор Si начинался раньше, чем Sj.