Параллельная компьютерная архитектура — Введение

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

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

Почему параллельная архитектура?

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

Тенденции применения

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

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

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

$$Speedup (p \ processors) \ equ \ frac {Производительность (p \ processors)} {Производительность (1 \ процессор)}$$

Для единственной исправленной проблемы,

$$performance \ of \ a \ computer \ system = \ frac {1} {Время \ необходимое \ для \ завершения \ проблемы \}$$ $$Speedup \ _ {исправлено \ problem} (p \ processors) = \ frac {Время (1 \ процессор)} {Время (р \ процессор)}$$

Научно-технические вычисления

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

Коммерческие вычисления

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

Технологические Тенденции

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

Основной технологией, используемой здесь, является технология СБИС. Поэтому в настоящее время все больше и больше транзисторов, затворов и цепей могут быть установлены в одной области. С уменьшением базового размера функции VLSI тактовая частота также увеличивается пропорционально ей, в то время как число транзисторов увеличивается как квадрат. Можно ожидать, что использование нескольких транзисторов одновременно (параллелизм) будет работать намного лучше, чем при увеличении тактовой частоты

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

Архитектурные тенденции

Развитие технологий решает, что возможно; Архитектура преобразует потенциал технологии в производительность и возможности. Параллелизм и локальность — это два метода, где большие объемы ресурсов и большее количество транзисторов повышают производительность. Однако эти два метода конкурируют за одни и те же ресурсы. Когда несколько операций выполняются параллельно, количество циклов, необходимых для выполнения программы, уменьшается.

Тем не менее, ресурсы необходимы для поддержки каждого из одновременных действий. Ресурсы также необходимы для выделения локального хранилища. Наилучшая производительность достигается благодаря промежуточному плану действий, в котором используются ресурсы для использования степени параллелизма и локальности.

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

• Вакуумные трубки
• Транзисторы
• Интегральные схемы
• VLSI

До 1985 года в продолжительности доминировал рост параллелизма на уровне битов. 4-разрядные микропроцессоры, затем 8-разрядные, 16-разрядные и т. Д. Чтобы уменьшить количество циклов, необходимых для выполнения полной 32-разрядной операции, ширина пути данных была удвоена. Позже были введены 64-битные операции.

Рост параллелизма на уровне обучения доминировал с середины 80-х до середины 90-х годов. Подход RISC показал, что было просто распределить этапы обработки инструкций так, чтобы в среднем инструкция выполнялась почти в каждом цикле. Развитие технологии компиляции сделало конвейеры инструкций более производительными.

В середине 80-х годов микропроцессорные компьютеры состояли из

• Целочисленный процессор
• Блок с плавающей запятой
• Контроллер кеша
• SRAM для данных кэша
• Хранение меток

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

Конвергенция параллельных архитектур

Параллельные машины были разработаны с несколькими различными архитектурами. В этом разделе мы обсудим различные параллельные компьютерные архитектуры и характер их конвергенции.

Архитектура связи

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

Модель программирования — это верхний слой. Приложения написаны в модели программирования. Модели параллельного программирования включают в себя —

• Общее адресное пространство
• Передача сообщений
• Параллельное программирование данных

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

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

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

Общая память

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

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

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

Архитектура передачи сообщений

Архитектура передачи сообщений также является важным классом параллельных машин. Он обеспечивает связь между процессорами в виде явных операций ввода-вывода. В этом случае связь объединяется на уровне ввода / вывода вместо системы памяти.

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

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

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

конвергенция

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

Параллельная обработка данных

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

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

Основные вопросы дизайна

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

В этом разделе мы обсудим коммуникационную абстракцию и основные требования модели программирования.

Коммуникационная абстракция

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

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

Требования к модели программирования

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

Чтобы убедиться, что зависимости между программами принудительно установлены, параллельная программа должна координировать активность своих потоков.

Параллельная компьютерная архитектура — модели

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

Современные компьютеры имеют мощные и обширные программные пакеты. Чтобы проанализировать развитие производительности компьютеров, сначала мы должны понять основные разработки аппаратного и программного обеспечения.

• Основные этапы развития компьютера — Есть два основных этапа развития компьютера — механические или электромеханические части. Современные компьютеры развивались после внедрения электронных компонентов. Электроны с высокой подвижностью в электронных компьютерах заменили рабочие части в механических компьютерах. Для передачи информации электрический сигнал, который распространяется почти со скоростью света, заменяется механическими передачами или рычагами.

• Элементы современных компьютеров . Современная компьютерная система состоит из компьютерного оборудования, наборов команд, прикладных программ, системного программного обеспечения и пользовательского интерфейса.

Основные этапы развития компьютера — Есть два основных этапа развития компьютера — механические или электромеханические части. Современные компьютеры развивались после внедрения электронных компонентов. Электроны с высокой подвижностью в электронных компьютерах заменили рабочие части в механических компьютерах. Для передачи информации электрический сигнал, который распространяется почти со скоростью света, заменяется механическими передачами или рычагами.

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

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

• Эволюция компьютерной архитектуры. За последние четыре десятилетия компьютерная архитектура претерпела революционные изменения. Мы начали с архитектуры фон Неймана, и теперь у нас есть мультикомпьютеры и мультипроцессоры.

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

Эволюция компьютерной архитектуры. За последние четыре десятилетия компьютерная архитектура претерпела революционные изменения. Мы начали с архитектуры фон Неймана, и теперь у нас есть мультикомпьютеры и мультипроцессоры.

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

Мультипроцессоры и мультикомпьютеры

В этом разделе мы обсудим два типа параллельных компьютеров —

• Мультипроцессоры
• Мультикомпьютеры

Мультикомпьютеры с общей памятью

Три наиболее распространенные модели мультипроцессоров с общей памятью —

Единый доступ к памяти (UMA)

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

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

Неоднородный доступ к памяти (NUMA)

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

Архитектура кэш-памяти только (COMA)

Модель COMA является частным случаем модели NUMA. Здесь все распределенные основные памяти преобразуются в кэш-память.

• Мультикомпьютеры с распределенной памятью. Мультикомпьютерная система с распределенной памятью состоит из нескольких компьютеров, известных как узлы, соединенные между собой сетью передачи сообщений. Каждый узел действует как автономный компьютер, имеющий процессор, локальную память и иногда устройства ввода-вывода. В этом случае все локальные воспоминания являются частными и доступны только для локальных процессоров. Вот почему традиционные машины называются машинами без удаленного доступа к памяти (NORMA) .

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

Мультивектор и SIMD Компьютеры

В этом разделе мы обсудим суперкомпьютеры и параллельные процессоры для векторной обработки и параллелизма данных.

Вектор Суперкомпьютеры

В векторном компьютере векторный процессор присоединяется к скалярному процессору в качестве дополнительной функции. Хост-компьютер сначала загружает программу и данные в основную память. Затем скалярный блок управления декодирует все инструкции. Если декодированные инструкции являются скалярными операциями или программными операциями, скалярный процессор выполняет эти операции, используя скалярные функциональные конвейеры.

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

SIMD Суперкомпьютеры

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

Модели PRAM и VLSI

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

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

Параллельные машины с произвольным доступом

Шепердсон и Стерджис (1963) смоделировали обычные однопроцессорные компьютеры как машины с произвольным доступом (ОЗУ). Fortune и Wyllie (1978) разработали модель машины с произвольным доступом (PRAM) для моделирования идеализированного параллельного компьютера с нулевыми затратами на доступ к памяти и синхронизацией.

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

Ниже приведены возможные операции обновления памяти.

• Эксклюзивное чтение (ER). В этом методе в каждом цикле только один процессор может читать из любой области памяти.

• Эксклюзивная запись (EW). В этом методе по крайней мере один процессор может одновременно выполнять запись в область памяти.

• Одновременное чтение (CR) — позволяет нескольким процессорам считывать одну и ту же информацию из одной и той же области памяти в одном цикле.

• Параллельная запись (CW) — позволяет одновременные операции записи в одну и ту же область памяти. Чтобы избежать конфликта записи, настроены некоторые политики.

Эксклюзивное чтение (ER). В этом методе в каждом цикле только один процессор может читать из любой области памяти.

Эксклюзивная запись (EW). В этом методе по крайней мере один процессор может одновременно выполнять запись в область памяти.

Одновременное чтение (CR) — позволяет нескольким процессорам считывать одну и ту же информацию из одной и той же области памяти в одном цикле.

Параллельная запись (CW) — позволяет одновременные операции записи в одну и ту же область памяти. Чтобы избежать конфликта записи, настроены некоторые политики.

Модель сложности СБИС

Параллельные компьютеры используют микросхемы VLSI для изготовления процессорных массивов, массивов памяти и крупных коммутационных сетей.

В настоящее время технологии СБИС являются двухмерными. Размер чипа VLSI пропорционален объему памяти (памяти), доступной в этом чипе.

Мы можем вычислить пространственную сложность алгоритма по площади чипа (A) реализации чипа VLSI этого алгоритма. Если T — это время (задержка), необходимое для выполнения алгоритма, то AT задает верхнюю границу общего числа битов, обработанных с помощью чипа (или ввода-вывода). Для некоторых вычислений существует нижняя граница f (s), такая что

AT ² > = O (f (s))

Где A = площадь чипа и T = время

Треки архитектурного развития

Эволюция параллельных компьютеров я распространил по следующим трекам —

• Несколько треков процессора
  • Многопроцессорная дорожка
  • Мультикомпьютерный трек
• Несколько данных трек
  • Векторный трек
  • SIMD трек
• Отслеживание нескольких потоков
  • Многопоточный трек
  • Отслеживание потока данных

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

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

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

Процессор в параллельных системах

В 80-х годах для изготовления мультикомпьютеров под названием Transputer был популярен процессор специального назначения. Транспортер состоял из одного центрального процессора, небольшой памяти SRAM, интерфейса основной памяти DRAM и четырех каналов связи, все на одном кристалле. Для параллельной компьютерной связи каналы были соединены в сеть транспортеров. Но ему не хватает вычислительной мощности и, следовательно, он не может удовлетворить растущий спрос на параллельные приложения. Эта проблема была решена путем разработки процессоров 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. Космический куб Caltech (Seitz, 1983) — первый мультикомпьютер первого поколения.

Настоящее и будущее развитие

Компьютеры следующего поколения превратились из мультикомпьютеров среднего и мелкого размера в глобальную виртуальную память. Мультикомпьютеры второго поколения все еще используются в настоящее время. Но с использованием более качественных процессоров, таких как i386, i860 и т. Д., Компьютеры второго поколения получили большое развитие.

Компьютеры третьего поколения — это компьютеры следующего поколения, где будут использоваться узлы, реализованные с помощью VLSI. Каждый узел может иметь процессор 14 MIPS, каналы маршрутизации 20 МБ / с и 16 КБ ОЗУ, интегрированные в один чип.

Система Intel Paragon

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

Механизмы передачи сообщений

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

Схемы маршрутизации сообщений

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

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

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

Тупик и виртуальные каналы

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

Когда все каналы заняты сообщениями и ни один из каналов в цикле не освобожден, возникает ситуация взаимоблокировки. Чтобы избежать этого, необходимо следовать схеме предотвращения тупиковых ситуаций.

Согласованность и синхронизация кэша

В этой главе мы обсудим протоколы согласованности кэша, чтобы справиться с проблемами несогласованности мультикаша.

Проблема когерентности кэша

В многопроцессорной системе несоответствие данных может происходить среди смежных уровней или в пределах одного уровня иерархии памяти. Например, кэш и основная память могут иметь несовместимые копии одного и того же объекта.

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

Пусть X будет элементом общих данных, на которые ссылаются два процессора, P1 и P2. В начале три копии X соответствуют. Если процессор P1 записывает новые данные X1 в кэш, используя политику сквозной записи , эта же копия будет немедленно записана в общую память. В этом случае возникает несоответствие между кэш-памятью и основной памятью. Когда используется политика обратной записи , основная память будет обновляться, когда измененные данные в кеше заменяются или становятся недействительными.

В целом, существует три источника проблемы несоответствия —

• Обмен записываемыми данными
• Процесс миграции
• Активность ввода / вывода

Протоколы Snoopy Bus

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

В этом случае у нас есть три процессора P1, P2 и P3, имеющие непротиворечивую копию элемента данных ‘X’ в своей локальной кэш-памяти и в общей памяти (рисунок-а). Процессор P1 записывает X1 в свою кэш-память, используя протокол недействительной записи . Таким образом, все остальные копии становятся недействительными через шину. Он обозначается буквой «Я» (рис. Б). Недействительные блоки также называются грязными , то есть их не следует использовать. Протокол записи-обновления обновляет все копии кэша через шину. При использовании кэша обратной записи копия памяти также обновляется (рисунок-в).

Кэш-события и действия

Следующие события и действия происходят при выполнении команд доступа к памяти и аннулирования —

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

• Хит записи — если копия находится в грязном или зарезервированном состоянии, запись выполняется локально, а новое состояние грязное. Если новое состояние действительно, команда write-invalidate транслируется на все кэши, аннулируя их копии. Когда разделяемая память записывается, результирующее состояние резервируется после этой первой записи.

• Ошибка записи — если процессору не удается записать в локальную кэш-память, копия должна поступить либо из основной памяти, либо из удаленной кэш-памяти с грязным блоком. Это делается отправкой команды read-invalidate , которая сделает недействительными все копии кэша. Затем локальная копия обновляется с грязным состоянием.

• Хит чтения — Хит чтения всегда выполняется в локальной кэш-памяти без изменения состояния или использования шины снупи для аннулирования.

• Замена блока — если копия загрязнена, ее необходимо записать обратно в основную память методом замены блока. Однако, когда копия находится в допустимом, зарезервированном или недействительном состоянии, замена не производится.

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

Хит записи — если копия находится в грязном или зарезервированном состоянии, запись выполняется локально, а новое состояние грязное. Если новое состояние действительно, команда write-invalidate транслируется на все кэши, аннулируя их копии. Когда разделяемая память записывается, результирующее состояние резервируется после этой первой записи.

Ошибка записи — если процессору не удается записать в локальную кэш-память, копия должна поступить либо из основной памяти, либо из удаленной кэш-памяти с грязным блоком. Это делается отправкой команды read-invalidate , которая сделает недействительными все копии кэша. Затем локальная копия обновляется с грязным состоянием.

Хит чтения — Хит чтения всегда выполняется в локальной кэш-памяти без изменения состояния или использования шины снупи для аннулирования.

Замена блока — если копия загрязнена, ее необходимо записать обратно в основную память методом замены блока. Однако, когда копия находится в допустимом, зарезервированном или недействительном состоянии, замена не производится.

Протоколы на основе каталогов

Используя многоступенчатую сеть для создания большого мультипроцессора с сотнями процессоров, необходимо изменить протоколы Snoopy Cache для соответствия возможностям сети. Широковещательная передача, являющаяся очень дорогой для выполнения в многоступенчатой ​​сети, команды согласованности отправляются только тем кэшам, которые хранят копию блока. Это является причиной разработки протоколов на основе каталогов для мультипроцессоров, подключенных к сети.

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

Механизмы аппаратной синхронизации

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

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

Когерентность кэша в машинах с общей памятью

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

Основные проблемные области —

• Обмен записываемыми данными
• Процесс миграции
• Активность ввода / вывода

Обмен записываемыми данными

Когда два процессора (P1 и P2) имеют один и тот же элемент данных (X) в своих локальных кэшах, и один процесс (P1) выполняет запись в элемент данных (X), поскольку кэш-память — это локальный кэш P1 сквозной записи, основная память Также обновлено. Теперь, когда P2 пытается прочитать элемент данных (X), он не находит X, потому что элемент данных в кэше P2 устарел.

Процесс миграции

На первом этапе кеш P1 содержит элемент данных X, тогда как P2 ничего не имеет. Процесс на P2 сначала записывает на X, а затем мигрирует на P1. Теперь процесс начинает чтение элемента данных X, но, поскольку процессор P1 устарел, данные не могут быть прочитаны. Итак, процесс в P1 записывает данные в элемент X и затем мигрирует в P2. После миграции процесс на P2 начинает считывать элемент данных X, но обнаруживает устаревшую версию X в основной памяти.

Активность ввода / вывода

Как показано на рисунке, устройство ввода-вывода добавляется к шине в двухпроцессорной многопроцессорной архитектуре. В начале оба кэша содержат элемент данных X. Когда устройство ввода-вывода получает новый элемент X, оно сохраняет новый элемент непосредственно в основной памяти. Теперь, когда P1 или P2 (предположим, P1) пытается прочитать элемент X, он получает устаревшую копию. Итак, P1 выполняет запись в элемент X. Теперь, если устройство ввода-вывода пытается передать X, оно получает устаревшую копию.

Единый доступ к памяти (UMA)

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

Неравномерный доступ к памяти (NUMA)

В архитектуре NUMA есть несколько кластеров SMP, имеющих внутреннюю непрямую / совместно используемую сеть, которые связаны в масштабируемую сеть передачи сообщений. Итак, архитектура NUMA — это логически распределенная физически распределенная архитектура памяти.

В машине NUMA кэш-контроллер процессора определяет, является ли ссылка на память локальной памятью SMP или удаленной. Чтобы уменьшить количество удаленных обращений к памяти, архитектуры NUMA обычно применяют процессоры кэширования, которые могут кэшировать удаленные данные. Но когда задействованы кеши, необходимо поддерживать когерентность кеша. Таким образом, эти системы также известны как CC-NUMA (Cache Coherent NUMA).

Архитектура кэш-памяти только (COMA)

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

Архитектуры COMA в основном имеют иерархическую сеть передачи сообщений. Переключатель в таком дереве содержит каталог с элементами данных в качестве своего поддерева. Поскольку данные не имеют домашнего местоположения, их нужно явно искать. Это означает, что удаленный доступ требует обхода по коммутаторам в дереве для поиска в их каталогах требуемых данных. Таким образом, если коммутатор в сети получает несколько запросов от своего поддерева для одних и тех же данных, он объединяет их в один запрос, который отправляется родителю коммутатора. Когда запрашиваемые данные возвращаются, коммутатор отправляет несколько копий по своему поддереву.

COMA против CC-NUMA

Ниже приведены различия между COMA и CC-NUMA.

• COMA имеет тенденцию быть более гибким, чем CC-NUMA, потому что COMA прозрачно поддерживает миграцию и репликацию данных без необходимости в ОС.

• Машины COMA дороги и сложны в сборке, потому что им требуется нестандартное оборудование для управления памятью, а протокол когерентности сложнее реализовать.

• Удаленный доступ в COMA часто медленнее, чем в CC-NUMA, поскольку для поиска данных необходимо пройти через древовидную сеть.

COMA имеет тенденцию быть более гибким, чем CC-NUMA, потому что COMA прозрачно поддерживает миграцию и репликацию данных без необходимости в ОС.

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

Удаленный доступ в COMA часто медленнее, чем в CC-NUMA, поскольку для поиска данных необходимо пройти через древовидную сеть.

Аппаратное обеспечение

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

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

Расслабленные модели согласованности памяти

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

Технические характеристики системы

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

Ниже приведены несколько моделей спецификаций, использующих релаксации в программном порядке.

• Ослабление порядка программ записи-чтения — этот класс моделей позволяет аппаратным средствам подавлять задержку операций записи, которые были пропущены в кэш-памяти первого уровня. Когда ошибка записи находится в буфере записи и не видна другим процессорам, процессор может завершить чтение, которое попало в его кэш-память, или даже одно чтение, которое отсутствует в его кэш-памяти.

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

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

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

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

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

Интерфейс программирования

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

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

Механизмы перевода

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

Преодоление ограничений емкости

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

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

Третичные тайники

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

Архитектура кэш-памяти (COMA)

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

Снижение стоимости оборудования

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

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

Последствия для параллельного программного обеспечения

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

Проектирование соединительных сетей

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

Сеть состоит из ссылок и коммутаторов, которые помогают отправлять информацию от исходного узла к целевому узлу. Сеть определяется ее топологией, алгоритмом маршрутизации, стратегией коммутации и механизмом управления потоком.

Организационная структура

Взаимосвязанные сети состоят из следующих трех основных компонентов:

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

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

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

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

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

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

Взаимосвязанная сеть

Взаимосвязанные сети состоят из коммутационных элементов. Топология — это шаблон для соединения отдельных коммутаторов с другими элементами, такими как процессоры, память и другие коммутаторы. Сеть позволяет обмениваться данными между процессорами в параллельной системе.

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

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

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

  • Многоступенчатые сети — многоступенчатая сеть состоит из нескольких этапов коммутаторов. Он состоит из переключателей ‘axb’, которые подключаются с использованием определенной схемы межкаскадного соединения (ISC). Небольшие коммутационные элементы 2×2 являются распространенным выбором для многих многоступенчатых сетей. Количество ступеней определяет задержку в сети. Выбирая различные шаблоны межкаскадного соединения, можно создавать различные типы многоступенчатых сетей.

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

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

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

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

Многоступенчатые сети — многоступенчатая сеть состоит из нескольких этапов коммутаторов. Он состоит из переключателей ‘axb’, которые подключаются с использованием определенной схемы межкаскадного соединения (ISC). Небольшие коммутационные элементы 2×2 являются распространенным выбором для многих многоступенчатых сетей. Количество ступеней определяет задержку в сети. Выбирая различные шаблоны межкаскадного соединения, можно создавать различные типы многоступенчатых сетей.

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

Оценка компромиссов проектирования в топологии сети

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

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

маршрутизация

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

Механизмы маршрутизации

Арифметика, выбор порта на основе источника и просмотр таблицы — это три механизма, которые высокоскоростные коммутаторы используют для определения выходного канала на основе информации в заголовке пакета. Все эти механизмы проще, чем общие вычисления маршрутизации, реализованные в традиционных маршрутизаторах LAN и WAN. В параллельных компьютерных сетях коммутатор должен принимать решение о маршрутизации для всех своих входов в каждом цикле, поэтому механизм должен быть простым и быстрым.

Детерминированная маршрутизация

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

Тупик свободы

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

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

Дизайн переключателя

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

Порты

Общее количество выводов фактически является общим количеством входных и выходных портов, умноженных на ширину канала. Поскольку периметр чипа растет медленно по сравнению с площадью, переключатели, как правило, ограничены по штырьку.

Внутренний канал данных

Канал данных — это соединение между каждым из набора входных портов и каждым выходным портом. Обычно это называется внутренней поперечиной. Неблокирующая поперечина — это та, где каждый входной порт может быть подключен к отдельному выходу в любой перестановке одновременно.

Канальные буферы

Организация буферного хранилища внутри коммутатора оказывает важное влияние на производительность коммутатора. Традиционные маршрутизаторы и коммутаторы, как правило, имеют большие буферы SRAM или DRAM, внешние по отношению к коммутационной матрице, в то время как в коммутаторах VLSI буферизация является внутренней по отношению к коммутатору и выходит из того же кремниевого бюджета, что и путь данных и секция управления. По мере увеличения размера и плотности микросхемы становится доступно больше буферизации, и у проектировщика сети появляется больше возможностей, но все же буферное пространство является наиболее предпочтительным, и его организация важна.

Управление потоком

Когда несколько потоков данных в сети пытаются использовать одни и те же общие сетевые ресурсы одновременно, необходимо предпринять некоторые действия для управления этими потоками. Если мы не хотим потерять какие-либо данные, некоторые потоки должны быть заблокированы, а другие продолжаются.

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

Допуск латентности

Скорость микропроцессоров увеличилась более чем в десять раз за десятилетие, но скорость памяти товаров (DRAM) только удвоилась, т. Е. Время доступа сократилось вдвое. Следовательно, задержка доступа к памяти с точки зрения тактовых циклов процессора возрастает в шесть раз за 10 лет. Мультипроцессоры обострили проблему.

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

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

Обзор толерантности к задержке

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

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

Допуск латентности при явной передаче сообщений

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

Операция синхронной отправки имеет задержку связи, равную времени, которое требуется для передачи всех данных в сообщении пункту назначения, времени для обработки приема и времени для возврата подтверждения. Задержка синхронной операции приема — это издержки ее обработки; который включает в себя копирование данных в приложение и дополнительную задержку, если данные еще не поступили. Мы хотели бы скрыть эти задержки, включая накладные расходы, если это возможно, на обоих концах.

Допуск латентности в общем адресном пространстве

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

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

Блокировка передачи данных в общем адресном пространстве

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

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

Продолжение прошлых событий с большими задержками в общем адресном пространстве

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

Предварительная связь в общем адресном пространстве

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

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

Многопоточность в общем адресном пространстве

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

• Не требует специального анализа программного обеспечения или поддержки.

• Поскольку он вызывается динамически, он может обрабатывать непредсказуемые ситуации, такие как конфликты в кэше и т. Д., А также предсказуемые.

• Как и предварительная выборка, она не меняет модель согласованности памяти, поскольку не изменяет порядок доступа в потоке.

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

Не требует специального анализа программного обеспечения или поддержки.

Поскольку он вызывается динамически, он может обрабатывать непредсказуемые ситуации, такие как конфликты в кэше и т. Д., А также предсказуемые.

Как и предварительная выборка, она не меняет модель согласованности памяти, поскольку не изменяет порядок доступа в потоке.

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

Эта тенденция может измениться в будущем, поскольку задержки становятся все более продолжительными по сравнению со скоростями процессора. Также с более сложными микропроцессорами, которые уже предоставляют методы, которые могут быть расширены для многопоточности, и с новыми технологиями многопоточности, разрабатываемыми для объединения многопоточности с параллелизмом на уровне команд, эта тенденция, безусловно, претерпевает некоторые изменения в будущем.