С. Н. Ан

• Название: С. Н. Ан
• Дата: 28.08.2021
• Размер: 217.92 Kb.
• Имя файла: question39.docx
• Тип: Документы; #228178
• страница: 11 из 13

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

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

Приведем примеры топологий, которые применяются в параллельных вычислительных

_{системах. Распространенной является хорошо масштабируемая топология "гиперкуб":}

_{2-мерный гиперкуб}

3-мерный гиперкуб

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

Другим примером топологии является двумерная решетка. Это обычная квадратная

решетка с граничными соединениями разного рода:

Плоская решетка

Более сложный тип коммуникации дается многоступенчатыми соединениями. В этом случае на одном конце соединения находятся процессоры, а на другом процессоры или другие узлы. В середине располагаются переключатели. При передаче данных от узла к узлу переключатели устанавливаются таким образом, чтобы обеспечить требуемое соединение. Очевидно, для этого требуется некоторое время - "время установки". Примерами многоступенчатых соединений являются соединения "бабочка" и "омега". Эти соединения формируются из переключателей, имеющих 2 входа и 2 выхода. Входы и выходы коммутируются.

Количество переключателей, необходимое для нормальной работы сети с n входами и n

выходами O(n log2n).

^{Соединение "бабочка"} _{Перекрестное соединение}

Более устойчивую и эффективную работу обеспечивает перекрестное соединение. Переключатели динамически конфигурируются так, чтобы обеспечить требуемое соединение. Масштабируемость такого соединения не очень хорошая, так как добавление нового узла требует включения дополнительно 2n-1 переключателей.

Важнейшими атрибутами системы коммуникаций являются стратегии управления, переключения и синхронизации. Что касается управления, то здесь можно выделить две альтернативы: централизованное управление единым контроллером (модулем управления) и распределенное управление. Примерами распределенного управления являются работа многоступенчатых соединений, где каждый узел принимает решение, как поступить с поступившим сообщением - оставить его себе или передать соседу. Другой вариант используется, например, в соединениях типа "звезда", где каждое сообщение пересылается в контроллер, который определяет его дальнейшую судьбу.

Синхронизация тоже может быть глобальной, когда синхронизующая последовательность импульсов передается всем узлам вычислительной системы, но может быть и локальной, когда каждый узел имеет свой собственный генератор. Последний вариант называется асинхронной работой. Преимущество глобальной синхронизации, характерной для SIMD машин заключается в более простой аппаратной и программной реализации, а асинхронные системы, чаще всего это MIMD-компьютеры - более гибкие.

Стратегии переключения тоже бывают двух видов. Во-первых, это пакетное переключение, когда сообщение разбивается на более мелкие пакеты, пересылаемые по сети. Преодолев очередное соединение, пакет попадает на очередной узел, который определяет, куда этот пакет должен быть отправлен и должен ли он быть отправлен вообще. В конце концов пакеты должны прибыть на узел-адресат, причем пути их могут быть разными. На последнем узле пакеты собираются и восстанавливается переданное сообщение. Во-вторых, возможно цепное переключение, когда между отправителем и адресатом создается магистраль, по которой и передается сообщение целиком.