Архитектура вычислительных систем

1.

ВОЕННО-КОСМИЧЕСКАЯ АКАДЕМИЯ ИМЕНИ А.Ф. МОЖАЙСКОГО
Кафедра информационно-вычислительных систем и сетей
РАЗДЕЛ 3. Вычислительные системы
Тема 8. Архитектура вычислительных систем
Доктор технических наук профессор,
БАСЫРОВ А.Г.

2.

ОРГАНИЗАЦИЯ ЭВМ И СИСТЕМ
Лекция №25
Топологии вычислительных систем
Цель: сформировать у обучающихся знания о топологиях
сети межсоединений вычислительных систем
Учебные вопросы:
1.Понятие топологии сети межсоединений и метрики
сетевых соединений
2.Основные топологии сети межсоединений
вычислительных систем
2

3.

Учебный вопрос № 1
Понятие топологии сети межсоединений
и метрики сетевых соединений
3

4.

Понятие топологии сети межсоединений
Топология ВС – абстрактная характеристика структуры
ВС, учитывающая только свойства существования
элементов структуры и их связности (организация ее
внутренних коммуникаций)
Коммуникационная система ВС представляет собой сеть, узлы
которой связаны трактами передачи данных — каналами
В роли узлов могут выступать процессоры, модули памяти,
устройства ввода/вывода, коммутаторы либо несколько
перечисленных элементов, объединенных в группу
Топология сети межсоединений –
структура линий коммутации между
процессорами вычислительной системы
4

5.

Понятие топологии сети межсоединений
ТИПЫ ТОПОЛОГИЙ
СТАТИЧЕСКАЯ
ДИНАМИЧЕСКАЯ
ТИПЫ УЗЛОВ В СЕТИ
Терминальный
узел
Коммутатор
Терминальный +
коммутатор
ТИПЫ СВЯЗЕЙ МЕЖДУ УЗЛАМИ
непосредственные
косвенные
5

6.

Понятие топологии сети межсоединений
АТРИБУТЫ СЕТИ МЕЖСОЕДИНЕНИЙ
стратегия
синхронизации
стратегия
коммутации
стратегия
управления
синхронная
синхронизация
с коммутацией
соединений
централизованное
управление
асинхронная
синхронизация
с коммутацией
пакетов
децентрализованное
управление
6

7.

Понятие топологии сети межсоединений
Функции маршрутизации данных в вычислительных
системах – функция, задающая порядок выбора
промежуточных узлов от узла-источника к узлу-приемнику
Функция маршрутизации данных задает правило вычисления
возможного адреса одного из смежных узлов по адресу второго узла
ФУНКЦИИ МАРШРУТИЗАЦИИ ДАННЫХ
ПЕРЕСТАНОВКА
ТАСОВАНИЕ
БАТТЕРФЛЯЙ
РЕВЕРСИРОВАНИЕ БИТОВ
СДВИГ
7

8.

Функция «перестановка»
E k (bm ,..., bk ,....., b1) (bm ,..., bk ,..., b1)
001
000
010
011
100
111
110
101
8

9.

Функция «тасование»
Виды функции «тасование»
идеальное тасование
отсутствие тасования
субтасование по i-му биту
супертасование по i-му биту
9

10.

Функция «тасование»
идеальное тасование
S (bm , bm 1,..., b1) (bm 1, bm 2 ,.., b1,bm)
отсутствие тасования
U (bm , bm 1,..., b1) (b1, bm ,.., b2)
10

11.

Функция «тасование»
субтасование по i-му биту
S (bm , bm 1,..bi ,...., b1) (bm ,...,bi 1,bi 1,...,bi)
i
примеры для i=2
супертасование по i-му биту
S (bm , bm 1,..bi ,...., b1) (bm 1,..., bm i 1,bm ,.bm i ,..., b1)
i
11

12.

Функция «баттерфляй»
12
B(bm , bm 1,....., b1) (b1, bm 1, ..., b2 , bm)
m=2
m=3

13.

Функция «реверсирование битов»
R(bm , bm 1,....., b1) (b1, b2 , ..., bm)
13

14.

Функция «сдвиг»
SH ( x) ( х 1) mod N
m=3
14
(N 2 )
m

15.

Метрики сетевых соединений
размер сети
диаметр сети
порядок узла
пропускная способность
задержка
связность
ширина бисекции
полоса бисекции
стоимость
15

16.

Метрики сетевых соединений
16
размер сети – количество узлов, объединяемых сетью
диаметр – максимальное расстояние между двумя
процессорами сети (число дуг в кратчайшем маршруте,
соединяющим два максимально удаленных узла)
Характеризует максимально необходимое время для передачи
данных между процессорами
порядок узла – сумма числа входных и выходных каналов
узла, то есть число узлов сети, с которыми данный узел
связан напрямую
пропускная
способность
сети
–
количество
информации, которое может быть передано по сети в
единицу времени

17.

Метрики сетевых соединений
17
задержка сети – время, требуемое на прохождение
сообщения через сеть. В сетях, где время передачи
сообщений зависит от маршрута, говорят
минимальной и максимальной задержках сети
о
средней,
связность – минимальное количество дуг, которое надо
удалить для разделения сети передачи данных на две
несвязные области
ширина бисекции (бинарного деления) – минимальное
количество дуг, которое надо удалить для разделения сети
передачи данных на две несвязные области одинакового
размера
полоса бисекции – наименьшая полоса пропускания по
всем возможным бисекциям сети
стоимость – общее количество линий передачи данных
в многопроцессорной вычислительной системе

18.

Метрики сетевых соединений
18
размер сети
=8
диаметр сети
=3
порядок узла
=3
связность
=2
ширина бисекции
=4
стоимость
= 11

19.

Учебный вопрос № 2
Основные топологии сети межсоединений
вычислительных систем
19

20.

Основные топологии сети межсоединений ВС
ВНУТРЕННИЕ СВЯЗИ
статические топологии
динамические топологии
сети связи
одномерные
шины
цепочка
кольцо
звезда
трехмерные
дерево
сетка
трехмерный куб
двумерные
гиперкубические
одношинная топология
многошинная топология
коммутаторы
перекрестные
матричный
однокаскадные
прямой двоичный куб
тасовка
многокаскадные
омега
ось
баньян
другие
20

21.

Статические топологии
21
полный граф – система, в которой
между любой парой процессоров
существует прямая линия связи
Полный граф
линейка – система, в которой все
процессоры
перенумерованы
по
порядку и каждый процессор, кроме
первого и последнего, имеет линии
связи только с двумя соседними
Линейка

22.

Статические топологии
22
кольцо – топология, получаемая из
линейки
процессоров
соединением
первого и последнего процессоров
линейки
Кольцо
звезда – система, в которой все
процессоры имеют линии связи с
некоторым управляющим процессором
Звезда

23.

статические топологии
дерево – многоуровневая система, в которой
процессоры более высокого уровня имеют линии
связи с двумя процессорами следующего по
порядку более низкого уровня
23

24.

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

25.

статические топологии
25
ГИПЕРКУБЫ
Гиперкуб
размерностью 2
(порядок узла d=2)
Гиперкуб
размерностью 3
(порядок узла d=3)
Гиперкуб размерностью 4 (порядок узла d=4)

26.

Основные топологии сети межсоединений ВС
Сравнительная характеристика топологий сети
Топология
Диаметр
Полный
граф
1
Звезда
2
1
1
N-1
Линейка
N-1
1
1
N-1
Кольцо
N 2
2
2
N
Гиперкуб
log2N
N/2
log2N
N log2N/2
Решетка
2 N 2
2 N
4
2N
Ширина Связность Стоимость
бисекции
N2/4
N-1
N(N-1)/2
26

27.

Основные топологии сети межсоединений вычислительных систем
одношинная топология
общая шина
общая шина с коммутатором
(арбитром шины)
27

28.

динамические топологии
многошинная топология
с подключением ко всем шинам
28

29.

динамические топологии
многошинная топология
с подключением к одной из шин
29

30.

динамические топологии
многошинная топология
с подключением к части шин
30

31.

динамические топологии
многошинная топология
с подключением по классам
31

32.

Принципы построения коммутаторов внутренних связей
Перекрестный коммутатор
X1…X4 – входы
Y1…Y4 – выходы
32

33.

Принципы построения коммутаторов внутренних связей
Состояния коммутирующего элемента
прямое соединение
верхнее раздвоение
перекрестное соединение
нижнее раздвоение
33

34.

Основные типы коммутаторов
однокаскадный
коммутатор «Тасовка»
многокаскадная сеть коммутации
«Омега»
34

35.

Основные типы коммутаторов
многокаскадная сеть коммутации «Баньян»
35

36.

Задание на самостоятельную работу
36
Задание:
1. Повторить материал лекции по конспекту
2. Изучить рекомендованную литературу [3, с.37-57],
[4, с.94-98, 494-525];
Найти значения функций маршрутизации для 16-процессорной
ВС:
E2(N), S(N), U(N), S3(N), S3(N), B(N), R(N),
где N – [номер курсанта по списку (журналу)] по модулю 16.