Какова местность ссылок?

Ответ 1

Это не имело бы значения, если бы ваш компьютер был заполнен сверхбыстрой памятью.

Но, к сожалению, дело не в этом, а память компьютера выглядит примерно так ¹:

+----------+
| CPU      |  <<-- Our beloved CPU, superfast and always hungry for more data.
+----------+
|L1 - Cache|  <<-- works at 100% of CPU speed (fast)
+----------+
|L2 - Cache|  <<-- works at 25% of CPU speed (medium)
+----+-----+
     |
     |      <<-- This thin wire is the memory bus, it has limited bandwidth.
+----+-----+  <<-- works at 10% of CPU speed.
| main-mem |  <<-- The main memory is big but slow (because we are cheap-skates)
+----------+
     |
     |     <<-- Even slower wire to the harddisk
+----+-----+
| harddisk | <<-- Works at 0,001% of CPU speed
+----------+ 

Пространственная локация
На этой диаграмме чем ближе данные к ЦП, тем быстрее цП может добраться до него.
Это связано с Spacial Locality. Данные имеют пространственную локализацию, если они расположены близко друг к другу в памяти.
Из-за дешевых коньков, которые мы являемся оперативной памятью, на самом деле это не произвольный доступ, это действительно Slow if random, less slow if accessed sequentially Access Memory SIRLSIAS-AM. DDR SDRAM передает одну серию из 32 или 64 байтов для одной команды чтения или записи.
Вот почему разумно хранить связанные данные близко друг к другу, чтобы вы могли последовательно читать кучу данных и экономить время.

Временная местность
Данные остаются в основной памяти, но не могут оставаться в кеше, иначе кэш перестанет быть полезным. Только самые последние использованные данные могут быть найдены в кеше; старые данные выталкиваются.
Это связано с temporal locality. Данные имеют сильную временную локализацию, если к ним обращаются одновременно.
Это важно, потому что если элемент A находится в кэше (хорошо), то, скорее всего, элемент B также находится в кэше.

Сноска 1:

Это упрощение с процентами, составленными для примера, но оно дает правильное представление о порядке величин для типичных процессоров.

На самом деле задержка и пропускная способность являются отдельными факторами, причем задержку труднее улучшить для памяти дальше от процессора. Но предварительная выборка HW и/или exec-of-exec может скрыть задержку в некоторых случаях, например, циклическое выполнение по массиву. При непредсказуемых шаблонах доступа эффективная пропускная способность памяти может быть намного ниже, чем 10% кэша L1d.

Эта упрощенная версия также исключает эффекты TLB (локальность гранулярности страницы) и локальность DRAM-страницы. (Не то же самое, что страницы виртуальной памяти). Более подробное описание аппаратного обеспечения памяти и программного обеспечения для него см. в разделе Что должен знать каждый программист о памяти?

Связано: Почему размер кэша L1 меньше, чем размер кэша L2 в большинстве процессоров? объясняет, почему многоуровневая иерархия кэша необходима для получения комбинации задержки/пропускной способности и емкости (и скорость попадания) мы хотим.

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

В многоядерных процессорах кэш-память L1i/L1d и L2 обычно является частным кешем для каждого ядра с общим кешем L3. Разные ядра должны конкурировать друг с другом за пропускную способность L3 и память, но у каждого есть своя пропускная способность L1 и L2. См. Как такое быстрое кеширование? для получения эталонного результата от двухъядерного процессора IvyBridge 3GHz: совокупная пропускная способность чтения кеша L1d на обоих ядрах 186 ГБ/с против 9,6 ГБ/с полосы пропускания для чтения DRAM с оба ядра активны. (Таким образом, память = 10% L1d для одноядерных процессоров является хорошей оценкой пропускной способности для процессоров настольных компьютеров этого поколения, имеющих только 128-битные пути загрузки/хранения данных SIMD). И латентность L1d 1,4 нс против латентности DRAM 72 нс

Ответ 2

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

Ответ 3

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

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

Пространственная локальность позволяет процессору улучшить производительность доступа к памяти благодаря:

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

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

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

Более интересной формой временной локализации является то, что два (или более) смежных во времени доступа, наблюдаемые один раз, могут повторяться снова вместе. То есть - если вы однажды получили доступ к адресу A и вскоре после этого адреса B, и в какой-то более поздний момент ЦП обнаружит другой доступ к адресу A - он может предсказать, что вы, скорее всего, скоро снова получите доступ к B, и продолжите предварительную выборку заранее. Устройства предварительной выборки, предназначенные для извлечения и прогнозирования этого типа отношений (временные средства предварительной выборки), часто используют относительно большой объем памяти для записи многих таких отношений. (См. Предварительную выборку Маркова, а в последнее время ISB, STMS, Domino и т.д.)

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