1. Введение

Системы активной памяти являются частым подходом к преодолению преграды памяти для приложений с нерегулярным доступом, которые не поддаются таким методы, как предварительная выборка или улучшение в иерархии кэш-памяти. Центральная идея в этом подходе состоит в том, чтобы выполнить параллельные вычисления [2, 4, 7] или рассеяться/собрать операции, вызванные через методы переотображения адреса [1] в системе памяти, чтобы или разгрузить вычисление непосредственно или сократить количество неудачных обращений в кэш процессора. Оба активных подхода памяти создают когерентность problems|even на унипроцессоре systems|since есть или дополнительные процессоры в системе памяти, воздействующей на данные непосредственно, или основному процессору позволяют относиться к тем же данным через несколько адресов.

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

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

   2. Расширения протокола DSM для активных систем памяти

Наш встроенный контроллер памяти работает последовательности программного кода для реализации согласования протоколов по той же философии, как FLASH многопроцессорных [6]. Тем не менее, контроллер также включает в себя специализированное оборудование, чтобы ускорить выполнение активных протоколов памяти. Наши базовые (не расширенные) работают на основе MSI. Для всех нормальных (не-ре-подключенных) запрашивает память, наш контроллер памяти следует этой базе протоколов. Каждая запись каталога 8 битов шириной. Вектор акционер занимает 4 бита, таким образом, мы можем поддерживать до 4 процессоров. Это может быть расширено увеличивая ширину поля акционера. Эти четыре бита хранят вектор списка акционера если строка кэша находится в общем состоянии или идентификаторе владельца для грязного монопольного состояния. Два бита выделены, чтобы поддержать информацию о состояние строки кэша. Грязный бит указывает, является ли строка кэша в грязное монопольном состояния. Бит AM используется для нашего активного протокола памяти расширения и не используются основным протоколом. Два остающихся бита неиспользуются.

   2.1 Активное расширение памяти

Как пример методов переназначения адреса, порождает проблему когерентности , рисунок 1 показывает что элемент данных D0 в строке кэша C0 отображен некоторым методом переназначения адреса на элементах данных D1; D2 и D3, принадлежащий трем различным строкам кэша C1; C2 и C3, соответственно. Это означает это D1; D2 и D3 представляют те же данные, что и D0 и наши активные расширения протокола памяти должны сохранить их когерентными.Как и в рисунке, если С1 и С2 кэшируются в грязной и общим состоянием, соответственно, процессор может написать новое значение D1, но читать устаревшие значения из D2. Мы расширяем основную когерентность кэша протокол, чтобы осуществить взаимное исключение между кэширующимися состояниями строки, которые отображены друг на друге так, чтобы только одна строка кэша четыре отображенных строки кэша (как в примере выше) могут кэшироваться в одно время. Если процессор получит доступ к другой отображенной строке кэша, то это пострадает неудачное обращение в кэш и наш протокол лишат законной силы старую строку кэша прежде ответ с требуемой строкой кэша.

Для каждого запроса памяти наш протокол сверяется с битом AM перед записью а для требуемой строки кэша. Бит AM из строки кэша указывает, были ли какие-либо данные в строке повторно отображенные и кэшируется процессорами в системе по различным адресам. Если бит AM в нуле, нет никакой возможности нарушения когерентности и протокол ведет себя точно так же, как основной протокол с одной дополнительной гарантией когерентности task|to в будущем, протокол устанавливает биты AM в записях каталога всех строк кэша, которые отображены на требуемую строку. Однако, если бит AM установлен, некоторые повторно отображенные строки кэша (мы коллективно вызываем эти строки R), кэшируются в системе и есть потенциальная проблема когерентности данных. Кэширующиеся состояния R получены, читая соответствующий каталог записи. Если R находится в грязном монопольном состоянии, протокол отправляет запрос владельцу R, чтобы получить новую копию данных, обновляет отображенное значение данных в требуемой строке кэша, отправляют данные запрашиваемой стороне, и записывает полученный кэш обратно. Если R находится в общем состоянии, протокол отправляет запросы аннулирования всем акционерам, чтение требуемой строки кэша из памяти (так как строка чистая) и отправляет данные запрашивающему. В обоих случаях протокол обновляет AM биты в записях каталога всех строк кэша отображенных на требуемую строку.

   2.2 Поддержка Active Memory Transpose

Хотя мы реализовали четыре активных операций с памятью транспонированной матрицы , разреженных матриц Scatter / Gather, связанного списка линеаризации и слияния памяти [5] для экономии места мы транспонировали матрицы в качестве примера.Предположим следующее: квадратная матрица размерности N, А0 является транспонированной матрицей, сопоставлена двум процессорам P0 и P1. Размер строки кэша составляет 128 байтов и размер элемента данных 8 байтов (одно двойное слово), таким образом, одна строка кэша содержит 16 элементов. В определенный момент , как изображен снимок памяти в рисунке 2 и P0 выполняет следующий код:
 for i=0 to N-1
  for j=0 to N-1
   x += A'[i][j];

 
P0 читает строку кэша C0 A0, эти данные отсутствубт в кэше. C0 составленный из 16 двойных слов w00; w10;:::; w150, которые являются тем же как w0; w1;:::; w15 и эти 16 строк кэша C0; C1;:::; C15 A содержат их. P0 и P1 кэшируют C1, C2 и C14 в грязном или совместно используемом состоянии как показано на рисунке. P0 отправляет запрос чтения в основное память и контроллер памяти вызывают надлежащую когерентную обработку.

Обработчик протокола читает запись каталога C0 и проверяет Бит AM. В этом случае бит AM установлен потому что C1, C2 и C14 отображены на C0, и они кэшируются. Таким образом, вместо использования базового протокола вызван наш расширенный протокол. Физический адрес C0 , повторно отображенный в аппаратуре (подробная микроархитектура контроллера может быть найдена в [5]), вычисляется адреса строки кэша отображенный на C0, которые в этом случае являются C0; C1;:::; C15. Так как C0 принадлежит повторно отображенному адресному пространству и повторно отображенное физическое адресное пространство непрерывно, от физического адреса C0 протокол может вычислить позиция C0 в перемещенной матрице (т.е. A0), если зная размерности матрицы и размер каждого элемента матрица в байтах. Эта информация вместе с виртуальным адресом матрицы (т.е. A) сохранен в таблице, которая инициализирована в начале приложения через системный вызов библиотеки. Протокол вычисляет виртуальные адреса C0, C1; ::: C15 и смотрит TLB резидента в памяти контроллера, чтобы вычислить соответствующий 16 физических адресов. Затем, протокол читает записи каталога для каждой из этих строк кэша и проверяет бит (чистая или нет) и вектор акционера. Для C1 мы находим, что он кэшируется P0 в грязном монопольном состоянии. Протокол отправляет запрос в P0 потому что в этой точке у w10 есть устарелое значение и новое значение - w1, находящийся в кэше P0. На запрос получаем ответ от P0, протокол обновляет w10 и также записывает C1 обратно в память. Для C2 мы находим, что это кэшируемый P0 и P1 в общем состоянии, таким образом, протокол отправляет аннулирования к P0 и P1 для этой строки. В этом случае протокол может считайть корректное значение w20 непосредственно из оперативной памяти. Случай для C14 подобен C1 за исключением того, что P1, вместо P0. Для других строк кэша, которые чисты в оперативной памяти, протокол ничего не должен сделать. Теперь, когда протокол вытеснил все кэшируемые строки, повторно отображенные на C0 из кэша P0 и P1 и обновленный данные C0 с новым значения, это готово ответить на P0 с C0. Наконец, протокол обновляет биты AM всех записей каталога строк кэша повторно отображенный на C0. Поскольку C0 теперь кэшируется, биты AM C0; C1;::: ; C15 набор и C0 чистые. Это гарантирует правильность для будущего доступа к любой из этих строк кэша.

Мы описали, как наш Matrix Transpose протокол, осуществляет взаимное исключение между кэшем нормальных и повторно отображенных строк. Однако, это чрезмерно строго, так как это законно кэшировать и нормальные и повторно отображенные строки, если оба находятся в общем состоянии. Мы находим, хотя это для Matrix Transpose, осуществляя взаимный исключение достигается более высокая производительность, потому что все перемещаемые приложения, которые мы исследовали, есть следующий образец совместного использования: процессор сначала читает нормальные строки кэша из части набора данных, присвоенный ему, в конечном счете пишет в него и затем идет дальше считывать и в конечном счете обновить повторно отображенные строки кэша. Поэтому, доступы имеют тенденцию "мигрировать" от одного пространства к другогму. Когда активный контроллер памяти видит запрос чтения на нормальный или повторно отображенный кэш это знает это в конечном счете будет запрос обновления на ту же строку кэша. Далее, не будет никакого доступа от другого кэша между чтением. Таким образом, наши расширения протокола когерентности кэша принимают решение о недействительности всх строк кэша в другом пространстве, отображенном на требуемую строку во время чтения. Это сохраняет обработчик обновления более простым, потому что это он не должен беспокоится о недействительности совместно используемой строки кэша. Однако, мы нашли, что Sparse Matrix Scatter/Gather, делает не показательным миграционный процесс совместного использования, и поэтому мы ослабляем ограничение взаимного исключения в этом случае. Это иллюстрирует преимущество гибких контроллеров памяти с адаптацией протокола когерентности к потребностям приложения.

   2.3 Расширения протокола мультиузла

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

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

   3. Оценка протокола

В этом разделе рассматриваются издержки протокола памяти и связанные с протоколом проблемы производительности. Дополнительные издержки памяти в протоколе активной памяти происходят от увеличения размера кода обработчика протокола, каталога издержки пространства для повторно отображенных строк кэша и пространство, требуемое для хранения отображенной информации в таблице, доступной встроенным протоколам процессора. Как пример увеличения размера кода обработчика, начальный размер кода протокола составляет 20 КБ, но добавление расширения протокола, чтобы поддерживать активную матрицу памяти обсужденную в Разделе 2 увеличивает размер кода протокола до 33 КБ.Sparse Matrix Scatter/Gather, Линеаризация Связанного списка и У Memory-side Merge меняют размеры кода протокола до 24 КБ и 26 КБ соответственно. Издержки пространства для каталога зависят от размер повторно отображенного адресного пространства. Наконец, таблица отображения занимает только 128 байт. Эта дополнительная память издержки независимы от числа узлов в системе, кроме того, что маленькая таблица отображения должна быть тиражирована в каждый узел системы.

Есть много проблем производительности для активных протоколов памяти, не зависят от стандартных протоколы DSM. Мы кратко обсудим некоторые из них. Одна главное потенциальное узкое место в производительности - заполнение контроллера памяти. К службе идет запрос на определенную строку кэша, протоколу, вероятно, придется запрашивать записи каталога всех повторно отображенных строк кэша , и, вероятно, придется взять различные виды базируемых действий на состояниях каталога. Выполнение всех этих поисков каталога в программное обеспечение, работающее на нашем контроллере программируемого ЗУ, было слишком медленным. Вместо этого у нашего контроллера есть специализированный конвейерный аппаратный адрес модуль вычисления, который вычисляет 16 повторно отображенных адресов строки кэша, загрузки записи каталога в специальных аппаратных средствах регистрируют и инициируют любой необходимый доступ памяти данных. Наши обработчики протокола программного обеспечения строго контролируют этот активный блок данных памяти, ударяя баланс между надежностью и производительностью. Как пример среднего числа заполнения контроллера, в системе с одним узлом для 1, 2 и 4 процессоров для нормального заполнения контроллера выполнения 7.7%, 21.3% и 43.2% полного времени выполнения соответственно, в то время как для активного протокола памяти это - 15.5%, 29.4% и 47.8%, хотя нужно помнить, что время выполнения активного протокола памяти меньше, и поэтому проценты заполнения естественно выше.

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

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

   Список литературы

1. Carter J. B. Impulse: Building a Smarter Memory Controller. In Proceedings of the Fifth International Symposium on High Performance Computer Architecture, January 1999.
2. Hall M. Mapping Irregular Applications to DIVA, A PIM-based Data-Intensive Architecture. Supercomputing, Portland, OR, Nov. 1999.
3. Heinrich M., Speight E., Chaudhuri. M. Active Memory Clusters: Effcient Multiprocessing on Commodity Clusters. In Proceedings of the Fourth International Symposium on High-Performance Computing, Lecture Notes in Computer Science, Springer-Verlag, May 2002.
4. Kang Y. FlexRAM: Toward an Advanced Intelligent Memory System. International Conference on Computer Design, October 1999.
5. Kim D., Chaudhuri M., Heinrich M. Leveraging Cache Coherence in Active Memory Systems. In Proceedings of the 16th ACM International Conference on Supercomputing, New York City, June 2002.
6. Kuskin J. The Stanford FLASH Multiprocessor. In Proceedings of the 21st International Symposium on Computer Architecture, pages 302-313, April 1994.
7. Oskin M., Chong F. T., Sherwood T. Active Pages: A Computation Model for Intelligent Memory. In Proceedings of the 25th International Symposium on Computer Architecture, 1998.