| Руководитель проекта Соколинский Леонид Борисович |
|
Краткая аннотация Предложена формализация понятия
"параллельная система баз данных'', базирующаяся на концепции виртуальных
машин. На основе данной формализации разработан новый подход к классификации
архитектур параллельных систем баз данных. Сформулированы требования к
параллельной системе баз данных, служащие критериями для сравнения различных
архитектур. Рассмотрены различные классы архитектур параллельных систем баз
данных и проведен их сравнительный анализ. |
| Полученные за отчетный
период важнейшие результаты 1) На основе концепции виртуальных машин баз данных выполнены классификация и сравнительный анализ архитектур параллельных систем баз данных. 2) Реализован эмулятор виртуальных мультипроцессоров баз данных (ЭВМБД). 3) Выполнена адаптация алгоритма LFU-K для веб-кэширования. Проведены вычислительные эксперименты на искусственных и реальных трассах, подтверждающие высокую эффективность LFU-K для веб-кэширования. 4) Реализован эмулятор функций MPI для среды Windows, позволяющий использовать штатный отладчик MS Visual C++. Исходные тексты и документация эмулятора доступны в Интернет по адресу http://omega.susu.ru/simulatorMPI. 5) Реализован прототип параллельной СУБД Омега на кластере Infinity (http://cluster.susu.ru). Исходные тексты и документация прототипа доступны в Интернет по адресу http://omega.susu.ru. 6) Разработан и апробирован электронный учебный курс "Параллельные системы баз данных". Материалы курса доступны в Интернет по адресу http://pdbs.susu.ru. 7) Создана WWW страница, посвященная прототипу параллельной СУБД Омега: http://omega.susu.ru/index.html. 8) Обновлена и дополнена WWW страница проекта Омега: http://sok.susu.ru/OmegaProject/index.html. 9) Обновлена и дополнена WWW страница, посвященная данному гранту РФФИ: http://sok.susu.ru/grants/rfbr/2003/k_omega.html. 10) Опубликовано 7 научных работ, в том числе: одна статья в журнале "Программирование" и одна статья в "Lecture Notes in Computer Science". |
| Методы и подходы,
использованные в ходе выполнения проекта АРХИТЕКТУРА ПАРАЛЛЕЛЬНЫХ СИСТЕМ БАЗ ДАННЫХ. В работах [1, 7] введено понятие виртуальной параллельной машины баз данных, которое может служить эффективным инструментом при проектировании сложных гибридных архитектур параллельных систем баз данных. Данный инструмент позволяет определять различные уровни абстракции при проектировании системной архитектуры. Этапы проектирования представляют собой иерархию виртуальных машин. Каждая следующая виртуальная машина реализует предыдущую. В целях классификации и сравнительного анализа архитектур современных параллельных систем баз данных проанализирован классификационный подход М. Стоунбрейкера, предложенный в середине 80-х годов ХХ века. Показано, что классификация Стоунбрейкера нуждается в определенном уточнении и обобщении. Данное обобщение и уточнение было нами выполнено путем использования абстракции виртуальных параллельных машин баз данных и введения дополнительных классов иерархических кластерных архитектур. Сформулированы и рассмотрены основные требования к параллельной системе баз данных. На основе сформулированных требований и обобщенной классификации Стоунбрейкера был проведен сравнительный анализ современных архитектур параллельных систем баз данных. Этот анализ показал, что наилучшие показатели имеет гибридные архитектуры класса CDN. Эксперименты, проведенные на базе системы Омега, подтверждают сделанный вывод. Более детальную информацию можно найти в работе [1], полный текст которой доступен по адресу http://sok.susu.ru/papers/abstracts/Sokolinsky%2004R.html. МОДЕЛИРОВАНИЕ И АНАЛИЗ ИЕРАРХИЧЕСКИХ АРХИТЕКТУР ПАРАЛЛЕЛЬНЫХ СИСТЕМ БАЗ ДАННЫХ. Предложен новый подход к моделированию иерархических аппаратных архитектур параллельных систем баз данных. Разработан программный комплекс, получивший название ЭВМБД (Эмулятор Виртуальных Мультипроцессоров Баз Данных). ЭВМБД позволяет моделировать практически любые архитектуры параллельных систем баз данных. Это дает возможность исследовать широкий спектр перспективных архитектур, в том числе гибридных иерархических кластерных архитектур, без больших затрат на их аппаратную реализацию. С помощью разработанного программного комплекса можно выполнять моделирование работы многопроцессорных систем баз данных на вычислительной системе с любым количеством процессоров, в том числе и на однопроцессорной. Данный подход был применен для моделирования иерархических гибридных архитектур класса CDN [1]. Предварительные эксперименты подтвердили адекватность и эффективность предложенной модели. Более детальную информацию по ЭВМБД можно найти в работе [4], полный текст которой находится по адресу http://kps.susu.ru/publications/SSA2004.pdf. ПРИМЕНЕНИЕ АЛГОРИТМА LFU-K ДЛЯ WEB-КЭШИРОВАНИЯ. В работе [3] исследована применимость алгоритма LFU-K для веб-кэширования. Алгоритм LFU-K был разработан в рамках данного проекта для параллельной СУБД Омега [2]. Проведенные исследования показали, что этот алгоритм может с успехом применяться и для веб-кэширования. Результаты экспериментов представлены в работе [3], полный текст которой находится по адресу http://syrcodis.citforum.ru/2004/prischepa.pdf. ТЕХНОЛОГИЯ ОТЛАДКИ ПАРАЛЛЕЛЬНЫХ MPI-ПРОГРАММ В СРЕДЕ WINDOWS. В работе [5] предложено решение, основанное на эмуляции параллельных процессов и обменов данными между ними с помощью стандартных средств ОС Windows. Разработан эмулятор обменов сообщениями, который представляет собой динамически компонуемую библиотеку, интерфейс которой есть подмножество функций стандарта MPI, используемое в разработке прототипа СУБД Омега. Таким образом, эмулятор позволяет запускать прототип непосредственно из среды MS Visual C++ (без загрузчика) и использовать весь спектр средств встроенного отладчика. Переход от отладки к тестированию и обратно не требует изменения исходных текстов модулей и связан лишь с изменением параметров их компоновки. Эмулятор обеспечивает представление процессов, запускаемых на процессорных узлах, в виде процессов ОС Windows, каждый из которых представляет собой совокупность следующих потоков (нитей): мастер, отправитель, получатель и терминатор. Поток-мастер выполняет собственно код процесса. Поток-отправитель обрабатывает массив, элементами которого являются очереди сообщений, передаваемых другим процессам программы. Поток-получатель обрабатывает очередь сообщений, поступающих от потоков-отправителей других процессов программы. Поток-терминатор выполняет аварийное завершение всех процессов программы, если поток-мастер одного из процессов выполнил функцию MPI_Abort. Прием-передача сообщения от процесса S процессу R выглядит следующим образом (далее мы будем именовать потоки как Master, Sender и Receiver, а индексы имен будут указывать на принадлежность к процессу). При выполнении функции посылки сообщения поток MasterS добавляет в соответствующую очередь потока SenderS запись о данном сообщении и открывает ему семафор для начала передачи сообщения. Поток SenderS создает в оперативной памяти процесса S область, доступную для потока ReceiverR, записывает в нее передаваемое сообщение и генерирует для ReceiverR событие о необходимости начать прием. После этого поток SenderS переходит к ожиданию подтверждения от потока ReceiverR о завершении приема. При получении подтверждения SenderS уничтожает ранее созданную область и памяти и закрывает семафор передачи сообщения. Поток ReceiverR выполняет перманентное ожидание события о необходимости начать прием. При наступлении такого события он обращается к области памяти, которую создал SenderS, и считывает переданное им сообщение. После этого ReceiverR высылает потоку SenderS подтверждение о завершении приема сообщения. Разработанный эмулятор имеет самостоятельное значение и может быть использован не только в рамках разработки прототипа параллельной СУБД, но и для отладки параллельных программ, выполняющих обмен сообщениями на основе стандарта MPI. ПРОТОТИП ПАРАЛЛЕЛЬНОЙ СУБД ОМЕГА. Реализован прототип параллельной СУБД Омега на кластере Infinity (http://cluster.susu.ru). Основной формой параллельной обработки запросов в прототипе является фрагментный параллелизм. Каждое отношение (таблица) базы данных делится на горизонтальные фрагменты, распределяемые по процессорным узлам вычислительной системы. Способ фрагментации определяется функцией фрагментации, вычисляющей для каждого кортежа отношения номер процессорного узла, на котором должен быть размещен этот кортеж. Запрос выполняется в виде нескольких параллельных процессов (агентов), каждый из которых обрабатывает отдельный фрагмент отношения. Полученные фрагменты сливаются в результирующее отношение. Обработка запросов в прототипе осуществляется следующим образом. Компилятор запросов проверяет синтаксис запроса и формирует его внутреннее представление. В качестве языка запросов в прототипе используется язык, основанный на реляционной алгебре. Внутренним представлением запроса является дерево, в котором листьями являются отношения, а узлами - реляционные операции (выборка, соединение и др.). В качестве сыновей узла выступают операнды реляционной операции, представляющей данный узел. Для унифицированного представления узлов дерева запроса используется скобочный шаблон, который может получать и посылать данные и выполнять какую-либо одну реляционную операцию. Генератор последовательных планов "вставляет" в скобочный шаблон каждого узла дерева запроса реализацию соответствующей реляционной операции. Параллелизатор запросов выполняет преобразование последовательного плана запроса в параллельный план, вставляя в соответствующие места дерева запроса специальный оператор обмена exchange. Оператор exchange имеет два специальных параметра, определяемых пользователем: номер порта обмена и указатель на функцию распределения. Функция распределения для каждого кортежа вычисляет логический номер процессорного узла, на котором данный кортеж должен быть обработан. Параметр "порт обмена" позволяет включать в дерево запроса произвольное количество операторов exchange (для каждого оператора указывается свой уникальный порт обмена). Менеджер параллельных агентов по параллельному плану запроса формирует параллельных агентов для узлов вычислительной системы. Исполнитель запросов интерпретирует (исполняет) параллельного агента на заданном процессорном узле вычислительной системы. Менеджер файлов реализует низкоуровневые операции с отношениями базы данных: сканировать отношение, выдать очередной кортеж отношения и др. Менеджер сообщений предоставляет функции для обмена сообщениями (кортежами) между процессорными узлами вычислительного системы. Обмен сообщениями реализован на основе стандарта Message Passing Interface (MPI). Исходные тексты и документация по прототипу доступны в Интернет по адресу http://omega.susu.ru. ЭЛЕКТРОННЫЙ УЧЕБНЫЙ КУРС "ПАРАЛЛЕЛЬНЫЕ СИСТЕМЫ БАЗ ДАННЫХ". В рамках проекта разработан электронный учебный курс "Параллельные системы баз данных" для студентов старших курсов и аспирантов, специализирующихся в области системного программирования. Курс включает в себя практикум, целью которого является разработка прототипа параллельной СУБД. Студенты обеспечиваются библиотекой функций прототипа, справочником по функциям библиотеки и набором контрольных тестов прототипа. С помощью готовых интерфейсов и библиотеки функций прототипа студентам необходимо выполнить реализацию модулей прототипа в порядке сверху-вниз в соответствии с модульной структурой прототипа. При проверке прототипа на контрольных тестах необходимо заменить библиотечные функции собственными реализациями. Разработанный электронный учебный курс был успешно апробирован на Зимней школе-практикуме молодых ученых и специалистов "Технологии параллельного программирования" (25 января-7 февраля 2004 г., Нижний Новгород). Материалы курса размещены в сети Интернет по адресу http://pdbs.susu.ru. ПУБЛИКАЦИИ ПО ПРОЕКТУ [1] Соколинский Л.Б. Обзор архитектур параллельных систем баз данных // Программирование. -2004. -№6. -C. 1-15. [2] Sokolinsky L.B. LFU-K: An Effective Buffer Management Replacement Algorithm // Database Systems for Advances Applications, 9th International Conference, DASFAA 2004, Jeju Island, Korea, March 17-19, 2004, Proceedings. Lecture Notes in Computer Science, Vol. 2973. -Springer. -2004. -P. 670-681. [3] Prischepa V.V. An Efficient Web Caching Algorithm Based on LFU-K Replacement Policy // Proceedings of the Spring Young Researcher's Colloquium on Database and Information Systems (St. Petersburg, May 27-28, 2004). -SPb.: NIIMM. -2004. -P. 46-49. [4] Костенецкий П.С. Моделирование и анализ иерархических архитектур параллельных систем баз данных // Международная научная конференция "Суперкомпьютерные системы и их применение" (SSA'2004): Доклады конференции (26-28 октября 2004 г., Минск). -Мн.: ОИПИ НАН Беларуси. -2004. -C. 116-120. [5] Лепихов А.В. Реализация функций стандарта MPI для эмуляции обменов сообщениями между узлами многопроцессорной вычислительной системы // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы четвертого международного научно-практического семинара и Всероссийской молодежной школы. -Самара: Изд-во Самарского научного центра РАН. -2004. -C. 179-180. [6] Цымблер М.Л., Соколинский Л.Б., Лепихов А.В. Прототипирование параллельной СУБД как основа учебного курса по параллельным системам баз данных // Международная научная конференция "Суперкомпьютерные системы и их применение" (SSA'2004): Доклады конференции (26-28 октября 2004 г., Минск). -Мн.: ОИПИ НАН Беларуси. -2004. -C. 212-217. [7] Sokolinsky L.B. Survey of Architectures of Parallel Database Systems // Programming and Computer Software. 2004. Vol. 30. No. 6. P. 337-346. |
| Адреса (полностью)
ресурсов в Internet, подготовленных авторами по данному проекту http://sok.susu.ru/grants/rfbr/2003/k_omega.html http://sok.susu.ru/OmegaProject/index.html http://cluster.susu.ru/index.html http://omega.susu.ru/simulatorMPI/index.html http://omega.susu.ru/index.html http://pdbs.susu.ru/index.html |