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

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

ТОКАРЕВ Андрей Николаевич

СТРАТЕГИЯ РАЗМЕЩЕНИЯ ПОДЗАДАЧ В РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ КЛАСТЕРНО-МЕТАКОМПЬЮТЕРНОГО ТИПА

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

#

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

ПЕНЗА 2005

Работа выполнена на кафедре «Вычислительная техника» в Пензенском государственном университете.

Научный руководитель - доктор технических наук,

профессор Вашкевич Н. П.

Официальные оппоненты: доктор технических наук,

профессор Лебедев В. Б.;

кандидат технических наук, доцент Бнкташев Р. А.

Ведущая организация - ФГУП «НИКИРЭТ» г. Заречный Пензенской обл.

Защита диссертации состоится « »_2005 г., в_часов,

на заседании диссертационного совета Д 212.186.01 в Пензенском государственном университете по адресу: 440026, г. Пенза, ул. Красная, 40.

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

Автореферат разослан «_»_2005 г.

Ученый секретарь У

диссертационного совета /

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

профессор

Шашков Б. Д.

ИчРГ

12171И

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

Актуальность проблемы. В популярных технологиях параллельного программирования типа 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 страницы приложений.

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

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

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

ся их достоинства и недостатки. Выделяются параметры кластерно-метакомпьютерных систем.

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

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

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

Предлагается стратегия размещения подзадач в идеально надежной системе. Вводятся три основных характеристики связки узел/канал связи: индекс производительности Iиндекс пропускной способности 1-р и индекс латентности ^.

Вводится термин «обобщенный объем задачи» Sj, включающий

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

С использованием этих данных аналитически выводится время решения некоторой у -й подзадачи в / -м узле

кс1п+(к8 +кК)1а

ty=2tLi+Sj-

hihi

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

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

Из условия максимальной эффективности выводится система линейных уравнений, аналитически описывающая процесс решения задачи в РВСКМТ, в результате решения которой находится массив подзадач 5 = [5], 52,53,..., ].

Рассматривается также вариант последовательного характера выдачи подзадач сервером, который необходимо учитывать для большого числа вычислительных узлов и для задач с большими объемами данных для передачи узлам (рис. 1).

N

-V

/о Г, Т2 /э I

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

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

Предложенные стратегии позволяют оптимальным образом разместить подзадачи в РВСКМТ без учета отказов узлов.

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

Рис. 2 иллюстрирует тот факт, что любой узел может отказать на этапе решения своей подзадачи (если время решения подзадачи ^

больше времени безотказной работы узла ) и восстановиться лишь через время восстановления Tf.

к J " "...

-X-

Рис. 2. Работа ненадежного вычислительного узла во времени

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

В силу того, что вероятность безотказной работы уменьшается с ростом времени работы /, необходимо определить время Т^, которое будет соответствовать такой вероятности безотказной работы, которая нас устроит. По этой вероятности для каждого узла можно определить время, в течение которого узел будет функционировать, а затем соответственно этому времени определить объем подзадачи 5" (рис. 3).

Рис. 3. Процесс расчета блока в одном узле

Время решения подзадачи первым узлом состоит из времени непосредственного расчета блоков, времени холостого расчета следующих блоков и времени восстановления узла после отказов:

Г, =М1[Т„1(Р) + ТХ1 +ткх]-[тхх +гя].

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

А/, [ты (/>) + 7>, +Тт]- [7*1 + 7>, ] = М2 2 (Р) + ТХ2 + ТН2 ]-[Тх 2 + ТЯ2 £

ТХ2 + [ТХ2 ТхЗ + ТЮ

= [т„ы (Р) +Тш+т^]-[тш+ Тт ];

м 'кс1п+(к5+к Я)1С,

В этой системе последнее уравнение, являющееся условием полноты задачи, получено с использованием утверждения, что на этапе [0;7^1 ] работа узла не отличается от работы в безотказной системе.

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

идеальных систем, находится подзадача минимального объема ^гшп = т!п(5,), исходя из которого определяется количество подзадач.

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

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

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

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

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

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

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

Возможны два варианта организации данного адаптивного метода размещения:

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

Так как узел к моменту получения результата решения первой подзадачи уже функционирует в течение некоторого времени Т*,

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

Предлагается алгоритм функционирования серверного узла для данного адаптивного метода размещения подзадач.

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

Процесс функционирования узла является дискретным марковским процессом с двумя состояниями. На участках графика функции надежности, где надежность близка к единице, как показывает практика, функция надежности хорошо аппроксимируется линейной функцией (график на рис. 5 построен по статистическим данным, полученным программами NS Logger и NS Analyzer, рассматриваемыми в четвертой главе).

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

Л1М-0?

Рис. 5. Аппроксимация функции надежности узла линейной функцией

Из найденного с использованием этой методики значения переходной вероятности тс|2 можно определить значение времени т до перехода из состояния 1 в состояние 2, т. е. отказ узла:

Х + ц

Предлагается метод адаптивного размещения подзадач в РВСКМТ. Начальная часть задачи разбивается с использованием одного из методов статической стратегии размещения подзадач. К моменту отказа узла серверу известен ряд характеристик, которые по-

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

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

Предлагается алгоритм функционирования серверного узла, реализующего данную адаптивную стратегию размещения.

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

Все предложенные в данной работе методы размещения подзадач были опробованы на РВСКМТ собственной разработки «MathNet» при решении как расчетно-ориентированных задач, где кс > {kg + kR) (поиск экстремумов, численное интегрирование), так и обменно-ориентированных задач, где кс <(к$+кц) (умножение матриц).

1. Статическая стратегия размещения подзадач в системе без отказов. В качестве исходных данных для реализации данной стратегии были сначала выбраны тактовые частоты процессоров, а затем результаты выполнения тестовой подзадачи. Полученное уменьшение времени расчета составляет 19% (рис. 6).

Рис. 6. Результаты тестовых запусков в идеально надежной системе

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

По сравнению с равномерным разбиением на 120 подзадач, которое является наилучшим, предложенная стратегия дает уменьшение времени расчета на величину от 10 до 25% (а для обменно-ориентированных задач - на величину от 21 до 53%) в зависимости от производительности отказавшего узла. Кроме того, предложенная стратегия дает принципиальную возможность решить задачу на системе с множественными отказами, тогда как при простом равномерном делении задачи на подзадачи большинство таких подзадач решается вхолостую из-за того, что при достаточно большом размере подзадачи узел отказывает до того, как подзадача решена, а при малом размере подзадачи решающее влияние на протекание процесса вычислений начинает оказывать сеть.

Рис. 7. Сравнение результатов тестов для ненадежных систем

3. Динамическая адаптивная стратегия размещения подзадач.

Были проведены тестовые запуски для метода адаптивного размещения подзадач с имеющейся статистикой и для метода с динамически рассчитываемыми данными о надежности узлов. Результаты тестирования приведены на рис. 8.

2500 • 2400

О ИММКНОС1И

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

Предложенная динамическая адаптивная стратегия размещения подзадач позволяет уменьшить время расчета в РВСКМТ с ненадежными узлами на величину от 8 до 10% и значительно уменьшить нагрузку на сеть за счет меньшего количества передаваемых подзадач. Кроме того, один из рассмотренных методов не нуждается в наличии статистической информации о надежности узлов.

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

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

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

Сдано в производство 14.10.05. Формат 60х84*/16. Бумага писчая. Печать офсетная. Усл. печ. л. 1,16. Заказ № 629. Тираж 100.

Издательство Пензенского государственного университета. 440026, Пенза, Красная, 40

ч >

í !

Ir

2 О 4 3 6

РНБ Русский фонд

2006-4 22414

ВВЕДЕНИЕ.

Глава 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 Выводы по главе.'.

В настоящее время фундаментальные и прикладные проблемы, эффективное решение которых возможно только с использованием высокопроизводительных вычислений, объединены понятием "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. Динамическая адаптивная стратегия размещения подзадач на основе имеющихся заранее или рассчитываемых динамически данных о надежности узлов.

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

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