Конференции ИВТ СО РАН

Третья российско-германская школа по параллельным вычислениям на высокопроизводительных вычислительных системах

28 августа - 8 сентября 2006 года, Новосибирск, Академгородок

Тезисы докладов

7-ое сентября

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

Костенецкий П.С.

Южно-Уральский государственный университет,
каф. "Системное программирование" (Челябинск)

Введение

В настоящее время все большее распространение получают иерархические многопроцессорные архитектуры. В многопроцессорной системе с иерархической архитектурой процессорные устройства, память, диски и проч. связываются друг с другом в соответствии с некоторой иерархией. На первом уровне иерархии находятся процессорные ядра, размещенные на одном кристалле. На втором уровне находятся многоядерные процессоры, объединенные в многопроцессорные модули с общей памятью (SMP). На третьем уровне SMP-модули объединяются в кластер с помощью высокоскоростной соединительной сети. Четвертый уровень представляют Grid-системы, включающие в себя несколько кластеров. Корпоративные Grid-системы могут объединяться в кооперативные Grid-объединения на базе Интернет. И так далее.

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

Иерархические архитектуры порождают большое количество различных классов конфигураций. Некоторая классификация таких архитектур дана в {B_Sok04}. Исследование подобных архитектур затруднено, так как практическое конструирование мультипроцессоров требует больших финансовых затрат, связанных с приобретением и реконфигурацией дорогостоящего оборудования. Как следствие, актуальной становится задача разработки моделей представления многопроцессорных систем баз данных, которые позволяли бы исследовать различные многопроцессорные конфигурации без их аппаратной реализации. Моделирование всех одноуровневых архитектур для оперативной обработки транзакций было выполнено Стоунбрейкером и Бхайдом {B_Bhide88a,B_Bhide88b}. В работах {B_Bouganim96, B_Xu97} моделируются некоторые классы двухуровневых конфигураций, однако в общем виде многопроцессорные иерархические конфигурации не исследовались. В связи с этим возникает проблема выбора оптимального класса конфигураций для определенного класса приложений баз данных. В данной работе описана модель DMM (Database Multiprocessor Model), позволяющая моделировать и исследовать произвольные многопроцессорные иерархические конфигурации в контексте приложений класса OLTP {B_DeWitt95}.

Моделирование иерархических архитектур

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

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

Аппаратное обеспечение параллельной системы баз данных представляется в виде DM-дерева. DM-дерево - это ориентированное дерево {B_Knuth3}, узлы которого относятся к одному из трех классов:

- процессорные модули;

- дисковые модули;

- модули сетевых концентраторов.

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

На структуру DM-дерева накладываются следующие ограничения:

1) корнем DM-дерева может быть только модуль сетевого концентратора; дисковые и процессорные модули не могут иметь дочерних узлов, т.е. они всегда

2) являются листьями DM-дерева.

3) модуль сетевого концентратора не может иметь менее двух дочерних узлов.

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

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

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

С каждым дисковым модулем и модулем сетевого концентратора в модели DMM ассоциируется очередь, в которую помещаются пересылаемые пакеты.

Модель DMM допускает асинхронный обмен пакетами в том смысле, что процессорный модуль может инициализировать новый обмен, не дожидаясь завершения предыдущего. Однако мы предполагаем, что процессорный модуль может иметь в каждый момент не более s_{r} незавершенных операций чтения и s_{w} незавершенных операций записи.

Время работы системы в модели DMM делится на дискретные промежутки, называемые тактами. Такт определяется как фиксированная последовательность шагов, семантика которых будет определена ниже.

Пусть P обозначает множество всех процессорных модулей DM-дерева, D- множество всех дисковых модулей, N - множество всех модулей сетевых концентраторов, {M}={P}U{D}U{N} - множество всех узлов DM-дерева. Для произвольного M из {M} введем следующие обозначения: F(M) - родительский модуль узла M, T(M) - поддерево с корнем в вершине M.

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

Операция чтения.

Пусть процессорному модулю P требуется прочитать пакет E с диска D. Если процессор P ранее инициализировал s_{r} ещё незавершенных операций чтения, то он переводится в состояние ожидания. Если количество незавершенных операций чтения меньше s_{r}, то в очередь диска D помещается пакет E с адресом получателя alpha(E)=P и адресом отправителя beta(E)=D. На рис. представлен псевдокод данного алгоритма.

Операция записи.

Пусть процессорному модулю P требуется записать пакет E на диск D из множества D. На рис. представлен псевдокод алгоритма, инициирующего запись.

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

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

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

Модель DMM допускает выполнение на одном процессоре смеси параллельных транзакций. При этом каждая транзакция Z_{i} (i=1..k) представляется своей собственной парой групп читающих и пишущих процессов.

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

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

На каждом такте работы все активные процессорные модули должны выполнять операции чтения-записи. В соответствии с этим, активный процессорный модуль должен выбрать некоторый процесс и произвести операцию чтения с диска или записи на диск, ассоциированный с ним. Мы будем называть такой процесс активным. Функция активности имеет следующую семантику значений: 1 - процесс активен на данном такте, 0 - процесс не активен.

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

P.S. Из-за невозможности вставлять формулы и рисунки, текст серьезно пострадал.

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

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]