• Токарев Андрей Николаевич
  • 2005
  • 20

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

Стратегия размещения подзадач в распределенных вычислительных системах кластерно-метакомпьютерного типа - темы дипломов, курсовиков, рефератов и докладов Ознакомиться с текстом работы
Специальность ВАК РФ: 05.13.15 — Вычислительные машины и системы
  • Реферун рекомендует следующие темы дипломов:
  • Анализ архитектур систем распределенных вычислений, способов оптимизации их построения и оптимизации процесса вычислений
  • Обзор архитектур распределенных вычислительных систем
  • Классификация архитектур многопроцессорных вычислительных систем
  • Обзор вычислительных систем метакомпьютерного типа
  • Реферун советует написать курсовую работу на тему:
  • Простая задача назначения
  • Задачи компоновки, решаемые в теории автоматизации проектирования
  • Стратегия размещения узлов и подзадач в системе распределенных вычислений кластерно-метакомпыотерного типа
  • Размещение подзадач в идеально надежной системе
  • Реферун советует написать реферат на тему:
  • Размещение подзадач с использованием равномерного деления
  • Классификация стратегий размещения подзадач и обоснование выбора адаптивной стратегии размещения подзадач
  • Модуль сбора статистики для системы распределенных вычислений
  • Обзор пакетов оптимизации
  • Реферун предлагает написать доклад на тему:
  • Математическая модель планирования использования ресурсов
  • Блок структурной оптимизации
  • Показатели и критерии эффективности загрузки
  • Программный комплекс нечеткой балансировки нагрузки
  • Структура программы с описанием функций составных частей и связи между ними
  • Формат, описание и способ кодирования входных данных
  • Анализ эффективности работы системы
Поделиться с друзьями:

Выдержки из автореферата диссертации Токарев Андрей Николаевич, 2005, 05.13.15 — Вычислительные машины и системы

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

В настоящее время во всем мире идет активная работа по совершенствованию теоретических и практических основ функционирования кластерных и метакомпьютерных систем. Это отражено в работах В. Воеводина, Вл. Воеводина, В. Коваленко, А. Орлова, JI. Соко-линского, Д. Смирного в России, Г. Эндрюса, И. Фостера, Ф. Хофф-мана, Р. Вильямса за пределами нашей страны.

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

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

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

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

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

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

Поставленная цель достигается решением следующих задач:

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

2. Исследование скоростных и надежностных характеристик узлов и каналов связи распределенной вычислительной системы (РВС) и разработка стратегии размещения узлов в РВС с учетом этих характеристик.

3. Создание классификации стратегий размещения подзадач в РВС с обоснованиями применимостей каждой стратегии.

4. Разработка статической стратегии размещения подзадач в РВС с учетом скоростных и надежностных характеристик узлов и каналов связи.

5. Разработка динамической адаптивной стратегии размещения подзадач в системе для учета изменений состава системы в процессе решения задачи.

6. Создание программного обеспечения для реализации разработанной стратегии размещения подзадач в реальных РВС.

Объектом исследования диссертационной работы является распределенная вычислительная система кластерно-метакомпьютер-ного типа.

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

Методы исследования основаны на положениях теории графов, теории вероятности, теории надежности и теории марковских процессов.

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

В результате проведенных исследований достигнуто следующее:

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

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

3. Предложена расчетно-обменная характеристика задач, применение которой позволяет учесть соотношения объемов передаваемых на узлы данных и таким образом настроить РВС на определенный тип задач.

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

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

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

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

Реализация и внедрение результатов работы. Диссертация является теоретическим обобщением научно-исследовательских работ, выполненных автором в Пензенском государственном университете. Данная диссертационная работа проводилась по гранту для поддержки научно-исследовательской работы аспирантов высших учебных заведений Министерства образования России по теме «Высокопроизводительная вычислительная система повышенной надежности с динамическим распределением ресурсов», шифр АОЗ-3.16-349. Также результаты диссертации использовались для проведения работ по гранту Министерства образования России по теме «Теория и методы организации управления распределенными вычислительными процессами в многопроцессорных вычислительных системах и метакомпьютерных сетях», шифр Т02-03.3-2476. Результаты работы были использованы в рамках создания Регионального центра суперкомпьютерных вычислений и телекоммуникационных баз данных коллективного пользования. Результаты диссертационной работы применялись в рамках проведения расчетов характеристик моделей сигналов радиоволновых средств обнаружения в распределенной вычислительной системе для ФГУП «НИКИРЭТ».

Апробация работы. Основные результаты работы докладывались и обсуждались на международных и всероссийских научно-технических конференциях и . семинарах, в том числе на XII и XIII Международных школах-семинарах «Синтез и сложность управляющих систем» (Пенза, октябрь 2000 и 2001 гг.); XIII научно-технической конференции студентов и профессорско-преподавательского состава Пензенского государственного университета (Пенза, 2002 г.); V и VI Международных научно-технических конференциях «Новые информационные технологии и системы» (Пенза, 2002 и 2004 гг.); Международном юбилейном симпозиуме «Актуальные проблемы науки и образования» (Пенза, 2003 г.); V и VI Всероссийских научно-практических молодежных конференциях «Антикризисное управление в России в современных условиях» (Москва, МГТУ им. Н. Э. Баумана, 2004 г.); 5-й Международной конференции и 1-м Международном форуме молодых ученых «Актуальные проблемы современной науки» (Самара, СамГТУ, 2004 и 2005 гг.).

Работа автора по теме «Разработка оптимальной стратегии размещения узлов в распределенной вычислительной системе метаком-пькггерного типа» получила Диплом за лучшую научно-исследовательскую работу на 5-й Международной конференции молодых ученых «Актуальные проблемы современной науки» (г. Самара, 2004 г.).

Основные положения, выносимые на защиту:

1. Стратегия размещения узлов в РВС для поиска местоположения и количества серверных узлов системы.

2. Расчетно-обменные характеристики задачи, решаемой в РВС.

3. Классификация стратегий размещения подзадач в РВС.

4. Статическая стратегия размещения подзадач на основе данных о производительности и надежности узлов и каналов связи.

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

Публикации. По теме диссертации опубликовано 16 печатных работ, в том числе 7 статей и 9 тезисов докладов.

Структура и объем работы. Данная диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы, включающего 75 наименований, и приложений. Объем работы: 160 страниц основного машинописного текста, 44 рисунка, 11 таблиц, 2 страницы приложений.

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

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

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

3. Разработана универсальная расчетно-обменная характеристика задач, решаемых в РВС.

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

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

6. Разработано программное обеспечение (программы NS Logger, NS Analyzer, NS Manager) для снятия статистики, построения надежностных характеристик узлов и организации системы управления заданиями в РВСКМТ, реализующее стратегии размещения подзадач в системе любого типа из предложенной классификации.

7. Проведена проверка полученных теоретических результатов на реальной вычислительной системе «MathNet» как для расчетно-ориентированных задач (вычисление экстремумов функций и численное интегрирование), так и для обменно-ориентированных задач (умножение матриц), которая доказала эффективность предложенных решений.

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

1. Токарев А. Н. Построение и анализ кластерной вычислительной системы на базе ПЭВМ, объединенных сетью «Fast Ethernet» / А. Н. Токарев, А. В. Антонов // Синтез и сложность управляющих систем: Материалы XII Междунар. школы-семинара (г. Пенза, 15-21 октября 2001 г.). - М.: Изд-во МГУ, 2001. - Ч. 1.-С. 13-17.

2. Токарев А. Н. Принципы организации параллельной вычислительной системы с доступом через Интернет / А. Н. Токарев, А. В. Антонов // Синтез и сложность управляющих систем: Материалы XII Междунар. школы-семинара (г. Пенза, 14-20 октября 2002 г.); Под общ. ред. чл.-кор. РАН О. Б. Лупанова. - М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ, 2002. -Ч. 1.-С. 21-25.

3. Токарев А. Н. Структура распределенной вычислительной системы и организация удаленного доступа к ней / А. Н. Токарев, А. В. Антонов // Новые информационные технологии и системы: Тр. V Междунар. науч.-техн. конф. - Пенза: Изд-во Пенз. гос. ун-та, 2002.-С. 100-103.

4. Токарев А. Н. Высокопроизводительная вычислительная система повышенной надежности с динамическим распределением ресурсов / А. Н. Токарев, А. В. Антонов, А. В. Дубравин, Б. Д. Шашков // Актуальные проблемы науки и образования: Тр. Междунар. юбил. симп. - Пенза: Изд-во Пенз. гос. ун-та, 2003. - С. 385-387.

5. Токарев А. Н. Оптимизация функционирования распределенной вычислительной системы с использованием выбора стратегии размещения // Новые информационные технологии и системы: Тр. VI Междунар. науч.-техн. конф. - Пенза: Изд-во Пенз. гос. ун-та, 2004.-С. 92-100.

6. Токарев А. Н. Оптимизация алгоритмов при их реализации в системе распределенных вычислений / А. Н. Токарев, Н. П. Вашке-вич // Изв. высш. учеб. заведений. Поволж. регион. Технические науки. - 2004.-№ 2.

7. Токарев А. Н. Разработка оптимальной стратегии размещения узлов в распределенной вычислительной системе метакомпьютерно-

го типа // Актуальные проблемы современной науки: Тр. 5-й Между-нар. конф. молодых ученых и студ. - Самара, 2004. - С. 72-75.

8. Токарев А. Н. Универсальное распределение подзадач для ме-такомпьютера // Антикризисное управление в России в современных условиях: Материалы VI Всерос. науч.-практ. молодежной конф. -М.: Изд-во МГТУ им. Н. Э. Баумана, 2004. - С. 300-302.

9. Токарев А. Н. Программный комплекс «Система распределенных вычислений «MathNet» / А. Н. Токарев, А. В. Антонов, А. В. Дуб-равин, Б. Д. Шашков // Вычислительные системы и технологии обработки информации: Сб. науч. тр. - Пенза: Изд-во Пенз. гос. ун-та, 2005,-Вып. 3.- С. 90-100.

10. Токарев А. Н. Программный комплекс «Система распределенных вычислений «MathNet». Оптимизация производительности // Вычислительные системы и технологии обработки информации: Сб. науч. тр. - Пенза: Изд-во Пенз. гос. ун-та, 2005 - Вып. 3 - С. 111-121.

11. Токарев А. Н. Адаптивная стратегия размещения подзадач в распределённых вычислительных системах кластерно-метакомпью-терного типа // Актуальные проблемы современной науки: Тр. 1-го Междунар. форума. - Самара, 2005. - С. 110-113

12. Токарев А. Н. Оптимизация размещения подзадач в распределённых вычислительных системах с ненадёжными узлами // Актуальные проблемы современной науки: Тр. 1-го Междунар. форума.-Самара, 2005.-С. 113-116.

Токарев Андрей Николаевич

Стратегия размещения подзадач в распределенных вычислительных системах кластерно-метакомпьютерного типа

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

Редактор О. Ю. Ещина Технический редактор Я. А. Вьялкова

Корректор Я. А. Сидельникова Компьютерная верстка Я. В. Ивановой

ИД №06494 от 26.12.01

Поделиться с друзьями: