WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     || 2 | 3 |

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

САХАРОВ Илья Евгеньевич УПРЕЖДАЮЩЕЕ КЭШИРОВАНИЕ В ПОДСИСТЕМЕ ВНЕШНЕЙ ПАМЯТИ ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ Специальность: 05.13.18 – Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

Иваново, 2009 1

Работа выполнена в Костромском государственном технологическом университете.

доктор технических наук, профессор

Научный консультант:

Шведенко Владимир Николаевич доктор технических наук, профессор

Официальные оппоненты:

Пантелеев Евгений Рафаилович кандидат технических наук, доцент Жирков Владислав Федорович

Ведущая организация: Московский государственный технический университет им. Н.Э. Баумана

Защита состоится " 25 " сентября 2009 года в 11 часов на заседании диссертационного совета Д 212.064.03 в по адресу: 153003, г. Иваново, ул. Рабфаковская, 34, ауд. Б-237.

С диссертацией можно ознакомиться в библиотеке ИГЭУ, с авторефератом можно ознакомиться на сайте ИГЭУ www.ispu.ru

Автореферат разослан « » 2009 года.

Ученый секретарь диссертационного совета кандидат технических наук, доцент Шульпин А.А.

2 Введение Актуальность диссертационного исследования. Одной из современных тенденций развития высокопроизводительных систем является интеграция различных ресурсов в единую сетевую среду распределенных вычислений (ССРВ). Данная среда позволяет использовать разнородные средства как единый вычислительный ресурс. ССРВ состоит из множества территориально размещенных вычислительных систем, соединенных различными каналами связи, характеристики которых могут динамически изменяться в широких пределах и представляет собой GRID-систему.

Приложения (задачи) пользователей выполняются на одной или нескольких вычислительных системах, входящих в состав ССРВ. Из большого территориального расположения компонент ССРВ возникает задержка передачи данных по каналам связи и задержка обращения к дисковым накопителям.

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

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

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

Объект исследования – подсистема внешней памяти высокопроизводительных распределенных вычислительных систем.

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

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

1. Разработать имитационную модель упреждающего кэширования.

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

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

4. Разработать организацию упреждающего кэширования для эффективной работы подсистемы ввода/вывода ССРВ.

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

Научная новизна:

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

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

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

3. Разработан метод упреждающего кэширования для однопотоковых и многопотоковых приложений с интенсивным вводом/выводом.

Реализация результатов работы. Результаты, полученные в ходе проведения исследования, были экспериментально апробированы в Институте химической физики им. Н.Н.Семенова г. Москва, в учебном процессе Академии ФСБ РФ.

Апробация работы. Основные положения диссертационной работы изложены в докладах на следующих научно-практических конференциях: пятой Всероссийской научной конференции молодых ученых СПбГУ 2008, научно-технической и информационное обеспечение деятельности спецслужб» 2-3 февраля 2006 года ИКСИ АФСБ РФ, второй Всероссийской научной конференции факультета ВМК МГУ им. М.В. Ломоносова.

Публикации. По теме диссертации опубликовано 8 статей.

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

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

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

В первой главе «Обзор современных технологий повышения производительности распределенных вычислений» описываются проблемы работы с данными, сопровождающие выполнение различных приложений с интенсивным вводом/выводом, а также рассматриваются существующие алгоритмы формирования предвыборок. Использование файловой предвыборки является сложно реализуемым методом из-за ряда недостатков.

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

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

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

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

Во второй главе «Разработка имитационной модели и исследование эффективности применения упреждающего кэширования для ССРВ» описывается имитационная модель упреждающего кэширования для ССРВ.

Также дается представление об алгоритме моделирования, приводиться схема имитационной модели в терминах алгоритма моделирования и средства моделирования и описывается программная реализация модели. Дается полное представление системной модели обращения к данным, а также математической оценки эффективности упреждающего кэширования. Исследуется эффективность применения упреждающего кэширования для ССРВ. Описывается механизм функционирования упреждающего кэширования в ССРВ, реализованный в имитационной модели. Время выполнения приложения T, равняется (1) T = NI / O (TCPU + TI / O) NI /O где - количество операций ввода-вывода, TCPU - среднее время исполнения процессором приложения, между двумя последовательными запросами к данным, TI / O - среднее время на выполнение одного запроса на ввод/вывод.

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

(2) TMISS =THIT +TNetwork+Tserver+Tdisk +Tdriver Коэффициент попадания в кэш-память зависит от среднего времени доступа. Максимальный выигрыш от применения упреждающего кэширования для одной сформированной последовательности обращений к файлам не буTNetwork+Tdisk +Tserver Bx дет превышать. Обозначим через - временное преимущество от применения упреждающего кэширования, тогда (3) Bx = (Tdisk +Tnetwork +Tserver) - x (TCPU +THIT +Tdriver) P = x = (Tdisk +Tnetwork+Tserver)/THIT) Bx (4), при =P – горизонт предвыборки, определяет количество запросов после которых, предвыборка является не эффективной.

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

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

Рисунок 1 - Функция выигрыша приBx менения упреждающего кэширования Tdisk +Tnetwork +Tserver На основе системной модели обращения к данным была создана P – горизонт имитационная модель модуля упрежпредвыборки дающего кэширования на языке GPSS. Модуль упреждающего кэшиx Tdisk +Tnetwork +Tserver рования представляет собой многоканальную систему массового обслуTHIT живания с ожиданием. Модель поделена на сегменты. Изначальным транзактом является, так называемый, транзакт-паспорт задания, от него создаются копии, а сам он уничтожается. Число копий равно количеству узлов, на которых запускается задача. Каждый из созданных транзактов-паспортов занимает свой узел и остается в нем до момента полного выполнения задания на данном узле. Имитационная модель состоит из 12 сегментов. Структурная схема имитационной модели изображена на рис.2.

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

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

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

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

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

Рисунок 2 - Структурная схема имитационной модели В третей главе «Программная реализация метода упреждающего кэширования» описывается предлагаемый метод упреждающего кэширования, преимущества и недостатки метода.

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

Pages:     || 2 | 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»