ПОД конспект (1184369), страница 10
Текст из файла (страница 10)
Число процессоров в таких системах всегдаограничено.Статические сетиСтатические сети имеют жестко фиксированные соединения, вход и выход зафиксированы безвозможности переключения. Наиболее простой топологией сети является линейка – одномерная сетка. Дляобеспечения передачи информации между несмежными узлам используются транзитные пересылки.
Дляцепочки из М узлов наиболее медленная пересылка есть пересылка между конечными ПЭ линейки и онапотребует (М-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. If the switch has M inputs and N outputs, then a crossbar has a matrix with M x N cross-points or placeswhere there the "bars" "cross". A given crossbar is a single layer, non-blocking switch.
Collections of crossbars canbe used to implement multiple layer and/or blocking switches. Дополнительно см. Вопрос 34.41. Многокаскадные коммутационные сети.Сначала см. Вопрос 34.Источник 1: Среди традиционных сетей особое положение занимают сети, базирующиеся на большомчисле идентичных ключевых элементов. Это сети с многокаскадными связями (MIN – MultistageInterconnection Network).
Идеология таких сетей используется при построении коммутаторов ATM. Из такихсетей наиболее известной является Delta Banyan (Batcher-switch). Эта сеть содержит регулярную структуруN*N переключателей с двух направлений на два. Сеть содержит log2N число каскадов, каждый из которыхимеет N/2 переключателей. Для управления маршрутизацией сообщений в этой сети необходимо log2N битинформации. Схема 4-каскадной сети Delta-2 приведена на рис.Источник 2: Многокаскадные сети основаны на использовании 2х2 перекрестных переключателей коммутаторов. В таких сетях на одном конце находятся процессоры, на другом - процессоры или другиеузлы, а между ними располагаются переключатели.
При передаче информации от узла к узлу переключателиустанавливаются таким образом, чтобы обеспечить требуемое соединение. На приведена схема соединения"омега", являющейся сетью с блокировкой, в которой один маршрут передачи данных может заблокировать24другие маршруты. Для соединения n процессоров с n модулями памяти требуется (n/2)*log2nпереключателей.Матричный коммутатор обеспечивает полную связность, т.е. любой процессорный элемент (ПЭ) можетсвязаться с любым другим процессорным элементом или модулем памяти (МП).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
