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

1. Блокирующие и неблокирующие многоуровневые сети

 

Минимальным требованием  к сети с коммутацией является поддержка соединения любого входа с любым выходом. Для этого в сети с n входами и n выходами система ключей обязана предоставить n \ вариантов коммутации входов и выходов (перестановок - permutations). Проблема усложняется, когда сеть должна обеспечивать одновременную передачу данных между многими парами терминальных узлов (multicast), причем так, чтобы не возникали конфликты (блокировки) из-за передачи данных через одни и те же коммутирующие элементы в одно и то же время. Подобные топологии должны поддерживать n" перестановок. С этих позиций все топологии CMC с коммутацией разделяются на три типа: неблокирующие, неблокирующие с реконфигурацией и блокирующие.

В неблокирующих сетях  обеспечивается соединение между любыми парами входных и выходных терминалов без перенастройки коммутирующих  элементов сети, В рамках этой группы различают сети строго неблокирующие (strictly non-blocking) и неблокирующие в широком смысле (wide sense non-blocking), В строго неблокирующих сетях возникновение блокировок принципиально невозможно в силу примененной топологии. К таким относятся матричная сеть и сеть Клоша. Неблокирующими в широком смысле называют топологии, в которых конфликты при любых соединениях не возникают только при соблюдении определенного алгоритма маршрутизации.

В неблокирующих сетях  с реконфигурацией также возможна реализация соединения между произвольными входными и выходными терминалами, но для этого необходимо изменить настройку коммутаторов сети и маршрут связи между соединенными терминалами. Примерами таких сетей служат сети Бенеша, Бэтчера, «Мемфис» и др.

В блокирующих сетях, если какое-либо соединение уже установлено, это может стать причиной невозможности  установления других соединений. К блокирующим относятся сети «Баньяна, «Омега», n-куб и др.

 

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

 

Архитектура с командными словами сверхбольшой длины или со сверхдлинными командами (VLIW, Very Long Instruction Word) известна с начала 80-х годов. VLIW – это набор команд, организованных наподобие горизонтальной микрокоманды в микропрограммном устройстве управления.

Идея VLIW базируется на том, что задача эффективного планирования параллельного выполнения нескольких команд возлагается на «разумный» компилятор. Такой компилятор вначале исследует исходную программу с целью обнаружить все команды, которые могут быть выполнены одновременно без возникновения конфликтов. В процессе анализа компилятор может даже частично имитировать выполнение рассматриваемой программы. На следующем этапе компилятор пытается объединить такие команды в пакеты, каждый из которых рассматривается как одна сверхдлинная команда. Объединение нескольких простых команд в одну сверхдлинную производится по следующим правилам:

• количество простых команд, объединяемых в одну команду сверхбольшой длины, равно числу имеющихся в процессоре функциональных (исполнительных) блоков (ФБ);
• в сверхдлинную команду входят только такие простые команды, которые исполняются разными ФБ, т.е. обеспечивается одновременное исполнение всех составляющих сверхдлинной команды.

Длина сверхдлинной команды обычно составляет от 256 до 1024 бит. Такая метакоманда содержит несколько полей (по числу образующих ее простых команд), каждое из которых описывает операцию для конкретного функционального блока. На рис. 1 показан возможный формат сверхдлинной команды и взаимосвязь между ее полями и ФБ, реализующими отдельные операции.

Каждое поле сверхдлинной команды отображается на свой функциональный блок, что позволяет получить максимальную отдачу от аппаратуры блока исполнения команд.

VLIW-архитектуру можно рассматривать как статическую суперскалярную архитектуру. Распараллеливание кода производится на этапе компиляции, а не динамически во время исполнения. То, что в выполняемой сверхдлинной команде исключена возможность конфликтов, позволяет предельно упростить аппаратуру VLIW-процессора и добиться более высокого быстродействия.

В качестве простых команд, образующих сверхдлинную, обычно используются команды RISC-типа, поэтому архитектуру VLIW иногда называют пост-RISC-архитектурой. Максимальное число полей в сверхдлинной команде равно числу вычислительных устройств и обычно колеблется в диапазоне от 3 до 20. Все вычислительные устройства имеют доступ к данным, хранящимся в едином многопортовом регистровом файле. Отсутствие сложных аппаратных механизмов, характерных для суперскалярных процессоров (предсказание переходов, внеочередное исполнение и т.д.) дает значительный выигрыш в быстродействии и возможность более эффективно использовать площадь кристалла. Подавляющее большинство цифровых сигнальных процессоров и мультимедийных процессоров с производительностью более 1 млрд операций/с базируется на VLIW-архитектуре. Серьезная проблема VLIW – усложнение регистрового файла и связей этого файла с вычислительными устройствами.

Рис. 1. Формат сверхдлинной команды и взаимосвязь полей команды с составляющими блока исполнения

 

 

3. Структура пакета данных и пакета подтверждения, передаваемых в транспьютерных ВС

 

Передача информации производится синхронно под воздействием либо общего генератора тактовых импульсов (ГТИ), либо локальных ГТИ с одинаковой частотой следования импульсов. Информация передается в виде пакетов. Каждый раз, когда пересылается пакет данных, приемник отвечает пакетом подтверждения (рис. 2).

Рис. 2. Организация ввода/вывода в транспьютерной системе

 

Пакет данных состоит из двух битов-единиц, за которыми следуют 8-битовые данные и ноль (всего 11 бит). Пакет подтверждения - это простая  комбинация 10 (всего два бита), она  может быть передана, как только пакет данных будет идентифицирован интерфейсом входного канала. Каналы обеспечивают аппаратную поддержку операторов ввода и вывода языка Occam и функционируют словно каналы ПДП, то есть пакеты могут пересылаться один за другим как векторы. Для коммуникаций между процессами внутри транспьютера вместо внешних каналов операторы ввода/вывода используют внутренние каналы транспьютера.

Интерфейс событий дает возможность  внешнему устройству привлечь внимание и получить подтверждение. Этот интерфейс функционирует как входной канал и аналогично программируется.

 

4. Схема классификации параллелизма  
по уровню и гранулярности.

 

Методы и средства реализации параллелизма зависят от того, на каком уровне он должен обеспечиваться. Обычно различают следующие уровни параллелизма:

• Уровень заданий. Несколько независимых заданий одновременно выполняются на разных процессорах, практически не взаимодействуя друг с другом. Этот уровень реализуется на ВС с множеством процессоров в многозадачном режиме.
• Уровень программ. Части одной задач» выполняются на множестве процессоров. Данный уровень достигается на параллельных ВС.
• Уровень команд. Выполнение команды разделяется на фазы, а фазы нескольких последовательных команд могут быть перекрыты за счет конвейеризации. Уровень достижим на ВС с одним процессором.
• Уровень битов (арифметический уровень). Биты слова обрабатываются один за другим, это называется бит-последовательной операцией. Если биты снова обрабатываются одновременно, говорят о бит-параллельной  операции. Данный уровень реализуется в обычных и суперскалярпых процессорах.

К понятию уровня параллелизма тесно примыкает понятие гранулярности. Эта мера отношения объема вычислений, выполненных в параллельной задаче, к объему коммуникаций (для обмена сообщениями). Степень гранулярности  варьируется от мелкозернистой да крупнозернистой. Определим понятия крупнозернистого (coarse grained), среднезернистого (medium grained) и мелкозернистого (fine grained) параллелизма.

Крупнозернистый параллелизм: каждое параллельное вычисление достаточно независимо от остальных, причем требуется  относительно редкий обмен информацией  между отдельными вычислениями. Единицами  распараллеливания являются большие  и независимые программы, включающие тысячи команд. Этот уровень параллелизма обеспечивается операционной системой,

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

Мелкозернистый параллелизм: каждое параллельное вычисление достаточно мало и элементарно, составляется из десятков команд. Обычно распараллеливаемыми  единицами являются элементы выражения  или отдельные итерации цикла, имеющие небольшие зависимости по данным. Сам термин «мелкозернистый параллелизм» говорит о простоте и быстроте любого вычислительного действия. Характерная особенность мелкозернистого параллелизма заключаете; в приблизительном равенстве интенсивности вычислений и обмена данными. Этот уровень параллелизма часто используется распараллеливающим (векторизирующим) компилятором.

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