Понимание пространственной и временной локализации - PullRequest
Новая
       63

Понимание пространственной и временной локализации

0 голосов
/ 04 мая 2018

Я готовился к финалу своей архитектуры и наткнулся на следующие строки кода: 

for(i = 0; i <= N ;i++){
   a[i] = b[i] + c[i]; 
}

Вопрос заключается в следующем: «Как этот фрагмент кода демонстрирует примеры временной и пространственной локальности? Обязательно рассмотрите ссылки на память для данных и инструкций. "

Что касается пространственной локальности, я полагаю, что код демонстрирует это путем доступа к смежным ячейкам памяти (a [0], затем a [i] и т. Д.). Однако мое замешательство связано с временной локализацией. Я не уверен, как этот фрагмент кода ссылается на то же место в течение небольшого периода времени? Любая помощь будет принята с благодарностью.

Ответы [ 2 ]

0 голосов
/ 04 мая 2018

Я не уверен, как этот фрагмент кода ссылается на то же место в течение небольшого промежутка времени.

В дополнение к ответу txtechhelp , инструкции , составляющие цикл for, также сохраняются в памяти. Эти инструкции «выбираются» из памяти / кэша каждый раз, когда они выполняются. Поскольку каждая из этих инструкций выполняется N + 1 раз за очень короткий промежуток времени, это демонстрирует временную локализацию.

0 голосов
/ 04 мая 2018

Я не уверен, как этот фрагмент кода ссылается на то же место в течение небольшого промежутка времени?

Как уже отмечалось, к переменной i обращаются довольно часто, возьмем следующую строку кода в вашем примере: 

a[i] = b[i] + c[i];

В этом примере a, b и c все предположительно относятся к типам массивов, указывающим на разные области памяти (даже если смежные, все же разные); однако переменная i равна read каждый раз, когда на нее ссылаются, чтобы затем определить местоположение массива для ссылки.

Думайте об этом так: 

get i from memory and store value in register x.
get value of b + [value in register x] from memory, store in register b.
get i from memory and store value in register y
get value of c + [value in register y] from memory, store in register c.
get i from memory and store value in register z
add value of [register b] to value in [register c] and store in memory location a + [value in register z]

Оптимизирующий компилятор, скорее всего, увидит эту временную локальность и вместо этого сделает что-то похожее на следующее: 

get i from memory and store value in register i.
get value of b + [value in register i] from memory, store in register b.
get value of c + [value in register i] from memory, store in register c.
add value of [register b] to value in [register c] and store in memory location a + [value in register i]

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

Надеюсь, это поможет.

...