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

   1. Введение

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

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

   2. Протоколы когерентности кэш-памяти

В мультипроцессорах с разделяемой шиной сама шина ограничивает ресурсы системы даже при небольшом количестве процессоров; ключом к решению задачи максимизации производительности системы, является минимизация нагрузки на шину со стороны каждого процессора. Оснащение каждого процессора собственной кэш-памятью может существенно снизить объем информации, передаваемой по шине, так как многие задачи теперь не будут требовать передачи сообщения по ней. Требования к шине также могут быть уменьшены за счет использования алгоритма обратной записи при обновлении оперативной памяти (вместо сквозной записи) [12]. Все схемы, рассматриваемые в данной работе, используют обратную запись. Однако мы смоделируем и сквозную запись для сравнения.

За исключением протоколов Firefly и Dragon [15, 9] все предложенные решения поддерживают когерентность, позволяя любому числу процессоров читать заданный блок, но лишь одному процессору писать в него (в один такт времени). В отличие от решений, эффективных для сетей, которые требуют глобальной информационной таблицы, методы для разделяемой шины поддерживают когерентность на основе информации, хранящейся локально в каждом кэше. Каждый кэш-контроллер прослушивает транзакции и, если необходимо (в зависимости от типа транзакции и состояния блока), осуществляет действия, необходимые для поддержания когерентности между кэшами, имеющими копии этого блока. Для каждой транзакции наблюдающий кэш-контроллер должен определить, имеет ли он копию блока, путем сопоставления адреса блока, обнаруженного на шине с адресами блоков, присутствующих в кэш-памяти. Если это единичная копия ячейки кэша, каждая попытка сопоставления будет требовать цикл кэш-памяти, на протяжении которого кэш будет недоступен для обслуживания запросов процессора к памяти.

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

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

   2.1 Протокол однократной записи (write-once)

Это первый протокол, описанный в литературе [6]; схема однократной записи Гудмана была разработана для одноплатных компьютеров с использованием шины Multibus. Обязательность применения протокола на основе шины является ограничением, но упрощает реализацию. В схеме однократной записи блоки в локальном кэше могут находиться в одном из 4-х состояний: Invalid, Valid (неизмененный, возможно разделяемый), Reserved (не требующий обратной записи) и Dirty (записанный более одного раза, не согласованный с оперативной памятью). Блоки, помеченные для замещения в кэше, должны быть записаны обратно в оперативную память, только если они находятся в состоянии Dirty.

Схема работает следующим образом:
 1) Промах чтения (read miss). Если есть другая копия этого блока в каком-то кэше в состоянии Dirty, кэш с этой копией блокирует память от передачи данных до тех пор, пока блок не будет заменен в оперативной памяти, и поставляет этот блок самостоятельно. Если ни один кэш не имеет такой копии, то блок поставляется из оперативной памяти. Все кэши, которые имеют копии этого блока, изменяют их состояния на Valid;
 2) Попадание записи (write hit). Если блок в состоянии Dirty, то запись может бать призведена локально без задержки. Если блок в состоянии Reserved, запись также может быть произведена без задержки, при этом состояние блока меняется на Dirty. Если блок в состоянии Valid, записываемое слово переписывается в оперативную память, после чего состояние блока изменяется на Reserved. Другие кэши с этой копией наблюдают за записью через шину и меняют состояния своих копий на Invalid. Если блок замещен в состоянии Reserved, он не нуждается в обратной записи, так как копия в оперативной памяти является текущей;
 3) Промах записи (write miss). Как и в случае промаха при чтении, блок загружается из памяти, или, если он находится в состоянии Dirty в каком-то кэше, – из этого кэша. После наблюдения промаха записи на шине все остальные кэши помечают свои копии как недостоверные. Как только блок загружен, происходит запись, и состояние блока меняется на Dirty. Диаграмма переходов для протокола однократной записи представлена на рис. 1.

   2.2 Synapse

Данный метод был использован в Synapse N+1, мультипроцессоре для отказоустойчивой обработки транзакций [5]. N+1 отличается от других архитектур на основе разделяемой шины, рассматриваемых нами наличием двух системных шин. Дополнительная шина расширяет полосу пропускания настолько, что система может включать в себя до 28 процессоров. Другое примечательное различие – включение однобитового тэга для каждого блока кэша в оперативной памяти, указывающего, должна ли ОП отвечать на промах по этому блоку. Если какой-то кэш содержит модифицированную копию блока, то оперативная память благодаря этому тэгу не будет отвечать на запросы (со стороны других кэшей). Это предотвращает возникновение гонки кэшей: если какой-либо кэш не отвечает быстро, то нужно предупредить ответ со стороны ОП. Блоки кэша могут находиться в следующих состояниях: Invalid, Valid (не изменен, возможно разделяемый) и Dirty (изменен, и нет согласованной копии).

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

Протокол Synapse разрешает проблему когерентности следующим образом:
 1) Промах чтения. Если другой кэш имеет Dirty-копию, читающий кэш получает негативный ответ. Затем обладатель блока записывает его в основную память, одновременно сбрасывая битовый тэг и меняя локальное состояние на Invalid. Читающий кэш затем должен послать дополнительный запрос для получения блока из ОП. Следует отметить, что блок всегда поставляется его обладателем: оперативной памятью или кэшем. Загружаемый блок всегда имеет состояние Valid;
 2) Попадание при записи. Если блок находится в состоянии Dirty, то запись может быть проведена без задержки. Если блок находится в состоянии Valid, процесс передачи идентичен случаю промаха при записи (включая полный цикл передачи данных) при отсутствии признака недостоверности;
 3) Промах при записи. Как и в случае промаха при чтении, блок всегда поставляется из основной памяти, если в другом кэше есть Dirty-копия, то она сначала должна быть записана в основную память обладателем блока. Каждый кэш с Valid-копиями блока изменяет их состояние на Invalid, после чего загружается блок, бывший в состоянии Dirty. Тэг блока в основной памяти устанавливается таким образом, чтобы ОП проигнорировала последующие запросы этого блока.

Диаграмма переходов для протокола Synapse представлена на рис. 2.

   2.3 Berkeley

Этот подход был применен в RISC-мультипроцессоре, разработанном в Университете Калифорнии в Беркли [8]. Сема подобна подходу Synapse с двумя основными различиями: здесь используются передачи типа кэш-кэш в случае разделяемых блоков, а «грязные» блоки не записываются обратно в память, когда становятся разделяемыми, что требует одного дополнительного состояния.

Используются следующие состояния блоков: Invalid, Valid (возможно разделяемый и не измененный), Shared-dirty (возможно разделяемый и модифицированный) и Dirty (модифицированный, копии в других кэшах отсутствуют) – см. рис. 3.

Блок в состоянии Shared-dirty и Dirty должен быть записан в основную память, если он выбран для замещения. Блок в состоянии Dirty может находиться только в одном кэше. Блок в состоянии Shared-dirty может находиться только в одном кэше, но он также может присутствовать в состоянии Valid в других кэшах. Как и Synapse, Berkeley использует идею владения: кэш, который содержит блок в состоянии Dirty или Shared-dirty объявляется владельцем блока. Если блок не принадлежит ни одному кэшу, владельцем является память.

Проблема когерентности разрешается следующим способом:
 1) Промах чтения. Если в каком то кэше есть блок в состоянии Dirty или Shared-dirty, кэш с данной копией должен предоставить блок другому кэшу и изменить его локальное состояние на Shared-dirty. Если блок находится в каком-либо другом состоянии или некэширован, то он поставляется из основной памяти. В любом случае состояние блока в запрашивающем кэше становится Valid. Следует отметить, что блок всегда поставляется его владельцем;
 2) Попадание при записи. Если блок находится в состоянии Dirty, запись продолжается без замедления. Если блок в состоянии Valid или Shared-dirty, то сигнал недостоверности должен быть послан на шину перед тем, как запись продолжится. Все остальные кэши аннулируют свои копии, при этом локальное состояние блока в вызывающем кэше изменяется на Dirty;
   3) Промах при записи. Как и в случае промаха при чтении блок приходит непосредственно от его обладателя. Все остальные кэши с копиями этого блока изменяют их состояния на Invalid, а блок в запрашивающем кэше переходит в состояние Dirty.

   2.4 Illinois

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

Схема предполагает наличие следующих четырех состояний для кэшируемых блоков: Invalid, Valid-exclusive (не модифицированный, единственная копия), Shared (не модифицированный и есть копии в других кэшах) и Dirty (модифицированный, копия только в одном кэше) – см. рис. 4. Блоки записываются в память при вытеснении, только если они находятся в состоянии Dirty.

Схема работает следующим образом:
 1) Промах чтения. Если у любого другого кэша есть копия блока, он выставляет ее на шину. Если блок в состоянии Dirty, он также одновременно записывается в основную память. Если блок в состоянии Shared, то кэш с наивысшим приоритетом выставляет его на шину. Все кэши, имеющие копию блока, заметят промах и изменят состояния своих копий на Shared. Если блок приходит из памяти и другие кэши не имеют его копии, то он загружается с состояние Valid-exclusive;
 2) Попадание при записи. Если блок находится в состоянии Dirty, запись может быть произведена без задержки. Если блок в состоянии Valid-exclusive, он также может быть записан немедленно с изменением его состояния Dirty. Если блок в состоянии Shared, запись откладывается до тех пор, пока сигнал аннулирования не будет послан на шину, что вызовет смену всех состояний копии блока в других кэшах на Invalid. Затем записывающий кэш сможет продолжить запись и установит локальное состояние блока в Dirty;
 3) Промах при записи. Как и в случае промаха при чтении, если в другом кэше есть копия блока, то блок поставляется этим кэшем. Остальные кэши аннулируют свои копии, блок загружается в вызывающий кэш в состояние Dirty.

   3. Имитационная модель

Порядок, в котором протоколы были описаны в предыдущем разделе, был выбран специально, чтобы показать либо усложнение протокола, либо потребность в более «интеллектуальной» шине. Основная цель исследования – дать некоторые количественные оценки протоколов по основным показателям (которые будут определены позднее) в зависимости от числа процессоров, которые будут использовать разделяемую шину, не вызывая перегрузки системы. С этой целью мы используем имитационную модель, описанную ниже, вместо аналитической модели, которая не может отразить тонкие различия между некоторыми протоколами. Имитационная модель управляется некоторыми искусственными потоками обращений, а не потоками, реально действующими в мультипроцессоре. Некоторые дампы работы системы при решении задач могут быть созданы, но все же они будут выглядеть искусственными.

Первый шаг в моделировании, реализованный с помощью Simula, – это создание модели базового мультипроцессора. К этой базовой модели в дополнение были созданы зависимые от протокола дополнения (различные версии для каждой оцениваемой схемы). Поскольку мы собираемся оценивать сами протоколы, а не их реализации, предполагаем, что все не зависимые от протокола параметры идентичны. Таким образом, рабочая нагрузка представляется следующим образом: для каждого сеанса моделирования поток обращений процессора одинаков для всех схем и зависит от случайного начального параметра. Мы также предполагаем идентичные конфигурации систем: все схемы оцениваются с одной шиной (несмотря на то, что протокол Synapse предполагает использований двух), а каждый кэш имеет 2 копии каталога кэша. Этот дополнительный каталог позволяет системе слежения за шиной сравнивать адреса, не оказывая влияния на производительность кэш-памяти, за исключением случаев успешного сопоставления, когда контроллер должен предпринять действия согласно протоколу.

   3.1 Модель мультипроцессора

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

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

Процесс шины получает служебные запросы от всех кэшей и обслуживает их в порядке очереди. Запросы могут быть четырех типов: промах чтения, промах записи, обратная запись «грязного блока» и (в зависимости от схемы) запрос на разрешение записи, сигнал аннулирования или широковещательная рассылка нового значения слова – все, что связано с попаданиями при записи на не модифицированных разделяемых блоках. Концептуально процесс шины включает в себя реализацию дополнительной логики кэша, ответственной за сравнение адресов, поэтому он может определить положение всех кэшируемых копий разделяемых блоков. Если в процессе обработки одного из четырех вышеперечисленных типов запросов, процесс шины обнаруживает, что другие кэши нуждаются в поставке данных (если блок запрошен откуда-либо и он находится в состоянии Dirty) или в смене локального состояния (например, в случае аннулирования копий при записи в разделяемый блок), команды посылаются в соответствующий кэш. Когда транзакция закончена, шина посылает кэшу сигнал, разрешающий продолжение работы.

   3.2 Модель рабочей нагрузки

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

Поток обращений каждого процессора представляется объединением двух потоков: потока обращений к разделяемым блокам и потока обращений к собственным блокам. Каждый раз при обращении к памяти, процессор генерирует обращение к разделяемому блоку с вероятностью smd, а обращение к частному блоку с вероятностью 1-smd. Аналогично, вероятность того, что это запрос на чтение – rd, а что на запись – 1-rd.

Если запрос адресован частному блоку, то попадание наблюдается с вероятностью h, а промах – с вероятностью 1-h. В случае попадания при записи будем считать, что блок уже модифицирован с вероятностью wmd, не модифицирован – с вероятностью 1-wmd. Частные блоки, по определению, не могут присутствовать в других кэшах. Следует отметить, что модель рабочей нагрузки для частных блоков отражает установившееся поведение системы, а не поведение системы при загрузке (в кэш уже загружено большинство блоков, к которым будут производиться обращения в ближайшее время, коэффициент попаданий уже выровнялся).

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

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

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

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

Если блок является частным, то он модифицирован с вероятностью md (и нуждается в записи в основную память), не модифицирован – с вероятностью 1-md (в этом случае никакие действия не требуются).

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

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

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

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

Эти 2 уравнения определяют отношения, принятые для результатов моделирования. Хотя эти приближения не являются совершенно точными, они служат хорошей оценкой относительных величин-параметров имитационной модели: md, wmd и rd.

    Литература

1. Archibald, J., Baer, J.-L. An economical solution to the cache coherence problem. In Proceedings of the 11th International Symposium on Computer Architecture. IEEE, New York, 1984, pp. 355-362.
2. Censier L. M., Feautrier P. A new solution to coherence problems in multicache systems. IEEE Trans. Comput. C-27, 12 (Dec. 1978), 1112-1118.
3. Dubois M., Briggs F. Effects of cache coherency in multiprocessors. IEEE Trans. Comput. C-32, 11 (Nov. 1982), 1083-1099.
4. Fielland G., Rodgers D. 32-bit computer system shares load equally among up to 12 processors. Electron. Design (Sept. 1984), 153-168.
5. Frank S. J. Tightly coupled multiprocessor systems speed memory access times. Electronics 57, 1 (Jan. 1984), 164-169.
6. Goodman, J. R. Using cache memory to reduce processor-memory traffic. In Proceedings of the 10th International Symposium on Computer Architecture. IEEE, New York, 1983, pp. 124-131.
7. Goodman J. R. Cache memory optimization to reduce processor-memory traffic. J. VLSI Comput. Syst. 2, 1 (1986), in press.
8. Katz R., Eggers S., Wood D. A., Perkins C., Sheldon R. G. Implementing a cache consistency protocol. In Proceedings of the 12th International Symposium on Computer Archttecture. IEEE, New York, 1985, pp. 276-283.
9. Mccreight E. The Dragon computer system: An early overview. Tech. Rep., Xerox Corp., Sept. 1984.
10. Papamarcos M., Patel J. A low overhead coherence solution for multiprocessors with private cache memories. In Proceedings of the 11th International Symposium on Computer Architecture. IEEE, New York, 1984, pp. 348-354.
11. Rudolph L., Segall Z. Dynamic decentralized cache schemes for MIMD parallel processors. In Proceedings of the 1 lth International Symposium on Computer Architecture. IEEE, New York, 1984, pp. 340-347.
12. Smith A. J. Cache memories. ACM Comput. Suru. 24,3 (Sept. 1982), 473-530.
13. Sweazey P., Smith A. J. A class of compatible cache consistency protocols and their support by the IEEE Futurebus. In Proceedings of the 13th International Symposium on Computer Architecture. IEEE, New York, 1986, pp. 414-423.
14. Tanc C. K. Cache system design in the tightly coupled multiprocessor system. In Proceedkgs of the 1976 AFIPS National Computer Conference. AFIPS, Reston, Va., 1976, pp. 749-753.
15. Thacker C. Private communication, Digital Equipment Corp., July 6, 1984.
16. Yen W. C., Fu, K. S. Coherence problem in a multicache System. In Proceedings of the 1982 International Conference on Parallel Processing. IEEE, New York, 1982, pp. 332-339.