1.2 Структура вс типа «Обобщенный nD-куб»
Реализация обмена с помощью структуры типа «Обобщенный nD- куб» представлена на рисунке 1.
Рисунок 1 - Схема представления обобщенного 3-х мерного гиперкуба 2х4х3
Рисунок 2 - Схема представления обобщенного 3-х мерного гиперкуба 3х3х6
Структура вычислительной системы типа
«Обобщенный nD-куб» описывается графом
GS =(М, S*), где М – множество вычислительных
модулей, определяемых вершинами графа,
М ={mi}, i = 0, … , N-1,
.
По каждой координате j, j=1,…,n вводятся
точки Nj={0,1, ... , Nj-1}, где Nj
– размерность куба по координате j.
Множество вершин графа ВС определяется
декартовыми произведениями [N1]
[N2]
…
[Nn],
|N1|·|N2|·…·|Nn|=N. Две вершины соединяются
ребром, если декартовы произведения,
определяющие эти вершины, отличаются
друг от друга на 1.
Основные определения, необходимые для разработки алгоритма распределения программных модулей по вычислительным модулям вычислительной сети
Вершина – оператор ИЛГ заданной задачи.
Вес вершины (P) – время расчета вершины на i-ом процессоре.
Степень вершины (Vi) – количество узлов, находящиеся от i-ой вершины на минимальном расстоянии.
Коэффициент передачи (pA) – время передачи между узлами ВС.
Комплексный узел – транзитный узел ВС.
Время старта вершины (sT) – время старта расчета вершины в существующем разбиении вершин между процессорами.
Время финиша вершины (fT) – время финиша расчета вершины в существующем разбиении вершин между процессорами.
Нить – набор из одной или нескольких вершин, которые последовательно рассчитываются на одном процессоре.
Множество нитей (Т) – совокупность всех нитей заданного ИЛГ.
Пучок нитей ({Pz}) – множество связанных между собой нитей.
Таблица связей к-ой нити (TSk) – совокупность нитей, связанных с k-ой нитью (имеет Sk элементов).
Массив связей (MS) – упорядоченное множество связей всех нитей одного пучка.
Распределение операторов по вм вычислительной системы с распределенной памятью для информационно-логической граф-схемы
При построении плана распределения операторов по ВМ вычислительной системы с распределённой памятью для информационной граф-схемы возникают определённые трудности, связанные с передачей информации через транзитные ВМ. Сущность метода заключается в том, что на первом этапе создаются нити без учёта обмена информацией между ВМ. Затем при построении нитей в моменты обмена данными длины нитей корректируются на время обмена информацией в данной точке. Вначале получаем модифицированные веса вершин в виде pm,j=pj+qj,i ,где pj – вес j-й вершины, qj,i – вес дуги, исходящей из j-й вершины. При использовании транзитных ВМ модифицированный вес возрастает на qj,i(n-1), где n – количество используемых транзитных процессоров.
Структура ВС с общей памятью. Применяется в многопроцессорных системах и не используется в многомашинных системах
Коммуникационная сеть вырождается в общую шину. Дополнительно к преимуществу структуры общей шины данная структура обладает тем достоинством, что обмен информацией между процессорами не требует дополнительных операций, а осуществляется благодаря доступу процессора к памяти.
Системы с общей оперативной памятью образуют современный класс ВС — многопроцессорных супер-ЭВМ. Одинаковый доступ всех процессоров к программам и данным представляет широкие возможности организации параллельного вычислительного процесса (параллельных вычислений). Отсутствуют потери реальной производительности на межпроцессорный (между задачами, процессами и т.д.) обмен данными (рис.3)
Рисунок 3 – Вычислительная система с общей памятью
Рисунок 4 – Граф-схема параллельного алгоритма