КОГЕРЕНТНОСТЬ ПАМЯТИ многопроцессорнЫХ вычислительнЫХ систем

А.А. Дерюгин

(Москва, Московский энергетический институт (технический университет), Россия)

В многопроцессорных вычислительных системах (МВС) с общей памятью (рис. 1) в целях повышения быстродействия в состав каждого из вычислительных модулей (PM) включается кэш-память (CM). При этом в процессе работы МВС обрабатываемые данные из модуля общей памяти (BM) передаются в CM (и обратно) блоками, обычно содержащими 4 слова. Адреса или теги блоков, находящиеся в данный момент в каждой из CM, фиксируются в таблице блоков, расположенной в контроллере этой CM .

Рис. 1. Структура МВС с общей памятью

PM – процессорный модуль, содержащий кэш-память (CM); BM – модуль общей памяти; IO – устройства ввода/вывода; HB – системная шина

В CM разных PM в одно и то же время может находиться один и тот же блок данных. Когерентность – это согласованность данных, хранящихся в BM и в кэш-памятях разных процессорных модулей, под которой понимается тот факт, что считываться из каждой ячейки блока должно последнее значение данных, записанных в эту ячейку [1, 2].

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

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

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

Для уменьшения этого времени разработано много различных протоколов поддержания когерентности [2, 3]. Все они основываются на сокращении числа сквозных записей и числа широковещательных опросов всех контроллеров CM на предмет определения есть ли в других CM блок, передаваемый в данный момент из BM в одну из CM. Первое действие вызывает блокировку работы одного PM, а второе – блокировку всей МВС.

Число опубликованных работ, в которых рассматриваются различные протоколы поддержания когерентности, составляет несколько десятков. Упомянем здесь только самый известный протокол MESI (Modified/Exclusive/Shared/Invalid), используемый в МВС, построенных на базе микропроцессоров Pentium и др. По этому протоколу предусмотрено 4 возможных состояния блоков, находящихся кэш-памятях (модифицированный, эксклюзивный, общий и недостоверный) и их переходы из одного состояния в другое для всех возможных режимов работы МВС.

Однако во всех работах речь идет о следствии нарушения когерентности и не вскрывается причина ее появления.

Для выявления причины нарушения когерентности рассмотрим фрагмент графа, отражающего параллельное выполнение частей программы, представленных в виде узлов (рис. 2). После выполнения
узла 1 могут одновременно (параллельно) выполняться узлы 2 и 3, например, в PM1 и PM2.

Данные, используемые при выполнении узлов 2 и 3, могут быть представлены в виде трех групп:

Рис. 2. Фрагмент графа параллельного выполнения частей программы

А – данные, которые используются только в узле 2 и могут изменяться (в дальнейшем – изменяемые данные),

В – изменяемые данные, используемые только в узле 3,

К – данные, используемые в узлах 2 и 3. Эти данные не могут изменяться в принципе, поскольку в случае изменения этих данных параллельное выполнение узлов 2 и 3 невозможно.

Если данные из групп А, В и К разместить в разные блоки, то узлы 2 и 3 могут выполняться параллельно без какого-либо взаимного влияния и без нарушения когерентности. Для пересылок блоков из BM в CM (и обратно) может быть применен весьма эффективный алгоритм обратной записи. При этом изменяемые данные должны передаваться из кэш-памятей PM1 и PM2 в BM только один раз после выполнения узлов 2 и 3.

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

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

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

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

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

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

3. Разработчикам аппаратуры надо:

- ввести в один из системных регистров PM параметр "размер блока" для передачи его компилятору на этапе конфигурирования МВС,

- убрать все средства, обеспечивающие поддержание когерентности: сквозную запись, протоколы наблюдения, широковещательные аннулирования и обновления и т.п. [1].

Автор отлично понимает, что предлагаемые им выше меры опоздали лет на 15 – 20, "поезд уже ушел"... Но "лучше поздно, чем никогда", поскольку поддержание когерентности сейчас обходится слишком дорого как в отношении аппаратурных, так и временных затрат, особенно в МВС с матричной структурой связей между PM и модулями общей памяти.

Все это позволяет надеяться, что предложения автора будут востребованы – "игра стоит свеч".

ЛИТЕРАТУРА

1. Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем: Учебник для вузов. – СПб.: Питер, 2004. – 668 с.

2. Katz R. H., Eggers S.J., Wood D.A., Perkins C.L., Sheldon R.G. "Implementing a Cache Consistency Protocol". Proceedings of the12^th International Symposium on Computer Architecture, 1985.

3. Tomasevic M., Milutinovic V. "The Cache Coherence Problem in Shared-Memory Multiprocessors", IEEE Computer Society Press, Los Alamitos, CA. 1993.б ь