Характеристики топологии сети
В качестве основных характеристик топологии сети передачи данных наиболее широко используется следующий ряд показателей:
• Диаметр – показатель, определяемый как максимальное расстояние между двумя процессорами (под расстоянием обычно понимается величина кратчайшего пути между процессорами); данная величина может характеризовать максимально-необходимое время для передачи данных между процессорами, поскольку время передачи обычно прямо пропорционально длине пути;
• Связность (connectivity) – показатель, характеризующий наличие разных маршрутов передачи данных между процессорами сети; конкретный вид данного показателя может быть определен, например, как минимальное количество дуг, которое надо удалить для разделения сети передачи данных на две несвязные области;
• Ширина бинарного деления (bisection width) – показатель, определяемый как минимальное количество дуг, которое надо удалить для разделения сети передачи данных на две несвязные области одинакового размера;
• Стоимость – показатель, который может быть определен, например, как общее количество линий передачи данных в многопроцессорной вычислительной системе.
Алгоритмы маршрутизации
Очевидно, что временные задержки при передаче данных по каналам связи при взаимодействии процессов влияют на эффективность параллельных вычислений. Алгоритмы маршрутизации определяют путь передачи данных от процессора-источника до процессора получателя сообщения. Алгоритмы маршрутизации должны определять оптимальный, т.е. кратчайший путь передачи данных с использованием детерминированных и адаптивных методов выбора маршрутов (адаптивные алгоритмы определяют пути передачи данных в зависимости от существующей загрузки коммуникационных каналов).
К числу наиболее распространенных оптимальных алгоритмов относится класс методов покоординатной маршрутизации (dimension-ordered routing), в которых поиск путей передачи данных осуществляется поочередно для каждой размерности топологии сети коммуникации. Например, для двумерной решетки такой подход приводит к маршрутизации, при которой передача данных сначала выполняется по одному направлению (например, по горизонтали до достижения вертикали процессоров, в которой располагается процессор назначения), а затем данные передаются вдоль другого направления (данная схема известна под названием алгоритма XY-маршрутизации).
Для гиперкуба покоординатная схема маршрутизации может состоять, например, в циклической передаче данных процессору, определяемому первой различающейся битовой позицией в номерах процессоров, на котором сообщение располагается в данный момент времени, и на который сообщение должно быть передано.
Время передачи данных между процессорами определяет длительность выполнения параллельного алгоритма в многопроцессорной вычислительной системе. Время передачи данных включает:
− время начальной подготовки (tн) характеризует длительность подготовки сообщения для передачи, поиска маршрута в сети и т.п.;
− время передачи служебных данных (tс) между двумя соседними процессорами (между которыми имеется физический канал передачи данных); к служебным данным может относиться заголовок сообщения, блок данных для обнаружения ошибок передачи и т.п.;
− время передачи одного слова данных по одному каналу передачи данных (tк); длительность подобной передачи определяется пропускной способностью сети.
Рассмотрим два наиболее распространенных метода передачи данных.
Первый – выполняет передачу сообщений как неделимых (атомарных) блоков информации (store-and-forward routing or SFR). В этом случае процессор-отправитель готовит весь объем данных для передачи, определяет процессор, которому следует направить данные, и запускает операцию передачи данных. Процессор-получатель сообщения, осуществляет прием данных, затем, при необходимости приступает к передаче принятого сообщения далее по маршруту. Время передачи данных tпд для сообщения размером m байт по маршруту длиной l определяется выражением
При достаточно длинных сообщениях временем передачи служебных данных можно пренебречь и выражение может быть записано в более простом виде
Второй способ - выполняет передачу сообщений в виде блоков информации, в результате чего передача данных может быть сведена к передаче пакетов. В этом случае принимающий процессор может осуществлять пересылку данных по дальнейшему маршруту непосредственно сразу после приема очередного пакета, не дожидаясь завершения приема данных всего сообщения. Время пересылки данных при использовании метода передачи пакетов будет определяться выражением
В большинстве случаев метод передачи пакетов приводит к более быстрой пересылке данных; кроме того, данный подход снижает потребность в памяти для хранения пересылаемых данных для организации приема-передачи сообщений, а для передачи пакетов могут использоваться одновременно разные коммуникационные каналы. С другой стороны, реализация пакетного метода требует разработки более сложного аппаратного и программного обеспечения сети, может увечить накладные расходы (время подготовки и время передачи служебных данных).
3. Классификация многопроцессорных вычислительных систем. Понятие пропускной способности и латентности, методы их измерения.
Одним из наиболее распространенных классификаторов многопроцессорных ВС является система Флинна (Flynn), в основу которой положен способ взаимодействия последовательностей (потоков) выполняемых команд и обрабатываемых данных. В результате такого подхода различают следующие основные типы систем:
1. SISD (Single Instruction, Single Data) – системы с одиночным потоком команд и одиночным потоком данных; к данному типу систем можно отнести обычные последовательные ЭВМ;
2. SIMD (Single Instruction, Multiple Data) – системы с одиночным потоком команд и множественным потоком данных; это многопроцессорные вычислительные системы, в которых в каждый момент времени может выполняться одна и та же команда для обработки нескольких информационных элементов; подобной архитектурой обладают, например, многопроцессорные системы с единым устройством управления;
3. MISD (Multiple Instruction, Single Data) – системы с множественным потоком команд и одиночным потоком данных. Относительно данного типа систем нет единого мнения – ряд специалистов говорят, что примеров конкретных ЭВМ, соответствующих данному типу вычислительных систем, не существует, и введение подобного класса предпринимается для полноты системы классификации; другие же относят к данному типу, например, системы с конвейерной обработкой данных;
4. MIMD (Multiple Instruction, Multiple Data) – системы с множественным потоком команд и множественным потоком данных; к подобному классу систем относится большинство параллельных многопроцессорных вычислительных систем.
Хотя система Флинна широко используется при конкретизации типов компьютерных систем, такая классификация приводит к тому, что практически все виды параллельных систем (несмотря на их существенную разнородность) относятся к одной группе MIMD. Неоднократные предпринимались попытки детализации системы Флинна. Так, например, для класса MIMD была предложена структурная схема, в которой дальнейшее разделение типов многопроцессорных систем основывается на способах организации памяти: системы на общей и распределенной памяти.
Существующие параллельные ВС класса MIMD образуют два технических подкласса: симметричные мультипроцессоры (SMP) и системы с массовым параллелизмом (МРР).
1. Симметричные мультипроцессоры используют принцип разделяемой(общей) памяти. В этом случае система состоит из нескольких однородных процессоров и массива общей памяти. Все процессоры имеют доступ к любой ячейке памяти с одинаковой скоростью. Аппаратно поддерживается когерентность (согласованность) кэш памяти.
Наличие общей памяти сильно упрощает взаимодействие процессоров между собой, однако накладывает сильные ограничения на их число. Вся система работает под управлением единой ОС.
2. Системы с массовым параллелизмом (массивно-параллельные системы massively parallel processor или MPP), примером которых являются кластерные вычислительные системы − это совокупность вычислительных узлов, объединенных в рамках некоторой сети для решения одной задачи. В настоящее время, в качестве вычислительных узлов используются многоядерные процессорные элементы (SMP узлы). Каждый узел работает под управлением своей копии операционной системы, в качестве которой чаще всего используются юниксоподобные ОС (Linux, AIX и т.п) или OC WINDOWS. Состав и мощность узлов может меняться даже в рамках одного кластера, давая возможность создавать неоднородные (гетерогенные) вычислительные системы.
Для кластерных систем принципиальное значение имеют топология и архитектура коммуникационных сетей и соответствующие характеристики - латентность и пропускная способность.