Помощь в написании студенческих работ
Антистрессовый сервис

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

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

Диссертационные исследования выполнялись в рамках федеральных целевых программ «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007 — 2013 годы» (ГК № 02.514.11.0002 «Разработка программных технологий для развития российского сегмента Грид, систем параллельного программирования, систем компьютерной графики») и «Научные… Читать ещё >

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

Содержание

  • ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ
  • ГЛАВА 1. ОСНОВЫ ОРГАНИЗАЦИИ ФУНКЦИОНИРОВАНИЯ РАСПРЕДЕЛЁННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
    • 1. Л Понятие о распределённых вычислительных системах
    • 1. ЛЛ Модель коллектива вычислителей
    • 1. Л.2 Классификация архитектур вычислительных систем
    • 1. Л.З Функциональная организация распределённых ВС
      • 1. 2. Основные режимы функционирования ВС
      • 1. 2. Л Монопрограммный режим
        • 1. 2. 2. Мультипрограммный режим
      • 1. 3. Классификация задач
      • 1. 4. Формирование расписания обработки наборов масштабируемых задач на распределённых вычислительных системах
        • 1. 4. 1. Задача формирования расписаний
        • 1. 4. 2. Обзор методов и алгоритмов формирования расписаний
        • 1. 4. 3. Методы кодирования расписаний
        • 1. 4. 4. Обзор средств планирования
      • 1. 5. Выводы
  • ГЛАВА 2. АЛГОРИТМЫ ФУНКЦИОНИРОВАНИЯ РАСПРЕДЕЛЁННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ В РЕЖИМЕ ОБРАБОТКИ НАБОРА МАСШТАБИРУЕМЫХ ЗАДАЧ
    • 2. 1. Методы решения
    • 2. 2. Выбор параметров масштабируемых задач
    • 2. 3. Формирование укрупненных задач с целью минимизации времени решения задач набора
      • 2. 3. 1. Стохастический алгоритм
      • 2. 3. 2. Генетический алгоритм
    • 2. 4. Многокритериальная оптимизация формирования укрупненных задач
      • 2. 4. 1. Последовательный генетический алгоритм с кроссинговером перетасовки генов
      • 2. 4. 2. Параллельный генетический алгоритм с кроссинговером перетасовки генов
    • 2. 5. Формирование последовательности решения укрупнённых задач с целью минимизации штрафа за задержку их решения
    • 2. 6. Формирование итогового расписания решения масштабируемых задач на распределенных ВС
    • 2. 7. Моделирование алгоритмов формирования расписаний решения задач на распределённых вычислительных системах
    • 2. 8. Выводы
  • ГЛАВА 3. ПРОСТРАНСТВЕННО РАСПРЕДЕЛЕННАЯ ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ
    • 3. 1. Архитектура пространственно-распределенной мультикластерной вычислительной системы
    • 3. 2. Программное обеспечение пространственно-распределённой мультикластерной вычислительной системы
      • 3. 2. 1. Стандартные компоненты
      • 3. 2. 2. Пакет MOJOS поддержки мультипрограммных режимов обработки наборов масштабируемых задач
      • 3. 2. 2. Интерфейс с системами пакетной обработки заданий
    • 3. 3. Выводы

Актуальность работы. Возрастающая потребность в решении сложных задач науки, техники и экономики привела к созданию распределённых высокопроизводительных вычислительных систем (ВС). В общем случае распределённая ВС — это композиция множества элементарных машин (ЭМ) и сети межмашинных связей. Элементарная машина — это основной функциональный и структурный элемент ВСконфигурация ЭМ допускает варьирование в широких пределах — от процессорного ядра до ЭВМ или специализированного ускорителя. Все основные ресурсы распределённых ВС (как аппаратурные, так и программные) являются логически и технически рассредоточенными. Количество ЭМ в распределённых ВС допускает варьирование от нескольких единиц до сотен тысяч (например, в системе Fujitsu К Computer [85] количество вычислительных ядер равно 705 024).

Исследования в области распределённых вычислительных систем ведутся с середины XX столетия [23 — 27]. С тех пор в нашей стране и за рубежом выполнен ряд фундаментальных работ, посвященных проблемам организации высокопроизводительных вычислительных средств: проведены исследования по теории функционирования и построению оптимальных (макро)структур ВС, проработаны многие аспекты создания программного обеспечения, исследован широкий круг задач, допускающих эффективную реализацию на распределённых ВС [4, 5, 7, 9, 10, 13, 18, 20−22, 99, 133, 134]. Построены отечественные вычислительные системы с программируемой структурой: «Минск-222», СУММА, МИНИМАКС, МИКРОС, МВС, СКИФ и др.

Фундаментальный вклад в теорию и практику вычислительных систем и параллельных вычислительных технологий внесли советские и российские учёные, среди которых: Е. П. Балашов, В. Б. Бетелин, B.C. Бурцев, В.В.

Васильев, В. М. Глушков, В. Ф. Евдокимов, Э. В. Евреинов, A.B. Забродин,.

B.П. Иванников, М. Б. Игнатьев, A.B. Каляев, И. А. Каляев, JI.H. Королев,.

C.А. Лебедев, В. К. Левин, Г. И. Марчук, Ю. И. Митропольский, Д. А. Поспелов, И. В. Прангишвили, Д. В. Пузанков, Г. Е. Пухов, Г. Г. Рябов,.

A.A. Самарский, В. Б. Смолов, А. Н. Томилин, Я. А. Хетагуров,.

B.Г. Хорошевский, Б. Н. Четверушкин, Ю. И. Шокин, H.H. Яненко, а также зарубежные учёные: S. Cray, М. Flynn, I. Foster, D. Hillis, С. Kesselman, DL. Slotnick, A. Tanenbaum, D. Feitelson и другие. При решении проблем оптимизации функционирования распределённых ВС большую роль сыграли фундаментальные работы в области дискретной математики и исследовании операций советских и российских учёных: В. Л. Береснева, Э. Х. Гимади, В. Т. Дементьева, Ю. И. Журавлева, К. В. Рудакова и зарубежных — R. Bellmann, D. Johnson, М. Koffman, Н. Taha и других.

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

В режиме обработки набора задач на распределённой ВС требуется сформировать расписание их решения. Для каждой задачи необходимо определить подсистему ЭМ и момент запуска на выполнение ветвей соответствующей параллельной программы. Этот режим хорошо изучен для задач, параметры которых (ранг и время решения) заданы скалярными величинами, такие алгоритмы внедрены в системы пакетной обработки заданий (TORQUE, SLURM, Altair PBS Pro и др.).

Анализ пользовательских задач показывает [119], что более 80% из них обладают свойством масштабируемости. Такие задачи допускают решение на подсистемах с различным количеством ЭМ и называются масштабируемыми или «пластичными» (moldable) [129]. Актуальной является задача разработки алгоритмических и программных средств организации функционирования распределённых ВС в мультипрограммном режиме обработки наборов масштабируемых задач.

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

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

В соответствии с целью определены нижеследующие задачи исследования.

1. Анализ современных подходов к организации функционирования распределённых ВС в мультипрограммных режимах.

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

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

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

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

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

Созданный программный пакет MOJOS — MOldable JObs Scheduling предназначен для моделирования, отладки и анализа алгоритмов формирования расписаний решения масштабируемых задач на распределённых ВС.

Программные средства внедрены в действующую пространственно-распределённую мультикластерную вычислительную систему Центра параллельных вычислительных технологий (ЦПВТ) ФГОБУ ВПО «СибГУТИ» и Лаборатории вычислительных систем Федерального государственного бюджетного учреждения науки Института физики полупроводников им. А. В. Ржанова Сибирского отделения РАН (ИФП СО РАН).

Реализация и внедрение результатов работы. Основные результаты диссертации нашли применение в работах по созданию и развитию пространственно-распределённой мультикластерной вычислительной системы ЦПВТ ФГОБУ ВПО «СибГУТИ» и Лаборатории ВС ИФП СО РАН.

Диссертационные исследования выполнялись в рамках федеральных целевых программ «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007 — 2013 годы» (ГК № 02.514.11.0002 «Разработка программных технологий для развития российского сегмента Грид, систем параллельного программирования, систем компьютерной графики») и «Научные и научно-педагогические кадры инновационной России» (ГК № 02.740.11.0006 «Проведение исследований в области распределённых вычислительных систем и развитие научно-учебного центра параллельных вычислительных технологий ФГОБУ ВПО „СибГУТИ“»). Работа поддержана грантами грантами Президента РФ по поддержке молодых российских учены и ведущих научных школ (№ НШ-5176.2010.9, НШ-2175.2012.9, МК-2317.2012.9), Российского фонда фундаментальных исследований № 09−07−13 534, 08−07−22, 09−07−95, 11−07−109, грантом мэрии г. Новосибирска молодым учёным № 10−11 (2011), а так же грантами ФГОБУ ВПО «СибГУТИ» (2009, 2010, 2011).

Внедрение результатов диссертационного исследования подтверждается соответствующими актами.

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

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

— Международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы» (с. Дивноморское Гелен-джикского района, 2009);

— Международной научно-технической конференции «Суперкомпьютерные технологии: разработка, программирование, применение» (с. Дивноморское Геленджикского района, 2010);

— Международной научно-технической конференции «Студент и научно-технический прогресс» (г. Новосибирск, 2009, 2010, 2011);

— Международной научной молодёжной школе «Высокопроизводительные вычислительные системы» (с. Дивноморское Геленджикского района, 2010);

— Российской конференции с международным участием «Новые информационные технологии в исследовании сложных структур» (г. Томск, 2008, 2010);

— Научной школе-практикуме для молодых учёных и специалистов «Технологии высокопроизводительных вычислений и компьютерного моделирования» (г. Санкт-Петербург, 2009);

— Российской научно-технической конференции «Информатика и проблемы телекоммуникаций» (г. Новосибирск, 2008, 2009, 2010, 2011);

— Российской конференции с участием иностранных учёных «Распределённые информационные и вычислительные ресурсы» (г. Новосибирск, 2010);

— Всероссийской конференции молодых учёных по математическому моделированию и информационным технологиям (г. Красноярск, 2010);

— Пятой сибирской конференции по параллельным и высокопроизводительным вычислениям (г. Томск, 2009).

Публикации. По теме диссертации опубликовано 19 работ, из которых 3 — в изданиях из списка ВАК. Результаты исследований отражены в отчётах по грантам и НИР.

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

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

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

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

Структура и объём диссертации. Диссертационная работа состоит из введения, трёх глав, заключения и списка литературных источников, изложенных на 97 страницах, а также приложений на 25 страницах.

Основные результаты диссертации опубликованы в работах [28 -34, 53 — 62, 101, 102, 104].

ЗАКЛЮЧЕНИЕ

.

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

1. Разработано семейство полиномиальных алгоритмов многокритериальной оптимизации мультипрограммного функционирования распределённых ВС в режиме обработки наборов масштабируемых задач. Алгоритмы основаны на стохастических, эвристических и эволюционных методах оптимизации и позволяют учитывать пользовательские приоритеты на размеры подсистем ЭМ для каждой масштабируемой задачи. Отклонение от нижней границы времени решения задач в среднем составило 15 — 20%.

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

3. Предложен алгоритм работы планировщика распределённых ВС (алгоритм ALG6), который осуществляет формирование расписания обработки наборов масштабируемых задач из последовательностей укрупнённых задач, полученных в результате совместного использования алгоритмов ALG2−5.

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

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

Показать весь текст

Список литературы

  1. , Б. А. Многопроцессорные ЭВМ и методы их проектирования / Б. А. Бабаян, А. В. Бочаров, А. С. Волин. М.: Высшая школа, 1990. — 143 с.
  2. , В. Б. Архитектура цифровых процессоров обработки сигналов / В. Б. Бетелин и др. М.: РАН, 1993. — 20 с.
  3. , Е. П. Микро и мини-ЭВМ учебное пособие для ВУЗов / Е. П. Балашов, В. Л. Григорьев, Г. А. Петров. Л.: Энергоатомиздат, 1984. — 376 с.
  4. , Е. П. Микропроцессоры и микропроцессорные системы / Е. П. Балашов, Д. В. Пузанков, В. Б. Смолов. М.: Радио и связь, 1981.-326 с.
  5. , А. Б. Планирование параллельных вычислительных процессов / А. Б. Барский. М.: Машиностроение, 1980. — 192 с.
  6. , А. Б. Параллельные процессы в вычислительных системах / А. Б. Барский. М.: Изд-во «Радио и связь», 1990. — 256 с.
  7. , В. С. Параллелизм вычислительных процессов и развитие архитектур суперЭВМ / В. С. Бурцев. М.: ИВВС РАН, 1997. — 352 с.
  8. , В. С. Супер-ЭВМ : сборник научных трудов / В. С. Бурцев. -М.: АН СССР, отдел вычислительной математики, 1992. 95 с.
  9. , В. В. Многопроцессорные вычислительные структуры для анализа задач на сетях / В. В. Васильев, А. Г. Додонов // Проблемы электроники и вычислительной техники. 1976. — № 4. — С. 85−97.
  10. , А. И. Высокопроизводительные системы обработки данных / А. И. Водяхо, Н. Н. Горпец, Д. В. Пузанков. М.: Высшая школа, 1997.-304 с.
  11. , В. В. Параллельные вычисления / В. В. Воеводин, Вл. В. Воеводин. СПб.: БХВ-Петербург, 2002. — 608 с.79
  12. , В. П. Основы параллельных вычислений для многопроцессорных вычислительных систем / В. П. Гергель, Р. Г. Стронгин. -Нижний Новгород: Изд-во ННГУ, 2003. 184 с.
  13. , М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон — пер. с англ. М.: Мир, 1982. — 416 с.
  14. , Д. С. Планирование вычислений в системах жесткого реального времени (обзор и перспективы) / Д. С. Герушин // Вычислительная техника. Системы управления. 1991. — Вып. 6. — С. 4 — 51.
  15. , Э. X. Дискретные экстремальные задачи принятия решений / Э. X. Гимади, Н. И. Глебов. Новосибирск: НГУ, 1991. — 76 с.
  16. , JI. А. Генетические алгоритмы / JL А. Гладков, В. В. Курей-чик, В. М. Курейчик — под ред. В. М. Курейчика. 2-е изд., испр. и доп. — М.: ФИЗМАТЛИТ, 2006. — 320 с. — ISBN 5−9221−0510−8
  17. , А. В. Задачи двумерной упаковки и раскроя: обзор /А. В. Головистиков // Информатика. 2008. — Вып. 20. — С. 18−33.
  18. , Б.А. Расчет характеристик и планирование параллельных вычислительных процессов / Б. А. Головкин. М.: Радио и связь, 1983.-272 с.
  19. , М. Операционные система микроЭВМ / М. Дамке. -М.: Финансы и статистика, 1985. 151 с.
  20. , Ю. К. Вычислительные системы из мини-ЭВМ / Ю. К. Дмитриев, В. Г. Хорошевский. М.: Радио и связь, 1982. — 304 с.
  21. , А. Г. Введение в теорию живучести вычислительных систем / А. Г. Додонов, М. Г. Кузнецова, Е. С. Горбачик. Киев: Нау-кова думка, 1990. — 180 с.
  22. , В. Ф. Параллельные вычислительные структуры на основе разрядных методов / В. Ф. Евдокимов, А. И. Стасюк. К.: Нау-кова думка, 1987.-311 с.
  23. , Э. В. О возможности построения вычислительных систем высокой производительнсоти / Э. В. Евреинов. Новосибирск: Изд-во СО АН СССР, 1962 г. — стр?
  24. , Э. В. О возможности построения вычислительных систем в условиях запаздывания сигналов / Э. В. Евреинов // Вычислительные системы. 1962. — № 3. — С. 3−16.
  25. , Э. В. Однородные вычислительные системы, структуры и среды / Э. В. Евреинов. М.: Радио и связь, 1981. — 208 с.
  26. , Э. В. Однородные универсальные вычислительные системы высокой производительности / Э. В. Евреинов, Ю. Г. Косарев. -Новосибирск: Наука. Сибирское отд-е, 1966. 308 с.
  27. , Э.В. Однородные вычислительные системы / Э. В. Евреинов, В. Г. Хорошевский. Новосибирск: Наука. Сибирское отд-е, 1978.-319 с.
  28. Жук, С. Н. Онлайновый алгоритм упаковки прямоугольников в несколько полос с гарантированными оценками точности / С. Н. Жук // Труды Института Системного программирования: Методы синтеза и анализа. 2007. — Т. 12, — С. 7−16.
  29. , С. С. Управление процессами в операционных системах UNIX и WINDOWS NT: Учебное пособие по курсу «Операционные системы» / С. С. Калитин, Л. В. Гераскина. М.: МЭИ, 2000. — 44 с.
  30. , И. А. Реконфигурируемые мультиконвейерные вычислительные структуры / И. А. Каляев — под. ред. И. А. Каляева. Ростов-н/Д.: ЮНЦ РАН, 2008. — 320 с.
  31. , С. Проектирование операционных систем для малых ЭВМ / С. Кейслер — пер. с англ. М.: Мир, 1986. — 680 с.
  32. , В. Н. Управление заданиями в распределённой среде и протокол резервирования ресурсов / В. Н. Коваленко, А. В. Орлов. -М.: Препринт ИПМ № 1, 2002. 25 с.
  33. , В. Н. Управление параллельными заданиями в гриде с неотчуждаемыми ресурсами / В. Н. Коваленко, Е. И. Коваленко, Д.
  34. A. Корягин и др. М.: Препринт ИПМ РАН 63, 2007. — С. 1−28.
  35. , Р. В. Теория расписаний / Р. В. Конвей, В. Л. Максвелл, Л.
  36. B. Миллер. М.: Наука, 1975. — 360 с.
  37. , В. В. Архитектура вычислительных систем с программируемой структурой / В. В. Корнеев. Новосибирск: Наука, 1985. -164 с.
  38. , В. В. Архитектуры с распределенной разделяемой памятью / В. В. Корнеев // Открытые системы. 2001. — № 3. — С. 15−23.
  39. , В. В. Параллельные вычислительные системы / В. В. Корнеев. М.: Нолидж, 1999. — 320 с.
  40. , Ю. Г. Математическое обеспечение однородных вычислительных систем / Ю. Г. Косарев, Н. Н. Миренков // Вычислительные системы. 1974. — Вып. 58. — С. 61−79.
  41. , Э. Г. Теория расписаний и вычислительные машины / Л. Дж. Бруно, Р. Л. Грэхем, В. Г. Коглер и др. — под ред. Б. А. Головкина, пер. с англ. В. М. Амочкина, М.: Изд-во «Наука», 1984. 336 С.
  42. , Н. Н. Вероятностный анализ шельфовых алгоритмов упаковки прямоугольников в полосу / Н. Н. Кузюрин, А. И. Поспелов // Дискретная математика. 2006. — Т. 18, № 1. — С. 76−90.
  43. , В. М. Параллельные генетические алгоритмы: обзор и состояние проблемы / В. М. Курейчик, Д. С. Кныш // Известия РАН. Теория и системы управления. 2010. — № 4 — С. 72−82.
  44. , А. Как построить и использовать суперкомпьютер / А. Лацис. М.: Бестселлер, 2003. — 240 с.
  45. , С. Н. Алгоритмы планирования решения масштабируемых задач на распределённых вычислительных системах / С. Н. Мамойленко, А. В. Ефимов // Вестник СибГУТИ. Новосибирск: Изд-во «СибГУТИ», 2010. — № 2. — С. 66 — 78.
  46. , С. А. Упаковка прямоугольников в полосу модифицированным методом Нелдера-Мида с использованием генетического алгоритма / С. А. Мартишин, М. В. Храпченко // Труды Института системного программирования РАН. 2010. — Т. 19. — С. 135−156.86
  47. , Н. Н. Параллельное программирование для многомодульных вычислительных систем / Н. Н. Миренков. М.: Радио и связь, 1989.-319 с.
  48. , О. Г. Параллельные системы с распределенной памятью: структуры и организация взаимодействий / О. Г. Монахов, Э. А. Монахова. Новосибирск: Изд-во СО РАН, 2000. — 242 с.
  49. , О. Г. Параллельные системы с распределенной памятью: управление ресурсами и заданиями / О. Г. Монахов, Э. А. Монахова. Новосибирск: Изд-во ИВМиМГ СО РАН, 2001.- 168 с.
  50. , Э. А. Генетический алгоритм блочной структуры в задачах двумерной упаковки / Э. А. Мухачева, А. С. Мухачева, А. В. Чиглинцев // Информационные технологии. Машиностроение. М., 1999. -№ 11. — С. 13−18.
  51. , В. Д. Принятие решений в многокритериальной среде: количественный подход / В. Д. Ногин. М.: Физматлит, 2002. — 176 с.
  52. , В.Г. Сетевые операционные системы / В. Г. Олифер, Н. А. Олифер. СПб.: Питер, 2001. — 544 с.
  53. Г. А. Булевы модели синтеза параллельных планов решения вы-числительных задач / Г. А. Опарин, А. П. Новопашин // Вестник НГУ. Серия: Информационные технологии. 2008. — Том 6, Вып. 1. -С. 53−59.
  54. Операционная система СМ ЭВМ РАФОС: Справочник / J1. И. Валиков, Г. В. Вигдорчик, А. Ю. Воробьев и др. М.: Финансы и статистика, 1984. — 207 с.
  55. Основы теории оптимизации / Д. В. Ногин и др. М.: Высшая школа, 1986. — 384 с.
  56. , В. А. Организация функционирования однородных вычислительных систем и стохастическое программирование / В. А. Павский, В. Г. Хорошевский // Вычислительные системы. -1975.-Вып. 63.-С. 3−16.
  57. , И. В. Вычислительные системы / И. В. Панфилов, А. М. Половко. М.: Изд-во «Советское радио», 1980. — 302 с.
  58. , Д. А. Введение в теорию вычислительных систем / Д. А. Поспелов. М.: Изд-во «Советское радио», 1972. — 280 с.
  59. Сайт Центра параллельных вычислительных технологий ФГОБУ ВПО «СибГУТИ» Электронный ресурс. Режим доступа: http: //cpct. sibsutis. ru (дата обращения: 25.01.2012).
  60. Сайт проекта Survey on two-dimensional packing Электронный ресурс. Режим доступа: http://www.ese.liv.ас.uk/~epa/survey.pdf свободный (дата обращения: 25.01.2012).
  61. Сайт проекта Cluster resources: Products Maui Cluster Scheduler Электронный ресурс. — Режим доступа: http://www.clusterresources.com/pages/products/ma ui-cluster-scheduler.php, свободный (дата обращения: 25.01.2012).
  62. Сайт проекта Windows НРС Server 2008 I Microsoft Supercomputing I Supercomputers Электронный ресурс. Режим доступа: http://www.microsoft.com/hpc, свободный (дата обращения: 25.01.2012).
  63. Сайт проекта IBM Redbooks I Workload Management with LoadLeveler Электронный ресурс. Режим доступа http://www.redbooks.ibm.com/abstracts/sg2 46 038.html, свободный (дата обращения: 25.01.2012).88
  64. Сайт проекта Grid Computing I Oracle Grid Engine I Software I Sun Microsystems Электронный ресурс. Режим доступа: http://www.sun.com/software/sge, свободный (дата обращения: 25.01.2012)
  65. Сайт проекта PBS Works Enabling On-Demand Computing Электронный ресурс. — Режим доступа: http://www.openpbs.org, свободный (дата обращения: 25.01.2012).
  66. Сайт проекта TORQUE Электронный ресурс. Режим доступа: http://www.clusterresources.com/pages/products/to rque-resource-manager.php, свободный (дата обращения 25.01.2012).
  67. Сайт проекта Тор500 Электронный ресурс. Режим доступа: http: / /www. top50 0. org, свободный (дата обращения 25.01.2012).
  68. , М.С. Алгоритмы распределения набора задач с переменными параметрами по машинам вычислительной системы /М. С. Седельников // Автометрия. 2006. — Т. 42. — № 1. — С. 68−76.
  69. , С.И. Генетический алгоритм составления расписания выполнения параллельных заданий в распределенной вычислительной системе / С. И. Смагин, Т. С. Шаповалов // Вычислительные технологии. 2010. — Т. 15. — № 5. — С. 107−122.
  70. , В. Операционные системы / В. Столингс — 4-е изд. М.: Вильяме, 2002. — 848 с.
  71. , Б.Ю. Программное обеспечение мультитранспьютерных систем / Б. Ю. Сырков, С. В. Матвеев. М.: Диалог-МИФИ, 1992. -150 с.
  72. , Э. Архитектура компьютера / Э. Таненбаум. СПб.: Питер, 2002. — 704 с.
  73. , Э. Распределенные системы: принципы и парадигмы / Эндрю Таненбаум, Стен М. Ван — пер. с англ. А. Леонтьев. СПб.: Питер, 2003. — 877 с.
  74. , Э. Современные операционные системы / Э. Таненбаум — 2-е изд. СПб.: Питер, 2002. — 1040 с.
  75. , X. А. Введение в исследование операций, 7-е издание / X. А. Taxa — пер. с англ. под ред. А. А. Минько. М.: Издательский дом «Вильяме», 2005.-912 с.
  76. , С. П. Управление процессами в современных операционных системах / С. П. Титаренко. Белгород: БелГТАСМ, 1999. — 38 с.
  77. , В. В. Модели распределенных вычислений / В. В. Топорков. М.: ФИЗМАТЛИТ, 2004. — 320 с.
  78. , А. В. Оптимальное управление распределенными системами. Теория и приложения / А. В. Фурсиков. Новосибирск, 1999. -40 с.
  79. , Я. А. Основы проектирования управляющих вычислительных систем / Я. А. Хетагуров. М.: Радио и связь, 1991. — 287 с.
  80. , В. Г. Вычислительная система МИКРОС / В. Г. Хорошевский. Новосибирск: Препринт ИМ СО АН СССР 38 (ОВС-19), 1983.-52 с.
  81. , В. Г. Инженерный анализ функционирования вычислительных машин и систем / В. Г. Хорошевский. М.: Радио и связь, 1987.-256 с.
  82. , В. Г. Архитектура вычислительных систем / В. Г. Хорошевский. М.: МГТУ им. Н. Э. Баумана, 2008. — 520 с.
  83. , В. Г. Масштабируемый инструментарий параллельного мультипрограммирования пространственно-распределенных вычислительных систем / В. Г. Хорошевский, М. Г. Курносов, С. Н. Ма-мойленко, К. В. Павский, А. В. Ефимов, А. А. Пазников, Е. Н.90
  84. Перышкова // Вестник СибГУТИ. Новосибирск: Изд-во «СибГУ-ТИ», 2011.-№ 11.-С. 3−18.
  85. , К. Системное программирование в UNIX. Руководство программиста по разработке ПО / К. Хэвиленд, Д. Грэй, Б. Салама — пер. с англ. М.: ДМК Пресс, 2000. — 368 с.
  86. , Д. Операционные системы / Д. Цикритзис, Ф. Бернстайн. М.: Мир, 1977.-336 с.
  87. , Т. С. Генетический алгоритм составления расписаний для распределенных гетерогенных вычислительных систем / Т. С.
  88. , В. В. Пересветов // Вычислительные методы и программирование. 2009. — Т. 10. — С. 159−167.
  89. , Д. Б. Вычислительные методы теории принятия решений / Д. Б. Юдин. М.: Наука. — 1989.
  90. , В. S. А 5/4 algorithm for two-dimensional packing / В. S. Baker, D. J. Brown, H. P. Katseff // Journal of Algorithms. 1981. — № 2. — P 348 — 368.
  91. Baker, M. Cluster Computing White Paper / M. Baker // UK, Portsmouth: University of Portsmouth, 2000. 119 p.
  92. Baker, B. S. Orthogonal Packings in Two Dimensions / B. S. Baker, E. G. Jr. Coffman, L. Rivest Ronald // SIAM J. Comput., 1980. Vol. 9, № 4. -P. 846−855.
  93. Barsanti, L. Adaptive job scheduling via predictive job resource allocation / L. Barsanti, A. Sodan // Lecture Notes in Computer Science. 2007. -Vol. 4376,-P. 115−140.
  94. Blazewicz, J. Scheduling subject to resource constraints: classification and complexity / J. Blazewicz, J.K. Lenstra // Discrete Applied Mathematics. 1983. — Vol. 5. — P. 11−24.
  95. Bortfeldt, A. Two metaheuristics for strip packing problems / A. Bort-feldt, H. Gehring // 5-th International Conference of the Decision Sciences Institute. Athen, Griechenland, 1999.
  96. Bortfeldt, A. A Parallel Genetic Algorithm for Solving the Container Loading Problem / A. Bortfeldt, G. Hermann // International Transactions in Operational Research. 2002. — Vol. 9, Issue 4. — P. 497.
  97. Brune M. Managing clusters of geographically distributed highperformance computers / M. Brune, J. Gehring, A. Keller, A. Reinefeld // Concurrency Practice and Experience. — 1999. — Vol. 11(15). — P. 887 911.
  98. Burke, E. K. A New Placement Heuristic for the Orthogonal Stock-Cutting Problem / E. K. Burke, G. Kendall, G. Whitwell // Operations Research. 2004. — Vol. 52, № 4. — P. 655−671.
  99. Cirne, W. When the herd is smart aggregate behavior in the selection of job request / W. Cirne, C. Grande, F. Berman // IEEE Transactions in Parallel and Distributed Systems. 2003. — Vol. 14. — P. 181−192.
  100. Cirne, W. A model for moldable supercomputer jobs / W. Cirne, F. Berman // 15th Intl. Parallel & Distributed Processing Symp. 2001.
  101. Cirne, W. A Comprehensive Model of the Supercomputer Workload / W. Cirne, F. Berman // 4th Ann. Workshop Workload Characterization. -2001.
  102. Coffman, E. G. Performance bounds for level-oriented two-dimensional packing algorithms / E.G. Coffman, M.R. Garey, D.S. Johnson et al. // SIAM Journal on Computing. 1980. — Vol. 9. — P. 808−826.
  103. Dagli, C. H. Simulated annealing approach for solving stock cutting problem Systems / C. H. Dagli, A. Hajakbari // Man and Cybernetics. Conference Proceedings, IEEE International Conference. 1990. — Vol. 1. — P. 221−223.
  104. Davis, L. Job shop scheduling with genetic algorithms / L. Davis // In proceedings of an International Conference on Genetic Algorithms and their Applications, Pittsburgh, Lawrence Erlbaum Associates: 1985. P. 136−140.
  105. Devis, E.W. A Comparison of Heuristic and Optimum Solutions in Resource-Constrained Project Scheduling / E.W. Devis, J.H. Patterson // Management Science. 1975. — Vol. 21, № 8. — P. 944−955.
  106. Devis, E.W. An algorithm for optimal project scheduling under multiple resource constraints / E.W. Devis, G.E. Heidorn // Management Science. 1971. — Vol 17, № 12. — P. 803−817.
  107. Downey A.B. A Parallel Workload Model and Its Implications for Processor Allocation // 6th Intl. Symp. High Performance Distributed Comput., 1997.
  108. Feitelson, D. G. Theory and practice in parallel job scheduling / Dror G. Feitelson, Larry Rudolph, Uwe Schwiegelshohn et al. // Job Scheduling Strategies for Parallel Processing. 1997. — Vol. 1291. — P. 1−34. — ISBN: 978−3-540−63 574−1.
  109. Feitelson, D.G. Improved utilization and responsiveness with gang scheduling in Job Scheduling Strategies for Parallel Processing / D.G. Feitelson, M.A. Jette // Lecture Notes in Computer Science. 1997. — Vol. 1291. -P. 238−261.
  110. Feitelson, D.G. Metrics and benchmarking for parallel job scheduling / D.G.Feitelson, L. Rudolph // Lecture Notes in Computer Science. 1998. -Vol. 1459.-P. 1−24.
  111. Feitelson, D.G. Toward convergence in job schedulers for parallel supercomputers / D.G.Feitelson, L. Rudolph // Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science. 1996. — Vol. 1162.-P. 1−26.
  112. Feitelson, D.G. Packing schemes for gang scheduling / D.G.Feitelson // Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science. 1996. — Vol. 1162. — P. 89−110.
  113. Flynn, M. Very high-speed computing system / M. Flynn // Proc. of IEEE, 1966.-№ 54.-P. 1901−1909.
  114. Flynn, M. Some Computer Organisations and Their Effectiveness // IEEE Trans. Computers. 1972. — Vol. 21, № 9. — P. 948−960.94
  115. Fox, M.S. ISIS a Knowledge-based system for factory scheduling / M.S. Fox, S.F. Smith // Expert Systems. — 1984. — Vol. 1, № 1. — P. 25−49.
  116. Garey, M. Bounds for multiprocessor scheduling with resource constraints / M. Garey, R. Graham // SIAM Journal on Computing. 1975. — Vol. 4, № 2.-P. 187−200.
  117. Garey, M. Computers and intractability: a guide to the theory of NP-Completeness / M. Garey, D. Johnson. New York: W. H. Freeman and Co., 1990. — 338 p.
  118. Gilmore, P. C. A Linear Approach to the Cutting-Stock Problem / P. C. Gilmore, R. E. Gomery// Operations Research. 1961. — Vol 9. -P. 849 859.
  119. Harvey, W.D. Limited discrepancy search / W. D. Harvey, M. L. Ginsberg. CIRL, University of Oregon, Eugene, OR, USA. — 1995.
  120. Hildum, D. Flexibility in a knowledge-based system for solving dynamic resource-constrained scheduling problems. Umass CMPSCI Technical Report N.94−77 / D. Hildum. University of Massachusetts, Amherst. -1994.
  121. Hilliard M.R. Machine Learning Applications to Job Shop Scheduling / M.R. Hilliard, et al. // In proceedings of the AAAI-SIGMAN Workshop on Production Planning and Scheduling. New York: ACM, 1988. P. 728−737.
  122. Hopper, E. An Empirical Investigation of Meta-Heuristic and Heuristic Algorithms for a 2D Packing Problem / E. Hopper, B.C.H. Turton // European Journal of Operational Research. 2001. — Vol. 128, № 1. — P. 3457.
  123. Hopper, E. Problem Generators for Rectangular Packing Problems / E. Hopper, B.C.H. Turton // Studia Informatica Universalis. 2002. — Vol. 2, № l.-P. 123−136.
  124. Husbands, P. Genetic algorithms for scheduling. Technical Report N.89/ P. Husbands. AISB Quarterly. — 1996.
  125. Jackson, D. Core algorithms of the Maui scheduler / D. Jackson, Q. Snell, M. Clement // Lecture Notes in Computer Science. 2001. — Vol. 2221. -P. 87−102.
  126. Kenyon, C. A Near-optimal Solution to a Two-dimensional Cutting Stock Problem / C. Kenyon, E. Remila // Mathematics of Operations Research 25. -2000. Vol. 4. — P. 645−656.
  127. Land, A.H. An autmatic method of solving discrete programming problems
  128. A. H. Land, A. G. Doig // Econometrica. 1960. — Vol. 28 — P. 497−520.
  129. Lawler, E.L. Branch and Bound methods: a survey / E.L. Lawler, D.E. Wood // Operations Research. 1966. — Vol. 14, № 4. — P. 699−719.
  130. Lodi, A. Two-dimensional packing problems: a survey / A. Lodi, S. Mar-tello, M. Monaci // European Journal of Operational Research. 2002. -Vol. 141.-P. 241−252.
  131. Neumann, K. Stochastic project networks temporal analysis, scheduling and cost minimization / K. Neumann. — Berlin: Springer-Verlag, 1990.
  132. Patterson, J. H. A comparison of exact approaches for solving the multiple constrained resource, project scheduling problem / J. H. Patterson // Management Science. 1984. — Vol. 30, № 7. — P. 854−867.
  133. Panwalker, S. A survey of scheduling rules / S. Panwalker, W. Iskander // Operations Research. 1997. — Vol. 25, № 1. — P. 45−61.
  134. Parallel workloads archive Электронный ресурс. // Режим доступа: http://www.es.huji.ас.il/labs/parallel/workload/ (дата обращения: 25.01.2012).
  135. Poshyanonda, P. Two dimensional nesting problem: artificial neural network and optimization approach Neural Networks / P. Poshyanonda, A. Bahrami, C. H. Dagli // International Joint Conference. 1992. — Vol.4. -P. 572−577.
  136. Schwiegelshohn, U. Analysis of First-Come-First-Serve Parallel Job Scheduling / U. Schwiegelshohn, R. Yahyapour // In proceedings of the 9th SIAM Symposium on Discrete Algorithms. 1998. — P. 629−638.
  137. Shmueli, E. Backfilling with lookahead to optimize the packing of parallel jobs / E. Shmueli, D. G. Feitelson // J. Parallel & Distributed Comput. -2005. Vol. 65, № 9. — P. 1090−1107.
  138. Steuer, R. E. Multiple Criteria Optimization, Theory, Computation and Application / R. E. Steuer. Krieger Pub Co, 1986. — 546 p.
  139. Wang, P. Y. Data set generation for rectangular placement problems / P. Y. Wang, C.L. Valenzuela // European Journal of Operational Research. -2001.-Vol. 134.-P. 378−391.
Заполнить форму текущей работой

Сессия? Спокойно!