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

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

---

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