Моделирование работы кэш памяти, Not recently Used

@Qazan · Регистрация: 30.04.2013

Студворк — интернет-сервис помощи студентам

Добрый день!

Написал программу - модель кэша.

Кэш состоит из групп.
Группа состоит из записей.

Каждая запись имеет флаги чтения, записи и присутствия.

Бит присутствия заполняется при первом обращений к записи и более не изменяется.
Бит чтения заполняется при доступе на запись или чтение.
Бит записи заполняется только при доступе на запись.

Имеется параметр - размер пространственной локальности.
Этим параметром кэш разбивается на участки равного размера.

В случае кэш-промаха происходит полное чтение участка к записи которого происходил доступ.

Также кэш имеет счетчик обращений.

Вопрос: должен ли изменятся счетчик при "подкачке" записей?

А также необходимо ли устанавливать бит чтения в 1 у таких "подкачанных" записей?

Добавлено через 1 час 52 минуты
Скорее вопрос такой: Считать ли проверку кэш-попадания обращением?

Или же полноценное обращение это когда мы изменяем флаги и возможно меняем содержимое диска?
А проверку адреса на предмет кэш-попадания можно сделать не изменяющей состояния?

Т.е. так:
Проверить было ли кэш попадание.
если нет, то

1. Подгрузить левую окрестность нашего адреса
2. Обратиться на чтение или запись по данному адресу
3. Прочитать правую окрестность точки.

Итого здесь будет N обращений, включая обращение по исходному адресу.
если N это размер окрестности(пространственной локальности).

Пример:
Допустим мы при каждом обращений подгружаем 1024 записи. Изначально кэш чист.

Первое обращение идет по адресу 413.
Проверяем его получаем кэш промах

Делаем обращения на чтение 0 - 412 записей из диска.
Делаем исходное обращение по 413. (допустим на запись)
Делаем обращения на чтение 414 - 1023 записей из диска.

Итого на счетчике кэша имеем 1024 обращения.

Счетчик используется для того, чтобы на Nом обращений занулять все флаги обращения, поскольку алгоритм NRU.

@ViktorFX · 15.10.2018, 01:56

Сообщение от Qazan

Также кэш имеет счетчик обращений.

Обращений для чего (чтение,записи?)

Сообщение от Qazan

Считать ли проверку кэш-попадания обращением?

Ну если счетчик работает и на чтение, то проверку осуществляему чтением я бы считал.

Сообщение от Qazan

Или же полноценное обращение это когда

Все зависит от реализованой вами модели, и смысла вложенного в слово "полноценный".

Сообщение от Qazan

А проверку адреса на предмет кэш-попадания можно сделать не изменяющей состояния?

Состояние я так понимаю это :

Сообщение от Qazan

Бит присутствия заполняется при первом обращений к записи и более не изменяется.

Ну вы же обращаетесь чтением для проверки.
Это мне вообще не понятно. Вы проверите, обнаружите что там пусто да и вся запись пуста и проделаете N обращений? А в перспективе все время будете перепроверять поскольку бит присутствия не изменяется? А не проще ли если провереное место пустое (что ко всему прочему портит всю запись) изменить бит присутствия?

А это точно Джава? (с)

@Qazan · 15.10.2018, 20:23 **[ТС]**

Сообщение от ViktorFX

А это точно Джава? (с)

На Java писал

: https://bitbucket.org/Rakhim

Ссылка на место где происходит считывание элемента кэша, и, в случае кэш-промаха, считывание некоторой окрестности ("локали").

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

Java
1
readLocality(..)

.
Планирую переписать как:

Java
1
2
3
4
5
6
7
8
9
    private static void readLocality(Cache cache, int address, int start, int length) {
        for (int i = 0; i < address; i++) {
            cache.process(start + i, true);
        }
 
        for (int i = address + 1; i < length; i++) {
            cache.process(start + i, true);
        }
    }

Но мне интересно верный ли это подход, как на самом деле происходит в кэше процессора.

Добавлено через 49 минут

Сообщение от ViktorFX

А не проще ли если проверенное место пустое (что ко всему прочему портит всю запись) изменить бит присутствия?

Признак присутствия заполняется при первом обращений, подобно тому как инстанциируются классы Java.

Ввел его, для того, чтобы первое обращение по нулевому адресу к еще "свежему" кэшу не было кэш-попаданием.
Сам признак присутствия не используется алгоритмом замещения NRU.

Добавлено через 1 час 21 минуту
Точнее так переписал функцию считывания локали:

Java
1
2
3
4
5
6
7
8
9
10
11
    private static void readLocality(Cache cache, int address, int length) {
        final int start = (address / length) * length;
        for (int i = start; i < address; i++) {
            cache.process(i, true);
        }
 
        final int end = start + length;
        for (int i = address + 1; i < end; i++) {
            cache.process(i, true);
        }
    }

Вопрос: так ли происходит при работе алгоритма в кэша процессора?
Верно ли это концептуально

Добавлено через 9 минут
В принципе график кэш-попаданий получился логичным(по оси Х размеры пространственной локальности 2, 4, 8, 16, .. 1024):

Количество кэш-промах уменьшается вдвое при линейном обращений соизмеримым с общим размером кэша.

@Qazan · 15.10.2018, 20:24 **[ТС]**

График:

@Qazan · 15.10.2018, 20:48 **[ТС]**

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

@Qazan · 15.10.2018, 20:48 **[ТС]**

Т.е. кэш-попадания стабильно 50%.

@ViktorFX · 16.10.2018, 07:04

Qazan, К сожалению я вам не могу помочь, я в этой теме вообще не разбираюсь, мои вопросы лишь свидетельствуют о общих знаниях и обширных интересах, и здесь скорее логика и общие суждения.
Тема интересна, я думаю кто-то уже "прокладывал дорожку", я бы начал именно с этого, хотя в инете к сожалению не все можно найти.

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@Qazan 215 / 63 / 25 Регистрация: 30.04.2013 Сообщений: 865 Записей в блоге: 10

	Моделирование работы кэш памяти, Not recently Used 14.10.2018, 23:32. Показов 1744. Ответов 6 Метки нет (Все метки) Добрый день! Написал программу - модель кэша. Кэш состоит из групп. Группа состоит из записей. Каждая запись имеет флаги чтения, записи и присутствия. Бит присутствия заполняется при первом обращений к записи и более не изменяется. Бит чтения заполняется при доступе на запись или чтение. Бит записи заполняется только при доступе на запись. Имеется параметр - размер пространственной локальности. Этим параметром кэш разбивается на участки равного размера. В случае кэш-промаха происходит полное чтение участка к записи которого происходил доступ. Также кэш имеет счетчик обращений. Вопрос: должен ли изменятся счетчик при "подкачке" записей? А также необходимо ли устанавливать бит чтения в 1 у таких "подкачанных" записей? Добавлено через 1 час 52 минуты Скорее вопрос такой: Считать ли проверку кэш-попадания обращением? Или же полноценное обращение это когда мы изменяем флаги и возможно меняем содержимое диска? А проверку адреса на предмет кэш-попадания можно сделать не изменяющей состояния? Т.е. так: Проверить было ли кэш попадание. если нет, то 1. Подгрузить левую окрестность нашего адреса 2. Обратиться на чтение или запись по данному адресу 3. Прочитать правую окрестность точки. Итого здесь будет N обращений, включая обращение по исходному адресу. если N это размер окрестности(пространственной локальности). Пример: Допустим мы при каждом обращений подгружаем 1024 записи. Изначально кэш чист. Первое обращение идет по адресу 413. Проверяем его получаем кэш промах Делаем обращения на чтение 0 - 412 записей из диска. Делаем исходное обращение по 413. (допустим на запись) Делаем обращения на чтение 414 - 1023 записей из диска. Итого на счетчике кэша имеем 1024 обращения. Счетчик используется для того, чтобы на Nом обращений занулять все флаги обращения, поскольку алгоритм NRU. 0

@Qazan 215 / 63 / 25 Регистрация: 30.04.2013 Сообщений: 865 Записей в блоге: 10
	15.10.2018, 20:24 [ТС]
	График: Миниатюры 0

@Qazan 215 / 63 / 25 Регистрация: 30.04.2013 Сообщений: 865 Записей в блоге: 10
	15.10.2018, 20:48 [ТС]
	При увеличении количество запросов вдвое (растягивание модели программы) больше чем размер кэша дало следующий результат: Миниатюры 0

@Qazan 215 / 63 / 25 Регистрация: 30.04.2013 Сообщений: 865 Записей в блоге: 10
	15.10.2018, 20:48 [ТС]
	Т.е. кэш-попадания стабильно 50%. 0

@ViktorFX 528 / 263 / 70 Регистрация: 11.12.2016 Сообщений: 1,223
	16.10.2018, 07:04
	Qazan, К сожалению я вам не могу помочь, я в этой теме вообще не разбираюсь, мои вопросы лишь свидетельствуют о общих знаниях и обширных интересах, и здесь скорее логика и общие суждения. Тема интересна, я думаю кто-то уже "прокладывал дорожку", я бы начал именно с этого, хотя в инете к сожалению не все можно найти. 0