В информатике локальность ссылок , также известная как принцип локальности , [1] представляет собой тенденцию процессора повторно обращаться к одному и тому же набору ячеек памяти в течение короткого периода времени. [2] Существует два основных типа локальности ссылок — временная и пространственная локальность. Временная локальность относится к повторному использованию определенных данных и/или ресурсов в течение относительно небольшого периода времени. Пространственная локальность (также называемая локальностью данных [3] ) относится к использованию элементов данных в относительно близких местах хранения. Последовательная локальность, особый случай пространственной локальности, возникает, когда элементы данных располагаются и к ним осуществляется линейный доступ, например, обход элементов в одномерном массиве .
Локальность — это тип предсказуемого поведения, который встречается в компьютерных системах. Системы, которые демонстрируют сильную локальность ссылок, являются отличными кандидатами для оптимизации производительности с помощью таких методов, как кэширование , предварительная выборка для памяти и расширенные предикторы ветвлений ядра процессора.
Существует несколько различных типов местностей отсчета:
Для того, чтобы извлечь выгоду из временной и пространственной локальности, которые встречаются часто, большинство систем хранения информации являются иерархическими . Равноудаленная локальность обычно поддерживается разнообразными нетривиальными инструкциями инкремента процессора. Для локальности ветвления современные процессоры имеют сложные предикторы ветвления, и на основе этого предсказания менеджер памяти процессора пытается собрать и предварительно обработать данные правдоподобных альтернатив.
Существует несколько причин локальности. Эти причины — либо цели, которые нужно достичь, либо обстоятельства, которые нужно принять, в зависимости от аспекта. Причины, перечисленные ниже, не являются разрозненными ; на самом деле, список ниже идет от самого общего случая к частным случаям:
Если большую часть времени значительная часть ссылок агрегируется в кластеры, и если форма этой системы кластеров может быть хорошо предсказана, то ее можно использовать для оптимизации производительности. Существует несколько способов извлечь выгоду из локальности с помощью методов оптимизации . Распространенными методами являются:
Иерархическая память — это аппаратная оптимизация, которая использует преимущества пространственной и временной локальности и может использоваться на нескольких уровнях иерархии памяти. Страничная разбивка , очевидно, выигрывает от временной и пространственной локальности. Кэш — это простой пример использования временной локальности, поскольку это специально разработанная, более быстрая, но меньшая область памяти, обычно используемая для хранения недавно использованных данных и данных рядом с недавно использованными данными, что может привести к потенциальному повышению производительности.
Элементы данных в кэше не обязательно соответствуют элементам данных, которые пространственно близки в основной памяти; однако элементы данных переносятся в кэш по одной строке кэша за раз. Это означает, что пространственная локальность снова важна: если ссылаются на один элемент, несколько соседних элементов также будут перенесены в кэш. Наконец, временная локальность играет роль на самом низком уровне, поскольку результаты, на которые ссылаются очень близко друг к другу, могут храниться в регистрах машины . Некоторые языки программирования (например, C ) позволяют программисту предлагать хранить определенные переменные в регистрах.
Локальность данных — типичная функция обращения к памяти обычных программ (хотя существует множество нерегулярных моделей доступа к памяти). Она делает иерархическую структуру памяти прибыльной. В компьютерах память делится на иерархию, чтобы ускорить доступ к данным. Нижние уровни иерархии памяти, как правило, медленнее, но больше. Таким образом, программа достигнет большей производительности, если она использует память, пока она кэшируется на верхних уровнях иерархии памяти, и избегает переноса других данных на верхние уровни иерархии, которые вытеснят данные, которые будут использоваться в ближайшее время в будущем. Это идеал, и иногда его невозможно достичь.
Типичная иерархия памяти (время доступа и размеры кэша являются приблизительными значениями типичных значений, используемых по состоянию на 2013 год [обновлять]для целей обсуждения; фактические значения и фактическое количество уровней в иерархии могут различаться):
Современные машины склонны считывать блоки более низкой памяти на следующий уровень иерархии памяти. Если это вытесняет используемую память, операционная система пытается предсказать, какие данные будут использоваться реже всего (или позже всего) и переместить их вниз по иерархии памяти. Алгоритмы прогнозирования, как правило, просты, чтобы уменьшить сложность оборудования, хотя они становятся несколько сложнее.
Типичным примером является умножение матриц :
для 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 ] ; Временная локальность вышеприведенного решения обеспечивается, поскольку блок может быть использован несколько раз, прежде чем перейти к следующему, так что он реже перемещается в память и из нее. Пространственная локальность улучшается, поскольку элементы с последовательными адресами памяти, как правило, вытягиваются вверх по иерархии памяти вместе.
