Местонахождение ссылки - Locality of reference

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

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

Типы населенных пунктов

Существует несколько различных типов справочной местности:

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

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

Актуальность

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

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

Общее использование

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

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

Использование пространственной и временной местности

Иерархическая память

Основная статья: Иерархия памяти

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

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

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

Типичная иерархия памяти (время доступа и размеры кэша являются приблизительными значениями, используемыми с 2013 года для целей обсуждения; фактические значения и фактическое количество уровней в иерархии различаются):

  • Регистры процессора (8–256 регистров) - немедленный доступ со скоростью внутреннего ядра процессора
  • Кеши ЦП L1 (от 32 КБ до 512  КБ ) - быстрый доступ со скоростью внутренней шины памяти, принадлежащей исключительно каждому ядру
  • Кеши ЦП L2 (от 128 КБ до 24  МБ ) - немного более медленный доступ, со скоростью шины памяти, разделяемой между двойниками ядер
  • Кеши ЦП L3 (от 2 МБ до 32  МБ ) - еще более медленный доступ, при этом скорость шины памяти распределяется между еще большим количеством ядер одного процессора
  • Основная физическая память ( RAM ) (от 256 МБ до 64  ГБ ) - медленный доступ, скорость которого ограничена пространственными расстояниями и общими аппаратными интерфейсами между процессором и модулями памяти на материнской плате.
  • Диск ( виртуальная память , файловая система ) (от 1 ГБ до 256  ТБ ) - очень медленный из-за более узкого (по разрядности), физически гораздо более длинного канала данных между основной платой компьютера и дисковыми устройствами, а также из-за требуется посторонний программный протокол поверх медленного аппаратного интерфейса
  • Удаленная память (другие компьютеры или облако) (практически без ограничений) - скорость варьируется от очень медленной до очень медленной.

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

Умножение матриц

Типичный пример - матричное умножение : 

for i in 0..n
  for j in 0..m
    for k in 0..p
      C[i][j] = C[i][j] + A[i][k] * B[k][j];

При изменении порядка цикла для jи kускорение умножения больших матриц становится значительным, по крайней мере, для языков, в которых непрерывные элементы массива помещаются в последнее измерение. Это не изменит математический результат, но повысит эффективность. В этом случае «большой» означает, приблизительно, более 100 000 элементов в каждой матрице или достаточное количество адресуемой памяти, так что матрицы не помещаются в кэш-память L1 и L2. 

for i in 0..n
  for k in 0..p
    for j in 0..m
      C[i][j] = C[i][j] + A[i][k] * B[k][j];

Причина этого ускорения заключается в том, что в первом случае операции чтения A[i][k]находятся в кеше (поскольку kиндекс является непрерывным последним измерением), но B[k][j]нет, поэтому существует штраф за промахи в кеше B[k][j]. C[i][j]не имеет значения, потому что его можно поднять из внутреннего цикла - переменная цикла есть k. 

for i in 0..n
  for j in 0..m
    temp = C[i][j]
    for k in 0..p
      temp = temp + A[i][k] * B[k][j];
    C[i][j] = temp

Во втором случае операции чтения и записи C[i][j]находятся в кеше, чтение B[k][j]- в кеше, а чтение A[i][k]может быть выведено из внутреннего цикла. 

for i in 0..n
  for k in 0..p
    temp = A[i][k]
    for j in 0..m
      C[i][j] = C[i][j] + temp * B[k][j];

Таким образом, во втором примере нет штрафа за промахи в кэше во внутреннем цикле, в то время как в первом примере штраф за кеширование.

На процессоре 2014 года второй вариант примерно в пять раз быстрее первого, если он написан на C и скомпилирован с помощью gcc -O3. (Тщательное изучение дизассемблированного кода показывает, что в первом случае GCC использует инструкции SIMD, а во втором - нет, но потери кэша намного хуже, чем усиление SIMD.)

Временная локальность также может быть улучшена в приведенном выше примере с помощью техники, называемой блокировкой . Большую матрицу можно разделить на подматрицы равного размера, чтобы на меньшие блоки можно было ссылаться (умножаться) несколько раз, пока они находятся в памяти. Обратите внимание, что этот пример работает для квадратных матриц размеров SIZE x SIZE, но его можно легко расширить для произвольных матриц, заменив SIZE_I, SIZE_J и SIZE_K там, где это необходимо. 

for (ii = 0; ii < SIZE; ii += BLOCK_SIZE)
  for (kk = 0; kk < SIZE; kk += BLOCK_SIZE)
    for (jj = 0; jj < SIZE; jj += BLOCK_SIZE)
      maxi = min(ii + BLOCK_SIZE, SIZE);
      for (i = ii; i < maxi; i++)
        maxk = min(kk + BLOCK_SIZE, SIZE);
        for (k = kk; k < maxk; k++)
          maxj = min(jj + BLOCK_SIZE, SIZE);
          for (j = jj; j < maxj; j++)
            C[i][j] = C[i][j] + A[i][k] * B[k][j];

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

Смотрите также

использованная литература

Список используемой литературы