Место ссылки

Для проверки этой статьи нужны дополнительные цитаты . Помогите улучшить эту статью , добавив ссылки на надежные источники . Неподтвержденные материалы могут быть оспорены и удалены. Найти источники:  «Местоположение ссылки» – новости  · газеты  · книги  · ученый  · JSTOR ( июль 2008 г. ) ( Узнайте, как и когда удалять это сообщение )

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Типичным примером является умножение матриц :

для i в 0 .. n    для j в 0 .. м    для k в 0 .. p    С [ я ][ j ] = С [ я ][ j ] + А [ я ][ к ] * В [ к ][ j ] ;      

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

для i в 0 .. n    для k в 0 .. p    для j в 0 .. м    С [ я ][ j ] = С [ я ][ j ] + А [ я ][ к ] * В [ к ][ j ] ;      

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

для i в 0 .. n    для j в 0 .. м    температура = C [ i ][ j ]   для k в 0 .. p    темп = темп + A [ i ][ k ] * B [ k ][ j ] ;       C [ i ][ j ] = темп  

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

для i в 0 .. n    для k в 0 .. p    темп = А [ я ][ к ]   для j в 0 .. м    C [ i ][ j ] = C [ i ][ j ] + темп * B [ k ][ j ] ;      

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

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

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

для ( ii = 0 ; ii < РАЗМЕР ; ii += РАЗМЕР_БЛОКА )          для ( кк = 0 ; кк < РАЗМЕР ; кк += РАЗМЕР_БЛОКА )          для ( jj = 0 ; jj < РАЗМЕР ; jj += РАЗМЕР_БЛОКА )          макси = мин ( ii + РАЗМЕР_БЛОКА , РАЗМЕР ) ;      для ( i = ii ; i < макси ; i ++ )        maxk = min ( kk + РАЗМЕР_БЛОКА , РАЗМЕР ) ;      для ( k = kk ; k < maxk ; k ++ )        maxj = min ( jj + РАЗМЕР_БЛОКА , РАЗМЕР ) ;      для ( j = jj ; j < maxj ; j ++ )        С [ я ][ j ] = С [ я ][ j ] + А [ я ][ к ] * В [ к ][ j ] ;      

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

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

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