Местоположение ссылки - Locality of reference

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 для я в 0..п2   для j в 0..м3     для k в 0..п4       C[я][j] = C[я][j] + А[я][k] * B[k][j];

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

1 для я в 0..п2   для k в 0..п3     для j в 0..м4       C[я][j] = C[я][j] + А[я][k] * B[k][j];

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

1 для я в 0..п2   для j в 0..м3     темп = C[я][j]4     для k в 0..п5       темп = темп + А[я][k] * B[k][j];6     C[я][j] = темп

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

1 для я в 0..п2   для k в 0..п3     темп = А[я][k]4     для j в 0..м5       C[я][j] = C[я][j] + темп * B[k][j];

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

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

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

 1 для (ii = 0; ii < РАЗМЕР; ii += РАЗМЕР БЛОКА) 2   для (кк = 0; кк < РАЗМЕР; кк += РАЗМЕР БЛОКА) 3     для (jj = 0; jj < РАЗМЕР; jj += РАЗМЕР БЛОКА) 4       макси = мин(ii + РАЗМЕР БЛОКА, РАЗМЕР); 5       для (я = ii; я < макси; я++) 6         maxk = мин(кк + РАЗМЕР БЛОКА, РАЗМЕР); 7         для (k = кк; k < maxk; k++) 8           maxj = мин(jj + РАЗМЕР БЛОКА, РАЗМЕР); 9           для (j = jj; j < maxj; j++)10             C[я][j] = C[я][j] + А[я][k] * B[k][j];

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

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

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

  1. ^ Не путать с принцип локальности по физике.
  2. ^ Уильям., Столлингс (2010). Компьютерная организация и архитектура: проектирование для производительности (8-е изд.). Река Аппер Сэдл, Нью-Джерси: Prentice Hall. ISBN  9780136073734. OCLC  268788976.
  3. ^ а б "NIST Big Data Interoperability Framework: Volume 1", [https://doi.org/10.6028/NIST.SP.1500-1r2 урна: doi: 10.6028 / NIST.SP.1500-1r2
  4. ^ Ахо, Лам, Сетхи и Ульман. «Составители: принципы, методы и инструменты» 2-е изд. Pearson Education, Inc. 2007 г.
  5. ^ "Обзор методов обхода кеша ", JLPEA, том 6, № 2, 2016 г.

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