Архитектура параллельного компьютера - Краткое руководство
За последние 50 лет произошли огромные изменения в производительности и возможностях компьютерных систем. Это стало возможным с помощью технологии очень крупномасштабной интеграции (СБИС). Технология VLSI позволяет разместить большое количество компонентов на одном кристалле и увеличить тактовую частоту. Следовательно, одновременно может выполняться больше операций, параллельно.
Параллельная обработка также связана с локализацией данных и передачей данных. Parallel Computer Architecture - это метод организации всех ресурсов для максимизации производительности и программируемости в пределах, установленных технологией и стоимостью в любой момент времени.
Почему параллельная архитектура?
Параллельная компьютерная архитектура добавляет новое измерение в развитие компьютерных систем за счет использования все большего количества процессоров. В принципе, производительность, достигаемая за счет использования большого количества процессоров, выше, чем производительность одного процессора в данный момент времени.
Тенденции применения
С развитием аппаратных возможностей увеличился и спрос на хорошо работающие приложения, что, в свою очередь, потребовало разработки компьютерной архитектуры.
До эры микропроцессоров высокопроизводительная компьютерная система была получена за счет экзотических схемотехники и машинной организации, что сделало их дорогими. Теперь высокопроизводительная компьютерная система получается за счет использования нескольких процессоров, а наиболее важные и требовательные приложения написаны как параллельные программы. Таким образом, для повышения производительности необходимо разрабатывать как параллельные архитектуры, так и параллельные приложения.
Чтобы повысить производительность приложения, необходимо учитывать ускорение. Speedup на процессорах p определяется как -
$$Speedup(p \ processors)\equiv\frac{Performance(p \ processors)}{Performance(1 \ processor)}$$Для единственной фиксированной проблемы
$$performance \ of \ a \ computer \ system = \frac{1}{Time \ needed \ to \ complete \ the \ problem}$$ $$Speedup \ _{fixed \ problem} (p \ processors) =\frac{Time(1 \ processor)}{Time(p \ processor)}$$Научные и инженерные вычисления
Параллельная архитектура стала незаменимой в научных вычислениях (например, физика, химия, биология, астрономия и т. Д.) И инженерных приложениях (таких как моделирование резервуаров, анализ воздушного потока, эффективность сгорания и т. Д.). Практически во всех приложениях существует огромный спрос на визуализацию результатов вычислений, что приводит к необходимости разработки параллельных вычислений для увеличения скорости вычислений.
Коммерческие вычисления
В коммерческих вычислениях (таких как видео, графика, базы данных, OLTP и т. Д.) Также необходимы высокоскоростные компьютеры для обработки огромного количества данных в течение определенного времени. Desktop использует многопоточные программы, которые почти похожи на параллельные программы. Это, в свою очередь, требует разработки параллельной архитектуры.
Технологические тенденции
С развитием технологий и архитектуры появляется большой спрос на разработку высокопроизводительных приложений. Эксперименты показывают, что параллельные компьютеры могут работать намного быстрее, чем максимально развитый одиночный процессор. Более того, параллельные компьютеры могут быть разработаны в рамках технологии и стоимости.
Основная используемая здесь технология - это технология СБИС. Таким образом, в настоящее время все больше и больше транзисторов, затворов и схем могут быть установлены в одной и той же области. С уменьшением размера базовой СБИС тактовая частота также увеличивается пропорционально ей, а количество транзисторов растет пропорционально квадрату. Можно ожидать, что использование нескольких транзисторов одновременно (параллелизм) будет работать намного лучше, чем при увеличении тактовой частоты.
Технологические тенденции предполагают, что базовый единичный строительный блок будет обеспечивать все более большую емкость. Следовательно, увеличивается возможность размещения нескольких процессоров на одном кристалле.
Архитектурные тенденции
Развитие технологий решает, что выполнимо; Архитектура преобразует потенциал технологии в производительность и возможности.Parallelism и localityЭто два метода, в которых большие объемы ресурсов и большее количество транзисторов повышают производительность. Однако эти два метода конкурируют за одни и те же ресурсы. Когда несколько операций выполняются параллельно, количество циклов, необходимых для выполнения программы, уменьшается.
Однако необходимы ресурсы для поддержки каждой из параллельных операций. Ресурсы также необходимы для выделения локального хранилища. Наилучшая производительность достигается за счет промежуточного плана действий, в котором ресурсы используются для использования определенной степени параллелизма и степени локальности.
Как правило, история компьютерной архитектуры была разделена на четыре поколения, имеющих следующие основные технологии:
- Вакуумные трубки
- Transistors
- Интегральные схемы
- VLSI
До 1985 г. в продолжительности доминировал рост параллелизма на уровне битов. 4-битные микропроцессоры, за которыми следуют 8-битные, 16-битные и так далее. Чтобы уменьшить количество циклов, необходимых для выполнения полной 32-битной операции, ширина пути данных была увеличена вдвое. Позже были введены 64-битные операции.
Рост в instruction-level-parallelismдоминировала с середины 80-х до середины 90-х годов. Подход RISC показал, что этапы обработки инструкций были простыми, так что в среднем инструкция выполнялась почти в каждом цикле. Развитие технологий компиляторов сделало конвейеры команд более производительными.
В середине 80-х микропроцессорные компьютеры состояли из
- Целочисленный блок обработки
- Блок с плавающей запятой
- Контроллер кеша
- SRAM для данных кэша
- Хранение тегов
По мере увеличения емкости микросхемы все эти компоненты были объединены в одну микросхему. Таким образом, одна микросхема состояла из отдельного оборудования для целочисленной арифметики, операций с плавающей запятой, операций с памятью и операций ветвления. Помимо конвейерной обработки отдельных инструкций, он извлекает несколько инструкций за раз и по возможности отправляет их параллельно различным функциональным блокам. Этот тип параллелизма на уровне команд называетсяsuperscalar execution.
Параллельные машины были разработаны с несколькими отличными архитектурами. В этом разделе мы обсудим различные параллельные компьютерные архитектуры и природу их конвергенции.
Коммуникационная Архитектура
Параллельная архитектура дополняет традиционные концепции компьютерной архитектуры архитектурой связи. Компьютерная архитектура определяет критические абстракции (такие как граница между пользователем и системой и граница аппаратно-программного обеспечения) и организационную структуру, тогда как архитектура связи определяет основные операции связи и синхронизации. Это также касается организационной структуры.
Модель программирования - это верхний уровень. Приложения написаны в программной модели. Модели параллельного программирования включают -
- Общее адресное пространство
- Передача сообщений
- Параллельное программирование данных
Shared addressпрограммирование похоже на использование доски объявлений, где можно общаться с одним или несколькими людьми, размещая информацию в определенном месте, которая является общей для всех остальных людей. Индивидуальная деятельность координируется, отмечая, кто какую задачу выполняет.
Message passing это как телефонный звонок или письма, когда конкретный получатель получает информацию от определенного отправителя.
Data parallelпрограммирование - это организованная форма сотрудничества. Здесь несколько человек одновременно выполняют действия с отдельными элементами набора данных и обмениваются информацией во всем мире.
Общая память
Мультипроцессоры с общей памятью - один из самых важных классов параллельных машин. Он обеспечивает лучшую пропускную способность при многопрограммных рабочих нагрузках и поддерживает параллельные программы.
В этом случае все компьютерные системы позволяют процессору и набору контроллера ввода-вывода получать доступ к набору модулей памяти посредством некоторого аппаратного взаимодействия. Емкость памяти увеличивается за счет добавления модулей памяти, а емкость ввода-вывода увеличивается за счет добавления устройств к контроллеру ввода-вывода или путем добавления дополнительного контроллера ввода-вывода. Производительность обработки можно увеличить, дождавшись появления более быстрого процессора или добавив больше процессоров.
Все ресурсы организованы вокруг центральной шины памяти. Через механизм доступа к шине любой процессор может получить доступ к любому физическому адресу в системе. Поскольку все процессоры равноудалены от всех ячеек памяти, время доступа или задержка для всех процессоров одинаковы для каждой ячейки памяти. Это называетсяsymmetric multiprocessor.
Архитектура передачи сообщений
Архитектура передачи сообщений также является важным классом параллельных машин. Он обеспечивает связь между процессорами в виде явных операций ввода-вывода. В этом случае обмен данными осуществляется на уровне ввода-вывода, а не на уровне системы памяти.
В архитектуре передачи сообщений взаимодействие пользователя выполняется с использованием вызовов операционной системы или библиотеки, которые выполняют множество действий нижнего уровня, включая фактическую операцию связи. В результате существует дистанция между моделью программирования и операциями связи на физическом уровне оборудования.
Send и receiveявляется наиболее распространенной операцией связи на уровне пользователя в системе передачи сообщений. Send определяет локальный буфер данных (который должен быть передан) и принимающий удаленный процессор. Прием определяет процесс отправки и локальный буфер данных, в который будут помещены передаваемые данные. В операции отправкиidentifier или tag прикрепляется к сообщению, и операция получения определяет правило сопоставления, например, конкретный тег от определенного процессора или любой тег от любого процессора.
Комбинация отправки и соответствующего приема завершает копирование из памяти в память. Каждая сторона указывает свой локальный адрес данных и событие парной синхронизации.
Конвергенция
Развитие аппаратного и программного обеспечения стерло четкую границу между общей памятью и лагерями передачи сообщений. Передача сообщений и общее адресное пространство представляют две разные модели программирования; каждый дает прозрачную парадигму для совместного использования, синхронизации и общения. Тем не менее, основные машинные структуры сошлись к общей организации.
Параллельная обработка данных
Другой важный класс параллельных машин называется по-разному - массивы процессоров, параллельная архитектура данных и машины с одной инструкцией и множеством данных. Основная особенность модели программирования заключается в том, что операции могут выполняться параллельно с каждым элементом большой регулярной структуры данных (например, массива или матрицы).
Языки параллельного программирования данных обычно применяются путем просмотра локального адресного пространства группы процессов, по одному на процессор, образуя явное глобальное пространство. Поскольку все процессоры взаимодействуют друг с другом и существует глобальное представление всех операций, можно использовать либо общее адресное пространство, либо передачу сообщений.
Основные проблемы проектирования
Только разработка модели программирования не может повысить эффективность компьютера, и не может сделать это только разработка аппаратного обеспечения. Однако развитие компьютерной архитектуры может повлиять на производительность компьютера. Мы можем понять проблему дизайна, сосредоточившись на том, как программы используют машину и какие базовые технологии предоставляются.
В этом разделе мы обсудим абстракцию коммуникации и основные требования модели программирования.
Коммуникационная абстракция
Коммуникационная абстракция - это главный интерфейс между моделью программирования и реализацией системы. Это похоже на набор инструкций, который обеспечивает платформу, чтобы одна и та же программа могла правильно работать во многих реализациях. Операции на этом уровне должны быть простыми.
Коммуникационная абстракция подобна контракту между аппаратным и программным обеспечением, который позволяет друг другу повышать гибкость, не влияя на работу.
Требования к модели программирования
В параллельной программе есть один или несколько потоков, работающих с данными. Модель параллельного программирования определяет, какие данные потоки могутname, который operations могут выполняться с указанными данными, и в каком порядке выполняются операции.
Чтобы убедиться в том, что зависимости между программами применяются, параллельная программа должна координировать деятельность своих потоков.
Параллельная обработка данных была разработана как эффективная технология в современных компьютерах, чтобы удовлетворить потребность в более высокой производительности, более низкой стоимости и точных результатах в реальных приложениях. Параллельные события являются обычным явлением на современных компьютерах из-за практики мультипрограммирования, многопроцессорности или многопроцессорности.
Современные компьютеры имеют мощные и обширные программные пакеты. Чтобы проанализировать развитие производительности компьютеров, сначала мы должны понять основы развития аппаратного и программного обеспечения.
Computer Development Milestones - Существует два основных этапа развития компьютера - mechanical или же electromechanicalчасти. Современные компьютеры эволюционировали после появления электронных компонентов. Электроны с высокой подвижностью в электронных компьютерах заменили рабочие части в механических компьютерах. Для передачи информации электрический сигнал, который движется почти со скоростью света, заменяет механические шестерни или рычаги.
Elements of Modern computers - Современная компьютерная система состоит из компьютерного оборудования, наборов инструкций, прикладных программ, системного программного обеспечения и пользовательского интерфейса.
Вычислительные проблемы подразделяются на числовые вычисления, логические рассуждения и обработку транзакций. Для решения некоторых сложных задач может потребоваться сочетание всех трех режимов обработки.
Evolution of Computer Architecture- За последние четыре десятилетия компьютерная архитектура претерпела революционные изменения. Мы начали с архитектуры фон Неймана, а теперь у нас есть мультикомпьютеры и мультипроцессоры.
Performance of a computer system- Производительность компьютерной системы зависит как от возможностей машины, так и от поведения программы. Возможности машины можно улучшить с помощью более совершенных аппаратных технологий, расширенных архитектурных функций и эффективного управления ресурсами. Поведение программы непредсказуемо, поскольку зависит от приложения и условий выполнения.
Мультипроцессоры и мультикомпьютеры
В этом разделе мы обсудим два типа параллельных компьютеров:
- Multiprocessors
- Multicomputers
Мультикомпьютеры с общей памятью
Три наиболее распространенные модели мультипроцессоров с общей памятью:
Унифицированный доступ к памяти (UMA)
В этой модели все процессоры равномерно распределяют физическую память. Все процессоры имеют одинаковое время доступа ко всем словам памяти. Каждый процессор может иметь частную кэш-память. То же правило применяется для периферийных устройств.
Когда все процессоры имеют равный доступ ко всем периферийным устройствам, система называется symmetric multiprocessor. Когда только один или несколько процессоров могут получить доступ к периферийным устройствам, система называетсяasymmetric multiprocessor.
Неравномерный доступ к памяти (NUMA)
В многопроцессорной модели NUMA время доступа зависит от местоположения слова памяти. Здесь общая память физически распределяется между всеми процессорами и называется локальной памятью. Совокупность всех локальных запоминающих устройств образует глобальное адресное пространство, доступное для всех процессоров.
Архитектура только кэш-памяти (COMA)
Модель COMA - это частный случай модели NUMA. Здесь вся распределенная основная память преобразуется в кэш-память.
Distributed - Memory Multicomputers- Мультикомпьютерная система с распределенной памятью состоит из нескольких компьютеров, известных как узлы, связанных между собой сетью передачи сообщений. Каждый узел действует как автономный компьютер, имеющий процессор, локальную память и иногда устройства ввода-вывода. В этом случае вся локальная память является частной и доступна только для локальных процессоров. Вот почему традиционные машины называютсяno-remote-memory-access (NORMA) машины.
Мультивекторные и SIMD-компьютеры
В этом разделе мы обсудим суперкомпьютеры и параллельные процессоры для векторной обработки и параллелизма данных.
Вектор суперкомпьютеры
В векторном компьютере векторный процессор присоединяется к скалярному процессору как дополнительная функция. Главный компьютер сначала загружает программу и данные в основную память. Затем скалярный блок управления декодирует все инструкции. Если декодированные инструкции являются скалярными операциями или операциями программы, скалярный процессор выполняет эти операции, используя скалярные функциональные конвейеры.
С другой стороны, если декодированные инструкции являются векторными операциями, то инструкции будут отправлены в блок векторного управления.
SIMD суперкомпьютеры
В компьютерах SIMD к блоку управления подключено N процессоров, и все процессоры имеют свои индивидуальные блоки памяти. Все процессоры связаны сетью межсетевого взаимодействия.
Модели PRAM и VLSI
Идеальная модель дает подходящую основу для разработки параллельных алгоритмов без учета физических ограничений или деталей реализации.
Модели могут быть применены для получения теоретических пределов производительности на параллельных компьютерах или для оценки сложности СБИС по площади кристалла и времени работы до того, как кристалл будет изготовлен.
Параллельные машины с произвольным доступом
Шепердсон и Стерджис (1963) смоделировали обычные однопроцессорные компьютеры как машины с произвольным доступом (RAM). Fortune и Wyllie (1978) разработали модель параллельной машины с произвольным доступом (PRAM) для моделирования идеализированного параллельного компьютера с нулевыми накладными расходами на доступ к памяти и синхронизацией.
PRAM с N-процессором имеет общий блок памяти. Эта разделяемая память может быть централизованной или распределенной между процессорами. Эти процессоры работают в синхронизированном цикле чтения-памяти, записи-памяти и вычислительного цикла. Таким образом, эти модели определяют, как обрабатываются одновременные операции чтения и записи.
Ниже приведены возможные операции обновления памяти -
Exclusive read (ER) - В этом методе в каждом цикле только одному процессору разрешено читать из любой области памяти.
Exclusive write (EW) - В этом методе по крайней мере одному процессору разрешено записывать в ячейку памяти за раз.
Concurrent read (CR) - Это позволяет нескольким процессорам считывать одну и ту же информацию из одной и той же области памяти в одном цикле.
Concurrent write (CW)- Это позволяет одновременные операции записи в одну и ту же ячейку памяти. Чтобы избежать конфликта записи, настроены некоторые политики.
Модель сложности СБИС
Параллельные компьютеры используют микросхемы VLSI для изготовления массивов процессоров, массивов памяти и крупномасштабных коммутационных сетей.
В настоящее время технологии СБИС являются двумерными. Размер микросхемы СБИС пропорционален объему дискового пространства (памяти), доступного в этой микросхеме.
Мы можем вычислить пространственную сложность алгоритма по площади микросхемы (A) реализации этого алгоритма микросхемы СБИС. Если T - время (задержка), необходимое для выполнения алгоритма, то AT дает верхнюю границу общего числа битов, обработанных через чип (или ввод / вывод). Для некоторых вычислений существует нижняя граница f (s) такая, что
В 2 > = O (f (s))
Где A = площадь чипа и T = время
Пути архитектурного развития
Эволюцию параллельных компьютеров я распространил по следующим направлениям -
- Несколько дорожек процессора
- Многопроцессорный трек
- Мультикомпьютерный трек
- Множественная дорожка данных
- Векторный трек
- SIMD трек
- Отслеживание нескольких потоков
- Многопоточный трек
- Дорожка потока данных
В multiple processor trackпредполагается, что разные потоки выполняются одновременно на разных процессорах и обмениваются данными через общую память (многопроцессорный трек) или систему передачи сообщений (мультикомпьютерный трек).
В multiple data trackпредполагается, что один и тот же код выполняется на большом количестве данных. Это выполняется путем выполнения одинаковых инструкций для последовательности элементов данных (векторная дорожка) или посредством выполнения той же последовательности инструкций для аналогичного набора данных (дорожка SIMD).
В multiple threads trackпредполагается, что чередование выполнения различных потоков на одном процессоре, чтобы скрыть задержки синхронизации между потоками, выполняющимися на разных процессорах. Чередование потоков может быть грубым (многопоточная дорожка) или точным (дорожка потока данных).
В 80-х годах для создания мультикомпьютеров был популярен специальный процессор под названием Transputer. Транспьютер состоял из одного базового процессора, небольшой памяти SRAM, интерфейса основной памяти DRAM и четырех каналов связи, все на одном кристалле. Чтобы сделать параллельную компьютерную связь, каналы были соединены, чтобы сформировать сеть Transputers. Но ему не хватает вычислительной мощности, и поэтому он не может удовлетворить растущий спрос на параллельные приложения. Эта проблема была решена разработкой RISC-процессоров, к тому же это было дешево.
Современный параллельный компьютер использует микропроцессоры, которые используют параллелизм на нескольких уровнях, таких как параллелизм на уровне команд и параллелизм на уровне данных.
Высокопроизводительные процессоры
На сегодняшнем рынке параллельных компьютеров доминируют процессоры RISC и RISCy.
Характеристики традиционного RISC:
- Имеет несколько режимов адресации.
- Имеет фиксированный формат для инструкций, обычно 32- или 64-битный.
- Имеет специальные инструкции загрузки / сохранения для загрузки данных из памяти в регистр и сохранения данных из регистра в память.
- Арифметические операции всегда выполняются с регистрами.
- Использует конвейерную обработку.
Большинство микропроцессоров в наши дни являются суперскалярными, то есть в параллельном компьютере используются несколько конвейеров команд. Следовательно, суперскалярные процессоры могут выполнять более одной инструкции одновременно. Эффективность суперскалярных процессоров зависит от количества параллелизма на уровне команд (ILP), доступного в приложениях. Чтобы конвейеры оставались заполненными, инструкции на аппаратном уровне выполняются в другом порядке, чем порядок программ.
Многие современные микропроцессоры используют суперконвейерный подход. При супер конвейерной обработке , чтобы увеличить тактовую частоту, работа, выполняемая внутри ступени конвейера, сокращается, а количество ступеней конвейера увеличивается.
Процессоры очень большого командного слова (VLIW)
Они получены из горизонтального микропрограммирования и суперскалярной обработки. Инструкции в процессорах VLIW очень большие. Операции внутри одной инструкции выполняются параллельно и направляются для выполнения в соответствующие функциональные блоки. Итак, после получения инструкции VLIW ее операции декодируются. Затем операции отправляются в функциональные блоки, в которых они выполняются параллельно.
Векторные процессоры
Векторные процессоры являются сопроцессором универсального микропроцессора. Векторные процессоры обычно представляют собой регистр-регистр или память-память. Векторная команда выбирается и декодируется, а затем выполняется определенная операция для каждого элемента векторов операндов, тогда как в обычном процессоре для векторной операции требуется структура цикла в коде. Чтобы сделать его более эффективным, векторные процессоры объединяют несколько векторных операций в цепочку, т. Е. Результат одной векторной операции пересылается другой как операнд.
Кеширование
Кэши - важный элемент высокопроизводительных микропроцессоров. Через каждые 18 месяцев скорость микропроцессоров становится вдвое, но чипы DRAM для основной памяти не могут конкурировать с этой скоростью. Итак, кеши вводятся, чтобы преодолеть разрыв в скорости между процессором и памятью. Кэш - это быстрая и небольшая память SRAM. Многие другие кэши применяются в современных процессорах, таких как кеши буферов просмотра трансляции (TLB), кеши инструкций и данных и т. Д.
Кэш с прямым подключением
В кэшах с прямым отображением функция "по модулю" используется для однозначного сопоставления адресов в основной памяти с ячейками кеша. Поскольку одна и та же запись кэша может иметь несколько отображаемых блоков основной памяти, процессор должен иметь возможность определить, является ли блок данных в кэше тем блоком данных, который действительно необходим. Эта идентификация выполняется путем сохранения тега вместе с блоком кеша.
Полностью ассоциативный кэш
Полностью ассоциативное сопоставление позволяет разместить блок кеша в любом месте кеша. Используя некоторую политику замены, кеш определяет запись кэша, в которой он хранит блок кеша. Полностью ассоциативные кэши имеют гибкое сопоставление, которое сводит к минимуму количество конфликтов записей кэша. Поскольку полностью ассоциативная реализация стоит дорого, они никогда не используются в больших масштабах.
Наборно-ассоциативный кэш
Наборно-ассоциативное отображение - это комбинация прямого отображения и полностью ассоциативного отображения. В этом случае записи кэша подразделяются на наборы кэша. Как и при прямом отображении, существует фиксированное отображение блоков памяти в набор в кэше. Но внутри набора кэша блок памяти отображается полностью ассоциативным образом.
Стратегии кеширования
Помимо механизма отображения, кэшам также нужен ряд стратегий, которые определяют, что должно происходить в случае определенных событий. В случае (набор-) ассоциативных кешей кеш должен определять, какой блок кеша должен быть заменен новым блоком, входящим в кеш.
Некоторые хорошо известные стратегии замены:
- Первый пришел - первый ушел (FIFO)
- Наименее недавно использованные (LRU)
В этой главе мы обсудим мультипроцессоры и мультикомпьютеры.
Межсоединения многопроцессорной системы
Параллельная обработка требует использования эффективных системных межсоединений для быстрой связи между устройствами ввода / вывода и периферийными устройствами, мультипроцессорами и общей памятью.
Иерархические шинные системы
Иерархическая система шин состоит из иерархии шин, соединяющих различные системы и подсистемы / компоненты в компьютере. Каждая шина состоит из ряда сигнальных, управляющих и силовых линий. Различные шины, такие как местные шины, шины объединительной платы и шины ввода / вывода, используются для выполнения различных функций соединения.
Местные шины - это шины, реализованные на печатных платах. Шина объединительной платы - это печатная схема, на которой используется множество разъемов для подключения функциональных плат. Шины, которые соединяют устройства ввода / вывода с компьютерной системой, известны как шины ввода / вывода.
Поперечный переключатель и многопортовая память
Коммутируемые сети обеспечивают динамическое соединение между входами и выходами. В системах малого или среднего размера в основном используются перекрестные сети. Многоступенчатые сети могут быть расширены до более крупных систем, если проблема увеличения задержки может быть решена.
И линейный переключатель, и многопортовая организация памяти представляют собой одноступенчатую сеть. Хотя построение одноступенчатой сети обходится дешевле, для установления определенных соединений может потребоваться несколько проходов. В многоступенчатой сети имеется более одной ступени распределительных коробок. Эти сети должны иметь возможность подключать любой вход к любому выходу.
Многоступенчатые и комбинированные сети
Многоступенчатые сети или многоступенчатые сети межсоединений представляют собой класс высокоскоростных компьютерных сетей, которые в основном состоят из обрабатывающих элементов на одном конце сети и элементов памяти на другом конце, соединенных коммутирующими элементами.
Эти сети применяются для построения более крупных многопроцессорных систем. Это включает в себя Omega Network, Butterfly Network и многие другие.
Мультикомпьютеры
Мультикомпьютеры - это архитектуры MIMD с распределенной памятью. На следующей диаграмме показана концептуальная модель мультикомпьютера -
Мультикомпьютеры - это машины для передачи сообщений, которые применяют метод коммутации пакетов для обмена данными. Здесь у каждого процессора есть собственная память, но нет глобального адресного пространства, так как процессор может получить доступ только к своей собственной локальной памяти. Таким образом, коммуникация не прозрачна: здесь программисты должны явно добавлять примитивы коммуникации в свой код.
Отсутствие глобально доступной памяти является недостатком мультикомпьютеров. Это можно решить, используя следующие две схемы -
- Виртуальная общая память (VSM)
- Общая виртуальная память (SVM)
В этих схемах прикладной программист предполагает большую общую память, которая имеет глобальную адресацию. При необходимости обращения к памяти, сделанные приложениями, переводятся в парадигму передачи сообщений.
Виртуальная общая память (VSM)
VSM - это аппаратная реализация. Таким образом, система виртуальной памяти операционной системы прозрачно реализована поверх VSM. Итак, операционная система думает, что она работает на машине с общей памятью.
Общая виртуальная память (SVM)
SVM - это программная реализация на уровне операционной системы с аппаратной поддержкой блока управления памятью (MMU) процессора. Здесь единицей совместного использования являются страницы памяти операционной системы.
Если процессор обращается к определенной области памяти, MMU определяет, находится ли страница памяти, связанная с доступом к памяти, в локальной памяти или нет. Если страницы нет в памяти, в обычной компьютерной системе она выгружается с диска операционной системой. Но в SVM операционная система выбирает страницу с удаленного узла, которому принадлежит эта конкретная страница.
Три поколения мультикомпьютеров
В этом разделе мы обсудим три поколения мультикомпьютеров.
Выбор дизайна в прошлом
При выборе технологии процессора разработчик мультикомпьютеров выбирает недорогие процессоры со средней зернистостью в качестве строительных блоков. Большинство параллельных компьютеров построено на стандартных микропроцессорах. Для нескольких компьютеров была выбрана распределенная память, а не общая память, что ограничило бы масштабируемость. Каждый процессор имеет свой собственный блок локальной памяти.
Что касается схемы соединения, у мультикомпьютеров используются прямые сети с передачей сообщений, точка-точка, а не сети с коммутацией адресов. В качестве стратегии управления разработчик нескольких компьютеров выбирает асинхронные операции MIMD, MPMD и SMPD. Cosmic Cube Caltech (Seitz, 1983) - первый из мультикомпьютеров первого поколения.
Настоящее и будущее развитие
Компьютеры следующего поколения эволюционировали от мультикомпьютеров со средним и мелким зерном, использующих глобально разделяемую виртуальную память. Мультикомпьютеры второго поколения все еще используются. Но использование более совершенных процессоров, таких как i386, i860 и т. Д., Компьютеры второго поколения получили большое развитие.
Компьютеры третьего поколения - это компьютеры следующего поколения, в которых будут использоваться узлы, реализованные на СБИС. Каждый узел может иметь процессор 14 MIPS, каналы маршрутизации 20 Мбайт / с и 16 Кбайт ОЗУ, интегрированных в один кристалл.
Система Intel Paragon
Раньше для создания мультикомпьютеров гиперкуба использовались однородные узлы, поскольку все функции были переданы хосту. Таким образом, это ограничивало пропускную способность ввода-вывода. Таким образом, для решения крупномасштабных проблем эффективно или с высокой пропускной способностью эти компьютеры не могли использоваться. Система Intel Paragon была разработана для преодоления этой трудности. Он превратил мультикомпьютер в сервер приложений с многопользовательским доступом в сетевой среде.
Механизмы передачи сообщений
Механизмы передачи сообщений в многокомпьютерной сети требуют специальной аппаратной и программной поддержки. В этом разделе мы обсудим некоторые схемы.
Схемы маршрутизации сообщений
В мультикомпьютере со схемой маршрутизации с сохранением и пересылкой пакеты являются наименьшей единицей передачи информации. В сетях с маршрутизацией через «червоточины» пакеты далее разделяются на порции. Длина пакета определяется схемой маршрутизации и реализацией сети, тогда как длина пакета зависит от размера сети.
В Store and forward routing, пакеты являются основной единицей передачи информации. В этом случае каждый узел использует буфер пакетов. Пакет передается от узла источника к узлу назначения через последовательность промежуточных узлов. Задержка прямо пропорциональна расстоянию между источником и местом назначения.
В wormhole routingпередача от узла источника к узлу назначения осуществляется через последовательность маршрутизаторов. Все переходы одного и того же пакета передаются в неразрывной последовательности конвейерным способом. В этом случае только заголовок знает, куда идет пакет.
Тупик и виртуальные каналы
Виртуальный канал - это логическая связь между двумя узлами. Он образован флит-буфером в узле источника и узле приемника и физическим каналом между ними. Когда для пары выделяется физический канал, один буфер источника соединяется с одним буфером приемника, чтобы сформировать виртуальный канал.
Когда все каналы заняты сообщениями и ни один канал в цикле не освобожден, возникает ситуация тупика. Чтобы избежать этого, необходимо следовать схеме предотвращения тупиковых ситуаций.
В этой главе мы обсудим протоколы согласованности кеша, которые помогут справиться с проблемами несогласованности нескольких кешей.
Проблема согласованности кеша
В многопроцессорной системе несогласованность данных может возникать между соседними уровнями или внутри одного и того же уровня иерархии памяти. Например, кэш и основная память могут иметь несовместимые копии одного и того же объекта.
Поскольку несколько процессоров работают параллельно и независимо несколько кешей могут иметь разные копии одного и того же блока памяти, это создает cache coherence problem. Cache coherence schemes помогают избежать этой проблемы, поддерживая единообразное состояние для каждого кэшированного блока данных.
Пусть X будет элементом общих данных, на который ссылаются два процессора, P1 и P2. Вначале согласованы три копии X. Если процессор P1 записывает новые данные X1 в кэш, используяwrite-through policy, та же копия будет немедленно записана в общую память. В этом случае возникает несогласованность между кэш-памятью и основной памятью. Когдаwrite-back policy используется, основная память будет обновляться, когда измененные данные в кэше заменяются или становятся недействительными.
В общем, существует три источника проблемы несогласованности:
- Совместное использование записываемых данных
- Миграция процесса
- Активность ввода / вывода
Протоколы Snoopy Bus
Протоколы Snoopy обеспечивают согласованность данных между кэш-памятью и общей памятью через систему памяти на основе шины. Write-invalidate и write-update политики используются для поддержания согласованности кеша.
В этом случае у нас есть три процессора P1, P2 и P3, имеющие согласованную копию элемента данных «X» в их локальной кэш-памяти и в общей памяти (рисунок-a). Процессор P1 записывает X1 в свою кэш-память, используяwrite-invalidate protocol. Таким образом, все остальные копии аннулируются через шину. Обозначается буквой «I» (рис. B). Недействительные блоки также известны какdirty, т.е. их нельзя использовать. Вwrite-update protocolобновляет все копии кеша через шину. Используяwrite back cache, копия памяти также обновляется (Рисунок-c).
Кэшировать события и действия
Следующие события и действия происходят при выполнении команд доступа к памяти и аннулирования:
Read-miss- Когда процессор хочет прочитать блок, а его нет в кэше, происходит ошибка чтения. Это инициируетbus-readоперация. Если грязной копии не существует, то основная память, имеющая согласованную копию, предоставляет копию запрашивающей кэш-памяти. Если грязная копия существует в удаленной кэш-памяти, этот кеш будет ограничивать основную память и отправлять копию в запрашивающую кэш-память. В обоих случаях копия кэша перейдет в допустимое состояние после промаха чтения.
Write-hit - Если копия грязная или reservedсостояние, запись выполняется локально, а новое состояние - грязное. Если новое состояние допустимо, команда write-invalidate транслируется во все кеши, делая их копии недействительными. Когда общая память записывается, результирующее состояние резервируется после этой первой записи.
Write-miss- Если процессору не удается выполнить запись в локальную кэш-память, копия должна поступать либо из основной памяти, либо из удаленной кэш-памяти с грязным блоком. Это делается путем отправкиread-invalidateкоманда, которая сделает недействительными все копии кеша. Затем локальная копия обновляется до грязного состояния.
Read-hit - Чтение-попадание всегда выполняется в локальной кэш-памяти, не вызывая перехода состояния или не используя шину отслеживания для аннулирования.
Block replacement- Если копия грязная, она должна быть записана обратно в основную память методом замены блока. Однако, если копия находится в действительном, зарезервированном или недействительном состоянии, замена не производится.
Протоколы на основе каталогов
Используя многоступенчатую сеть для создания большого мультипроцессора с сотнями процессоров, протоколы отслеживания кэширования необходимо модифицировать в соответствии с возможностями сети. Широковещательная передача в многоступенчатой сети очень дорога, поэтому команды согласованности отправляются только в те кеши, которые хранят копию блока. Это причина для разработки протоколов на основе каталогов для сетевых мультипроцессоров.
In a directory-based protocols system, data to be shared are placed in a common directory that maintains the coherence among the caches. Here, the directory acts as a filter where the processors ask permission to load an entry from the primary memory to its cache memory. If an entry is changed the directory either updates it or invalidates the other caches with that entry.
Hardware Synchronization Mechanisms
Synchronization is a special form of communication where instead of data control, information is exchanged between communicating processes residing in the same or different processors.
Multiprocessor systems use hardware mechanisms to implement low-level synchronization operations. Most multiprocessors have hardware mechanisms to impose atomic operations such as memory read, write or read-modify-write operations to implement some synchronization primitives. Other than atomic memory operations, some inter-processor interrupts are also used for synchronization purposes.
Cache Coherency in Shared Memory Machines
Maintaining cache coherency is a problem in multiprocessor system when the processors contain local cache memory. Data inconsistency between different caches easily occurs in this system.
The major concern areas are −
- Sharing of writable data
- Process migration
- I/O activity
Sharing of writable data
When two processors (P1 and P2) have same data element (X) in their local caches and one process (P1) writes to the data element (X), as the caches are write-through local cache of P1, the main memory is also updated. Now when P2 tries to read data element (X), it does not find X because the data element in the cache of P2 has become outdated.
Process migration
In the first stage, cache of P1 has data element X, whereas P2 does not have anything. A process on P2 first writes on X and then migrates to P1. Now, the process starts reading data element X, but as the processor P1 has outdated data the process cannot read it. So, a process on P1 writes to the data element X and then migrates to P2. After migration, a process on P2 starts reading the data element X but it finds an outdated version of X in the main memory.
I/O activity
As illustrated in the figure, an I/O device is added to the bus in a two-processor multiprocessor architecture. In the beginning, both the caches contain the data element X. When the I/O device receives a new element X, it stores the new element directly in the main memory. Now, when either P1 or P2 (assume P1) tries to read element X it gets an outdated copy. So, P1 writes to element X. Now, if I/O device tries to transmit X it gets an outdated copy.
Uniform Memory Access (UMA)
Uniform Memory Access (UMA) architecture means the shared memory is the same for all processors in the system. Popular classes of UMA machines, which are commonly used for (file-) servers, are the so-called Symmetric Multiprocessors (SMPs). In an SMP, all system resources like memory, disks, other I/O devices, etc. are accessible by the processors in a uniform manner.
Non-Uniform Memory Access (NUMA)
In NUMA architecture, there are multiple SMP clusters having an internal indirect/shared network, which are connected in scalable message-passing network. So, NUMA architecture is logically shared physically distributed memory architecture.
In a NUMA machine, the cache-controller of a processor determines whether a memory reference is local to the SMP’s memory or it is remote. To reduce the number of remote memory accesses, NUMA architectures usually apply caching processors that can cache the remote data. But when caches are involved, cache coherency needs to be maintained. So these systems are also known as CC-NUMA (Cache Coherent NUMA).
Cache Only Memory Architecture (COMA)
COMA machines are similar to NUMA machines, with the only difference that the main memories of COMA machines act as direct-mapped or set-associative caches. The data blocks are hashed to a location in the DRAM cache according to their addresses. Data that is fetched remotely is actually stored in the local main memory. Moreover, data blocks do not have a fixed home location, they can freely move throughout the system.
COMA architectures mostly have a hierarchical message-passing network. A switch in such a tree contains a directory with data elements as its sub-tree. Since data has no home location, it must be explicitly searched for. This means that a remote access requires a traversal along the switches in the tree to search their directories for the required data. So, if a switch in the network receives multiple requests from its subtree for the same data, it combines them into a single request which is sent to the parent of the switch. When the requested data returns, the switch sends multiple copies of it down its subtree.
COMA против CC-NUMA
Ниже приведены различия между COMA и CC-NUMA.
COMA имеет тенденцию быть более гибким, чем CC-NUMA, потому что COMA прозрачно поддерживает миграцию и репликацию данных без необходимости в ОС.
Машины COMA дороги и сложны в сборке, потому что им требуется нестандартное оборудование для управления памятью, а протокол когерентности труднее реализовать.
Удаленный доступ в COMA часто медленнее, чем в CC-NUMA, поскольку для поиска данных необходимо пройти по древовидной сети.
Есть много способов снизить стоимость оборудования. Один из методов заключается в менее тесной интеграции вспомогательного средства связи и сети в узел обработки и увеличения задержки связи и занятости.
Другой метод - обеспечение автоматической репликации и согласованности программным, а не аппаратным обеспечением. Последний метод обеспечивает репликацию и согласованность в основной памяти и может выполняться с различной степенью детализации. Это позволяет использовать стандартные комплектующие для узлов и межсоединений, сводя к минимуму стоимость оборудования. Это заставляет программиста добиваться хорошей производительности.
Расслабленные модели согласованности памяти
Модель согласованности памяти для общего адресного пространства определяет ограничения в том порядке, в котором операции с памятью в одном и том же или разных местах кажутся выполняемыми по отношению друг к другу. Фактически, любой системный уровень, поддерживающий модель именования совместно используемого адресного пространства, должен иметь модель согласованности памяти, которая включает интерфейс программиста, интерфейс пользовательской системы и аппаратно-программный интерфейс. Программное обеспечение, которое взаимодействует с этим слоем, должно знать свою собственную модель согласованности памяти.
Технические характеристики системы
Системная спецификация архитектуры определяет порядок и переупорядочение операций с памятью, а также то, какую производительность можно реально получить от этого.
Ниже приведены несколько моделей спецификаций, использующих ослабления в программном порядке.
Relaxing the Write-to-Read Program Order- Этот класс моделей позволяет аппаратному обеспечению подавлять задержку операций записи, которая была пропущена в кэш-памяти первого уровня. Когда ошибка записи находится в буфере записи и не видна другим процессорам, процессор может завершить чтение, которое попадает в его кэш-память, или даже одно чтение, которое отсутствует в его кэш-памяти.
Relaxing the Write-to-Read and Write-to-Write Program Orders- Разрешение операций записи в обход предыдущих невыполненных операций записи в различные места позволяет объединить несколько операций записи в буфер записи перед обновлением основной памяти. Таким образом, несколько промахов записи перекрываются и становятся видимыми вне очереди. Мотивация состоит в том, чтобы еще больше минимизировать влияние задержки записи на время простоя процессора и повысить эффективность связи между процессорами, сделав новые значения данных видимыми для других процессоров.
Relaxing All Program Orders- По умолчанию не гарантируются никакие программные заказы, кроме зависимостей данных и управления внутри процесса. Таким образом, преимущество состоит в том, что несколько запросов на чтение могут выполняться одновременно, и в программном порядке могут быть обойдены более поздними записями, а сами могут завершаться не по порядку, что позволяет нам скрыть задержку чтения. Этот тип моделей особенно полезен для динамически планируемых процессоров, которые могут продолжать прошлые ошибки чтения для других ссылок на память. Они допускают множество переупорядочений, даже исключение доступа, выполняемого при оптимизации компилятора.
Интерфейс программирования
Программные интерфейсы предполагают, что программные заказы вообще не должны поддерживаться между операциями синхронизации. Гарантируется, что все операции синхронизации явно помечены или идентифицированы как таковые. Библиотека времени выполнения или компилятор преобразует эти операции синхронизации в подходящие операции сохранения порядка, предусмотренные спецификацией системы.
Затем система обеспечивает последовательное согласованное выполнение, даже если она может переупорядочивать операции среди операций синхронизации любым желаемым образом, не нарушая зависимости от места в процессе. Это дает компилятору достаточную гибкость среди точек синхронизации для переупорядочивания, которое он желает, а также предоставляет процессору возможность выполнять столько переупорядочений, сколько позволяет его модель памяти. В интерфейсе программиста модель согласованности должна быть как минимум такой же слабой, как и у аппаратного интерфейса, но не обязательно такой же.
Механизмы перевода
В большинстве микропроцессоров преобразование меток в механизмы поддержания порядка сводится к вставке подходящей инструкции барьера памяти до и / или после каждой операции, помеченной как синхронизация. Он будет сохранять инструкции с отдельными загрузками / хранилищами, указывая, какие порядки применять, и избегая дополнительных инструкций. Однако, поскольку операции обычно выполняются нечасто, большинство микропроцессоров зашли так далеко.
Преодоление ограничений мощности
Мы рассмотрели системы, которые обеспечивают автоматическую репликацию и согласованность аппаратно только в кэш-памяти процессора. Кэш-память процессора, без предварительной репликации в локальную основную память, реплицирует удаленно распределенные данные непосредственно по ссылке.
Проблема с этими системами заключается в том, что область локальной репликации ограничивается аппаратным кешем. Если блок заменяется из кэш-памяти, он должен быть извлечен из удаленной памяти, когда он снова понадобится. Основная цель систем, обсуждаемых в этом разделе, - решить проблему емкости репликации, но при этом обеспечить согласованность аппаратных средств и высокую степень детализации блоков кэша для повышения эффективности.
Третичные кеши
Чтобы решить проблему емкости репликации, можно использовать большой, но более медленный кэш удаленного доступа. Это необходимо для функциональности, когда узлы машины сами по себе являются небольшими многопроцессорными системами и их можно просто увеличить для повышения производительности. Он также будет содержать реплицированные удаленные блоки, которые были заменены из кэш-памяти локального процессора.
Архитектуры только кэш-памяти (COMA)
В машинах COMA с каждым блоком памяти во всей основной памяти связан аппаратный тег. Не существует фиксированного узла, на котором всегда есть гарантия выделения места для блока памяти. Данные динамически мигрируют или реплицируются в основной памяти узлов, которые обращаются к ним / привлекают их. Когда осуществляется доступ к удаленному блоку, он реплицируется в привлекательной памяти и помещается в кэш, а аппаратное обеспечение поддерживает согласованность в обоих местах. Блок данных может находиться в любой памяти аттракционов и может легко перемещаться от одного к другому.
Снижение стоимости оборудования
Снижение затрат означает перенос некоторых функций специализированного оборудования на программное обеспечение, работающее на существующем оборудовании. Программному обеспечению гораздо проще управлять репликацией и согласованностью в основной памяти, чем в аппаратном кэше. Недорогие методы, как правило, обеспечивают репликацию и согласованность в основной памяти. Для эффективного управления согласованностью каждый из других функциональных компонентов ассистента может получить выгоду от специализации и интеграции оборудования.
Исследовательские усилия направлены на снижение затрат с помощью различных подходов, например, путем осуществления контроля доступа на специализированном оборудовании, но возлагая другие действия на программное обеспечение и обычное оборудование. Другой подход заключается в выполнении программного управления доступом и предназначен для выделения согласованной абстракции общего адресного пространства на обычных узлах и сетях без специальной аппаратной поддержки.
Последствия для параллельного программного обеспечения
Модель ослабленной согласованности памяти требует, чтобы параллельные программы помечали требуемые конфликтующие обращения как точки синхронизации. Язык программирования предоставляет возможность пометить некоторые переменные как синхронизирующие, которые затем будут переведены компилятором в подходящую инструкцию сохранения порядка. Чтобы ограничить собственное переупорядочение доступа компилятора к общей памяти, компилятор может использовать метки сам по себе.
An interconnection networkв параллельной машине информация передается от любого исходного узла к любому желаемому узлу назначения. Эта задача должна быть выполнена с минимальной задержкой. Это должно позволить одновременное выполнение большого количества таких переводов. Причем он должен быть недорогим по сравнению со стоимостью остальной машины.
Сеть состоит из ссылок и коммутаторов, которые помогают отправлять информацию от исходного узла к узлу назначения. Сеть определяется своей топологией, алгоритмом маршрутизации, стратегией коммутации и механизмом управления потоком.
Организационная структура
Сети межсетевого взаимодействия состоят из следующих трех основных компонентов:
Links- Линия связи - это кабель из одного или нескольких оптоволоконных или электрических проводов с разъемом на каждом конце, подключенным к коммутатору или порту сетевого интерфейса. Благодаря этому аналоговый сигнал передается с одного конца, принимается с другого, чтобы получить исходный цифровой поток информации.
Switches- Коммутатор состоит из набора входных и выходных портов, внутренней «поперечины», соединяющей все входы со всеми выходами, внутренней буферизации и управляющей логики для осуществления соединения ввода-вывода в каждый момент времени. Обычно количество входных портов равно количеству выходных портов.
Network Interfaces- Сетевой интерфейс ведет себя совершенно иначе, чем коммутационные узлы, и может быть подключен через специальные ссылки. Сетевой интерфейс форматирует пакеты и создает информацию о маршрутизации и управлении. Он может иметь буферизацию ввода и вывода по сравнению с переключателем. Он может выполнять сквозную проверку ошибок и управление потоком. Следовательно, его стоимость зависит от сложности обработки, емкости хранилища и количества портов.
Межсетевое соединение
Сети межсетевого взаимодействия состоят из коммутационных элементов. Топология - это шаблон для подключения отдельных коммутаторов к другим элементам, таким как процессоры, памяти и другие коммутаторы. Сеть позволяет обмениваться данными между процессорами в параллельной системе.
Direct connection networks- Прямые сети имеют двухточечные соединения между соседними узлами. Эти сети являются статическими, что означает, что соединения точка-точка являются фиксированными. Некоторыми примерами прямых сетей являются кольца, сетки и кубы.
Indirect connection networks- Непрямые сети не имеют фиксированных соседей. Топология связи может динамически изменяться в зависимости от требований приложения. Непрямые сети можно разделить на три части: шинные сети, многоступенчатые сети и перекрестные переключатели.
Bus networks- Шинная сеть состоит из нескольких битовых линий, к которым подключено несколько ресурсов. Когда шины используют одни и те же физические линии для данных и адресов, данные и адресные линии мультиплексируются по времени. Когда к шине подключено несколько мастеров шины, требуется арбитр.
Multistage networks- Многоступенчатая сеть состоит из нескольких ступеней коммутаторов. Он состоит из переключателей «axb», которые подключаются по определенной схеме межкаскадного соединения (ISC). Компактные коммутационные элементы 2x2 являются обычным выбором для многих многокаскадных сетей. Количество ступеней определяет задержку сети. Выбирая различные схемы межкаскадных соединений, можно создавать различные типы многоступенчатой сети.
Crossbar switches- Поперечный переключатель содержит матрицу простых элементов переключателя, которые могут включаться и выключаться для создания или разрыва соединения. Включив переключающий элемент в матрице, можно установить соединение между процессором и памятью. Поперечные переключатели являются неблокирующими, то есть все перестановки связи могут выполняться без блокировки.
Оценка компромиссов при проектировании в топологии сети
Если основной проблемой является расстояние трассировки, то необходимо максимизировать размер и создать гиперкуб. При маршрутизации с промежуточным хранением, предполагая, что степень переключения и количество каналов не были существенным фактором стоимости, а количество каналов или степень переключения являются основными затратами, размер необходимо минимизировать, а сетку построен.
В худшем случае для каждой сети предпочтительнее иметь сети большого размера, в которых все пути короткие. В схемах, где каждый узел обменивается данными только с одним или двумя ближайшими соседями, предпочтительно иметь низкоразмерные сети, поскольку фактически используются только некоторые из измерений.
Маршрутизация
Алгоритм маршрутизации сети определяет, какой из возможных путей от источника к месту назначения используется в качестве маршрутов и как определяется маршрут, по которому следует каждый конкретный пакет. Маршрутизация в порядке измерения ограничивает набор допустимых путей, поэтому существует ровно один маршрут от каждого источника до каждого пункта назначения. Тот, который получается при первом прохождении правильного расстояния в измерении высокого порядка, затем в следующем измерении и так далее.
Механизмы маршрутизации
Арифметика, выбор порта на основе источника и просмотр таблицы - это три механизма, которые высокоскоростные коммутаторы используют для определения выходного канала по информации в заголовке пакета. Все эти механизмы проще, чем обычные вычисления маршрутизации, реализованные в традиционных маршрутизаторах LAN и WAN. В параллельных компьютерных сетях коммутатор должен принимать решение о маршрутизации для всех своих входов в каждом цикле, поэтому механизм должен быть простым и быстрым.
Детерминированная маршрутизация
Алгоритм маршрутизации является детерминированным, если маршрут сообщения определяется исключительно его источником и местом назначения, а не другим трафиком в сети. Если алгоритм маршрутизации выбирает только кратчайшие пути к месту назначения, он минимален, в противном случае он не минимален.
Свобода тупика
Тупик может возникнуть в различных ситуациях. Когда два узла пытаются отправить данные друг другу, и каждый начинает отправку до того, как один из них получит, может возникнуть «лобовая» взаимоблокировка. Другой случай взаимоблокировки возникает, когда несколько сообщений конкурируют за ресурсы в сети.
Основной метод доказательства отсутствия тупиков в сети состоит в том, чтобы очистить зависимости, которые могут возникать между каналами в результате сообщений, перемещающихся по сетям, и показать отсутствие циклов в общем графике зависимостей каналов; следовательно, нет схем трафика, которые могут привести к тупику. Обычный способ сделать это - пронумеровать ресурсы канала так, чтобы все маршруты следовали определенной возрастающей или убывающей последовательностям, чтобы не возникали циклы зависимости.
Дизайн переключателя
Дизайн сети зависит от конструкции коммутатора и того, как коммутаторы соединены между собой. Степень коммутатора, его внутренние механизмы маршрутизации и его внутренняя буферизация определяют, какие топологии могут поддерживаться и какие алгоритмы маршрутизации могут быть реализованы. Как и любой другой аппаратный компонент компьютерной системы, сетевой коммутатор содержит путь к данным, управление и хранилище.
Порты
Общее количество контактов - это фактически общее количество портов ввода и вывода, умноженное на ширину канала. Поскольку периметр микросхемы растет медленно по сравнению с площадью, переключатели имеют тенденцию быть ограниченными по выводам.
Внутренний канал данных
Путь данных - это связь между каждым из набора входных портов и каждым выходным портом. Обычно ее называют внутренней поперечиной. Неблокирующая перекладина - это та, где каждый входной порт может быть подключен к отдельному выходу в любой перестановке одновременно.
Буферы каналов
Организация буферной памяти в коммутаторе имеет важное значение для производительности коммутатора. Традиционные маршрутизаторы и коммутаторы, как правило, имеют большие буферы SRAM или DRAM, внешние по отношению к коммутационной матрице, в то время как в коммутаторах VLSI буферизация является внутренней по отношению к коммутатору и исходит из того же бюджета кремния, что и канал данных и секция управления. По мере увеличения размера и плотности микросхемы становится доступной больше буферизации, и у разработчика сети появляется больше возможностей, но все же буферная площадь становится главным выбором, и ее организация важна.
Управление потоком
Когда несколько потоков данных в сети пытаются использовать одни и те же общие сетевые ресурсы одновременно, необходимо предпринять некоторые действия для управления этими потоками. Если мы не хотим потерять какие-либо данные, некоторые потоки должны быть заблокированы, а другие продолжаются.
Проблема управления потоками возникает во всех сетях и на многих уровнях. Но в параллельных компьютерных сетях он качественно отличается от локальных и глобальных сетей. В параллельных компьютерах сетевой трафик должен доставляться примерно так же точно, как и трафик по шине, и существует очень большое количество параллельных потоков в очень малом масштабе.
Скорость микропроцессоров увеличилась более чем в десять раз за десятилетие, но скорость обычных запоминающих устройств (DRAM) только удвоилась, то есть время доступа уменьшилось вдвое. Таким образом, латентность доступа к памяти с точки зрения тактовых циклов процессора вырастает в шесть раз за 10 лет. Мультипроцессоры усугубили проблему.
В системах на основе шины установление шины с высокой пропускной способностью между процессором и памятью имеет тенденцию к увеличению задержки получения данных из памяти. Когда память физически распределена, задержка сети и сетевого интерфейса добавляется к задержке доступа к локальной памяти на узле.
Задержка обычно увеличивается с увеличением размера машины, поскольку большее количество узлов подразумевает большее количество коммуникаций по сравнению с вычислениями, большее количество скачков в сети для общего обмена данными и, вероятно, большее количество конфликтов. Основная цель проектирования оборудования - уменьшить задержку доступа к данным при сохранении высокой масштабируемой пропускной способности.
Обзор допуска к задержке
Лучше всего понять, как обрабатывается допустимая задержка, если посмотреть на ресурсы машины и то, как они используются. С точки зрения процессора, архитектура связи от одного узла к другому может рассматриваться как конвейер. Этапы конвейера включают сетевые интерфейсы в источнике и получателе, а также в сетевых каналах и коммутаторах по пути. Есть также этапы в помощнике связи, системе локальной памяти / кеш-памяти и главном процессоре, в зависимости от того, как архитектура управляет связью.
Проблема использования в базовой структуре связи состоит в том, что либо процессор, либо архитектура связи заняты в данный момент времени, а в конвейере связи одновременно занят только один этап, поскольку передаваемое одиночное слово проходит путь от источника к месту назначения. Цель устойчивости к задержкам - максимально перекрыть использование этих ресурсов.
Допуск к задержке при явной передаче сообщений
Фактическая передача данных при передаче сообщений обычно инициируется отправителем с помощью операции отправки. Операция получения сама по себе не побуждает к передаче данных, а скорее копирует данные из входящего буфера в адресное пространство приложения. Связь, инициированная получателем, осуществляется путем отправки сообщения запроса процессу, который является источником данных. Затем процесс отправляет данные обратно через другую отправку.
Операция синхронной отправки имеет задержку связи, равную времени, необходимому для передачи всех данных в сообщении адресату, времени обработки приема и времени возврата подтверждения. Задержка синхронной операции приема - это накладные расходы на ее обработку; что включает в себя копирование данных в приложение и дополнительную задержку, если данные еще не прибыли. Мы хотели бы скрыть эти задержки, включая накладные расходы, если это возможно, на обоих концах.
Допуск задержки в общем адресном пространстве
Базовая коммуникация осуществляется посредством чтения и записи в общем адресном пространстве. Для удобства это называется обменом данными чтения-записи. Связь, инициированная получателем, осуществляется с помощью операций чтения, в результате которых осуществляется доступ к данным из памяти или кеша другого процессора. Если нет кэширования общих данных, инициируемая отправителем связь может осуществляться посредством записи в данные, которые размещены в удаленной памяти.
В случае согласованности кэша эффект записи более сложен: либо запись приводит к отправителю, либо инициированному получателем обмену данными, в зависимости от протокола согласованности кеша. Связь, инициируемая получателем или отправителем, в разделяемом адресном пространстве с аппаратной поддержкой чтения и записи, естественно, является мелкозернистой, что делает очень важной задержку допуска.
Блокировать передачу данных в общем адресном пространстве
В совместно используемом адресном пространстве аппаратно или программно объединение данных и инициирование передачи блоков могут выполняться явно в пользовательской программе или прозрачно системой. Явные передачи блоков инициируются путем выполнения команды, аналогичной отправке в пользовательской программе. Команда отправки объясняется помощником связи, который конвейерно передает данные от исходного узла к месту назначения. В месте назначения помощник связи извлекает слова данных из сетевого интерфейса и сохраняет их в указанных местах.
Есть два основных отличия от передачи сообщений отправки-получения, оба из которых возникают из-за того, что процесс отправки может напрямую указывать структуры данных программы, в которые данные должны быть помещены в место назначения, поскольку эти местоположения находятся в общем адресном пространстве. .
Обработка прошедших событий с большой задержкой в общем адресном пространстве
Если операция с памятью сделана неблокирующей, процессор может перейти от операции к памяти к другим инструкциям. Для записи это обычно довольно просто реализовать, если запись помещается в буфер записи, а процессор продолжает работу, в то время как буфер заботится о передаче записи в систему памяти и отслеживании ее завершения по мере необходимости. Разница в том, что в отличие от записи, за чтением обычно очень скоро следует инструкция, которой требуется значение, возвращаемое чтением.
Предварительная связь в общем адресном пространстве
Предварительная коммуникация - это метод, который уже широко используется в коммерческих микропроцессорах, и его важность, вероятно, возрастет в будущем. Команда предварительной выборки не заменяет фактическое чтение элемента данных, и сама команда предварительной выборки должна быть неблокирующей, если она предназначена для достижения своей цели - сокрытия задержки через перекрытие.
В этом случае, поскольку общие данные не кэшируются, предварительно выбранные данные помещаются в специальную аппаратную структуру, называемую буфером предварительной выборки. Когда слово фактически считывается в регистр на следующей итерации, оно считывается из заголовка буфера предварительной выборки, а не из памяти. Если бы задержка, которую нужно скрыть, была намного больше, чем время для вычисления одной итерации цикла, мы бы предварительно выбрали несколько итераций вперед, и потенциально в буфере предварительной выборки было бы несколько слов за раз.
Многопоточность в общем адресном пространстве
С точки зрения сокрытия различных типов задержки, аппаратная многопоточность, возможно, является универсальным методом. Он имеет следующие концептуальные преимущества перед другими подходами:
Не требует специального программного анализа или поддержки.
Поскольку он вызывается динамически, он может справляться с непредсказуемыми ситуациями, такими как конфликты кеша и т. Д., А также с предсказуемыми.
Как и предварительная выборка, он не меняет модель согласованности памяти, поскольку не меняет порядок доступа внутри потока.
В то время как предыдущие методы нацелены на сокрытие задержки доступа к памяти, многопоточность потенциально может так же легко скрыть задержку любого события с большой задержкой, если событие может быть обнаружено во время выполнения. Это также включает синхронизацию и задержку инструкций.
Эта тенденция может измениться в будущем, поскольку задержки становятся все больше по сравнению со скоростью процессора. Также с более сложными микропроцессорами, которые уже предоставляют методы, которые могут быть расширены для многопоточности, и с новыми технологиями многопоточности, разрабатываемыми для объединения многопоточности с параллелизмом на уровне команд, эта тенденция, безусловно, будет претерпевать некоторые изменения в будущем.