WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

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

ЛЫМАРЬ Татьяна Юрьевна

РАЗРАБОТКА МОДЕЛЕЙ

ПАРАЛЛЕЛЬНОГО ВЫПОЛНЕНИЯ ЗАПРОСОВ

В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ

С РАСПРЕДЕЛЕННОЙ ПАМЯТЬЮ

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

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

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

Челябинск-2002

Работа выполнена на кафедре математического обеспечения ЭВМ Челябинского государственного университета.

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

кандидат физико-математических наук, доцент СОКОЛИНСКИЙ Леонид Борисович

Официальные оппоненты:

доктор технических наук, профессор ГОЛЬДШТЕЙН Сергей Людвигович кандидат физико-математических наук, ст.н.с ПРОХОРОВ Владимир Валентинович

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

Научно-исследовательский вычислительный центр Московского государственного университета им. М.В. Ломоносова

Защита состоится 11 декабря 2002 г. в 10 часов на заседании диссертационного совета Д 212.296.02 по присуждению ученой степени доктора (кандидата) наук при Челябинском государственном университете по адресу 454021 г. Челябинск ул. Братьев Кашириных, 129.

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

Автореферат разослан 11 ноября 2002 г.

Ученый секретарь диссертационного совета, кандидат физико-математических наук Л.Б. Соколинский

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

Актуальность работы. В настоящее время системы управления базами данных (СУБД) используются практически во всех сферах человеческой деятельности, связанных с хранением и обработкой информации. Научная и практическая деятельность человека выдвигает все новые масштабные задачи, требующие обработки сверхбольших баз данных. Фактически единственным эффективным решением проблемы хранения и обработки сверхбольших баз данных является использование параллельных систем баз данных, обеспечивающих параллельную обработку запросов на многопроцессорных вычислительных системах.





В области параллельных систем баз данных существует ряд направлений, требующих дополнительных научных исследований. Одним из таких направлений является разработка методов организации параллельного выполнения запросов применительно к новым гибридным (иерархическим) архитектурам параллельных баз данных. Одним из наиболее известных классов гибридных архитектур, является архитектура CE (Clustered-Everything), в которой кластеры процессоров, использующих общие память и диски, объединяются в систему без совместного использования ресурсов. Однако, подобные конфигурации не обеспечивают высоких отказоустойчивости и доступности данных. В соответствии с этим, большой интерес представляют архитектуры класса CD (Clustered-Disk), в которой в систему без совместного использования ресурсов объединяются кластеры процессоров с распределенной памятью и общими дисками. Данные архитектуры способны обеспечить более высокие отказоустойчивость и доступность данных, демонстрируя производительность, сравнимую с CE–системами. Примером архитектуры такого класса может служить трехуровневая иерархическая CD2 архитектура, разработанная для параллельной системы баз данных Омега.

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

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

• исследование и анализ существующих моделей и методов организации параллельного выполнения запросов;

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

• разработка на базе предложенных моделей и методов исполнителя запросов СУБД Омега;

• проведение вычислительных экспериментов по исследованию эффективности разработанных моделей и методов.

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

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

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

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





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

склад, файл, временный файл, канал кондуктора, канал маршрутизатора;

• на основе предложенных концепций и методов спроектирован и реализован исполнитель запросов параллельной СУБД Омега для многопроцессорного вычислительного комплекса МВС, не имеющий в настоящее время отечественных аналогов.

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

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

Данная работа выполнялась при финансовой поддержке Российского фонда фундаментальных исследований (проекты 97-07-90148, 00-07-90077, 01-07-06039, 02-07Апробация работы. Результаты диссертационной работы неоднократно докладывались автором на международных и всероссийских научных конференциях, в том числе:

• на IV Международной Балтийской конференции IEEE по базам данных и информационным системам - BalticDB&IS'2000 (Вильнюс, Литва, 1-5 мая 2000 г.) при финансовой поддержке РФФИ (грант 00-07-93007);

• на 3-й Международной конференции по программированию и информационным технологиям CSIT'2001 (Уфа, 21-26 сентября 2001 г.);

• на Всероссийской научной конференции "Высокопроизводительные вычисления и их приложения" (Черноголовка, 30 октября - 2 ноября 2000 г.);

• на Международной конференции "Распределенные системы: оптимизация и приложения в экономике и науках об окружающей среде" - DSO'2000 (Екатеринбург, мая - 2 июня 2000 г.).

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

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения, списка литературы (116 наименований) и приложения.

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

В первой главе «Архитектура систем параллельной обработки транзакций»

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

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

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

1) автоматические диспетчеризация и синхронизация процессов выполнения реляционных операций в дереве запроса;

2) расширяемость путем добавления новых параллельных алгоритмов выполнения реляционных операций;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

С каждой нитью связывается числовая функция, выдающая значения в интервале (0;1) и называемая фактор-функцией. Значение, выдаваемое фактор-функцией в некоторый момент времени, будем называть Т-фактором нити в данный момент времени.

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

Т-фактор можно определить следующим образом. Определим i как меру заполнения склада нити Ti, 0i1 для всех i. Назовем данную меру Т-фактором нити Ti.

Значение i = 1 соответствует полному заполнению склада нити Ti. Значение i = 0 соответствует ситуации, когда склад нити Ti пуст.

Определим фактор-функцию fj(t) нити Tj как вещественную функцию, вычисляющую значение Т-фактора нити Tj в момент времени t.

Пусть нити Ti1, Ti2,..., Tik являются производителями данных для нити Ti. Нить Tj будем называть дизъюнктивной, если для ее работы достаточно, чтобы хотя бы один из складов подчиненных нитей Ti1, Ti2,..., Tik был не пуст. Нить Tj будем называть конъюнктивной, если для ее работы необходимо, чтобы все склады подчиненных нитей Ti1, Ti2,..., Tik были не пусты. Мы будем говорить, что дерево нитей некоторого процесса находится в нормальной форме, если все входящие в него нити являются либо дизъюнктивными, либо конъюнктивными. Из теоремы о нормальной дизъюнктивной форме исчисления высказываний непосредственно вытекает, что любое дерево нитей может быть приведено к нормальной форме путем эквивалентных преобразований.

Определим для нитей следующие три возможных состояния.

Нить Ti находится в состоянии простоя в момент времени t, если fi(t) = 1.

Дизъюнктивная нить Ti находится в заблокированном состоянии в момент времеk f ij (t ) = 0. Конъюнктивная нить Ti находится в заблокированном сони t, если стоянии в момент времени t, если Нить Ti готова к работе, если она не простаивает и не заблокирована.

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

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

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

Для определения формулы динамического приоритета введем следующие параметры.

Пусть с каждой нитью связан счетчик C. Данный счетчик увеличивается на единицу всякий раз, когда нить получает управление. Каждые m циклов диспетчеризации счетчики C всех нитей пересчитываются по формуле C := C*k, где k некоторое фиксированное значение, 0 k 1.

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

Здесь K и N некоторые нормализующие константы, которые наряду с m и k являются настраиваемыми параметрами менеджера нитей. Параметр threshold_nice задает положительное значение порога приятности для пользовательских нитей. Для системных нитей используется формула вычисления динамического приоритета, в которой этот параметр опущен.

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

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

Выполнение физического плана происходит следующим образом. Менеджер запросов запускает нить, соответствующую корневому операторному фрейму в дереве фреймов, представляющем данный физический план. Указатель на соответствующий операторный фрейм присваивается переменной cargo, ассоциированной с данной нитью (менеджер нитей для каждой нити поддерживает атрибут cargo типа void*). Это необходимо для того, чтобы в теле нити и в теле фактор-функции в процессе их выполнения можно было бы через данный атрибут получить доступ к значению любого атрибута (слота) соответствующего операторного фрейма. Сразу после своего запуска нить проверяет значение указателя на левого сына своего операторного фрейма. Если данный указатель не пуст, то запускается нить, соответствующая левому сыну, и переменной cargo, ассоциированной с этой нитью, присваивается указатель на левого сына.

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

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

склад.

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

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

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

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

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

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

1) обмены между операциями, выполняющимися на одном процессоре;

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

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

4) обмены между операциями и диском.

Соответственно обмен данными должен осуществляться посредством разных механизмов:

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

2) во втором варианте обменов передача данных осуществляется по каналам Омегакондуктора;

3) в третьем варианте обменов передача данных осуществляется с помощью функций Омега-маршрутизатора;

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

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

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

Потоки являются аргументами и результатами операций физической алгебры, то есть входными и выходными данными узлов дерева запроса. Логически поток представляет собой виртуальный файл типа FIFO. Его можно создавать (метод New), уничтожать (метод Delete), открывать (метод Open), закрывать (метод Close), устанавливать в начальное состояние (метод Reset). В поток можно помещать (записывать) записи (метод Write) и из потока можно извлекать (считывать) записи (метод Read) по правилу FIFO (первым записан, - первым считан).

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

«Склад», «Файл», «Временный файл», «Канал кондуктора» и «Канал маршрутизатора».

Для каждого из стандартных классов система предоставляет готовую реализацию методов New, Delete, Open, Close, Reset, Write и Read. Кроме этого, пользователь может определять дополнительные классы потоков, но в этом случае реализацию данных методов он должен указывать явно.

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

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

2) указатель на фактор-функцию нити;

3) указатель на выходной поток;

4) указатель на левого сына (может быть пустым);

5) указатель на правого сына (может быть пустым);

6) тип нити (конъюнктивная или дизъюнктивная).

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

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

-оператор является составным оператором и включает в себя четыре оператора:

gather, scatter, split и merge. Все указанные операторы реализуются на базе общего операторного фрейма.

Оператор split - это конъюнктивный бинарный оператор, который осуществляет разбиение гранул, поступающих из входного потока (ассоциируется с левым сыном), на две группы: свои и чужие. Свои гранулы - это гранулы, которые должны быть обработаны на данном процессорном узле. Эти гранулы помещаются в выходной поток (склад) оператора split. Чужие гранулы, то есть гранулы, которые должны быть обработаны на процессорных узлах, отличных от данного, помещаются оператором split в выходной поток (склад) правого сына, в качестве которого фигурирует оператор scatter. В данном случае выходной поток оператора split играет роль входного буфера (это достигается путем инвертирования фактор-функции, которая в данном случае будет выдавать значение один для пустого склада и значение ноль - для полностью заполненного склада).

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

Нульарный оператор gather выполняет перманентное чтение гранул данных из указанного порта со всех узлов кластера, отличных от данного. Считанные гранулы помещаются в выходной поток (склад) оператора gather. При переполнении склада процесс чтения гранул приостанавливается.

Оператор merge определяется как дизъюнктивный бинарный оператор, который забирает гранулы из выходных потоков (складов) своих сыновей и помещает их в собственный выходной поток (склад).

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

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

ставленные в виде левоориентрованных деревьев. Здесь join обознаjoin чает операцию соединения по некоторому общему атрибуту, store Q3 операцию записи результирующего отношения на диск. Мы испольjoin зовали деревья с максимальной глубиной (количеством операций бут a1 является атрибутом соединения для отношения Q1, атрибут a является атрибутом соединения для отношения Q2, атрибут a3 является атрибутом соединения для отношения Q3.

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

В реальных коммерческих приложениях баз данных часто встречается распределение, близкое к правилу "80-20". Данное правило гласит, что 80% обращений адресуется к 20% базы данных. Близким к данному распределению является распределение по закону Зипфа. В соответствие с этим законом вероятность встретить N значений атрибута определятся следующим образом:

где c = 1/HN, HN - гармоническое число.

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

Одним из параметров запроса, влияющим на эффективность выполнения запроса, является фактор селективности. Фактор селективности определяется как отношение:

Здесь size_of_the_join_result - размер результата соединения, size_of_the_source_relation - размер левого исходного (промежуточного) отношения в дереве запроса. Мы предполагали, что все операции соединения в дереве запроса имеют один и тот же фактор селективности.

Важным параметром базы данных является параметр VCF(R.ai), вычисляемый как отношение V/|R|, где |R| - размер отношения R, V - количество различных значений в столбце ai отношения R. В наших экспериментах мы предполагали, что все атрибуты отношения R имеют одинаковое значение параметра VCF.

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

Время выполнения (мс) 10 14 18 22 26 30 34 38 одинаковых значений нивелирует неравномерность распределения.

В последнем эксперименте мы исследовали производительность Омега-кластера в сравнении с производительностью SE кластера. Для этого мы выполнили на МВС эмуляцию 4-процессорного кластера с SE Относительная производительность 2 6 10 14 18 22 26 30 34 38 на всех процессорах кластера. На графике приведена относительная производительность Омега-кластера при выполнении мультисоединений различной глубины. Цифра 100% соответствует времени выполнения соответствующего мультисоединения на SE кластере с тем же количеством процессоров, что и у Омега-кластера. Результаты данного эксперимента показывают, что использование потоковой модели может значительно повысить производительность Омега-кластера. При длине склада, равной 32, производительность Омега-кластера при выполнении мультисоединений составляет около 80% от производительности SE кластера.

Проведенные эксперименты подтверждают эффективность предложенных моделей и подходов.

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

Исполнитель запросов системы Омега включает в себя следующие компоненты:

1. Класс Stock реализует абстрактный тип "Склад", необходимый для реализации потоковой модели. Экземпляры класса Stock имеют структуру очереди. В склад можно помещать элементы (widgets), представляющие собой байтовые строки фиксированной длины. Память для склада выделяется и освобождается динамически.

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

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

4. Модуль -оператора реализует ранее описанную модель параллелизации, предложенную для исполнителя запросов системы Омега.

5. Класс Tree реализует абстрактный тип "Дерево запроса" и предоставляет методы создания и обхода деревьев. Класс Tree не поддерживает дисциплину скобочной модели. В Tree-деревьях не предопределяются потоковые связи между узлами.

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

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

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

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

В заключении перечислены основные результаты работы.

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

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

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

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

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

Основные результаты диссертации опубликованы в следующих работах:

1. Lymar T.Y. Implementation of Relational Operations in Omega Parallel Database System // Proc. of the 3rd Int. Workshop on Computer Science and Information Technologies, Ufa, Russia, September 21-26, 2001. -Ufa State Aviation Technical University. 2001.

Vol. 2. P. 50-56.

2. Lymar T.Y., Sokolinsky L.B. Data Streams Organization in Query Executor for Parallel DBMS // Databases&Information System. Proceedings of the 4th IEEE International Baltic Workshop, Lithuania, Vilnius, May 1-5, 2000. -Vilnius: Technica. 2000. Vol. 1.

P. 85-88.

3. Лымарь Т.Ю., Соколинский Л.Б. Инкапсуляция параллелизма в исполнителе запросов СУБД Омега // Высокопроизводительные вычисления и их приложения: Труды Всероссийск. науч. конф.(30 октября - 2 ноября 2000 г., г. Черноголовка). -М.: Издво МГУ. 2000. C. 136- 4. Лымарь Т.Ю., Соколинский Л.Б. Управление потоками данных в параллельном исполнителе запросов СУБД Омега для МВС // Распределенные системы: оптимизация и приложения в экономике и науках об окружающей среде (DSO'2000). Сб.

докл. к Междунар. конф. (Екатеринбург, 30 мая - 2 июня 2000 г.). -Екатеринбург:

УрО РАН. 2000. C. 326-328.

5. Лымарь Т.Ю., Соколинский Л.Б. Организация параллельного исполнителя запросов на базе многопроцессорного вычислительного комплекса МВС // Вестник Челябинского университета. Сер. 3. Математика, механика, информатика. 2002. No.1(6).

C. 177-188.

6. Лымарь Т.Ю. Уточнение стоимостной модели оптимизации запросов с учетом распределения процессоров // Алгоритмический анализ некорректных задач: Тез. докл.

Всерос. науч. конф. (Екатеринбург, 2-6 февраля 1998 г.). -Екатеринбург: УрГУ.

1998. C. 149- 7. Соколинский Л.Б., Лымарь Т.Ю. О выборе оптимального плана выполнения запроса в параллельной системе баз данных // Проблемы оптимизации и экономические приложения: Тезисы докладов международной конференции. -Омск: Омск. гос.

ун-т. 1997. C. 146.

Формат 60x84 1/16. Бумага офсетная.

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

Тираж 100 экз. Заказ №. Бесплатно.

Челябинский государственный университет.

454021 Челябинск, ул. Братьев Кашириных, Полиграфический участок Издательского центра ЧелГУ.

454021 Челябинск, ул. Молодогвардейцев, 57б

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

«Ягодка Евгений Алексеевич ПОДДЕРЖКА ПРИНЯТИЯ УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ О СООТВЕТСТВИИ ОБЪЕКТА ЗАЩИТЫ ОБЯЗАТЕЛЬНЫМ ТРЕБОВАНИЯМ ПОЖАРНОЙ БЕЗОПАСНОСТИ Специальность: 05.13.10 – Управление в социальных и экономических системах (технические наук и) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Москва 2014 2 Работа выполнена в НИО организации надзорной деятельности (ОНД) учебно-научного комплекса (УНК) ОНД ФГБОУ ВПО Академия Государственной...»

«Телипенко Елена Викторовна СИСТЕМА ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ ПРИ УПРАВЛЕНИИ РИСКОМ БАНКРОТСТВА ПРЕДПРИЯТИЯ Специальность 05.13.10 – Управление в социальных и экономических системах (технические наук и) Автореферат диссертации на соискание учёной степени кандидата технических наук Новосибирск – 2013 Работа выполнена в Юргинском технологическом институте (филиале) федерального государственного бюджетного образовательного учреждения высшего профессионального образования...»

«Жегуло Ольга Анатольевна ИССЛЕДОВАНИЕ И РЕАЛИЗАЦИЯ НЕПРОЦЕДУРНЫХ ПРЕОБРАЗОВАНИЙ ПРОГРАММ ДЛЯ ПОСТРОЕНИЯ РАСШИРЯЕМОЙ СИСТЕМЫ РАСПАРАЛЛЕЛИВАНИЯ 05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук Ростов-на-Дону – 2007 3 Работа выполнена на кафедре информатики и вычислительного эксперимента факультета математики, механики и компьютерных наук Южного...»

«Авдюшенко Александр Юрьевич НОВЫЕ ЧИСЛЕННЫЕ МОДЕЛИ ГИДРОДИНАМИКИ ТУРБОМАШИН 05.13.18 — Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Новосибирск — 2014 Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте вычислительных технологий Сибирского отделения Российской академии наук, г. Новосибирск. Научный руководитель : доктор...»

«Вагин Денис Владимирович РАЗРАБОТКА МЕТОДОВ КОНЕЧНОЭЛЕМЕНТНОГО МОДЕЛИРОВАНИЯ ТРЕХМЕРНЫХ ЭЛЕКТРОМАГНИТНЫХ ПОЛЕЙ НА НЕСТРУКТУРИРОВАННЫХ СЕТКАХ 05.13.18 – Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Новосибирск – 2012 Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Новосибирский государственный...»

«Елистратов Николай Александрович РЕШЕНИЕ ОБРАТНОЙ ПРОБЛЕМЫ N-МЕРНЫХ АФФИННЫХ САМОПОДОБНЫХ ФУНКЦИЙ МЕТОДОМ ГОЛОСОВАНИЯ ДЛЯ ВСПЛЕСК-МАКСИМУМОВ Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва - 2011 г. Работа выполнена в ФГБОУ ВПО Московском государственном технологическом университете СТАНКИН. Научный руководитель : доктор...»

«НОВОСЕЛЬЦЕВ Виталий Борисович ФОРМАЛЬНАЯ ТЕОРИЯ СТРУКТУРНЫХ МОДЕЛЕЙ ОПИСАНИЯ ИНФОРМАЦИОННЫХ СИСТЕМ И МЕТОДЫ УСТАНОВЛЕНИЯ ВЫВОДИМОСТИ Специальность 05.13.01 – Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации) АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук Томск – 2006 Работа выполнена на кафедре оптимизации систем управления Томского политехнического университета...»

«ТРОЯНОВСКИЙ Владимир Михайлович АНАЛИЗ И ПАРАМ ЕТРИЧЕСКИЙ СИНТЕЗ СТОХАСТИЧЕСКИХ СИСТЕМ УПРАВЛЕНИЯ Специальность: 05.13.01 – Системный анализ, управление и обработка информации (вычислительная техника и информатика) Автореферат диссертации, представленной на соиск ание ученой степени доктора технических наук Москва, 2008 Работа выполнена в Московском государственном институте электронной техник и (техническом университете) на кафедре Информатика и программное обеспечение...»

«Митрофанова Елена Юрьевна НЕЙРОСЕТЕВЫЕ СЖИМАЮЩИЕ ПРЕОБРАЗОВАНИЯ ДАННЫХ И АЛГОРИТМЫ СОЗДАНИЯ ЦИФРОВЫХ ВОДЯНЫХ ЗНАКОВ В ОБЪЕКТАХ МУЛЬТИМЕДИА ГРАФИЧЕСКИХ И ЗВУКОВЫХ ФОРМАТОВ Специальность 05.13.17 – Теоретические основы информатики АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Воронеж – 2014 2 Работа выполнена в ФГБОУ ВПО Воронежский государственный университет Научный руководитель : доктор технических наук, профессор Сирота Александр Анатольевич...»

«Коршиков Сергей Борисович МЕТОД РЕЗУЛЬТАТИВНОГО ИСКАЖЕНИЯ ГЕОМЕТРИЧЕСКИХ ДАННЫХ ДЛЯ ОБЕСПЕЧЕНИЯ БЕЗОПАСНОСТИ ЭЛЕКТРОННЫХ МОДЕЛЕЙ МАШИНОСТРОИТЕЛЬНЫХ ИЗДЕЛИЙ Специальность 05.13.01 Системный анализ, управление и обработка информации (Авиационная и ракетно-космическая техника) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Москва – 2008 год 2 Работа выполнена на кафедре Прикладная информатика Аэрокосмического факультета Московского авиационного...»

«ЛЫКОВ Иван Александрович Режимы с обострением процессов переноса в атмосфере: особенности математического и численного моделирования методами нелинейной динамики Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Екатеринбург 2013 Работа выполнена на кафедре общей и молекулярной физики и в секторе нелинейной динамики НИИ Физики и прикладной...»

«Матвеев Юрий Николаевич ОСНОВЫ ПОСТРОЕНИЯ АВТОМАТИЗИРОВАННЫХ СИСТЕМ ОПЕРАТИВНОГО УПРАВЛЕНИЯ ТЕХНИЧЕСКОЙ БЕЗОПАСНОСТЬЮ ХИМИЧЕСКИХ ПРОИЗВОДСТВ Специальность 05.13.06 — Автоматизация и управление технологическими процессами и производствами (в промышленности) АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук Тверь – 2011 Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Тверской...»

«Сонис Роман Григорьевич Совершенствование элементов системы управления электронным документооборотом на основе методов функциональной стандартизации и технологии открытых систем Специальность: 05.13.05—Элементы и устройства вычислительной техники и систем управления, 05.13.15— Вычислительные машины и системы. АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Москва 2006 Работа выполнена в ГОУ ВПО Московский государственный институт радиотехники,...»

«НЬЯНГ Будал МОДЕЛИ ЗАЩИТЫ ОТ ПЕРЕГРУЗОК В УЗЛАХ УПРАВЛЕНИЯ УСЛУГАМИ CAMEL 05.13.13 – Телекоммуникационные системы и компьютерные сети АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Санкт-Петербург 2009 Работа выполнена в Санкт-Петербургском государственном университете телекоммуникаций им. проф. М.А. Бонч-Бруевича на кафедре Систем коммутации и распределения информации и в Научнотехническом центре Протей. Научный руководитель : доктор...»

«ЧЕКИНА Александра Валерьевна ГЕНЕТИЧЕСКАЯ КЛАСТЕРИЗАЦИЯ ТЕХНИЧЕСКОЙ ДОКУМЕНТАЦИИ В ПРОЕКТНЫХ РЕПОЗИТОРИЯХ САПР 05.13.12 – Системы автоматизации проектирования (промышленность) Автореферат диссертации на соискание ученой степени кандидата технических наук Ульяновск – 2012 Работа выполнена на кафедре Информационные системы в Ульяновском государственном техническом университете. Научный руководитель : доктор технических наук, профессор Ярушкина Надежда Глебовна Официальные...»

«Галкин Владимир Викторович СЕРВИСНО-ОРИЕНТИРОВАННАЯ СИСТЕМА ИНФОРМАЦИОННОГО МЕНЕДЖМЕНТА КАК ИНСТРУМЕНТ ПОДДЕРЖКИ ПРИНЯТИЯ УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ 05.13.10 – Управление в социальных и экономических системах (экономические наук и) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата экономических наук Ростов-на-Дону-2008 Диссертация выполнена в ГОУ ВПО Ростовский государственный университет путей сообщения на кафедре Экономика и финансы Научный руководитель – доктор...»

«Вавилов Вячеслав Анатольевич ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ СЕТЕЙ МНОЖЕСТВЕННОГО ДОСТУПА, ФУНКЦИОНИРУЮЩИХ В СЛУЧАЙНОЙ СРЕДЕ 05.13.18 – Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Томск – 2006 Работа выполнена на кафедре теории вероятностей и математической статистики факультета прикладной математики и кибернетики Томского государственного университета Научный...»

«ГЕНРИХОВ ИГОРЬ ЕВГЕНЬЕВИЧ ПОСТРОЕНИЕ И ИССЛЕДОВАНИЕ ПОЛНЫХ РЕШАЮЩИХ ДЕРЕВЬЕВ ДЛЯ ЗАДАЧ КЛАССИФИКАЦИИ ПО ПРЕЦЕДЕНТАМ 05.13.17 – теоретические основы информатики Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2013 Работа выполнена на кафедре теоретической информатики и дискретной математики математического факультета в Федеральном государственном бюджетном образовательном Учреждении Высшего профессионального образования...»

«Репнев Дмитрий Николаевич АДАПТАЦИЯ СЕТКИ КОНЕЧНЫХ ЭЛЕМЕНТОВ В ЗАДАЧАХ АНАЛИЗА ТЕПЛОВЫХ РЕЖИМОВ ИЗДЕЛИЙ РАДИОЭЛЕКТРОНИКИ СРЕДСТВАМИ САПР Специальность 05.13.12 – Системы автоматизации проектирования (в электронике, радиотехнике и связи) Автореферат диссертации на соискание ученой степени кандидата технических наук Москва – 2010 Работа выполнена на кафедре конструирования и технологии РЭС Московского авиационного института (государственного технического университета). Научный...»

«ФОКИН Василий Александрович МОДЕЛЬ СОГЛАСОВАНИЯ БИОМЕДИЦИНСКИХ ДАННЫХ И КОМПЛЕКС ПРОГРАММ ДЛЯ ИНТЕГРАЛЬНОЙ ОЦЕНКИ СОСТОЯНИЯ БИОСИСТЕМ 05.13.18 – математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук Томск – 2009 Работа выполнена на кафедре медицинской и биологической кибернетики ГОУ ВПО Сибирский государственный медицинский университет. Научные консультанты: доктор...»






 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

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