Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



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

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

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

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

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

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

2.Полагаем .

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

4.Вычислим

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





Дата публикования: 2015-02-18; Прочитано: 222 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с)...