Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683

16.4. Эквивалентные преобразования параллельных алгоритмов и 
программ
Эквивалентным 
преобразованием 
будем 
называть 
любое 
преобразование программы в эквивалентную ей программу. 
Программы будем называть эквивалентными по графам зависимостей, 
если: 
- 
пространства итераций программ эквивалентны; 
- 
соответствие эквивалентности является изоморфным для графов; 
- 
сопоставляемые при изоморфизме дуги графов зависимостей 
относятся к входным переменным с одними и теми же номерами.
Графы зависимости эквивалентных программ назовем графами 
эквивалентности 
Программы, графы алгоритмов которых эквивалентны, являются 
различными формами одного и того же алгоритма. Однако эти программы 
могут иметь различный объем памяти для вычислений и отличаться 
способами создания массивов, а также порядком в наборах входных и 
выходных данных

---

173 
Массовый параллелизм в преобразованной программе представлен в 
форме циклов ParDo. Преобразование выполняется над пространством 
итераций и изменяет используемые переменные.
Последовательность преобразования: 
1.
Выполняется эквивалентное преобразование пространства итераций. 
2.
Для новой программы выбираются такие переменные, чтобы при 
преобразовании пространства итераций разные переменные 
переходили в разные, одинаковые — в одинаковые. 
3.
В 
новом 
пространстве 
итераций 
устанавливается 
лексикографический 
порядок, 
при 
котором 
образ 
графа 
зависимостей будет лексикографически правильным. 
Эквивалентное преобразование программы осуществляется с целью 
описания параллелизма в программе при помощи специальных циклов.