На правах рукописи

Воробьев Павел Евгеньевич

РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ ОПТИМАЛЬНОГО

КЕШИРОВАНИЯ ФАЙЛОВ НА ВНЕШНИХ НОСИТЕЛЯХ

Специальность: 05.13.15 – Вычислительные машины, комплексы и

компьютерные сети

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва – 2010

Работа выполнена в Федеральном государственном учреждении «Государственный научно-исследовательский институт информационных технологий и телекоммуникаций» (ФГУ ГНИИ ИТТ «ИНФОРМИКА»)

Научный руководитель: д.т.н., профессор Тихонов А.Н.

Официальные оппоненты: д.т.н., профессор Саксонов Е.А.

к.т.н., доцент Бычкова Н.А.

Ведущая организация: Московский государственный университет приборостроения и информатики (МГУПИ)

Защита диссертации состоится «21» декабря 2010г. в 14-00 часов на заседание диссертационного совета Д 212.133.03 при МИЭМ: 109028, Москва, Б.

Трехсвятительский пер., д. 3.

С диссертацией можно ознакомиться в библиотеке Московского государственного института электроники и математики.

Автореферат разослан «20» Ноября 2010г.

Ученый секретарь диссертационного совета Д 212.133. доктор технических наук, доцент Леохин Ю.Л.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Кроме того, с ростом сложности, а также размерности технических и научных задач возрастают требования к объему внешней памяти. Рост объема памяти в свою очередь приводит к большим физическим размерам носителей и препятствует снижению времени доступа и увеличению скорости передачи данных в такой памяти.

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

Однако до настоящего времени решение подобного рода задач технического проектирования и программирования в основном базировалось на опыте использования машин со сравнительно невысокой производительностью, обладавших процессорами с тактовой частотой до одного Ггц. Такой эмпирический подход уже на ранних стадиях разработки мог внести ошибки в решения, устранение большинства которых обходится слишком высокой ценой. Это в полной мере относится к решению задач декомпозиции файлов данных и их размещения в многоуровневой памяти ЭВМ, которые бы минимизировали верхнюю границу числа обращений к внешним носителям и ряду других задач, возникающих в процессе создания систем с базами данных и АСУ.

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

анализ современных аппаратных средств, используемых в качестве внешних носителей информации в компьютерах;

разработка и выбор математических моделей, предназначенных для поиска эффективных стратегий управления внешними носителями;

использование созданных моделей для разработки алгоритмов оптимального кеширования файлов;

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

кэширования и декомпозиции файлов данных для современных вычислительных машин;

учитывающие размеры кэшируемых файлов, частоту обращений к ним, а также объем памяти используемых компьютеров, применительно к построенным моделям;

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

математический анализ, амортизационный анализ алгоритмов, элементы теории игр, имитационное моделирование, комбинаторная оптимизация, математическая статистика, анализ временных рядов.

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

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

принцип оптимума Парето для оценки эффективности решений, полученных на многокритериальных моделях;

подходы, применяемые в комбинаторном программировании, которые были использованы для доказательства теорем третьей главы.

Научная новизна работы заключается в следующем:

стратегий кэширования и декомпозиции файлов данных для современных вычислительных машин;

кэширования, учитывающие размеры кэшируемых файлов, частоту обращений к ним, а также объем памяти используемых компьютеров, применительно к построенным моделям;

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

Практическая значимость работы:

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

Реализация и внедрение результатов исследований. Результаты, полученные в диссертации, внедрены и эффективно используются в Федеральном государственном учреждении «Государственный научноисследовательский институт информационных технологий и телекоммуникаций» (ФГУ ГНИИ ИТТ «ИНФОРМИКА»), Северо-Кавказском Горно-Металлургическом Институте (Государственный Технологический Университет), а так же в Московском государственном технологическом университете «Станкин» (МГТУ «Станкин»).

Апробация работы. Основные положения диссертации докладывались на семинарах ФГУ ГНИИ ИТТ «Информика», на Всероссийской научнометодической конференции «Телематика» (Санкт-Петербург, 2007,2008,2009), на международных конференциях «ИТ-технологии: развитие и приложения», Владикавказ, 2008 и 2009 годы, на международной научной конференции «Информационные технологии и системы. Наука и практика», Владикавказ 2009 год, на семинарах кафедры автоматизированной обработки информации Северо-Кавказского горно-металлургического института (государственного технологического университета) г. Владикавказ.

Публикации. Результаты диссертационной работы отражены в опубликованных печатных работах, в том числе 1 – в рецензируемом журнале из списка ВАК РФ.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Объем диссертации страница.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

1. Проведен детальный анализ причин ограниченного быстродействия внешних накопителей, учитывающий их конструктивные особенности.

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

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

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

реализованных в последующих главах диссертации, содержательно поставлены и систематизированы задачи исследования оптимальных стратегий кэширования, в том числе:

минимизация верхней границы суммарного времени фиксированного числа обращений к внешним носителям;

минимизация времени при единичных обращениях ко всем файлам, размещенным на внешних носителях (оптимум по Парето);

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

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

взаимодействия внешних носителей и оперативной памяти компьютеров.

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

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

Пусть Wi - размер i-го внешнего файла (Мб.);

U i - размер i-го кэш блока, предназначенного для кэширования V - объем свободной оперативной памяти (Мб.).

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

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

а во втором используется модель, позволяющая минимизировать верхнюю границу числа обращений к внешним накопителям при однократном считывании любого файла:

Распараллеливая для сокращения времени поиск информации в n файлах m рабочими станциями однородной локальной вычислительной сети, каждая рабочая станция которой исследует «своё» подмножество файлов, можно показать, что (2) в этом случае сводится к виду:

где: I j - подмножество файлов, обследуемое j-ой рабочей станцией - объем свободной оперативной памяти j-ой рабочей станции