6.2.5. Вопросы к разделу 6.2

1. В чём отличие распределения операторов решаемой задачи для ВС с общим полем памяти от ВС с разделяемой памятью.

2. Постройте матрицу дистанций для обобщённого четырёхмерного куба.

3. Как строятся нити на базе диаграмм ранних сроков окончания выполнения операторов?

4. Стратегии планирования использования ВМ при планировании логических операторов.

5. Как учитывается время обмена информацией при планировании вычислений для ВС с распределённой памятью?

6. Способ построения матрицы следования для для граф-схемы алгоритма решаемой задачи на ВС с распределённой памятью при использовании ВМ с одновременной передачей информации.

7. При загрузке нитей в ВС чему следует отдать предпочтение: увеличению числа процессоров в системе или увеличению степени вершин коммуникационной среды?

8. Изобразите диаграмму трансляционно-циклического обмена для пяти ВМ.

Глава 7. Исследование информационных граф-схем решаемых задач с векторными весами для планирования параллельных вычислений

7.1 Информационная граф-схема решаемых задач с векторными весами вершин

7.1.1 Понятие об неоднородных системах

В вычислительной практике наряду с однородными системами получают всё большее распространение неоднородные вычислительные системы (НВС). В неоднородные ВС входят разнотипные вычислительные модули, объединённые с помощью коммутационных сред, обеспечивающих обмен данными меду ними. Программные модули, которые предполагается решать на разнотипных ВМ, имеют, как правило, различные времена решения. В связи с этим, у каждой вершины граф-схемы решаемой задачи появляется вектор времени решения рассматриваемой задачи. Размер вектора времени решения определяется количеством типов ВМ. Пусть, например, НВС имеет три типа ВМ, тогда задача, которую предполагается решать на рассматриваемой неоднородной вычислительной системе можно представить в виде граф-схемы, как показано на рисунке 7.1.1.

(2,8,4)

(1,5, )

(7,4, )

(4, , ) (2,6, )

Рисунок 7.1.1. Граф-схема задачи, которая будет решаться на неоднородной вычислительной системе.

Как правило, веса составляющих вектора j-й вершины (p_j,1, p_j,2, …, p_j,n) упорядочиваются следующим образом: составляющая вектора p_j,1 определяет время решения программного модуля на первом типе ВМ, p_j,2 – на втором и т.д. Символ « » обозначает, что рассматриваемый модуль на данном типе процессора не может выполняться. Так, на рисунке 7.1.1 оператор 2 не может быть выполнен на третьем типе процессора. Для исследования граф-схем, предназначенных для решения на НВС, упорядочим составляющие векторов веса в порядке неубывания, не теряя при этом информацию о принадлежности составляющей к типу ВМ, исключив при этом символ «  », уменьшив при этом размерность соответствующего вектора. Преобразуем граф-схему с векторными весами в граф-схему со скалярными весами, используя следующее правило: каждая j-я вершина с векторным весом образует n вершин, где n размерность вектора . Преобразованная граф-схема показана на рисунке 7.1.2.

Выделяя вершины с одинаковыми типами ВМ, получим граф-схемы частей задачи, решаемых на соответствующих типах ВМ. Эти граф-схемы будем обозначать как G=(X, P, I, Г), где i I – тип ВМ, за которым закреплён оператор j X и называть G - выборкой граф-схемы G. При анализе векторных граф-схем, с помощью методов, применяемых для скалярных граф-схем, сложность решения задачи возрастает в

Q = ,

где q_j – размерность j-ого вектора, n – количество векторов в рассматриваемой граф-схеме. Для рассматриваемой граф-схемы рисунка 7.1.2 количество G-выборок составит G=3*2*2*1*2=24. В G-выборках каждый оператор закреплён за определённым процессором.

2(1) 4(3) 8(2)

1(1) 5(2) 4(2) 7(1)

4(1) 2(1) 6(2)

Рисунок 7.1.2. Преобразованная граф-схема задачи с векторными весами в граф-схему со скалярными весами вершин

Для уменьшения сложности решения задач, представленных векторными граф-схемами, путём сведения их решения к Q задач со скалярными весами небезинтересной является теорема об уменьшении количества скалярных граф-схем для данной векторной граф-схемы.

Теорема 7.1.1

Если

1. {N_i}, i=1, …, k, – набор ВМ вычислительной системы,

2. оператор z входит только в одно полное множество ВНО с числом операторов r,

3. компоненты веса вершины оператора z упорядочены по не убыванию так, что p_z1 p_z2 p_z,s , p_z,s+1= … = p_z,k= при s < k, где s – количество процессоров способных выполнить данную операцию.

4. существует положительное w < s такое, что при w = 1, 0 r N_i ,

а при w > r, ,

то при исследовании и выполнении планов данного последовательного алгоритма можно положить p_z,w+1=…=p_z,w+s= , что приводит к исключении процессоров соответствующих типов, начиная с номера w+1, из рассмотрения при поиске вариантов назначения оператора z.

Доказательство. Очевидно, что если исключить оператор z, входящий в одно полное множество ВНО, оставив неизменными моменты окончания других операторов, входящих в это множество, оператор z не выполнять, то общее время решения задачи не увеличится. Если время решения задачи оператора z на одном из r процессоров не больше, чем на каждом из

вычислительных модулей, то размещение оператора z на одном из ВМ заставит простаивать ВМ из множества z. Теорема доказана.Таким образом, при определённых условиях, имеется возможность исключить некоторые типы процессоров, что, как правило, приводит к сокращению времени решения задачи.

Рассмотрим пример.

(1,3,2)

(3, ,1)

(6,5, )

(5,5,1)

( ,2,3) (1,2,2)

Рисунок 7.1.3. Граф-схема задачи с векторными весами

В данном примере рассматривается ВС с тремя типами процессоров по одному процессору каждого типа. Образуется три множества ВНО : ВНО₁ = {1}, ВНО₂ = {(2), 3}, ВНО₃ = {(4), 5}. Для ВНО₁: r=1, N₁=1 и неравенство пункта 4 теоремы выполняется, тогда в операторе 1 целесообразно взять веса (1, , ). Для ВНО₂: не выполняется условие (3) теоремы – соответствующие веса не упорядочены. Для ВНО₃: : r=2, N₁=1, w=2. неравенство пункта 4 запишется в виде: 1 2 2. Для четвёртой вершины целесообразно выбрать веса – (1, 1, ). Общее число выборок для граф-схемы, представленной на рисунке 7.1.3 до применения теоремы 7.1.1 равно R=3*2*2*3**3*2=216, после применения теоремы – R =1*2*2*2*3*2=48. Если к каждой выборке применять рассмотренные выше методы исследования для однородных ВС, то трудоёмкость определения параметров неоднородных ВС после применения теоремы 7.1.1 сокращается почти в пять раз. В отдельных случаях для анализа неоднородных ВС применяются младшие G-выборки графа G*, поэтому могут оказаться полезными следующие определения.