Slides_OEVM_final
.pdf
Лекция 6. Сети межсоединений:
топология
Типовые топологии
Полный граф (completely-connected graph) –
система, в которой между любой парой 
процессоров существует прямая линия связи.
Такая топология обеспечивает минимальные затраты при передаче данных, однако является
сложно реализуемой при большом количестве процессоров;
141
© С. Г. Мосин, 2007
Лекция 6. Сети межсоединений:
топология
Типовые топологии
Линейка (linear array) – система, в которой все процессоры перенумерованы по порядку и каждый процессор, кроме первого и последнего, имеет линии связи только с двумя соседними (с предыдущим и последующим) процессорами. Такая схема является, с одной стороны, просто реализуемой, c другой стороны, соответствует структуре передачи данных при решении многих вычислительных задач (например, при организации конвейерных вычислений);
142
© С. Г. Мосин, 2007
Лекция 6. Сети межсоединений:
топология
Типовые топологии
Кольцо (ring) – данную топологию получают
из линейки процессоров соединением первого и последнего процессоров линейки;
Звезда (star) – система, в которой все
процессоры имеют линии связи с некоторым управляющим процессором.
Данная топология является эффективной, например, при организации
централизованных схем параллельных вычислений;
143
© С. Г. Мосин, 2007
Лекция 6. Сети межсоединений:
топология
Типовые топологии
Решетка (mesh) – система, в которой граф линий связи образует прямоугольную сетку.
Подобная топология может быть достаточно 
просто реализована и эффективно 
использована при параллельном выполнении 
многих численных алгоритмов; 
144
© С. Г. Мосин, 2007
Лекция 6. Сети межсоединений:
топология
Типовые топологии
Гиперкуб (hypercube) – данная топология представляет собой частный случай структуры решетки, когда по каждой размерности сетки имеется только два процессора (т.е. гиперкуб содержит 2N процессоров при размерности N).
145
© С. Г. Мосин, 2007
Лекция 6. Сети межсоединений:
топология
Характеристики топологии
Топология |
Диаметр |
Ширина |
Связность бисекции |
Стоимость |
|
|
|
|
|
|
|
Полный граф |
1 |
p2/4 |
p–1 |
p(p–1)/2 |
|
|
|
|
|
|
|
Звезда |
2 |
1 |
1 |
p–1 |
|
|
|
|
|
|
|
Полное двоичное дерево |
2log((p+1)/2) |
1 |
1 |
p–1 |
|
|
|
|
|
|
|
Линейка |
p–1 |
1 |
1 |
p–1 |
|
|
|
|
|
|
|
Кольцо |
p/2 |
2 |
2 |
p |
|
|
|
|
|
|
|
Решетка N = 2 |
_ |
_ |
2 |
_ |
|
2(Öp–1) |
Öp |
2(p–Öp) |
|||
|
|
||||
|
|
|
|
|
|
Гиперкуб |
log p |
p/2 |
log p |
(p log p)/2 |
|
|
|
|
|
|
146
© С. Г. Мосин, 2007
Лекция 6. Сети межсоединений:
коммутация
Задача коммутатора – принимать пакеты, которые приходят на любой входной порт, и отправлять пакеты из соответствующих выходных портов. Каналы могут быть последовательными и параллельными.
Стратегии переключения:
1.Коммутация каналов. Перед передачей пакетов требуется резервирование всего пути от начального пункта до конечного (порты + буферы).
2.Коммутация с промежуточным хранением. Весь пакет посылают из исходного пункта в первый коммутатор, где он хранится целиком, затем в следующий и т.д.
Требование – наличие буферов.
147
© С. Г. Мосин, 2007
Лекция 6. Сети межсоединений:
коммутация
Методы буферизации:
1.Буферизация на входе. Один или несколько буферов связывают с каждым входным портом в форме очереди FIFO. Если пакет в начале очереди нельзя передать из-за занятости нужного выходного порта, то пакет ждет освобождения ресурса.
2.Буферизация на выходе. Буферы связаны с выходными портами.
3.Общая буферизация. Один буфер динамически распределяется по портам по мере необходимости. Недостаток – сложность управления.
148
© С. Г. Мосин, 2007
Лекция 6. Сети межсоединений:
маршрутизация
Алгоритмы выбора маршрута:
1.Маршрутизация от источника. Источник определяет весь путь заранее. Путь выражают списком из номеров портов,
которые необходимо использовать в каждом коммутаторе до пункта назначения.
2.Распределенная маршрутизация. Каждый коммутатор сам решает в какой выходной порт отправить каждый приходящий пакет. Если правила выбора одинаковы для всех пакетов, то маршрутизация статическая. Если коммутатор учитывает изменение состояния трафика, то маршрутизация адаптивная.
149
© С. Г. Мосин, 2007
Лекция 6. Сети межсоединений:
методы передачи данных
Время передачи данных, состоит из следующего ряда величин:
1.Время начальной подготовки (tн) характеризует длительность подготовки сообщения для передачи, поиска маршрута в сети и т. п.;
2.Время передачи служебных данных (tс) между двумя соседними процессорами (т.е. для процессоров, между которыми имеется физический канал передачи данных).
3.Время передачи одного слова данных по одному каналу
передачи данных (tк). Длительность подобной передачи
определяется полосой пропускания коммуникационных каналов в сети.
150
© С. Г. Мосин, 2007