Местоположение ссылки

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

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

Типы местности

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Регистры ЦП (8–256 регистров) – немедленный доступ со скоростью самого внутреннего ядра процессора.
• L1 Кэш ЦП (от 32 КБ до 512 КБ ) — быстрый доступ, скорость самой внутренней шины памяти принадлежит исключительно каждому ядру.
• Кэш ЦП L2 (от 128 КБ до 24 МБ ) — немного более медленный доступ, при этом скорость шины памяти распределяется между двумя ядрами.
• Кэш-память ЦП L3 (от 2 МБ до максимум 64 МБ ) — еще более медленный доступ, при этом скорость шины памяти распределяется между еще большим количеством ядер одного и того же процессора.
• Основная физическая память ( ОЗУ ) (от 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];

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

См. также

• Алгоритм, не обращающий внимания на кэш
• Алгоритм избегания общения
• Фрагментация файловой системы
• Разделенное глобальное адресное пространство
• Порядок строк и столбцов
• Масштабируемая местность
• Блокнот памяти
• Рабочий набор
• эвристика

Библиография

• Питер Дж. Деннинг , «Принцип локальности» , Сообщения ACM , том 48, выпуск 7, (2005), страницы 19–24.
• Питер Дж. Деннинг, Стюарт К. Шварц, «Свойства модели рабочего набора» , Communications of the ACM , том 15, выпуск 3 (март 1972 г.), страницы 191–198