Структура ВС типа циркулянта и типа Л(N,v,g)

Циркулянта. Представляется виде dn-графов, которые описываются Dn=G(N, q₁, …, q_n), где N –число вершин графа (вычислителей), которые нумеруются от 0 до N-1, q₁, …, q_n – образующие числа, такие что 0< q₁< q₂<…< q_n< . N, q₁, …, q_n – взаимно простые (наибольший общий делитель равен 1). n – число образующих чисел. Вершина i соединяется ребрами с вершинами (i ± q₁)mod(N), …,(i ±q_n)mod(N). Обычно циркулянта представляется в виде матрицы или хордового кольца.

Л(N,ν,g). N – количество вычислителей. ν – степень вершин. g – обхват графа (самый короткий контур (цикл) в графе).

Алгоритм построения такой структуры довольно сложен. Структура представляется в виде матрицы следования.Структура ВС типа «Л(N,ν,g) – граф» описывается графом GS=(M, S*), где M={m_i}, i=0, …, N-1; S* – симметричная вычислительная сеть, описываемая матрицей смежности. В матрице смежности пишется: номер элемента – номера элементов, с которым он соединяется. (на рисунке Л(8,4,4) и Л(16,4,4))

2. Алгоритм оценки мин. кол-ва процессоров , i=1,…,m необ-го для выполнения заданного алгоритма за время Т.

Функция называется загрузкой отрезка
для С помощью функции Z определяется загрузка отрезка [ a,b ], выполняемыми на этом отрезке операторами. Функция называется минимальной загрузкой отрезка для Смысл этого определения заключается в том, что при любом планировании операторов для выполнения при решении задачи за время Т, загрузка отрезка не может быть меньше вычисленной величины. Для составления алгоритма вычисления данной функции введем функцию . Алгоритм вычисления функции

1.Вычисляются ранние и поздние сроки окончания выполнения операторов.

2.Полагаем .

3.Анализируем последовательность оператора

4.Вычислим

5.После перебора всех операторов получаем значение