Временная и пространственная локальность с массивами

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

В Примере, подобном этому: А[0][1], А[0] [2], А[0] [3].... etc

Демонстрирует ли это временную локальность? Я вижу, что одна и та же строка доступна много раз, но с разными смещениями... означает ли это, что доступ осуществляется по другому адресу?

Кроме того, правильно ли я говорю, что пример, подобный этому: А [1], А[2], А[3]... etc

Демонстрирует пространственную локальность?

Надеюсь, что некоторые разъяснения о том, как временная и пространственная локальность работают в реальном коде, помогут мне лучше понять их.

4 29
arrays caching cpu-architecture cpu-cache

4 ответа:

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

Говорят, что последовательность ссылок имеет локальность spatial, Если вещи, на которые ссылаются близко во времени, также близки в пространстве (ближайшие адреса памяти, ближайшие сектора на диске и т. д.). Последовательность, как говорят, имеет локальность temporal, Если доступы к одной и той же вещи сгруппированы во времени.

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

Ваш первый пример 

A[0][1], A[0][2], A[0][3]

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

Ваш второй пример 

A[1], A[2], A[3]

Также показывает пространственную локальность, но не временную локальность.

Вот пример, который показывает темпоральную локальность 
A[1], A[2000], A[1], A[1], A[2000], A[30], A[30], A[2000], A[30], A[2000], A[30], A[4], A[4]
60

Простыми словами,

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

Пространственная локальность: концепция, согласно которой вероятность обращения к ресурсу равна выше, если на ресурс рядом с ним просто ссылались.

Источник(Ы): Википедия

12

Вот пример кода с локальностью: 

var sum = 0;
for (i = 0; i < n; i++){
  for(j=0; j < m ; j++){
    sum += a[i][j];
    }
}
return sum;

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

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

2

Временная локальность является частным случаем пространственной локальности .

0