СКИПОДы конспект лекций (1127769), страница 10
Текст из файла (страница 10)
Однако, детализация работы протокола в реальном устройстве приводит кзначительным усложнениям полученной картины. Так, даже для простейшего протокола типа MSI(однопроцессорная система) имеем 11 состояний (8 из которых переходных), 13 возможных событий и 21действие.34. Типы внутренних связей.Сети обмена делятся на три типа: шины, статические сети, динамические сети.Быстродействие сети обмена определяется быстродействием узлов и связей между ними, параметрыпоследних определяются: пропускной способностью непрерывного потока данных и максимальнымколичеством самых маленьких пакетов, которые можно передать за единицу времени (время передачипакета нулевой длины, задержка).
Некоторые сетевые интерфейсы:ТехнологияMbyte/sЗадержка (мкс)Fast Ethernet12.5156Gigabit Ethernet12533Myrinet2456SCI4001.5ШиныСистема связи ПЭ через коммутирующую общую шину отличаются от других схем простотой, однако еепроизводительность ограничивается необходимостью обеспечивать в любой момент времени не болееодного запроса на передачу информации. Общая шина с центральным коммутатором обеспечиваетарбитраж запросов процессоров на передачу информации - выделение одного из запросов на доступ кшине и обеспечение монопольного права на владения шиной на все время требуемого обмена. Шины пропускная способность 100 Мбайт/с для 2 -20 ПЭ (Multimax). Число процессоров в таких системах всегдаограничено.Статические сетиСтатические сети имеют жестко фиксированные соединения, вход и выход зафиксированы безвозможности переключения.
Наиболее простой топологией сети является линейка – одномерная сетка. Дляобеспечения передачи информации между несмежными узлам используются транзитные пересылки. Дляцепочки из М узлов наиболее медленная пересылка есть пересылка между конечными ПЭ линейки и онапотребует (М-1) транзитных пересылок. Число таких пересылок для любой статической топологии сетисчитается ее параметром и называется – диаметром сети.
Если связать конечные ПЭ линейки, то такаятопология - кольцо будет иметь меньший диаметр. Сети могут иметь вид: одномерный линейный массив,двумерное кольцо, звезда, сетка и гексагональный массив, дерево, трехмерное полностью связанноехордовое кольцо, 3 -мерный куб, сети из циклически связанных 3-мерных кубов, D - мерный массив стопологией гиперкуба, тасовка (совершенная, обменная). Недостаток - необходимость маршрутизациитранзитных сообщений. По топологии гиперкуба, каждое ПЭ связывается со своим ближайшем соседом в nмерном пространстве. У каждого узла в двумерном гиперкубе имеются два ближайших соседа, втрехмерном - три, в четырехмерном - четыре.Динамические сетиДинамические сети - сети с возможностью динамического (коммутируемого) соединения узлов сети друг сдругом.
Особое место занимает полный коммутатор.Полный коммутатор обеспечивает полную связность каждого узла в сети, причем, обеспечиваетнезависимость (не блокируемость) пересылок. Недостаток: высокая стоимость аппаратуры и ограниченнаяразмерность.Перечисленные выше однокаскадные сети обмена содержат фиксированное число каскадов или один каскадпереключателей. Многокаскадные сети могут быть получены комбинацией некоторых однокаскадных сетейи могут составить конкуренцию полному коммутатору. Например, стандартная сеть Клоша (Клоса) можетиметь нечетное число каскадов и строится из сетей меньших размеров.
Clos networks have three stages: theingress stage, middle stage, and the egress stage. Each stage is made up of a number of crossbar switches (seediagram below), often just called crossbars. Each call entering an ingress crossbar switch can be routed through anyof the available middle stage crossbar switches, to the relevant egress crossbar switch. A middle stage crossbar isavailable for a particular new call if both the link connecting the ingress switch to the middle stage switch, and thelink connecting the middle stage switch to the egress switch, are free.
Clos networks are defined by three integers n,22m, and r. n represents the number of sources which feed into each of r ingress stage crossbar switches. Each ingressstage crossbar switch has m outlets, and there are m centre stage crossbar switches. There is exactly one connectionbetween each ingress stage switch and each middle stage switch. There are r egress stage switches, each with minputs and n outputs.
Each middle stage switch is connected exactly once to each egress stage switch.35. Статические и динамические коммуникаторы.См Вопрос 34.36. Параметры статических коммутационных сетей.См Вопрос 34.37. Топологии линейки, решетки, пирамиды.Наиболее простой топологией сети является линейка – одномерная сетка. Для обеспечения передачиинформации между несмежными узлам используются транзитные пересылки.
Для цепочки из М узловнаиболее медленная пересылка есть пересылка между конечными ПЭ линейки и она потребует (М-1)транзитных пересылок. Решетка –таблица, в которой узлы связаны только со своими соседями вверх и вниз– то есть матрица. Удобно для решения и представления задач с изображением и другимипространственными задачами, где решение тесно связано с решением соседних по пространству частей.Деревья имеют хорошую структуру для большого числа задач, в которых информация сортируется,сравнивается или каким-либо образом уплотняется и реорганизуется, а также где она запоминается,извлекается или передается.
Матрицы имеют хорошую структуру для локальной передачи информации.Наилучшими считаются пирамидальные многопроцессорные системы, поскольку они очень эффективныне только при параллельной локальной обработке,но и при глобальных передачах и преобразованияхинформации. Древовидная топология пирамиды определяет возможность накопления и объединенияинформации по мере поэтапного преобразования данных. Также наиболее актуально для изображения.Матричные, конвейерные и в особенности пирамидальные структуры обеспечивают увеличениепроизводительности и вычислительной мощности на несколько порядков по сравнению с традиционнымиЭВМ с одним ЦП. Они особенно пригодны для обработки изображений, распознавания образов и в системахтехнического зрения.
Они также хорошо соответствуют требованиям технологии СБИС благодаря своейрегулярной микромодульной структуре.38. Топология гиперкуба.Двоичный гиперкуб - распространенная, хорошо масштабируемая и очень удачная топология (рис. 25). Вней 2k процессоров организованы в k-мерный гиперкуб. У каждого процессора k непосредственныхсоединений (k = log2N), максимальное расстояние между узлами k. Для адресации узлов в гиперкубекаждому узлу присваивается идентификационный номер (ID).
Двоичное представление ID соседних узловотличается одним разрядом. Алгоритм пересылки сообщения от одного узла к другому основан напобитовом сравнении двоичных представлений ID текущего узла и адресата. Для каждого процессора легко23определить всех его соседей - они отличаются лишь значением какого-либо одного разряда в двоичномпредставлении ID. Каждая грань k-мерного гиперкуба является гиперкубом размерности k-1.
См. такжеТаненбаум, стр 43.39. Согласование сеточных топологий со структурой гиперкуба.Сеточная топология (mesh), при которой компьютеры связываются между собой не одной, а многимилиниями связи, образующими сетку. В полной сеточной топологии каждый компьютер напрямую связан совсеми остальными компьютерами. В этом случае при увеличении числа компьютеров резко возрастаетколичество линий связи. Кроме того, любое изменение в конфигурации сети требует внесения изменений всетевую аппаратуру всех компьютеров, поэтому полная сеточная топология не получила широкогораспространения. Частичная сеточная топология предполагает прямые связи только для самых активныхкомпьютеров, передающих максимальные объемы информации.
Остальные компьютеры соединяются черезпромежуточные узлы. Сеточная топология позволяет выбирать маршрут для доставки информации отабонента к абоненту, обходя неисправные участки. С одной стороны, это увеличивает надежность сети, сдругой же – требует существенного усложнения сетевой аппаратуры, которая должна выбирать маршрут.40. Перекрестный коммутатор.Crossbar switches have a characteristic matrix of switches between the inputs to the switch and the output of theswitch.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
