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

□034ТЬкг»х

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

САХАРОВ Илья Евгеньевич

2 О АБГ ¿009

УПРЕЖДАЮЩЕЕ КЭШИРОВАНИЕ В ПОДСИСТЕМЕ ВНЕШНЕЙ ПАМЯТИ ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Специальность: 05.13.18 - Математическое моделирование, численные

методы и комплексы программ

АВТОРЕФЕРАТ

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

Иваново, 2009

003475251

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

Научный руководитель:

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

Официальные оппоненты: доктор технических наук, профессор

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

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

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

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

Ученый секретарь диссертационного совета

кандидат технических наук, доцент Шульпин А.А.

Пантелеев Евгений Рафаилович

кандидат технических наук, доцент Жирков Владимир Федорович

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Г = + (1)

где Ии0 - количество операций ввода-вывода, Тсри - среднее время исполнения процессором приложения, между двумя последовательными запросами к данным, Тпо - среднее время на выполнение одного запроса на ввод/вывод.

Время выполнения запросов выборки данных, зависит от того, где располагаются эти данные. Пусть Тшт - время выборки одного блока данных из кэш-памяти. Задержка выборки блока данных с диска равняется Тт. Время передачи запроса по сети и время передачи блока данных равняется ТЫеМоЛ, а время обработки запроса удаленным компьютером или серверов Т1епег Для выборки буфера и обслуживания этого запроса требуется процессорное время ТФЫг - время обслуживание запроса драйвером устройства. Итак, время выполнения запроса, если блок данных располагается не в кэш-памяти, в общем случае, будет равняться:

Коэффициент попадания в кэш-память зависит от среднего времени доступа. Максимальный выигрыш от применения упреждающего кэширования для одной сформированной последовательности обращений к файлам не будет превышать ТЫеМ0Гк+Тал+Т!еП11Г, Обозначим через Вх- временное преимущество от применения упреждающего кэширования, тогда

Тцгт + ^¿пто-)

(3)

Р = х = (?лл+ТпеЫоЛ+Т^1ТН1Т), при В= О (4)

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

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

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

6

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

Рисунок 1 - Функция выщрыша применения упреждающего кэширования

На основе системной модели обращения к данным была создана имитационная модель модуля упреждающего кэширования на языке GPSS. Модуль упреждающего кэши-+Тмкогк +Т„„.г Л рования представляет собой многока-Тшт нальную систему массового обслужи-

вания с ожиданием. Модель поделена на сегменты. Изначальным транзактом является, так называемый, транзакт-паспорт задания, от него создаются копии, а сам он уничтожается. Число копий равно количеству узлов, на которых запускается задача. Каждый из созданных транзактов-паспортов занимает свой узел и остается в нем до момента полного выполнения задания на данном узле. Имитационная модель состоит из 12 сегментов. Структурная схема имитационной модели изображена на рис.2.

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

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

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

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

т 4.т + т

е disk network server

гортокт прслвыборкм

'Хы

СО« Я.-1

С ]в г» еьп®

О >» 'К*

I—

| ©РРССАЗ»

«»100 у— 0»ги -1—, Ф «кал*-

1 С-ИЗАУ"' • - л ">"

1

" Г

• I _

{; ©«(л-

{{ фа>гм ! \ ! | !! |!

0 М Г!5 • --

{ ф ЮТИЛ-1

{ С<5ГО1 I

071 № — &ГСТРА Еяд'ше.пга ©74 АС«

и С179 гаг ^©»»ЛЧ&у,

Си»!**

ОйиХ, Ч"''

О 1С] 7РА

41

л

Ш.ЕХЛви Оивим

г--»- ¿К

____

©«эш-^

озс.сои-« ф -

фнбти

• ф ГМ ^

..Л*

_£)12?У1 ,

"»Г'Л^ СММТ»

р

£?!» К1

Си« га1 Сгпв'^

¿эе^.тла: <4— еиота>

С Ш ТСР

¥1"

В третей главе «Программная реализация метода упреяедаю-щего кэширования»

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

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

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

Рисунок 2 - Структурная схема имитационной модели

Все современные разработки (практические реализации) принято делить на три направления:

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

Специальные приложения, контролирующие упреждающие выборки и кэширование: подобными системами занимался Patterson. Он модифицировал два unix приложения: make и grep, таким образом, что файловой системе передавалась информация о файлах, к которым собирается обратиться приложение заранее. Такой подход повысил эффективность исполнения приложения от 13 до 30%.

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

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

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

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

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

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

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

1. create_prefetch_thread(prefetch_iunction): эта функция позволяет приложению создать упреждающий поток и выполнить prefetch_fuction.

2. prefetch_xxx(): это множество функций, которые заменяют в упреждающем потоке все стандартные функции ввода/вывода.

3. inform_open(file_pointer) и inform_close(file_pointer): Эти функции необходимы для того, чтобы информировать упреждающий поток об открытии или закрытии файлов вычислительным потоком.

4. synchronize(synchronization_point, type): эта функция синхронизации двух потоков.

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

1. Открытие файла: Упреждающий поток должен ожидать пока вычислительный поток откроет файл. Потоки синхронизируются вызовом syn-chronize() с указанием номера синхронизационной точки (табл. 1).

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

точки синхронизации. Если входные данные считываются из конфигурационных файлов, тогда также добавляются точки синхронизации.

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

Рисунок 3 - Системная архитектура

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

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

Этот алгоритм запускается итеративно для каждой процедуры до тех пор, пока не дойдет до конца приложения. Для создания правильного упреждающего потока, кроме внутреннего анализа функций необходимо произвести межфункциональный анализ зависимостей. Анализ построен на поиске информации о входных переменных функций, возвращаемых значениях и глобальных переменных. Анализатор кода включает упрощенную поддержку многопотоковых приложений, написанных под спецификации МР1СН.

Все вызовы упреждения, которые использует упреждающий поток, содержатся в библиотеке упреждающих вызовов, размещаются и хранятся в памяти очередь команд на упреждение. Структура очереди команд на упреждение имеет следующий вид: {идентификатор файла, номер блока, идентификатор вызова}. Идентификатор файла и блока определяют реальный физи-

ческий блок данных, который необходимо предвыбрать. Идентификатор вызова определяет вызов, который инициировал запуск механизма упреждения для данного блока. Начальное значение идентификаторов вызовов начинается с 0. Файловая таблица для каждого файла дескриптора содержит смещение. Используя эту информацию всегда можно вычислить номер блока для вызовов рге£е1сЬ_геас1 и ргеГе1сЬ_1зеек.

Таблица 1

Пример вычислительного и упреждающего потоков

int fp;

Вычислительный поток (BE)** Упреждавший потек(УП)

void main(void){ Void prefetch fuctionWoid) (

int i; int datatlOOJ; int I;

/«создание упреждающего потока*/

##С1 create_prefetch__thread (

(void*)prefetch_function);

/♦открытие файла данных*/

С2 fp-open("mydata.dat", 0_RD0NLY);

/♦сигнал упреждающеыу потоку*/

##сз synchronize(1, signal); /♦ожидание открытия файла*/

$SP1 synchronize(1, wait)}

/♦указание об открытии файла*/

$$P2 inform_open(fp)/

С4 for(i»99; i>-0; i—){ /♦предвыборка*/

/*ВБОД-ВЫВОД*/ P3 forli«99j i—И

С5 lseek(fp, i*4/ SEEK SET)/

С6 re&dtfp, tdatat99-iT, 4)? /*тольк© ввод-вывод*/

/♦вычисления*/ P4 prefetch_lseek(fp,i*4,SEEK_SET);

С7 data[99-i] - data[99-i]*i? P5 prefetch__cead(fp, 4} г

} /♦закрытие файла*/

С8 close(fp)/ }

> /•указание о закрытие файла*/

$$P6 inform close (fp) *

**Слева вычислительный поток, справа упреждающий поток. Внутри функции main строчки без ## являются оригинальным кодом приложения. Б этот код были вставлены изменения по созданию упреждающего потока. Строчки без символа $$ были взяты с оригинального кода приложения. В упреждающем потоке не присутствуют вычисления.

В четвертой главе «Проверка соответствия разработанной имитационной модели и предлагаемого метода упреяедающего кэширования»

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

1. XDataSlice (версия 2.2) - средство визуализации трехмерных массивов. Позволяет динамически загружать большие массивы данных.

2. Приложение для расчета быстрого преобразования Фурье FFT (fast Fourier transform).

3. Agrep (версия 2.0.4) - программа поиска в текстовых файлах. Данная утилита осуществляет поиск текста по шаблонам среди большого количества текстовых файлов.

4. PostgreSQL (версия 7.0.3) - расширенная версия СУБД Postgres. Запускался процесс расчета индексов для четырех частей базы.

5. Mpich2 - реализация MPI. Использовалась программа перемножения двух матриц, файлы которых располагаются на множестве узлов ввода/вывода.

Загруючный модуль

Рисунок 4 - Архитектура исполняющей системы

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

Исследовалось влияние конвекции на теплоотвод в коаксиальном цилиндре с учетом объемного энерговыделения. Рассматривается жидкость в пространстве между двумя коаксиальными цилиндрами радиусов Rt и R0. Сами цилиндры поддерживаются при температурах Т0 и Г,-. В системе происходит постоянное энерговыделение с объемной мощностью Q, не зависящей от координат среды. После обезразмеривания и перехода к новым переменным, исходная система сводилась к системе трех уравнений второго порядка: На рис. 5 представлена поверхность RaT(Ra,cг), которая отделяет точки, соответствующие двумерной конвекции, от трехмерных режимов. Приведенные в работе расчеты касались двумерной модели (R, 9) и не очень больших чисел Рэлея. Кроме того, достаточно просто учитывалось энерговыделение в

системе. Увеличение RaT приводит к изменению структуры конвективного течения, поэтому анализ конвективных потоков играет исключительно важную роль при расчете геометрии лазерной системы. На рис. 6 представлены линии тока и профиль температур в координатах радиус-угол для параметров: а = 2, г,- = 1, г0 = 2, RaT = 3 • 104, Ra = 0. Как видно из рисунка, наблюдается сильная неоднородность распределения температуры по углу. Максимальное значение температуры превышает соответствующее значение максимальной температуры в системе без конвекции. Для того, чтобы проследить эволюцию температур и линий тока с течением времени, необходимо вычислить соответствующие поля. Для вычисления каждого поля (в рамках реализации задачи это представляет собой матрицу некоторого^ размера) на каждом временном шаге необходимо решить систему трех уравнений (5-7).

V V = -со (5)

V 2® = 1 Рг

до дю V да

— + и—+--

dt дг г дв

+ RaT

sinÖ— + -COS0 — дг г дв

(6)

_,2 да vdcp , д<р дг гдв dt

Расчет всех полей для построения рисунка 6 занимал от 20 до 40 часов функционирования реализованной программы. При выполнении подобной задачи на вычислительном кластере с учетом упреждающего ■ кэширования расчет полей составил от 16 до 32 часов. Для получения более точных оценок конвективного течения в системы коаксиальных цилиндров необходимо было использовать большие числа Рэлея и сложную модель энерговыделения в системе. Это привело к увеличению размеры матриц над которыми проводились измерения. Размер матриц достигали 14000 на 10000 элементов. Такие размеры матрицы необходимы для достижения требуемой точности. Каждый элемент представлял собой число типа float. Для расчета каждого элемента требуются еще три матрицы такого же размера, над которыми производились сложные вычисления по формулам (5-7). Для каждого шага по времени задавались граничные условия, которые хранились в отдельном файле.

Необходимо отметить, что приведенные расчеты касаются только двумерных массивов. Эту задачу необходимо было решать и для трехмерных массивов и для различных чисел Релея. Показано, что конвекция особенно сильно влияет на параметры системы именно в области теплового взрыва. Такой вывод указывает на необходимость учета конвективного теплоотвода при любых расчетах газовых лазеров и разрядов. Данная задача решалась на вычислительном кластере, состоящим из 12 вычислительных машин и одной управляющей машины. Характеристики вычислительных узлов: процессор Intel Pentium 3 800 Мгц с 256 Мбайт оперативной памяти. Использовалась файловая система PVFS.

В результате общее количество считанных блоков составило более 80 ООО ООО блоков по 4 Кбайта каждый. Общий объем обработанной информации составил порядка 305 Гбайт. Необходимо учитывать, что в дальнейшем придется решать данную задачу для трехмерного поля.

Рисунок 5- Критическая поверхность ЯаТ(Ка,а)

Рисунок б - Изотермы и линии тока при и =2, На.

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

ВЫВОДЫ

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

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

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

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

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

метод позволяет уменьшить время исполнения приложений от 10 до 50%.

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

Публикации по теме диссертации

По перечшо рецензируемых изданий ВАК:

1. Киселев A.B., Корнеев В.В., Семенов Д.В., Сахаров И.Е. Управление метакомпьютерными системами [текст]. Открытые системы № 2 февраль-март 2005. С. 11-16.

2. Сахаров И.Е. Организация упреждающего кэширования для приложений, исполняющихся в ССРВ [текст]. Вестник ИГЭУ - апрель 2009.

3. Сахаров И.Е. Математическое представление метода упреждающего кэширования и оценка эффективности разработанного метода [текст]. Вестник ИГЭУ - апрель 2009.

4. Сахаров И.Е. Метод упреждающего кэширования для приложений, исполняющихся в ССРВ [текст]. Вестник ВНИИЖТ, 2/2009 С. 32-33.

Публикации в других изданиях:

5. Сахаров И.Е. Метод упреждающего кэширования на основе разделения потоков в высокопроизводительных распределенных вычислительных системах [текст]: монография. КГТУ, 2008. - 100 с.

6. Сахаров И.Е. Организация упреждающего кэширования в сетевой среде распределенных вычислений [текст]. Труды Пятой Всероссийской научной конференции молодых ученых СПбГУ 2008. С. 78-89.

7. Сахаров И.Е. Организация упреждающего кэширования в сетевой среде распределенных вычислений [текст]. Материалы шестой межведомственной конференции «Научно-технической и информационное обеспечение деятельности спецслужб» 2-3 февраля 2006 года ИКСИ АФСБ РФ» том 4. С. 139-142.

8. Киселев A.B., Корнеев В.В., Семенов Д.В., Сахаров И.Е. Организация упреждающего кэширования в сетевой среде распределенных вычислений [текст]. Труды Второй Всероссийской научной конференции М: Издательский отдел факультета ВМК МГУ им. М.В. Ломоносова. С. 152158

Сахаров Илья Евгеньевич

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

Подписано в печать 29.06.2009. Печ. л. 1,0. Заказ 452. Тираж 100. РИО КГТУ, Кострома, ул. Дзержинского, 17

ВВЕДЕНИЕ.

ГЛАВА 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. Обзор параллельных файловых систем.

Сетевая файловая система NFS - Network File System.39'

Параллельная Виртуальная Файловая Система PVFS - Parallel Virtual

File System.

Глобальная файловая система GFS - Global File System.

Параллельная файловая система GPFS - General Parallel File System.

Параллельная файловая система SPFS- Scotch Parallel File System.

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. Выводы по второй главе.

ГЛАВА 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. Выводы по четвертой главе.

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

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

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

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

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

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

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

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

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

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

Для многих приложений обычное кэширование является не эффективным, поскольку рабочая область данных, с которыми работает приложение, значительно превышает размеры кэш-файлов, используемых операционными системами. Всеми известный подход осуществления предвыборки данных, до момента их реального использования, используется во множестве проектов под операционными системами типа UNIX и Linux[21]. В большинстве случаев предполагается, что требуемые данные располагаются последовательно друг за другом, когда программа обращается к i-ому блоку, осуществляется подкачка блоков от i+1 до i+n, где п -количество подкачиваемых блоков. Для большинства обычных приложений этот подход является эффективным, но для приложений с интенсивным обменом данным, подобный подход не работает. Как правило, подобные приложения обращаются одновременно к большому количеству файлов, которые в общем случае могут быть распределены произвольным образом. Различные приложения осуществляют различные схемы выборки данных из файлов, что еще более усложняет задачу предвыборки. Предлагается использовать механизм упреждающего кэширования, который учитывает реальную последовательность обращений к файлам. Команды предвыборки получают требуемую информацию в процессе дополнительного запуска кода оригинальной программы.

Упреждающее кэширование и просто кэширование достаточно давно и успешно используются в современных файловых системах и в различных приложениях [20,22,64]. Тем не менее, в большинстве подобных систем упреждающее кэширование является сильно зависимым от приложений и в основном базируются на политике LRU — least recently used. К сожалению, в приложениях использующих интенсивный обмен данными подобные методы не обеспечивают требуемую эффективность.

Все существующие методы упреждения данных делятся на три категории: методы, основанные на npHMepax(pattern-based), на HCTopHH(history-based) и методы статического анализа^айс). Метод, основанный на примерах, осуществляет предвыборку в соответствии с некоторым фиксированным заранее определенным множеством примеров доступа. Этот метод крайне эффективен, когда доступ к данным в приложение соответствует одному из элементов множества. И не может ничего изменить для приложений, не попадающих в это множество. Методы, основанные на истории; осуществляют предвыборку, основываясь на наблюдении предыдущих последовательностей обращений к данным. Этот подход эффективен для предвыборки последовательности обращений подобной предыдущей, но если последовательность обращений сильно изменилась по сравнению со всеми предыдущими, то эффективность резко1 падает. По этой и еще некоторым другим причинам, методы, основанные на истории, будут неэффективны для приложений, которые зависят от меняющихся входных данных. Наконец, методы, основанные на статическом анализе, используют компилятор (или какое либо другое средство) для внесения вызовов упреждающего кэширования в приложении на основе анализа кода программы до ее запуска. Этот метод ограничен возможностями компилятора для внесения изменений в код приложения, так чтобы доступ к данным, которые будут востребованы приложением в будущем, учитывал предвыборку. Возможности внесения подобных изменений в код приложения препятствует зависимость программы от значений данных, которые определяются только в результате ее выполнения. Сложность реализации этой возможности заключается в проведении статического анализа обращения для циклических участков кода.

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

Хорошо известно; что многие процессоры используют спекулятивное исполнение кода программы (например архитектура Intel IA-64) для большей эффективности определить следующую ветвь программы и тем самым уменьшить* время исполнения [25,26,32]. В диссертации доказывается, что использование упреждающего кэширования на основе разделения потоков* уменьшает время простоя при операциях ввода-вывода:

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

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

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

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

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

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

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

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

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

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

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

В диссертации рассматриваются следующие основные вопросы:

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

• при каких условиях упреждающее кэширование является эффективным;

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

• каким образом упреждающее кэширование влияет на работу подсистемы внешней памяти и ССРВ в целом;

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

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

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

Результаты диссертационного исследования внедрены:

1. В институте химической физики им. Семенова г. Москва.

2. Результаты исследования используются в учебном процессе ИКСИ

Академии ФСБ России.

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

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

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

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

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

ОБЩИЕ ВЫВОДЫ ПО РАБОТЕ

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

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

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

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

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

• метод должен быть эффективным, реализованным с минимальными аппаратными затратами и надежным;

• метод не должен оказывать влияние на системные процессы;

• метод должен работать на уровне приложений и не затрагивать организацию структур памяти.

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

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

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

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

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

1. Корнеев В.В., Киселев А.В., Семенов Д.В., Сахаров И.Е. Организация упреждающего кэширования в сетевой среде распределенных вычислений. Вестник ИКСИ Серия «В» Выпуск 3 Том 2.

2. Киселев А.В., Корнеев В.В., Семенов Д.В., Сахаров И.Е. Управление метакомпьютерными системами. Открытые системы №02 февраль-март 2005 80с. стр. 11-16.

3. Сахаров И.Е. Организация упреждающего кэширования в сетевой среде распределенных вычислений. Труды Пятой Всероссийской научной конференции молодых ученых СПбГУ 2008. стр. 78-89.

4. Сахаров И.Е. Организация упреждающего кэширования для приложений, исполняющихся в ССРВ. Вестник Ивановского Государственного Энергетического Университета Выпуск 1/2009. С. 85-91.

5. Сахаров И.Е. Математическое представление метода упреждающего кэширования и оценка эффективности разработанного метода. Вестник Ивановского Государственного Энергетического Университета. Выпуск 1/2009. С. 114-118.

6. Сахаров И.Е. Метод упреждающего кэширования дляприложений, исполняющихся в ССРВ. Вестник Российских Железных Дорог. Выпуск Апрель 2009. С. 34-37.

7. Сахаров И.Е. Метод упреждающего кэширования на основе разделения- потоков в высокопроизводительных распределенных вычислительных система: монография. Издательство Костромского Государственного Технологического Университета, 2008. — 100 с.

8. И. Олифер Н.А., Олифер В.Г. Сетевые операционные системы СПб: Питер, 2001. 544 стр. С. 267-280:

9. Олифер Н.А., Олифер В.Г. Комьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. 2-е изд. СПб: Питер, 2005. -544. стр. 243-265.

10. Кудрявцев Е.М. Основы имитационного моделирования различных систем М.: ДМК Пресс, 2004. 320 е.: ил. (Серия «Проектирование»).

11. Томашевский В.Н., Жданова Е.Г. Имитационной моделирование в среде GPSS М.:Бестселлер, 2003, с. 5-24.

12. Копылов В.Н., Онищенко Ю.А. Имитационное моделирование на-базе пакета GPSS/PS Учебно-методическое пособие. М.: Типография в.ч 33965, 1998.- 133 с.

13. Разработка макета распределенной файловой системы организации внешней памяти кластеров (Шифр — «ФСВП») Отчет научно-исследовательского Центра электронной вычислительной техники, 2002. — 75 с.

14. Рамакришман С. Эффективность сквозной кластеризации (Effective End-to-End Clustering). Oracle Magazine/Русской издание 2003 г. // http://www.oracIemagazine.ru.

15. Кузнецов С.Д. Операционная система UNIX. Информационно-аналитические материалы Центра Информационных технологий. Глава 2. Распределенные файловые системы. //http://www.dstu. edu. ru/povtas/sud/books/osunix/dir. html.

16. Федорчук А. Введение в POSIX'hbh3m. Сетевое издание LINUXCENTER. 2005. Глава 9. Физика файловых систем. // http://www.linuxcenter.ru.

17. Гордеев А.В. Операционные системы 2-е изд. Учебник для ВУЗов. ПИТЕР 2007. Глава 5.-736 с. стр. 561-592.

18. Орлов С. Оптика на рабочем месте. «Открытые системы», 2003 №10. стр. 27-30.

19. Корнеев В.В., Киселев А.В. Современные микропроцессоры. М.:

20. НОЛИДЖ, 1998.-240с. стр. 145-177.

21. Кузьминский М. Эволюция микроархитектуры х86-процессоров Intel. «Открытые системы», 2006 №10. // http://www. osp. ru/text/print/302/3584541. html

22. Процессоры Intel и AMD. КомпьютерПресс 2005, №12 стр. 42-45.

23. Bcuiuee М.К., Китаев Е.Л., Слепенков М.И., "Служба директорий LDAP как инструментальное средство для создания распределенных информационных систем", Препринт ИПМ, 2000.

24. М.К. McKusick. A Fast File System for UNIX. ACM Transaction on Computer System, 2(3); August 1994.

25. Официальный сайт компании Intel // hhtp://intel.com/.

26. Основы построения операционных систем промышленного назначения // hhtp: //www. ibm. com/developerworks/ru/edu/osarchitecturecoursel/section8. ht ml.

27. История процессоров Intel http://www.stfw.ru/.

28. Обзор дисковых подсистем хранения данных // http://www. itscope. ru/2007/01/22/obzordiskovychmassivov. html/.

29. Справочное руководство Mandrakelinux 10.1 Глава 8,9,10. I I http://lafox.net/docs/Command-Line-ru/index.html/,

30. Hennessy J.L. and Patterson D.A. Computer architecture: A quantitative approach. Morgan Kaufmann Publishers, San Francisco, CA, 1999.

31. Growchowski Ed. Ibm leadership in disk storage // http: //www. storage, ibm. com/technolo/growchows/grochoO l.htm/.

32. Patterson R.H. Informed Prefetching and Caching CMU-CS-97-204, -December 1997.

33. Patterson R.H., Gibson G.A., Satyanarayanan M. A Status Report on Research in Transparent Informed Prefetching. ACM Operating Systems Review, 1993.

34. Patterson R.H., Gibson G.A., Ginting E., Stodolsky D., Zelenka J. Informed prefetching and caching. In Proceedings of the 15th ACM Symposium on Operating System Principles (SOSP), December 1995.

35. Tomkins A., Patterson H., Gibson G.A. Informed multi-process prefetching and caching. In Proceedings of the 1997 ACM Sigmetrics International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), June 1997.

36. Chang F., Gibson G.A. Automatic I/O Hint Generation through Speculative Execution. Operating Systems Design and Implementation 2001.

37. Chang F. W. Using speculative execution to automatically hide I/O latency December 7, 2001 CMU-CS-01-172 p.21-23.

38. Trivedi. K.S. On the paging performance of array algorithms. IEEE Transactions on Computers, 26(10):938-947, 1977.

39. Brown A.D. and Mowry T.C. Taming the memory hogs: Using compiler inserted releases to manage physical memory intelligently. In Proceedings of the 4th USENIX Symposium on Operating Systems Design and Implementation (OSDI), October 2000.

40. Hammond L., Willey M., Olukotun K. Data speculation support for a chip multiprocessor. In Proceedings of the 8th ACM International Conference on Architectural Support for Programming Languages and Operating Systems1. ASPLOS), October 1998.

41. FranaszekP.A., Robinson J.T., Thomasian A. Concurrency control for high contention environments. ACM Transactions on Database Systems (TODS), 17(2):304-345, June 1992.

42. Salem K., Garcia-Molina H. Disk striping. In Proceedings of the 2nd IEEE International Conference on Data Engineering, 1986.

43. Curewitz K. Practical Prefetching via Data Compressing. In ACM Conference on Management of Data, May 1993.

44. Lei H., Duchamp D. An analytical approach to file prefetching. In Proceedings of the USENIX Winter 1997 Technical Conference, January 1997.

45. Harty K., Cheriton D.R. Application-controlled physical- memory using external page-cache management. Proceedings of the fifth international conference on Architectural- support for programming languages and operating systems, 1992.

46. Cao P., Felten E.W., Karlin A.R., Li K. Implementation and performance of integrated application-controlled file caching, prefetching and disk scheduling. ACM Transaction on Computer Systems (TOCS), 14(4):311-343, 1996.

47. Cao P. et al. A Study of Integrated Prefetching and Caching Strategies. In ACM Conference on Measurement and Modeling of Computer systems, May 1995.

48. Roshberg D. et al. Prefetching over a Network: Early Experience with CTIP. SIGMENTRIC Performance Evaluation Review, 25(3).

49. Tait C. D. et al. Intelligent File Hoarding for Mobile Computers. In Proceedings of the International Conference of Mobile Computing and

50. Networking, November 1995.

51. Mowry T.C., Demke A.K., Krieger O. Automatic Compiler-Inserted I/O Prefetching for Out-of-Core Applications. Proceedings of the 1996 Symposium on Operating Systems Design and Implementation.

52. LeroyX. The LinuxThreads Library. // http://pauillac. inria.fr/~xl eroy/l inuxthreads/.

53. Curewitz K. et al. Practical Prefetching via Data Compression. In ACM Conference on Management of Data, May 1997.

54. Kotz D. et al. Practical Prefetching Techniques for Parallel File Systems. In International Conference on Parallel and Distributed Information Systems, December 1999.

55. Foster /., Kesselman С., Tuecke S., The Anatomy of the Grid: Enabling Scalable Virtual Organizations. International Journal of High Performance Computing Applications, 15 (3). 200-222. 2001.

56. Официальный сайт Globus // http://www.globus.org.

57. Soltis S.R., Erickson G.M., Preslan K. W., O'Keefe M.T., Ruwart T.M. The Global File System: A File System for Shared Disk Storage IEEE Transactions on<Parallel and Distributed Systems.

58. Cams P.H., Ligon W.B. Ill, Ross R.B., Thakur R. PVFS: A Parallel File System For Linux Clusters Proceedings of the 4th Annual Linux Showcaseand Conference Atlanta, GA, October. 2000, c. 317-327.

59. Описание параллельной виртуальной файловой системы PVFS 2001 г. // http://www.parl. clemson. edu/pvfs/desc. html.

60. Описание файловой системы GPFS. //http://publib. boulder, ibm. com/infocenter/clresctr/topic/com. ibm. cluster.gpfs. doc/ gpfsJaqs/gpfsfaqs.html.

61. Wu S., Manber U. AGREP a fast approximate pattern-matching tool. In Proceedings of the USENIX Winter 1992 Technical Conference, 1992.

62. Официальный сайт файловой системы GFS // hhtp://sources, redhat. com/cluster/gfs/.

63. Red Hat Global File System. //http://www. linuxtopia. org/onlineJbooks/linuxsustemsadministartion/globalJil esystemGFS/index.html.

64. General Parallel File System. //hhtp://www-OS. ibm. com/systems/clusters/software/gpfs/index. html/.

65. Baker M., Hartman J.H., Kupfer M.D., ShiriffK. W. "Measurements of Distributed File System" Proc. 13th ACM Symp. Operating Systems Principles., pp. 198-211, Oct. 1991.

66. Freedman C.S., Burger J., DeWitt D.J. SPIFFI-A Scalable Parallel File System for the Intel Paragon. Parallel and Distributed Systems. November 1996 (vol. 7, № 11). Pp.1185-1200.

67. Silberschatz, Galvin, Gagne. Operating System Concepts with Java -7th Edition, 2007. Chapter 13: I/O Systems.

68. Cao P. et al. Application Controlled File Caching Policies. In Usenix summer 1994 technical conference, June 1994.

69. Официальный сайт СУБД PostreSQL // http://www.postgresql.com/.

70. Roschina N.A., Uvarov A.V., Osipov A.I. Natural convection in an annulus between coaxial horizontal cylinders with internal heat generation. Int. J. of Heat Mass Transfer. 2005, v. 48, p. 4518-4525