#matrix #cpu-cache #localityofreference
#матрица #cpu-cache #localityofreference
Вопрос:
В настоящее время я рассматриваю матрицу n x n M из 64-разрядных целых элементов, хранящихся в основной памяти в порядке следования строк. У меня есть кэш данных L1 объемом 16 КБ, разделенный на блоки 64B (без L2 или L3). Мой код предназначен для распечатки каждого элемента массива по одному, либо путем обхода матрицы в порядке первой строки, либо в порядке первого столбца.
В случае, когда n = 16 (т. Е. матрица 16 x 16), я насчитал 0 промахов кэша, используя как порядок строк, так и порядок столбцов, поскольку матрица M полностью помещается в кэш размером 16 КБ (для извлечения элемента ей никогда не нужно переходить в основную память). Как бы я справился со случаем, скажем, n = 256 (матрица 256 x 256 из 64-битных целых чисел); т. е. Когда M не полностью помещается в кеш? Должен ли я считать все целые числа, которые не соответствуют промахам, или можно как-то использовать пространственную локальность? Предположим, что кэш изначально пуст.
Комментарии:
1. Я не вижу части «файл» из заголовка? «Кэш» — это общая концепция — ваша ОС обычно имеет кэш в памяти для файлов на диске, но это не кэш размером 16 КБ, разделенный на блоки 64B.
2. @MSalters извинения — я изменил «файл», чтобы не вводить в заблуждение (надеюсь, теперь лучше?). Кроме того, мы должны предположить, что кэш изначально пуст — изменит ли это ответ для n = 16 (т. Е. Приведет к ненулевым промахам)? Предполагая, что пустой catch будет означать, что у меня будет промах для каждого блока, который я вношу в кеш, разве это не будет 32 промаха?
3. Если кэш изначально пуст, то первый доступ должен быть промахом кэша. Поэтому ответ не может быть нулевым. Сколько еще вам нужно будет выяснить. Подсказка: учитывайте не только промахи кэша, но и удаление кэша.
4. @MSalters большое спасибо! Думаю, я разобрался 🙂
Ответ №1:
«0 промахов кэша», похоже, предполагает, что вы начинаете с M, уже находящегося в кэше. Это уже немного подозрительно, но нормально.
Для случая 256×256 вам необходимо смоделировать поведение кэша. У вас должны быть промахи кэша, чтобы внести недостающие записи. Каждый промах кэша приводит не только к запрошенному int, но и к 7 смежным целым числам.