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

На правах рукописи КОСТЕНЕЦКИЙ Павел Сергеевич

МОДЕЛИРОВАНИЕ И АНАЛИЗ ИЕРАРХИЧЕСКИХ МНОГОПРОЦЕССОРНЫХ СИСТЕМ БАЗ ДАННЫХ

05.13.18 - математическое моделирование, численные методы и комплексы программ

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

Челябинск-2010

004600484

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

Научный руководитель: доктор физ.-мат. наук, профессор

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

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

ВОЕВОДИН Владимир Валентинович;

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

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

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

Ведущая организация: Институт программных систем имени

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

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

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

Л.Б. Соколинский

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

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

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

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

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 г., Челябинск);

- на Втором весеннем коллоквиуме молодых исследователей в области баз данных и информационных систем (8У11Со018) (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 включает в себя модель аппаратной платформы, модель операционной среды, стоимостную модель и модель транзакций. Модель аппаратной платформы строится следующим образом. Множество модулей многопроцессорной системы разбивается на три непересекающихся подмножества:

т = ф и э и от, <р п э = 0, <р п «к = 0, ю п т=0 _

ф обозначает множество процессорных модулей, D - множество дисковых модулей, 9t - множество модулей сетевых концентраторов.

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

( [/

\/р еф

УЛГ еЙЛ

(тк(А) = /'лГт(А) = М)

^ ) = Рл Пп(Л ) = А/)^

^V (¡т1(/Г) = О л Пп(Л') = М)

=>Ме<Я

=>М бЭТ

УМ 6 ОТ

(1) (2)

(3)

(4)

'(¡ш1(Л) = Л/ути(Л') = М) " I л(1пи(Я) = М V ¡п!1(Я') = Л/)

Здесь каждое ребро Е представляется в виде двух противоположно направленных дуг А и А'; тк(А) - узел, являющийся начальным для дуги А; Гт(А) -узел, являющийся конечным для дуги А.

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

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

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

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

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

Пусть задано регулярное £>А/-дерево Тс корнем N. Пусть {М[,...,Мк}

- множество узлов 1-го яруса дерева Т. Определим поддерево Тм с корнем в узле М: (1 < < к) конструктивно следующим образом:

1) для всех_/' таких, что \<]<к и удалить все листья, и инцидентные им ребра, от которых есть путь до корня Ы, имеющий длину больше единицы и проходящий через узел М];

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

3) для всехJ таких, что \<]'<к и У^/, удалить узел тЦ- и инцидентное ему ребро;

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

Теорема 1. Пусть задано регулярное ДМ-дерево Тс высотой больше единицы. Пусть {М,,...,МЛ} - множество узлов 1-го яруса дерева 77 Тогда для любого /, 1 < г < к, поддерево Ти является регулярным ДМ-деревом ли-

бо тривиальным деревом, состоящим из одного узла М, такого, что МефиЗЭ.

Теорема 2. Пусть Т- регулярное ДЛ/-дерево. Тогда А(Т) < и £>|, где ф - множество процессорных модулей, £> - множество дисковых модулей дерева Т.

С каждым узлом М е ЯЛ(Т) в £>М-дереве Тсвязывается весовая функция ?](М), которая определяет время, необходимое узлу для обработки некоторой порции данных.

ИМ-деревья Т, и Тг называются изоморфными, если существуют взаимно однозначное отображение Г множества узлов 2Л (7,) дерева Т, на множество узлов ЯЯ(Т2) дерева Т, и взаимно однозначное отображение g множества ребер <£(Т,) дерева 7; на множество ребер <Е(Х2) дерева Т2 такие, что:

(1) ребро Е инцидентно узлам М и М' в дереве 7[ тогда и только тогда, когда ребро инцидентно узлам ((М) и ("(А/') в дереве Т2;

(2) РеЩТ,) о ф(Т2).

(3) ОеЩТ,) о {(й)ЕЩТ2).

(4) МеЩТ,) о ^)6«П(Г,);

(5) = 1 (М)

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

Будем называть регулярное ОМ-дерево Т высоты А > 2 симметричным, если любые два смежных поддерева уровня 1 (о <1 <И(Т)) имеют одинаковую высоту и являются изоморфными.

Теорема 3. Пусть Т- симметричное ДЛ/-дерево с корнем N. Тогда И(Т)< 1од2(|<}Зи2)|), где ф - множество процессорных модулей, Э - множество дисковых модулей дерева Т.

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

if r(f>) < sr then

Поместить пакет E с адресом p в очередь D;

г(Я ++ ; else wait;

end if__

Рис. I.

if w{P) < s then

v

Поместить пакет E с адресом D в очередь родительского сетевого концентратора;

w(p)++; else wait;

end if_

Рис. г.

Извлечь пакет Е из очереди N; if а(£) <г Т(Ю then

Поместить Е в очередь FIN) ; else

Найти максимальное поддерево U дерева TIN), содержащее а(Е); if Т(а(Е> )= = [/ then if ог(ЙеР then

r(a{E) ) -- ; else

Поместить E в очередь a(E); end if else

Поместить E в очередь R{U); end if

end if_

Рис. 3.

Извлечь пакет E из очереди D; if a(E) GD then

wlP(E))-- ; else

Поместить E в очередь родитель-

Модель операционной среды строится следующим образом. Наименьшей неделимой единицей обработки данных является пакет. С каждым дисковым модулем и модулем сетевого концентратора в модели О ММ ассоциируется очередь, в которую помещаются пересылаемые пакеты. Модель И ММ допускает асинхронный обмен пакетами в том смысле, что процессорный модуль может инициализировать новый обмен, не дожидаясь завершения предыдущего. Процессорный модуль может иметь в каждый момент не более незавершенных операций чтения и незавершенных операций записи. Время работы системы в модели йММделится на дискретные промежутки, называемые тактами. Для произвольного Мед.Л введем следующие обозначения: /•"(Л-/) - родительский модуль узла М, Т(М) - поддерево с корнем в вершине М.

Псевдокод операции чтения представлен на рис. 1. Здесь г(Р) - количество незавершенных операций чтения процессора Р, ¡г - максимальное допустимое число незавершенных операций чтения.

ского узла; end if

Рис. 4.

На рис. 2 представлен псевдокод алгоритма инициирующего запись. Здесь \у(Р) - количество незавершенных операций записи процессора Р, максимальное допустимое число незавершенных операций записи.

Модуль сетевого концентратора ЫеЛ осуществляет перманентную передачу пакетов по соединительной сети, выполняя алгоритм, изображенный на рис. 3. Здесь Е - пакет, а(Е) - адресат пакета Е, Т(М) - поддерево с корнем N. - родительский модуль узла М ф - множество процессорных модулей, г(Р) - количество незавершенных операций чтения процессора Р, Я(Ц) ~ корень поддерева и.

Дисковый модуль £>е£> осуществляет перманентное чтение и запись пакетов, выполняя алгоритм, изображенный на рис. 4. Здесь Р(Е) - отправитель пакета, \у(р(Е)) - количество незавершенных операций записи отправителя.

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

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

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

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

Стоимостная модель определяется следующим образом. С каждым модулем А/еЙЛ связывается коэффициент трудоемкости /гм е Е, 1 < км < +оо. Полагаем Ър = 1, УР е ф. Для модуля сетевого концен-

тратора IVеЩ вводим функцию помех /к(т") -

5Н. Здесь /я," обозна-

чает число пакетов, проходящих через N на /-том такте; 0 < ды < 1 - масштабирующий коэффициент; ты > 1 - пороговое значение (максимальное число одновременно передаваемых пакетов, не вызывающее замедление работы модуля сетевого концентратора). Время, требуемое модулю сетевого концентратора N для выполнения /-того такта, вычисляется по формуле 'Г Общее время работы системы, затраченное на обра-

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

Модель транзакций строится следующим образом. Последовательная транзакция 2 моделируется путем задания двух групп процессов р и а: 2 = {р,а>}, Группа р включает в себя читающие процессы,

группа со - пишущие процессы. Для каждого читающего и пишущего процесса задается количество обращений к диску, которое он должен произвести. После того, как процесс выполнил все обращения, он удаляется из множества р или со соответственно. Транзакция 2 = {р,о)} считается завершенной, когда р и а = 0. Каждая транзакция Z = {р, О)} разбивается на конечную последовательность шагов: 2Х,...,2Здесь 5 обозначает количество шагов транзакции. В соответствие с этим каждый процесс хери© транзакции 2разбивается на £ шагов: х,,...,.*^. Каждый шаг х{ (/ = 1,...,х) описывается тройкой чисел (и,,^,,^), где с1- - номер диска, с которым процесс х обменивается данными на /-том шаге; и, - количество обращений к диску;

- вероятность обращения процесса х к диску 011 на каждом такте работы

эмулятора в течении 1-го шага.

Параллельная транзакция Ъ, выполняемая на / процессорных модулях, моделируется путем задания / последовательных транзакций , каждая из которых выполняется на отдельном процессорном модуле. Алгоритм, моделирующий выполнение отдельной транзакции на процессорном модуле, определяется следующим образом. Пусть задана транзакция X = {р,а>}, состоящая из 5 шагов: 2.....,2^. Обозначим через Xмножество всех читающих

и пишущих процессов, составляющих транзакцию Ъ\ X = риа>. Пусть Х-{х\...,^}. Каждый процесс х-' (у = 1,.. ,,г) делится нал шагов: Пусть выполнение транзакции 2 находится на /-том шаге. Предположим, что процесс х' получил управление. Пусть г'-тый шаг процесса х1 имеет вид хI - (^'Р!'^!)-Предполагается, что процесс г1 может получить управление на /-том шаге только в случае и/ >0. Тогда на текущем такте выполняется следующая последовательность действий.

1. Значение п! уменьшается на единицу.

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

3. Если = 0 и / < то увеличить / (номер текущего шага транзак-

н

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

Модель ПММ допускает выполнение на одном процессоре смеси последовательных транзакций = в режиме разделения времени. При этом каждая транзакция 2' (г =1,...,&) представляется своей собственной парой групп читающих и пишущих процессов: X' ={р',со'}. Все множество процессов моделирующих выполнение смеси транзакций на некотором

к

процессоре Р е ф определяется следующим образом:

¡=1

запуске новой транзакции на процессоре Р, в множество Ф,, динамически добавляются читающие и пишущие процессы, представляющие данную транзакцию. Если какой-либо процесс завершается, то он удаляется из множества ФР.

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

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

Здесь ф - множество всех процессорных модулей /Ж-дерева; я(х) - общее количество шагов процесса х; п(х,1) - количество обращений к диску, которые осталось выполнить процессу х на шаге г"; р(хл) - вероятность обращения процесса х к диску при выполнении ¿-го шага; g - функция срабатывания, вычисляемая следующим образом. Для каждого шага ( процесса х е Ф известна вероятность р" обращения процесса х к диску, ассоциированному с этим процессом на г-том шаге. Функция срабатывания g{px¡) = С определяется как функция дискретной случайной величины С, закон распределения которой задается следующим рядом распределения:

for (P=P.beginO ;P!=P.end() ;P+ + ) { prob = 0;

for(x=P.$.begin() ,-x!=P.4>.end() ; x+ + ) { if (n(x, i(x)) == 0) continue; prob += p (x, i (x) ) ; if (g(prob)) return x;

b

Рис. 5.

G 1 0

Р Р* 1-rf

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

В четвертой главе, «Вычислительные эксперименты», отражены результаты вычислительных экспериментов, выполненных с использованием

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

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

50

40

0

2

20 ]---_

ю!-

16 32

Количество плов

8,. 16 32 Количество \члов

Рис. 6.

Рис. 7.

-О-т» к

-А : >

__ -С

Л

. д - ■

-о- -.. &• - - - -

~W-i.vpi.niie при у»ми яри »»ОЛ»

Рис. 8.

» 10 12 (4 16 18 20 23 24 26 2.1 .1» 32 34 ЗГ> Скорость диско в/сст (ус.гед.>

Рис 9.

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

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

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

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

Количеств.' V-LKiB

Рис. 10.

тельности.

Табл. 1.

Тип ума Основные характеристики Цена с инфраструктурой (тыс. руб.)

1 Одноядерный процессор Intel Xeon DP ЕМ64Т и один диск SAS 73.4 Гб 266

2 Двуядерный процессор Intel Xeon ЕЗ110 и два диска SAS 73.4 Гб 298

3 Два двуядерных процессора Intel Xeon ЕЗ 110 и четыре диска SAS 73.4 Гб 325

4 Два четырехъядерных процессора Intel Xeon Е5472 и восемь дисков SAS 73.4 Гб 395

Основные результаты диссертационной работы

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

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

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

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

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

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

Статьи, опубликованные журналах из списка ВАК

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

Другие публикации

2. Костенецкий П.С. Моделирование параллельных систем баз данных для вычислительных кластеров // Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность: Труды Всероссийск. науч. конф. (21-26 сентября 2009 г., г. Новороссийск). М.: Изд-во МГУ. 2009. С. 300-304.

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

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

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

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

Подписано в печать 28.01.2010 Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1,0. Уч.-изд. л. 1,2. Тираж 100 экз.

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

Свидетельство о регистрации программы

Введение.

Глава 1. Обработка транзакций в многопроцессорных иерархиях.

1.1. Многопроцессорные иерархии.

1.2. Организация параллельной обработки запросов.

1.3. Обзор моделей многопроцессорных систем.

1.3.1. Аппаратно-архитектурные модели.

1.3.2. Классификация моделей параллельных вычислений.

1.3.3. Параллельные вычислительные модели с общей памятью.

1.3.4. Параллельные вычислительные модели с распределенной памятью

1.3.5. Параллельные вычислительные модели с иерархией памяти.

1.4. Выводы по главе 1.

Глава 2. Модель мультипроцессоров баз данных.

2.1. Требования к модели.

2.1.1. Специфика приложений баз данных класса ОЬТР.

2.1.2. Иерархическая структура соединительной сети.

2.1.3. Дисковый ввод/вывод.

2.1.4. Фрагментный параллелизм.

2.1.5. Передача сообщений по соединительной сети.

2.1.6. Оценка стоимости запросов.

2.1.7. Специфика реляционной модели данных.

2.1.8. Параллельные транзакции.

2.1.9. Межтранзакционный параллелизм.

2.2. Формальное описание модели.

2.2.1. Базовые определения.

2.2.2. Модель аппаратной платформы.

2.2.3. Модель операционной среды.

2.2.4. Стоимостная модель.

2.2.5. Модель транзакций.

2.3. Выводы по главе 2.

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

3.1. Модель вариантов использования эмулятора ЭМБ.

3.2. Архитектура эмулятора БМ8.

3.3. Принципы работы эмулятора БМЭ.

3.4. Язык описания конфигураций.

3.5. Выводы по главе 3.

Глава 4. Вычислительные эксперименты.

4.1. Параметры вычислительных экспериментов.

4.2. Подтверждение адекватности модели БММ.

4.3. Моделирование 8МР-узлов.

4.4. Влияние интерконнекта и дисков на масштабирование.

4.5. Оптимизация стоимости расширения системы.

4.6. Выводы по главе 4.

Актуальность темы

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

Важным классом приложений для многопроцессорных систем являются задачи, связанные с обработкой сверхбольших баз данных [81]. Возникновение сверхбольших баз данных обусловлено расширением сферы применения СУБД. Примерами приложений, характеризующихся сверхбольшим объемом хранимых данных, являются электронная коммерция [43,89], электронные библиотеки [11], геоинформационные системы [38, 104], мультимедийные архивы [97, 131], социальные сети [39, 126], научные базы данных [22, 81] и многие другие.

Одной из самых больших и быстро наполняемых научных баз данных является база данных проекта WLCG (Worldwide Large Hadron Collider Computing Grid) [79, 116]. Главной целью проекта WLCG является использование грид-среды для обработки экспериментальных данных получаемых с Большого адронного коллайдера (Large Hadron Collider, LHC) Европейского центра ядерных исследований (CERN). Поток экспериментальных данных, который необходимо обрабатывать, составляет около 15 петабайт в год [8].

Другим примером сверхбольшой базы данных является база данных проекта системы SkyServer проекта SDSS (Sloan Digital Sky Survey) [121, 122, 133]. Данный проект предполагает создание виртуальной обсерватории, доступной через Интернет. База данных проекта должна объединить в себе полную информацию о наблюдениях всех участков звездного неба различными обсерваториями мира. Суммарный объем данных, поступающих с телескопов, составляет около 5 петабайт в год [123].

Работы по созданию виртуальной обсерватории ведутся также и в России [3, 27]. В настоящее время начаты работы по двум масштабным космическим экспериментам «Лира» и «Свеча» [31], целью которых является высокоточный многоцветный фотометрический обзор звезд всего неба вплоть до 16-17 звездной величины. В обзор войдут около 400 млн. звезд. Измерения будут вестись в 10 спектральных полосах от 0.2 до 1.0 мкм с борта Российского сегмента МКС. Для хранения базы данных проекта «Лира» потребуется дисковое пространство суммарным объемом до 1 петабай-та. Для хранения данных проекта «Свеча» потребуется дисковое пространство размером несколько экзабайт.

Еще одним примером сверхбольших баз данных являются базы данных проекта EOS/DIS (Earth Observation System/Data Information System) [76, 124], разрабатываемого агентством NASA в США. Система наблюдения земли EOS включает в себя множество спутников, которые собирают информацию, необходимую для изучения долгосрочных тенденций состояния атмосферы, океанов, земной поверхности. Начиная с 1998 года, спутники поставляют информацию в объеме 1/3 петабайт в год. Предполагается, что к 2010 году общий объем поддерживаемых в системе данных превысит 20 петабайт.

Фактически единственным эффективным решением проблемы хранения и обработки сверхбольших баз данных является использование параллельных систем баз данных [67, 81], обеспечивающих параллельную обработку запросов на многопроцессорных вычислительных системах. В области технологий параллельной обработки запросов для реляционных баз данных достигнуты значительные успехи, воплощенные в целом ряде исследовательских и коммерческих СУБД. В качестве примеров успешных коммерческих проектов создания параллельных систем баз данных можно привести DB2 Parallel Edition [109], NonStop SQL [37, 68, 83] и Teradata [47, 77]. Подобные системы объединяют тысячи процессоров и жестких дисков и способны обрабатывать петабайтные базы данных. Тем не менее, в области параллельных систем баз данных до сих пор остается ряд направлений, требующих дополнительных научных исследований [42]. Одно из них - дальнейшее развитие аппаратной архитектуры параллельных систем баз данных. В ближайшем будущем крупные организации будут располагать базами данных объемом в несколько петабайт [49]. Для обработки подобных объемов информации потребуются параллельные машины с новыми иерархическими многопроцессорными многоядерными архитектурами, поддерживающими сотни тысяч процессоров [51], что в десятки раз превышает их число в самых мощных современных системах.

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

Цель и задачи исследования

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

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

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

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

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

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

Методы исследования

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

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

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

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

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

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

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

Теоретическая и практическая ценность

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

Практическая ценность работы заключается в том, что на базе предложенной модели DMM разработан эмулятор многопроцессорных иерархических машин баз данных DMS {Database Multiprocessor Simulator). Эмулятор DMS представляет собой программный комплекс, позволяющий моделировать и исследовать эффективность различных иерархических многопроцессорных конфигураций [32] в контексте задач баз данных класса ОЬТР[Щ.

Структура и объем работы

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

Основные результаты диссертационной работы

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

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

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

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

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

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

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

2. 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. 245251.

3. Костенецкий П. С. Моделирование параллельных систем баз данных для вычислительных кластеров // Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность: Труды Всерос-сийск. науч. конф. (21-26 сентября 2009 г., г. Новороссийск). М.: Изд-во МГУ. 2009. С. 300-304.

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

5. Костенецкий П. С. Jlenuxoe А.В., Соколинский Л.Б. Некоторые аспекты организации параллельных систем баз данных для мультипроцессоров с иерархической архитектурой // Алгоритмы и программные средства параллельных вычислений: Сб. науч. тр. Вып. 9./ Екатеринбург: УрО РАН. 2006. С. 42-83.

6. Kostenetskii P.S., Lepikhov A.V., Sokolinskii L.B. Technologies of parallel database systems for hierarchical multiprocessor environments // Automation and Remote Control. 2007. Vol. 68, No. 5. P. 847-859.

7. Костенецкий П.С., Соколинский Л.Б. Моделирование иерархических архитектур параллельных систем баз данных // Научный сервис в сети Интернет: технологии распределенных вычислений: Труды всерос-сийск. науч. конф. (19-24 сентября 2005 г., г. Новороссийск). М.: Изд-во МГУ. 2005. С. 21-24.

8. Kostenetsky P.S., Sokolinsky L.B., KuligA. Simulating multiprocessor database system architectures // Proceedings of Spring Young Researcher's Colloquium in Databases and Information Systems (SYRCoDIS'2005). June

1-2, 2005. Research-in-progress reports. St.-Petersburg, Russia: VVM.com.Ltd., 2005. P. 25-27.

9. Костенецкий П.С., Соколинский Л.Б. Моделирование и анализ иерархических архитектур параллельных систем баз данных // Суперкомпьютерные системы и их применение (SSA'2004) (26-28 октября 2004 г., г. Минск, Республика Беларусь), тез. докл. междунар. науч. конф., Минск: ОИПИ НАН Беларуси. 2004. С. 116-120.

10. Бородулин КВ., Костенецкий П.С. Исследование производительности вычислительных кластеров на базе четырехъядерных процессоров Intel Xeon Е5472 по системе тестов TopCrunch // Научный сервис в сети Интернет: решение больших задач: Труды Всероссийск. науч. конф. (2227 сентября 2008 г., г. Новороссийск). М.: Изд-во МГУ. 2008. С. 109113.

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

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

Апробация работы

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

- на Всероссийской научной конференции «Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность» (21-26 сентября 2009 г., Новороссийск); на Всероссийской научной конференции «Научный сервис в сети Интернет: решение больших задач» (22-27 сентября 2008 г., Новороссийск); на Международной научной конференции «Высокопроизводительные вычисления, сети и коммуникационные системы (НРС!ч1С8-07)» (9-12 июля 2007 г., Орландо, США); на Международной научной конференции «Параллельные вычислительные технологии» (29 января - 2 февраля 2007 г., Челябинск); на Всероссийской научной конференции «Научный сервис в сети Интернет: технологии распределенных вычислений» (19-24 сентября 2005 г., Новороссийск); на Втором весеннем коллоквиуме молодых исследователей в области баз данных и информационных систем (БУКСоБК) (1-2 июня 2005 г., Санкт-Петербург); на Международной научной конференции «Суперкомпьютерные системы и их применение» (26-28 октября 2004 г., Минск).

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

1. Буч Г., Рамбо Д., Якобсон И. Язык UML. Руководство пользователя. 2-е изд. М.: ДМК Пресс, 2007. 496 с.

2. Витковский В.В. и др. Проект Российской виртуальной обсерватории. // Научный сервис в сети Интернет: Труды Всероссийск. науч. конф. (2328 сентября 2002 г., г. Новороссийск). М.: Изд-во МГУ. 2002.

3. Воеводин Вл.В. Решение больших задач в распределенных вычислительных средах. //Автоматика и Телемеханика. 2007, No. 5, С. 32^4-5.

4. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608 с.

5. Вычислительный кластер «СКИФ Урал». URL: http://supercomputer.susu.ru/computers/ckifural/index.html (дата обращения: 08.11.2009).

6. Девитт Д., ГрэйД. Параллельные системы баз данных: будущее высокоэффективных систем баз данных // СУБД. 1995. №2. С. 8-31.

7. Демичев А.П., Ильин В.А., Крюков А.ТТ. Введение в грид-технологии. Препринт НИИЯФ МГУ 2007-11/832, 2007. 87 с.

8. КнутД.Э. Искусство программирования, т. 1. Основные алгоритмы, 3-е изд. М.: Издательский дом «Вильяме», 2000. 720 с.

9. Когаловский М.Р. Энциклопедия технологий баз данных. М.: Финансы и статистика, 2002. 800 с.

10. Когаловский М.Р., Новиков Б. А. Электронные библиотеки новый класс информационных систем // Программирование, 2000. №3. С. 3-8.

11. Корлеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999. 320 с.

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

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

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

15. Куссулъ H.H., Шелестов А.Ю. Grid-системы для задач исследования Земли. Архитектура, модели и технологи. Киев: "Наукова думка", 2008. 452 с.

16. Кузнецов С.Д. SQL. Язык реляционных баз данных. -М.: Майор, 2001. -192 с.

17. Кузнецов С.Д. Большие хлопоты с большими объемами данных // Открытые системы. СУБД. 2008. №4. С. 20-27.

18. Кузьминский M. Nehalem: микроархитектура и производительность // Открытые системы. 2009. №8. С. 10-14.

19. Левин И.И., Омаров О.М. Расширение сетей Петри для моделирования распределенных вычислений // Информационные технологии моделирования и управления. Воронеж: Научная книга, 2005. С. 555-562.

20. Лепихов A.B., Соколинский Л.Б. Обработка запросов в СУБД для кластерных систем // Программирование. 2010 (в печати).

21. Лескин A.A., Мальцев П.А., Спиридонов A.M. Сети Петри в моделировании и управлении. JI.: Наука, 1989. 133 с.

22. Никулина И.О., Старцева Е.Б. Применение аппарата сетей Петри для моделирования экономических процессов: Метод, указания./ Уфимск. гос. авиац. техн. ун-т; Уфа, 2001. 32 с.

23. Омаров О.М. Моделирование параллельных алгоритмов с использованием сетей Петри // Искусственный интеллект. 2005. № 4. С. 240-244.

24. Параллельная СУБД Омега для многопроцессорных иерархий Сайт проекта. URL: http://fireforge.net/projects/omega/ (дата обращения: 24.10.2009).

25. Соколинский Л.Б. Обзор архитектур параллельных систем баз данных // Программирование. 2004. № 6. С. 49-63.

26. Соколинский Л.Б. Организация параллельного выполнения запросов в многопроцессорной машине баз дан-ных с иерархической архитектурой // Программирование. 2001. No. 6. С. 13-29.

27. Стивене У.P. UNIX: взаимодействие процессов. СПб.: Мастер-класс, 2003. 576 с.

28. Федотов И.Е. Некоторые приемы параллельного программирования / ГОУ ВПО «Московский государственный институт радиотехники, электроники и автоматики» М., 2008. 188 с.

29. Хаманн Ф. Отказоустойчивая операционная система Tandem NonStop Kernel // Открытые системы. 1997. №3. С. 32-36.

30. Цветков В.Я. Геоинформационные системы и технологии. М.: Финансы и статистика, 1998. 288 с.

31. Aggarwal A., et al. A model for hierarchical memory // Proceedings of the 19th Annual ACM Symp. on Theory of Computing. ACM. 1987, P. 305314.

32. Aggarwal A., et al. Hierarchical Memory with Block Transfer // Proceedings of the 28th IEEE Symp. On Foundations of Computer Science. USA. 1987. P. 204-216.

33. Agrawal R., Ailamaki A., Bernstein P.A. et al. The Claremont Report on Database Research // Communications of the ACM. 2009. Vol. 52, No. 6.1. P. 56-65.

34. Agrawal R., Srikant R., Xu Y. Database technologies for electronic commerce // 28th international conference on Very Large Data Bases, Hong Kong, China, August 20 23, 2002. Proceedings. VLDB Endowment, 2002. P. 1055- 1058.

35. Alfawair M., Aldabbas., et al. Grid Evolution // IEEE International Conference on Computer Engineering & Systems, Cairo, Egypt, 27-29 November, 2007, Proceedings. IEEE Computer Society. 2007. P. 158-163.

36. Alpern B, et al. The uniform memory hierarchy model of computation // Al-gorithmica. 1994. Vol. 12 No. 2/3 P. 72-109.

37. Ballinger C., Fryer R. Born To Be Parallel: Why Parallel Origins Give Te-radata an Enduring Performance Edge // IEEE Data Engineering Bulletin. 1997. Vol. 20, No. 2. P. 3-12.

38. Bar-Noy A., Kipnis S. Designing broadcasting algorithms in the Postal model for message passing systems // Proceedings of the SPAA'92, USA. 1992. P. 13-22.

39. Bell G., Gray J. What's next in high-performance computing // Communications of. ACM. 2002. Vol. 45, No. 2, P. 91-95.

40. Bell G., Gray J., Szalay A.S. Petascale Computational Systems // IEEE Computer. 2006. Vol. 39, No. 1. P. 110-112.

41. Bilardi G. Models for parallel and hierarchical computation // Proceedings of the 4th international conference on Computing frontiers. ACM: New York, 2007. P. 95-96.

42. Borkar S. Y. et al. Platform 2015: Intel processor and platform evolution for the next decade: URL:http://www.cs.helsmki.fl/u/kerola/rio/papers/borkar2015.pdf (дата обращения: 08.11.2009). 2005.

43. Bosque J.L., Pastor L. A Parallel Computational Model for Heterogeneous Clusters // IEEE Transactions on Parallel and Distributed Systems. 2006. Vol. 17, No. 12. P. 1390-1400.

44. Cameron K. W., et al. Lognp and Log3p: accurate analytical model of point-to-point communication in distributed systems // IEEE Transactions on Computers, 2007. Vol. 56 No. 3. P. 314-327.

45. Cameron K. W., Sun X.H. Quantifying locality effect in data access delay: memory LogP // Proceedings of the 2003 IEEE International Parallel and Distributed Processing Symposium, France. 2003.

46. Cavin R., Hutchby J.A., et al. Emerging Research Architectures // Computer. 2008. Vol. 41, No. 5. P. 33-37.

47. Cha H., Lee D. H-BSP: A Hierarchical BSP Computation Model // The Journal of Supercomputing. 2001. Vol. 18, No. 2. P. 179-200.

48. Chen H., Decker J., Bierbaum N. Future Networking for Scalable I/O // 24th IASTED international Conference on Parallel and Distributed Computing and Networks, Innsbruck, Austria, February 14—16, 2006, Proceedings, ACTA Press, 2006. P. 128-135.

49. Cole R., et al. The APRAM: incorporating asynchrony into the PRAM model // Proceedings of the 1st Annual ACM SPAA'89. USA. 1989. P. 169-178.

50. Cook S, Reckhow R. Time Bounded Random Access Computers // Journal of Computer and Systems Sciences. 1973. No. 7. P. 354-375.

51. Cormen T.H., Goodrich M.T. A bridging model for parallel computation, communication, and I/O // ACM Computing Surveys. 1996. Vol. 28, No.4.

52. Culler D., et al. LogP: A Practical Model of Parallel Computation. Commun. ACM, 1996. Vol. 39, No. 11. P. 78-85.

53. Culler D, et al. LogP: towards a realistic model of parallel computation // Proceedings of PPoPP'93 USA. 1993. P. 1-12.

54. Dasgupta S. A Hierarchical Taxonomic System for Computer Architectures // IEEE Computer. 1990. Vol. 23, No. 3. P. 64-74.

55. De La Torre P., Kruskal C.P. Towards a single model of efficient computation in real parallel computers // Future Generation Computer Systems, Elsevier Science Publishers. 1992, Vol. 8, No. 4. P. 395-408.

56. DeWitt D.J., Gray J. Parallel Database Systems: The Future of HighPerformance Database Systems // Communications of the ACM. 1992. Vol. 35, No. 6. P. 85-98.

57. Englert S., Glasstone R., Hasan W. Parallelism and its Price: A Case Study of NonStop SQL/MP // ACM SIGMOD Record. 1995. Vol. 24, No. 4. P. 61-71.

58. Flynn M.J. Computer Organization and Architecture // Operating Systems, An Advanced Course. Springer, 1978 (Lecture Notes in Computer Science; Vol. 60). P. 17-98.

59. Flynn M.J. Very High Speed Computing Systems // Proc. IEEE. 1966. Vol. 54. P. 1901-1909.

60. Flynn M.J., RuddK. W. Parallel architectures // ACM Computing Surveys. 1996. Vol. 28, No. 1. P. 67-70.

61. Fortune S., Wyllie J,C. Parallelism in random access computers // Proceedings of the Tenth Annual ACM Symposium on Theory of Computing. USA. 1978. P. 114-118

62. Foster I. Т., Grossman R.L. Blueprint for the future of high-performance networking: Data integration in a bandwidth-rich world // Communications of the ACM. 2003. Vol. 46, No. 11. P. 50-57.

63. Foster I. Т., Kesselman C., Nick J., Tuecke S. The Physiology of the Grid: An Open Grid Service Architecture for Distributed Systems Integration. URL: http://www.globus.org/ogsa (дата обращения: 08.11.2009). 2002.

64. Foster I. What is the Grid? A Three Point Checklist. URL: http://www.gridtoday.com/02/0722/100136.html (дата обращения: 08.11.2009). 2002.

65. Frew J., Dozier J. Data Management for Earth System Science // ACM SIGMOD Record. 1997. Vol. 26, No. 1. P. 27-31.

66. Gibbons P., et al. The QRQW PRAM: accounting for contention in parallel algorithms. Proceedings of the 5th annual ACM-SIAM SODA'94, USA. 1994. P. 638-648.

67. Girone M. CERN Database Services for the LHC Computing Grid // International Conference on Computing in High Energy and Nuclear Physics (CHEP'07). Journal of Physics: Conference Series. Vol.119. 2008.

68. Goldschlager L M. A Universal interconnection pattern for parallel computers // Journal of the ACM. 1982, 29(4). P. 1073-1086.

69. Gray J., et al. Scientific Data Management in the Coming Decade // SIG-MOD Record. 2005. Vol. 34, No. 4. P. 34-41.

70. Handbook of Parallel Computing: Models, Algorithms and Applications. Chapman & Hall/CRC Press, 2007. 1224 p.

71. Heywood T., Ranka S. A practical hierarchical model of parallel computation. 1. The model. // Journal of Parallel and Distributed Computing. 1992. Vol. 16. P. 212-232.

72. Hill J., McColl B., Stefanescu D.C. et al. BSPlib: The BSP programming library//Parallel Computing, Vol. 24. 1998. P. 1947-1980.

73. Hill J., Crumpton P.I., Burgess D.A. The theory, practice, and a tool for BSP performance prediction // EuroPar'96, August 1996. Springer-Verlag, 1996. P. 697-705.

74. Hill J., Jarvis S., Siniolakis C., et al. Analysing an SQL application with a BSPlib call-graph profiling tool // EuroPar'98, LNCS, Springer-Verlag, September 1998. Springer Berlin. 1998. P. 157-164.

75. JaJa J.F., Kwan W.R. The block distributed memory model // IEEE Transaction on Distributed and Parallel Systems. 1996. Vol. 7, No. 8. P. 830-840.

76. Kalakota R., Whinston A. Readings in Electronic Commerce. Addison-Wesley, 1997. 340 p.

77. Kim C. Future Memory Technology Trends and Challenges // 7th international Symposium on Quality Electronic Design, March 27-29, 2006, proceedings. IEEE Computer Society. P. 513.

78. Kostenetskii P.S., Lepikhov A. V., Sokolinskii L.B. Technologies of parallel database systems for hierarchical multiprocessor environments // Automation and Remote Control. 2007. Vol. 68, No. 5. P. 847-859.

79. Leiserson C., Maggs B. Communication efficient parallel algorithms for distributed random access computers // Algorithmica. 1988. Vol. 3. P. 53-77.

80. Li Z. Y., et al. Models and resource metrics for parallel and distributed computation // Proceedings of 28th Hawaii International Conference on System Sciences. USA. 1995. Vol. 2. P. 51-60.

81. Lu G. Multimedia Database Management System. Artech House, 1999.

82. Maggs B M, et al. Models of Parallel Computation: A Survey and Synthesis // Proceedings of 28th Hawaii Int. Conf. on System Sciences. Wailea, USA. 1995. P. 61-70.

83. Maertens H. A Classification of Skew Effects in Parallel Database Systems // 7th International Euro-Par Conference, August 28-31, 2001, Manchester, UK, Proceedings. Springer. 2001. Vol. 2150. P.291-300.

84. McColl W.F. General purpose parallel computing. Lectures on Parallel Computation // Cambridge University Press. 1993. P. 337-391.

85. Meuer H.W. The TOP500 Project: Looking Back Over 15 Years of Supercomputing Experience. Informatik Spektrum 2008. Vol. 31 No. 3 P. 203222.

86. Norman M. G., Zurek T., Thanisch P. Much Ado About Shared-Nothing // ACM SIGMOD Record. 1996. Vol. 25, No. 3. P. 16-21.

87. Parkhurst J., Darringer J., Grundmann B. From single core to multi-core: preparing for a new exponential // IEEE/ACM international Conference on Computer-Aided Design, San Jose, California, November 05-09, 2006. ACM, 2006. P. 67-72.

88. Peterson J.L. Petri Net Theory and the Modeling of Systems, Englewood Cliffs, Prentice Hall, 1981. 290 p.

89. Pfister G. Sizing Up Parallel Architectures // Database Programming Design OnLine. URL: http://www.dbpd.com (дата обращения: 08.11.2009). 1998. Vol. 11, No. 5.

90. Rahm E. Parallel Query Processing in Shared Disk Database Systems // ACM SIGMOD Record. 1993. Vol. 22, No. 4. P. 32-37.

91. Raman V., Han W., Narang I. Parallel Querying with Non-Dedicated Computers // Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, August 30 September 2, 2005. ACM. 2005. P. 61-72.

92. ReedD.A. Grids, the TeraGrid, and Beyond // Computer. 2003. Vol. 36, No. l.P. 62-68.

93. Roberts L. G. Beyond Moore's Law: Internet Growth Trends // Computer 2000. Vol. 33, No. 1 P. 117-119.

94. Rumbaugh J. Getting Started Using Use Cases to Capture Requirements / J. Rumbaugh // Journal of Object Oriented Programming. 1994. Vol. 7, № 5. P. 8-12.

95. Schoene R., Nagel W.E., Oiger S Analyzing Cache Bandwidth on the Intel 2 Core Architecture // Parallel Computing: Architectures, Algorithms and Applications. 2007. Vol. 38. P. 365-372.

96. Scherger M., Baker J., Potter J. Using UML to Describe the BSP Model of Parallel Computation // Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications. CSREA Press. 2002. Vol. 2. P. 578-583.

97. Selic B. UML 2: a model-driven development tool // IBM Syst. J. 2006. Vol. 45, №3. P. 607-620.

98. Shiers J. The Worldwide LHC Computing Grid (worldwide LCG) // Computer Physics Communications. 2007. Vol. 177 No. 1-2. P. 219-223.

99. Skillicorn D.B., Talia D. Models and languages for parallel computation // ACM Computing Surveys. 1998. Vol. 30, No. 2. P. 123-169.

100. Snyder L. Type architectures, shared memory, and the corollary of modest potential // Annu. Review of Computer Science, 1986, Vol. 1. P. 289-317.

101. Stonebraker M. The case for shared nothing // Database Engineering Bulletin. 1986. Vol. 9, No. 1. P. 4-9.

102. Szalay A.S. The Sloan Digital Sky Survey and beyond // SIGMOD Record. -2008. Vol. 37, No. 2. P. 61-66.

103. Szalay A.S., et al. The SDSS SkyServer Public Access to the Sloan Digital Sky Server Data // Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Madison, Wisconsin, June 3-6, 2002. ACM Press. 2002.

104. Szalay A.S., Gray J., Vandenberg J. Petabyte Scale Data Mining: Dream or Reality? // Technical Report MSR-TR-2002-84. Microsoft Research. 2002.

105. Szalay A., Gray J. The World-Wide Telescope // Science. 2001. Vol. 293, P. 2037-2040.

106. Tsvetovat M., Diesner J., Carley, K.M. Netlntel: a database for manipulation of rich social network data. Technical Report CMU-ISRI-04-135. Carnegie Mellon University, School of Computer Science, Institute for Software Research International. 2005.

107. ValiantL.G. A bridging model for parallel computation. Communication of the ACM. 1990. Vol. 33, No. 8. P. 103-111.

108. Valiant L.G. General Purpose Parallel Architectures / Handbook of theoretical computer science (Vol. A): algorithms and complexity. Cambridge, MA, USA. MIT Press. 1991. P. 943-973.

109. Vangal S. An 80-Tile 1.28TFLOPS Network-on-Chip in 65nm CMOS // Solid-State circuits conference, February 11-15,2007. P. 98-105.

110. W3C. Extensible Markup Language (XML) 1.0 (Fifth Edition). World Wide Web Consortium. 2006. URL: http://www.w3.org/TR/2006/REC-xml-20060816 (дата обращения: 08.11.2009).

111. Wen J., Li Q., Ma W., Zhang H. A multi-paradigm querying approach for a generic multimedia database management system // ACM SIGMOD Record Volume 32 , Issue 1, March 2003. Proceedings. ACM, New York, NY, USA. P. 26-34.

112. Williams M.H., Zhou S. Data Placement in Parallel Database Systems // Parallel database techniques. IEEE Computer society, 1998. P. 203-218.

113. XiangH., Baker M., Nichol R. Experiences Mirroring and Distributing the Sloan Digital Sky Survey // International Conference on Grid and Cooperative Computing Workshops, Hunan, China, 21-23 October, 2006, IEEE Computer Society, 2006. P. 518-521.

114. Zhang Y., Chen G., Sun G, Miao Q. Models of parallel computation: a survey and classification // Frontiers of Computer Science in China. 2007. Vol. 1, No. 2. P. 156-165.

115. Zhang Y.Q. DRAM(h): a parallel computation model for high performance numerical computing // Chinese Journal of Computers. 2003. Vol. 26, No. 12. P. 1660-1670.

116. Zhang Y.Q. Performance optimizations on parallel numerical software package and study on memory complexity. Dissertation of Doctoral Degree Beijing, P.R. China / Institute of Software, Chinese Academy of Sciences, 2000.