авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

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

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

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

КОСТЕНЕЦКИЙ Павел Сергеевич МОДЕЛИРОВАНИЕ И АНАЛИЗ ИЕРАРХИЧЕСКИХ МНОГОПРОЦЕССОРНЫХ СИСТЕМ БАЗ ДАННЫХ 05.13.18 – математическое моделирование, численные методы и комплексы программ

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

Челябинск – 2010

Работа выполнена на кафедре системного программирования Южно-Уральского государственного университета.

доктор физ.-мат. наук, профессор

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

СОКОЛИНСКИЙ Леонид Борисович.

Официальные оппоненты: член-корр. РАН, доктор физ.-мат. наук, профессор ВОЕВОДИН Владимир Валентинович;

кандидат физ.-мат. наук, доцент ДЕМЕНЕВ Алексей Геннадьевич.

Институт программных систем имени

Ведущая организация:

А.К. Айламазяна РАН

Защита состоится 3 марта 2010 г. в 12 часов на заседании диссертационного совета Д 212.298.14 при Южно-Уральском государственном университете по адресу: 454080, г. Челябинск, пр. Ленина, 76, ауд. 1001.

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

Автореферат разослан 2 февраля 2010 г.

Ученый секретарь диссертационного совета Л.Б. Соколинский

Общая характеристика работы

Актуальность темы. Современные многопроцессорные системы в большинстве случаев организуются по иерархическому принципу. Напри мер, большая часть вычислительных кластеров сегодня имеют трехуровне вую архитектуру. В рамках такой архитектуры многопроцессорная система строится как набор однородных вычислительных модулей, соединенных вы сокоскоростной сетью. Это – первый (верхний) уровень иерархии. Каждый вычислительный модуль является, в свою очередь, многопроцессорной сис темой с разделяемой памятью и образует второй уровень иерархии. Так как в современной кластерной системе, как правило, используются многоядерные процессоры, то мы получаем третий уровень иерархии. Еще одним источни ком многопроцессорных иерархий являются Grid-технологии, позволяющие объединять несколько различных кластеров в единую вычислительную сис тему. Подобная Grid-система будет иметь многоуровневую иерархическую структуру.

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

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

Разработать математическую модель мультипроцессоров баз данных, 1.

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

Разработать методы и алгоритмы, позволяющие реализовать предло 2.

женную модель на ЭВМ.

Спроектировать и реализовать эмулятор многопроцессорных иерархи 3.

ческих машин баз данных.

Произвести проверку адекватности модели мультипроцессоров баз 4.

данных путем сравнения результатов, полученных на эмуляторе, с ре зультатами, полученными на реальной параллельной СУБД.

При помощи эмулятора провести вычислительные эксперименты для 5.

поиска оптимальных аппаратных архитектур параллельных систем баз данных.

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

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

Разработана математическая модель для описания иерархических мно 1.

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

Создана модель операционной среды, позволяющая моделировать ра 2.

боту приложения с интенсивным дисковым вводом-выводом на иерар хической многопроцессорной системе.

Разработана стоимостная модель для оценки времени, расходуемого на 3.

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

Предложена модель для описания выполнения смеси транзакций в 4.

многопроцессорной системе.

Теоретическая ценность работы состоит в том, что в ней дано фор мальное описание модели мультипроцессоров баз данных DMM (Database Multiprocessor Model), включающей в себя модель аппаратной платформы, модель операционной среды, стоимостную модель и модель транзакций.

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



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

на Международной научной конференции «Высокопроизводительные вычисления, сети и коммуникационные системы (HPCNCS-07)» (9-12 июля 2007 г., Орландо, США);

на Всероссийской научной конференции «Научный сервис в сети Ин тернет: масштабируемость, параллельность, эффективность» (21-26 сентября 2009 г., Новороссийск);

на Всероссийской научной конференции «Научный сервис в сети Ин тернет: решение больших задач» (22–27 сентября 2008 г., Новорос сийск);

на Международной научной конференции «Параллельные вычисли тельные технологии» (29 января – 2 февраля 2007 г., Челябинск);

на Втором весеннем коллоквиуме молодых исследователей в области баз данных и информационных систем (SYRCoDIS) (1–2 июня 2005 г., Санкт-Петербург);

на Всероссийской научной конференции «Научный сервис в сети Ин тернет: технологии распределенных вычислений» (19-24 сентября 2005 г., Новороссийск);

на Международной научной конференции «Суперкомпьютерные сис темы и их применение» (26–28 октября 2004 г., Минск).

Публикации. По теме диссертации опубликовано 6 печатных работ и получено одно свидетельство Роспатента об официальной регистрации программы для ЭВМ. Статья [1] опубликована в научном журнале «Автома тика и телемеханика», включенном ВАК в перечень журналов, в которых должны быть опубликованы основные результаты диссертаций на соискание ученой степени доктора и кандидата наук. В статье [1] П.С. Костенецкому принадлежит раздел 2 (стр. 113-117). В работах [4-6] Л.Б. Соколинскому принадлежит постановка задачи, П.С. Костенецкому принадлежат все полу ченные результаты.

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

Содержание работы Во введении приводится обоснование актуальности темы, формули руются цели работы, ее новизна и практическая значимость;

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





Первая глава, «Обработка транзакций в многопроцессорных ие рархиях», посвящена описанию и исследованию многопроцессорных вы числительных систем с иерархической архитектурой. Иерархическая много процессорная система – это многопроцессорная система, в которой процес соры объединяются в единую систему с помощью соединительной сети, имеющей иерархическую структуру и обладающую свойствами однородно сти по горизонтали и неоднородности по вертикали. Однородность по гори зонтали означает, что в пределах одного уровня иерархии скорость обменов между двумя процессорами является постоянной величиной, независимо от того в каком поддереве иерархии эти процессоры находятся. Неоднород ность по вертикали означает, что скорость обменов на разных уровнях ие рархии существенно различается и этот факт должен учитываться в алго ритмах СУБД для многопроцессорных иерархий.

Основой параллельной обработки запросов в реляционных системах баз данных является фрагментный параллелизм. Данная форма параллелиз ма предполагает фрагментацию отношения, являющегося аргументом реля ционной операции, по дискам многопроцессорной системы. Обработка за проса в параллельной СУБД на вычислительном кластере состоит из трех этапов. На первом этапе SQL-запрос передается пользователем на выделен ную host-машину, где транслируется в некоторый последовательный физи ческий план. На втором этапе последовательный физический план преобра зуется в параллельный план, представляющий собой совокупность парал лельных агентов. Это достигается путем вставки специального оператора обмена exchange в соответствующие места дерева запроса. На третьем этапе параллельные агенты пересылаются с host-машины на соответствующие вы числительные узлы, где интерпретируются исполнителем запросов. Резуль таты выполнения агентов объединяются корневым оператором exchange на нулевом узле, откуда передаются на host-машину. Роль host-машины может играть любой узел вычислительного кластера.

В конце главы 1 произведен обзор наиболее известных параллельных вычислительных моделей с общей памятью RAM, PRAM, YPRAM, HPRAM, параллельных вычислительных моделей с распределенной памятью BSP, LogP, LogGP, параллельных вычислительных моделей с иерархией памяти Memory logP,DRAM(h,k), H-BSP, а так же рассмотрено использование ие рархической сети Петри для моделирования параллельных процессов. Про веденный обзор показывает, что указанные модели не учитывают иерархи ческую структуру соединительной сети. Кроме этого, все рассмотренные модели не учитывают специфику параллельных систем баз данных, исполь зующих фрагментный параллелизм. В связи с этим, актуальной является за дача разработки новых моделей и методов анализа иерархических много процессорных систем баз данных.

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

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

M = P D N, P D,P N,D N.

P обозначает множество процессорных модулей, D – множество дисковых модулей, N – множество модулей сетевых концентраторов.

DM-графом будем называть связный ациклический граф (свободное дерево) W ( M, E ), в котором множество ребер E удовлетворяет следующим ограничениям:

;

(1) P D,N init( A) P fin( A) M ;

(2) PP M E ( A, A ) E N M M init( A ) P fin( A ) M init( A) D fin( A) M ;

(3) DD M E ( A, A ) E N M M init( A ) D fin( A ) M init( A) M init( A ) M (4) M D P M E A, A, E A, A E E M.

init( A) M init( A ) M Здесь каждое ребро E представляется в виде двух противоположно направ ленных дуг A и A';

init(A) – узел, являющийся начальным для дуги A;

fin(A) – узел, являющийся конечным для дуги A.

DM-деревом будем называть DM-граф, в котором имеется выделенная вершина N N, называемая корневым сетевым концентратором.

Уровень узла дерева – это длина пути от корня до узла. Уровень корня всегда равен нулю. Высота h( ) дерева – это максимальный уровень его узлов. m-й ярус дерева – множество узлов дерева, на уровне m от корня дере ва. Узел M является сыном узла M, тогда, и только тогда, когда узлы M и M являются смежными и уровень M на единицу больше уровня M.

DM-дерево является регулярным, если выполняются следующие усло вия:

процессорные и дисковые модули не могут иметь сыновей, то есть они всегда являются листьями (концевыми узлами);

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

Пусть задано регулярное DM-дерево с корнем N. Пусть M 1,, M k – множество узлов 1-го яруса дерева. Определим поддерево M i с корнем в узле Mi (1 i k ) конструктивно следующим образом:

для всех j таких, что 1 j k и j i, удалить все листья, и инцидент 1) ные им ребра, от которых есть путь до корня N, имеющий длину больше единицы и проходящий через узел M j ;

если на шаге 1 было удалено не менее одного листа, снова перейти на 2) шаг 1, в противном случае перейти на шаг 3;

для всех j таких, что 1 j k и j i, удалить узел Mj и инцидентное 3) ему ребро;

удалить узел N и инцидентное ему ребро.

4) Теорема 1. Пусть задано регулярное DM-дерево с высотой больше единицы. Пусть M 1,, M k – множество узлов 1-го яруса дерева. Тогда для любого i, 1 i k, поддерево M i является регулярным DM-деревом ли бо тривиальным деревом, состоящим из одного узла M, такого, что M P D.

Теорема 2. Пусть – регулярное DM-дерево. Тогда h( ) P D, где P – множество процессорных модулей, D – множество дисковых моду лей дерева.

С каждым узлом M M( ) в DM-дереве связывается весовая функ ция ( M ), которая определяет время, необходимое узлу для обработки не которой порции данных.

DM-деревья 1 и 2 называются изоморфными, если существуют вза имно однозначное отображение f множества узлов M( 1 ) дерева 1 на мно жество узлов M( 2 ) дерева 2 и взаимно однозначное отображение g мно жества ребер E( 1 ) дерева 1 на множество ребер E( 2 ) дерева 2 такие, что:

(1) ребро E инцидентно узлам M и M в дереве 1 тогда и только тогда, когда ребро g(E) инцидентно узлам f(M) и f( M ) в дереве 2 ;

P( f( P) P( P ) );

(2) 1 D( D( D ) f( D) );

(3) 1 N( 1 ) f( N ) N( N );

(4) (f( M )) (M ).

(5) Упорядоченную пару отображений q (f,g) будем называть изомор физмом DM-дерева на DM-дерево. Под уровнем поддерева дерева 1 мы будем понимать уровень корня этого поддерева в дереве. Два поддере ва одного уровня называются смежными, если их корни являются братьями, то есть в дереве существует узел, являющийся общим родителем по отноше нию к корневым узлам данных поддеревьев.

Будем называть регулярное DM-дерево высоты h 2 симметрич ным, если любые два смежных поддерева уровня l ( 0 l h( ) ) имеют оди наковую высоту и являются изоморфными.

Теорема 3. Пусть – симметричное DM-дерево с корнем N. Тогда D, где P – множество процессорных модулей, D – мно h( ) log2 P жество дисковых модулей дерева.

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

Модель операционной среды if r(P) s then r строится следующим образом. Наи Поместить пакет E с адресом P в очередь D;

меньшей неделимой единицей обработ r(P)++;

ки данных является пакет. С каждым else wait;

дисковым модулем и модулем сетевого end if концентратора в модели DMM ассоции Рис. 1.

руется очередь, в которую помещаются if w(P) s then w пересылаемые пакеты. Модель DMM Поместить пакет E с адресом D в допускает асинхронный обмен пакета очередь родительского сетевого концентратора;

ми в том смысле, что процессорный мо w(P)++;

дуль может инициализировать новый else wait;

обмен, не дожидаясь завершения пре end if дыдущего. Процессорный модуль мо Рис. 2.

жет иметь в каждый момент не более sr Извлечь пакет E из очереди N;

незавершенных операций чтения и sw if (E) T(N) then Поместить E в очередь F(N);

незавершенных операций записи. Время else работы системы в модели DMM делится Найти максимальное поддерево U на дискретные промежутки, называе дерева T(N), содержащее (E);

if T( (E))==U then мые тактами. Для произвольного if (E) P then M M введем следующие обозначения:

r( (E))-- ;

else F(M) – родительский модуль узла M, Поместить E в очередь (E);

T(M) – поддерево с корнем в вершине end if M.

else Поместить E в очередь R(U);

Псевдокод операции чтения пред end if ставлен на рис. 1. Здесь r(P) – количест end if во незавершенных операций чтения Рис. 3.

процессора P, sr – максимальное допус Извлечь пакет E из очереди D;

if (E) D then тимое число незавершенных операций w((E))-- ;

чтения.

else Поместить E в очередь родитель На рис. 2 представлен псевдокод ского узла;

end if алгоритма инициирующего запись.

Рис. 4.

Здесь w(P) – количество незавершен ных операций записи процессора P, sw– максимальное допустимое число не завершенных операций записи.

Модуль сетевого концентратора N N осуществляет перманентную передачу пакетов по соединительной сети, выполняя алгоритм, изображен ный на рис. 3. Здесь E – пакет, (E) – адресат пакета E, T(N) – поддерево с корнем N, F(N) – родительский модуль узла N, P – множество процессорных модулей, r(Р) – количество незавершенных операций чтения процессора P, R(U) – корень поддерева U.

Дисковый модуль D D осуществляет перманентное чтение и запись пакетов, выполняя алгоритм, изображенный на рис. 4. Здесь (E) – отправи тель пакета, w((E)) – количество незавершенных операций записи отправи теля.

Такт определяется как следующая последовательность действий:

каждый модуль сетевого концентратора обрабатывает все пакеты, 1) ожидающие передачи;

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

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

3) Стоимостная модель определяется следующим образом. С каждым модулем связывается коэффициент трудоемкости MM. Полагаем hP 1, P P. Для модуля сетевого концен hM, 1 hM miN тратора N N вводим функцию помех f N (m ). Здесь miN обозна N i N N чает число пакетов, проходящих через N на i-том такте;

0 N 1 – масшта бирующий коэффициент;

N 1 – пороговое значение (максимальное число одновременно передаваемых пакетов, не вызывающее замедление работы модуля сетевого концентратора). Время, требуемое модулю сетевого кон центратора N для выполнения i-того такта, вычисляется по формуле tiN hN f N (miN ), N N. Общее время работы системы, затраченное на обра ботку смеси транзакций в течении k тактов, вычисляется по формуле k max(tiN ) max(hD ).

t NN ND i Модель транзакций строится следующим образом. Последовательная транзакция Z моделируется путем задания двух групп процессов и:

. Группа включает в себя читающие процессы, Z {, }, группа – пишущие процессы. Для каждого читающего и пишущего про цесса задается количество обращений к диску, которое он должен произве сти. После того, как процесс выполнил все обращения, он удаляется из мно жества или соответственно. Транзакция Z {, } считается завер шенной, когда. Каждая транзакция Z {, } разбивается на ко нечную последовательность шагов: Z1,, Z s. Здесь s обозначает количество шагов транзакции. В соответствие с этим каждый процесс x тран закции Z разбивается на s шагов: x1,, xs. Каждый шаг xi ( i 1,, s ) описы вается тройкой чисел (ni, pi, di ), где d i – номер диска, с которым процесс x обменивается данными на i-том шаге;

ni – количество обращений к диску;

pi – вероятность обращения процесса x к диску Ddi на каждом такте работы эмулятора в течении i-го шага.

Параллельная транзакция Z, выполняемая на l процессорных модулях, 1 l моделируется путем задания l последовательных транзакций Z,, Z, каж дая из которых выполняется на отдельном процессорном модуле. Алгоритм, моделирующий выполнение отдельной транзакции на процессорном модуле, определяется следующим образом. Пусть задана транзакция Z {, }, со стоящая из s шагов: Z1,, Z s. Обозначим через X множество всех читающих и пишущих процессов, составляющих транзакцию Z: X. Пусть X {x1,, x r }. Каждый процесс x j ( j 1,, r ) делится на s шагов: x1j,, xsj.

Пусть выполнение транзакции Z находится на i-том шаге. Предположим, что процесс x j получил управление. Пусть i-тый шаг процесса x j имеет вид xij (nij, pij, di j ). Предполагается, что процесс x j может получить управление на i-том шаге только в случае nij 0. Тогда на текущем такте выполняется следующая последовательность действий.

j Значение ni уменьшается на единицу.

1.

Процесс x j инициирует операцию обмена с диском, имеющим номер 2.

di j.

r nij Если 0 и i s, то увеличить i (номер текущего шага транзак 3.

j ции) на единицу.

Модель DMM допускает выполнение на одном процессоре смеси по Z i i 1,..., k следовательных транзакций в режиме разделения времени.

i При этом каждая транзакция Z (i 1,..., k ) представляется своей собствен i i i ной парой групп читающих и пишущих процессов: Z {, }. Все множе ство процессов моделирующих выполнение смеси транзакций на некотором k i i процессоре P P определяется следующим образом: ). При ( P i запуске новой транзакции на процессоре P, в множество P динамически добавляются читающие и пишущие процессы, представляющие данную транзакцию. Если какой-либо процесс завершается, то он удаляется из мно жества P.

Выполнение смеси транзакций P на некотором процессоре P органи зуется следующим образом. На каждом такте работы эмулятора процессор P должен инициализировать одну операцию обмена с дисками. В соответствие с этим, процессор должен выбрать некоторый процесс x и произвести операцию чтения с диска или записи на диск, ассоциированный с x на теку щем шаге. Такой процесс называется активным. Все процессы из множества организуются в список. Вводится указатель на текущий элемент списка (его начальная позиция может быть произвольной). Для определения актив ного процесса используется алгоритм, изображенный на рис. 5.

for (P=P.begin();

P!=P.end();

P++){ Здесь P – множество всех про prob = 0;

цессорных модулей DM-дерева;

for(x=P.Ф.begin();

x!=P.Ф.end();

x++){ if (n(x,i(x)) == 0) continue;

s(x) – общее количество шагов prob += p(x,i(x));

процесса x;

n(x,i) – количество об if (g(prob)) return x;

};

ращений к диску, которые оста };

лось выполнить процессу x на ша Рис. 5.

ге i;

p(x,i) – вероятность обраще ния процесса x к диску при выполнении i-го шага;

g – функция срабатыва ния, вычисляемая следующим образом. Для каждого шага i процесса x x известна вероятность pi обращения процесса x к диску, ассоциированному с x этим процессом на i-том шаге. Функция срабатывания g ( pi ) G определя ется как функция дискретной случайной величины G, закон распределения которой задается следующим рядом распределения:

G 1 x x p 1- pi P i В третьей главе, «Эмулятор многопроцессорных иерархических машин баз данных», описывается процесс проектирования и реализации программной системы DMS (Database Multiprocessor Simulator), представ ляющей собой эмулятор многопроцессорных иерархических машин баз дан ных. Проектирование эмулятора производилось при помощи унифицирован ного языка моделирования UML 2.0. Требования к эмулятору DMS зафикси рованы при помощи модели вариантов использования. Приводятся диаграм мы классов модели аппаратной платформы и модели операционной среды.

Построены диаграммы последовательности для операций чтения и записи, диаграмма последовательности работы модуля сетевого концентратора и диаграмма последовательности работы дискового модуля. Для представле ния информации о мультипроцессорных иерархиях разработан язык описа ния многопроцессорных иерархических конфигураций HMML, базирующийся на синтаксисе расширяемого языка разметки XML. Для автоматизации про цесса создания входных файлов разработан HMML-генератор. Эмулятор DMS был реализован на языке C++. Исходные тексты эмулятора свободно доступны в сети Интернет по адресу http://kps.susu.ru/science/dms/. На эмуля тор DMS получено свидетельство Роспатента об официальной регистрации программы для ЭВМ.

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

Для подтверждения адекватности модели DMM была использована параллельная СУБД «Омега», установленная на вычислительном кластере «СКИФ Урал». Размеры отношений R и S составляли соответственно 6 000 000 и 600 000 000 записей. Результаты выполнения транзакций приве дены на СУБД «Омега» приведены на рис. 6. С помощью эмулятора DMS было произведено моделирование выполнения таких же транзакций на DM-дереве, описывающем вычислительный кластер «СКИФ Урал». Резуль таты этих экспериментов приведены на 7. Сравнение показывает, что эмуля тор DMS адекватно моделирует выполнение транзакций на вычислительном кластере для любых значений коэффициента перекоса. Это подтверждает адекватность модели DMM.

Рис. 6. Рис. 7.

Рис. 8. Рис 9.

На рис. 8 показано влияние пропускной способности систем ной шины на общую производи тельность SMP-узла на многоядер ных процессорах. Эти результаты были получены с помощью эмуля тора DMS. Данный эксперимент показывает, что при увеличении числа процессорных ядер и дисков, системная шина становится узким местом SMP архитектуры. Когда Рис. 10.

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

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

На рис. 10 показа Табл. 1.

Цена ны зависимости, полу Тип с инфра структурой ченные с помощью эму Основные характеристики узла лятора DMS, которые (тыс. руб.) Одноядерный процессор Intel Xeon DP можно использовать для EM64T и один диск SAS 73.4 Гб оценки эффективности Двуядерный процессор Intel Xeon E решений по приобрете и два диска SAS 73.4 Гб нию и модернизации вы Два двуядерных процессора Intel Xeon E3110 и четыре диска SAS 73.4 Гб числительных кластеров Два четырехъядерных процессора Intel для приложений баз Xeon E5472 и восемь дисков SAS 73.4 Гб данных. Указанные за висимости были получены при моделировании четырех типов узлов, приве денных в табл. 1. Предположим, например, что в бюджете некоторой органи зации в 2010 г. имеется 10 миллионов рублей на приобретение вычислитель ного кластера для приложений баз данных. Необходимо подобрать на эту сумму наиболее производительную аппаратную архитектуру, варьируя кон фигурацию и количество узлов системы. На основе зависимостей на рис. можно определить, что при заданной цене, наибольшую производительность будет обеспечивать конфигурация, состоящая из 25 узлов типа 4.

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

Основные результаты диссертационной работы На защиту выносятся следующие новые научные результаты.

Разработана новая математическая модель мультипроцессоров баз 1.

данных DMM (Database Multiprocessor Model), включающая в себя мо дель аппаратной платформы, модель операционной среды, стоимост ную модель и модель транзакций.

Разработаны методы и алгоритмы, позволяющие реализовать модель 2.

DMM на ЭВМ.

Разработан эмулятор многопроцессорных иерархических машин баз 3.

данных DMS (Database Multiprocessor Simulator), реализующий модель DMM. Произведена проверка адекватности модели мультипроцессоров баз данных путем сравнения результатов, полученных на эмуляторе DMS, с результатами, полученными на реальной параллельной СУБД.

С использованием эмулятора DMS проведены вычислительные экспе 4.

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

Публикации по теме диссертации Статьи, опубликованные в журналах из списка ВАК 1. Костенецкий П.С., Лепихов А.В., Соколинский Л.Б. Технологии парал лельных систем баз данных для иерархических многопроцессорных сред // Автоматика и телемеханика. 2007. No. 5. C. 112-125.

Другие публикации 2. Костенецкий П.С. Моделирование параллельных систем баз данных для вычислительных кластеров // Научный сервис в сети Интернет:

масштабируемость, параллельность, эффективность: Труды Всероссийск.

науч. конф. (21-26 сентября 2009 г., г. Новороссийск). М.: Изд-во МГУ, 2009. С. 300-304.

3. Костенецкий П.С. Разработка эмулятора виртуальных мультипроцессоров баз данных // Параллельные вычислительные технологии: Труды международной науч. конф. (29 января - 2 февраля 2007 г., г. Челябинск). Челябинск.: Изд-во ЮУрГУ, 2007. C. 285.

4. Kostenetskiy P.S., Sokolinsky L.B. Analysis of Hierarchical Multiprocessor Database Systems // Proceedings of the 2007 International Conference on High Performance Computing, Networking and Communication Systems (HPCNCS-07), July 9-12 2007, Orlando, FL, USA. ISRST. 2007. P. 245–251.

5. Костенецкий П.С., Соколинский Л.Б. Моделирование иерархических архитектур параллельных систем баз данных // Научный сервис в сети Интернет: технологии распределенных вычислений: Труды всероссийск.

науч. конф. (19–24 сентября 2005 г., г. Новороссийск). М.: Изд-во МГУ, 2005. C. 21–24.

6. Костенецкий П.С., Соколинский Л.Б. Моделирование и анализ иерархических архитектур параллельных систем баз данных // Суперкомпьютерные системы и их применение (SSA'2004) (26– октября 2004 г., г. Минск, Республика Беларусь), тез. докл. междунар.

науч. конф., Минск: ОИПИ НАН Беларуси. 2004. С. 116–120.

Свидетельство о регистрации программы 7. Костенецкий П.С. Соколинский Л.Б. Свидетельство Роспатента об официальной регистрации программы для ЭВМ «Эмулятор параллельных систем баз данных» № 2009616225 от 11.11.2009.

Работа выполнялась при поддержке Российского фонда фундаментальных исследований (проекты 06-07-89148, 09-07-00241-А).

Подписано в печать 28.01. Формат 60х84 1/16. Бумага офсетная.

Печать офсетная. Усл. печ. л. 1,0. Уч.-изд. л. 1,2.

Тираж 100 экз.

Типография «Фотохудожник» 454111, г. Челябинск, ул. Свободы, 155/

 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.