Система пакетной обработки заданий в гетерогенной вычислительной сети тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Хачкинаев, Геннадий Месропович

• Хачкинаев, Геннадий Месропович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Хачкинаев, Геннадий Месропович

Введение.

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

Заключение

Список литературы диссертационного исследования кандидат технических наук Хачкинаев, Геннадий Месропович, 2004 год

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.