Справочник - английское объяснение эквидистантности

Question

Я читаю статью в Википедии о ссылочной локации, и я не могу не найти объяснение, приведенное для эквидистантной местности, довольно загадочным.

Я не могу понять этого, и мне было интересно, может ли кто-нибудь попытаться объяснить это простым английским языком?

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

Что это означает с " петлей, получающей доступ к местоположениям в эквидистантном образце "? Расположены ли места на одинаковом расстоянии друг от друга?

Что это за фигня о том, что " пространственно-временное координатное пространство является пунктирной линией "? Это не имеет смысла для меня.

Если бы кто-нибудь мог дать какое-то разъяснение о том, что означает местность Эквидистант, это было бы здорово!

Answer 1

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

Возьмем, к примеру, массив, если вы делаете что-то вроде этого (пример C++):

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> test = { 1, 2, 3, 4, 5};
    for(int& i: test)
    {
        std::cout << i << std::endl;
    }
}

В векторе (или массиве на других языках) элементы упакованы в непрерывный блок с фиксированными шагами. Так что если первый элемент test находится по адресу Xтогда второй элемент будет X+Yтретий на X+2Y, ..., Таким образом, сам вектор является очень простым примером пространственной локализации, и еще лучше локализация очень предсказуема. Кроме того, к элементам осуществляется доступ в узком цикле, поэтому мы также имеем хорошую временную пространственность. Поскольку к элементам также осуществляется последовательный доступ, мы имеем равноудаленную пространственность в "пространстве-времени". Это означает, что как только процессор распознает X+Y, X+2Y, X+3Y шаблон, который он ищет, может начать извлекать будущие элементы в кеше.

Вы можете сравнить это, например, с:

#include <iostream>
#include <list>

int main()
{
    std::list<int> test = { 1, 2, 3, 4, 5};
    for(int& i: test)
    {
        std::cout << i << std::endl;
    }
}

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

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <iterator>

int main()
{
    std::vector<int> test = { 1, 2, 3, 4, 5 };
    std::vector<unsigned int> indices = { 0, 1, 2, 3, 4 };
    std::random_device rd;
    std::shuffle(std::begin(indices), std::end(indices), std::mt19937 { rd() });
    for (unsigned int& i : indices)
    {
        std::cout << test[i] << std::endl;
    }
}

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

Answer 2

петля доступа к местоположениям в эквидистантном паттерне

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

Таким образом, эквидистантная локальность одинакова для каждой итерации.