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

• Автор: Сахаров, Илья Евгеньевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Кострома
• Количество страниц: 137 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.
ГЛАВА 1. ОБЗОР СОВРЕМЕННЫХ ТЕХНОЛОГИЙ ПОВЫШЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛЕНИЙ

1.1. Введение.

1.2. Проблема задержек при дисковых операциях.

1.3. Предвыборка операций вводавывода

1.3.1. Преимущества и недостатки использования упреждающего кэширования.

1.3.2. Особенности упреждающего кэширования.

1.3.3. Планирование и управление упреждающего кэширования.

1.3.4. Алгоритм предсказания данных.

Методы, основанные на примерах

Методы, основанные на истории.
Методы статистического анализа
1.4. Способ разделения потоков приложения.
1.5. Другие подходы к организации упреждающего кэширования
1.6. Обзор параллельных файловых систем.
Сетевая файловая система i
Параллельная Виртуальная Файловая Система V Vi
i .
Глобальная файловая система i
Параллельная файловая система i .
Параллельная файловая система i .
1.7. Выводы по первой главе.
ГЛАВА 2. РАЗРАБОТКА ИМИТАЦИОННОЙ МОДЕЛИ И ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ПРИМЕНЕНИЯ УПРЕЖДАЮЩЕГО КЭШИРОВАНИЯ ДЛЯ ССРВ.
2.1. Введение.
2.2. Математическое представление упреждающего кэширования
2.2.1. Системная модель обращения к данным для упреждающего кэширования.
2.2.2. Математическая оценка эффективности упреждающего кэширования.
2.3. Структура и принципы функционирования механизма упреждающего кэширования в имитационной модели.
2.3.1. Модель параллельной программы
2.3.2. Описание функционирования имитационной модели
2.3.3. Условия проведения экспериментов с имитационными моделями
2.3.4. Результаты экспериментирования с имитационными моделями
2.4. Вывод,I по второй главе.
ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДА УПРЕЖДАЮЩЕГО КЭШИРОВАНИЯ.
3.1. Введение.
3.2. Метод упреждающего кэширования.
3.2.1. Потенциальные преимущества упреждающего кэширования
3.2.2. Способ разделения приложения на два потока
Архитектуру упреждающего кэширования.
Упреждающий поток
Синхронизация
Генерация упреждающего потока
Ограничения.
Анализатор кода для многопотоковых приложений.
Архитектура исполняющей системы.
3.3. Выводы по третей главе
ГЛАВА 4. ПРОВЕРКА СООТВЕТСТВИЯ РАЗРАБОТАННОЙ ИМИТАЦИОННОЙ МОДЕЛИ И ПРЕДЛАГАЕМОГО МЕТОДА УПРЕЖДАЮЩЕГО КЭШИРОВАНИЯ.
4.1. Введение
4.2. Оценка производительности модуля упреждающего кэширования .
4.2.1. Условия проведения экспериментов.
4.2.2. Результаты экспериментов и их анализ.
4.2.3 Пример решения задачи о тепловом взрыве.
4.3. Выводы по четвертой главе.
ОБЩИЕ ВЫВОДЫ ПО РАБОТЕ.
СПИСОК ЛИТЕРАТУРЫ


Предлагается использовать механизм упреждающего кэширования, который учитывает реальную последовательность обращений к файлам. Команды предвыборки получают требуемую информацию в процессе дополнительного запуска кода оригинальной программы. Упреждающее кэширование и просто кэширование достаточно давно и успешно используются в современных файловых системах и в различных приложениях [,,]. LRU - least recently used. К сожалению, в приложениях использующих интенсивный обмен данными подобные методы не обеспечивают требуемую эффективность. HCTopHH(history-based) и методы статического ananH3a(static). Метод, основанный на примерах, осуществляет предвыборку в соответствии с некоторым фиксированным заранее определенным множеством примеров доступа. Этот метод крайне эффективен, когда доступ к данным в приложение соответствует одному из элементов множества. И не может ничего изменить для приложений, не попадающих в это множество. Методы, основанные на истории, осуществляют предвыборку, основываясь на наблюдении предыдущих последовательностей обращений к данным. Этот подход эффективен для предвыборки последовательности обращений подобной предыдущей, но если последовательность обращений сильно изменилась по сравнению со всеми предыдущими, то эффективность резко' падает. По этой и еще некоторым другим причинам, методы, основанные на истории, будут неэффективны для приложений, которые зависят от меняющихся входных данных. Наконец, методы, основанные на статическом анализе, используют компилятор (или какое либо другое средство) для внесения вызовов упреждающего кэширования в приложении на основе анализа кода программы до ее запуска. Этот метод ограничен возможностями компилятора для внесения изменений в код приложения, так чтобы доступ к данным, которые будут востребованы приложением в будущем, учитывал предвыборку. Возможности внесения подобных изменений в код приложения препятствует зависимость программы от значений данных, которые определяются только в результате ее выполнения. Сложность реализации этой возможности заключается в проведении статического анализа обращения для циклических участков кода. В диссертации представлен четвертый новый подход автоматического выделения информации о предвыборке, который называется упреждающее кэширование на основе разделения потоков. Данный метод позволяет сократить отношение времени выполнения приложения, ко времени доступа к памяти, а также исключает некоторые недостатки описанных выше трех методов. Например, по сравнению с методом примеров данный метод способен осуществлять предвыборку произвольной последовательности обращений к данным. По сравнению с методом историй этот метод позволяет осуществлять предвыборку данных, которые никогда раньше не использовались. И по отношению к методу статического анализа не делает сложных анализов кода. Хорошо известно; что многие процессоры используют спекулятивное исполнение кода программы (например архитектура 1ШеА-) для большей эффективности определить следующую ветвь программы и тем самым уменьшить- время исполнения [,,]. В диссертации доказывается, что использование упреждающего кэширования на основе разделения потоков' уменьшает время простоя при операциях ввода-вывода. В частности, в диссертации предлагается осуществлять, для-определения данных о предвыборке, дополнительный запуск кода приложения. Этот дополнительный запуск реализуется в виде потока, получившего название упреждающий ноток. Основная идея заключается в разложении приложения на два потока: вычислительный поток, содержащий неизмененный код оригинальной программы, включающий все вычислительные операции и все операции ввода/вывода и- упреждающий поток, содержащий все оригинальные инструкции, которые имеют отношение к вводу/выводу. Предметом исследования являются модели, методы и алгоритмы, упреждающего кэширования. Разработать имитационную модель упреждающего кэширования. ССРВ. Методами исследования являются1 системный анализ, методы имитационного моделирования, аналитические методы разработки и оптимизация разрабатываемых алгоритмов и средств.