Относится ли пространственная локальность, обеспечиваемая кешем, к виртуальной памяти, физической памяти или к обоим?

Question

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

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

• Когда мы определяем массив или объектструктура нединамически или динамически (через malloc ()), верно ли, что такой массив или объект размещается непрерывно?Относится ли «смежный» к виртуальной памяти или физической памяти или к обоим?

Если пространственная локальность кэша предназначена для физической памяти, а не обязательно для виртуальной памяти, и ОС может выделять программу на C виртуальноне обязательно физически смежные массивы, как мы можем написать программу, которая использует пространственную локальность кэша?

Спасибо.

Answer 1

Предположим, что вы используете язык программирования, который поддерживает только одномерные массивы. Допустим, у вас есть матрица 3x3.Вы реализуете двумерные массивы с помощью

a [i, j] = a (i*3 + j)

Если вы структурируете свой доступ к массиву.Если вы перебираете элементы массива, если индекс внешнего цикла равен i, а индекс внутреннего цикла равен j, вы получаете доступ в следующем порядке:

a(0), a(1), a(2), ..... a(8)

Если вы делаете j индексом внешнего цикла, а i - внутреннимИндекс цикла, к которому вы обращаетесь по порядку:

a(0), a(3), a(6), a(1), a(4), a(7), a(2), a(5), a(8)

Вы прыгаете в своем массиве.Этот скачок вызывает хаос с кешами, потому что кеши ожидают захват памяти в группах.

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

Answer 2

1) На самом деле и то и другое, но почему это не так.

2) Кэши работают с блоками данных, называемыми линиями, а байты в строке являются как виртуальными, так и физически смежными.Типичные размеры строки составляют 16,32,64 байта.Две смежные строки кэша должны быть физически смежными, если они находятся на одной странице.Типичные размеры страниц составляют 4,8,16 К. Таким образом, машина с 32-байтовой строкой кэша и 4K базовой страницы имеет 128 строк на страницу.

3,4) В элементах C структуры, объединения или массивапрактически смежные.От операционной системы зависит, будет ли она физически смежной.

(1) Часть 2: Существует еще один кэш, называемый буфером преобразования просмотра (TLB), в котором хранятся недавно использованные отображения страниц.Без такого механизма для каждой ссылки на память потребовались бы две ссылки на физическую память: одна для загрузки преобразования адресов памяти, которая затем применялась бы для генерации требуемой ссылки на память.

Предположим, что в вашем TLB было 32 записи (глупо малов эти дни), и у вас был код, который обходил массив следующим образом:

char *p;
for (p = array; p < array + 4096; p++) {
     char *q;
     for (q = p; q < p + 32 * 4096; q += 4096) {
           *q += 1;
     }
}

Вы бы эффективно имитировали машину без TLB, поскольку каждая ссылка на память '* q' будет отсутствовать в TLB инеобходимо извлекать из памяти.

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