Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ВОПРОС 30
Классификация вычислительных систем Флинна [PDA версия] Наиболее ранней и наиболее известной классификацией является архитектур является архитектура, придуманная Флинном в 1966 г. Данная классификация базируется на понятии потока. Под потоком понимается последовательность элементов команд или данных, обрабатываемых процессором. На основе числа потоков команд и потоков данных выделяют 4 класса архитектур:
1) SISD – одиночный поток команд, одиночный поток данных. К данному классу относят все классические последовательные машины. В них есть только один поток команд, все команды обрабатываются последовательно, друг за другом. Каждая команда осуществляет одну операцию с 1 потоком данных.
2) MISD – множественный поток команд, одиночный поток данных. Данная архитектура подразумевает большое число процессоров, обрабатывающих один и тот же поток данных. Однако на данный момент не существует такой системы
3) MIMD – множественный поток команд, множественный поток данных. Данный класс подразумевает, что есть несколько устройств обработки команд (процессоры), объединенные в некий единый комплекс, и каждое работает со своим потоком команд и данных
Дополнение к классификации Флинна
4) SIMD
Было предложено разбить класс SISD на 2 подкласса:
1) архитектуры с единственным функциональным устройством
2) архитектуры, имеющие в своем составе несколько функциональных устройств
Класс SIMD одиночного потока команд и множественного потока данных был разделен на два подкласса:
1) архитектуры с пословно-последовательной обработкой информации
2) архитектуры с разрядно-последовательной обработкой информации
Класс MIMD разбит на:
1) системы со слабой связью между процессорами (системы с распределенной памятью)
2) системы с сильной связью (с общей памятью)
ВОПРОС 31
Архитектурные особенности организации ЭВМ различных классов.
По перечисленным признакам и их сочетаниям среди архитектур выделяют:
По разрядности интерфейсов и машинных слов: 8-, 16-, 32-, 64-, 128- разрядные (ряд ЭВМ имеет и иные разрядности);
По особенностям набора регистров, формата команд и данных: CISC, RISC, VLIW;
По количеству центральных процессоров: однопроцессорные, многопроцессорные, суперскалярные;
многопроцессорные по принципу взаимодействия с памятью: симметричные многопроцессорные (SMP), масcивно-параллельные (MPP), распределенные.
Архитектура ЭВМ - это многоуровневая иерархия аппаратурно-программных средств, из которых строится ЭВМ. Каждый из уровней допускает многовариантное построение и применение. Конкретная реализация уровней определяет особенности структурного построения ЭВМ. В последующих разделах учебника эти вопросы подробно рассматриваются.
Детализацией архитектурного и структурного построения ЭВМ занимаются различные категории специалистов вычислительной техники. Инженеры-схемотехники проектируют отдельные технические устройства и разрабатывают методы их сопряжения друг с другом. Системные программист создают программы управления техническими средствами, информационного взаимодействия между уровнями, организации вычислительного процесса. Программисты-прикладники разрабатывают пакеты программ более высокого уровня, которые обеспечивают взаимодействие пользователей с ЭВМ и необходимый сервис при решении ими своих задач. Переменные в С могут быть локальными и глобальными
Самого же пользователя интересуют обычно более общие вопросы, касающиеся его взаимодействия с ЭВМ (человеко-машинного интерфейса), начиная со следующих групп характеристик ЭВМ, определяющих ее структуру:
· технические и эксплуатационные характеристики ЭВМ (быстродействие и производительность, показатели надежности, достоверности, точности, емкость оперативной и внешней памяти, габаритные размеры, стоимость технических и программных средств, особенности эксплуатации и др.);
· характеристики и состав функциональных модулей базовой конфигурации ЭВМ; возможность расширения состава технических и программных средств; возможность изменения структуры;
· состав программного обеспечения ЭВМ и сервисных услуг (операционная система или среда, пакеты прикладных программ, средства автоматизации программирования).
Одной из важнейших характеристик ЭВМ является ее быстродействие, которое характеризуется числом команд, выполняемых ЭВМ за одну секунду. Поскольку в состав команд ЭВМ включаются операции, различные по длительности выполнения и по вероятности их использования, то имеет смысл характеризовать его или средним быстродействием ЭВМ, или предельным (для самых “коротких” операций типа “регистр-регистр”). Современные вычислительные машины имеют очень высокие характеристики по быстродействию, измеряемые десятками и сотнями миллионов операций в секунду. Например, в ближайшее время ожидается появление микропроцессора совместного производства фирм Intel и Hewlett-Packard (шифр Р7), быстродействие которого должно достичь миллиарда операций в секунду.
Реальное или эффективное быстродействие, обеспечиваемое ЭВМ, значительно ниже, и оно может сильно отличаться в зависимости от класса решаемых задач. Сравнение по быстродействию различных типов ЭВМ, резко отличающихся друг от друга своими характеристиками, не обеспечивает достоверных оценок. Поэтому очень часто вместо характеристики быстродействия используют связанную с ней характеристику производительности -объем работ, осуществляемых ЭВМ в единицу времени. Например, можно определять этот параметр числом задач, выполняемых за определенное время. Однако сравнение по данной характеристике ЭВМ различных типов может вызвать затруднения. Поскольку оценка производительности различных ЭВМ является важной практической задачей, хотя такая постановка вопроса также не вполне корректна, были предложены к использованию относительные характеристики производительности. Так, например, фирма Intel для оценки процессоров предложила тест, получивший название индекс iCOMP (Intel Comparative Microprocessor Performance). При его определении учитываются четыре главных аспекта производительности: работа с целыми числами, с плавающей точкой, графикой и видео. Данные имеют 16- и 32-разрядное представление. Каждый из восьми параметров при вычислении участвует со своим весовым коэффициентом, определяемым по усредненному соотношению между этими операциями в реальных задачах
ВОПРОС 32
Параллельные вычислительные системы — это физические компьютерные, а также программные системы, реализующие тем или иным способом параллельную обработку данных на многих вычислительных узлах.
Например, для быстрой сортировки массива на двухпроцессорной машине можно разделить массив пополам и сортировать каждую половину на отдельном процессоре. Сортировка каждой половины может занять разное время, поэтому необходима синхронизация.
Параллелизм
Основная статья: Параллельные вычисления
Идея распараллеливания вычислений основана на том, что большинство задач может быть разделено на набор меньших задач, которые могут быть решены одновременно. Обычно параллельные вычисления требуют координации действий. Параллельные вычисления существуют в нескольких формах: параллелизм на уровне битов, параллелизм на уровне инструкций, параллелизм данных, параллелизм задач. Параллельные вычисления использовались много лет в основном в высокопроизводительных вычислениях, но в последнее время к ним возрос интерес вследствие существования физических ограничений на рост тактовой частоты процессоров. Параллельные вычисления стали доминирующей парадигмой в архитектуре компьютеров, в основном в форме многоядерных процессоров.[2]
Писать программы для параллельных систем сложнее, чем для последовательных[3], так как конкуренция за ресурсы представляет новый класс потенциальных ошибок в программном обеспечении (багов), среди которых состояние гонки является самой распространённой. Взаимодействие и синхронизация между процессами представляют большой барьер для получения высокой производительности параллельных систем. В последние годы также стали рассматривать вопрос о потреблении электроэнергии параллельными компьютерами.[4] Характер увеличения скорости программы в результате распараллеливания объясняется законом Амдала.
Параллелизм на уровне битов
Эта форма параллелизма основана на увеличении размера машинного слова. Увеличение размера машинного слова уменьшает количество операций, необходимых процессору для выполнения действий над переменными, чей размер превышает размер машинного слова. К примеру: на 8-битном процессоре нужно сложить два 16-битных целых числа. Для этого вначале нужно сложить нижние 8 бит чисел, затем сложить верхние 8 бит и к результату их сложения прибавить значение флага переноса. Итого 3 инструкции. С 16-битным процессором можно выполнить эту операцию одной инструкцией.
Исторически 4-битные микропроцессоры были заменены 8-битными, затем появились 16-битные и 32-битные. 32-битные процессоры долгое время были стандартом в повседневных вычислениях. С появлением технологии x86-64 для этих целей стали использовать 64-битные процессоры.
Параллелизм задач
Стиль программирования, основанный на параллелизме задач, подразумевает, что вычислительная задача разбивается на несколько относительно самостоятельных подзадач и каждый процессор загружается своей собственной подзадачей.
ВОПРОС 33
Назначение матричных вычислительных систем - обработка больших массивов данных (во многом схоже с назначением векторных ВС). В основе матричных систем лежит матричный процессор (array processor), состоящий из регулярного массива процессорных элементов (ПЭ).
Организация систем подобного типа на первый взгляд достаточно проста. Они имеют общее управляющее устройство, генерирующее поток команд, и большое число ПЭ, работающих параллельно и обрабатывающих каждый свой поток данных.
Между матричными и векторными системами есть существенная разница. Матричный процессор интегрирует множество идентичных функциональных блоков (ФБ), логически объединенных в матрицу и работающих в SIMD-стиле. Не столь существенно, как конструктивно реализована матрица процессорных элементов — на едином кристалле или на нескольких. Важен сам принцип - ФБ логически скомпонованы в матрицу и работают синхронно, то есть присутствует только один поток команд для всех. Векторный процессор имеет встроенные команды для обработки векторов данных, что позволяет эффективно загрузить конвейер из функциональных блоков. В свою очередь, векторные процессоры проще использовать, потому что команды для обработки векторов — это более удобная для человека модель программирования, чем SIMD.
Структуру матричной вычислительной системы можно представить в следующем виде.
Обобщенная модель матричной ВС
Рассмотрим компоненты обобщенной модели матричной ВС.
Массив процессоров (МПр) осуществляет параллельную обработку множественных элементов данных.
Контроллер массива процессоров (КМП) генерирует единый поток команд, управляющий обработкой данных в массиве процессоров, выполняет последовательный программный код, реализует операции условного и безусловного переходов, транслирует в МПр команды, данные и сигналы управления. Команды обрабатываются процессорами в режиме жесткой синхронизации.
Сигналы управления используются для синхронизации команд и пересылок, а также для управления процессом вычислений, в частности определяют, какие процессоры массива должны выполнять операцию, а какие - нет.
Шина широковещательной рассылки служит для передачи команд, данных и сигналов управления из КМП в массив процессоров.
Шина результата служит для трансляции результатов вычислений из МПр в КМП (это требуется, поскольку выполнение операций условного перехода зависит от результатов вычислений).
Интерфейсная ВМ (front-end computer)
служит для обеспечения пользователя удобным интерфейсом при создании и отладке программ. В роли такой ВМ выступает универсальная вычислительная машина, на которую дополнительно возлагается задача загрузки программ и данных в КМП. Кроме того, загрузка программ и данных в КМП может производиться и напрямую с устройств ввода/вывода, например с магнитных дисков. После загрузки КМП приступает к выполнению программы, транслируя в МПр по широковещательной шине соответствующие SIMD-команды.
ВОПРОС 34
Многомашинные вычислительны системы (ММС) обеспечивают: повышения производительности, надежности и достоверности вычислений. Для этих целей использовали комплекс машин, схематически показанный на рис.
Положения 1 и 3 электронного ключа (ЭК) обеспечивало режим повышенной надежности. При этом одна из машин выполняла вычисления, а другая находилась в "горячем" или "холодном" резерве, т.е. в готовности заменить основную ЭВМ. Положение 2 электронного ключа соответствовало случаю, когда обе машины обеспечивали параллельный режим вычислений. Здесь возможны две ситуации:
обе машины решают одну и ту же задачу и периодически сверяют результаты решения. Тем самым обеспечивался режим повышенной достоверности, уменьшалась вероятность появления ошибок в результатах вычислений;
обе машины работают параллельно, но обрабатывают собственные потоки заданий. Возможность обмена информацией между машинами сохраняется. Этот вид работы относится к режиму повышенной производительности. Такая схема используется для организации работ на крупных вычислительных центрах, оснащенных несколькими ЭВМ высокой производительности.
Основные отличия ММС разных модификаций заключаются, как правило, в организации связи и обмена информацией между ЭВМ комплекса. Каждая из них сохраняет возможность автономной работы и управляется собственной ОС. Любая другая подключаемая ЭВМ комплекса рассматривается как специальное периферийное оборудование. В зависимости от территориальной разобщенности ЭВМ и используемых средств сопряжения обеспечивается различная оперативность их информационного воздействия.
ВОПРОС 35
Коммутационные (соединительные) сети в вычислительной технике стали использоваться сравнительно недавно - вместе с появлением параллельных ЭВМ. Помимо соединений процессор - память, сети коммутации применяются для соединений процессор - процессор. В общем случае сеть имеет М входов и L выходов и состоит из групп коммутационных элементов и линий связи между ними. Соединительные возможности сетей могут быть разными: в одной сети они ограничиваются несколькими вариантами коммутации входов с выходами, в других - представляют произвольные варианты соединений для передачи данных.
При малом числе соединяемых устройств коммутация (соединение) не представляет больших трудностей и может быть обеспечена различными способами. Однако при большом числе устройств, а их в современных вычислительных системах может быть несколько тысяч, организация необходимых связей между ними представляет серьезную проблему и требует тщательных решений.
В архитектуре параллельных вычислительных систем коммутационным сетям отводится одно из центральных мест. По своей сложности, стоимости и влиянию на основные характеристики параллельных систем они выступают наравне с такими основными компонентами, как устройства памяти и процессоры.
Выделяют три класса устройств, используемых для коммуникации в параллельных системах, которые могут быть применены и для упорядочения данных в параллельной памяти:
1) p-мерные конвейерные соединители;
2) матричные коммутаторы:
3) многоярусные сети (они являются более перспективными для упорядочения данных в параллельной памяти).
1) p-мерные конвейерные соединители.
В конвейерном соединителе p-мерная структура узлов связывается в каждом измерении таким образом, чтобы обеспечивалась последовательная конвейерная передача данных между ними. Продвижение данных происходит, как правило, синхронно. При передаче данных в 1-м измерении от узла i к узлу i+v данные последовательно проходят через все i1 узлов.
Каждый узел конвейерного соединителя должен содержать элементы памяти, обеспечивающие временное хранение данных. В простейшем случае это просто триггер со схемами занесения, в более сложных системах - многорегистровая буферная намять.
Примером одномерного конвейерного соединителя могут служить соединительная сеть мультипроцессора «ZMOB» и «Кембриджское кольцо», а двухмерного—система связи в матрице процессорных элементов вычислительной системы «ILLIAC-IV».
К достоинствам конвейерных соединителей можно отнести их простоту и регулярность, к существенным недостаткам - зависимость времени передачи данных от расстояния между узлами. Так, например, в системе ZMOB это время колеблется от 100 нс до 25.6 мкс. Кроме того, существуют проблемы с обеспечением надежности таких структур, так как сбой в одном узле может привести к искажению множества сообщений.
Рассматривая применимость p-мерных конвейерных структур для упорядочения данных в параллельной памяти, можно отметить, что они достаточно просто позволяют производить необходимые перестановки данных в тех случаях, когда при формировании запоминающей среды используются линейные периодические размещения. Известно, что соответствующие таблицы размещения строятся с использованием линейных сдвигов, которые и составляют основу алгоритмов упорядочения данных. Однако при этом приходится считаться с отмеченной выше зависимостью времени сдвига (упорядочения данных) от величины сдвига. В памяти это приводит к зависимости времени доступа от вида обращения, что нежелательно. Дополнительные трудности возникают, когда число модулей памяти в многоблочной запоминающей среде больше ширины доступа (M>L). В таком случае, приходится решать задачу маскирования «лишних» узлов конвейерного соединителя.
2). Матричные коммутаторы
Матричные коммутаторы (crossbar network) являются одним из наиболее гибких типов соединительных сетей. Обобщенная структура матричного коммутатора, обеспечивающего соединение М на L портов.
Сеть коммутации представляет собой множество связей между двумя наборами узлов, которые называются входами и выходами. Всего между M входами и L выходами существует ML раз личных связей, включая парные связи («один — одному»), связи «один—многим», смешанные связи.
Сеть, осуществляющая ML соединений, называется обобщенной соединительной сетью. Если сеть осуществляет только парные связи, она называется соединительной, в ней возможно M! Соединений. В соединительных сетях любой допустимый набор связей (перестановка) выполняется за один такт и без конфликтов.
Организация матричного коммутатора такова, что при отсутствии конфликтов все необходимые связи обеспечиваются одновременно. Конфликты возникают, когда два или более абонента требуют коммутации одного и того же узла. Понятно, что в каждом узле необходимо разрешать возникающие конфликты. Поэтому узел коммутации может представлять собой достаточно сложную схему.
Одной из разновидностей матричного коммутатора является сеть, называемая «полное соединение» (complete connection). В ней для установления связи каждого из М портов с L портами используются собственные L линий связи. Легко заметить, что число узлов коммутации в этом случае остается прежним.
Так как число узлов коммутации растет пропорционально произведению ML, то стоимость матричных коммутационных сетей при большом количестве портов весьма высока. Однако при малом числе соединяемых блоков они эффективно используются, в частности, и для упорядочения данных в параллельной памяти.
3). Многоярусные коммутационные сети
Когда количество портов, соединяемых коммутационной сетью, исчисляется сотнями или тысячами, использование матричных коммутаторов не представляется возможным из-за их высокой сложности и стоимости. Не эффективными оказываются и конвейерные соединители, обладающие в этом случае весьма низким быстродействием. Решением проблемы является использование многоярусных коммутационных сетей. Многоярусные сети строятся из нескольких ярусов коммутационных элементов (КЭ). КЭ может сам представлять некоторую соединительную сеть, например матричный переключатель. Чаще всего на практике используются простые КЭ с двумя входами и двумя выходами.
Выделяют три основных вида многоярусных сетей: неблокируемые сети, перестраиваемые и блокируемые сети.
Неблокируемые сети.
Если коммутационная сеть находится в состоянии, при котором невозможно найти путь соединения определенного незанятого входного порта с незанятым выходным, то говорят, что эта сеть заблокирована. Неблокируемыми, следовательно, называются такие сети, в которых всегда можно найти путь соединения для свободной пары портов.
Неблокируемые структуры получаются путем введения дополнительных ярусов коммутации. Несмотря на это многоярусные неблокируемые сети часто более экономичны, чем матричные коммутаторы. Так, например, число КЭ в матричном коммутаторе для М = L = 25 (двадцать пять входов соединяются с двадцатью пятью выходами) равно 625, в трехярусной схеме Клоза - 675, но при М = L = 100 для матричного коммутатора число КЭ уже 10000, a в схеме Клоза - 5700.
Перестраиваемые сети.
Близки к неблокируемым. Перестраиваемыми они называются потому, что могут выполнить, все возможные соединения между входными и выходными
портами, перестраивая существующие связи так, как этого требует установление незаблокированного пути для новой заданной пары портов. Структурная схема такой сети, называемой сетью Бенеша.
Неблокируемые и перестраиваемые сети, обеспечивая высокую гибкость и полноту коммутации, остаются все же достаточно сложными по структуре и соответственно требуют сложного управления. Они безусловно могут использоваться для упорядочения данных в параллельной памяти, однако их применение не всегда целесообразно. В большинстве случаев задача упорядочения решается при некотором ограниченном наборе коммутации и не требует выполнения условий неблокируемости. В связи с этим большой интерес представляют блокируемые многоярусные сети.
Блокируемые сети.
Одним из обобщений блокируемых сетей являются Бэнян-сети, которые введены Р. Гоуком и К. Липовским и использовались для построения мультипроцессорной архитектуры. Свое название они получили oт фигового дерева (banyan-tree). Авторы, очевидно, имели в виду определенное топологическое сходство индийской смоковницы и соответствующего графа.
Граф, описывающий структуру Бэнян-сети, содержит три типа вершин: начальные, не имеющие входящих ребер, конечные, не имеющие исходящих ребер, и промежуточные. Последние имеют и входящие, и выходящие ребра. Отметим некоторые топологические особенности Бэнян-сетей. Сеть, в которой каждый путь, от начальной вершины к конечной имеет длину l и для каждой пары <начальная вершина—конечная вершина> этот путь является единственным называется l-уровневой Бэнян-сетью. В такой сети имеется l уровней (ярусов) ребер и l + 1 уровней вершин. В l -уровневых Бэнян-сетях ребра связывают только вершины соседних уровней. Примем, что начальные вершины размещаются на уровне 0, а конечные - на уровне l. В дальнейшем рассматриваются только однородные Бэнян-сети, в которых для всех вершин одного уровня число входящих и число выходящих ребер есть величины постоянные. Структуру однородной Бэнян-сети можно охарактеризовать, если указать число вершин на каждом уровне L0, L1, …,Ll и для вершин каждого уровня число входящих (c) и выходящих (0) ребер. Так как в l-уровневой сети l ярусов ребер, то соответствующее описание всей сети задается l-компонентными векторами с= (с1, с2, ..., сl), о= (o1, o2, ..., ol) и вектором L= (L0, L1, ..., Ll).
Бэнян-сеть называется регулярной, если с1= с2= ...= сl и o1= o2= ...= ol, в противном случае сеть нерегулярна . Важное место в классе Бэнян-сетей занимают прямоугольные сети. Сеть является прямоугольной, если L0= L1= ...= Ll и с = о. Нерегулярные прямоугольные Бэнян-сети называются слабо прямоугольными, регулярные - строго прямоугольными.
Еще одним обобщенным видом блокируемых многоярусных систем являются Дельта-сети.
Строго прямоугольные Бэнян-сети с числом узлов на каждом уровне L = 21, построенные на 2 X 2-матричных переключателях, составляют особый подкласс сетей. Эти сети называются двоичными перестановочными (или просто перестановочными) сетями. К ним можно отнести такие широко известные сети как Омега-сеть, сеть типа двоичный n-Куб, модифицируемый манипулятор данных, базисная сеть.
Обобщенная двоичная перестановочная сеть может быть представлена log2L = l ярусами коммутационных элементов, соединенных между собой по определенному закону. Сеть, рассматриваемая как однонаправленная, осуществляет передачу данных от входа к выходу. Каждый ярус сети может быть представлен как два устройства, выполняющих последовательно две перестановки (рис. 6). Одна из них - статическая (St) осуществляется за счет того, что линии связи между ярусами могут изменять позицию при входе в следующий ярус. Статическая перестановка определяется выбранным законом межярусных соединений, она зафиксирована для конкретного вида сети. Вторая, динамическая перестановка (Di), осуществляется коммутационными элементами, и ее содержание определяется выбранным способом управления сетью, а также видом КЭ.
В двоичных перестановочных сетях в качестве КЭ используются 2 Х 2-переключатели двух типов. Модель КЭ первого типа составлена из двух мультиплексоров 2 X 1, управляемых независимо. Такой КЭ может находиться в четырех различных состояниях, определяемых управляющим сигналами c1, c0. Коммутационные элементы второго типа имеют только два состояния включения и управляются единственным управляющим сигналом с. Мы рассматриваем двоичные перестановочные сети как устройства упорядочения данных в параллельной памяти.
Динамическая перестановка полностью определяется состоянием управляющих сигналов, подаваемых на коммутационные элементы соответствующих ярусов, и, следовательно, при одинаковом управлении динамические перестановки в разных l-ярусных двоичных перестановочных сетях совпадают. Общие перестановки, выполняемые этими сетями, различаются только вследствие разных межярусных соединений, т. е. разных статических перестановок.
Рассмотрим и сравним между собой несколько конструкций сетей.
Рассмотрим двумерный коммутатор. Каждый процессорный элемент (ПЭ) соединен двусторонними связями с четырьмя соседними (справа, слева, снизу, сверху). Внешние связи МОГУТ в зависимости от решаемой задачи программно замыкаться по-разному: вытягиваться в цепочку , замыкаться в виде вертикально и горизонтально расположенных цилиндров, в виде тороида. Коммутационный элемент (КЭ) здесь обычно соединен с оборудованием ПЭ, и объем оборудования всего коммутатора растет пропорционально числу процессоров M.
Быстродействие любого коммутатора во многом определяется максимальным расстоянием D, под которым понимается число промежуточных узлов или тактов передачи информации между самыми удаленными процессорами.
Под кубическим коммутатором понимается пространственная трехмерная структура, где каждый процессор соединен с шестью соседними: четырьмя в своей плоскости и двумя в прилегающих плоскостях.
В общем случае все среды можно назвать n-мерными кубами, тогда кольцевой коммутатор имеет размерность п=1, а матрица - п=2 и т. д. Большое распространение в параллельной вычислительной технике получили среды с размерностями 2 и 3. Чем больше п при неизменном числе процессоров, тем больше радиус связей и тем меньше D. Под радиусом связи понимается число процессоров, напрямую связанных с данным ПЭ.
Величина п может быть и больше трех. Покажем общий прием построения n-кубов произвольной размерности.
Для примера рассмотрим возможные связи элемента 9 матрицы, изображенной на рис. 11, а. Этот элемент в своей строке связан с элементами 8 и 10, адреса которых отличаются на -1 и +1. Если бы данная строка составляла независимый коммутатор с размерностью 4 (n=1, M=4), то связи любого ПЭi такого коммутатора описывались бы рангом 1. Если элемент 9 находится в матрице, то его связи с элементом 5 верхней строки и элементом 13 нижней строки отличаются на +M и -M, где M=4 - размер строки. Следовательно, связи элемента ПЭi матричного коммутатора описываются рангом 2.
Если бы элемент 9 находился в кубе, то номера смежных элементов соседних плоскостей отличались бы на ±M2, в кубе степени 4 - на ±M3 и т. д. Такая методика позволяет построить куб любой степени и вычислить величину D.
Многокаскадные коммутаторы помогают создать более дешевые варианты соединительных и обобщенных соединительных сетей. Координатный переключатель NXN можно свести к двум (N/2XN/2) переключателям с замещением . В свою очередь переключатели N/2XN/2 могут быть разложены на более мелкие подобным же образом. Пример сети, приведенной до уровня стандартных 1<Э размерностью 2х2, дан на рис. 13, б. По определению, это полная соединительная сеть (сеть Бенеша), обеспечивающая N! возможных перестановок, каждая из которых выполняется за один такт работы сети. В такой сети отсутствуют конфликты для любых парных соединений.
Стандартный КЭ размерностью 2Х2 и возможные в нем соединения. Иногда для построения больших сетей применяются элементы 4Х4 или 8Х8. Основной недостаток сети Бенеша - большое количество элементов, необходимых для ее построения.
Широко используются неполные соединительные сети: омега-сеть, сеть Бенеша, R-сеть и др. Омега-сеть относится к типу сетей тасовки с замещением.
Коммутационные сети могут работать в двух режимах: коммутация каналов и коммутация сообщений. В первом случае сначала с помощью адресной системы устанавливается прямой электрический тракт между парой соединяемых точек, а затем по этому тракту передастся информация. Такой вид связи используется, например, в телефонных сетях. Во втором случае каждая передаваемая единица информации снабжается адресом требуемого выхода и перемещается от узла ni, к узлу ni+1, где i - номер каскада; п и т - номера коммутационных узлов в каскадах. После того как информация принята узлом mi+1, линия, соединявшая ni и mi+1, становится доступной для других соединении. Узел mi+1 по адресной части сообщения определяет дальнейший маршрут сообщения. В матрицах процессоров используется как коммутация каналов, так и коммутация сообщений.