Методы поиска оптимальных стратегий кэширования

Аннотация:
Джиоева С.А. – Представленная статья описывает проект, предусматривающий создание математического аппарата и, на его основе, драйвера файловой системы с оптимальным размещением информации на внешних носителях и эффективной системой управления кэшированием, обеспечивающим оптимальное использование аппаратных ресурсов компьютеров. Для того, чтобы снизить энергопотребление компьютеров и вычислительных систем, необходимо создать интеллектуальную систему управления его иерархической памятью. Данный научный проект, описанный этой статьѐй, отражающет конструктивные особенности внешних носителей информации. Значимость исследования состоит в создании энергосберегающей системы управления иерархической памятью современных вычислительных систем, не снижающей их быстродействие. Результаты исследования можно будет применить в системах информационного поиска и в вычислительных комплексах. Проводимое исследование будет интегрировано в учебный процесс СКГМИ (ГТУ). Разработанный драйвер будет включен в программное обеспечение учебных компьютерных классов. Кроме этого возможно применение драйвера в операционной среде, используемой АСУ ВУЗ. Данная работа может представлять интерес для разработчиков операционных систем, а также для разработчиков запросно-поисковых систем и создателей мобильных информационно-вычислительных комплексов, заинтересованных в энергосбережении и минимизации времени поиска данных

Общая постановка проблемы
Проблема обработки больших объѐмов информации в последнее время становится главной во всех областях информационных технологий. От обработки операций чтения-записи зависит работа системы в целом. Производительность процессоров, как и оперативная память, растѐт непрерывно и напрямую зависит от размеров кэша. Зависимость производительности процессоров от размеров кэша можно рассмотреть с разных сторон – зависимость непосредственно от процессора, от размеров кэша, от уровневого строения кэша (кэш первого уровня – L1, второго уровня – L2, кэш третьего уровня – L3). L1 кэш работает на частоте процессора. Зачастую является возможным выполнять несколько операций чтения-записи одновременно. L2 кэш – второй по быстродействию, но больший по объѐму. L3 кэш – наименее быстродействующий, но более внушительного размера. L3 кэш медленнее предыдущих кэшей, но быстрее, чем оперативная память. Главными задачами оптимизации компьютерных систем являются:

1. оптимизация использования кэша – определение оптимального соотношения частоты процессора, объѐмов кэш L1, L2, L3;
2. оптимизация размеров кэш.

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

Этап оптимизации использования кэша
На первом этапе определяются оптимальные размеры кэша. Нужно определить, при каких соотношениях частоты процессора, объѐмов кэша система работает наиболее быстро и продолжает быть экономически оправданной. С выпуском ядра с объѐмом кэша L2 1 Мбайт, этот процессор стал основой линейки настольных процессоров. Впрочем, более быстрые тактовые частоты и больший объѐм кэша даже тогда не значили очень много. Сегодня ситуация изменилась: лучшая производительность и меньшее энергопотребление немало обязаны размеру кэша.
Кэши процессора играют вполне определѐнную роль: они уменьшают количество обращений к памяти.
Есть разные способы организации иерархии кэша. Кэш L1 всегда был в составе процессора, но поначалу кэш L2 устанавливался на материнские платы, как было в случае многих компьютеров. Для кэш-памяти первого уровня использовались простые чипы статической памяти.
Встроенный кэш L2 дал существенный прирост производительности практически в любых приложениях. Увеличение производительности оказалось столь существенным, что появление кэша L2 можно назвать самым важным фактором производительности. Отключение кэша L2 снизит производительность сильнее, чем отключение второго ядра у двуядерного процессора.
Однако кэш-память влияет не только на производительность. Она стала мощным инструментом, позволяющим создавать разные модели процессоров.
Вопрос заключается в следующем: насколько различие в объѐме кэша влияет на производительность?
Как показали различные тесты, на определѐнном этапе объѐм кэша перестаѐт влиять на производительность систем и быть экономически оправданным. С этого уровня рассматривается этап оптимизации размеров КЭШа [5].

Этап оптимизации размеров кэша
Здесь рассмотрим сравнительный анализ различных стратегий кэширования данных.
Одним из аспектов проектирования оптимальных программных продуктов является размещение данных в памяти ЭВМ и определение оптимальных размеров кэш-блоков [2]. Если все файлы пользователя первоначально размещены на внешнем носителе, а в оперативной памяти созданы блоки кэширования, то формальная постановка задачи, предназначенная для комплексной оптимизации размещения информационных файлов на внешних накопителях и определения оптимального размера блока кэширования при одинаковом размере файлов и разной вероятности обращений, имеет следующий вид [1]:

где δ – объём оперативной памяти; U – размер кэш-блока; V – размер внешних файлов; q – объѐм файлов в оперативной памяти; n – количество файлов; c, a – коэффициенты.

Найдем решение, отвечающее экстремальному значению целевой функции методом множителей Лагранжа [5].
Функция Лагранжа будет иметь вид:

Отсюда следует возможность получить решение (2), приравнивая к нулю производные :

Отсюда следует решение, отвечающее экстремальному значению целевой функции (3):

После этого необходимо проверить, действительно ли система (4) отвечает оптимальному решению (3).
При подстановке:

Можем определить объѐм файлов в оперативной памяти:

Теперь выясним, является ли это решение оптимальным.

Классическая модель кэширования
Если все файлы пользователя первоначально размещены на внешнем носителе, а в оперативной памяти созданы блоки кэширования, каждый из которых предназначен для сканирования «своего» файла, то формальная постановка задачи минимизации числа обращений к внешним носителям имеет следующий вид [3, 4]:

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

Т.к. правая часть положительная, можно убедиться, что полученный результат является обобщением решения (1) [1].
Математическое определение размеров кэш-блоков может занимать значительные вычислительные объѐмы. При этом для определѐнных задач и расчѐтов самостоятельное определение размеров кэш-блоков значительно превосходит решения, полученные с помощью классического файлового распределения.

Список источников

1. Гроппен В.О., Мазин В.В. Эффективная реализация одной стратегии взаимодействия внешней и оперативной памяти ЭВМ // Тезисы докладов ХI всесоюзного совещания по проблемам управления. – Ташкент, 1989. – С. 202.
2. Гроппен В.О. Принципы решения многокритериальных задач с помощью эталонов // Труды XII Всероссийской научно-методической конференции Телематика. – СПб., 2005. – Т. 1. – С. 125-128.
3. Гроппен В.О. Модели и алгоритмы комбинаторного программирования. – Изд. РГУ, 1983.
4. Маисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации – 1978.
5. Воробьѐв П.Е., Внешние накопители данных: конструкция и эффективная эксплуатация // X международная конференция «ИТ-технологии: Развитие и приложения. – 2009. – С. 9-18.
6. Мухачѐва Э.А., Рубинштейн Г.Ш. Математическое программирование. – Новосибирск, Наука, 1977. – 320 с.