Организация функционирования распределенных вычислительных систем в режиме обработки наборов масштабируемых задач тема диссертации и автореферата по ВАК РФ 05.13.15, кандидат технических наук Ефимов, Александр Владимирович

• Ефимов, Александр Владимирович
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Ефимов, Александр Владимирович

СОДЕРЖАНИЕ

ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ

ВВЕДЕНИЕ

ГЛАВА 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

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 Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЯ

Приложение 1 Сводная таблица алгоритмов

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

вычислительной системы

Приложение 3 Исходные тексты программ

ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ

АЛУ - арифметико-логическое устройство. БИС - большая интегральная схема. ВМ - вычислительный модуль. ВС - вычислительная система.

ИФПСОРАН - Федеральное государственное бюджетное учреждение науки Институт физики полупроводников им. A.B. Ржанова Сибирского отделения Российской академии наук. ЛК - локальный коммутатор. ЛП - локальная память.

МКМД - Множественный поток команд и множественный поток данных. МКОД - Множественный поток команд и одиночный поток данных. НИР - Научно-Исследовательская работа.

ОКМД - Одиночный поток команд и множественный поток данных. ОКОД - Одиночный поток команд и одиночный поток данных. ОС - операционная система. ПК - персональный компьютер. ПО - программное обеспечение.

СО АН СССР - Сибирское отделение Академии наук Союза Советских Социалистических Республик. СУ - системное устройство.

ФГОБУ ВПО "СибГУТИ" - Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования "Сибирский государственный университет телекоммуникаций и информатики". ЦПВТ - Центр параллельных вычислительных технологий. ЭВМ - электронная вычислительная машина. ЭМ - элементарная машина. ЭП - элементарный процессор. API - Application Programming Interface.

BFDH - Best-Fit Decreasing Height. FCFS - First Come First Serve. JSDL - Job Submission Description Language. LJF - Longest-Job-First.

MIMD - Multiple Instruction stream / Multiple Data stream. MISD - Multiple Instruction stream / Single Data stream. MOJOS - Moldable Jobs Scheduling MPI - Message Passing Interface. SAT - SATisfiability.

SIMD - Single Instruction stream / Multiple Data stream. SISD - Single Instruction stream / Single Data stream. SJF - Shortest-Job-First.

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

ВВЕДЕНИЕ

Актуальность работы. Возрастающая потребность в решении сложных задач науки, техники и экономики привела к созданию распределённых высокопроизводительных вычислительных систем (ВС). В общем случае распределённая ВС - это композиция множества элементарных машин (ЭМ) и сети межмашинных связей. Элементарная машина - это основной функциональный и структурный элемент ВС; конфигурация ЭМ допускает варьирование в широких пределах - от процессорного ядра до ЭВМ или специализированного ускорителя. Все основные ресурсы распределённых ВС (как аппаратурные, так и программные) являются логически и технически рассредоточенными. Количество ЭМ в распределённых ВС допускает варьирование от нескольких единиц до сотен тысяч (например, в системе 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-13534, 08-07-00022, 09-07-00095, 11-07-00109, грантом мэрии г. Новосибирска молодым учёным № 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 страницах.

Содержание работы.

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

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

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

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

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

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

Заключение диссертации по теме «Вычислительные машины и системы», Ефимов, Александр Владимирович

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Ефимов, Александр Владимирович, 2012 год

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

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. Ефимов, А. В. Организация функционирования распределенных вычислительных систем при обработке наборов масштабируемых задач / А. В. Ефимов, С. Н. Мамойленко, Е. Н. Перышкова // Вестник ТГУ: Управление, вычислительная техника и информатика. - Томск : Изд-во НТЛ, 2011. - № 2(15). - С. 51-60. - ISSN 1998-8605.

29. Ефимов, А. В. Генетический алгоритм организации мультипрограммного функционирования распределенных вычислительных систем / А. В. Ефимов // Пятая сибирская конференция по параллельным и высокопроизводительным вычислениям: материалы конференции. - Томск : Изд-во ТГУ, 2010. - С. 136 - 139.

30. Ефимов, А. В. Формирование расписаний выполнения параллельных адаптирующихся программ на распределенных вычислительных системах / А. В. Ефимов // Информационные технологии: материалы XLVIII международной научно-технической конференции «Студент и научно-технический прогресс». - Новосибирск : Изд-во НГУ, 2010. - С. 297.

31. Ефимов, А. В. Моделирование алгоритмов формирования расписаний решения масштабируемых задач на распределённых вычислительных системах / А. В. Ефимов, С. Н. Мамойленко, Е. Н. Максимова // XIII Российская конференция с участием иностранных ученых «Распределенные информационные и вычислительные ресурсы» (DICR-2010): программа и тезисы докладов. - Новосибирск, 2010. -С. 24.

32. Ефимов, А. В. Анализ эффективности планировщика MAUI на распределенных вычислительных системах / А. В. Ефимов // Материалы Российской научно-технической конференции «Информатика и проблемы телекоммуникаций». - Новосибирск : Изд-во СибГУТИ, 2009. -С. 122- 123.

33. Ефимов, А. В. Генетический алгоритм распределения набора задач с нефиксированными параметрами по машинам распределенной вычислительной системы / А. В. Ефимов // Материалы XLVII международной научно-технической конференции «Студент и научно-технический прогресс». - Новосибирск : Изд-во НГУ, 2009. - С. 206.

34. Ефимов, А. В. Генетический алгоритм распределения параллельных задач с нефиксированными параметрами по машинам распределенной вычислительной системы / A.B. Ефимов, С.Н. Мамойленко // II сессия научной школы-практикума молодых ученых и специалистов «Технологии высокопроизводительных вычислений и компьютерного моделирования». - 2009. - Режим доступа:

http://еscience.ifmo.ru/files/hpc2009/thesises.pd f - Загл. с экрана.

35. Жук, С. Н. Онлайновый алгоритм упаковки прямоугольников в несколько полос с гарантированными оценками точности / С. Н. Жук // Труды Института Системного программирования: Методы синтеза и анализа. - 2007. - Т. 12, - С. 7-16.

36. Калитин, С. С. Управление процессами в операционных системах UNIX и WINDOWS NT: Учебное пособие по курсу "Операционные системы" / С. С. Калитин, Л. В. Гераскина. - М. : МЭИ, 2000. - 44 с.

37. Каляев, И. А. Реконфигурируемые мультиконвейерные вычислительные структуры / И. А. Каляев ; под. ред. И. А. Каляева. - Ростов-н/Д. : ЮНЦ РАН, 2008. - 320 с.

38. Кейслер, С. Проектирование операционных систем для малых ЭВМ / С. Кейслер ; пер. с англ. - М. : Мир, 1986. - 680 с.

39. Коваленко, В. Н. Управление заданиями в распределённой среде и протокол резервирования ресурсов / В. Н. Коваленко, А. В. Орлов. -М. : Препринт ИПМ №1, 2002. - 25 с.

40. Коваленко, В. Н. Управление параллельными заданиями в гриде с неотчуждаемыми ресурсами / В. Н. Коваленко, Е. И. Коваленко, Д.

A. Корягин [и др.]. - М. : Препринт ИПМ РАН 63, 2007. - С. 1-28.

41. Коваленко, Е. И. Расширение возможностей кластерных систем управления для информащионного обслуживания грид-диспетчера / Е. И. Коваленко, О. Н. Шорин // Труды международной конференции "Распределенные вычисления и Грид-технологии в науке и образовании". - Дубна, 2004. - С. 144-147

42. Конвей, Р. В. Теория расписаний / Р. В. Конвей, В. Л. Максвелл, Л.

B. Миллер. - М.: Наука, 1975. - 360 с.

43. Корнеев, В. В. Архитектура вычислительных систем с программируемой структурой / В. В. Корнеев. - Новосибирск : Наука, 1985. -164 с.

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

45. Корнеев, В. В. Параллельные вычислительные системы / В. В. Корнеев. - М.: Нолидж, 1999. - 320 с.

46. Косарев, Ю. Г. Математическое обеспечение однородных вычислительных систем / Ю. Г. Косарев, Н. Н. Миренков // Вычислительные системы. - 1974. - Вып. 58. - С. 61-79.

47. Коффман, Э. Г. Теория расписаний и вычислительные машины / Л. Дж. Бруно, Р. Л. Грэхем, В. Г. Коглер [и др.] ; под ред. Б.А. Головкина, пер. с англ. В.М. Амочкина, М.: Изд-во «Наука», 1984. - 336 С.

48. Кузюрин, Н. Н. Вероятностный анализ шельфовых алгоритмов упаковки прямоугольников в полосу / Н. Н. Кузюрин, А. И. Поспелов // Дискретная математика. - 2006. - Т. 18, № 1. - С. 76-90.

49. Курейчик, В. М. Параллельные генетические алгоритмы: обзор и состояние проблемы / В.М. Курейчик, Д.С.Кныш // Известия РАН. Теория и системы управления. - 2010. - № 4 - С. 72-82.

50. Курносов, М. Г. Планирование выполнения параллельных программ набора на распределенной вычислительной системе / М. Г. Курносов, С. В. Рыбалко // Материалы ХЬУ Международной научной студенческой конференции "Студент и научно-технический прогресс". -Новосибирск: Изд-во НГУ, 2007. - С. 42-43.

51. Курносов, М. Г. Синтез расписания запуска параллельных программ на распределенной вычислительной системе / М. Г. Курносов, С. В. Рыбалко // Материалы Российской научно-технической конференции "Информатика и проблемы телекоммуникаций". - Новосибирск : Изд-во СибГУТИ, 2007. - С. 272-274.

52. Лацис, А. Как построить и использовать суперкомпьютер / А. Лацис. - М. : Бестселлер, 2003. - 240 с.

53. Максимова, Е. Н. Параллельный генетический алгоритм формирования расписания решения параллельных адаптирующихся задач на распределенных вычислительных системах / Е. Н. Максимова, С. Н. Мамойленко, А. В. Ефимов // Информатика и проблемы телекомму-

никаций: материалы Российской научно-технический конференции. - Новосибирск : Изд-во ГОУ ВПО «СибГУТИ», 2010. - Т. 1. - С. 163.

54. Максимова, Е. Н. Эволюционный подход к формированию расписаний выполнения адаптирующихся программ на распределенной вычислительной системе / Е. Н. Максимова, А. В. Ефимов, С. Н. Ма-мойленко // Новые информационные технологии в исследовании сложных структур: тезисы докладов Восьмой Российской конференции с международным участием. - Томск : HTJI, 2010. - С. 17.

55. Максимова, Е. Н. Параллельный генетический алгоритм формирования расписаний решения масштабируемых задач на распределенных вычислительных системах / Е. Н. Максимова, А. В. Ефимов, С. Н. Мамойленко // XI Всеросийская конференция молодых ученых по математическому моделированию и информационным технологиям: программа и тезисы докладов. - Новосибирск : Изд-во ИВТ СО РАН, 2010.-С. 32.

56. Мамойленко, С. Н. Применение генетических алгоритмов для распе-ределния наборов задач по машинам вычислительной системы / С. Н. Мамойленко, Н. А. Медведева, А. Ю.Поляков // Материалы Международной научно-технической конференции "Многопроцессорные вычислительные и управляющие системы", 2007. - С. 70-75

57. Мамойленко, С. Н. Формирование расписания выполнения набора параллельных адаптирующихся задач на распределенных вычислительных системах / С. Н. Мамойленко, А. В. Ефимов // Материалы международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы» (МВУС - 2009).-Таганрог : Изд-во ТИИ ЮФУ, 2009. - Т. 1. - С. 200 - 202.

58. Мамойленко, С. Н. Генетический алгоритм распределения параллельных задач с нефиксированными параметрами по машинам распределенной вычислительной системы / С. Н. Мамойленко, А. В. Ефимов // Программа и тезисы докладов «Пятая сибирская конфе-

85

ренция по параллельным и высокопроизводительным вычислениям». - Томск : Изд-во ТГУ, 2009. - С. 69 - 71.

59. Мамойленко, С. Н. Применение эволюционных алгоритмов для распределения набора задач с нефиксированными параметрами по машинам распределенной вычислительной системы / С. Н. Мамойленко, А. Ю. Поляков, А. В. Ефимов [и др.] // Материалы Российской научно-технической конференции «Информатика и проблемы телекоммуникаций». - Новосибирск : Изд-во СибГУТИ, 2008. - Т. 1. -С. 144 - 145.

60. Мамойленко, С. Н. Применение эволюционных алгоритмов для распределения набора задач с нефиксированными параметрами по машинам распределенной вычислительной системы / С. Н. Мамойленко, А. Ю. Поляков, А. В. Ефимов [и др.] // Тезисы докладов Седьмой Российской конференции с международным участием «Новые информационные технологии в исследовании сложных структур». -Томск : НТЛ, 2008. - С. 70.

61. Мамойленко, С. Н. Алгоритмы планирования решения масштабируемых задач на распределённых вычислительных системах / С. Н. Мамойленко, А. В. Ефимов // Вестник СибГУТИ. - Новосибирск : Изд-во «СибГУТИ», 2010. - № 2. - С. 66 - 78.

62. Мамойленко, С. Н. Организация мультипрограммного режима обработки набора параллельных адаптирующихся программ на распределенных вычислительных системах / С. Н. Мамойленко, А. В. Ефимов // Информатика и проблемы телекоммуникаций: материалы Российской научно-технический конференции. - Новосибирск : Изд-во ГОУ ВПО «СибГУТИ», 2010. - Т. 1. - С. 166.

63. Мартишин, С. А. Упаковка прямоугольников в полосу модифицированным методом Нелдера-Мида с использованием генетического алгоритма / С. А.Мартишин, М. В. Храпченко // Труды Института системного программирования РАН. - 2010. - Т. 19. - С. 135-156.

86

64. Миренков, Н. Н. Параллельное программирование для многомодульных вычислительных систем / Н. Н. Миренков. - М. : Радио и связь, 1989.-319 с.

65. Монахов, О. Г. Параллельные системы с распределенной памятью: структуры и организация взаимодействий / О. Г. Монахов, Э. А. Монахова. - Новосибирск : Изд-во СО РАН, 2000. - 242 с.

66. Монахов, О. Г. Параллельные системы с распределенной памятью: управление ресурсами и заданиями / О. Г. Монахов, Э. А. Монахова. - Новосибирск : Изд-во ИВМиМГ СО РАН, 2001.- 168 с.

67. Мухачева, Э. А. Генетический алгоритм блочной структуры в задачах двумерной упаковки / Э.А. Мухачева, А. С. Мухачева, А. В. Чиглинцев // Информационные технологии. Машиностроение. - М., 1999. -№11. - С. 13-18.

68. Мухачева, A.C. Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения. / А. С. Мухачева, А. В. Чиглинцев, М.А. Смагин [и др.] // Приложение к журналу Информационные технологии. Машиностроение. - М., 2001. - №10. - 24 с.

69. Ногин, В. Д. Принятие решений в многокритериальной среде: количественный подход / В. Д. Ногин. - М. : Физматлит, 2002. - 176 с.

70. Олифер, В.Г. Сетевые операционные системы / В. Г. Олифер, Н. А. Олифер. - СПб. : Питер, 2001. - 544 с.

71. Опарин Г.А. Булевы модели синтеза параллельных планов решения вы-числительных задач / Г.А. Опарин, А.П. Новопашин // Вестник НГУ. Серия: Информационные технологии. - 2008. - Том 6, Вып. 1. -С. 53-59.

72. Операционная система СМ ЭВМ РАФОС: Справочник / J1. И. Валиков, Г. В. Вигдорчик, А. Ю. Воробьев [и др.]. - М. : Финансы и статистика, 1984. - 207 с.

73. Основы теории оптимизации / Д. В. Ногин [и др.]. - М. : Высшая школа, 1986. - 384 с.

74. Павский, В. А. Организация функционирования однородных вычислительных систем и стохастическое программирование / В. А. Павский, В. Г. Хорошевский // Вычислительные системы. -1975.-Вып. 63.-С. 3-16.

75. Панфилов, И. В. Вычислительные системы / И. В. Панфилов, А. М. Половко. - М. : Изд-во "Советское радио", 1980. - 302 с.

76. Поспелов, Д. А. Введение в теорию вычислительных систем / Д. А. Поспелов. - М. : Изд-во "Советское радио", 1972. - 280 с.

77. Сайт Центра параллельных вычислительных технологий ФГОБУ ВПО «СибГУТИ» [Электронный ресурс]. - Режим доступа: http: //cpct. sibsutis . ru (дата обращения: 25.01.2012).

78. Сайт проекта Survey on two-dimensional packing [Электронный ресурс]. - Режим доступа: http://www.ese.liv.ас.uk/~epa/survey.pdf свободный (дата обращения: 25.01.2012).

79. Сайт проекта Cluster resources: Products - Maui Cluster Scheduler [Электронный ресурс]. - Режим доступа : http://www.clusterresources.com/pages/products/ma ui-cluster-scheduler.php, свободный (дата обращения: 25.01.2012).

80. Сайт проекта Windows НРС Server 2008 I Microsoft Supercomputing I Supercomputers [Электронный ресурс]. - Режим доступа: http://www.microsoft.com/hpc, свободный (дата обращения: 25.01.2012).

81. Сайт проекта IBM Redbooks I Workload Management with LoadLeveler [Электронный ресурс]. - Режим доступа http://www.redbooks.ibm.com/abstracts/sg2 46 038.ht

ml, свободный (дата обращения: 25.01.2012).

88

82. Сайт проекта Grid Computing I Oracle Grid Engine I Software I Sun Microsystems [Электронный ресурс]. - Режим доступа: http://www.sun.com/software/sge, свободный (дата обращения: 25.01.2012)

83. Сайт проекта PBS Works - Enabling On-Demand Computing [Электронный ресурс]. - Режим доступа: http://www.openpbs.org, свободный (дата обращения: 25.01.2012).

84. Сайт проекта TORQUE [Электронный ресурс]. - Режим доступа: http://www.clusterresources.com/pages/products/to rque-resource-manager.php, свободный (дата обращения 25.01.2012).

85. Сайт проекта Тор500 [Электронный ресурс]. - Режим доступа: http : / /www. top50 0 . org, свободный (дата обращения 25.01.2012).

86. Седельников, М.С. Алгоритмы распределения набора задач с переменными параметрами по машинам вычислительной системы /М. С. Седельников // Автометрия. - 2006. - Т. 42. - № 1. - С. 68-76.

87. Смагин, С.И. Генетический алгоритм составления расписания выполнения параллельных заданий в распределенной вычислительной системе / С. И. Смагин, Т. С. Шаповалов // Вычислительные технологии. - 2010. - Т. 15. - № 5. - С. 107-122.

88. Столингс, В. Операционные системы / В. Столингс ; 4-е изд. - М. : Вильяме, 2002. - 848 с.

89. Сырков, Б.Ю. Программное обеспечение мультитранспьютерных систем / Б. Ю. Сырков, С. В. Матвеев. - М. : Диалог-МИФИ, 1992. -150 с.

90. Таненбаум, Э. Архитектура компьютера / Э. Таненбаум. - СПб. : Питер, 2002. - 704 с.

91. Таненбаум, Э. Распределенные системы: принципы и парадигмы / Эндрю Таненбаум, Стен М. Ван ; пер. с англ. А. Леонтьев. - СПб. : Питер, 2003. - 877 с.

92. Таненбаум, Э. Современные операционные системы / Э. Таненбаум ; 2-е изд. - СПб. : Питер, 2002. - 1040 с.

93. Taxa, X. А. Введение в исследование операций, 7-е издание / X. А. Taxa ; пер. с англ. под ред. А. А. Минько. - М. : Издательский дом "Вильяме", 2005.-912 с.

94. Титаренко, С. П. Управление процессами в современных операционных системах / С. П. Титаренко. - Белгород : БелГТАСМ, 1999. - 38 с.

95. Топорков, В. В. Модели распределенных вычислений / В. В. Топорков. - М. : ФИЗМАТЛИТ, 2004. - 320 с.

96. Фурсиков, А. В. Оптимальное управление распределенными системами. Теория и приложения / А. В. Фурсиков. - Новосибирск, 1999. -40 с.

97. Хетагуров, Я. А. Основы проектирования управляющих вычислительных систем / Я. А. Хетагуров. - М. : Радио и связь, 1991. - 287 с.

98. Хорошевский, В. Г. Вычислительная система МИКРОС / В. Г. Хорошевский. - Новосибирск: Препринт ИМ СО АН СССР 38 (ОВС-19), 1983.-52 с.

99. Хорошевский, В. Г. Инженерный анализ функционирования вычислительных машин и систем / В. Г. Хорошевский. - М. : Радио и связь, 1987.-256 с.

100. Хорошевский, В. Г. Архитектура вычислительных систем / В. Г. Хорошевский. - М. : МГТУ им. Н. Э. Баумана, 2008. - 520 с.

101. Хорошеский, В. Г. Масштабируемый инструментарий параллельного мультипрограммирования пространственно-распределенных вычислительных систем / В. Г. Хорошевский, М. Г. Курносов, С. Н. Ма-мойленко, К. В. Павский, А. В. Ефимов, А. А. Пазников, Е. Н.

90

Перышкова // Вестник СибГУТИ. - Новосибирск : Изд-во «СибГУ-ТИ», 2011.-№ 11.-С. 3-18.

102. Хорошевский, В. Г. Планирование выполнения параллельных программ с нефиксированными параметрами на распределенных вычислительных системах / В. Г. Хорошевский, С. Н. Мамойленко, А. В. Ефимов // Высокопроизводительные вычислительные системы (ВПВС-2010): материалы седьмой международной научной молодежной школы. - Таганрог : Изд-во ТТИ ЮФУ, 2010. - С. 95 - 100. -ISBN 978-5-8327-0382-4.

103. Хорошевский, В. Г. Архитектурные концепции, анализ и организация функционирования вычислительных систем с программируемой структурой / В. Г. Хорошевский, С. Н. Мамойленко, М. Г. Курносов // Труды Международной научно-технической конференции "Информационные технологии и математическое моделирование систем". - М. : Изд-во РАН, 2008.

104. Хорошевский, В. Г. Планирование выполнения параллельных программ с нефиксированными параметрами на распределенных вычислительных системах / В. Г. Хорошевский, С. Н. Мамойленко, А. В. Ефимов // Суперкомпьютерные технологии: разработка, программирование, применение: материалы международной научно-технической конференции. - Таганрог : Изд-во ТТИ ЮФУ, 2010. -Т.2. - С. 97 - 101. - ISBN 978-5-8327-0383-1.

105. Хэвиленд, К. Системное программирование в UNIX. Руководство программиста по разработке ПО / К. Хэвиленд, Д. Грэй, Б. Салама ; пер. с англ. - М.: ДМК Пресс, 2000. - 368 с.

106. Цикритзис, Д. Операционные системы / Д. Цикритзис, Ф. Бернстайн. - М.: Мир, 1977.-336 с.

107. Шаповалов, Т. С. Генетический алгоритм составления расписаний для распределенных гетерогенных вычислительных систем / Т. С.

Шаповалов, В. В. Пересветов // Вычислительные методы и программирование. - 2009. - Т. 10. - С. 159-167.

108. Юдин, Д. Б. Вычислительные методы теории принятия решений / Д. Б. Юдин. - М. : Наука. - 1989.

109. Baker, В. S. А 5/4 algorithm for two-dimensional packing / В. S. Baker, D. J. Brown, H. P. Katseff // Journal of Algorithms. - 1981. - № 2. - P 348 - 368.

110. Baker, M. Cluster Computing White Paper / M. Baker // UK, Portsmouth: University of Portsmouth, 2000. - 119 p.

111. 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.

112. 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.

113. Blazewicz, J. Scheduling subject to resource constraints: classification and complexity / J. Blazewicz, J.K. Lenstra // Discrete Applied Mathematics. - 1983. - Vol. 5. - P. 11-24.

114. 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.

115. 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.

116. 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. 887911.

117. 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.

118. 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.

119. Cirne, W. A model for moldable supercomputer jobs / W. Cirne, F. Berman // 15th Intl. Parallel & Distributed Processing Symp. - 2001.

120. Cirne, W. A Comprehensive Model of the Supercomputer Workload / W. Cirne, F. Berman // 4th Ann. Workshop Workload Characterization. -2001.

121. 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.

122. 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.

123. 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.

124. 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.

125. 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.

126. Downey A.B. A Parallel Workload Model and Its Implications for Processor Allocation // 6th Intl. Symp. High Performance Distributed Comput., 1997.

127. Dutot, Pierre-François. Bi-criteria algorithm for scheduling jobs on cluster platforms / Pierre-François Dutot, Lionel Eyraud, Grégory Mounié [et al.] // Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, Barcelona, Spain. - 2004. - P. 125 - 132. -ISBN: 1-58113-840-7.

128. 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-63574-1.

129. 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.

130. 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.

131. 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.

132. 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.

133. Flynn, M. Very high-speed computing system / M. Flynn // Proc. of IEEE, 1966.-№54.-P. 1901-1909.

134. Flynn, M. Some Computer Organisations and Their Effectiveness // IEEE Trans. Computers. - 1972. - Vol. 21, № 9. - P. 948-960.

94

135. 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.

136. Garey, M. Bounds for multiprocessor scheduling with resource constraints / M. Garey, R. Graham // SIAM Journal on Computing. - 1975. - Vol. 4, №2.-P. 187-200.

137. 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.

138. Gilmore, P. C. A Linear Approach to the Cutting-Stock Problem / P. C. Gilmore, R. E. Gomery// Operations Research. - 1961. - Vol 9. -P. 849859.

139. Goodman, E.D A Genetic Algorithm Approach to Compaction, Bin Packing, and Nesting Problems, Release 3.01 / E.D Goodman, A.Y. Tetel-baum, V.M. Kureichik // Intelligent Systems Laboratory and Case Center for Computer-Aided Engineering and Manufacturing, Michigan State University. - 1995. - P. 80.

140. Harvey, W.D. Limited discrepancy search / W. D. Harvey, M. L. Ginsberg. - CIRL, University of Oregon, Eugene, OR, USA. - 1995.

141. 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.

142. 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.

143. 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.

144. Hopper, E. Problem Generators for Rectangular Packing Problems / E. Hopper, B.C.H. Turton // Studia Informática Universalis. - 2002. - Vol. 2, № l.-P. 123-136.

145. Husbands, P. Genetic algorithms for scheduling. Technical Report N.89/ P. Husbands. - AISB Quarterly. - 1996.

146. 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.

147. 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.

148. Land, A.H. An autmatic method of solving discrete programming problems

/ A. H. Land, A. G. Doig // Econometrica. - 1960. - Vol. 28 - P. 497-520.

149. Lawler, E.L. Branch and Bound methods: a survey / E.L. Lawler, D.E. Wood // Operations Research. - 1966. - Vol. 14, №4. - P. 699-719.

150. 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.

151. Neumann, K. Stochastic project networks - temporal analysis, scheduling and cost minimization / K. Neumann. - Berlin: Springer-Verlag, 1990.

152. 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.

153. Panwalker, S. A survey of scheduling rules / S. Panwalker, W. Iskander // Operations Research. - 1997. - Vol. 25, № 1. - P. 45-61.

154. Parallel workloads archive [Электронный ресурс] // Режим доступа: http://www.es.huji.ас.il/labs/parallel/workload/ (дата обращения: 25.01.2012).

155. 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.

156. Rohlfshagen, P. A genetic algorithm with exon shuffling crossover for hard bin packing problems / P Rohlfshagen, J.A. Bullinaria.// Proceedings of the 9th annual conference on Genetic and evolutionary computation.-ACM New York, NY, USA, 2007.-pp.1365 - 1371

157. 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.

158. 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.

159. Srinivasan, S. Characterization of backlling strategies for parallel job scheduling / S. Srinivasan, R. Kettimuthu, V. Subramani, S. Sadayappan // In proceedings of the International Conference on Parallel Processing Workshops, IEEE Computer Society Press, Los Alamitos: 2002. - P. 514519.

160. Steuer, R. E. Multiple Criteria Optimization, Theory, Computation and Application / R. E. Steuer. - Krieger Pub Co, 1986. - 546 p.

161. 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.