Стратегия размещения подзадач в распределенных вычислительных системах кластерно-метакомпьютерного типа тема диссертации и автореферата по ВАК РФ 05.13.15, кандидат технических наук Токарев, Андрей Николаевич
- Специальность ВАК РФ05.13.15
- Количество страниц 170
Оглавление диссертации кандидат технических наук Токарев, Андрей Николаевич
ВВЕДЕНИЕ.
Глава 1. Анализ архитектур систем распределенных вычислений, способов оптимизации их построения и оптимизации процесса вычислений.
1.1 Обзор архитектур распределенных вычислительных систем.
1.1.1 Классификация архитектур многопроцессорных вычислительных систем.
1.1.2 Обзор вычислительных систем метакомпьютерного типа.
1.2 Обзор методов компоновки и размещения.
1.2.1 Простая задача назначения.!.
1:2.2 Квадратичная задача назначения.
1.2.3 Задачи, решаемые с помощью линейного и динамического* программирования.
1.2.4 Задачи компоновки, решаемые в теории автоматизации проектирования.!.
1.215 Методы оптимизации размещения из теории графов.
1.3 Обзор средств управления заданиями в распределенных вычислительных системах.
1.4 Выводы по главе.1.
Глава 2. Стратегия размещения узлов и подзадач в системе распределенных вычислений кластерно-метакомпыотерного типа.
2.1 Стратегия размещения узлов в РВСКМТ.
2.2 Размещение подзадач в идеально надежной системе.
2.3 Размещение подзадач в системе с отказами.
2.4 Размещение подзадач с использованием равномерного деления.
2.5 Выводы по главе.
Глава 3. Система управления заданиями на основе адаптивной стратегии размещения подзадач.
• • з.
3.1 Классификация стратегий размещения подзадач и обоснование выбора адаптивной стратегии размещения подзадач.
3.1.1 Метод равномерного размещения в идеальных системах (системах без отказов узлов).
3.1.2 Метод равномерного размещения в реальных системах (системах с отказами узлов).
3.1.3 Метод неравномерного размещения в идеальных системах (системах без отказов узлов).
3.1.4 Метод неравномерного размещения в реальных системах (системах с отказами узлов).
3.1.5 Обоснование выбора адаптивной стратегии размещения подзадач
3.1.6 Метод адаптивного размещения подзадач с барьерной адаптацией.
3.1.7 Метод адаптивного размещения подзадач с непрерывной адаптацией .:.
3.2 Система управления заданиями на основе адаптивного метода размещения подзадач с непрерывной адаптацией.'.
3.2.1 Размещение на основе известных статистических данных о надежности узлов.
3.2.2 Размещение на основе динамически рассчитываемых данных о надежности узлов.!.
3.3 Выводы по главе.
Глава 4. Программный комплекс для управления распределенной вычислительной системой кластерно-метакомпьютерного типа.
4.1 Основные характеристики систем управления заданиями для кластерно-метакомпьютерных систем.
4.2 Модуль сбора статистики для системы распределенных вычислений.
4.2.1 Программа журналирования NS Logger.
А.22 Программа анализа статистики NS Analyzer.
4.3 Модуль планирования вычислений для распределенной вычислительной системы.
4.4 Результаты работы РВСКМТ для расчетно-ориентированных задач.
4.4.1 Равномерное разбиение в системе без отказов.
4.4.2 Статическая стратегия размещения подзадач в системе без отказов
4.4.3 Статическая стратегия размещения подзадач в системе с отказами.
4.5 Результаты работы РВСКМТ для обменно-ориентированных задач.
4.5.1 Равномерное разбиение в системе без отказов.
4.5.2 Статическая стратегия размещения подзадач в системе без отказов
4.5.3 Статическая стратегия размещения подзадач в системе с отказами.
4.6 Результаты применения адаптивной стратегии размещения подзадач в системе с отказами.'.!.
4.6.1 Размещение на основе известных статистических данных о надежности узлов.
4.6.2 Размещение на основе динамически рассчитываемых данных о ■> надежности узлов.'.'.
4.7 Выводы по главе.'.
Рекомендованный список диссертаций по специальности «Вычислительные машины и системы», 05.13.15 шифр ВАК
Разработка системы запуска ресурсоемких приложений в облачной гетерогенной среде2013 год, кандидат технических наук Е Мьинт Найнг
Адаптивные алгоритмы обработки информации в мультиагентных системах2002 год, кандидат технических наук Вересов, Игорь Германович
Распараллеливание программ для суперкомпьютеров с параллельной памятью и открытая распараллеливающая система2004 год, доктор технических наук Штейнберг, Борис Яковлевич
Разработка и анализ параллельных алгоритмов параметрического синтеза для массивно-параллельных суперкомпьютеров2004 год, кандидат технических наук Катуева, Ярослава Владимировна
Организация территориально-распределенных вычислений с использованием декомпозиционных моделей2008 год, кандидат технических наук Ильин, Павел Евгеньевич
Введение диссертации (часть автореферата) на тему «Стратегия размещения подзадач в распределенных вычислительных системах кластерно-метакомпьютерного типа»
В настоящее время фундаментальные и прикладные проблемы, эффективное решение которых возможно только с использованием высокопроизводительных вычислений, объединены понятием "Grand challenges", которое включает в себя, например, задачи предсказания климата и глобальных изменений в земной коре [1], задачи аэродинамики для самолетостроения и создания; реактивных двигателей [2], распознавание изображений при навигации движущихся объектов [3], и т.д.
При решении этих задач возникает потребность в значительно больших вычислительных ресурсах, чем может предоставить обычный компьютер. Таким задачам необходимо либо большее быстродействие, либо возможность обрабатывать и хранить большие объемы информации.
Большого быстродействия требуют сложные, многомерные задачи; которые необходимо решить в течение определенного, достаточно ограниченного времени. Один из наиболее характерных примеров - задачи прогноза погоды. Область решения (атмосфера) разбивается на отдельные пространственные; ячейки, причем для расчета временных изменений? вычисления в каждой ячейке повторяются много раз. Если объем ячейки равен
1 км3, то для моделирования слоя атмосферы высотой в 10 км потребуется 8 *
5x10 таких ячеек. Предположим, что вычисления в каждой ячейке потребуют 200 операции с плавающей точкой, тогда за один временной шаг потребуется выполнить 1011 операций с плавающей точкой. Для того, чтобы произвести расчет прогноза погоды с заблаговременностью 10 дней с 10-ти минутным шагом по времени, компьютеру производительностью 100 MFlops (ГО8 операций с плавающей точкой в секунду) потребуется 10 секунд или свыше 100 дней. Для того, чтобы произвести расчет за 10 мин, потребуется уже компьютер производительностью 1.7 TFlops (1.7 х 10 операций с плавающей точкой в секунду) [48].
Таким образом, поскольку для решения подобных задач существует спрос на вычислительные системы повышенной мощности, современный рынок предлагает суперкомпьютеры, отвечающие достаточно высоким требованиям. К ним относятся комплексы, собранные из специальных комплектующих, с использованием, как правило, векторных или матричных процессоров, позволяющих выполнять за 1 такт несколько операций;' а также специальные коммуникативные средства, дающие, в отличие от стандартных средств, гарантированную полосу пропускания для каждого подсоединенного к ним устройства. Такие специальные средства производят фирмы Cray research, IBM, Compaq, NEC и некоторые другие [5].
Логично сделать вывод, что основной задачей при создании суперкомпьютеров был девиз «производительность любой ценой». Специальные процессоры, дорогостоящая сверхбыстрая память, нестандартное периферийное оборудование - всё это приводит к увеличению стоимости таких систем в десятки и сотни раз.
Естественно, позволить себе купить суперкомпьютер может далеко не каждое предприятие,, которое занимается деятельностью, требующей ^ интенсивных расчетов.
Есть ли выход из этой ситуации?
Сейчас можно с уверенностью сказать: есть.
Из-за быстрого роста производительности персональных компьютеров и развития интрасетей, стало возможным создание высокопроизводительной вычислительной системы при помощи объединения ' в сеть существующих персональных компьютеров. Получаемая при этом вычислительная система -кластер - обладает многими преимуществами, главными из которых являются дешевизна, доступность, возможность постепенного расширения и модернизации.
Однако, при создании кластерной системы нужно сделать выбор: либо система обеспечивает повышенную надежность вычислений, любо дает увеличение производительности. Эти термины обычно исключают друг друга, т.е. повышение надежности всегда сопровождается увеличением кода программы, большими требованиями к памяти, вследствие дублирования информации или хранения параметров для проверки корректнрсти данных, дополнительными проверками и т.п. Все это, естественно, снижает быстродействие системы. Наоборот, если считать оборудование абсолютно надежным, то можно не учитывать возможность его отказа и работать без дополнительных проверок, кодирования и дублирования информации. Таким образом, некую абстрактную кластерную систему можно настроить либо на большее быстродействие, либо на большую надежность.
Многие существующие системы распределенных вычислений изначально настроены либо на одно, либо на другое.
Так, узким местом Beowulf-кластеров (В èowulf - технология организации параллельных вычислений на Linùx-кластерах) [53,54] является головная машина-сервер. На ней хранится информация о структуре кластера и с нее осуществляется запуск параллельных программ, поэтому кластер не сможет работать в случае ее отказа.
Популярная' в настоящее время технология параллельного; программирования MPI (Message Passing Interface - Интерфейс передачи-сообщений) позволяет организовать распределенные вычисления в многомашинном комплексе на основе передачи сообщений. Данная технология: (в частности ее свободно-распространяемая версия MPICH (MPI CHameleon)) настроена на оптимальное быстродействие - в ней нет низкоуровневых средств слежения за отказами узлов, и неполадки с одним из них приводят к краху системы в целом и необходимости начинать вычисления с начала [49,50].*
Кроме того, в вышеупомянутых системах практически не имеется средств смены конфигурации кластера во время вычислительного процесса, и они слабо ориентированы на гетерогенную сеть, ' состоящую из множества вычислительных узлов самых разных конфигураций - от персонального компьютера с процессором i486 до многопроцессорной стойки с процессорами Alpha. При написании MPI-программ для таких систем приходится прибегать к разного рода ухищрениям, учитывая разброс скоростных и архитектурных характеристик вычислительных узлов.
Этих "недостатков не имеют системы другого класса - метакомпьютеры [51,52]. Это распределенные вычислительные системы, в которых нет постоянного соединения между вычислительными узлами, и которые могут динамически менять свою конфигурацию. Обычно в таких системах вычислительному узлу передаются данные для расчета, и он «отключается» от системы и решает свою задачу. После того, как данные готовы, он подключается к головной машине, возвращает результат и берет следующую порцию данных.
Налицо преимущества такой системы: возможность оптимального размещения задачи по вычислительным узлам разной архитектуры и различной мощности, возможность динамического подключения и отключения произвольного количества вычислительных узлов.
Недостаток метакомпьютерной системы - ориентированность на задачи; переборного и поискового типа, где вычислительные узлы не взаимодействуют друг с другом.
В настоящее время во всем мире идет активная работа по> совершенствованию теоретических и практических основ функционирования кластерных и метакомпьютерных систем, созданию оптимальных методов размещения задач в распределенной вычислительной системе и механизмов планирования вычислений и оптимизации вычислительного процесса. Это отражено в работах В.Воеводина, Вл. Воеводина [4,33,55], В.Коваленко [34,42], А. Орлова, Л. Соколинского, Д. Смирного [44] в России, Г. Эндрюса [57], И. Фостера [51,52]; Ф. Хоффмана, Р. Вильямса [38,39] за пределами нашей страны.
Разработано множество средств планирования вычислительного процесса и управления заданиями в распределенных вычислительных системах, но ни одно из них, естественно, не является универсальным. Кроме того, основная масса исследований проводится в области глобальных метакомпьютерных систем с гигантским множеством пользователей и огромным количеством вычислительных узлов. При этом упор делается на эффективное обслуживание потока заданий от множества , пользователей. И очень мало разработано методик анализа вычислительного процесса в кластерно-метакомпьютерных системах, которые не являются столь глобальными, как метакомпьютеры и столь простыми, как кластеры, и соответственно, требуют к себе особого подхода.
Например, в работах В.Коваленко, А. Орлова, Е. Хухлаева [34,42] (Институт прикладной математики имени М.В.Келдыша РАН, г. Москва) для управления заданиями в распределенной вычислительной среде предлагается идея метадиспетчера (или грид-диспетчера), который планирует размещение заданий в группах вычислительных узлов метакомпьютера в соответствии с требованиями каждого задания к ресурсам и с имеющимися ресурсами в узлах, при этом используется распределенная база данных, имеющая информацию о ресурсах. При этом, так как предполагается, что метадиспетчер имеет дело с большим количеством разнородных заданий, приходящих с разных направлений, большее внимание уделено определению очередности запуска и предсказанию моментов старта заданий в узлах, когда выполнение будет наиболее эффективно.
Такой подход не совсем обоснован для кластерно-метакомпьютерных' систем, в которых множественный гетерогенный поток заявок как таковой отсутствует из-за централизованной структуры управления системой, но присутствует задача, которую необходимо распределить между вычислительными узлами таким образом, чтобы обеспечить минимальное время расчета. При этом должна учитываться разная производительность узлов и каналов связи между узлами и сервером (т.е. гетерогенность системы).
В работах Д. Смирного [44] (Институт математики и механики УрО РАН, г.Екатеринбург) предлагается решение задачи эффективного распределения процессов в многомашинном вычислительном комплексе путем решения оптимизационной задачи методом ветвей и границ. При этом учитываются пропускные способности каналов связи. Полученное улучшение за счет перераспределения процессов достигает 12%. Однако, недостатком такого подхода является необходимость иметь историю вычислений программы для каждого из процессов. Кроме того, в этих исследованиях не учитываются характеристики надежности узлов и каналов связи.
В работах Н.П. Вашкевича, Б.Д. Шашкова и А.В. Антонова [58]
Пензенский государственный университет, г.Пенза) рассматриваются способы повышения эффективности параллельных и распределенных вычислений за счет переработки алгоритма параллельной программы с использованием моделей недетерминированных цифровых автоматов и теории марковских процессов. При этом рассматривается возможность анализа различных вариантов реализации алгоритма задачи по трудоемкости и выбора наиболее эффективного из них. Также предложен способ организации вычислительной системы, позволяющий осуществлять динамическую балансировку загрузки отдельных ее узлов за счет разделения программы на заведомо большое число? ветвей и асинхронного запуска параллельных процессов. • • | , .
Однако, данный подход не учитывает пропускные способности каналов связи, что может снизить эффективность предложенных методов. Кроме того?,-не учитываются надёжностные характеристики элементов системы.
Целью данной диссертационной работы является разработка и совершенствование методов и алгоритмов повышения эффективности распределенных вычислений в' системах кластерно-метакомпьютерного типа.
Поставленная цель достигается решением следующих задач:
1. Анализ вариантов организации и особенностей кластерных и метакомпьютерных вычислительных систем, исследование существующих методов оптимизации размещения элементов.
2. Исследование скоростных и надежностных характеристик узлов и каналов связи распределенной вычислительной системы (РВС) и' разработка стратегии размещения узлов в РВС с учетом этих характеристик.
3. Создание классификации стратегий размещения подзадач в РВС с обоснованиями применимостей каждой стратегии.
4. Разработка статической стратегии размещения подзадач в РВС с учетом скоростных и надежностных характеристик узлов и каналов связи.
5. Разработка динамической адаптивной стратегии размещения подзадач в системе для учета изменений состава системы в процессе решения задачи.
6. Создание программного обеспечения для реализации разработанной стратегии размещения подзадач в реальных РВС.
Объектом исследования диссертационной работы является распределенная вычислительная система кластерно-метакомпьютерного типа.
Предметом исследования является структурная организация РВС, стратегии размещения узлов и подзадач для планирования и' управления вычислительным процессом в РВС.
Методы исследования основаны на положениях теории графов, теории вероятности, теории надежности и теории марковских процессов.
Научная новизна состоит в развитии научных основ и теоретическом анализе способов и методов организации и функционирования распределенных вычислительных систем.
В результате проведенных исследований достигнуто следующее:
1. Разработана стратегия размещения узлов РВС, реализуемая^на основе поиска потокового центра графа и позволяющая повысить эффективность РВС за счет учета характеристик производительности и надежности узлов, входящих в систему.
2; Предложена классификация стратегий размещения подзадач в РВС, которая позволяет выделить основные параметры, достоинства и недостатки каждой стратегии и области ее применимости.
31 Предложена расчетно-обменная характеристика задач, применение которой позволяет учесть соотношения объемов передаваемых на узлы данных и таким образом настроить РВС на определенный тип задач.
4. Разработана статическая стратегия размещения подзадач в РВС, отличающаяся тем, что она учитывает характеристики производительности и надежности узлов и каналов связи. . 12
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 г).
Публикации. По теме диссертации опубликовано 16 печатных работ, в том числе 7 статей и 9 тезисов докладов.
Структура и объем работы. Данная диссертационная работа состоит из четырех глав, заключения и приложения.
В первой главе проводится обзор существующих классификаций вычислительных систем, в частности распределенных вычислительных систем. Анализируются варианты построения высокопроизводительных систем с параллельной обработкой данных, производится анализ особенностей кластерно-метакомпьютерных систем. Анализируются методы компоновки и размещения, потенциально применимые для решения задачи эффективного размещения узлов распределенной вычислительной системы в имеющейся сети. Проводится анализ исследований эффективности планирования вычислений в распределенных системах. На основании проведенного анализа формулируются задачи дальнейшего исследования.
Во второй главе предлагаются модели, основанные на теории графов, теории вероятности и теории надежности, позволяющие повысить эффективность систем распределенных вычислений как на этапе проектирования структуры системы, так и на этапе деления задачи на параллельные подзадачи. Предлагаются возможные способы организации статического распределения подзадач для вычислительных узлов системы.
Третья глава посвящена разработке классификации стратегий и методов размещения подзадач в вычислительных узлах системы распределенных вычислений, исходя из которой осуществляется выбор того или иного метода для систем с определенными параметрами. На основе результатов, полученных в главе 2, и с учетом выработанной классификации разрабатывается динамическая адаптивная стратегия размещения узлов, учитывающая изменение структуры вычислительной системы во время процесса вычисления задачи. Для этого используются положения теории надежности и теории марковских процессов.
Четвертая глава посвящена разработке программного обеспечения для реализации предложенных во второй и третьей главах стратегий размещения подзадач, а также проверке полученных теоретических результатов на практике. В ней предложено описание разработанного программного комплекса системы управления заданиями, который позволяет осуществлять получение и накопление статистических характеристик узлов системы распределенных вычислений, рассчитывать характеристики надежности узлов, осуществлять разбиение задачи на подзадачи в соответствии с полученными характеристиками и на основе выработанных в главах 2 и 3 стратегий размещения подзадач. Приводятся результаты замеров временных характеристик работы системы.
Основные положения, выносимые на защиту:
1. Стратегия размещения узлов в РВС для поиска местоположения и количества серверных узлов системы.
2. Расчетно-обменные характеристики задачи, решаемой в РВС.
3. Классификация стратегий размещения подзадач в РВС.
4. Статическая стратегия размещения подзадач на основе данных о производительности и надежности узлов и каналов связи.
5. Динамическая адаптивная стратегия размещения подзадач на основе имеющихся заранее или рассчитываемых динамически данных о надежности узлов.
Похожие диссертационные работы по специальности «Вычислительные машины и системы», 05.13.15 шифр ВАК
Оценка производительности распределенных вычислительных комплексов на основе модели эталонных систем2010 год, кандидат физико-математических наук Хританков, Антон Сергеевич
Исследование и организация эффективных вычислений в параллельных системах баз данных на основе сетей ЭВМ2001 год, кандидат технических наук Маликов, Андрей Валерьевич
Применение мелкозернистого локально-параллельного программирования при решении задач математической физики методом сеток2008 год, кандидат технических наук Заручевская, Галина Васильевна
Инструментальный комплекс для разработки и применения гетерогенных распределенных вычислительных сред2009 год, кандидат технических наук Корсуков, Александр Сергеевич
Моделирование адаптивных систем управления манипуляционных роботов на параллельных вычислительных структурах2000 год, кандидат технических наук Иншаков, Дмитрий Юрьевич
Заключение диссертации по теме «Вычислительные машины и системы», Токарев, Андрей Николаевич
4.7 Выводы по главе
В результате проведенной работы, описанной в данной главе, был разработан и реализован полный пакет программного обеспечения для организации планирования распределенных вычислений, реализующий предложенные в главах 2 и 3 стратегии размещения подзадач в РВСКМТ, были реализованы несколько алгоритмов как расчетной, так и обменной направленности, и был проведен ряд тестов на реальной вычислительной системе «МаИтеЬ>, который позволил провести оценку и сравнение предложенных стратегий размещения подзадач.
Основные полученные результаты:
1. Разработано программное обеспечение (программы NS Logger и NS Analyzer) для снятия статистики и построения надежностных характеристик узлов распределенной вычислительной системы, которые в дальнейшем используются стратегиями размещения подзадач в системах с отказами.
2. Разработано программное обеспечение (программа NS Manager) для организации системы управления заданиями в распределенных вычислительных системах кластерно-метакомпьютерного типа, реализующее стратегии размещения подзадач в системе любого типа из предложенной классификации.
3. Проведена проверка полученных теоретических результатов на реальной вычислительной системе «Mathnet» как для расчетно-ориентированных задач (вычисление экстремумов функций и численное интегрирование), так для обменно-ориентированных задач (умножение матриц), которая показала повышение эффективности расчетов при применении предложенных решений в среднем на величину 20%.
4. Проведен анализ сравнение полученных результатов тестов, который позволил сделать выводы о применимости того или иного метода размещения подзадач для определенных видов задач.
ЗАКЛЮЧЕНИЕ
В диссертационной работе были разработаны научные основы и проведен теоретический анализ систем распределенных вычислений и протекающих в них процессов с целью рассмотрения возможных способов повышения их эффективности за счет оптимального размещения узлов вычислительной системы в реальной сети, применения стратегий размещения подзадач в узлах вычислительной системы, имеющих определенные характеристики производительности и надежности.
В результате проведенных исследований достигнуто следующее:
1. Разработана стратегия размещения узлов распределенной вычислительной системы, которая позволяет повысить общую эффективность вычислений за счет учета характеристик производительности и надежности узлов, входящих в систему.
2. Разработана классификация стратегий размещения подзадач в распределенных вычислительных системах, которая позволяет выделить, основные параметры, достоинства и недостатки каждой стратегии и составляющих ее методов, а также области их применимости, что в конечном итоге позволит выбрать правильный метод размещения для определенных решаемых задач.
3. Разработана универсальная расчетно-обменная характеристика задач, решаемых в системе распределенных вычислений.
4. Разработана статическая стратегия размещения подзадач в системе распределенных вычислений, которая учитывает характеристики производительности и надежности узлов и каналов связи.
5. Разработана динамическая адаптивная стратегия размещения подзадач в системе распределенных вычислений, которая учитывают изменения характеристик системы и перераспределяет объемы выдаваемых узлам подзадач во время вычислительного процесса.
6. Разработано программное обеспечение (программы NS Logger и NS Analyzer) для снятия статистики и построения надежностных характеристик узлов распределенной вычислительной системы, которые в дальнейшем используются стратегиями размещения подзадач в системах с отказами.
7. Разработано программное обеспечение (программа NS Manager) для организации системы управления заданиями в распределенных вычислительных системах кластерно-метакомпьютерного типа, реализующее стратегии размещения подзадач в системе любого типа из предложенной классификации.
8. Проведена проверка полученных теоретических результатов на реальной вычислительной системе «Mathnet» как для расчетно-ориентированных задач (вычисление экстремумов функций и численное интегрирование), так для обменно-ориентированных задач (умножение матриц), которая доказала эффективность предложенных решений.
Список литературы диссертационного исследования кандидат технических наук Токарев, Андрей Николаевич, 2005 год
1. Желиговский В.А., Пинский В.И., Розенберг B.J1. Параллельная реализация блоковых моделей динамики литосферы // Распределенные системы: оптимизация и приложения в экономике и науках об окружающей среде. Екатеринбург. УрО РАН. - 2000. - С. 315-318.
2. Гусев А. В., Луцкий А. Е., Петрушенков И. JI. Приложение многопроцессорных систем в аэродинамическом проектированиисамолетов // Вопросы атомной науки и техники. Серия "Математическоемоделирование физических процессов". 1992. - Вып. 3. - С. 11-14.
3. Костоусов В.Б. Реализация алгоритмов высокоточной навигации по геофизическим полям на параллельных вычислительных системах // Алгоритмы и программные средства параллельных вычислений. Сб. науч. тр. Екатеринбург. УрО РАН. 1995. - С. 86-100.
4. В.В. Воеводин, Вл.В. Воеводин Параллельные вычисления. СПб.: БХВ-Петербург, 2002, 608 с.
5. Архитектуры и топологии многопроцессорных вычислительных систем. Электронный учебник под ред. А. Богданова и др., (http://www.informika.ru). 2003.
6. Thakkar S. S., Sweiger М. Performance of an OLTP Application on Symmetry Multiprocessor System // Proc. of the 17th Annual Int. Symposium on Computer Architecture. Seattle, WA, June 1990. IEEE Computer Society Press, 1990. - P. 228-238.
7. Pfister G. Sizing Up Parallel Architectures // DataBase Programming & Design OnLine (http://www.dbpd.com), May 1998. Vol. 11.- No. 5.
8. The Globus Project // http://www.globus.org
9. Distributed.net RSA Challeges // http://www.distributed.net
10. SETI@Home Search for Extraterrestrial Intelligence //http://setiathome.ssl.berkeley.edu11 .The Condor Project // http://www.cs.wisc.edu/condor « 12.Система метакомпьютинга X-Com // http://meta.parallel.ru
11. Pomentable Т., An algorithm for Minimizing Backboard Wiring Functions, Comm. ACM, 8, №11, November 1965, pp. 699-703
12. B.T. Горяинов и др. Статистическая радиотехника. М.: Сов.радио, 1980,-544с.
13. К.К. Морозову В.Г. Одиноков Использованием ЭЦВМ при конструировании некоторых узлов в РЭА. М.: Сов.радио, 1972
14. В.К. Попков, Ю.Ф. Мухопад Специализированные вычислительные среды. Улан-Удэ: Бурят.кн.изд., 1982, - 192с.
15. В.И. Нечипоренко Структурный анализ и методы построения надежных систем. М.: Сов.радио, 1968, - 256с.
16. М.И. Соболевский Анализ и оптимизация структур матричных вычислительных систем. -М.: Энергия, 1979, 168с.
17. Г.Ф.Янбых, Б.А.Столяров Оптимизация информационно-вычислительных сетей. -М.: Радио и связь, 1987, 232с.
18. В. Пятаев, А.В. Семашко Особенности формализации задачи оптимизации структуры кампусных сетей. Электронный журнал «Исследовано в России» // http://zhurnal.ape.relarn.ru/articles/2001/000.pdf
19. Optimization models for communication network design. L. Berry, B. Murtagh, G. McMahon, S. Sugden. Proceedings of the Fourth International Meeting Decision Sciences Institute, Sydney Australia, 1997
20. Griffith, P.S., Proestaki, A. & Sinclair, M.C., Heuristic Topological Design of Low-cost
21. Optical Telecommunication Networks, Proc. 12th UK Performance Engineering Workshop, Edinburgh, September 1996, pp. 129-140.
22. В.Г. Олифер, H.A. Олифер Компьютерные сети. Принципы, технологии, протоколы. СПб: Издательство «Питер», 1999, - 672с.
23. М.В. Кульгин Технологии корпоративных сетей. Энциклопедия. СПб.: Издательство «Питер», 1999, - 704 с.
24. Ю.П. Зайченко, Ю.В. Гонта Структурная оптимизация сетей ЭВМ. К.: Техшка, 1986. - 168с.
25. В. Коваленко, Д. Корягин Вычислительная инфраструктура будущего Журнал «Открытые системы», №11-12/1999
26. Northouse Richard A., Fu King-Sun. Dynamic scheduling of large digital computer systems using adaptive control and clustering techniques. "IEEE Trans. Syst., Man. and Cybern.", 1973, v.3, №3, p.225-234
27. Динамическое планирование больших ВС с использованием адаптивного управления. Экспресс-информация. Вычислительная техника. М.: ВИНИТИ, 1973, №34, с.1-7
28. Лаборатория Параллельных Информационных Технологий НИВЦ МГУ // http://www.parallel.ru
29. И. Шагин Тестирование производительности вычислительных систем // http://www.exelenz.ru
30. Тесты производительности компьютеров и системного ПО // http -.//parallel, rb .ru/computers/benchmarks/
31. A.H. Андреев, Вл.В.Воеводин Методика измерения основных характеристик программно-аппаратной среды. // www.dvo.ru/benchmarks.htm
32. В.Коваленко, Е.Коваленко Пакетная обработка заданий в компьютерных сетях. «Открытые системы», №07-08,2000
33. М. Кузьминский. NQS и пакетная обработка в Unix. «Открытые системы» 1997, №1. http://www.osp.ru/os/1997/01/18.htm
34. Д.Владимиров Кластерная система Condor. «Открытые системы», №0708,2000
35. А.В.Богданов Параллельное программирование и использование прикладного ПО на параллельных суперкомпьютерах. // http://skif.pereslavl.ru/csa/
36. R.D.Williams Performance of Dynamic Load Balancing Algorithms for Unstructured Mesh Calculations // http.7/citeseer.ni.nec.com/correct/59103
37. J.Gwo, F.Hoffman, W.Hargrowe Mechanistic-based genetic algorithm search on a Beowulf cluster of linux PCs // http://research.esd.ornl.gov/~forrest/hpc2000/
38. Д.П.Андерсон Общественный компьютинг. Вовлечение людей в науку. // ^ www.gridclub.ru/grid public.pdf
39. D. P. Anderson, J. Cobb, Е. Korpela, М. Lebofsky, and D. Werthimer. SETI@home: An experiment in public-resource computing. Communications of the ACM, Nov. 2002, Vol. 45 No. 11, pp. 56-61.
40. Я. Ковалика. М.: Радио и связь, 1988.
41. Проектрирование монтажных плат на ЭВМ. Под ред. К.К.Морозова, М.:1. Сов. радио, 1979, 224 с.
42. Теория и методы автоматизации проектирования вычислительных систем. Под ред. М.Брейера, М.: Мир, 1977, 282 с.
43. Н. Кристофидес Теория графов. Алгоритмический подход. М.: Мир, 1978, -432 с.
44. Павлова М. Высокопроизводительные алгоритмы // http://www.csa.ru/analitik49.«LAM/MPI Parallel Computing One-step Tutorial: MPI: It's easy to get started», статья на http://www.lam-mpi.org
45. О.Евсеев И. «MPI программный инструмент для параллельных вычислений», статья на http://www.csa.ru51 .Ian Foster "WHAT IS THE GRID? A THREE POINT CHECKLIST" // http://www-fp.mcs.anl.gov/~foster/Articles/WhatIsTheGrid.pdf
46. Я. Фостер, К.Кессельман, С.Тьюке Анатомия Грид Создание масштабируемых виртуальных организаций // http://www.Rridclub.ru/gridwhat2.pdf
47. Radajewski J., Eadline D. Beowulf HO WTO
48. Что такое Beowulf? (технология организации параллельных вычислений на Linux-кластерах) // Лаборатория Параллельных Информационных Технологий, НИВЦ МГУ (http://parallel.ru)
49. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984г.
50. Amdahl G. Validity of the single-processor approach to achieving large-scale computing capabilities. // Proc. 1967 AFIPS Conf., AFIPS Press. 1967
51. Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования. М., С-Пб, Киев: Изд. «Вильяме». - 2003. - 505с.
52. Антонов A.B. Эффективная организация параллельных распределенных вычислений на основе кластерной технологии. // Диссертационная работа на соискание ученой степени кандидата технических наук. Пенза 2005.
53. Вентцель Е. С. Исследование операций. М., «Советское радио», 1972, 552 с.
54. Токарев А. Н. Инструментальная система проектирования и верификации алгоритмов цифровых устройств обработки информации / А. В. Антонов, А. Н. Токарев // XXXVIII международная научная студенческая конференция, г.Новосибирск, 2000г.
55. Токарев А. Н. Инструментальная подсистема автоматизации проектирования управляющей и операционной части цифровыхустройств / А. В. Антонов, А. Н. Токарев // VIII международная студенческая школа-семинар, г. Судак, 2000г.
56. Токарев А. Н. Принципы организации параллельной вычислительной системы с доступом через Интернет / А. В. Антонов, А. Н. Токарев // Материалы XIII Международной школе-семинаре «Синтез и сложность управляющих систем» (Пенза, 14-20 октября 2002).
57. Токарев А. Н. Программный комплекс «Система распределенных вычислений» Ма1:Ше1:. Оптимизация производительности. Сборник научных трудов «Вычислительные системы и технологии обработки информации» Пенза: Изд-во ПензГУ, 2005
58. Токарев А. Н. Оптимизация алгоритмов при их реализации в системе распределенных вычислений. / А.Н. Токарев, Н.П. Вашкевич // Известия высших учебных заведений Поволжский регион Технические науки, №2 2004г.
59. Токарев А. Н. Адаптивная стратегия размещения подзадач в распределённых вычислительных системах кластерно-метакомпьютерного типа // Труды 1-го Международного форума «Актуальные проблемы современной науки». Самара, 2005 г. Стр. 110113
60. Токарев А. Н. Оптимизация размещения подзадач в распределённых вычислительных системах с ненадёжными узлами // Труды 1-го Международного форума «Актуальные проблемы современной науки». Самара, 2005 г. Стр. 113-116
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.