Введение к работе
Значительный рост производительности процессоров, появление их многоядерных версий, а также уменьшение времени цикла оперативной памяти привели к тому, что обработка запросов ввода/вывода стала критической в эффективности вычислительных систем. Улучшение технических характеристик аппаратных средств ЭВМ, емкость внешней памяти в которых возросла до сотен терабайт, по экстенсивному пути развития ограничено технологическими возможностями и уровнем развития конструкторской базы, прежде всего из-за присущих механическим носителям физических ограничений. Вследствие этого такой метод повышения производительности компьютеров теряет свою привлекательность и заставляет искать другие пути повышения производительности вычислительных машин.
Кроме того, с ростом сложности, а также размерности технических и научных задач возрастают требования к объему внешней памяти. Рост объема памяти в свою очередь приводит к большим физическим размерам носителей и препятствует снижению времени доступа и увеличению скорости передачи данных в такой памяти.
Таким образом, стремление добиться максимальной
производительности вычислительных систем при заданных ограничениях на ресурсы аппаратных средств приводит к необходимости реализации собственных, специфичных для конкретного приложения алгоритмов ввода/вывода и, следовательно, неразрывно связано с повышением научно-технического уровня проектирования, включающего оптимизацию организации данных и программного обеспечения на основе изучения объемов и количества баз данных, методов доступа к данным, связей между данными, особенностей жизненного цикла данных, анализа потока обращений к внешним носителям.
Однако до настоящего времени решение подобного рода задач технического проектирования и программирования в основном базировалось
на опыте использования машин со сравнительно невысокой
производительностью, обладавших процессорами с тактовой частотой до одного Ггц. Такой эмпирический подход уже на ранних стадиях разработки мог внести ошибки в решения, устранение большинства которых обходится слишком высокой ценой. Это в полной мере относится к решению задач декомпозиции файлов данных и их размещения в многоуровневой памяти ЭВМ, которые бы минимизировали верхнюю границу числа обращений к внешним носителям и ряду других задач, возникающих в процессе создания систем с базами данных и АСУ.
Целью работы является создание и использование системы математических моделей, учитывающих технические характеристики применяемых для решения конкретных задач компьютеров для повышения скорости обмена данными между оперативной памятью и внешними носителями, а также контроль полученных результатов с помощью средств имитационного моделирования. Для достижения этой цели в работе поставлены и решены следующие задачи:
анализ современных аппаратных средств, используемых в качестве внешних носителей информации в компьютерах;
разработка и выбор математических моделей, предназначенных для поиска эффективных стратегий управления внешними носителями;
использование созданных моделей для разработки алгоритмов оптимального кеширования файлов;
разработка новой методики, предназначенной для контроля эффективности полученных результатов, использующей методы имитационного моделирования и учитывающей специфику размещенных на внешних носителях данных и конструктивные особенности применяемых внешних накопителей.
На защиту выносятся:
математические модели поиска оптимальных стратегий
кэширования и декомпозиции файлов данных для современных вычислительных машин;
алгоритмы поиска оптимальных стратегий кэширования,
учитывающие размеры кэшируемых файлов, частоту обращений к ним, а
также объем памяти используемых компьютеров, применительно к построенным моделям;
методика имитационного контроля полученных результатов,
использующая специфику размещенных на внешних носителях данных и
конструктивные особенности применяемых компьютеров.
Методами исследований, используемыми в работе, являются математический анализ, амортизационный анализ алгоритмов, элементы теории игр, имитационное моделирование, комбинаторная оптимизация, математическая статистика, анализ временных рядов.
При этом применялись:
метод множителей Лагранжа, который, применительно к исследовавшимся моделям, гарантировал глобально оптимальное решение, причем полученное не итеративно, а аналитически, т. е. с минимальными временными затратами;
метод эталонов, который был использован, благодаря тому, что он позволяет перейти от многокритериальной математической модели к однокритериальной, оптимальное решение которой будет, одновременно, Парето-оптимальным решением исходной многокритериальной задачи;
принцип оптимума Парето для оценки эффективности решений, полученных на многокритериальных моделях;
подходы, применяемые в комбинаторном программировании,
которые были использованы для доказательства теорем третьей главы.
Научная новизна работы заключается в следующем:
разработаны математические модели поиска оптимальных стратегий кэширования и декомпозиции файлов данных для современных вычислительных машин;
разработаны алгоритмы поиска оптимальных стратегий кэширования, учитывающие размеры кэшируемых файлов, частоту обращений
к ним, а также объем памяти используемых компьютеров, применительно к построенным моделям;
разработана методика имитационного контроля полученных результатов, использующая специфику размещенных на внешних носителях данных и конструктивные особенности применяемых компьютеров. Практическая значимость работы:
На основании созданного комплекса математических моделей оптимального кэширования файлов баз данных, включающий различные целевые функции, разработан алгоритм, позволяющий осуществлять оптимальное кэширование данных в двухуровневой памяти ЭВМ в соответствии с выбранными целями.
Реализация и внедрение результатов исследований. Результаты,
полученные в диссертации, внедрены и эффективно используются в
Федеральном государственном учреждении «Государственный научно-
исследовательский институт информационных технологий и
телекоммуникаций» (ФГУ ГНИЙ ИТТ «ИНФОРМИКА»), Северо-Кавказском
Горно-Металлургическом Институте (Государственный Технологический
Университет), а так же в Московском государственном технологическом
университете «Станкин» (МГТУ «Станкин»).
Апробация работы. Основные положения диссертации докладывались
на семинарах ФГУ ГНИЙ ИТТ «Информика», на Всероссийской научно-методической конференции «Телематика» (Санкт-Петербург, 2007,2008,2009), на международных конференциях «ИТ-технологии: развитие и приложения», Владикавказ, 2008 и 2009 годы, на международной научной конференции «Информационные технологии и системы. Наука и практика», Владикавказ 2009 год, на семинарах кафедры автоматизированной обработки информации Северо-Кавказского горно-металлургического института (государственного технологического университета) г. Владикавказ.
Публикации. Результаты диссертационной работы отражены в 6 опубликованных печатных работах, в том числе 1 - в рецензируемом журнале из списка ВАК РФ.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Объем диссертации 123 страница.
Похожие диссертации на Разработка методов и алгоритмов оптимального кэширования файлов на внешних носителях
