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

005004850

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

Аль-хулайди Абдулмаджид Ахмед Галеб

РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИШОВ УПРАВЛЕНИЯ ОЧЕРЕДЯМИ ЗАДАНИЙ ПРИ ОРГАНИЗАЦИИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ В КЛАСТЕРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

Специальность^. 13.01 - Системный анализ, управление и обработка информации (Вычислительная техника и информатика)

АВТОРЕФЕРАТ

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

-8 ДЕК 2011

Ростов-на-Дону 2011

005004850

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

Научный руководитель: Заслуженный деятель науки РФ,

доктор технических наук, профессор Чернышев Юрий Олегович

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

Ромм Яков Евсеевич

Кандидат технических наук, доцент Остроух Евгений Николаевич

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

Ростовский

Ростовский государственный

университет путей сообщений (РГУПС), г. Ростов-на-Дону

Защита состоится « 22 » декабря 2011 г. в 1420 на заседании диссертационного совета Д 212.208.22 Южного федерального университета по адресу: г.Таганрог, пер. Некрасовский, 44, ауд. Д- 406.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, г. Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан « ¡5 »_1_[_2011 г.

Просим Вас прислать отзыв на автореферат, заверенный гербовой печатью учреждения, по адресу: 347928, ГСП-17А, Ростовская область, г.Таганрог, пер. Некрасовский, 44, диссертационный совет Д 212.208.22.

Ученый секретарь диссертационного совета Д 212.208.22,доктор технических наук, профессор

Целых А.Н.

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

Актуальность темы исследования. Решение многих важных практических задач требует пользования многопроцессорных систем. Важность вопросов оптимизации в них вычислитель-[X процессов, в том числе организации параллельных вычислений на кластерах, сегодня не вы-вает сомнений. В июле 2009 года на заседания Совета безопасности России, президент РФ А.Медведев говорил о важности кластеров для страны. При организации параллельных вычис -ний возникает проблема обеспечения ускорения решения задач. Общая производительность [числений на кластере во многом зависит от применяемых способов управления очередью зада-[й, поступающих на кластер. Использование эффективных алгоритмов управления очередью -о универсальный способ повышения скорости решения задачи, повышения производительности раллельных вычислений. В настоящее время к разработке новых моделей, методов, алгоритмов технологий управления очередями проявляется очень большой интерес со стороны научного ис-едования. Повышению эффективности управления очередями в параллельных вычислениях по-ящены работы таких ученых, как: Kelly P.P., Limic V., Chen L.,Norros I. Bhaskar T.R, Jeffrey M.K, li Jin,Daniel A, Wenbin Jiang, Jia-Shiang, Baras, John S, Коваленко B.H., Корягин Д.А., Семячкин А и других. Описанная проблема достаточно хорошо исследована в зарубежной литературе. К жалению, на русском языке редко встречаются даже переводы зарубежных работ по данной те-сгике. В известных и широко применяемых алгоритмов существует ряд недостатков, Как прави-, планировщики рассматривают задания из очереди по порядку, одно за другим. Однако, поря-к, в котором задания планируются, может вести к фрагментации ресурсов (большая часть про-ссоров занято мелкими заданиями); по этой причине, даже если задание имеет самый высокий иоритет, необходимый ему объём ресурсов может никогда не образоваться и задание может ни-гда не стартовать — возникнет эффект «зависания» (starvation). Основная проблема методов анирования, основанных на разделении времени процессоров, при обслуживании параллельных цаний, состоит в том, что процессы одного задания могут быть прерваны и перезапущены в раз-ie моменты времени, что приводит к снижению общей эффективности использования ресурсов, к как некоторое время тратится на ожидание одним процессом перезапуска другого. Эти обстоя-льства делают актуальным теоретическое и практическое исследование применения алгоритмов равления очередями заданий при организации параллельных вычислений для повышения эф-отивности производительности параллельных вычислений, обеспечения ускорения решения здч в кластерных системах.

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

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

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

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

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

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

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

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

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

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

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

1. Разработан стохастический подход к оценке управления очередями заданий с использованием Марковских процессов, и модель кластера MPI/MPICH_NEW на основе семантической сети для управления очередями заданий, при организации параллельных вычислений на кластере. Предложенный подход и модель отличаются от известных, таких, как методы разделения ресурсов (FCFS, Backfill, SJF) и методы разделения времени (Gang scheduling), по строению и структуре, тем, что они могут устранять проблемы старвации (зависания) заданий, требующих большого количества ресурсов, определять параметры планировщика Maui и обеспечивать эффективное использование свободных вычислительных ядер всех узлов кластера, среднего времени, которое задание проводит в очереди, для различного числа узлов.

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

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

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

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

1. Стохастический подход к оценке управления очередями заданий с использованием Maj ковских процессов для параллельных вычислений на кластере, и модель кластер MPI/MPICH_NEW на основе семантической сети для управления очередями заданий в планиро! щике Maui, что позволяет определять параметры планировщика Maui, обеспечивать эффекта ное использование свободных вычислительных ядер всех узлов кластера, повысить эффекта! ность производительности параллельных вычислений и уменьшить время ожидания заданий очереди.

2. Алгоритмы обслуживания очередями в кластерных вычислительных системах: алгорит распределения ресурсов между процессами, алгоритм управления порядком запуска заданий. 3i позволяет в совокупности получить более высокие показатели эффективности параллельных вь числений, обеспечить ускорение решения задач в кластерных системах и, уменьшить время ож! дания заданий в очереди.

3. Параллельные алгоритмы для нахождения опорного плана в транспортной задаче на ос» ве метода Фогеля; нахождения оптимального решения транспортной задачи на основе метода ni тенциала; нахождения минимального остовного дерева, на основе метода Борувки для выполн ния в кластерных системах, которые позволяют увеличить производительность и в том числе пр использовании нескольких тысяч процессоров, повысить эффективность параллельных вычисл ний и, обеспечить ускорение решения задач в кластерных системах.

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

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

х.

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

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

1. Использование стохастического подхода, модели и алгоритмов управления очередями ластерном пакете MPI/MPICH путем расширения его до MPI/ MP1CHNEW, т. е создание про-1ммной модели кластера, на основе VmWare (виртуальных машин), пакета Torque и пакета JI/MPICH (использовался OpenSourse) с целью повышения эффективности производительности раллельных вычислений.

2. Зарегистрированное в Реестре программ для ЭВМ, Федеральной службы по интеллекту-,1юй собственности, патентам и товарным знакам (Роспатент) от 29 июля 2011 г. " Программное гдство для исследования алгоритмов управления очередями заданий в кластерных системах", вышает эффективность производительности параллельных вычислений и уменьшает время идания заданий в очереди. Свидетельство о государственной регистрации программы для ЭВМ 2011615951.

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

Реестре программ для ЭВМ, Федеральной службы по интеллектуальной собственности, патен-л и товарным знакам (Роспатент) от 27 июля 2011 г. :

- «Параллельная программа дая решения транспортной задачи в кластерных системах». Свидетельство о государственной регистрации программы для ЭВМ № 2011615890;

- «Параллельная программа для нахождения минимального

остовного дерева в кластерных системах». Свидетельство о государственной регистрации программы для ЭВМ № 2011615889

4. Комплекс программ реализован на языке С++ под Windows ХР на ЭВМ типа IBM PC. сперименты проводились на кластере следующей конфигурации:

- 8 вычислительных узлов (Intel Pentium 4 2,4 ГГц);

- управляющий узел (Intel Pentium 4 2,4 ГГц).

- узлы объединены между собой сетью Infiniband (пропускная способность 4 Гбит/с).

Отличительная особенность разработанного программного комплекса - это эффективное

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

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

Реализация и внедрение результатов работы. Полученные результаты использованы при полнении фундаментальной госбюджетной научно-исследовательской работы тематического ана 2011 года ИЭиМ Донского государственного технического университета (ДГТУ) на кафедре ычислительные системы и информационная безопасность» («ВС и ИБ») по теме: «Разработка и следование моделей, методов и алгоритмов решения нелинейных транспортных задач, осно-нных на эволюционном моделировании», выполняемой по тематическому плану Мииобрнауки. пер и алы диссертации использованы в научно-исследовательской работе, выполняемой по гран-№ 10-01-00481-а на тему «Развитие теории и практики применения интеллектуальных методов >аспределительных системах управления базами данных », финансируемой Российским фондом ндаментальных исследований (1.01.2010-31.12.11). Кроме того, результаты выполненной рабо-, используются в учебном процессе на кафедре «ВС и БС» при чтении лекций и проведении актических занятий по дисциплинам «Автоматизированное управление», «Многопроцессорные стемы и параллельное программирование», «Высокопроизводительные вычислительные систе-

мы», «Основы оптимального управления», «Системное программирование», «Вычислительк машины, системы и сети».

Акты об использовании прилагаются.

Апробация диссертационной работы. Основные научные и практические результаты | боты докладывались, обсуждались и были одобрены на Международном конгрессе; " Интелл< туальные системы "(AIS-11) и " Интеллектуальные САПР "(CAD-2011)(г. Геленджик,2011г.) и Международных научно-технических конференциях: XXIII Международная научная конфер( ция " Математические методы в технике и технологиях " (ММТТ-23), (СГТУ, г. Саратов,2010] XXIV Международная научная конференция " Математические методы в технике и технологиях (ММТТ-24)(г. Киев,2011г.); IX Международная научная техническая конференция "Инновац! экология и ресурсосберегающие технологии на предприятиях машиностроения, авиастроен! транспорта и сельского хозяйства" (ИнЭРТ), (ДГТУ, г.Ростов н/Д,2010г.); XVI Международ! открытая научная конференция " Современные проблемы информатизации ",(СПИ-АС)( ВП г.Воронеж , 2011г.); Российская Академия Естествознания. Международная научная конферени " Новые информационные технологии и системы ",(г. Патгайя - Таиланд , 20 Юг.);VI Между! родный научно-методический симпозиум "Современные проблемы многоуровневого образо! ния" , (г. Дивноморск - 2011).

Публикации. По материалам диссертации опубликовано 20 печатных работ, в том числе статей в изданиях, входящих в «Перечень ведущих научных журналов и изданиях, выпускаемы: Российской Федерации», утвержденных ВАК РФ. По теме исследования получено 3 свидете.1 ства об официальной регистрации программ для ЭВМ.

Структура и объём работы. Рукопись диссертационной работы состоит из введения, чет рех глав, заключения, библиографического списка из 136 наименований, изложенных на 163 ст| ницах машинописного текста и 10 приложений, содержит 52 рисунок, 12 таблиц.

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

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

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

Вторая глава посвящена разработке модели управления очередями на основе семантическ сети и стохастического похода к оценке управления очередями заданий для параллельных в числений на кластерах, с использованием Марковских процессов, с целью повышения произво; тельности параллельных вычислений, обеспечения ускорения решения задач в кластерных сис мах и уменьшения времени ожидания заданий в очереди. В этой главе показано, как теоретическ положения теории массового обслуживания (ТМО) - теории очередей - и семантическая et применяются к практическим задачам управления очередями заданий в кластерной системе, основе семантической сети разработана модель кластера MPI/MPICH_NEW с многоядерны узлами, управляемого планировщика Maui. На рис. 1 представлена структурная схема модели ю стерной вычислительной системы для управления планировщиком Maui. Семантическая моде сети реализует четыре типа связей между объектами: классификацию, агрегирование, обобщен] ассоциацию. Модель существенно облегчает доступ к знаниям и повышает производительность целом. Рассмотрим работу модели. Обозначим сеть как N= (Q ,Т), где Q - множество узлов kj стера, Т - переходы. Структурная схема сети изображена на рис. 1.

>00 \ч tl / ООО \

(. a ) и"1- ......,

K—'---------с i .....-Jo V" —

/—* \ r......\ , V

t -—M у- >-......«-Г

tk*3- / 4........- tr„ v—'Л\ t**

©

Рис. 1. Структурная схема модели кластерной MPI/MPICH_NEW на основе семантической сети для управления планировщиком Maui

На рис.1, приведены следующие условные обозначения■Ql>—>QZ — узлы, создающие

эдные заявки; ti-tz — переходы, где г — общее число источников; Q — некоторая предвари-

1ьная входная очередь; О — внутренняя очередь планировщика; О ,..., О • — вычислила'«я

)ьные устройства, где № —текущее их количество; Аг 6 {0,1,...,Л' ), //-совокупное количест-вычислительных ядер в системе; t^ - te;v — переходы к вершине выхода (exit). Введем обозна-шя: alC - число ядер, выделенных задаче планировщиком. X, Y -соответственно минимальное максимальное число ядер, нужное заявке. тахТ-максимальное время выполнения заявки. \еТ- время, требуемое подзадаче для выполнения. ехС-число ядер, необходимых подзадаче. - множество подзадач. timeP - время нахождения заявки в системе, р - приоритет заявки, exclus war исключительного использования задачей ресурсов узла subCN - множество номеров под-ютеров. NS- общее количество подкластеров. нкционирование модели включает два процесса:

1. Освобождение ресурсов. Для каждой задачи происходит выделение ресурсов. Задача мчает в себя несколько подзадач. После того, как завершается выполнение подзадач, производя поиск других задач, не требующих уже полностью выделенных для них ресурсов, и отменя-выделение ресурсов, оказывающихся в таком случае лишними. Математически условие воз-жности освобождения ресурсов, используемых задач 3 h j-Qiù/jJ- ST [к]. exC<Q£,[/].a/C.. Количе-io освободившихся ресурсов в таком случае можно выразить как:

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

е ресурсы, т.е. 3,3/ : ^(Q [j\-Sl\k]£xC) > Q [;']л/С., и имеющие при этом наибольший

к

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

Исходя из вышеуказанных рассуждений, выделяемое для приоритегной задачи количество :урсов (MD) в виде формулы можно записать как

MD= Qr;,lj]Y'QE,lj]Y-RilV'

W,W <R.

: U).sri^].ercj - QE.Wl-"lc — число ресурсов, дополнительно требуемое задаче.

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

В диссертации разработан стохастический подход к оценке управления очередями с испо. зованием Марковских процессов на кластерных системах. Рассмотрим Марковский случайн процесс g(t) с конечным числом состояний £>,, Е\, ..,, Е„. Обозначим через Pi(l) вероятность то что случайный процесс в момент времени t находится в состоянии Ei: Pi-Pr{g{t)=Ei), i = 0,п.

Очевидно, что в любой момент времени I процесс находится в одном из п+\ возможных стояний, т.е. события g{t}=Ei, i = 0,п заключающиеся в том, что в момент времени t процесс на: дится в состояниях £(>, Ei ,..,, En, образуют полную группу несовместных событий. Отсюда еле, ет, что в любой момент времени t выполняется условие:

/=0

которое называется нормировочным. Совокупность вероятностей Pi(t), /=0,«, может быть npi ставлена вектором, называемым вектором состояний, с числом компонент, равным числу возмс ных состояний процесса:/^)^^'), ЛИ, ..., Pn(t)}.

Основная задача исследования системы с использованием Марковских случайных процесс заключается в определении вероятностей Pi{t), / = 0,п, нахождения процесса в любой момент в; мени t в том или ином состоянии, что дает полную информацию о случайном процессе. Для реи ния данной задачи необходимо:

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

2) описать переходы между состояниями. Состояние процесса в начальный момент време t=0 задается вектором начальных вероятностей: Р(0)={Р()(0), Р1(0), ..., Рп(0)}.

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

Для Марковских систем вероятность перехода на п шагов PtJ (то есть вероятность того,1 после п переходов из начального состояния i Марковская цепь будет находиться в конечном i стоянии j) будет стремиться к пределу itj с ростом i и будет независимым от начального состоя!" /'. Этот предел называется установившимся состоянием. В нашем случае установившееся сосп ние означает, что в некоторый момент в будущем, в системе будет находиться j заданий. С nos щью уравнения Эрланга возможно рассчитать вероятность устойчивого состояния приведени системы.

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

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

j-oJ*'-

В случае, если нас интересует число ожидающих заданий, находящихся в очереди Lq , то < можно найти, также выведя систему из устойчивого состояния.

На основе статистических данных использования модели системы можно определить те поступления заданий X и темп обслуживания системой. В соответствии с законом Литтла мо» сказать, что среднее время, которое задание проводит в системе

W=L

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

программного обеспечения в нашем случае Maui. Главная цель системы управления с очередью .»то уменьшение времени ожидания заданий в очереди.

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

Третья глава посвящена разработке алгоритмов управления очередями заданий для кла-ерных систем. Приводятся описания структурных схем алгоритма управления порядком запуска даний и алгоритма распределения ресурсов между процессами. Кроме этого, для проверки пред->женных модели и алгоритмов управления очередями заданий на кластерных системах, разрабо-IH ряд алгоритмов для решения распространённых на практике задач. Во-первых, алгоритм на-»ждения минимального остовного дерева на основе метода Борувки. Во-вторых, алгоритмы ре-ения транспортной задачи для параллельных систем. Выбираются основные классы задач, кото->ie будут решаться на кластере, модель и алгоритмы управления очередями. Приводятся теорети-:ские оценки оптимального количества вычислительных узлов кластерных систем, времени вы-хпнения параллельных алгоритмов решения транспортной задачи на кластере, вычислительной южности параллельного алгоритма нахождения минимального остовного дерева, на основе мета Борувки, с целью повышения эффективности параллельной обработки на кластере.

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

Предлагаемый алгоритм состоит из следующих процедур:

1. Определяются типы ресурсов, используемых данным заданием, их количество, а также эиоритет задачи.

2. Задания распределяются по очередям и упорядочиваются в порядке приоритета.

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

На рис. 2 представлена схема алгоритма распределения ресурсов между процессами

Рис.2. Структурная схема алгоритма распределения ресурсов между процессами

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

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

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

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

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

4. Получившееся множество заданий упорядочивается в соответствии с приоритетами, кот рые назначаются, исходя из ряда условий. В частности, принимаются во внимание запрашиваемь ресурсы, принадлежность задания тому или иному пользователю, историческая информация (кт сколько заданий запустил, чтобы избежать ситуации, когда кластер «оккупирован» кем-то, и н доступен для всех остальных). В соответствии с полученным упорядоченным списком произв дится планирование. Задания рассматриваются, начиная с самого приоритетного. На рис. 3 пре, ставлена структурная схема алгоритма управления порядком запуска, где i - номер задание.

Рис.3. Структурная схема алгоритма управления порядком запуска заданий

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

Параллельный алгоритм для нахождения минимального остовного дерева состоит из сл> дующих шагов (рис.4.):

Шаг 1 (выбор самого лёгкого): В списке ребер каждой вершины производится поиск самого кого инцидентного ребра.

Шаг 2 (поиск корня): Используя алгоритм подмены указателя для каждой вершины нахо-гся корень дерева, которому она принадлежит Сначала корень каждого компонента устанавли-гг свой указатель на себя. Каждая прочая вершина, первоначально указывает на другую конеч-о точку самого легкого инцидентного ему ребра. Указатели вершин далее обновляются повто-ошимися подменами указателя, так, что за одну замену указателя, вершина обновляет свой ука-ель на равный своего родителя.

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

Шаг 4 (слияние): Ребра всех вершин компонента, посылаются процессору, который имеет тсок ребер корня. Список ребер далее сливается процессором.

Шаг 5 (очистка): Каждый процессор, выполняет последовательный алгоритм на своем собст-шом списке ребер. На рис.4, представлены шаги параллельного алгоритма нахождения мини-иыюго остовного дерева.

Шаг 1. Выбор самого лёгкого ребра.

Шаг 2. Поиск корня. ООО О

Шаг 3. Переименование еершин. ¿66 <ь

Шаг 4. Слияние

Шаг 5. Очистка. ООО о

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

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

рувки оценена как 0(^!).

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

1. Для каждой строки и столбца матрицы стоимости перевозок определяем разницу между ¿меньшим значением стоимости и ближайшим к нему (т. н. штраф). Поиск штрафа по каждой >оке и столбцу оформляется в виде отдельной задачи и назначается свободному процессору.

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

3. Максимизируем поставку в ячейку х[ц], выбрав минимальное значение из потребности гребителя и[1] и мощности поставщика уЦ].

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

5. Если не все потребности (мощности) задействованы, то повторяем алгоритм.

На рис. 5. представлена структурная схема параллельного алгоритма нахождения опорного ана методом Фогеля.

Рис. 5. Структурная схема параллельного алгоритма нахождения опорного плана

методом Фогеля.

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

1. Полагаем v„ = 0;

2. Находимщ, i= 1 ..m, и Vj,j=1..n-1;

3. Разделяем множество клеток на части пропорционально количеству процессоров N. Пе] даём информацию вычислительным узлам;

4. Для каждой клетки (i, j) в группе рассчитываем kg = u, + v, - сд и находим max к^;

5. Получаем данные от вычислительных узлов и выбираем наибольший тахк (для ячей maxi, maxj) из max kg по группам;

9. Для каждой ячейки полагаем

где 1 - порядковый но-

6. Если maxk < 0, то план является оптимальным и метод завершается;

7. Строим цикл из ячейки (maxi, maxj), попутно находя наименьшее mine из значений с в ячейках, имеющие в цикле чётный номер;

8. Разбиваем цикл на части пропорционально количеству узлов N. Передаём координаты и положение ячеек цикла вычислительным узлам.

с:: + mine, I - нечётное, с, j - mine, I-ч ётное,

мер ячейки в цикле, i, j - координаты ячейки цикла

10. Переходим к шагу 3.

На рис. 7. представлена схема параллельного алгоритма нахождения оптимального решения транспортной задачи методом потенциалов. Приведены следующие условные обозначения: u;, vj — симплексные множители (или потенциалы) для строк и столбцов соответственно (i = l,2..m, j = l,2..n); Cjj — план поставок; — коэффициенты для каждой ячейки, которые рассчитываются по формуле kij = u, + Vj - Cij; mine - переменная, в которой хранится минимальное значение Cij для всех ячеек, входящих в цикл перерасчёта.

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

вающих узлов в параллельной системе равно q, причём

q <2т

, все данные задачи и программа

управлениям решением находится на управляющем узле (сервере, обозначен «С»).

Уровень 1 • г (i» 5m J Пер«СШКЯ cipc-к ¿столСио»'*

Уровень (M^J • • • QiO \ Пслгчет xtrrpa^<7« алжегрок

Уровень 3 * • • (Лч) , Пересылка штрвфо»

Уровень •J • ) ^ —ч Пересылка штрафовал« (П!то) срамшаа

Уроеснь 5 QÄhS • • • (мм Сраетни« UUp»lJ«»

Уровень б • » • Пересылка р«зульт*х*

Рис. 6. Схема одного этапа выполнения работ .¡-ой итерации для получения опорного плана методом штрафов

На рис.6 приведены следующие условные обозначения: П т один это номер операции пересылки (П) в матрице, т- номер строки (столбца)матрицы; М1, — одам это номер операции обработки (М) в матрице^ - номер вычислительного узла; С — сервер; т= 1, т — строки (га-

количество строк);ц=1, ц — узлы ^ - количество вычислительных узлов); Д =1, т-\ — номер итерации метода штрафов. Для определения числа операций, при реализации этого этапа решения, введём следующие обозначения: ~ вРемя пересылки строк (столбцов) матрицы по строкам

(столбцам) с сервера на каждый вычислительный узел.

Рис. 7. Схема параллельного алгоритма нахождения оптимального решения транспортной задачи на основе метода потенциалов.

Время пересылки матрицы можно выразить через пересылку одного элемента (элементарная ресылка): если вычёркиваются только строки (или только столбцы), то

^п =íu„ep x[m2 О'-')]. гДе / - время на пересылку одного элемента. Если вычёркива-

гея, попеременно, строка затем столбец, то г["п =

т -(;-1)х[гн-

ить среднее значение двух предыдущих выражений, то получим

Тп ~~ (замер. *

т

-и-Щт

У-1

Если

(1)

)' - время поиска штрафа для одной строки или столбца на одном узле

Время обработки строки (столбца) на одном узле обработки можно выразить через элемен-рные операции сравнения

е-Г

зл. обр

(2)

время выполнения одной операции сравнения при поиске минимального и следующе-

за ним элемента; Время, затрачиваемое на одном шаге, для поиска штрафа в каждой строке голбце), по всей матрице ресурсов для q узлов обработки, можно записать как

2т—7 + 1

+1|Г^,если<7<(2т-у+1),

Г^, еслид>(2т-у+1) Функция является дискретной, график её показан на рис.8, и рис. 9.

(3)

Рис. 8. График зависимости времени поиска штрафа от числа строк

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

во

Ч 120 £

§ Д_ - .

Г ___________ ._ __ _________________

I ДО ________ ... ... .....

О с > 5 Ю 15 колич*сгяо узлов. С) го

Рис. 9. График зависимости времени поиска штрафа от количества узлов для <7 = 1,20, /и = 10,у = 1,2« и Т*-' = 1.

графика, представленного на рисунке 9. видно, что при увеличении количества узлов с 1 до 1 емя поиска штрафа сократилось в 6 раз. Дальнейшее увеличение количества узлов не эффектив-- при изменении их количества с 7 до 20 получается только двукратный выигрыш(12 раз)

производительности. Дальнейшее увеличение количества узлов приведет к увеличению затрс времени.

Время, затрачиваемое на выполнение ¡-й итерации методом штрафов, определяется из фор мул (1)-(3). Для упрощения расчетов аппроксимируем эти функции:

Т,'п = Т1П'' + (-45-1СГ"?2 + 9• 1 (Г1 д--15-1О" )(2ш- ) +1)2 + (4• 10"'д2 - 0,11 63?+0,768) х

х(2да—/+1)—Зб-Ю"4 V +042-9+87- 10м]. +(2т-у+1)7'^+^+7^.

Зная время выполнения одной итерации алгоритма, можем найти общее время поиска речи ния с помощью параллельного алгоритма:

Тш = Е{

-0"~1)Х m •

O'-D

'».«, +К-45-10-6?2 + 9-10-4?-15-10-4X2m - у+ l)2 +

+ (4-10'V - 0,11631? + 0,768 )(2т - У + 1)- 3610"' + 0,12 ■ д + 87 ■ 10 "" ] 2(ш - У~1)х х + 3(2/и - ] + 1)<„„р + 3/„ „р_ -(2/и - у + 1)(-23 ■ 10'V + 2,2843 д - 2,8412) +

+ -(2/И-У + 1Х-31 -Ю'5?2 + 1,2843 д-3,8412)}. Отсюда получаем вычислительную сложность параллельного алгоритма, которая составляет В СП А— 0( ш 2). На рис.10, представлен график зависимости времени поиска штрафа (элеме : тарное время пересылки и обработки) от количества узлов и количества строк (столбцов)

ima воо

ООО

-т-2(ю in-SQQ

' Т ^ -

количества i-it.n.ij

Рис.10. Зависимость времени поиска штрафов от количества узлов и строк

(столбцов)

Из рис. 10 видно, что сокращение времени, для задачи с большой размерностью, значительь Время решения, для задачи размерности 500 при количестве узлов 20, примерно, в 2 раза меньп: чем при 10 узлах. Далее, время расчетов сокращается, не пропорционально количеству узлов, хо_ и, продолжает уменьшаться. Это вызвано, возрастанием количества пересылок, между вычисл:: тельными узлами.

Путем поиска экстремума функции Тю (д) определено оптимальное число узлов (процесс

ров):

£ [-9 ■■ 10"J (2m - j +1)2 + 0,1163(2m - j +1) ■- 0,12] („^

9 = 1

I [-9■ 10-5(2m-j +l)2 + 8• 10"3(2m-J +1)-72-10" ]/,„6„

Полученная величина q позволяет рационально выделять ресурсы для задачи при достиж нии нужного уровня производительности

В четвертой главе описана методика и приведены результаты экспериментальных исслед: ваний разработанных модели и алгоритмов управления очередями. Произведена экспериментам ная проверка и испытание эффективности предложенных модели и алгоритмов управления очер: дями заданий с помощью параллельных алгоритмов нахождения минимального остовного дерег решения транспортной задачи. Приводится сравнительная характеристика экспериментальных : теоретических оценок параллельных алгоритмов нахождения минимального остовного дерег решения транспортной задачи. Практическая значимость работы заключается в том, что алгорк: мы управления заданиями были применены для расширения библиотеки MPI/MPICH (со свобо. ной лицензией), т.е. в создании программной модели кластера, который содержит реализащ\ предложенных алгоритмов, а также создание программной модели в планировщике Maui, кот: рый содержит реализацию предложенной модели управления очередями. С использован»:

: зого пакета МР1/МР1СН_ЫЕ\^' была проверена эффективность параллельной программы нахо-~ения опорного плана и оптимального решения транспортной задачи, а также параллельной про-аммы нахождения минимального остовного дерева на кластере.

Испытания алгоритма решения транспортной задачи проводились в три этапа. На третьем при увеличении числа ядер от 30 до 40, производительность увеличивается существенно (в 1,37 раз выше при размерности матрицы 1000x1000). Результаты экспериментального исследова-: 1Я предложенной модели управления заданиями, использованных в кластерном пакете 71 \<1Р!('Н \'1Л\' и сравнение их с пакетом МР1/МР1СН приведены на рис.. 1!

Рис. 11. Гистограмма времени ожидания заданий в очереди при модельном и реальном экспериментах

Из гистограммы видно, что имеется незначительный прирост производительности при запуске программы в среде МРУМРГС^ИЕХУ, Однако, при увеличении числа ядер от 30 до 40 про-.¡водительность существенно увеличивается (в 1,37 раз выше при размерности 1000x1000). Почетность модели не превышает 8,87%.

На задаче нахождения минимального остовного дерева на кластере при параллельном алго-ггме на основе метода Борувки испытания проводились в два этапа. На первом этапе, при увели. иии количества вершин от 1000 до 6000 и 20 процессов производительность увеличивается (в 11,14 раз при количестве вершин 6000). На втором этапе, при увеличении количества вершин от Ю0 до 10000 и, числа процессов от 20 до 60 производительность увеличивается более заметно (в 1.29 раз при количестве вершин 10000).

На рис.12, представлен график времени выполнения разработанного параллельного алго-ттма на МР1/МР1СН и улучшенном кластерном пакете МР1/МР1СН_ЫЕ\У

■1,5

4

3 зз 1 3 5 2,5 • 1 2 ' "......1 ■■ : ' ■' ::: ^ ■ : -----

[~^»-МР1/МР1СН | ( -»— МР1/МР1СН №У/|'

-1

1 и

45

<Р ^ / / / / количество вершин

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

По оси абсцисс указано число процессов. Из графика видно, что имеется незначительный .. жрост производительности при запуске программы в среде МР1/МР1СН_№Ш (после внедрения >вых предложенных алгоритмов управления очередью). Однако, при увеличении числа процессе от 20 до 60 прирост производительности становится более заметным (в 1,29 раз быстрее при адичестве вершин 10000). Результаты проведенных экспериментов показывают, что среднее

время выполнения параллельного алгоритма, для нахождения минимального остовного дерева г. MPI/MPICHJNEW, меньше (по крайней мере., на 15.65%), по сравнению с MPIJVTPICH.

Приведены испытания и результаты экспериментальной проверки эффективности предл. женных алгоритмов управления очередями заданий на параллельном алгоритме решения тран: портной задачи на кластере. Испытания проводились в четыре этапа. На первом этапе, при ре:: мерности задачи 50x50, 70x70 и числе процессов 20, изменение производительности не происх" лит. На втором этапе, при размерности задачи 100x100,150x150 ,500x500 и, числа процессов 20 увеличение производительности становится более заметным (в 1,09 раз для матрицы размерное : 500x500). На третьем этапе, при размерности задачи 500x500 и, увеличении числа процессов от до 40, достигается увеличение производительности в 1,12 раз. На четвертом этапе, при увелич -нии числа процессов от 20 до 40, производительность увеличивается в 1,24 раз для матрицы ре : мерности ЮООхЮОО.Результаты вычислительных экспериментов приведены на рис,13.

Рис.13. График времени выполнения разработанного параллельного алгоритма решения транспортной задачи в кластерного пакета после и до применения алгоритмов управления очередями

По оси абсцисс указано число процессов. Из графиков видно, что имеется незначительнь прирост производительности при запуске программы в среде MPI/MPICH_NEW. Однако, при ув яичении числа процессов от 20 до 40 производительность, увеличивается в 1,24 раз, для матриц размерности 1000x1000. Результаты приведенных экспериментов показывают, что среднее вреа выполнения параллельного алгоритма, для решения транспортной задачи на MPI/MPICH_NE\ / меньше (по крайней мере, на 17,74%), по сравнению, с МР1_МР1СН . Согласно полученным р зультатам, ускорение при небольших размерностях задачи значительно меньше 0,5. Это означает что алгоритм неэффективно работает при небольших размерностях задачи. Однако, для болыш: размерностей получается значительный выигрыш — до 130% при нахождении опорного плана до 150% при нахождении оптимального решения транспортной задачи. Погрешность теоретич: ской оценки времени выполнения параллельного алгоритма не превышает 15% .Таким образо; : при увеличении размерности матриц соотношение операций пересылок и полезных операций су щественно уменьшается.

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

Заключение

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

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

2. Разработаны стохастический подход к оценке управления очередями заданий, с использов нием Марковских процессов, и модель кластера МР1/МР1СН_ЫЕ\¥ на основе семантическс сети для управления очередями заданий при организации параллельных вычислений I

кластере, что позволяет устранять проблемы старвации (зависания) заданий, требующих большого количества ресурсов, и определять параметры планировщика Maui; обеспечивает эффективное использование свободных вычислительных ядер всех узлов кластера. Прове денное экспериментальное исследование, предложенной модели кластера MPI/MPICH, для управления очередями заданий в планировщике Maui показало, что при увеличении числа ядер от 30 до 40 производительность увеличивается в 1,37 раз, при расчете матрицы размерности 1000x1000. Проведена сравнительная характеристика времени ожидания заданий при модельном и реальном экспериментах. Экспериментальная проверка установила, что погрешность, полученная при использовании модели управления очередями заданий, для параллельного алгоритма решения транспортной задачи, не превышает 8,87% Разработаны алгоритмы обслуживания очередями заданий, при параллельных вычислениях, в кластерных вычислительных системах: алгоритм распределения ресурсов между процессами и алгоритм управления порядком запуска заданий, которые позволяют значительно снизить ресурсы в ходе работы планировщика за счёт применения специального алгоритма планирования запуска заданий и снизить расход процессорного времени при преждевременной остановке заданий за счёт постоянной корректировки резервирования ресурсов и др. Испытания эффективности модели и алгоритмов управления очередями заданий, на кластерном пакете MPI/MPICH и на улучшенном кластерном пакете MPI/MPICH_NEW, содержащем модель и алгоритм управления очередями заданий, на основе транспортной задачи, показали, что при увеличении числа процессов от 20 до 40, производительность увеличивается в 1,24 раз для размерности матрицы 1000x1000,а на основе задачи нахождения минимального остовного дерева показали, что при увеличении числа процессов от 20 до 60, производительность увеличивается в 1,29 раз при количестве вершин равном 10000. Результаты проведенных экспериментов показали, что среднее время выполнения параллельного алгоритма решения транспортной задачи на MPI/MP1CH NEW меньше (по крайней мере, на 17,74%), а нахождения минимального остовного дерева на MPI/MP1CH NEW меньше (по крайней мере, на 15,65%) по сравнению с MPI/MPICH.

Разработаны параллельные алгоритмы и их теоретические оценки нахождения минимального остовного дерева, на основе метода Борувки; опорного плана в транспортной задаче, на основе метода Фогеля; оптимального решения транспортной задачи, на основе метода потенциала, для проверки предложенных алгоритмов управления очередями заданий в кластерных системах и многопроцессорной среде, позволяющих достигать значительной величины ускорения, в том числе и при использовании нескольких тысяч процессоров. Теоретически показано, что зависимость времени поиска штрафа, по методу Фогеля, от размерности задачи, близка к линейной. При большой размерности задачи от ш=500,получаем увеличение времени поиска штрафа. При увеличении количества узлов от 1 до 7, время поиска штрафа, сокращается в 6 раз. Дальнейшее увеличение количества узлов не эффективно - при изменении от 7 до 20, получается только двукратный выигрыш производительности в 12 раз. Дальнейшее увеличение количества узлов приводит к увеличению затрат времени. Получена теоретическая оценка вычислительной сложности параллельного алгоритма ,на основе метода Фогеля, которая составляет 0(т2). На основе данной оценки показано, что сокращение времени выполнения параллельного алгоритма для задач размерности ш=500, при количестве узлов q=20, примерно в 2 раза меньше, чем при q= 10.Далее время расчета сокращается, не пропорционально количеству узлов. Это вызвано возрастанием количества пересылок между вычислительными узлами; время передачи данных (время пересылки) в кластерной локальной сети в 500 раз меньше, чем время передачи данных в GRID сети. Получена теоретическая оценка вычислительной сложности параллельного алгоритма нахождения минимального остовного дерева, на основе метода Борувки, в кластерных системах, 2

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

разработанных параллельных алгоритмов для решения транспортной задачи и задачи на ждения минимального остовного дерева, при проверки предложенных алгоритмов управл ния очередями. Максимальное ускорение разработанного параллельного алгоритма, на о нове метода Борувки, составляет 1,32 раз, по отношению к известному, параллельному алг ритму Прима, ускорение которого составляет 1,29 раз. Кроме этого, для больших размерн сгей транспортных задач(например размерность матрицы 1000x1000),получается знач тельный выигрыш вычислений до 130%, при поиске опорного плана, и до 150% , при нах ждения оптимального решения транспортной задачи. Проведено сравнение эксперимента! ного и теоретического времени работы параллельного алгоритма нахождения опорного пл на транспортной задачи ,которое установило, что погрешность определения времени выпо нения параллельного алгоритма поиска опорного плана, не превышает 15% .

6. Разработан комплекс программ для исследования алгоритмов управления очередями зад ний в кластерных системах. А также, разработаны параллельные программы для решен! транспортной задачи и задачи нахождения минимального остовного дерева на кластернь системах, с помощью которых проведена проверка эффективности предложенной моде; и алгоритмов управления очередями заданий, в кластерных системах, реализация которЕ подтвердила их эффективность. Полученные теоретические и экспериментальные результаты позволяют сделать вывод о до тижении более высоких показателей эффективности производительности вычислений за сч распараллеливания вычислений, обеспечения ускорения решения задач и уменьшения време! ожидания заданий в очереди в кластерных системах.

Основные положения диссертации изложены в 20 работах, из них 8 работ в изданиях, входящих в перечень ВАК РФ.

I .Работы, опубликованные в изданиях из перечня ВАК РФ:

1. Аль-хулайди A.A. Программные пакеты, обеспечивающие параллельные вычислен! A.A. Аль-хулайди // Вестник ДГТУ. -2010. -Т.10,№1(44).- С. 28-35.

2. Аль-хулайди A.A. Анализ существующих пакетов в кластерных сетях/ А.А Аль-хулайд H.H. Садовой //Вестник ДГТУ. -2010. -Т. 10,№3(46).- С. 303-310.

3. Аль-хулайди A.A. Разработка алгоритмов управления заданиями при организаций паре лельных вычислений в кластерных вычислительных системах/А.А. Аль-хулайди, Ю. Чернышев // Вестник ДГТУ. -2011. -Т.11,№5(56)-С.715-722.

4. Аль-хулайди A.A. Экспериментальная и теоретическая оценки параллельных алгоритм нахождения минимального остовного дерева на кластерных системах/ A.A. Аль-хулай; Ю.О. Чернышев // Известия ЮФУ. Технические науки. Тематический выпуск. - Таганр< Изд-во ТТИ ЮФУ, 2011, №7 (120). - 258 е., С. 80-87.

5. Аль-хулайди A.A. Разработка параллельного алгоритма построения опорного плана Tpai портной задачи / A.A. Аль-хулайди // Наука и образование (МГТУ им. Н.Э. Баумана) 2011. -№5. - № гос. Регистрации 0421 Ю0025.[ электронный журнал]: - Режим достуг hUp://technomag.edu.ru/doc/182661 html

6. Аль-хулайди A.A. Разработка нового стохастического метода управления очередями за/ ний с использованием Марковских процессов для параллельных вычислений на класте) A.A. Аль-хулайди // Инженерный вестник Дона [Электронный ресурс]: Электронный на> но-шшовационный журнал. - 2011. - №1. - № гос. регистрации0421100096-Режим дост па: http:// http://ivdon.ru/magazine/latest/nly2011/332/

7. Аль-хулайди A.A. Разработка параллельного алгоритма нахождения оптимального реи ния транспортной задачи для выполнения на кластере/ A.A. Аль-хулайди, Ю.О. Черныш // Инженерный вестник Дона . Электронный научно-инновационный журнал, 2011. - №2. № гос. регистрации0421100096. [Электронный журнал]: - Режим достуг http.V/i vdon.ni/magazine/latest/n2y2011 /445/

8. Аль-хулайди Абдулмаджид Ахмед Галеб, Распределенные вычисления (Кластерные в числения) с использованием пакета параллельного программирования МР1//современн наукоемкие технологии - 2010. - № 4 - С. 82-83.

П. Свидетельства о регистрации программ на ЭВМ

9. Свидетельство о государственной регистрации программы для ЭВМ № 2011615951. Программное средство для исследования алгоритмов управления очередями заданий в кластерных системах/ Аль-хулайди А.А. - Зарег. в Реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам (Роспатент) от 29 июля 2011 г.

10. Свидетельство о государственной регистрации программы для ЭВМ № 2011615889. Параллельная программа для нахождения минимального остовного дерева на кластерных системах / Аль-хулайди А.А.,Чернышев Ю.О. -Зарег. в Реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам (Роспатент) от 27 июля 2011г.

11. Свидетельство о государственной регистрации программы для ЭВМ № 2011615890. Параллельная программа для решения транспортной задачи на кластерных системах / Аль-хулайди А.А., Чернышев Ю.О. -Зарег. в Реестре программ дня ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам (Роспатент) от 27 июля 2011 г.

Ш. Публикации на английском языке

12. Al-khulaidi A. A., Development of models of queue task in parallel computations in the cluster computing system/ A. A. Al-khulaidi //Congress information System and Technologies [IS&IT'll], 2-9 September, Divnomorskoe, Russia.-Moscow.: Physmathlit, 2011,Vol. 4. -P.3-9.

13. Al-khulaidi A. A. Theoretical estimation determines the optimal amount node cluster system through finding reference plan transportation problem/ A. A. Al-khulaidi, Y. O. Chernyshev //Congress information System and Technologies [IS&IT'll], 2-9 September, Divnomorskoe, Russia. -Moscow.: Physmathlit, 2011,Vol.4. -P.9-17.

14. Al-khulaidi A. A. Algorithm development of resource allocation between processes for parallel systems/A. A. Al-khulaidi //Современные проблемы многоуровневого образования: сб. Tp.VI междунар. науч.-метод.симпозиум/ДГТУ.-Ростов н/Д,2011.-С.234 -237.

15. Al-khulaidi Abdulmajed Ahmed Parallel computing problems while using MPI / MPICH cluster package// Современные проблемы многоуровневого образования: сб. тр. VI междунар. науч. -метод.симпозиума/-ДГТУ,- Ростов н/Д: Издательский центр ДГТУ,2011. - С.230 - 234.

IV. Публикации в других изданиях

16. Аль-хулайди А.А., Использование метода формульного анализа масштабируемости в кластерных сетях/ А.А. Аль-хулайди // Математические методы в технике и технологиях-ММТТ-23: сб.тр. XXIII Междунар. науч. конф/ СГТУ.-Саратов, 2010. -Т.9. -С.173-174.

17. Аль-хулайди, А. А., Разработка алгоритма управления порядком запуска заданий для параллельной обработки / А. А. Аль-хулайди // Инновация, экология и ресурсосберегающие технологии на предприятиях машиностроения, авиастроения, транспорта и сельского хозяйства : Т. IX Международной научно-технической конференции «ИнЭРТ-2010», 6-8 окт. /ДГТУ. —Ростов н/Д, 2010. -С. 426-433.

18. Аль-хулайди А.А., Разбиение кластерного пакета MPI/MPICH на классы функций / А. А. Аль-хулайди // Российская Академия Естествознания: Научный электронный архив академии естествознания (Свидетельства от российской Академия Естествознания)-2010. [Электронный режим]. -Режим доступа URL:http://www,econf.rae.ru/pdf/2010/05/287e03dbld.pdf

19. Аль-хулайди Абдулмаджид Ахмед. Реализация функций кластерного пакета MPI/MPICH / Абдулмаджид Ахмед Аль-хулайди // Российская Академия Естествознания: Научный электронный архив академии естествознания (Свидетельства от российской Академия Естест-вознакия}-2011 .[Электронный режим].-Режим доступа URL:http://econf.rae.ru/pdf/2011/08/525.pdf

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

и синтезе технологических и программно-телекоммуникационных систем: Сб.тр. XVI ждунар. науч. конф. - Воронеж: Научная книга,2011 ~Вып.16. -С.304-307.

Личный вклад автора в работах, написанных в соавторстве. В работах, опубликованн в соавторстве, относящихся к перечню ВАК РФ, Аль-хулайди A.A. принадлежат следующие ] зультаты: в [2] проведен анализ существующих кластерных систем обеспечивающие паралле: ных вычислений; в работе [3] разработаны алгоритмы управления очередями заданиями в к. стерных системах; в работе [4] проведена .экспериментальная и теоретическая оценки паралле: ных алгоритмов нахождения минимального остовного дерева на кластерных системах; в работе предложен параллельной алгоритм нахождения оптимального решения транспортной задачи i выполнения на кластере. В работах, опубликованных в других изданиях в соавторстве, А. хулайди A.A. принадлежат следующие результаты; в работе [13] получены теоретические оцен оптимального количества вычислительных узлов кластерных систем, общего времени выпол! ния параллельных алгоритмов решения транспортной задачи на кластере; в[10] -свидетельство отраслевой регистрации разработки: параллельная программа для нахождения минимального < товного дерева; в [1 ^-свидетельство об отраслевой регистрации разработки: параллельная п] грамма для решения транспортной задачи на кластере.

Аспирант Аль-хулайди A.A.

Тип.ТТИ ЮФУ Заказ №-3'^ТИр./^экз.

СПИСОК ИСПОЛЬЗОВАННЫХ СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ, МОДЕЛЕЙ И АЛГОРИТМОВ УПРАВЛЕНИЯ ОЧЕРЕДЯМИ ЗАДАНИЙ И ПАКЕТОВ, ОБЕСПЕЧИВАЮЩИХ ПАРАЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ В КЛАСТЕРНЫХ СИСТЕМАХ.

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

1.1.1. Метод FCFS (первый пришел, первый обслужен).

1.1.2 Метод Backfill (обратного заполнения).

1.1.3. Метод SJF (краткосрочного планирования).

1.2. Метод Gang scheduling (комплектного планирования).

1.3. Адаптивный метод управления потоком решения заданий в параллельной вычислительной среде.

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

1.4.1. Традиционный алгоритм FIFO.

1.4.2. Алгоритм Priority Queing (приоритетного обслуживания).

1.4.3. Алгоритм WQ (взвешенных очередей).

1.4.4. Алгоритм WFQ (взвешенного справедливого обслуживания).

1.5. Распределённые вычисления (кластерные вычисления) с использованием пакета параллельного программирования MPI.

1.6. Анализ существующих программных пакетов в кластерных системах.

1.6.1. Кластеры высокой доступности.

1.6.2. Кластеры распределения нагрузки.

1.6.3. Вычислительные кластеры.

1.7. Анализ программного обеспечения и средства его установки на кластер.

1.8. Кластерные системы управления пакетной обработкой (СПО).

1.9. Интегрированные программные средства для кластеров.

1.10. Проблемы параллельных вычислений, возникающие при использовании кластерного пакета MPI/MPICH.

1.11. Выводы.

ГЛАВА 2. РАЗРАБОТКА МОДЕЛИ УПРАВЛЕНИЯ ОЧЕРЕДЯМИ НА ОСНОВЕ СЕМАНТИЧЕСКОЙ СЕТИ И СТОХАСТИЧЕСКИЙ ПОДХОД К ОЦЕНКЕ УПРАВЛЕНИЯ ОЧЕРЕДЯМИ ЗАДАНИЙ В КЛАСТЕРНЫХ СИСТЕМАХ.

2.1. Модель кластера MPI/MPICH на основе семантической сети в планировщике Maui.

2.2. Управление очередями в кластерных системах.

2.2.1.Выбор критериев оценки алгоритмов управления очередями.

2.2.2.Схема организации вычислений.

2.2.3.Аппаратное обеспечение.

2.2.4.Менеджер ресурсов.

2.2.5. Планировщик задач к менеджерам ресурсов, работающий по методу backfill.

2.2.6.Конкретизация положений теории очередей для кластерной системы.

2.3. Основные положения теории Марковских процессов и стохастический подход к оценке управления очередями заданий.

2.4. Выводы.

ГАЛАВА 3. РАЗРАБОТКА АЛГОРИТМОВ УПРАВЛЕНИЯ ОЧЕРЕДЯМИ ЗАДАНИЙ И ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ДЛЯ ПРОВЕРКИ ЭФФЕКТИВНОСТИ ПРЕДЛОЖЕННЫХ АЛГОРИТМОВ НА КЛАСТЕРНЫХ

СИСТЕМАХ.

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

3.1.1. Алгоритм распределения ресурсов между процессами.

3.1.2 Алгоритм управления запуском заданий для кластерных систем.

4.2.2. Испытание и результаты экспериментальной проверки эффективности предложенной модели на основе транспортной задачи.

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

4.3.1. Алгоритм управления на основе параллельного алгоритма нахождения минимального остовного дерева по методу Борувки.

4.3.2. Сравнительная характеристика экспериментальной и теоретической оценки эффективности параллельных алгоритмов нахождения минимального остовного дерева.

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

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

4.4.2. Сравнение экспериментального и теоретического времени работы параллельного алгоритма нахождения опорного плана транспортной задачи на основе метода Фогеля.

4.4.3. Экспериментальная проверка эффективности параллельного алгоритма нахождения оптимального решения транспортной задачи на основе метода потенциалов.

4.5. Интерфейс программных стендов и работа с ними.

4.6.Вывод ы.

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

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

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

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

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

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

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

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

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

4.6.Выводы

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

2. Проведены экспериментальные исследования, разработанной модели и алгоритмов управления очередями заданий, на основе транспортной задачи. Испытания эффективности модели и алгоритмов управления очередями заданий на кластерном пакете МР1/МР1СН и на улучшенном кластерном пакете МР1/МР1СНКЕ\¥, содержащем модель и алгоритм управления очередями заданий, на основе транспортной задачи показали, что при увеличении числа процессов от 20 до 40, производительность увеличивается в 1,24 раз, для размерности матрицы 1000x1 ООО,а на основе задачи нахождения минимального остовного дерева показали, что при увеличении числа процессов от 20 до 60, производительность увеличивается в 1,29 раз, при количестве вершин, равном 10000. Результаты проведенных экспериментов показали, что среднее время выполнения параллельного алгоритма решения транспортной задачи на МР1/МР1СН1Ч[Е\¥ меньше (по крайней мере, на 17,74%) нахождения минимального остовного дерева, на МР1/МР1СНТч[Е\У меньше (по крайней мере, на 15,65% ) по сравнению, с МР1/МР1СН. Это позволяет в совокупности получить более высокие показатели эффективности параллельных вычислений, обеспечить ускорение решения задач в кластерных системах и уменьшить время ожидания заданий в очереди.

3. Проведенное экспериментальное исследование, предложенной модели кластера МР1/МР1СН, для управления очередями заданий в

142 планировщике Maui показало, что при увеличении числа ядер от 30 до 40, производительность увеличивается в 1,37 раз при расчете матрицы размерности 1000x1000. Проведена сравнительная характеристика времени ожидания заданий, при модельном и реальном экспериментах. Экспериментальная проверка установила, что погрешность, полученная при использовании модели управления очередями заданий, для параллельного алгоритма решения транспортной задачи, не превышает 8,87% .

4. Проведена сравнительная характеристика экспериментальной и теоретической оценок параллельных алгоритмов, для решения транспортной задачи и задачи нахождения минимального остовного дерева, при проверки предложенных алгоритмов управления очередями. Экспериментальная проверка показала, что максимальное ускорение разработанного параллельного алгоритма, на основе метода Борувки, составляет 1,32 раз, по отношению к известному параллельному алгоритму Прима, ускорение которого составляет 1,29 раз. Кроме этого, эксперимент показал, что для больших размерностей транспортных задач(например ,размерность матрицы 1000x1000) получается значительный выигрыш вычислений: до 130%, при поиске опорного плана, и до 150%, при нахождении оптимального решения транспортной задачи. Проведено сравнение экспериментального и теоретического времени работы параллельного алгоритма, нахождения опорного плана транспортной задачи ,которое установило, что погрешность определения времени выполнения параллельного алгоритма поиска опорного плана не превышает 15% .

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

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

Разработаны алгоритмы обслуживания очередями заданий, при параллельных вычислениях, в кластерных вычислительных системах: алгоритм распределения ресурсов между процессами и алгоритм управления порядком запуска заданий, которые позволяют значительно снизить ресурсы в ходе работы планировщика за счёт применения специального алгоритма планирования запуска заданий и снизить расход процессорного времени при преждевременной остановке заданий за счёт постоянной корректировки резервирования ресурсов и др. Испытания эффективности модели и алгоритмов управления очередями заданий, на кластерном пакете МР1/МР1СН и на улучшенном кластерном пакете

МР1/МР1СН1чПЕ\У, содержащем модель и алгоритм управления очередями заданий, на основе транспортной задачи, показали, что при увеличении числа процессов от 20 до 40, производительность увеличивается в 1,24 раз для размерности матрицы 1000x1 ООО,а на основе задачи нахождения минимального остовного дерева показали, что при увеличении числа процессов от 20 до 60, производительность увеличивается в 1,29 раз при количестве вершин равном 10000.

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

МР1/МР1СНКЕ\¥ меньше (по крайней мере, на 17,74%), а нахождения минимального остовного дерева на МР1/МР1СНЫЕ\¥ меньше (по крайней мере, на 15,65% ) по сравнению с МР1/МР1СН.

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

146 показано, что зависимость времени поиска штрафа, по методу Фогеля, от размерности задачи, близка к линейной. При большой размерности задачи от т=500,получаем увеличение времени поиска штрафа. При увеличении количества узлов от 1 до 7, время поиска штрафа, сокращается в 6 раз. Дальнейшее увеличение количества узлов не эффективно - при изменении от 7 до 20, получается только двукратный выигрыш производительности в 12 раз. Дальнейшее увеличение количества узлов приводит к увеличению затрат времени.

5. Получена теоретическая оценка вычислительной сложности параллельного алгоритма ,на основе метода Фогеля, которая составляет О(w2)- На основе данной оценки показано, что сокращение времени выполнения параллельного алгоритма для задач размерности т=500, при количестве узлов q=20, примерно в 2 раза меньше, чем при q= 10.Далее время расчета сокращается, не пропорционально количеству узлов. Это вызвано возрастанием количества пересылок между вычислительными узлами; время передачи данных (время пересылки) в кластерной локальной сети в 500 раз меньше, чем время передачи данных в GRID сети. Получена теоретическая оценка вычислительной сложности параллельного алгоритма нахождения минимального остовного дерева, на основе метода Борувки, в кластерных системах, 2 которая составляет, 0(").

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

Приведены сравнительные характеристики экспериментальных и полученных автором теоретических оценок, разработанных параллельных алгоритмов для решения транспортной задачи и задачи нахождения минимального остовного дерева, при проверки предложенных алгоритмов управления очередями. Максимальное ускорение разработанного параллельного алгоритма, на основе метода Борувки, составляет 1,32 раз, по отношению к известному, параллельному алгоритму Прима, ускорение которого составляет 1,29 раз. Кроме этого, для больших размерностей транспортных задач(например ,размерность матрицы 1000x1 ООО),получается значительный выигрыш вычислений до 130%, при поиске опорного плана, и до 150% , при нахождения оптимального решения транспортной задачи. Проведено сравнение экспериментального и теоретического времени работы параллельного алгоритма нахождения опорного плана транспортной задачи , которое установило, что погрешность определения времени выполнения параллельного алгоритма поиска опорного плана, не превышает 15% .

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

1. Norros I. A storage model with self-similar input /1. Norros //Queueing Systems AndTheir Applications. 1994. -N16. -P.369-387.

2. Kelly P.P. Analysis in Queueing Systems: Brownian models, cut constraints and resource pooling/ Kelly P.P. // Queueing Systems., 1993. N13. - P. 47-86.

3. Limic V. On the behavior of LIFO preemptive resume queues in Heavytraffic/ V. Limic // Elect. Comm. in Probab. 1999. - N4. -P. 13-27.

4. Kamp A. v., S. Schuster. Metatool 5.0: fast and flexible elementary modes analysis/A. v. Kamp , S. Schuster//Bioinformatics. 2006. -N22. -P. 1930-1931.

5. Chen L. Parallel simulation by multi-instruction, longest-path Algorithms/ L. Chen // Queueing Systems. 1997. -N 27. -P. 37-54.

6. Karatza H. D. A Simulation Model of Backfilling and I/O Scheduling in a Partitionable Parallel System/ Karatza H. D. //Proceedings of Winter Simulation Conference ACM, IEEE, SCS, Orlando,Florida, December,Orlando ,- 2000. -P. 496-505.

7. Flynn M. Some Computer Organisations and Their Effectiveness/ M. Flynn // IEEE Transactions on Computers. -1972. -N 9. -P.948-960.

8. Wang P., Dual-Direction Backfilling Algorithm for Job Scheduling/P. Wang, Xu Liu, Dan Meng, Jianfeng Zhan, Bibo Tu //HPC Asia conference. Kaohsiung, Taiwan. -2009. P.88-102.

9. Ward W., Scheduling Jobs on Parallel Systems Using a Relaxed Backfill Strategy/ W. Ward, L. Carrie //8th International Workshop on Job Scheduling Strategies for Parallel Processing, Spinger-Verlag. -2002. LNCS 2537. - P.88-102.

10. Hockney R. Parallel Computers: Architecture and Performance/ RHockney // Proc. Of Int. Conf. Parallel Computing. 1986. -N 85. - P.33-69.

11. Lifka D. The ANL/IBM SP scheduling system. In Job Scheduling Strategies for Parallel Processing / D. Lifka //Springer-Verlag, Lect. Notes Comput. -1995.-N. 949.-P. 295-303.

12. Mu'alem A. W Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling/ A. W. Mu'alem , D. G. Feitelson // IEEE Trans. Parallel Distributed Syst.-2001.-N12(6). -P. 529-543.

13. Maui scheduler. Cluster Resources Электронный pecypc.-2011. Режим доступа:http://www.supercluster.org/maui//, свободный.

14. Streit A. On Job Scheduling for HPC-Clusters and the Scheduler. /А. Streit //TR-00101, PC2 Paderborn Center for Parallel Computing, PaderbornUniversity. -2001. Электронный ресурс. - Режим доступа http://www.fz-iuelich.de/isc/vsgc/pub/strcit2001-QJS.pdf

15. Wiseman Y. Paired Gang Scheduling/ Y. Wiseman , D.G. Feitelson // Proc. Jerusalem Parallel Distributed Processing Symp., Nov. Jerusalem . -2001. -P. 218-222.

16. B. B Zhou .: Gang Scheduling with a Queue for Large Jobs/ Zhou B. B., Brent R. P.// IEEE International Parallel and Distributed ProcessingSymposium. -(2001).-N12.-P. 225-233.

17. Frachtenberg E. J.: Flexible CoScheduling: Mitigating Load Imbalance and Improvi Utilization of Heterogeneous Resources/ Frachtenberg E., Feitelson D.G. // 17th International Parallel andDistributed Processing Symposium. -2003.-39: 345-456.

18. Hockney R. Classification and Evaluation of Parallel Computer Systems /Hockney R.//lecture Notes in Computer Science. 1987.- N 295. - P. 13-25.

19. Chapin S.J. et all: Benchmarks and Standards for the Evaluation of Parallel Job Schedulers/ S.J. Chapin // Job Scheduling Strategiesfor Parallel Processing. -1999.-V.1234.-P. 67-90.

20. Goes L. F.: Proposal and Development of Reconfigurable Parallel Job Scheduling Algorithm/ L. F. Goes, W. Martins// Master' s Thesis. Belo Horizonte, Brazil(in Portuguese). 2004. -V.29.P. 345-456.

21. Low, Y.H. et al., Survey of Languages and Runtime Libraries for Parallel Discrete-Event Simulation//IEEEComputer Simulation. -1999.-N3. -P. 170-186.

22. Anderson, Cobb E. An experiment in public-resource computing / Anderson, Cobb E. // Comm. of the ACM. -2002. V. 45, No. 11. - P. 56-61.

23. Zhou B. B. An Efficient Resource Allocation Scheme for Gang Scheduling/ B.

24. B. Zhou, P. Mackerras, Johnson C. W., Walsh, D.//lst IEEE Computer Society International Workshop on Cluster Computing. Toqi 1999. - P. 18-194.

25. Martin R.D. Robust estimation via stochastic approximation/ R.D. Martin &

26. Анализ алгоритмов обслуживания очередей в сетях с поддержкой «Качества обслуживания» (QoS) / Е.Б.Фишман // Качество. Инновации. Образование. -2006. -№6. С.63- 71.

27. Федодеев Д. , Алгоритмы управления очередями / Д. Федодеев // Журнал сетевых решений/LAN. 2007. - Т. 13 (137). - С.26-31.

28. Климов, Г.П. Приоритетные системы обслуживания с ориентацией/ Г.П. Климов, Г.К.Мишкой.-М.: МГУ, 1979.-222 с.

29. Столлингс В. Современные компьютерные сети: Энциклопедия. - 2-е изд- СПб.: Питер. - 2003. - 782 с.

30. Таненбаум Э. Компьютерные сети. Классика computer science. 4-е / Э. Таненбаум. -4-е изд. -СПБ. Литер. 2008. - 992 с.

31. Меликов А.З. Приоритетное обслуживание в узлах коммутации сетей АТМ / А.З. Меликов, В.Ш. Фейзиев // Автоматика и вычислительная техника. -Харьков, 2005. Т.З. - С.79.

32. Kroner Н. Priority management in ATM switching nodes / H. Kroner, G. Hebuterne , P. Boyer, A. Gravey // IEEE J. Select. Areas Commun. 1991. -Vol.9, No.3.-P.418-427.

33. Антонов А. В. Оценка эффективности параллельных алгоритмов/ А. В. Антонов // Антикризисное управление в России в современных условиях: материалы VI Всерос. науч.-практ. Молодеж. конф. М.: Изд-во МГТУ им. Н. Э. Баумана, 2004. - С. 21- 22.

34. Гугель Ю.В. Характеристики параметров "Качество обслуживания" опорной инфраструктуры научно-образовательной сети / Ю.В. Гугель // Информатизация образования и науки. 2009. - Вып. 4. - С. 66-75.

35. Вегешна Ш. Качество обслуживания в сетях IP/ Ш. Вегешна. М.: Изд-во. Вильяме, 2003. -368с.

36. Коваленко В.Н. Методы и алгоритмы управления параллельными заданиями в гриде с ресурсами в форме кластеров/ В.Н. Коваленко, Д.А. Семячкин // Вестник Южного научного центра РАН. -2008. № 3(4). -С. 23-34.

37. Таненбаум Э. Компьютерные сети. Классика computer science/ Э. Таненбаум. 3-е изд. - СПБ.: Питер, 2002. - 829 с.

38. Аль-хулайди А. А. Распределенные вычисления (Кластерные вычисления) с использованием пакета параллельного программирования МР1/ А. А. Аль-хулайди //Современные наукоемкие технологии. (Электронный журнал). -2010.-№ 4-С. 82-83.

39. Аль-хулайди A.A. Разбиение кластерного пакета MPI/MPICH на классыфункций / А. А. Аль-хулайди // Российская Академия Естествознания

40. Научный электронный архив академии естествознания (Свидетельства от153

41. Кутепов В.П. Организация параллельных вычислений на системах / В.П. Кутепов. М.: Изд-во МЭИ, 1988. - 64 с.

42. Ластовецкий A.JI. Технологии параллельного программирования шрС Электронный ресурс. -Режим доступа: http://vvww.parallel.m/techympc/mpC-rus.html, свободный.

43. Johnston, W. Realtime Widely Distributed Instrumentation Systems. In Foster, I. and Kesselman, C. eds. //The Grid: Blueprint for a New Computing Infrastructure, Morgan Kaufmann. -1999. -P. 75-103.

44. Nick J.M. S/390 Cluster Technology: Parallel Sysplex/ J.M Nick , B.B. Moore //IBM Systems Journal. -1997. -36 (2). -P. 172-201.

45. Hockney R. Parallel Computers: Architecture and Performance/ R. Hockney // Proc. of Int. Conf. Parallel Computing'85. 1986. -P.33-69.

46. Livny M. High-Throughput Resource Management/ M. Livny, C. Kesselman //The Grid: Blueprint for a New Computing Infrastructure, Morgan Kaufmann. -1999.-P. 311-337.

47. Casanova H. A Network Server for Solving Computational Science Problems./ H. Casanova , J. Dongarra // International Journal of Supercomputer Applications and High Performance Computing. 1997. -N.ll (3). -P. 212223.

48. Foster I. Globus: A Metacomputing Infrastructure Toolkit /1. Foster., Kesselman // Intl J. Supercomputer Applications.-1997.-N.11.-P.115-128.

49. Robin Calkin. Portable programming with the parmacs message-passing library / Robin Calkin, Rolf Hempel, Hans-Christian Hoppe, Peter Wypior//Parallel Computing. -1994. 20(4). -P.615-632.

50. Maui scheduler: Электронный ресурс. Режим доступа: http://www.supercluster.org/maui Last Modified on 09/06/2003, last accessed in April 2009, свободный.

51. Foster I. Software Infrastructure for the I-WAY High Performance Distributed Computing Experiment /1. Foster, J. Geisler, W. Nickless, W.Smith// Proc. 5th IEEE Symposium on High Performance Distributed Computing. 1997. -P. 562-571.

52. Владимиров Д. Кластерная система Condor/ Д. Владимиров // Открытые системы — 2000. -№7-8. -С.20-26.

53. Ahmar Abbas. Grid Computing/ Ahmar Abbas //Charles River Media. 2004. -P.110-117.

54. Michael J. Brim How to install an OSCAR cluster / J. Brim Michael // The Open Cluster Group. -2001 Электронный ресурс. Режим доступа: http://www.csm.ornl.gov/oscar/papers.html, свободный.

55. Joseph D. Sloan, High Performance Linux Clusters With Oscar, Rocks, Open Mosix & Mpi/ D. Sloan Joseph // Fast results on terabytes of data. 2004. -P.368.

56. Robert L. Grossman, Compute and storage clouds using wide area high performance networks/ Robert L. Grossman, Yunhong Gu, Michal Sabala, Wanzhi Zhang //Future Generation Сотр. Syst. 2009 . -N.25(2). -P. 179-183.

57. Wunderlich, J.T. Functional verification of SMP, MPP, and vector-register supercomputers through controlled randomness/ J.T. Wunderlich//Computer Engineering Program . -2003. -P.l 17-122.

58. Buyya Rajkumar Buyya. High Performance Cluster Computing: Architecturesand Systems// Prentice Hall PTR. -NJ, (USA), 1999. V. 1. -P.227-233.

59. Al-khulaidi Abdulmajed Ahmed Parallel computing problems while using MPI / MPICH cluster package// Современные проблемы многоуровневого образования: сб. тр. VI междунар. науч. -метод.симпозиума/-ДГТУ-Ростов н/Д: Издательский центр ДГТУ,2011.

60. Blumofe R. Scheduling multithreaded computations by work stealing/ R. Blumofe, C. Leiserson // 35th Annual IEEE Conf. on Foundations of Computer Science. FOCS'94. Santa Fe, (New Mexico). -1994. -P. 356-368.

61. Casavant T. A taxonomy of scheduling in generalpurpose distributed computing systems/ T. Casavant, J. Kuhl // IEEE Trans. О Software Engineering. -1988. -V. 14.-No 2.-P. 141-154.

62. Feitelson D.G. A Survey о Scheduling in Multiprogrammed Parallel Systems/ D.G. Feitelson // Research Report RC 19790 (87657). IBM T. J. Watson ResearchCenter. -1994. -P. 171.

63. Streit A. On Job Scheduling for HPC-Clusters and the dynP Scheduler / A. Streit // Lect. Notes Comput.Sci Berlin,- 2001. -V. 2228. - P. 58-67.

64. Brando T. J. Comparing DCE and CORBA / T. J. Brando // Technical Report MP,MITRE. -1995. -P.93-95.

65. Сайт проекта TORQUE. Электронный ресурс. Режим доступа : http://www.clusterresources.com/pages/products/torque-resource-manager.php, свободный.

66. Сайт проекта TORQUE Resource Manager^eKTpoHHbift ресурс.- Режим доступа: http://en.wikipedia.org/ wiki/TORQUE ResourceManager , свободный.

67. Bharucha-Reid А. Т., Elements of the theory of Markov processes and their applications/ A. T. Bharucha-Reid // New York, McGraw-Hill

68. Book Co. (РЖМат, 1961, 4B29 К). -I960,- XI. -1960. -N468. -P. 11-50.

69. Boyer R. H. An integro-differential equation for a Markov process.

70. R. H. Boyer //Industr. and Appl. Math-1959. V7, № 4. - P. 473^186.

71. Clarke A. B. Waiting line process of Markov type / A. B. Clarke // Ann. Math Statistics. 1956. - V. 27, № 2. - P. 452 -459.

72. Udagawa K. Note on a relation between the Markov chain and the birth and death process/ K. Udagawa // J. Operat. Res. Soc. 1арап(РЖМат, 1962, 7B21). 1961. - V. 4, №1.-P. 27-45.

73. Vere-Jones D., Geometric ergodicity in denumerable Markov chains// Quart. J. Math.- 1962,- V.13, №49. P.7-28.

74. Ивченко Г.И., Коваленко И.Н. Теория массового обслуживания/ Г.И. Ивченко, В.А. Каштанов. — М.:Высш. Шк., 1982. — 256 с.

75. Гнеденко Б.Б. Введение в теорию массового обслуживания/ Гнеденко Б.Б., И.Н. Коваленко. — М.: Наука, 1966.-255 с.

76. Сейфулин А.И. Ситуационное моделирование полиграфических процессов:дисс. Канд. Техн. Наук/ А.И. Сейфулин. — М., 2002.

77. Кофман А. Массовое обслуживание. Теория и приложения/ А. Кофман , Р. Крюон — М.:Мир, 1965. — 304 с.

78. Клименок В.И. Теорема Руше в задаче нахождения стационарного распределения квазитеплицевой цепи Маркова / В.И. Клименок // Автоматика и вычислительная техника. 1998. -№1. - С.23-29.

79. Дудин А.Н. Системы массового обслуживания с коррелированными потоками/ А.Н. Дудин, В.И. Клименок Минск: БГУ, 2000. - 175 с.

80. Климов Г.П. Стохастические системы обслуживания/ Г.П. Климов М.: Наука, 1966.-244 с.

81. Кормен Т. Алгоритмы: построение и анализ/ Т. Кормен, Ч. Лейзерсон, Р. РивестМ. :МЦНМО,2001.-960с.

82. Альфред Ахо Структуры данных и алгоритмы/ Ахо Альфред, Э. Джон, Д. Ульман М. - СПб - Киев: Вильяме, 2000 г. - 384 с.

83. Курейчик В.М. Дискретная математика. Ч.З. Оптимизационные задачи на графах/ В.М. Курейчик. Таганрог: Изд-во ТРТУ, 1998. - 296 с.

84. Кормен Т. X. Алгоритмы: построение и анализ/ Т. X. Кормен , Ч. И. Лейзерсон , Р. Л. Ривест, К. Штайн- 2-е изд.— М.: Вильяме, 2005. — 1296 с.

85. Graham. R. L. On the history of the minimum spanning tree problem. / R. L. Graham and P. Hell. // Annals of the History of Computing. 1985. - N 7(1).-P. 43-57.

86. Chung S. Parallel implementation of Boruvka's minimum spanning tree algorithm. / S. Chung, A. Condon // Parallel Processing Symp. (IPPS'96). -1996.-P. 302-315.

87. Chazelle. B. A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity / B. Chazelle// Journal of the ACM. 2000. -N47. - P. 10281047.

88. David R. Karger. A randomized linear-time algorithm to find minimum spanning trees/ David R. Karger, Philip N. Klein, and Robert E. Tarjan // Journal of the ACM. -1995. N.42 (2). -P. 321-328.

89. King V. A simpler minimum spanning tree verification algorithm/ V. King //Algorithmic. -1997. -18. -P. 263-270.

90. Ш.Бурков В.H. Прикладные задачи теории графов / В.Н. Бурков, И.А. Горгидзе, С.Е. Ловецкий Тбилиси: Мецниереба. - 1974. - 234 с.

91. Алексеев А.О. Транспортная задача по критерию времени при ограниченном количестве транспортных средств/ А.О. Алексеев // Математические методы оптимизации и управления в сложных системах /-КГУ. Калинин,- 1984. - с. 60- 65.

92. Математическое моделирование экономических процессов на железнодорожном транспорте / А.Б. Каплан, А.Д. Майданов, A.M. Макарочкин и др. М.: Транспорт. -1984. -256 с.

93. Кузнецов Ю.Н. Математическое программирование / Ю.Н. Кузнецов, В.И. Кузубов, А.Б. Волощенко. М.: Высш. Шк,1976. -352с.

94. Высшая математика: Математическое программирование : Учеб. / A.B. Кузнецов, В.А.Сакович, Н.И. Холод. Минск.: Высш.шк., 1994. - 286 с.

95. Барский А. Б. Параллельное программирование/ А.Б. Барский СПб.: Бином, 2007. - 504 с.

96. Северин А. А. Исследование эффективности реализации численных методов на кластерах персональных ЭВМ/ А. А. Северин Минск, 2005.

97. Хохлюк В. И. Параллельные алгоритмы целочисленной оптимизации/ В. И. Хохлюк. М., 1987. - 224с.

98. Каныгин Т.П., Месхи Б.Ч., Соболь Б.В. Методы оптимизации / Г.И Каныгин., Б.Ч. Месхи , Б.В. Соболь — М.: Феникс, 2009 . — 384 с.

99. Аппроксимация Электронный ресурс. -Режим доступа: http://ru.wikipedia.org/wiki/AппpoкcимaцияПaдe (дата обращения 11.2.2011 г), свободный.

100. Грид Электронный ресурс. http://ru.wikipedia.org/wiki/rpHa (дата обращения 23.03.2011 ), свободный.

101. Аль-хулайди A.A. Использование метода формульного анализа масштабируемости в кластерных сетях/ A.A. Аль-хулайди // Математические методы в технике и технологиях-ММТТ-23: сб.тр. XXIII Междунар. науч. конф/ СГТУ.- Саратов, 2010. -Т.9. -С. 173-174.

102. Аль-хулайди A.A. Разработка алгоритмов управления заданиями при организаций параллельных вычислений в кластерных вычислительных системах/ A.A. Аль-хулайди , Ю.О. Чернышев// Вестник ДГТУ. -2011. -Т.11,№5(56) С.715 - 722.

103. Аль-хулайди A.A. Разработка параллельного алгоритма нахождения оптимального решения транспортной задачи для выполнения на кластере/ A.A. Аль-хулайди, Ю.О. Чернышев // Инженерный вестник Дона .

104. Электронный научно-инновационный журнал, 2011. №2. - № гос.161регистрации0421100096. Электронный журнал.: Режим доступа: http://ivdon.ru/magazine/latest/n2y2011/445/

105. Аль-хулайди Абдулмаджид Ахмед. Реализация функций кластерного пакета MPI/MPICH / Абдулмаджид Ахмед Аль-хулайди // Российская Академия Естествознания: Научный электронный архив академии естествознания (Свидетельства от российской

106. Академия Естествознания) -URL:http://econf.rae.ru/pdf/201 l/08/525.pdf

107. Коваленко В.Н. Метод опережающего планирования для грид/ .Н.Коваленко, Е.И.Коваленко, Д.А.Корягин, Э.З.Любимский // Ордена Ленина институт прикладной математикой имени М.В.Келдыша. Москва. -2005.-33с.

108. Al-khulaidi A. A. Algorithm development of resource allocation between processes for parallel systems/ A. A. Al-khulaidi //Современные проблемы многоуровневого образования: сб. тр. VI междунар. науч. -метод.симп. /ДГТУ- Ростов н/Д,2011. С.234 - 237.