WWW.DISS.SELUK.RU

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

 

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

Поляков Артём Юрьевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ СРЕДСТВ

ОТКАЗОУСТОЙЧИВОСТИ РАСПРЕДЕЛЁННЫХ

ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Специальность 05.13.15 – Вычислительные машины,

комплексы и компьютерные сети

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

кандидата технических наук

Новосибирск – 2010

Работа выполнена на Кафедре вычислительных систем Государственного образовательного учреждения высшего профессионального образования государственный университет телекоммуникаций и “Сибирский информатики” Федерального агентства связи Министерства связи и массовых коммуникаций РФ.

Научный руководитель – доктор технических наук профессор Член-корреспондент РАН Заслуженный деятель науки РФ Хорошевский Виктор Гаврилович

Официальные оппоненты: доктор технических наук профессор лауреат государственной премии СССР Рычков Александр Дмитриевич доктор технических наук Шидловский Станислав Викторович

Ведущая организация – Научно-исследовательский институт многопроцессорных вычислительных систем им. А. В. Каляева Южного федерального университета

Защита состоится “23” декабря 2010 г. в 14 час. 00 мин. на заседании Диссертационного совета Д 219.005.02 при ГОУ ВПО “СибГУТИ”, по адресу:

630102, г. Новосибирск, ул. Кирова, д. 86, ком. 625.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО “СибГУТИ”.

Автореферат разослан “” 2010 г.

Ученый секретарь Диссертационного совета Д 219.005. кандидат технических наук доцент И. И. Резван

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Это определяет потребность в средствах высокопроизводительной обработки информации. Одним из инструментов решения сложных задач являются распределённые вычислительные системы (ВС), характеризующиеся массовым параллелизмом. Они формируются из унифицированных элементов (модулей), которые функционально и конструктивно закончены и имеют средства сопряжения друг с другом. В качестве базовых модулей ВС служат элементарная машина (ЭМ), оснащённая устройством управления, арифметико-логическим устройством (АЛУ), памятью и локальным коммутатором (ЛК), и узел вводавывода (УВВ), обеспечивающий доступ к данным. Конструктивно одна или несколько ЭМ размещаются на вычислительном узле (ВУ). Современные ВС являются распределёнными и большемасштабными, количество ЭМ в них варьируется от десятков до сотен тысяч, а число УВВ от нескольких десятков до сотен. Например, система IBM Roadrunner состоит из 122 400 ЭМ и 216 УВВ, а система Cray XT5 Jaguar – из 224 162 ЭМ и 256 УВВ.

Согласно статистическим данным среднее время (–1) безотказной работы вычислительных узлов распределённых ВС лежит в промежутке 104 – 106 ч. ( – интенсивность потока отказов для одного ВУ). Но даже при использовании таких высоконадёжных компонентов в большемасштабных ВС время между частичными отказами в среднем составляет несколько дней. Это ставит под вопрос осуществимость решения трудоёмких задач, представленных параллельными программами с количеством ветвей, сопоставимым с числом элементарных машин в ВС.

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

Исследования в области распределённых вычислительных систем ведутся с 1960-х годов. Проблемам их создания и эксплуатации посвящён ряд фундаментальных работ. Разработаны основы теории функционирования ВС, синтеза оптимальных (макро)структур, теории надёжности и живучести ВС.

Созданы инструментальные средства программного обеспечения, изучен широкий круг задач, которые могут эффективно решаться на распределённых ВС. Построены отечественные распределенные ВС с программируемой структурой: “Минск-222”, МИНИМАКС, СУММА, МИКРОС, МВС и т. д.

Фундаментальный вклад в теорию и практику вычислительных систем, компьютерных сетей и параллельных вычислительных технологий внесли выдающиеся советские и российские учёные, среди которых: Е.П. Балашов, В.Б. Бетелин, В.С. Бурцев, В.В. Васильев, В.М. Глушков, В.Ф. Евдокимов, Э.В. Евреинов, А.В. Забродин, В.П. Иванников, М.Б. Игнатьев, А.В. Каляев, И.А. Каляев, Л.Н. Королев, В.Г. Лазарев, С.А. Лебедев, В.К. Левин, Г.И. Марчук, В.А. Мельников, Ю.И. Митропольский, Д.А. Поспелов, И.В. Прангишвили, Д.В. Пузанков, Г.Е. Пухов, Г.Г. Рябов, А.А. Самарский, В.Б. Смолов, А.Н. Томилин, Я.А. Хетагуров, В.Г. Хорошевский, Б.Н. Четверушкин, Ю.И. Шокин, Н.Н. Яненко, а также зарубежные учёные:

K.M. Chandy, G. Cooperman, S. Cray, J. Dongarra, M. Flynn, I. Foster, A. Gara, L. Lamport, M. Livny, J.S. Plank и другие.

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

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

В соответствии с целью определены нижеследующие задачи:

1. Анализ архитектурных особенностей современных ВС и подходов к обеспечению их отказоустойчивого функционирования.

2. Организация отказоустойчивых гетерогенных каналов связи между территориально удалёнными компонентами пространственнораспределённых ВС.

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

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

5. Реализация алгоритмов формирования отказоустойчивых гетерогенных каналов передачи данных в виде программного модуля ОС GNU/Linux.

6. Интеграция предложенных алгоритмов возобновления параллельных программ в существующие средства формирования распределённых КТ.

7. Создание системного программного инструментария, позволяющего выполнять сжатие КТ и формирование результирующих КТ в соответствии с техническими ограничениями (на объём используемой памяти); его интеграция с существующими средствами создания КТ (ССКТ).

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

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

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

2. Построена математическая модель ВС с отказоустойчивым выполнением параллельных программ. Модель предусматривает: 1) сохранение промежуточных состояний программ в контрольных точках, позволяющих возобновить программу в случае отказа; 2) сжатие КТ в процессе их создания.

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

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

5. Предложен параллельный алгоритм дельта-сжатия контрольных точек восстановления параллельных программ, разработанных с использованием стандарта OpenMP.

6. Разработан адаптивный подход, осуществляющий (суб)оптимальный выбор КТ, относительно которой будет выполняться дельта-сжатие. Целями являются: 1) минимизация объёма сжатой КТ; 2) уменьшение количество сжатых КТ, необходимых для формирования результирующей КТ.

7. Создан алгоритм пакетного сжатия, совмещающий универсальное и дельта-сжатие, который обеспечивает (суб)оптимальное время формирования результирующей КТ.

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

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

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

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

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

Реализация и внедрение результатов работы. Основные результаты диссертационной работы внедрены. Они, в частности, составляют основу программного инструментария поддержки отказоустойчивости пространственнораспределённой мультикластерной вычислительной системы Центра параллельных вычислительных технологий ГОУ ВПО “Сибирский государственный университет телекоммуникаций и информатики” (ЦПВТ ГОУ ВПО “СибГУТИ”) и Лаборатории вычислительных систем Института физики полупроводников им. А. В. Ржанова СО РАН (ИФП СО РАН). Вычислительная система активно используется в учебном процессе ГОУ ВПО “СибГУТИ”.

Диссертационные исследования выполнялись по программе ведущей научной школы (НШ-2121.2008.9, НШ-5176.2010.9), проекту 32.1.1 “Архитектура, проблемы функционирования и моделирование большемасштабных распределённых вычислительных систем” Программы IV.32.1 базовых исследований 09-07-00095 Российского фонда фундаментальных исследований.

Алгоритм распределения информационных блоков по разнородным каналам связи был реализован в виде режима драйвера объединения каналов OC GNU/Linux (Linux Channel Bonding). Модифицированный драйвер внедрен в программное обеспечение платформы Sigrand SG-17R отечественного производителя телекоммуникационного оборудования ООО “Сигранд” и применяется на действующих каналах связи в России и странах СНГ.

Алгоритм восстановления идентификационной информации процессов параллельной программы реализован в виде модуля свободно распространяемого пакета создания распределённых контрольных точек DMTCP (Distributed MultiThreaded CheckPointing), начиная с версии 1.1.9.

Предложенные алгоритмы дельта-сжатия КТ легли в основу программного инструментария HBICT (Hash-Based Incremental Checkpointing Tool), который позволяет: 1) производить оценку и выбор наиболее эффективного режима сжатия для конкретных параллельных программ и конфигураций ВС; 2) в сочетании с существующими средствами создания КТ выполнять автоматическое сжатие формируемых КТ (выполнена интеграция HBICT с пакетом DMTCP);

3) обеспечить (суб)оптимальное время формирования результирующей КТ из набора сжатых.

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

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

– Международных научно-технических конференциях “Многопроцессорные вычислительные и управляющие системы” (с. Дивноморское Геленджикского района, 2007, 2009 гг.).

– Международных научных студенческих конференциях “Студент и научно-технический прогресс” (г. Новосибирск, 2007, 2008, 2009, 2010 гг.).

– Всероссийских научно-технических конференциях “Информатика и проблемы телекоммуникаций” (г. Новосибирск, 2007, 2008, 2009, 2010 гг.).

– Всероссийских конференциях с международным участием “Новые информационные технологии в исследовании сложных структур” (г. Томск, 2008, 2010 гг.).

– Международной научной студенческой конференции “Научный потенциал студенчества – будущему России” (г. Ставрополь, 2008 г.).

– Международной научной конференции “Параллельные вычислительные технологии (ПаВТ’2010)” (г. Уфа, 2010 г.).

– Международной научно-технической конференции “Суперкомпьютерные технологии” (с. Дивноморское Геленджикского района, 2010 г.).

Публикации. По теме диссертации опубликовано 23 работы, включая статьи в рецензируемых журналах. Результаты исследований отражены в отчётах по грантам и НИР.

Основные положения диссертации, выносимые на защиту.

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

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

3. Алгоритм восстановления идентификационной информации процессов параллельной программы, который использует только стандартный интерфейс при взаимодействии с ОС.

4. Алгоритмы определения и сохранения модифицированных фрагментов контрольных точек восстановления (алгоритмы дельта-сжатия).

5. Программный инструментарий дельта-сжатия, реализующий предложенные алгоритмы.

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе вводится понятие распределенной вычислительной системы, описываются её архитектурные свойства и характеристики. Рассматриваются особенности вычислительных систем с программируемой структурой, кластерных, мультикластерных и GRID-систем.

Распределённые ВС – это вычислительные средства с MIMD архитектурой, которые представляют собой композицию элементарных машин и узлов ввода-вывода. Они являются основным инструментом решения трудоёмких задач.

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

Важным свойством ВС, в отличие от ЭВМ, является возможность частичного отказа, который нарушает нормальную работу лишь некоторого числа её компонентов. Основой методик обеспечения отказоустойчивости распределённых ВС является введение избыточности: аппаратурной или (и) программной.

Аппаратурная избыточность позволяет повысить отказоустойчивость за счёт одновременного использования нескольких компонентов для реализации одного и того же процесса (например, технологии RAID, Channel Bonding). Программная избыточность позволяет организовать отказоустойчивое выполнение параллельных программ. Наиболее распространёнными примерами данного подхода являются программы, обладающие свойством адаптируемости или возобновляемости. Свойство адаптируемости определяет способность программы подстраиваться под число исправных ЭМ. Свойство возобновляемости предполагает возможность сохранять промежуточное состояние параллельной программы, которое в дальнейшем может быть использовано для её перезапуска (возобновления). В диссертационной работе рассмотрены подходы, основанные как на аппаратурной, так и на программной избыточности.

Во второй главе предложены: 1) математическая модель отказоустойчивого гетерогенного канала передачи данных и алгоритм распределения информационных блоков по разнородным каналам связи; 2) математическая модель ВС с отказоустойчивым выполнением параллельных программ, компоненты алгоритмов возобновления параллельных программ из КТ, а также подходы к оптимизации времени создания и объёма распределённых КТ.

Модель отказоустойчивого гетерогенного канала передачи данных. При объединении пространственно удаленных компонентов ВС часто возможно одновременное использование нескольких разнородных телекоммуникационных каналов (радиоканал, выделенная линия, оптоволоконный кабель и т. д.) как единого логического канала связи.

Рассмотрим модель гетерогенного канала передачи данных. Пусть имеется множество C={1, 2,…, N} каналов связи (рис. 1), для каждого канала iC определена его пропускная способность bi. На вход гетерогенного канала подается набор информационных блоков D={1, 2,…,K}, для каждого блока kD определен его размер – sk.

Рис. 1. Схема гетерогенного канала передачи данных Алгоритм распределения блоков определяет сюръективное отображение f : D C, которое каждому информационному блоку ставит в соответствие один из исправных физических каналов. Алгоритм объединения осуществляет слияние информационных блоков в порядке их поступления: l1, l2, …, lK из каналов C.

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

где K – количество передаваемых информационных блоков.

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

Алгоритм распределения информационных блоков. Для решения описанной выше задачи автором предложен [1, 2, 16] эвристический алгоритм RateBalance распределения информационных блоков. Для каждого канала iC вводится параметр ti, хранящий значение времени окончания передачи данных, находящихся в очереди отправки канала. Далее определяется время доставки информационного блока размером s по каналу i в момент времени t' с учётом текущей загрузки: (s, i, t') = (t', ti) + s/bi, где В алгоритме RateBalance номер канала для информационного блока размером s выбирается по формуле i = arg min (s, j, t'), далее происходит корректировка соответствующего параметра ti по формуле ti = (t', ti) + s/bi.

Вычислительная сложность RateBalance при обработке одного информационного блока линейна – O(N). Моделирование предложенного алгоритма показало, что по сравнению с существующими аналогами он позволяет обеспечить пропорциональную загрузку разнородных каналов связи и приблизить совокупную пропускную способность к её верхней оценке.

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

Рассмотрим распределённую ВС, состоящую из множества ЭМ C={1, 2, …, N}, которые распределены по М вычислительным узлам E={1, 2, …, M}. Пусть также дан вектор = (1, 2, …, N), где i E содержит номер ВУ, на котором расположена ЭМ с номером i.

Параллельная программа P представляет собой совокупность процессов P=(1, 2, …, n'), при этом элементы {1, 2, …, n} реализуют ветви параллельного алгоритма, а {n + 1, n + 2,…, n' } составляют набор служебных процессов. Для выполнения P, реализующей параллельный алгоритм из n ветвей, выделяется подсистема из n ЭМ. Каждой ветви из P взаимно однозначно ставится в соответствие одна ЭМ из выделенной подсистемы, служебные процессы отображаются на множество вычислительных узлов. Таким образом, существует отображение всех процессов P на множество E: = (1, 2,…, n'), i E, где i определяет номер ВУ, на котором выполняется процесс i.

Пусть в рассматриваемой ВС реализовано отказоустойчивое выполнение параллельных программ. Тогда в процессе работы P происходит периодическое создание контрольных точек (КТ) восстановления, в которых сохраняется её промежуточное состояние. Обозначим через Kt распределённую КТ, которая была создана в некоторый момент времени t и состоит из набора локальных КТ, однозначно соответствующих процессам из P: Kt = (Kt1, Kt2,…, Ktn'). Каждая КТ Kti может быть представлена в виде пары Lti, Dti, где Lti – локальный компонент, включающий регионы памяти, идентификационную информацию процесса в ОС, информацию о потоках и открытых файлах и т.д.;

Dti = Gti, Tti – распределённый компонент, где Gti – фрагмент графа информационных связей (например, набор рёбер, инцидентных i), Tti – содержимое транзитных сообщений, передававшихся через Gti в момент t создания КТ Kt.

Пусть в момент времени t' выполняется возобновление программы P'={1, 2, …, n'} из КТ K' = Kt на исправной подсистеме ВУ, определяемой вектором '. Состояние P' в момент времени t' должно быть эквивалентно состоянию P в момент времени t, а именно: 1) любые процессы i, i' P, выполнявшиеся на одном ВУ (i = i'), восстанавливаются также на одном ВУ ('i = 'i');

3) идентификационная информация на вычислительных узлах эквивалентна;

4) состояние внешних связей процессов (сокетов, файлов и т. п.) идентично.

Идентификационная информация процессов ОС. В рамках ОС с каждым процессом ассоциирован набор идентификаторов – d, p, s, g, f, где:

d – идентификатор процесса, уникальный в рамках ВУ; p – уникальный идентификатор процесса-родителя; s – уникальный идентификатор сеанса, к которому принадлежит процесс; g – идентификатор группы; f – номер группы первого плана в рамках сеанса s. Описанная информация сохраняется в локальных компонентах КТ.

Отношение родитель-потомок определяет древовидную организацию процессов в ОС, при этом корнем является процесс с именем init и d = 1. Процессы могут объединяться в группы и сеансы, в рамках которых доступны определённые виды межпроцессных взаимодействий. Членство в группе первого плана даёт возможность осуществлять чтение с терминального устройства, ассоциированного с сеансом процесса.

Обеспечение эквивалентности идентификационной информации процессов параллельной программы. Пусть выполняется первое условие эквивалентности состояний программ. Номера процессов программы P, выполнявшихся на ВУ j, определим через ( j) = {i | i = j, iP}. Тогда процессы P'i, i будут выполняться на узле j* ( i 'i = j* ). Под эквивалентностью идентификационной информации будем понимать изоморфность иерархической организации процессов на узлах j и j* ( i, i' di = pi' d'i = p'i' ), а также выполнение i, i' условий сохранения:

1) принадлежности к одному сеансу (si = si' s'i = s'i');

2) лидерства в сеансе ( di = si d'i = s'i );

3) принадлежности к одной группе ( gi = gi' g'i = g'i' );

4) лидерства в группе ( di = gi d'i = g'i );

5) принадлежности к группе первого плана (f1 = f2 f'1 = f'2).

На данный момент известны решения указанной задачи только с использованием прямого доступа к внутренним структурам ядра ОС.

В диссертационной работе предложен [5, 8, 10, 11] алгоритм User Space Credential Restore (USCR), использующий для взаимодействия с ОС только интерфейс системных вызовов. Это позволяет применять его в средствах создания КТ, не имеющих прямого доступа к ядру ОС.

Задача оптимизации объёма КТ. Рассмотрим набор КТ (K1i, K2i,…, Kti), соответствующих состоянию i-го процесса в моменты времени 1, 2, …, t.

Введём функцию S(X), которая определяет размер объекта X в байтах. Пусть также определена функция сжатия КТ, созданной в момент времени t', относительно ряда предыдущих: (K1i, K2i,…, K(t'-1),i, Kt'i), которая формирует сжатую КТ Zt'i: S(Zt'i) S(Kt'i). При этом существует обратная функция - –1(K1i, Z2i,…, Z(t'-1),i, Zt'i) = Kt'i. Для оптимизации объёма дискового пространства, используемого для хранения распределённых КТ, и снижения накладных расходов, создаваемых при формировании КТ, необходимо минимизировать объём сжатой КТ.

Наиболее распространёнными вариантами сжатия КТ являются: 1) универсальные алгоритмы сжатия, для которых Zt'i = (Tt'i); 2) сжатие с помощью дельт (дельта-сжатие), которое предусматривает формирование инкрементных (Zt'i = (T(t'-1),i, Tt'i)) или дифференциальных (Zit' = (T1i, Tt'i)) контрольных точек (при одинаковой функции ).

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

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

Достаточно распространёнными являются алгоритмы дельта-сжатия, способные обнаруживать только модификации фрагментов. Существуют также подходы, рассчитанные на все указанные виды изменений. Например, алгоритмы, использующие принцип скользящего окна (A. Tridgell, 1999).

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

1. Разработанный алгоритм P-FHash [4, 9, 12] основан на методике крупноблочного распараллеливания. Он позволяет задействовать все доступные ядра узлов ВС для сжатия КТ параллельных программ, созданных с использованием стандарта OpenMP. Моделирование алгоритма P-FHash показало, что он имеет масштабируемость, близкую к линейной.

подход [13 – 15], совмещающий преимущества дифференциального и дифференциальные КТ. Пусть производится создание КТ Kti в момент времени t для процесса i P, текущая базовая КТ – Kt'i. В соответствии с алгоритмом P-FHash определяется количество модификаций относительно базовой КТ – Z1 = (Tt'i, Tti) и относительно предыдущей КТ Z2 = (T(t-1)i, Tti). Если ( S(Z1) – S(Z2) ) / S(Tti) B, где B – параметр алгоритма, определяющий некоторое граничное значение, то принимается решение о сохранении инкрементной КТ, которая становится базовой (t' = t) для последующих КТ. Моделирование предложенного подхода показало, что он позволяет существенно снизить объём и время создания КТ. На рис. 2 показаны объёмы несжатых и дельтасжатых КТ, полученных для прикладной программы моделирования газодинамических процессов в подушке безопасности автомобиля (Airbag).

Рис. 2. Объём S КТ, созданных для программы Airbag; n – номер КТ 3. Предложена модификация P-FHash [13, 15], совмещающая стандартные алгоритмы сжатия и дельта-сжатие. Для ускорения процесса формирования результирующей КТ используется частичное сжатие, которое предусматривает группировку изменённых блоков в пакеты, каждый из которых сжимается независимо от других. Моделирование показало, что данный подход позволяет примерно в два раза снизить накладные расходы при формировании КТ.

4. Предложен параллельный алгоритм формирования результирующей распределённой КТ в условиях возможного нарушения целостности сжатых КТ [15]. Данный алгоритм способен корректно обрабатывать ситуации, когда некоторые блоки одной или нескольких КТ были повреждены, и формировать максимально позднее целостное состояние из набора исправных блоков. В результате работы алгоритма результирующие локальные КТ ветвей параллельной программы располагаются в оперативной памяти вычислительных узлов и готовы к передаче ССКТ.

В третьей главе описана архитектура пространственно-распределённой мультикластерной вычислительной системы ЦПВТ ГОУ ВПО “СибГУТИ” и Лаборатории ВС ИФП СО РАН (рис. 3) и средства обеспечения отказоустойчивости ВС.

Рис. 3. Конфигурация пространственно-распределенной Система объединяет 9 пространственно-распределённых кластерных ВС.

Кластеры A – G расположены в ЦПВТ ГОУ ВПО “СибГУТИ”, а кластеры H, I – в Лаборатории ВС ИФП СО РАН. Каждый из кластеров A – I может рассматриваться как отдельная ВС, так и как компонент мультикластерной ВС. Системы A, B, C и H являются кластерами рабочих станций и персональных компьютеров. В состав кластера D (Xeon16) входит 4 вычислительных узла, построенных на двухъядерных процессорах Intel Xeon 5150 (Woodcrest). Кластер Е (Xeon32) состоит из четырёх вычислительных узлов, оснащённых двумя четырёхядерными процессорами Intel Quad Xeon E5345. Кластер F (Xeon80) укомплектован 10 вычислительными узлами, на каждом из которых расположено два четырёхядерных процессора Intel Quad Xeon E5420. Кластер G (Unicluster) укомплектован четырьмя вычислительными узлами, оснащёнными двумя четырёхядерными процессорами Intel Xeon E5410. Кластер I (Opteron10) состоит из 6 двухпроцессорных узлов, каждый из которых представляет собой систему NUMA на базе процессоров AMD Opteron 248.

Коммуникационные среды вычислительных кластеров построены на базе технологий Gigabit и Fast Ethernet, а для их объединения используется сеть Internet (технология VPN). Связь осуществляется через выделенные серверы сегментов ЦПВТ ГОУ ВПО “СибГУТИ” и Лаборатории ВС ИФП СО РАН. В целом система включает более 250 процессорных ядер и имеет пиковую производительность несколько TeraFLOPS. Мультикластерная ВС допускает масштабирование путём организации взаимодействия с множеством других систем.

Для организации отказоустойчивых каналов передачи данных выполнена реализация предложенного алгоритма RateBalance в виде дополнительного режима драйвера объединения каналов Linux Channel Bonding. Произведено его внедрение в состав программного обеспечения мультикластерной ВС и в оборудование отечественного производителя телекоммуникационных устройств Sigrand (http://www.sigrand.ru).

Для организации отказоустойчивого выполнения параллельных программ на мультикластерной ВС установлен свободно распространяемый пакет [6, 7] DMTCP (http://dmtcp.sourceforge.net/), представляющий собой универсальную систему создания КТ. В указанном пакете реализован предложенный алгоритм восстановления идентификационной информации процессов параллельных программ, он входит в базовый состав DMTCP, начиная с версии 1.1.9.

Создан программный инструментарий Hash Based Incremental Checkpointing Tool (HBICT, http://sourceforge.net/projects/hbict/), реализующий предложенные алгоритмы дельта-сжатия. Выполнена интеграция HBICT и пакета DMTCP. Созданные средства внедрены в мультикластерную ВС, проведено их моделирование.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

1.2. Разработан алгоритм RateBalance распределения информационных блоков по разнородным каналам связи. Алгоритм (в отличие от существующих аналогов) обеспечивает фиксированный уровень инверсий (нарушений порядка следования информационных блоков) в выходном потоке гетерогенного канала передачи данных, при котором не происходит переполнения окон приёма протоколов вышележащих уровней (например, TCP).

1.3. Осуществлено моделирование алгоритма RateBalance и показано, что он не чувствителен к различиям в пропускных способностях объединяемых каналов связи и обеспечивает стабильное приближение совокупной пропускной способности гетерогенного канала к её предельному значению.

1.4. Выполнено внедрение алгоритма RateBalance в программное обеспечение пространственно-распределённой мультикластерной ВС и телекоммуникационной платформы Sigrand SG-17R отечественного производителя ООО “Сигранд”.

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

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

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

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

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

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

3.1. Создан параллельный алгоритм дельта-сжатия P-FHash, который характеризуется линейным ускорением и предназначен для параллельных программ, использующих стандарт OpenMP.

3.2. Предложен адаптивный подход, сочетающий преимущества инкрементных и дифференциальных контрольных точек. Его использование позволяет снизить зависимость сжатых контрольных точек от предыдущих, что делает возможным сокращение объёмов хранимых данных (например, за счёт удаления устаревших точек – garbage collection). С другой стороны, подход обеспечивает низкие объёмы передаваемых данных, характерные для инкрементных контрольных точек.

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

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

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

4. Конфигурация пространственно-распределённой мультикластерной системы расширена средствами отказоустойчивости, которые обеспечивают:

1) формирование отказоустойчивых гетерогенных каналов связи;

2) восстановление параллельных программ из контрольных точек; 3) оптимизацию контрольных точек по времени создания и объёму.

Основные результаты диссертации опубликованы в работах [1–23].

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Поляков, А.Ю. Адаптивный подход к распределению информационных блоков по каналам передачи данных / А.Ю. Поляков // Электросвязь. – 2009. – №6. – С. 32-35. – ISSN 0013-5771.

2. Хорошевский, В.Г. Архитектура и программное обеспечение пространственнораспределённых вычислительных систем / В.Г. Хорошевский, М.Г. Курносов, С.Н. Мамойленко, А. Ю. Поляков // Вестник СибГУТИ. – Новосибирск: СибГУТИ, 2010. – №2. – С. 112-122.

3. Поляков, А.Ю. Оптимизация времени создания и объёма контрольных точек восстановления параллельных программ / А.Ю. Поляков, А.А. Данекина // Вестник СибГУТИ. – Новосибирск: СибГУТИ, 2010. – № 2. – C. 87-100.

4. Поляков, А.Ю. О восстановлении программ из контрольной точки / А.Ю. Поляков // Вестник ЮУрГУ. Серия “Математическое моделирование и программирование”. – 2010. – № 35(211), № 6. – С. 91-103.

5. Cooperman, G. DMTCP and Condor: a New Checkpointing Mechanism [Electronic resource] / G. Cooperman, K. Arya, P. Keller, A.Y. Polyakov // Condor Week 2010. – University of Wisconsin, 2010. – Режим доступа: http://www.cs.wisc.edu/ condor/CondorWeek2010/condor-presentations/cooperman-dmtcp.pdf.

6. Visan, A.M. Temporal Debugging using URDB [Electronic resource] / Ana Maria Visan, Artem Polyakov, Praveen S. Solanki, Kapil Arya, Tyler Denniston, Gene Cooperman // Technical Report.- Режим доступа: http://arxiv.org/abs/0910.5046v1.

7. Поляков, А.Ю. Организация объединенного канала передачи данных / А.Ю. Поляков // Инфосфера. – Новосибирск, 2009. – № 43. – C. 44-47.

8. Поляков, А.Ю. Об алгоритме восстановления структуры процессов из контрольной точки / А.Ю. Поляков // Материалы Международной научно-технической конференции “Многопроцессорные вычислительные и управляющие системы (МВУСТаганрог: ТТИ ЮФУ, 2009. – Т. 2. – C. 71-73. – ISBN 978-5-8327-0341-1.

9. Поляков, А.Ю. Параллельный алгоритм формирования инкрементных контрольных точек / А.Ю. Поляков // Материалы Международной научно-технической конференции “Суперкомпьютерные технологии: разработка, программирование, применение Таганрог: ТТИ ЮФУ, 2010. – Т.1. – С. 290 – 294. – ISBN 978-5-8327-0383-1.

10. Поляков, А.Ю. О восстановлении программ из контрольной точки / А.Ю. Поляков // Параллельные вычислительные технологии (ПаВТ’2010): Труды международной научной конференции (Уфа, 29 марта – 2 апреля 2010 г.) [Электронный ресурс]. – Челябинск: Издательский центр ЮУрГУ, 2010. – C. 299 - 310.

ISBN 978-5-696-03987-9. URL: http://omega.sp.susu.ac.ru/books/conference/PaVT2010/ full/155.pdf 11. Поляков, А.Ю. Об обеспечении отказоустойчивого решения параллельных задач // Материалы XLVII Международной научной студенческой конференции “Студент и научно-технический прогресс”. - Новосибирск: НГУ, 2009. – с. 211.

12. Данекина, А.А. О подходах к созданию инкрементных контрольных точек восстановления / А.А. Данекина, А.Ю. Поляков // Материалы XLVII Международной научной студенческой конференции “Студент и научно-технический прогресс”. – Новосибирск: НГУ, 2010. – с. 296.

13. Поляков, А.Ю. О подходах к оптимизации времени создания и объёма контрольных точек восстановления / А.Ю. Поляков, А.А. Данекина // Тезисы докладов Восьмой Российской конференции с международным участием “Новые информационные технологии в исследовании сложных структур (ICAM 2010)”. – Томск: НТЛ, 2010. – с. 23. – ISBN 9785-89503-440-8.

14. Молдованова, О.В. Исследование современных средств создания контрольных точек восстановления параллельных программ / О.В. Молдованова, А.Ю. Поляков // Тезисы докладов Восьмой Российской конференции с международным участием “Новые информационные технологии в исследовании сложных структур (ICAM 2010)”. – Томск: НТЛ, 2010. – с. 22. – ISBN 978-5-89503-440-8.

15. Данекина, А.А. Применение методов хеширования к задаче формирования инкрементных контрольных точек / А.А. Данекина, А.Ю. Поляков // Материалы Российской научно-технической конференции “Информатика и проблемы телекоммуникаций”. – 2010. – Т. 1. – с. 155.

16. Поляков, А.Ю. Организация объединенного канала передачи данных / А.Ю. Поляков // Материалы Российской научно-технической конференции “Информатика и проблемы телекоммуникаций”. – 2009. – Т. 1. – С. 131 – 132.

17. Поляков, А.Ю. Эвристические алгоритмы организации функционирования распределенной вычислительной системы с учетом экономических факторов / А.Ю. Поляков // Материалы II Международной научной студенческой конференции “Научный потенциал студенчества – будущему России”. – Ставрополь: СевКавГТУ, 2008. – Т. 3. – с. 180.

18. Поляков, А.Ю. Об алгоритмах организации функционирования вычислительных систем при обслуживании набора задач с учетом экономических факторов / А.Ю. Поляков // Материалы XLV Международной Научной Студенческой Конференции “Студент и научно-технический прогресс”. – Новосибирск: НГУ, 2007. – С. 45 - 46.

19. Поляков, А.Ю. Организация функционирования вычислительных систем при обслуживании наборов задач с учетом штрафа за задержку решения / А.Ю. Поляков // Российская научно-техническая конференция “Информатика и проблемы телекоммуникаций”. – Новосибирск: СибГУТИ, 2007. – С. 276 – 277.

20. Мамойленко, С.Н. Применение генетических алгоритмов для распределения наборов задач по машинам вычислительной системы / С.Н. Мамойленко, Н.А. Медведева, А.Ю. Поляков // Материалы Международной научно-технической конференции “Многопроцессорные вычислительные и управляющие системы”. – Таганрог: ТТИ ЮФУ, 2007. – Т. 2. – С. 70 – 75.

21. Поляков, А.Ю. Учет экономических факторов в задаче распределения ресурсов вычислительной системы / А.Ю. Поляков // Материалы XLVI Международной Научной Студенческой Конференции. – Новосибирск: НГУ, 2008. С. 78 – 79.

22. Мамойленко, С.Н. Применение эволюционных алгоритмов для распределения набора задач с нефиксированными параметрами по машинам распределенной вычислительной системы / С.Н. Мамойленко, Н.А. Медведева, А.Ю. Поляков, А.В. Ефимов // Тезисы докладов Седьмой Российской конференции с международным участием “Новые информационные технологии в исследовании сложных структур (ICAM-2008)”. – Томск: НТЛ, 2008. – с. 71.

23. Мамойленко, С.Н. Применение эволюционных алгоритмов для распределения набора задач с нефиксированными параметрами по машинам распределенной вычислительной системы / С.Н. Мамойленко, Н.А. Медведева, А.Ю. Поляков, А.В. Ефимов // Российская научно-техническая конференция “Информатика и проблемы телекоммуникаций”. – Новосибирск: СибГУТИ, 2008. – С. 144 – 145.

Разработка и исследование средств отказоустойчивости распределенных на соискание ученой степени кандидата технических наук Подписано в печать “19” ноября 2010 г.

Формат бумаги 60x84/16, отпечатано на ризографе, шрифт № 10, изд. л.1,6, заказ № 69, тираж 130 экз., ГОУ ВПО “СибГУТИ”.

630102, г. Новосибирск, ул. Кирова, д. 86.



 


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

«ГОДОВНИКОВ Евгений Александрович Автоматизированная система исследования алгоритмов идентификации и прогнозирования аварийных состояний в импульсных системах преобразования энергии. Специальность 05.13.06 – Автоматизация и управление технологическими процессами и производствами (промышленность) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Ханты-Мансийск – 2011 2 Работа выполнена в Федеральном государственном бюджетном образовательном...»

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

«Лизунов Александр Александрович Прецизионные преобразователи первичной информации инерциальных систем управления динамичными объектами специального назначения Специальность 05.13.05 – Элементы и устройства вычислительной техники и систем управления Автореферат диссертации на соискание ученой степени кандидата технических наук Москва 2011 г. Работа выполнена на кафедре Системы автоматического и интеллектуального управления Московского авиационного института (государственного...»

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

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

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

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

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

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

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

«Димитриченко Дмитрий Петрович Разработка и исследование методов интеллектуального поиска топологических структур с заданными свойствами 05.13.17 – Теоретические основы информатики Автореферат диссертации на соискание ученой степени кандидата технических наук Таганрог - 2013 Работа...»

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

«Лукьянцев Дмитрий Александрович Влияние самоподобности телекоммуникационного трафика на технические характеристики систем спутникового доступа к Интернет Специальность 05.13.13 – Телекоммуникационные системы и компьютерные сети АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Таганрог-2008 Работа выполнена на кафедре Радиоэлектронных средств защиты и сервиса Технологического института Южного федерального университета в г. Таганроге. Научный...»

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

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

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

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

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

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

«РАТУШНЯК Олег Александрович Методы сжатия данных без потерь с помощью сортировки параллельных блоков 05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей. АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Красноярск — 2002 Работа выполнена в Институте систем информатики им.А.П.Ершова Сибирского отделения Российской академии наук Научный руководитель : доктор физико-математических наук,...»








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

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