поведение кэша при избыточной записи - PullRequest
Новая
       34

поведение кэша при избыточной записи

2 голосов
/ 23 июля 2010

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

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

Например, существует ли оптимизация, которая сравнивает два значения и отбрасывает избыточную запись в основную память?В частности, как основные процессоры справляются с этим?Как насчет того, когда значение является специальным значением, например 0?Если такой оптимизации нет даже для специального значения, такого как 0, есть ли причина?

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

Делать это в коде не имеет смысла, так как сама инструкция ветвления может вызвать ненужную ошибку кэша (if (buf [i]) {...})

Ответы [ 3 ]

1 голос
/ 27 июля 2010

Предлагаемая вами аппаратная оптимизация не снизит задержку. Рассмотрим операции на самом низком уровне:

  1. Старое значение в местоположении загружается из кэша в ЦП (при условии, что оно уже находится в кэше).
  2. Сравниваются старые и новые значения.
  3. Если старое и новое значения различаются, новое значение записывается в кэш. В противном случае оно игнорируется.

Шаг 1 на самом деле может занять больше времени, чем шаги 2 и 3. Это потому, что шаги 2 и 3 не могут начаться, пока старое значение из шага 1 не будет занесено в ЦП. Ситуация была бы такой же, если бы она была реализована в программном обеспечении.

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

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

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

http://blogs.amd.com/developer/tag/sse4a/

Читать
  • попадание в кэш: данные считываются из строки кэша в целевой регистр
  • Отсутствие кэша: данные перемещаются из памяти в кэш и считываются в целевой регистр
Написать
  • попадание в кэш: данные перемещаются из регистра в строку кэша
  • Отсутствие кэша: строка кэша извлекается в кэш, а данные из регистра перемещаются в строку кэша
1 голос
/ 18 марта 2012

Я не знаю ни одного процессора, который бы выполнял описанную вами оптимизацию - исключая записи в чистые строки кэша, которые не изменили бы значение - но это хороший вопрос, хорошая идея, великие умы думают одинаково и все такое. *

Я написал очень большой ответ, а потом вспомнил: в литературе это называется «Тихие магазины». См. «Бесшумные магазины бесплатно», К. Лепак и М. Липасти, UWisc, MICRO-33, 2000.

Во всяком случае, в своем ответе я описал некоторые проблемы реализации.

Кстати, подобные темы часто обсуждаются в новостной группе USEnet comp.arch.

Я также пишу о них в моей вики, http://comp -arch.net

0 голосов
/ 26 июля 2010

Это не ответ на ваш первоначальный вопрос о компьютерной архитектуре, но может иметь отношение к вашей цели.

В этом обсуждении весь индекс массива начинается с нуля.

Предполагая, что n намного меньше size , измените ваш алгоритм так, чтобы он сохранял две части информации:

  1. Массив размер
  2. Массив n и счетчик, используемый для эмуляции установленного контейнера.Допускаются повторяющиеся значения.

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

Когда необходимо очистить полноразмерный массив, получите каждое значение, хранящееся в контейнере набора (который будет содержать k , среди прочего), и установите каждый соответствующий индексв полноразмерном массиве к нулю.

Можно также использовать похожую технику, известную как двухуровневая гистограмма или радикальная гистограмма.

Сохраняются два фрагмента информации:

  1. Массив size
  2. Логический массив ceil(size / M), где M это основа.ceil - функция потолка.

Каждый раз, когда ненулевое значение записывается в индекс k в полноразмерном массиве, элементfloor(k / M) в логическом массиве должен быть отмечен.

Допустим, bool_array[j] отмечен.Это соответствует диапазону от j*M до (j+1)*M-1 в полноразмерном массиве.

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

...