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

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

ХАЧКИНАЕВ ГЕННАДИЙ МЕСРОПОВИЧ

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

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

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

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

Научный руководитель:

Официальные оппоненты:

кандидат технических наук, доцент Букатов Александр Алексеевич

доктор технических наук, профессор Божич Владимир Иванович

кандидат технических наук, доцент Иванченко Александр Николаевич

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

Самарский государственный аэрокосмический университет

Защита состоится « 15_» апреля 2004 г. в часов на заседании

диссертационного совета К.212.208.04 по физико-математическим и техническим наукам в Ростовском государственном университете по адресу: 344090, г. Ростов-на-Дону, пр. Стачки, 200/1, корпус 2, ЮГИНФО РГУ, к. 206.

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

Автореферат разослан

«/3»

2004 г.

Ученый секретарь диссертационного совета

кандидат физико-математических наук

Муратова Г.В.

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

Актуальность темы. Численные методы широко применяются в современных научных исследованиях во многих отраслях науки для решения фундаментальных и прикладных задач. К таким задачам можно отнести задачи численного моделирования природных процессов, анализа экспериментальных данных в реальном времени, распознавание речи и изображений. В частности, на вычислительных ресурсах Центра высокопроизводительных вычислений (ЦВВ) РГУ решаются задачи квантовой механики, квантовой химии, астрофизики (задачи динамики галактик), радиофизики (моделирование газовых разрядов), задачи гидродинамики водоемов и фильтрации грунтовых вод.

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

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

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

РОСЛМЦНОНЛЛЬНАЯ

БИБЛИОТЕКА { СПтр « О» кя

ресурсам, единую политику управления ресурсами и т.д. Проблемам создания и организации таких систем посвящены работы Вл.В. Воеводина и его учеников, В.И.Золотарева, В.Н.Коваленко, Д.Фейтелсона, Е. Смирни и других ученых.

Существующие СПОЗ можно условно разделить на 2 класса:

1. Специализированные СПОЗ - применяются для поддержки конкретных супер-ЭВМ, обычно поставляются вместе с этими супер-ЭВМ.

2. СПОЗ общего назначения - могут применяться для достаточно широкого класса многопроцессорных систем.

Однако существующие СПОЗ обладают рядом недостатков:

1. Некоторые системы рассчитаны на управление однородными вычислительными сетями. В то же время, в состав вычислительных центров обычно входят разнородные системы, образуя гетерогенные вычислительные сети. Примеры таких систем, рассчитанных на планирование однородных систем - DJM, Task Broker, EASY.

2. Даже если система управления ориентирована на работу в гетерогенной вычислительной среде, от пользователя обычно требуется заранее (на этапе передачи задания в систему) определить количество процессоров, которые должны быть выделены заданию и их тип (тип вычислительной системы). Примеры таких систем - OpenPBS, Condor, LSF и т.д. Это не всегда удобно, если задание является переносимым (может выполняться на различных МВС) и масштабируемым (может выполняться на различном числе процессоров).

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

Кроме того, использование стандартных средств и интерфейсов для организации межпроцессорных взаимодействий позволяет создавать переносимые параллельные программы, которые могут выполняться на МВС разных типов с различной архитектурой. Например, реализации библиотеки MPI существуют для подавляющего большинства многопроцессорных систем (включая кластеры рабочих станций), а библиотеки POSIX thread доступны для большинства SMP-систем.

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

4

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

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

1.Провести сравнительный анализ современных систем управления заданиями для МВС, выявить их преимущества и недостатки.

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

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

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

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

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

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

8.Провести исследование характеристик разработанных алгоритмов планирования.

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

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

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

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

4.Результаты исследования эффективности алгоритмов планирования, подтвердившие преимущества разработанных средств по сравнению с другими известными СПОЗ.

Практическая значимость

Практическую значимость работы представляет созданная на базе разработанной архитектуры система управления заданиями TMS (Task Management System). Система позволяет объединить МВС с различной архитектурой и производительностью и использовать их как единый вычислительный комплекс. Система управления предоставляет единообразный интерфейс для пользователей, эффективно распределяет задания по имеющимся вычислительным ресурсам, облегчает администрирование вычислительной сети в целом.

Публикации. По теме диссертации опубликовано 13 печатных работ, в том числе 2 статьи и 11 тезисов докладов на конференциях.

Апробация результатов работы. Результаты работы докладывались и обсуждались на научно-практических конференциях: Международная научно-методическая конференция. "Телематика'2001", Санкт-Петербург, 2001 г.; Всероссийская научная конференция "Научный сервис в сети Интернет", Новороссийск, 2002 г.; XXIX Международная конференция "Информационные технологии в науке, образовании, телекоммуникации, бизнесе", 2002 г.; IX конференция представителей региональных сетей "Relarn-2002", Нижний Новгород, 2002 г.; Международная научно-техническая конференция "СуперЭВМ и многопроцессорные вычислительные системы", Таганрог, 2002 г.; IX Всероссийская научно-методическая конференция "Телематика'2002", Санкт-Петербург, 2002 г.; X Всероссийская научно-методическая конференция

"Телематика'2003", Санкт-Петербург, 2003 г.; Научно-методическая конференция "Современные информационные технологии в образовании: Южный Федеральный округ", Ростов-на-Дону, 2003 г.; Всероссийская научная конференция "Научный сервис в сети Интернет", Новороссийск, 2003 г.; Международная научная конференция "Интеллектуальные и многопроцессорные системы", Таганрог, 2003 г.; I Всероссийская научная конференция "Методы и средства обработки информации", Москва, 2003 г.

Реализация работы и внедрение результатов. Результаты работы использовались при выполнении и составили существенную часть результатов следующих НИР: проект В.0011 ФЦП «Интеграция» «Развитие центра высокопроизводительных вычислений для нужд вузовской и академической науки», № гос. регистрации 01.200.118684; проект № 341 «Исследование и разработка программных средств организации удаленного выполнения программ на гетерогенной вычислительной сети суперкомпьютерного центра Ростовского государственного университета» НТП Минобразования РФ «Государственная поддержка региональной научно-технической политики высшей школы и развитие ее научного потенциала», № гос. регистрации 01.200.118685; проект 1.7.43 «Разработка методов, технологии и специальных программных средств удаленного использования вычислительных ресурсов регионального центра высокопроизводительных вычислений в учебном процессе и научных исследованиях» НОП Минобразования РФ «Научное, научно-методическое, материально-техническое обеспечение развития технологий информационного общества и индустрии образования». Результаты работы внедрены в опытную эксплуатацию в центре высокопроизводительных вычислений РГУ.

Структура и объем. Диссертация состоит из введения, четырех глав, заключения и двух приложений. Основной текст диссертации содержит 158 страниц, 53 рисунка, 1 таблицу. Список литературы насчитывает 119 наименований.

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

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

В первой главе дается аналитический обзор существующих систем управления пакетной обработкой заданий, рассмотрены их ключевые особенности и области применения, отмечены преимущества и недостатки известных систем. Рассматриваются системы Condor, Codine, DQS и OpenPBS. Последняя система является одной из наиболее популярных СПОЗ. Основным недостатком этой системы является недостаточно четкая реализация концепции очередей, слабая поддержка неоднородных вычислительных сетей, а также ошибки в реализации. В частности, система некорректно работает в случае отказа одного или нескольких вычислительных узлов.

Кроме того, в главе рассматриваются различные типы МВС, приводится классификация МВС и описываются используемые технологии параллельного программирования (ГШ). При классификации МВС принято выделять системы с общей памятью (SMP) и распределенной памятью (МРР). Кластерные решения представляют собой более дешевый вариант МРР. Основная технология ПП, используемая в МРР-системах — механизм передачи сообщений. В этом случае все межпроцессорные обмены данными явно описаны в программе как обращения к процедурам отправки и получения сообщений. Для SMP-систем наиболее выгодным является потоковый параллелизм - в этом случае программа состоит из нескольких легковесных процессов (нитей), которые исполняются на различных процессорах, но при этом работают с одним и тем же адресным пространством в общей памяти. Изменения состояния памяти, сделанные одной нитью, сразу же становятся доступны всем остальным нитям без необходимости копировать данные в промежуточный буфер. Однако в целях повышения переносимости параллельных программ и библиотек, существуют механизмы автоматического отображения и синхронизации адресного пространства задачи в МРР-системах, а также реализации интерфейса обмена сообщениями через общую память в SMP-системах.

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

Исходя из требований к системе, а также из анализа существующих СПОЗ, были приняты следующие основные концептуальные положения, которые

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

Вычислительная сеть может состоять из произвольного набора вычислительных узлов (хостов), которые соединены высокоскоростной компьютерной сетью с поддержкой семейства протоколов TCP/IP.

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

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

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

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

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

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

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

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

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

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

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

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

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

Предлагаемая схема планирования включает следующие этапы:

Диспетчер планирования назначает заданиям из пула динамический

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

На первом этапе каждому заданию Диспетчер планирования присваивает некоторое значение - динамический приоритет. Это значение зависит от следующих факторов:

1. Времени нахождения задания в очереди

2. Ресурсоемкости задания (количества требуемых ресурсов)

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

4. Начального приоритета, определяемого владельцем задания.

Механизм динамических приоритетов является достаточно гибким для

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

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

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

планировщика некоторого класса имеет следующий вид: (рис. 1).

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

Рис. 1 График запуска заданий

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

На рис. 1 показан принцип выбора оптимальной размерности для задания. Задание 6 имеет три допустимых размерности - ( и Для размерности не существует окна достаточного размера, поэтому задание размещается после задания 5. Для размерностей ( и ( такие окна существуют, т.е. задание 6 может быть выполнено до задания 5, не влияя на время запуска последнего. В данном случае, при использовании размерности ( задание будет завершено раньше (^ < поэтому данная размерность считается оптимальной и

передается диспетчеру планирования для дальнейшей обработки.

Предполагается, что с увеличением размерности время обработки задания уменьшается - в противном случае нет смысла использовать большее количество процессоров. Однако эта зависимость нелинейная. Ускорением параллельной программы на N процессорах называют величину S(N) = Ti/Tn , где Тм - время выполнения задания на N процессорах, 1<S(N)SN. Эффективностью использования процессоров называют величину E(N) = S(N)/N, Oís E(N)á 1. Например, если при использовании восьми процессоров достигается двукратное ускорение, то эффективность равна 0.25.

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

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

L. = —-— , где T. - длина очереди для класса i. max 7]

Значения этих коэффициентов лежат в интервале от 0 до 1 и равны 1 для классов с максимальной загрузкой (локальное расписание которых имеет наибольшую длину). Если несбалансированность очередей превышает определенное администратором системы значение, необходим процесс выравнивания нагрузки на очереди отдельных классов. Этот процесс заключается в переносе заданий из очередей с высокой загрузкой в очереди с низкой загрузкой. Балансировка нагрузки производится по вычисленным коэффициентам загрузки

Для этого полностью повторяется второй этап, но при выборе локальной очереди класса, в которую нужно поместить задание, диспетчер планирования сравнивает не время прохождения задания для допустимых классов, а величины T(class) * L(class). Здесь T(class) - время прохождения задания для класса ресурсов class; L(class) - коэффициент загрузки для данного класса ресурсов.

Далее снова вычисляются коэффициенты загрузки для архитектур, и выполняется следующая итерация до тех пор, пока нагрузка в очередях не выровняется.

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

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

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

Для случая, когда задания являются полностью масштабируемыми, то есть могут выполняться на любом количестве ПЭ от 1 до Р, доказана теорема о том,

что предложенный алгоритм локального планирования является

аппроксимацией, где - минимально допустимая эффективность, т.е.

где L(TMS) - длина расписания, составленного

планировщиком, L(OPT) — минимально возможная длина расписания.

В третьей главе рассматривается система управления заданиями TMS, разработанная в рамках диссертационной работы с целью оснащения центра высокопроизводительных вычислений (ЦВВ) РГУ системой управления заданиями, и предъявляемые к ней требования. Рассматриваются концепции построения и архитектура системы управления заданиями, основные компоненты и модули, из которых состоит система. Описаны механизмы взаимодействия компонентов, рассмотрены аспекты безопасности и надежности системы, устойчивости к аппаратным и программным сбоям.

— Ц ОРТ)

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

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

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

1. Сервер планирования и учета. Он реализован в виде процесса-демона ОС UNIX и функционирует в фоновом режиме в течение всего жизненного цикла системы.

Основные функции данной подсистемы:

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

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

- Управление вычислительными узлами. Сервер планирования и учета

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

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

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

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

- Сохранение и передача пользователю результатов работы задания.

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

-Предоставление серверу планирования информации об узле - состояние узла (доступен/недоступен), данные о количестве ресурсов (процессоры, физическая и виртуальная память, дисковое пространство)

-Контроль за выполняющимися на узле заданиями и предоставление информации о потребляемых ими ресурсах.

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

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

3. Клиентские утилиты. Выполнены в виде отдельных исполнимых файлов

17

и могут запускаться на любом компьютере сети. Обеспечивают интерфейс командной строки с системой пользователям и администратору ЦВВ.

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

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

-tdel - утилита для удаления задания из очередей системы. -tget - позволяет получить с сервера файлы с результатами обработки задания.

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

Также в главе приведено описание программного интерфейса (API) различных компонентов системы управления.

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

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

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

Реализация системы TMS выполнена на языке программирования C+ + . Система внедрена в опытную эксплуатацию в ЦВВ РГУ.

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

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

Для исследования были использованы следующие данные:

1.Журналы использования вычислительных ресурсов ЦВВ РГУ за различные периоды времени.

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

3.Генератор заданий, позволяющий получать случайную последовательность заданий с заданными характеристиками распределения параметров.

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

1. Среднее время ожидания - время между поступлением задания в систему и запуском его на выполнение.

2. Среднее время прохождения - время между поступлением задания в систему и завершением выполнения задания.

3. Относительная задержка задания - отношение времени ожидания к времени прохождения.

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

5. Эффективность использования ресурсов вычислительных узлов.

В главе приведены графики и таблицы, наглядно демонстрирующие

приведенные выше показатели для различных случаев.

На приведенные ниже графиках показана зависимость основных характеристик расписания от доли масштабируемых заданий в эксперименте. Исходные данные были взяты из журнала обработки заданий в Суперкомпьютерном центре Сан-Диего (SDSC). На каждом графике показаны результаты для предложенной стратегии планирования (TMS), а также для стратегий PWS и AVG.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ, ВЫНОСИМЫЕ НА ЗАЩИТУ

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

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

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

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

5. Выполнена прототипная реализация системы управления заданиями TMS в среде ОС UNIX.

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

1.Букатов А.А., Хачкинаев Г.М. Разработка системы управления параллельными заданиями в гетерогенной вычислительной среде // Королев Л.Н. (ред.) Труды первой Всероссийской научной конференции "Методы и средства обработки информации", Москва, 2003, с. 197-202.

2.Букатов А.А., Хачкинаев Г.М. Организация выполнения заданий в распределенной вычислительной сети // Материалы Международной научной конференции "Интеллектуальные и многопроцессорные системы-2003" Таганрог, 2003, том 2, с. 86-88.

3.Букатов А.А., Хачкинаев Г.М. Система управления пакетной обработкой заданий // научно-теоретический журнал национальной академии наук Украины "Искусственный интеллект", 3/2003, с. 23-31.

4.Хачкинаев Г.М. Система планирования потока заданий в гетерогенной вычислительной среде // Труды всероссийской конференции «Научный сервис в сети Интернет» Новороссийск, 2003, с. 138-140.

5.Букатов А.А., Дацюк В.Н., Дацюк О.В., Хачкинаев Г.М. Опыт создания высокопроизводительного кластера с использованием двух коммуникационных сетей // Труды всероссийской конференции «Научный сервис в сети Интернет» Новороссийск, 2003, с. 110-112.

6.Букатов А.А., Хачкинаев Г.М. Система управления ресурсами в гетерогенных вычислительных сетях // Современные информационные технологии в

образовании: Южный Федеральный Округ. Тезисы докладов научно-методической конференции Ростов-на-Дону, 2003, с.49-51.

7.Букатов А.А., Хачкинаев Г.М. Система управления заданиями и ресурсами вычислительных сетей // Труды X Всероссийской научно-методической конференции "Телематика-2003" СПб, 2003 т.1, с. 122-123.

8.Букатов А.А., Хачкинаев Г.М Организация планирования потока заданий в гетерогенной вычислительной среде ЦВВ РГУ // Труды Всероссийской научно-методической конференции «Телематика'2002» СПб, 2002, с. 158-159.

9.Букатов А.А., Хачкинаев Г.М Система пакетного выполнения потока заданий в гетерогенной вычислительной среде // Труды Международной научно-технической конференции «СуперЭВМ и многопроцессорные вычислительные системы» (МВС-2002) Таганрог, 2002, с. 145-148.

Ю.Букатов А.А., Хачкинаев Г.М. Методы диспетчеризации потока заданий для эффективного выполнения на гетерогенной вычислительной сети // Материалы IX конференции представителей региональных сетей Relarn-2002 Нижний Новгород, 2002, с. 79-81.

П.Букатов А.А., Хачкинаев Г.М. Система планирования и выполнения потока заданий в гетерогенной вычислительной сети // Труды XXIX международной конференции «Информационные технологии в науке, образовании, телекоммуникации, бизнесе»,, 2002, с. 21-23.

12.Букатов А.А. Хачкинаев Г.М. Система управления пакетными заданиями в гетерогенной вычислительной сети ЦВВ РГУ //Труды всероссийской конференции «Научный сервис в сети Интернет» Новороссийск, 2002, с.261-263.

П.Букатов А.А., Дацюк В.Н., Хачкинаев Г.М. Система управления выполнением потока заданий в гетерогенной вычислительной среде // Труды Международной научно-методической конференции «Телематика'2001», СПб, 2001, с. 165-166. ^

Печать цифровая. Бумага офсетная. Гарнитура "Тайме". Формат 60 х 84 / 16. Объем 1,0 уч. - изд. л. Заказ № 69. Тираж 100 экз. Отпечатано в КМЦ "КОПИ ЦЕНТР* 344006, г. Ростов-на-Дону, Суворова, 19. тел. 47-34-88

4 -5401

Введение.

Глава 1. ОБЗОР СОВРЕМЕННЫХ СИСТЕМ ПАКЕТНОЙ ОБРАБОТКИ ЗАДАНИЙ В МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ.

1.1. Обзор многопроцессорных вычислительных систем.

1.2. Обзор средств программирования многопроцессорных вычислительных систем.

1.2.1. Коммуникационная библиотека MPI.

1.2.2. Среда выполнения параллельных программ PVM.

1.3. Системы управления пакетной обработкой заданий.

1.3.1. Кластерная система Condor.

1.3.2. Система DQS - Distributed Queuing System.

1.3.3. Система управления заданиями Codine.

1.3.4. Переносимая планирующая система PBS - Portable Batch System.

1.3.5. Архитектура систем управления заданиями.

1.4. GRID-технологии.

1.5. Выводы по главе 1.

Глава 2. МЕТОДЫ ПЛАНИРОВАНИЯ ОЧЕРЕДНОСТИ ВЫПОЛНЕНИЯ ЗАДАНИЙ НА МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ ГЕТЕРОГЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СЕТИ.

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

2.2. Ресурсы в системе управления заданиями TMS.

2.3. Задания в системе управления TMS.

2.3.1. Эффективность параллельных программ.

2.3.2. Расчет времени выполнения задания.

2.4. Постановка задачи планирования и ее сложность.

2.4.1. Классификация алгоритмов планирования.

2.4.2. Критерии оценки расписаний.

2.4.3. Известные дисциплины планирования.

2.5. Планирование заданий в системе управления TMS.

2.5.1. Приоритеты заданий.

2.5.2. Локальное планирование заданий.

2.5.3. Балансировка загрузки локальных очередей классов.

2.6. Теорема об эффективности локального планирования.

2.7. Выводы по главе 2.

Глава 3. РАЗРАБОТКА СИСТЕМЫ УПРАВЛЕНИЯ ВЫПОЛНЕНИЕМ ПОТОКА ПРОГРАММ НА ВЫСОКОПРОИЗВОДИТЕЛЬНОЙ ВЫЧИСЛИТЕЛЬНОЙ СЕТИ.

3.1. Назначение и требования к системе управления потоком заданий.

3.2. Общая организация системы TMS.

3.3. Сервер планирования и учета.

3.3.1. Структура сервера планирования и учета.

3.3.2. Основной конфигурационный файл сервера планирования.

3.3.3. Ограничения и учет использования ресурсов.

3.3.4. Организация сетевых взаимодействий.

3.3.5. Безопасность системы управления заданиями TMS.

3.3.6. Описание заданий.

3.3.7. Цикл обработки задания.

3.4. Модуль-агент узла.

3.5. Программные интерфейсы системы управления заданиями TMS.

3.5.1. Программный интерфейс планировщика SchedAPI.

3.5.2. Библиотека CommandAPI.

3.5.3. Программный интерфейс агента вычислительного узла AgentAPI.

3.6. Утилиты системы управления заданиями TMS.

3.6.1. Утилита tsub.

3.6.2. Утилита tstat.

3.6.3. Утилита tdel.

3.6.4. Утилита tget.

3.6.5. Утилита tconf.

3.7. Выводы по главе 3.

Глава 4. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ РАЗРАБОТАННЫХ МЕТОДОВ ПЛАНИРОВАНИЯ ЗАДАНИЙ.

4.1. Эмуляция внешней среды сервера планирования и учета.

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

4.3. Генератор заданий.

4.4. Конвертер журналов.

4.5. Результаты исследований.

4.6. Выводы по главе 4.

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

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

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

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

Существующие СПОЗ можно условно разделить на 2 класса:

1. Специализированные СПОЗ - применяются для поддержки конкретных супер-ЭВМ, обычно поставляются вместе с этими супер-ЭВМ.

2. СПОЗ общего назначения - могут применяться для достаточно широкого класса многопроцессорных систем.

Однако существующие СПОЗ обладают рядом недостатков:

1. Некоторые системы рассчитаны на управление однородными вычислительными сетями. В то же время, в состав вычислительных центров обычно входят разнородные системы, образуя гетерогенные вычислительные сети. Примерами систем пакетной обработки, рассчитанных на работу в однородных сетях, являются DJM, Task Broker, EASY.

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

Однако, одним из важных свойств большинства параллельных программ является их масштабируемость - т.е. способность выполняться на различном количестве процессоров. При этом, от количества выделенных процессоров зависит потребность программы в других ресурсах вычислительной системы -например, зависимость времени выполнения параллельной программы от числа процессоров определяется законом Амдала. Кроме того, использование стандартных средств и интерфейсов для организации межпроцессорных взаимодействий позволяет создавать переносимые параллельные программы, которые могут выполняться на МВС разных типов с различной архитектурой. Например, реализации коммуникационной библиотеки MPI существуют для подавляющего большинства многопроцессорных систем (включая кластеры рабочих станций), а библиотеки POSIX thread доступны для большинства SMP-систем.

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

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

1.Провести сравнительный анализ современных систем управления заданиями для МВС, выявить их преимущества и недостатки.

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

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

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

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

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

7.Провести исследование характеристик полученных алгоритмов планирования.

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

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

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

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

4.Результаты исследования эффективности алгоритмов планирования.

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

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

2. Методы и алгоритмы распределения заданий по вычислительным узлам сети, выбора размерности задания и времени запуска, а также балансировки загрузки различных вычислительных ресурсов, в совокупности составляющих систему планирования TMS (Task Management System).

3. Средства эмуляции работы системы планирования TMS и результаты исследования эффективности используемых подходов к планированию заданий.

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

5. Реализация системы управления заданиями TMS в среде ОС UNIX.

Практическая значимость.

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

Апробация результатов работы.

Результаты работы докладывались и обсуждались на научно-практических конференциях: Международная научно-методическая конференция "Телематика'2001", Санкт-Петербург, 2001 г.; Всероссийская научная конференция "Научный сервис в сети Интернет", Новороссийск, 2002 г.; XXIX Международная конференция "Информационные технологии в науке, образовании, телекоммуникации, бизнесе", 2002 г.; IX конференция представителей региональных сетей "ReIarn-2002", Нижний Новгород, 2002 г.; Международная научно-техническая конференция "СуперЭВМ и многопроцессорные вычислительные системы", Таганрог, 2002 г.; IX Всероссийская научно-методическая конференция "Телематика'2002", Санкт-Петербург, 2002 г.; X Всероссийская научно-методическая конференция "Телематика'2003", Санкт-Петербург, 2003 г.; Научно-методическая конференция "Современные информационные технологии в образовании: Южный Федеральный округ", Ростов-на-Дону, 2003 г.; Всероссийская научная конференция "Научный сервис в сети Интернет", Новороссийск, 2003 г.;

Международная научная конференция "Интеллектуальные и многопроцессорные системы", Таганрог, 2003 г.; I Всероссийская научная конференция "Методы и средства обработки информации", Москва, 2003 г.

Результаты работы использовались при выполнении и составили существенную часть результатов следующих НИР: проект В.0011 ФЦП «Интеграция» «Развитие центра высокопроизводительных вычислений для нужд вузовской и академической науки», № гос. регистрации 01.200.118684; проект № 341 «Исследование и разработка программных средств организации удаленного выполнения программ на гетерогенной вычислительной сети суперкомпьютерного центра Ростовского государственного университета» НТП Минобразования РФ «Государственная поддержка региональной научно-технической политики высшей школы и развитие ее научного потенциала», № гос. регистрации 01.200.118685; проект 1.7.3 «Разработка методов, технологии и специальных программных средств удаленного использования вычислительных ресурсов регионального центра высокопроизводительных вычислений в учебном процессе и научных исследованиях» НОП Минобразования РФ «Научное, научно-методическое, материально-техническое обеспечение развития технологий информационного общества и индустрии образования». Результаты работы внедрены в опытную эксплуатацию в центре высокопроизводительных вычислений РГУ.

Структура и структура диссертационной работы.

Материал основной части диссертационной работы изложен на 155 страницах машинописного текста. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 119 наименований, 53 рисунков, 1 таблицы и 2 приложений.

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

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

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

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

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

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

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

Заключение

1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - Санкт-Петербург: БХВ-Петербург, 2002. - 609 с.

2. Букатов А.А., Дацюк В.Н., Жегуло А.И. Программирование многопроцессорных вычислительных систем. Ростов-на-Дону: Из-во ООО «ЦВВР», 2003. - 208 с.

3. Корнеев В. Архитектуры с распределенной разделяемой памятью // Открытые системы. -2001. №3. - с. 15-23.

4. Параллельные компьютеры с распределенной памятью // ComputerWorld. — 1995.-№22.

5. Дубова Н. Суперкомпьютеры nCube // Открытые системы. 1995. - №2. -с. 42-48

6. Standard Performance Evaluation Corporation (SPEC), http://www.spec.org

7. Кузьминский M., Волков Д. Современные суперкомпьютеры: состояние и перспективы // Открытые системы. 1995. - №6. - с. 33-41.

8. Lumb I. Beyond Beowulf Clustering Choices for the Next Generation. - 2001.

9. Андреев А., Воеводин Вл.В., Жуматий С. Кластеры и суперкомпьютеры -близнецы или братья ? // Открытые системы. 2000. - №5-6. - с. 9-14.

10. Зубинский А. Кластеры о главном. // Компьютерное обозрение. — 2002. -№18-19.

11. Наиболее распространенные коммуникационные технологии. -http://parallel.ru/computers/interconnects.html

12. Коваленко В.Н., Коваленко Е.И., Корягин Д.А., Любимский Э.З., Орлов А.В., Хухлаев Е.В. Структура и проблемы развития программного обеспечения среды распределенных вычислений Грид. Препринт ИПМ им. М.В.Келдыша РАН, 2002, N 22. 23 с.

13. Коваленко В.Н., Коваленко Е.И., Корягин Д.А., Любимский Э.З., Хухлаев Е.В. Управление заданиями в рапределенной вычислительной среде // Открытые системы. 2001. - №5-6. - с.22-28.

14. Коваленко В.Н., Орлов А.В. Управление заданиями в распределенной среде и протокол резервирования ресурсов. Препринт ИПМ им. М.В.Келдыша РАН, 2002, N 1. 25 с.

15. Шевель А. Технология GRID // Открытые системы. 2001. - №2. - с. 36-39.

16. Кореньков В., Тихоненко Е. Организация вычислений в научных отраслях //Открытые системы. 2001. - №2. - с. 30-35.

17. Васенин В., Роганов В. GRACE: распределенные приложения в Internet // Открытые системы. 2001. - №5-6. - с. 29-33.

18. Коваленко В., Корягин Д. Эволюция и проблемы GRID. // Открытые системы. — 2003. №1. - с. 27-37.

19. Коваленко В., Корягин Д. Вычислительная инфраструктура будущего // Открытые системы. 1999. - №11-12. - с. 45-52.

20. Воеводин Вл.В. Курс лекций Параллельная обработка данных. -http://parallel.ru/vw/

21. Горелик A.M. Средства поддержки параллельности в языках программирования. // Открытые системы. — 1995. №2. - с. 34-41.

22. Богачев К.Ю., Основы параллельного программирования. — М.: «БИНОМ. Лаборатория знаний», 2003. — 342 е., ил.

23. Posix thread programming. http://www.llnl.gov/computing/tutorials/workshops/workshop/pthreads/MAIN.ht ml

24. MPI: A Message-Passing Interface Standard. Messsage Passing Interface Forum. — Version 1.1. 1995.-http://www-unix.mcs.anl.gov/mpi

25. Немнюгин С., Стесик О. Параллельное программирование для многопроцессорных вычислительных систем. — СПб.: БХВ-Петербург, 2002. — 400 е.: ил.

26. Блэк Ю. Сети ЭВМ: протоколы, стандарты, интерфейсы: Пер. с англ. — М. Мир, 1990.

27. Семенов Ю.А. Протоколы и ресурсы Internet. М.: Радио и связь, 1996. -320 с.

28. Geist A., Beguelin A., Dongarra J. PVM: Parallel Virtual Machine. A User's Guide and Tutorial for Networked Parallel Computing. Cambrige: MIT Press.

29. Евсеев И. Использование PVM. Введение в программирование. -http://www.csa.ru: 81 /~il/pvmtutor

30. Коваленко В.Н., Коваленко Е.И. Пакетная обработка заданий в компьютерных сетях // Открытые системы. 2000. - №7-8. - с. 10-19.

31. Кузьминский М. NQS и пакетная обработка в UNIX \\ Открытые системы. 1997. - №1. - с. 18-22.

32. Baker М.А., Yau H.W. Cluster Computing Review. NPAC Technical Report, SCCS-748, NPAC, Syracuse University, USA, October 1995.

33. Kaplan J. A., Nelson M. L. A Comparison of Queueing, Cluster and Distributed Compuing Systems. Technical Report, RNS-94-006, NASA Ames Research Center, 1994.

34. The Condor project homepage. http://www.cs.wisc.edu/condor

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

36. Vesseur J.J.J., Heederik R.N., Overeinder B.J., Sloot P.M.A. Experiments in Dynamic Load Balancing for Parallel Cluster Computing. In Proceedings of the Workshop on Parallel Programming and Computation ZEUS'95, 1995, p. 189194.

37. DISTRIBUTED QUEUEING SYSTEM 3.3.2 USER GUIDE. - 2000. -http://www.csb.yale.edu/userguides/sysresource/batch/doc/UserGuide.html

38. Duke D., Green Т., Pasko J. Research Toward a Heterogenous Networked Computing Cluster: The Distributed Queueing System, Version 3.0. -Supercomputer Computations Research Institute, Florida State University, March 1994.

39. Codine 5.2 Manual. 2000. -http://www.sapac.edu.au/orion/Documentation.html

40. Portable Batch System. http://www.openpbs.org

41. Portable Batch System Administrator Guide. 2000.

42. Henderson R. Job Scheduling Under the Portable Batch System. In Job Scheduling Strategies for Parallel Processing, Dror Feitelson and Larry Rudolph (Eds.), Lecture Notes in Computer Science Vol. 949, pp. 337-360, Springer-Verlag, 1995.

43. Globus Toolkit Documentation. http://www-unix.globus.org/toolkit/documentation.html

44. Boulet P., Dongarra J., Rastello F., Robert Y., Vivien F. Algorithmic issues on heterogeneous computing platforms. // Parallel Processing Letters, 9(2): pp. 197213, 1999.

45. Cime W. Using Moldability to improve performance of supercomputer jobs. PhD Thesis, 2001, 160 p.

46. Downey A. Using Queue Time Predictions for Processor Allocation. In Job Scheduling Strategies for Parallel Processing, Springer-Verlag, Lecture Notes in Computer Science Vol. 1291, Dror Feitelson and Larry Rudolph (eds.), 1997.

47. The ScaLAPACK Project. http://www.netlib.org/scalapack.

48. Amdahl G. Validity of the single-processor approach to achieving large-scale computing capabilities. // Proc. 1967 AFIPS Conf., AFIPS Press. 1967. -V.30, p. 483.

49. Havill J.T. A competitive online algorithm for a parallel job scheduling problem. Parallel and Distributed Computing and Systems Editors: M. Guizani and X. Shen, 2000, 826 pages, vol. 1 & 2.

50. Smirni E., Rosti E., Dowdy L.W., Serazzi G. Evalution of multiprocessor allocation policies. //Technical Report, Vanderbilt University, 1993.

51. Downey A.B. A model for speedup of parallel programs. U.C. Berkeley Technical Report CSD-97-933, 1997.

52. Dowdy L. W. On the partitioning of multiprocessor systems. Technical Report 88-06, Vanderbilt University, March 1988

53. Chen P., Chen Y., Goel M., Mang F. Approximation of Two-Dimensional Rectangle Packing.

54. Lodi A., Martello S., Vigo D. TSpack: A Unified Tabu Search Code for MultiDimensional Bin Packing Problems. // Annals of Operations Research.

55. Caprara A., Toth P. Lower Bounds and Algorithms for the 2-Dimensional Vector Packing Problem // to appear in Discrete Applied Mathematics, 2001.

56. Dell'Amico M., Martello S., Vigo D. A lower bound for the non-oriented two-dimensional bin packing problem. // Discrete Applied Mathematics 118, 2002, c. 13—24.

57. Li K. Analysis of an Approximation Algorithm for Scheduling Independent Parallel Task. // Discrete Mathematics and Theoretical Computer Science vol.3 N4,1999, p. 155-166.

58. Du J., Leung J. Y.-H. Complexity of scheduling parallel task systems. // SIAM Journal on Diskrete Mathematics, 2(4): pp. 473-487, 1989.

59. Li K., Pan Y. Probabilistic Analysis of scheduling precedence constrained parallel task on multicomputers with contigunous processor allocation. // IEEE Transactions on computers, vol 49(10), 2000.

60. Jansen K., Porkolab L. Linear-time approximation schemes for scheduling malleable parallel tasks. Research Report, Max-Planck-Institut for Informatik, 1998.

61. Petri S., Langendorfer H. Load balancing and fault tolerance in workstation clusters migrating groups of communicating processes. // Operating Systems Review. 1995. - Vol. 29, #4. - p. 25-36.

62. Afrati F., Bampis E., Chekuri C. Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates. // In Procedings of the 40th Simposium on Foundations of Computer Science (FOCS99), pp.32-43.

63. Kalyanasundaram В., Pruhs K.R. Maximizing job completions online. // In European Symposium on Algorithms, p. 235-246, 1998.

64. Turek J., Wolf J.L., Yu P.S. Scheduling parallelizable tasks: Putting it all on the shelf. Performance Evaluation Review, 20(1) p. 225- 236, 1992.

65. Drozdowski M. Scheduling Multiprocessor Tasks: An Overview. // European Journal of Operational Research 94, pp. 215-230, 1996.

66. Chang E.-C., Wang W., Kankanhalli M.S. Multidimensional on-line bin-packing: an algorithm and its average-case analysis. // Information Proceedings Letters. 1993. - Volume 48, #3. - p. 121-125.

67. Bischof S., Mayr E.W. On-line scheduling of parallel jobs with runtime restrictions. // ISAAC: 9th International Symposium on Algorithms and Computation.

68. Lai T.-H., Sahni S. Nearly On-Line Scheduling of Multiprocessor Systems with Memories. //Journal of Algorithms. 1983. - Vol. 4 #4. - p. 353-362.

69. Hall L.A., Schulz A.S., Shmoys D.B., Wein J. Scheduling to minimize average completion time: offline and on-line algorithms. // In Proc. of the 7th ACMSIAM Symp. on Discrete Algorithms, 1996, pp. 142—151.

70. Heiss H.-U. Processor Management in 2D-Grid Architectures: Buddy-Systems. GI-PARS-Mitteilungen No. 12, Dresden, 6.-8., 1993, pp. 14-23.

71. Mohapatra P., Yu C., Das C. R. A Lazy Scheduling Scheme for Hypercube Computers. // Parallel Distributed Computers. 27(1): pp. 26-37, 1995.

72. Varadarajan R., Hwang I. An efficient dynamic load balancing algorithm for adaptive mesh refinement. 1994.

73. Jansen К., Solis-Oba R., Sviridenko M. Makespan minimization in job shops: a linear time approximation scheme. // S1AM Journal of Discrete Mathematicsv. 16, pp. 288-300, 2003.

74. Krallmann J., Schwiegelshohn U., Yahyapour R. On the Design and Evaluation • of Job Scheduling Algorithms. // In Job Scheduling Strategies for Parallel

75. Processing, Springer-Verlag, Lectures Notes in Compututer Science vol. 1659, 1999.

76. Downey A.B. A parallel workload model and its implications for processor allocation//Cluster Computing, Vol. 1 #1, 1998, p. 133-145

77. Aida K., Kasahara H., Narita S. Job Scheduling Scheme for Pure Space Sharing among Rigid Jobs. // In Job Scheduling Strategies for Parallel Processing, Springer-Verlag, Lecture Notes in Computer Science Vol. 1459, 1988.

78. Zotkin D., Keleher P. Job-Length Estimation and Performance in Backfilling Schedulers. // 8th International Symposium on High Performance Distributed Computing (HPDC'99), Redondo Beach, California, USA, 3-6 Aug 1999.

79. Feitelson D. Weil A.M. Utilization and predictability in scheduling the IBM SP2 with backfilling. // In 12th Intl. Parallel Processing Symp., pp. 542-546, 1998.

80. James H.A., Hawick K.A., Coddington P.D. Scheduling independent tasks on metacomputing systems. Technical Report DHPC-066, University of Adelaide, Australia, 1999.

81. Feitelson, D. Job Scheduling in Multiprogrammed Parallel Systems. IBM Research Report RC 19970, Second Revision, 1997.

82. Maui High Performance Computing Center. The Maui Scheduler Web Page. -http://wailea.mhpcc.edu/maui/

83. Smith E. Various optimizers for singlestate production. Naval Research Logistics Quarterly, 3, 1956.

84. Coffman E.G., Johnson D.S., Shor P.W., Lueker G.S. Probabilistic analisys of packing and related partitioning problems. // In Probability and Algorithms, pp. 87-107, National Research Council, 1992.

85. Brecht Т. Guha К. Using parallel program characteristics in dynamic multiprocessor allocation policies. // Performance Evaluation, 27 & 28, pp. 519539, 1996.

86. Majumdar S., Eager D.I., Bunt R., Characterization of program for scheduling in multiprogramed parallel system. // Performance Evaluation, Vol 13(2). 1991. -pp.109-130.

87. Steia S., Tripathi S. An Analysis of Several Processor Partitioning Policies for Parallel Computers. Technical Report CS-TR-2684, University of Maryland, 1991.

88. Ghosal D., Serazzi G., Tripathi S. The Processor Working Set and Its Use in Scheduling Multiprocessor Systems. // IEEE Transaction on Software Engineering 17, May 1991, pp. 443-453.

89. Eager D., Zahorjan J., Lazowska E. Speedup Versus Efficiency in Parallel Systems. // IEEE Transaction on Computers, 38, March 1989, p. 408-423.

90. Naik V. K., Setia S. K., Squillante M. S., Performance analysis of job scheduling policies in parallel supercomputing environments. // In Supercomputing '93, p. 824-833, 1993.

91. Sevcik K. Characterization of Parallelizm in Applications and Their Use in Scheduling. // Proc. 1989 ACM SIGMETRICS and Performance '89 Int'l Conf. On Measurement and Modeling of Computer Systems, Berkeley, CA, pp. 171180, 1989.

92. Leinberger W., Karypis G., Kumar V. Job scheduling in the presence of multiple resource requirements. // In Supercomputing '99, November 1999.

93. Batat A. Feitelson D. Gang Scheduling with Memory Considerations. //IPDPS'2000, International Parallel and Distributed Processing Symposium, pp. 109-114,2000.

94. McCann С., Zahorjan J. Scheduling Memoiy Constrained Jobs on Distributed-Memory Parallel Computers. //In SIGMETRICS Conference on Measurement and Modeling of Computer Systems, pp. 208-291, 1995.

95. Smith W., Taylor V., Foster I. Using Run-Time Predictions to Estimate Queue Wait Times and Improve Scheduler Performance. //In Proceedings of the IPPS/SPDP'99 Workshop on Job Scheduling Strategies for Parallel Processing,1999.

96. Downey A. Predicting queue times on space-sharing parallel computers. // 11th International Parallel Processing Symposium (IPPS'97), Geneva, Switzerland, 1997.

97. Gibbons R. A Historical Application Profiler for Use by Parallel Schedulers. //Lecture Notes in Computer Science, vol. 1297, 58-75, Springer-Verlag, 1997.

98. Питц-Моултис H., Кирк 4. XML в подлиннике. СПб: Питер, 2000. - 736 с.

99. Chapin S., Cirne W., Feitelson D. Benchmarks and standards for the evaluation of parallel job schedulers. // Job Scheduling Strategies for Parallel Processing, Springer-Verlag, pp. 67-90, 1999.

100. Feitelson D. The Parallel Workload Archive. http://www.cs.huji.ac.il/labs/parallel/workload

101. Aida K. Effect of Job Size Characteristics on Job Scheduling Performance. //In Job Scheduling Strategies for Parallel Processing, Dror Feitelson and Larry Rudolph (Eds.), Springer-Verlag, Lecture Notes in Computer Science vol. 1911,2000.

102. Букатов А.А., Хачкинаев Г.М. Организация выполнения заданий в распределенной вычислительной сети // Материалы Международной научной конференции "Интеллектуальные и многопроцессорные системы-2003" Таганрог, 2003, том 2, с. 86-88.

103. Букатов А.А., Хачкинаев Г.М. Система управления пакетной обработкой заданий // научно-теоретический журнал национальной академии наук Украины "Искусственный интеллект". -2003. №3. - с. 23-31.

104. Хачкинаев Г.М. Система планирования потока заданий в гетерогенной вычислительной среде // Труды всероссийской конференции «Научный сервис в сети Интернет» Новороссийск, 2003, с. 138-140.

105. Букатов А.А., Дацюк В.Н., Дацюк О.В., Хачкинаев Г.М. Опыт создания высокопроизводительного кластера с использованием двух коммуникационных сетей // Труды всероссийской конференции «Научный сервис в сети Интернет» Новороссийск, 2003, с. 110-112.

106. Букатов А.А., Хачкинаев Г.М. Система управления заданиями и ресурсами вычислительных сетей // Труды X Всероссийской научно-методической конференции "Телематика-2003" СПб, 2003 т.1, с. 122-123.

107. Букатов А.А., Хачкинаев Г.М Организация планирования потока заданий в гетерогенной вычислительной среде ЦВВ РГУ // Труды Всероссийской научно-методической конференции «Телематика'2002» СПб, 2002, с. 158159.

108. Букатов А.А., Хачкинаев Г.М. Методы диспетчеризации потока заданий для эффективного выполнения на гетерогенной вычислительной сети // Материалы IX конференции представителей региональных сетей Relarn-2002 Нижний Новгород, 2002, с. 79-81.

109. Букатов А.А., Хачкинаев Г.М. Система планирования и выполнения потока заданий в гетерогенной вычислительной сети // Труды XXIX международной конференции «Информационные технологии в науке, образовании, телекоммуникации, бизнесе»,, 2002, с. 21-23.

110. Букатов А.А. Хачкинаев Г.М. Система управления пакетными заданиями в гетерогенной вычислительной сети ЦВВ РГУ //Труды всероссийской конференции «Научный сервис в сети Интернет» Новороссийск, 2002, с.261-263.

111. Букатов А.А., Дацюк В.Н., Хачкинаев Г.М. Система управления выполнением потока заданий в гетерогенной вычислительной среде // Труды Международной научно-методической конференции «Телематика'2001», СПб, 2001, с. 165-166.