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

детерминированным
, иначе - 
недетерминированным
. 
Каждой вершине графа детерминированного алгоритма однозначно 

---

67 
соответствует операция реализующей этот алгоритм программы. Для 
недетерминированного алгоритма такое соответствие построить нельзя. 
Введенный в рассмотрение граф алгоритма есть ориентированный 
ациклический мультиграф, что для любых программ означает выполнение 
только явных вычислений и невозможность определения величины через 
саму себя. В общем случае граф алгоритма есть мультиграф, т. е. две 
вершины могут быть связаны несколькими дугами. Это будет тогда, когда в 
качестве разных аргументов одной и той же операции используется одна и та 
же величина. Обозначим граф, как 
С= (V, Е),
где 
V
- множество вершин, 
Е
- 
множество дуг графа 
С
. 
На основе графа алгоритма можно построит по определенным 
правилам строгую параллельную форму графа. Совокупность вершин с 
одинаковыми индексами определяется, как ярус параллельной формы. 
Ширина яруса - число вершин в группе. Высота параллельной формы 
определяется числом ярусов параллельной формы, а ширину составляет 
максимальная ширина ярусов. Максимальной называется параллельная 
форма минимальной высоты.
Между различными реализациями одного и того же алгоритма на 
различных компьютерах и различными параллельными формами графа 
алгоритма существует взаимное соответствие. По результатам исследования 
графа алгоритма и его параллельных форм, можно оценить запас 
параллелизма в алгоритме и выбрать его лучшую реализацию на конкретном 
компьютере параллельной архитектуры.
6.3. Концепция неограниченного параллелизма 
Необходимость реализации решения задач на параллельных 
вычислительных системах способствовала развитию математической 
концепции 
построения 
параллельных 
алгоритмов 
‒ 
концепции 
неограниченного параллелизма. Концепция основана на предположении о 
том, что реализация алгоритма на параллельной вычислительной системе, не 

---

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