Лекция 2.

Тема. Организация памяти вычислительных систем.

План лекции.

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

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

3. Мультипроцессорная когерентность кэш-памяти.

4. Программные способы решения проблемы когерентности.

В вычислительных системах, объединяющих множество параллельно рабо-тающих процессоров или машин, важнейшей задачей является правильная орга-низация памяти. Различают вычислительные системы с общей памятью (shared memory) и ВС с распределенной памятью (distributed memory). В системах с общей памятью (совместно используемой или разделяемой памятью) память ВС рассматривается как общий ресурс, и каждый из процессоров имеет полный доступ ко всему адресному пространству. Системы с общей памятью называются сильно связанными (closely coupled systems).

В варианте с распределенной памятью каждому из процессоров придается собственная память. Процессоры объединяются в сеть и могут при необхо-димости обмениваться данными, хранящимися в их памяти, передавая друг другу сообщения. Такой вид ВС называется слабо связанным (loosely coupled systems).

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

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

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

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

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

а б

Рис. 2.1. Память с чередованием адресов: а – распределение адресов; б – элементы, извлекаемые с шагом 9 из массива 8 × 8

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

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

Системы памяти обеспечивают дополнительную гибкость при извлечении элементов векторов. В некоторых системах возможна одновременная загрузка каждого n-го элемента вектора, например, при извлечении элементов вектора v, хранящегося в последовательных ячейках памяти при n =4, память возвратит v0, v4, v8. Интервал между элементами называется шагом по индексу или «страйдом» (stride). Одним из интересных применений этого свойства может служить доступ к матрицам. Если шаг по индексу на единицу больше числа строк в матрице, одиночный запрос на доступ к памяти возвратит все диагональные элементы матрицы (рис. 2.1, б). Ответственность за то, чтобы все извлекаемые элементы матрицы располагались в разных банках, ложится на программиста.