Структура ВС типа обобщенный трехмерный гипертор описывается следующими соотношениями:

по каждой координате k=1, 2, 3 откладываются точки (вершины) с номерами 0,1,…,Nk-1, где Nk - размерность тора по координате k;

множество вершин графа коммутационной структуры задается декартовым произведением [0,1,…,N₁ -1] x [0,1,…,N₂ -1] x [0,1,…,N₃ -1];

две вершины соединяются ребром, если их декартовы произведения отличаются друг от друга на единицу по любой координате или на N₁ -1 по координате 1 или на N₂ -1 по координате 2 или на N₃ -1 по координате 3 соответственно.

Рис.1 - Схема представления обобщенного трехмерного тора 3x2x2

Данная структура ВС имеет ряд преимуществ перед другими структурами ВС такими, как циркулянта, n-мерный двоичный гиперкуб, обобщенный трехмерный гиперкуб, бинарное дерево. Обобщенный гипертор является симметричной структурой с множеством дополнительных связей, что значительно облегчает процесс распределения вершин информационного графа по процессорам заданной структуры вычислительной сети.

4. Описание алгоритма решения задачи

4.1 Основные определения

Вершина - оператор ИЛГ заданной задачи.

Вес вершины ( pV ) - время расчета вершины на i-ом процессоре.

Время старта вершины ( Vs ) - время старта расчета вершины в существующем разбиении вершин между процессорами.

Время финиша вершины ( Vf ) - время финиша расчета вершины в существующем разбиении вершин между процессорами.

Начальная и конечная вершины добавляются к информационному графу. Начальная вершина имеет номер 0 и необходима для того, чтобы граф имел одну точку входа. Конечная вершина имеет номер N+1, где N - размерность матрицы следования исходного информационного графа, и необходима, чтобы граф имел одну точку выхода. Веса этих вершин равны нулю. Веса дуг, выходящих из нулевой вершины равны единице. После этого добавления исходная матрица следования S преобразуется, будет иметь размер N+2 и обозначаться C.

Высота вершины ( h ) - максимальное время от начала выполнения вершины до конца выполнения алгоритма, заданного матрицей следования С.

По определению высота конечной вершины равна нулю.

Родители вершины - все предшествующие данной вершине вершины, от которых она зависит по данным.

Нить - набор из одной или нескольких вершин, которые последовательно рассчитываются на одном процессоре.

микропроцессорная сеть алгоритм планировщик

Родительские нити вершины - набор нитей, каждая из которых содержат одного или нескольких родителей данной вершины

Время готовности вершины ( r ) - максимум из времен финиша всех родителей вершины.

Время старта нити ( sT ) - время старта нити в существующем разбиении нитей между процессорами.

Время финиша нити ( fT ) - время финиша нити в существующем разбиении нитей между процессорами.

Номер процессора нити ( nfp ) - номер процессора, на котором рассчитывается нить в существующем разбиении.

4.2 Алгоритм построения нитей в сети G

Алгоритм построения нитей в графе G, представляющим решаемую задачу.

1. В графе G выделим множество начальных вершин В матрице S, построенной для графа G начальным вершинам соответствуют нулевые строки. Вычислим i: =1 - параметр определяющий текущий номер элемента в множестве , V - номер массива перебора операторов.

K: =1 - номер очередной создаваемой нити, -множество связей нитей с другими нитями, f: =0 - номер очередного разрезания графа G, - множество продолжения нитей.

2. Возьмем вершину .

3. Вычислим обобщенный вес вершины как если вес вершины не модифицировался или в противном случае.

4. Если из вершины не выходит связь, то переходим к шагу 9, иначе выполняется следующий шаг.