В информатике локальность ссылки , также известная как принцип локальности , [1] — это тенденция процессора многократно обращаться к одному и тому же набору ячеек памяти в течение короткого периода времени. [2] Существует два основных типа эталонной локальности – временная и пространственная. Временная локальность означает повторное использование определенных данных и/или ресурсов в течение относительно небольшого периода времени. Пространственная локальность (также называемая локальностью данных [3] ) относится к использованию элементов данных в относительно близких местах хранения. Последовательная локальность, особый случай пространственной локальности, возникает, когда элементы данных упорядочены и доступны к ним линейно, например, при перемещении элементов в одномерном массиве .
Локальность — это тип предсказуемого поведения, которое происходит в компьютерных системах. Системы, которые демонстрируют сильную локальность ссылок, являются отличными кандидатами для оптимизации производительности за счет использования таких методов, как кэширование , предварительная выборка для памяти и расширенные средства прогнозирования ветвей ядра процессора.
Существует несколько различных типов локальности ссылки:
Чтобы извлечь выгоду из часто встречающейся временной и пространственной локализации, большинство систем хранения информации являются иерархическими . Эквидистантная локальность обычно поддерживается разнообразными нетривиальными инструкциями приращения процессора. Для локальности ветвей современные процессоры имеют сложные предсказатели ветвей, и на основе этого предсказания диспетчер памяти процессора пытается собрать и предварительно обработать данные о возможных альтернативах.
Причин локальности несколько. Этими причинами являются либо цели, которых необходимо достичь, либо обстоятельства, которые необходимо принять, в зависимости от аспекта. Приведенные ниже причины не являются несовместимыми ; Фактически, приведенный ниже список идет от самого общего случая к частным случаям:
Если большую часть времени значительная часть ссылок объединяется в кластеры и если форму этой системы кластеров можно хорошо предсказать, то ее можно использовать для оптимизации производительности. Существует несколько способов извлечь выгоду из локальности, используя методы оптимизации . Распространенными методами являются:
Иерархическая память — это аппаратная оптимизация, которая использует преимущества пространственной и временной локальности и может использоваться на нескольких уровнях иерархии памяти. Очевидно, что пейджинг выигрывает от временной и пространственной локальности. Кэш — это простой пример использования временной локальности, поскольку он представляет собой специально разработанную, более быструю, но меньшую область памяти, обычно используемую для хранения недавно использованных данных и данных рядом с недавно использованными данными, что может привести к потенциальному увеличению производительности.
Элементы данных в кэше не обязательно соответствуют элементам данных, которые пространственно близки в основной памяти; однако элементы данных помещаются в кэш по одной строке за раз. Это означает, что пространственная локальность снова важна: если есть ссылка на один элемент, несколько соседних элементов также будут перенесены в кеш. Наконец, временная локальность играет роль на самом низком уровне, поскольку результаты, которые очень тесно связаны друг с другом, могут храниться в машинных регистрах . Некоторые языки программирования (например, C ) позволяют программисту предлагать хранить определенные переменные в регистрах.
Локальность данных — это типичная особенность обращения к памяти в обычных программах (хотя существует множество нестандартных шаблонов доступа к памяти). Это делает иерархическую структуру памяти выгодной. В компьютерах память разделена на иерархию, чтобы ускорить доступ к данным. Нижние уровни иерархии памяти, как правило, медленнее, но крупнее. Таким образом, программа достигнет большей производительности, если она использует память, пока она кэшируется на верхних уровнях иерархии памяти, и избегает переноса других данных на верхние уровни иерархии, которые вытеснят данные, которые будут использоваться вскоре в будущем. Это идеал, и иногда его невозможно достичь.
Типичная иерархия памяти (время доступа и размеры кэша являются приблизительными значениями, используемыми по состоянию на 2013 год [обновлять]для целей обсуждения; фактические значения и фактическое количество уровней в иерархии различаются):
Современные машины имеют тенденцию считывать блоки меньшей памяти на следующий уровень иерархии памяти. Если это вытесняет используемую память, операционная система пытается предсказать, к каким данным будет обращаться меньше всего (или позже), и переместить их вниз по иерархии памяти. Алгоритмы прогнозирования, как правило, просты, чтобы уменьшить сложность оборудования, хотя они становятся несколько сложнее.
Типичным примером является умножение матриц :
для меня в 0 .. н для j в 0 .. м для k в 0..p _ _ C [ я ][ j ] знак равно C [ я ][ j ] + A [ я ][ k ] * B [ k ][ j ] ; При переключении порядка цикла для jи kускорение умножения больших матриц становится существенным, по крайней мере, для языков, которые помещают смежные элементы массива в последнее измерение. Это не изменит математический результат, но повысит эффективность. В данном случае «большой» означает примерно более 100 000 элементов в каждой матрице или достаточно адресной памяти, так что матрицы не помещаются в кэши L1 и L2.
для меня в 0 .. н для k в 0..p _ _ для j в 0 .. м C [ я ][ j ] знак равно C [ я ][ j ] + A [ я ][ k ] * B [ k ][ j ] ; Причина такого ускорения заключается в том, что в первом случае операции чтения A[i][k]находятся в кеше (поскольку kиндекс является непрерывным, последним измерением), но B[k][j]это не так, поэтому существует штраф за промах в кеше для B[k][j]. C[i][j]не имеет значения, поскольку его можно вытащить из внутреннего цикла — там есть переменная цикла k.
для меня в 0 .. н для j в 0 .. м температура = C [ я ][ j ] для k в 0..p _ _ температура = температура + A [ i ][ k ] * B [ k ] [ j ] ; C [ я ][ j ] = температура Во втором случае чтение и запись C[i][j]находятся в кеше, чтение B[k][j]находится в кеше, а чтение A[i][k]может быть вынесено из внутреннего цикла.
для меня в 0 .. н для k в 0..p _ _ температура = А [ я ][ к ] для j в 0 .. м 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, где это необходимо.
для ( ii = 0 ; ii < РАЗМЕР ; ii += BLOCK_SIZE ) for ( kk = 0 ; kk < SIZE ; kk += BLOCK_SIZE ) для ( jj = 0 ; jj < РАЗМЕР ; jj += BLOCK_SIZE ) макси = мин ( ii + BLOCK_SIZE , РАЗМЕР ) ; для ( я = ii ; я < макси ; я ++ ) Макск = мин ( кк + BLOCK_SIZE , РАЗМЕР ) ; для ( k = kk ; k < maxk ; k ++ ) maxj = min ( jj + BLOCK_SIZE , SIZE ) ; для ( j = jj ; j < maxj ; j ++ ) C [ я ][ j ] знак равно C [ я ][ j ] + A [ я ][ k ] * B [ k ][ j ] ; Временная локальность приведенного выше решения обеспечивается тем, что блок можно использовать несколько раз, прежде чем двигаться дальше, поэтому он реже перемещается в память и из нее. Пространственная локальность улучшается, поскольку элементы с последовательными адресами памяти имеют тенденцию объединяться вверх по иерархии памяти.
