Математическое моделирование на графах. Часть 1. Берцун В.Н. - 42 стр.

UptoLike

Составители:

Рубрика:

42 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1

L = N/2 + N/4 + ··· + 1 = N – 1,

а количество параллельных операций k = log

N соответствует числу

тактов.

Концепция неограниченного параллелелизма [9], возникшая в се-

редине прошлого века, предполагает, что алгоритм, разработанный

для МВС, зависит только от числа процессоров p и имеет необходи-

мую память, одновременно доступную всем процессорам. В рамках

этой идеальной концепции алгоритмы оптимизируются только по

высоте ПФА. Эффективная реализация алгоритмов на МВС зависит

не только от числа процессоров p, которые пронумерованы от 0 до

p – 1, но и строения оперативной памяти. МВС может иметь общую

для всех процессоров память; либо распределенную память, когда

каждый процессор имеет свою локальную память. При создании вы-

числительного алгоритма необходимо учитывать и организацию

связи между процессорами (топологию сети), которая характеризу-

ется диаметром соответствующего связного графа.

Например, на рис. 1.46 представлен граф одного из вариантов

связи между процессорами i = 0,...,15 в виде двумерной решетки

(4 × 4). Для таких процессорных графов внутренний узел i непосред-

ственно связан с узлами i ± 1, i ± 4.

Рис. 1.46

В этом случае обмен информацией между вершиной i и несмеж-

ными вершинами осуществляется как последовательность обменов

между соседними вершинами.