Каналы связи и особенности передачи сообщений

РАСПРЕДЕЛЕННЫЕ ВЫЧИСЛЕНИЯ ЛЕКЦИЯ 10 КАНАЛЫ СВЯЗИ И ОСОБЕННОСТИ ПЕРЕДАЧИ СООБЩЕНИЙ Временные особенности передачи данных в каналах связи Передача данных от узла источника к узлу приёмнику в распределённой системе по каналам связи представляет собой комплексную процедуру. Приведем некоторые необходимые основные действия, которые выполняются в ходе этой процедуры: 1. Подготовка узла источника к посылке данных; 2. Подготовка узла приёмника к приёму данных; 3. Копирование данных из памяти процесса отправителя в системный буфер; 4. Передача данных из системного буфера в память адаптера канала и формирования в адаптере узла источника кадров сетевого протокола; 5. Собственно передача по каналу; 6. Расшифровка (с коррекцией ошибок) кадров протокола в адаптере узла приёмника и передача данных из памяти адаптера в системный буфер; 7. Копирование данных из системного буфера в память процесса получателя. Для того, чтобы получить представление о том, как можно приблизительно посчитать (прикинуть) временные затраты на передачу некоторого количества информации (M-байт), можно воспользоваться формулой: T=f(M,ρ)=Tl+M/ρ. (1) – где: ρ – пропускная способность канала, а Tl – время латентности. Время латентности – это время между началом процедуры передачи данных (точнее – начала действий узла источника по посылке данных) и тем, когда первый байт передаваемых данных окажется в точке назначения, то есть в памяти процесса получателя в узле приёмнике. Времена латентности определяются теоритически или экспериментально для каждого канала конкретной системы. Времена латентности могут быть неизменны, а могут меняться со временем, в зависимости от состояния системы и состояния канала связи. 1 Чтобы подсчитать время передачи M-байт данных, надо также знать пропускную способность канала ρ. Каналы передачи могут быть организованны поразному. На рис. 1 показаны четыре обобщённых случая организации канала с точки зрения их пропускной способности. 1 2 3 Короткая широкая связь (ρ→max) Node T=((Tl →milim) +(M/ρ)→min)) →min Node Короткая узкая связь (ρ→min) Node Node T=((Tl →lim) +(M/ρ)→max)) →max Длинная в среднем узкая связь (ρсред→min) ρ4 ρ2 ρ1 ρ5 ρ3 Node Node T=((Tl →max) +(M/ρсред)→max)) →max Длинная выделенная широкая связь (ρ→max) 4 Node Node при M→min; T=((Tl →malim) +(M/ρ)→0)) →malim при M→max; T=((Tl →lim) +(M/ρ)→min)) →min Рис. 1. Четыре организации канала с точки зрения пропускной способности Понятия узкая и широкая связь оценочно характеризуют высокую или низкую пропускную способность канала. Каналами с короткой связью можно назвать каналы, в которых связь организованна прямой линией между узлом источником и узлом приёмником. Каналами с длинной связью можно назвать каналы, в которых внутри связи имеются какие-то устройства посредники, разбивающие связь на стадии. В этом случае говорят о некоторой средней пропускной способности канала, как обобщающей характеристике совокупности пропускных способностей отдельных промежуточных линий усреднённых по времени (поскольку в таких системах чаще всего линии разделяются разными каналами, поэтому их загружен2 ность, то есть реальная пропускная способность, в разное время может быть разная). Однако, даже в длинном канале в ряде случаев может быть организована стабильно широкая связь (случай 4). Чтобы оценить вклад того или иного параметра во время передачи (в схемах на рис. 1), используем следующие оценочные обозначения: →min – влияние показателя уменьшается; →max – влияние показателя уменьшается; →lim (milim, malim) – влияние показателя ограничено неким пределом; →0 – влиянием показателя можно пренебречь; Топологии соединения узлов Можно выделить три основных типа топологий соединений вычислительных узлов: 1. Шинные соединения; 2. Прямые соединения; 3. Коммутируемые соединения. Другие топологии представляют собой комбинации эти типов. На рис. 2 показаны варианты шинных соединений. N N N N N N N N N N б) множественная общая N Фильтр сообщ. а) одиночная общая N N N N N в) множественная разделённая Рис. 2. Шинные соединения Связи в шинные соединениях организуются путём того, что все данные, выставляемые узлом источником на общую шину «видны» всем остальным узлам, которые считывают только то, что они должны принять. Это обстоятельство дела3 ет шинную организацию довольно простой и привлекательной. Поэтому она до недавнего времени широко применялась в многопроцессорных системах фирмы Intel и до сих пор применяется для связи процессоров с периферией внутри узлов. С другой стороны, общая шина а) является узким местом. Чем больше узлов подключено к шине, тем больше она загружается передачами, и в итоге реальная пропускная способность канала между любыми двумя узлами уменьшается. Чтобы организовать шинное соединение с большим числом узлов применяется множественная общая б), или множественная разделённая в) шины. В последнем случае шинное соединение разделяется на отдельные шины специальными фильтрами, которые из одной шины не пропускают сообщения в шину, узлам которой они не предназначены. На рис. 3. показаны варианты топологий с прямыми соединениями. В этом случае связи между смежными узлами организованы напрямую. При организации канала между несмежными узлами, промежуточные узлы являются посредниками при передаче. N N N N а) линейка N N N N N N N N N N N N N в) решетка б) кольцо N N N N N N N е) дерево N N N N N ж) полный граф N N N N N N N N г) 2D-тор д) гиперкуб N N N N N Коммутатор каналов N N N N з) с настраиваемыми каналами Рис. 3. Прямые соединения Особый случай представлен вариантом з) (с настраиваемыми каналами). Здесь двухточечные каналы настраиваются (программируются) перед началом ис4 пользования в специальном коммутаторе каналов. Что касается топологии д) (гиперкуб), то она детально будет рассмотрена делее На рис. 4. показаны варианты коммутируемых соединений. Для их организации используются коммутаторы сообщений. В них не программируются каналы, а организуется маршрутизация передачи сообщений с данными согласно протоколу. N N N Коммутатор сообщений N N N N узелкоммутатор N N N а) пассивная звезда N N N N КС КС N N N б) активная звезда N КС N N N N N Коммутатор сообщений N N N N Коммутатор сообщений Коммутатор сообщений N в) сетка г) иерархическая Рис. 4. Коммутируемые соединения Особо надо оговорить различие между вариантами а) и б). В пассивной звезде коммутатор сообщений производит маршрутизацию согласно протоколу и всё. В активной звезде узел-коммутатор может сам выполнять часть вычислительной нагрузки, а также может служить диспетчером, и пересылать данные не назначенному узлу, а узлу способному эффективно обработать принятые данные. Расчёт времени передачи данных между узлами Расчёт времени передачи сообщений с данными между узлами вычислительной системы в свободных каналах в топологиях: полный граф, звезда, полное двоичное дерево, линейка, кольцо, 2D-решетка, 2D-тор, гиперкуб. 5 Для начала необходимо обозначить некоторые важные характеристики топологий: диаметр – показатель (обозначим его d), определяемый как максимальное расстояние между двумя узлами сети (под расстоянием обычно понимается величина кратчайшего пути между узлами); связность – показатель, характеризующий наличие разных маршрутов передачи данных между процессорами сети; конкретный вид данного показателя может быть определен, например, как минимальное количество каналов, которое надо удалить для разделения сети передачи данных на две несвязные области; ширина бинарного деления – показатель, определяемый как минимальное количество дуг, которое надо удалить для разделения сети передачи данных на две несвязные области одинакового размера; стоимость – показатель, который может быть определен, например, как общее количество линий передачи данных в вычислительной системе. Целое сообщение с m d - диаметр N N Пакеты сообщения с mp с mp с mp tн – время начальной подготовки данных сообщения tс – время передачи служебной информации tк – время передачи по каналу единицы сообщения (байта, слова) tф – время завершения передачи на принимающем узле Время передачи данных целым единым сообщением T=tн+(mtk+tс)d или T=tн+(mtk+tс)d+tф Время передачи данных пакетами T=tн+mtk+tсd или T=tн+mtk+tсd+tф Рис. 5. Определение времени передачи сообщения с данными 6 На рис. 5 показан канал между двух узлов имеющий связь длиной в d стадий – то есть равна диаметру топологии. Данные передаются либо: единым сообщением представляющем собой пакет из M-байт в которые входят m-байт непосредственно данных и с-байт заголовка, либо сообщением пакетами по mp-байт (при этом у каждого пакета свой полноценный заголовок). По сравнению с формулой (1), в предлагаемых здесь формулах вместо пропускной способности канала ρ, предлагается использовать время передачи по каналу единицы сообщения tk. Время tk связано с пропускной способностью канала ρ не напрямую, но как конкретно соотносятся формулы на рис. 5 в формулой (1) в данной лекции не рассматривается. На рис. 6, 7 и 8 приведены формулы расчёта времени для заявленных ранее топологий (кроме гиперкуба). Формулы основаны на формулах из рис. 5. Главным их отличием между собой является то, как подсчитывается диаметр d. Формулы для расчёта времени передачи данных в топологиях взяты из учебного пособия: В.П. Гергель, Р.Г. Стронгин Основы параллельных вычислений для многопроцессорных вычислительных систем Целое сообщение T=tн+mtk+tс+tф N N N N Сообщение пакетами T=tн+mtk+tс+tф N полный граф N N Коммутатор сообщений N N Целое сообщение T=tн+(mtk+tс)2+tф N Сообщение пакетами T=tн+mtk+tс2+tф N звезда Рис. 6. Расчёт времени передачи данных для полного графа и звезды 7 N N N N N N двоичное дерево N N N N линейка N N N N Здесь и далее р - количество узлов N кольцо Целое сообщение T=tн+(mtk+tс)2log2((p-1)/2)+tф Сообщение пакетами T=tн+mtk+tс2log2((p-1)/2)+tф Целое сообщение T=tн+(mtk+tс)(p-1)+tф Сообщение пакетами T=tн+mtk+tс(p-1)+tф Целое сообщение T=tн+(mtk+tс) p/2 +tф Сообщение пакетами T=tн+mtk+tс p/2 +tф N N N N N N N N N N N N 2D-решётка N N N N N N N N N N N N N N N N Здесь и далее р - количество узлов Рис. 7. Расчёт времени передачи данных для двоичного дерева, линейки и кольца Целое сообщение T=tн+(mtk+tс)2( p-1)+tф Сообщение пакетами T=tн+mtk+tс2( p-1)+tф Целое сообщение T=tн+(mtk+tс)2 p/2 +tф Сообщение пакетами T=tн+mtk+tс2 p/2 +tф 2D-тор Рис. 8. Расчёт времени передачи данных для 2D-решетки и 2D-тора На рис. 9 показан расчёт времени передачи данных для гиперкуба. Приведём определение и описание данной топологии: 8 Гиперкуб (hypercube) - данная топология представляет собой частный случай структуры решетки, когда по каждой размерности сетки имеется только два процессора. 0,0,0,0 0,0,0,1 N N N N Целое сообщение T=tн+(mtk+tс)log2p+tф 0,1,0,1 N Сообщение пакетами T=tн+mtk+tсlog2p+tф N N N N N N N N N N 1,1,0,1 1,1,1,1 N 0,0 N 0,1 N 1,0 N 1,1 N Рис. 9. Расчёт времени передачи данных для гиперкуба Топология гиперкуба достаточно широко распространена на практике при объединении параллельных процессоров. Линия, соединяющая два узла определяет одномерный гиперкуб. Квадрат, образованный четырьмя узлами - двумерный гиперкуб, а куб из восьми узлов - трехмерный гиперкуб и т.д. Из этого ряда следует алгоритм получения n-мерного гиперкуба: начать с (n-1)-мерного гиперкуба, сделать его идентичную копию, а затем добавить связи между каждым узлом исходного гиперкуба и одноименным узлом копии. Гиперкуб размерности n = log2p имеет следующие характеристики: D = n; d = n; I = np/2; B = p/2. Увеличение размерности гиперкуба на единицу ведет к удвоению числа его узлов, увеличению порядка узлов и диаметра сети на единицу. Обмен сообщениями в гиперкубе базируется на двоичном представлении номеров узлов. Нумерация узлов производится так, что для любой пары смежных узлов двоичное представление номеров этих узлов отличается только в одной позиции. В силу сказанного, узлы 0010 и 0110 - соседи, а узлы 0110 и 0101 таковыми не являются. Описание топологии гиперкуба взято из: http://www.nsc.ru/win/elbib/data/show_page.dhtml?77+791 9