Системы с общей и распределенной памятью

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Системы с общей и распределенной памятью

Особенность ВС - множество параллельно работающих процессоров. Важная задача - задача организации памяти.

Две проблемы:

1) Различие между быстродействием процессора и памяти (как и в однопроцессорных системах);

2) Одновременный доступ к памяти нескольких процессоров.

В зависимости от организации памяти различают:

ВС с общей памятью (sharedmemory, мультипроцессоры, сильно связанные, closelycoupledsystems);

ВС с распределенной памятью (distributed memory, слабосвязанные, loosely coupled systems, мультикомпьютеры).

Различие между общей и распределенной памятью - это разница в структуре виртуальной памяти, то есть в том, как память выгладит со стороны процессора. Физически почти каждая система памяти разделена на автономные компоненты, доступ к которым может производиться независимо. Общую память от распределенной отличает то, каким образом подсистема памяти интерпретирует поступивший от процессора адрес ячейки. Для примера положим, что процессор выполняет команду LoadR0, i, означающую «Загрузить регистр R0 содержимым ячейки i». В случае общей памяти i - это глобальный адрес, и для любого процессора указывает на одну и ту же ячейку. В распределенной системе памяти i - это локальный адрес. Если два процессора выполняют команду LoadR0, i, то каждый из них обращается к i-й ячейке в своей локальной памяти, то есть к разным ячейкам, и в регистры R0 могут быть загружены неодинаковые значения.

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

Мультипроцессоры сложно строить, но легко программировать. Мультикомпьютеры легко строить, но сложно программировать.

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

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

Многоуровневая организация общей памяти

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

1) Общая память реализована на аппаратном обеспечении.

Одна копия операционной системы с одной таблицей распределения памяти. Для ОС память монолитна.

2) Общая память реализована на основе ОС и аппаратного обеспечения.

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

3) Реализация общей разделенной памяти на уровне программного обеспечения.

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

Память с чередованием адресов

Физически память вычислительной системы состоит из нескольких модулей (банков), при этом существенным вопросом является то, как в этом случае распределено адресное пространство (набор всех адресов, которые может сформировать процессор). Один из способов распределения виртуальных адресов по модулям памяти состоит в разбиении адресного пространства на последовательные блоки. Если память состоит изn банков, то ячейка с адресом i при поблочном разбиении будет находиться в банке с номером i/n. В системе памяти с чередованием адресов (interleavedmemory) последовательные адреса располагаются в различных банках: ячейка с адресом i находится в банке с номером imodn. Пусть, например, память состоит из четырех банков, по 256 байт в каждом. В схеме, ориентированной на блочную адресацию, первому банку будут выделены виртуальные адреса 0-255, второму - 256-511 и т.д. В схеме с чередованием адресов последовательные ячейки в первом банке будут иметь виртуальные адреса 0, 4, 8, … во втором банке - 1, 5, 9 и т.д.

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

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

Симметричные (SMP) многопроцессорные ВС. Архитектура типа UMA, COMA, NUMA

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

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

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

Технически UMA-системы предполагают наличие узла, соединяющего каждый из n процессоров с каждым из модулей памяти. Простейший путь построения таких ВС - объединение нескольких процессоров (P) с единой памятью (Mp) посредством общей шины (рис.). В этом случае, однако, в каждый момент времени обмен по шине может вести только один из процессоров, то есть процессоры должны соперничать за доступ к шине. Когда процессор Рi, выбирает из памяти команду, остальные процессорыPj (i<>j) должны ожидать, пока шина освободится. Если в систему входят только два процессора, они в состоянии работать с производительностью, близкой к максимальной, поскольку их доступ к шине можно чередовать; пока один процессор декодирует и выполняет команду, другой вправе использовать шину для выборки из памяти следующей команды.

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

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

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

Мультипроцессоры UMA с координатными коммутаторами

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

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

Недостаток системы: рост узлов как n². При наличии 1000 процессоров и 1000 модулей памяти получаем число узлов - 1 млн. Это неприемлемо. Тем не менее, координатные коммутаторы вполне применимы для систем средних размеров.

Мультипроцессоры UMA с многоступенчатыми сетями

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

Поле Модуль сообщает, какую память использовать. Поле Адрес определяет адрес в этом модуле памяти. В поле Код операции содержится операция, например READ или WRITE. Наконец, дополнительное поле Значение может содержать операнд, например 32-битное слово, которое нужно записать при выполнении операции WRITE. Коммутатор исследует поле Модуль и использует его для определения, через какую выходную линию нужно отправить сообщение: через X или через Y.

Наши коммутаторы 2x2 можно компоновать различными способами и получать многоступенчатые сети.

Один из возможных вариантов - сеть omega. Здесь мы соединили 8 процессоров с 8 модулями памяти, используя 12 коммутаторов. Для n процессоров и n модулей памяти нам понадобится log2n ступеней, n/2 коммутаторов на каждую ступень, то есть всего (n/2) log2n коммутаторов, что намного лучше, чем n2 узлов (точек пересечения), особенно для больших n.

Каждая ступень для передачи сигнала в соответствующем направлении использует биты в поле Модуль (0 - верхний выход, 1 - нижний). При этом после прохождения ступени соответствующие биты становятся не нужны и они заменяются на номер входной линии. Рассматривая пути a и b (на рис.), видим, что они используют разные коммутаторы, следовательно, запросы могут выполняться параллельно.

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

Мультипроцессоры NUMA

мультипроцессор память многоуровневый шина

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

Для большей масштабируемости мультипроцессоров приспособлена архитектура NUMA (NonUniformMemoryAccess - с неоднородным доступом к памяти). Как и мультипроцессоры UMA, они обеспечивают единое адресное пространство для всех процессоров, но, в отличие от машин UMA, доступ к локальным модулям памяти происходит быстрее, чем к удаленным.

Машины NUMA имеют три ключевые характеристики, которыми все они обладают и которые в совокупности отличают их от других мультипроцессоров:

1. Существует одно адресное пространство, видимое для всех процессоров.

2. Доступ к удаленной памяти производится с использованием команд LOAD и STORE.

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

В рамках концепцииNUMA реализуется несколько различных подходов, обозначаемых аббревиатурами СОМА, cc-numa и ncc-numa.

Особенности COMA

1) Локальная память каждого процессора рассматривается как кэш для доступа «своего» процессора.

2) Кэши всех процессоров рассматриваются как глобальная память системы, а сама глобальная память отсутствует.

3) Данные не привязаны к конкретному модулю памяти и не имеют уникального адреса, остающегося неизменным в течение всего времени существования переменной.

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

Достоинство

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

Недостаток

Если данные требуются нескольким процессорам, то строка кэша с данными должна перемещаться туда и обратно при каждом доступе к данным.

Особенности NC-NUMA (NoCachingNUMA - NUMA без кэширования)

1) Отсутствует кэш-память, это значит, что память гарантированно согласованна

2) Каждое слово памяти находится только в одном месте, нет копий.

3) От того, в какой памяти находится слово, зависит производительность.

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

Недостаток

Низкаярасширяемость

Особенности CC-NUMA (Cache Coherent Non-Uniform Memory Architecture)

1) Наличие кэша у процессоров.

2) Совместимость кэшей на программном или аппаратном уровне.

Способы обеспечения совместимости кешей:

A. Отслеживание системной шины (низкая масштабируемость, простота технической реализации)

B. Использование каталога (хранение БД кэш-строк в высокоскоростном специализированном аппаратном обеспечении)

Мультипроцессор SunEnterprise 10000

1) Архитектура UMA из одного корпуса с 64 процессорами.

2) Координатный коммутатор Gigaplahe-XB 16х16 запакован в плату, содержащую 8 гнезд с двух сторон.

3) Каждое гнездо вмещает огромную плату процессора (40x50 см), содержащую 4 процессора UltraSPARC на 333 МГц и ОЗУ на 4 Гбайт.

4) Жесткие требования к синхронизации и малое время ожидания.

5) Доступ к памяти вне платы занимает столько же времени, что и доступ к памяти на плате.

6) Длина строки кэш-памяти составляет 64 байта, а ширина канала связи составляет 16 байтов, поэтому для перемещения строки кэш-памяти требуется 4 цикла.

7) Помимо координатного коммутатора имеются 4 адресные шины, которые используются для отслеживания строк в кэш-памяти. Каждая шина используется для 1/4 физического адресного пространства.

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

Enterprise 10000 использует 4 отслеживающие шины параллельно, плюс очень широкий координатный коммутатор для передачи данных. Ясно, что такая система преодолевает предел в 64 процессора.

Размещено на Allbest.ru