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

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

14.10.2018, 23:32. Показов 1466. Ответов 6
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Добрый день!

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

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

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


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

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


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

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

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

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

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

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

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


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


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

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


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

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

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


Счетчик используется для того, чтобы на Nом обращений занулять все флаги обращения, поскольку алгоритм NRU.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.10.2018, 23:32
Ответы с готовыми решениями:

Очистка кэш памяти ПК
как написать программу, которая очищала бы кэш память

Окно кэш-памяти
Добрый день! Знающие CompModel, подскажите, пожалуйста, следующее. В окне Кэш-память снизу пишется...

Сколько нужно кэш памяти 1-2 уровней ?
Всем привет, подскажите пожалуйста сколько нужно кэш памяти для работы в VISUAL C 2008. А то я...

Увеличение производительности за счет кэш-памяти и конвейерности процессора
Читаю тут одну книгу и не понимаю. Перемножают матрицы. И говорят. Ну вот, если будем перемножать...

6
528 / 263 / 70
Регистрация: 11.12.2016
Сообщений: 1,223
15.10.2018, 01:56 2
Цитата Сообщение от Qazan Посмотреть сообщение
Также кэш имеет счетчик обращений.
Обращений для чего (чтение,записи?)
Цитата Сообщение от Qazan Посмотреть сообщение
Считать ли проверку кэш-попадания обращением?
Ну если счетчик работает и на чтение, то проверку осуществляему чтением я бы считал.
Цитата Сообщение от Qazan Посмотреть сообщение
Или же полноценное обращение это когда
Все зависит от реализованой вами модели, и смысла вложенного в слово "полноценный".
Цитата Сообщение от Qazan Посмотреть сообщение
А проверку адреса на предмет кэш-попадания можно сделать не изменяющей состояния?
Состояние я так понимаю это :
Цитата Сообщение от Qazan Посмотреть сообщение
Бит присутствия заполняется при первом обращений к записи и более не изменяется.
Ну вы же обращаетесь чтением для проверки.
Это мне вообще не понятно. Вы проверите, обнаружите что там пусто да и вся запись пуста и проделаете N обращений? А в перспективе все время будете перепроверять поскольку бит присутствия не изменяется? А не проще ли если провереное место пустое (что ко всему прочему портит всю запись) изменить бит присутствия?

А это точно Джава? (с)
0
215 / 63 / 25
Регистрация: 30.04.2013
Сообщений: 865
Записей в блоге: 10
15.10.2018, 20:23  [ТС] 3
Цитата Сообщение от 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):

Количество кэш-промах уменьшается вдвое при линейном обращений соизмеримым с общим размером кэша.
0
215 / 63 / 25
Регистрация: 30.04.2013
Сообщений: 865
Записей в блоге: 10
15.10.2018, 20:24  [ТС] 4
График:
Миниатюры
Моделирование работы кэш памяти, Not recently Used  
0
215 / 63 / 25
Регистрация: 30.04.2013
Сообщений: 865
Записей в блоге: 10
15.10.2018, 20:48  [ТС] 5
При увеличении количество запросов вдвое (растягивание модели программы) больше чем размер кэша дало следующий результат:
Миниатюры
Моделирование работы кэш памяти, Not recently Used  
0
215 / 63 / 25
Регистрация: 30.04.2013
Сообщений: 865
Записей в блоге: 10
15.10.2018, 20:48  [ТС] 6
Т.е. кэш-попадания стабильно 50%.
0
528 / 263 / 70
Регистрация: 11.12.2016
Сообщений: 1,223
16.10.2018, 07:04 7
Qazan, К сожалению я вам не могу помочь, я в этой теме вообще не разбираюсь, мои вопросы лишь свидетельствуют о общих знаниях и обширных интересах, и здесь скорее логика и общие суждения.
Тема интересна, я думаю кто-то уже "прокладывал дорожку", я бы начал именно с этого, хотя в инете к сожалению не все можно найти.
0
16.10.2018, 07:04
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.10.2018, 07:04
Помогаю со студенческими работами здесь

Наиболее эффективный алгоритм замещения для кэш-памяти большего объёма
Добрый день, интересует такой вопрос: Какой алгоритм замещения будет наиболее эффективным если...

Определить наличие кэш памяти процессора и его параметров (ассемблерные вставки)
Необходимо определить наличие кэш памяти процессора и его параметров с ассемблерными вставками. Из...

Загружаются ли в кэш данные из оперативной памяти при использовании арифметики указателей
Привет Операции с массивами работают быстрее если использовать индексацию указателей, чем при...

Samsung NP530U3C-A08RU Как проверить работает ли сейчас SSD-диск в качестве кэш-памяти?
После всяческих манипуляций с ноутбуком samsung np530u3c-a08ru и удалением/форматированием SSD...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru