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

log
2
n.
Эта параллельная 
форма реализуется на 
n/2
процессорах
, 
и загруженность процессоров 
уменьшается от яруса к ярусу. На рис. 23 для 
n = 8
представлен граф 
последовательного применения операции, внизу ‒
граф для принципа 
сдваивания. Начальные вершины символизируют ввод данных.
Таким образом, если какая
-
нибудь задача определяется 
n
входными 
данными, то в общем случае не существует алгоритма ее решения с высотой 
менее 
log
2
n.
Если получен алгоритм высоты порядка 
log
a 
n 
, где 
а > 0
, то 
такой алгоритм считается эффективным с точки зрения времени его 
реализации на параллельной вычислительной системе при исключении иных
аспектов реализации
. 
Идея абстракции относительно реальной работы параллельных систем, 
допускаемая 
концепцией, 
была 
использована 
в 
математических 
исследованиях и обеспечила появление ряда изобретений в численных 
методах.
Концепция получила развитие в 
1950-
1960 годы. Алгоритмы, 
построенные на основе концепции
, 
оказались несостоятельными, в связи с 
действительной сложностью информационных связей между операциями, 
Рис. 23. Последовательный граф и граф сдваивания
 

---

70 
численной неустойчивостью, наличием большого количества конфликтов в 
памяти. Однако, несмотря на недостатки концепции, предельная степень 
абстракции от реальной ситуации в вычислительных системах позволила 
проводить математические исследования, что привело к появлению 
отдельных изобретений в области численных методов.