glava2 (Лобусов Е.С. Теоретические основы параллельных вычислений), страница 4

Вид представления (4) очень хорошо подходит к описанию системы блок-диаграммой. Допустим имеем блок-диаграмму гидравлического сервопривода (рис.2.12).

Соответствующая система ОАДУ, где x = [x₁, x₂, ..., x₅]^T - вектор состояния, v = [v₁, v₂, ..., v₁₃]^T - вектор промежуточных переменных, f() - скалярная функция от переменных. Уравнения гидропривода с линейной

нагрузкой

Рис.2.12 Блок-диаграмма гидропривода с линейной нагрузкой.

Посредством последовательных подстановок для промежуточных переменных получается система только ОДУ

, (5)

где - управляющее воздействие, являющееся некоторой функцией времени. Отметим, что при таком приведении просматривается некоторая функциональная избыточность правых частей (вводятся дополнительно уравнения для промежуточных переменных обведенные пунктиром), но это является платой за получаемую однородность описания.

Воспользуемся для получения численного решения (5) простейшим методом интегрирования - методом Эйлера. Тогда

, i =1,2, … ,п (6)

где h - шаг интегрирования.

Записанное разностное уравнение (6) уже допускает графовую интерпретацию (рис.2.13) для каждого k-го шага интегрирования . После получения k+1-го значения переменной состояния на новом k+1 шаге осуществляется присвоение k-му значению вычисленного k+1 значения переменной состояния.

Таким образом, граф интегрирования ОДУ является фактически одноярусным с шириной равной порядку n ОДУ. Отсюда число процессоров для реализации процесса интегрирования не более n.

В тех случаях, когда не выполняется последовательное устранение промежуточных переменных, граф интегрирования ОДУ становится существенно сложнее. Так на рис.2.14 приведен граф интегрирования ОДУ типа (4) методом Эйлера для примера на рис.2.12. Ширина графа теперь может превысить порядок n. Однако появившиеся вершины чаще всего соответствуют несложным функциональным зависимостям и поэтому для них практически не выполняется условие (3). Именно по этой причине целесообразно проводить интегрирование ОДУ в приведенном виде (6). На рис.2.15 показана приведенная форма для графа рис.2.14,детализирующая граф на рис.2.13.

Не представляет трудностей получение графовых интерпретаций для других методов интегрирования.

2.3. Представление вычислительных сетей.

Под вычислительной сетью (ВС) понимается набор взаимодействующих между собой процессоров; при этом каждый из процессоров обладает своей собственной памятью, а взаимодействие осуществляется посредством двунаправленных каналов.

Отсюда такую ВС легко представить в виде взвешенного (размеченного) ориентированного графа, вершины которого соответствуют процессорам ВС, а дуги ориентированным каналам передачи информации; разметка вершин соответствует производительности процессоров (кол.опер./сек), а разметка дуг – скорости передачи информации (бит/сек).

Тем самым для ВС имеем граф

G_C = <P, V >,

г де P - множество вершин (процессоров), представляемое либо в виде вектора, компоненты которого производительности процессоров , либо в виде диагональной матрицы производительности ; j=1,m; m - число процессоров; p_j - производительность j-ого процессора; V - отношение на множестве P, задаваемое в виде взвешенной квадратной матрицы смежности , j, k = 1, m, элементы которой равны 0, если j-ая и k-ая вершины не связаны непосредственно, и весу v_jk - скорости передачи информации при наличии связи.

На рис.2.16 приведена элементарная модель двух взаимодействующих процессоров, а на рис.2.17 - несколько вариантов вычислительных сетей в виде графовых моделей. На этих графах стрелки на связях между вершинами не показаны.

Все эти графы являются сильно связанными. Считая все процессоры одинаковыми с производительностью p₀, а также одинаковыми скорости передачи данных v₀, имеем следующие матричные представления для графов G_C на рис.2.17 (если параметры процессоров и каналов различны, то тогда в качестве p₀ и v₀ берутся их максимальные значения и элементы матриц P и V становятся меньше 1):

V	V	V
P	P	P

Но в реальной ситуации важной переменной является время передачи единицы информации ( а не скорость передачи) и временная длина (стоимость) кратчайшего пути между произвольными процессорами (вершинами). С тем, чтобы найти минимальное время (стоимость) передачи единицы информации между произвольными процессорами (вершинами) следует ввести вместо матрицы V другую матрицу

(7)

t_ij - время передачи единицы информации между i и j процессорами. После этого для графа G_C = <P, T > с матрицей смежности T ищется наикратчайший путь между произвольными процессами и его составляющими. Результатом является матрица кратчайших путей

2.3.1. Представление процессоров с совмещением вычислений и ввода-вывода.

Р
ассмотренная выше модель процессора в ВС относится к самой простейшей, так как в ней процессор может выполнять в каждый момент времени только одну функцию: либо вычислений, либо обмена (ввода-вывода). Именно на этой простейшей модели и разрабатываются различные методы отображения.

В то же самое время в большинстве процессоров функции вычислений и обмена могут выполняться одновременно, то есть совмещаться во времени. Чтобы учесть такой эффект в модели между основным процессором и физическим каналом ввода-вывода помещается дополнительный процессор. Этот дополнительный процессор Ф обладает нулевой производительностью и соединяется с основным процессором Ц фиктивным каналом с неограниченной скоростью передачи данных (или нулевым временем передачи данных). На рис.2.18 как примеры приведены различные модели такого процессора с совмещением операций: а) процессор с совмещением и с одним внешним каналом; б) процессор с совмещением и с 2-мя последовательно работающими внешними каналами; в) процессор с совмещением и с 2-мя параллельно работающими каналами. Для сравнения на том же рисунке приведены модели процессора без совмещения: г) с одним внешним каналом; д)с 2-мя последовательно работающими внешними каналами. Как видно, в таких структурах без совмещения через центральный процессор проходят как вычисления, так и обмены.

Подобным образом можно составить модель процессора с другим числом внешних каналов с последовательным или параллельным режимом работы.

Имеется ещё один тип процессора, в котором наряду с совмещением операций и ввода-вывода, осуществляется квазипараллельный режим вычислений. Естественно, что этот квазипараллельный режим поддерживается и соответствующими программными средствами, в частности, языком параллельного программирования OCCAM. Графовая модель данного процессора с совмещением и квазипараллельной обработкой ничем не отличается от уже рассмотренной и приведённой на рис.2.18 а, б, в. Но тот или иной вид модели процессора с учётом основного принципа вычислений непосредственно определяет способ реализации алгоритма обработки!

28