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

Мамойленко Сергей Николаевич

ОРГАНИЗАЦИЯ ФУНКЦИОНИРОВАНИЯ РАСПРЕДЕЛЁННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ В МУЛЬТИЗАДАЧНЫХ РЕЖИМАХ

Специальность 05.13.15 — Вычислительные машины, комплексы и компьютерные сети

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

12 дпр ш

Новосибирск — 2012

005019889

005019889

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

Работа выполнена в Федеральном государственном образовательном бюджетном учреждении высшего профессионального образования «Сибирский государственный университет телекоммуникаций и информатики» Федерального агентства связи.

Научный консультант: доктор технических наук профессор

член-корреспондент РАН заслуженный деятель науки РФ Хорошевский Виктор Гаврилович

доктор физико-математических наук профессор академик РАН Шокин Юрий Иванович директор

Института вычислительных технологий СО РА доктор технических наук профессор Глинский Борис Михайлович заведующий лабораторией «Сибирский суперкомпьютерный центр» Института вычислительной математики и математической геофизики СО РАН

доктор технических наук профессор Цапко Геннадий Павлович заведующий Кафедрой автоматики и компьютерных систем Национального исследовательского Томского политехнического университета Научно-исследовательский институт многопроцессорных вычислительных систем имени академика A.B. Каляева Федерального государственного автономного образовательного учреждения высшего профессионального образования "Южный федеральный университет"

Защита состоится « 29 » мая 2012 г. в 1500 часов на заседании диссертационного совета Д 219.005.02 при ФГОБУ ВПО «Сибирский государственный университет телекоммуникаций и информатики» по адресу: 630102, г. Новосибирск, ул. Кирова, д. 86, ауд. 625.

С диссертацией можно ознакомиться в библиотеке ФГОБУ ВПО «СибГУТИ». Автореферат разослан 16 марта 2012 г. Учёный секретарь

диссертационного совета Д 219.005.02

кандидат технических наук, доцент И. И. Резван

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

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

Актуальность работы. Распределённые вычислительные системы (ВС) являются современным инструментарием обработки информации (список Тор500 (Ноябрь, 2011) суперкомпьютеров мира). В Российской Федерации технологии и программное обеспечение распределённых и высокопроизводительных ВС относят к критически важным (указ Президента Российской Федерации от 7 июля 2011 г. № 899).

Исследования в области распределённых ВС ведутся с середины XX столетия. С тех пор в нашей стране и за рубежом выполнен ряд фундаментальных работ, посвящённых проблемам организации высокопроизводительных вычислительных средств: проведены исследования но теории функционирования и построению оптимальных (макро)структур ВС, проработаны многие аспекты создания программного обеспечения, исследован широкий круг задач, допускающих эффективную реализацию на распределённых ВС. Построены отечественные вычислительные системы с программируемой структурой: «Минск 222», СУММА, МИНИМАКС, МИКРОС, МВС, СКИФ и др.

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

B. С. Бурцев, В. В. Васильев, В. М. Глушков, В. Ф. Евдокимов, Э. В. Евреинов, А. В. Забродин, В. П. Иванников, М. Б. Игнатьев, А. В. Каляев, И. А. Каляев, JI.H. Королёв, С. А. Лебедев, А. О. Лацис, В. К. Левин, И. И. Левин, Г. И. Марчук, Ю.И. Митропольский, Д. А. Поспелов, И. В. Прангишвили, Д.В. Пузанков, Г.Е. Пухов, Г.Г. Рябов, A.A. Самарский, В.Б. Смолов, А. Н. Томилин, Я. А. Хетагуров, В. Г. Хорошевский, Б. Н. Четверушкин, Ю. И. Шокин, Н. Н. Яненко, S. Cray, М. Flynn, D. Feitelson, I. Foster, D. Hillis,

C. Kesselman, DL. Slotnick, A. Tanenbaum и другие.

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

Задачи, решаемые на распределённых ВС, представляются параллельными программами и описываются рядом параметров, в числе которых: коли-

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

На практике широко используется и хорошо изучен режим обработки наборов задач, параметры которых заданы скалярными величинами. Повысить эффективность функционирования распределённых ВС возможно, если, в частности, задачи допускают решение на подсистемах с различным количеством ЭМ. Такие задачи называются масштабируемыми или «пластичными» (тоМаЫе). Исследования пользовательских запросов показывают, что свойством масштабируемости обладают более 80% задач. Также важно разрабатывать децентрализованные методы и алгоритмы управления ресурсами распределённых ВС при обслуживании потоков задач.

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов работы. Основные результаты исследований нашли применение в работах по созданию и развитию пространственно-распределённой мультикластерной ВС ЦПВТ ФГОБУ ВПО "СибГУТИ" и Лаборатории ВС ИФП СО РАН. Диссертационные исследования выполнялись в рамках федеральных целевых программ «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 годы» (ГК №02.514.11.0002 «Разработка программных технологий для развития российского сегмента Грид, систем параллельного программирования, систем компьютерной графики») и «Научные и научно-педагогические кадры инновационной России» (ГК №02.740.11.0006 «Проведение исследований в области распределённых вычислительных систем и развитие научно-учебного центра параллельных вычислительных технологий ФГОБУ ВПО "СибГУТИ"»). Работа поддержана грантами Российского фонда фундаментальных исследований (№ 00-01-

00126, 02-07-06099, 02-07-09380, 03-07-06008, 08-07-00022, 09-07-00095, 11-0700109), грантами Президента РФ по поддержке молодых российских учёных и ведущих научных школ (ЛШШ-2121.2008.9, НШ-5176.2010.9, НШ-2175.2012.9, МК-2317.2012.9), а так же грантами ФГОБУ ВПО "СибГУТИ" (2008-2011 гг.). Результаты работы внедрены в учебный процесс Сибирского государственного университета телекоммуникаций и информатики. Практическое использование результатов диссертационных исследований подтверждается соответствующими актами о внедрении.

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

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

• Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы» (2003 г., г. Геленджик);

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

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

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

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

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

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

• Международной научно-технической конференции «Информатикаи проблемы телекоммуникаций» (2001-2011 гг., г. Новосибирск);

• Международной научно-технической конференции «Информационные системы и технологии» (2003 г., г. Новосибирск);

• Первой Всероссийской научной конференции «Методы и средства обработки информации» (2003 г., г. Москва);

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

• Школе-семинаре «Распределённые кластерные вычисления» (2001 г., г. Красноярск).

• Научно-техническом семинаре ФГОБУ ВПО "СибГУТИ" (ежегодно);

Публикации. По теме диссертации опубликовано 63 работы, в том числе 9 — в изданиях из перечня ВАК.

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

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

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

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

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

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

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

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

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

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

В зависимости от способа задания значений параметров задачи принято разделять на: «фиксированные» (англ. rigid), «масштабируемые» (англ. moldable) и «адаптирующиеся» (англ. evolving и malleable). Фиксированные задачи требуют для выполнения программ чётко заданное количество ЭМ на определённое время. Для таких задач значения соответствующих параметров задаются скалярными величинами. Масштабируемые и адаптирующиеся задачи допускают выполнение программ на подсистемах с различным количеством ЭМ и временем выполнения. Параметры таких задач задаются диапазоном или вектором значений. При этом, для масштабируемых задач размер подсистемы ЭМ для выполнения программ выбирается один раз перед началом их решения и не меняется. Адаптирующиеся задачи допускают изменение количества ЭМ в процессе их решения. Исследования пользовательских запросов показывают, что свойством масштабируемости обладают более 80% задач.

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

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

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

На практике широко используется и хорошо изучен режим обработки наборов фиксированных задач. Наибольшее распространение получили системы TORQUE, Altair PBS Pro, Oracle Grid Engine, IBM LoadLeveler. Для планирования решения задач наборов чаще всего используются алгоритмы: FCFS (англ. First-Come-First-Served), SJF (англ. Shortest-Job-First), LJF (англ. Longest-Job-First), а так же технологии Backfilling и Gang Scheduling, позволяющие увеличить эффективность решения задач с небольшим временем решения. Существуют алгоритмы, учитывающие несколько критериев при планировании решения задач (например ранг задач и время решения). Системы пакетной обработки, используемые на практике, допускают наличие в очередях масштабируемых задач и позволяют пользователям указывать значения ранга в виде множества или диапазона. Планировщики обычно используют свойство масштабируемости, выбирая первое подходящее значение ранга и не учитывая время решения. Известны алгоритмы выбора значений параметров задач путём их ранжирования, исходя из прогнозируемой загрузки ВС или предполагаемого характера поступления задач.

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

Постановка задачи. Имеется распределённая ВС, состоящая из N элементарных машин. На вход системы поступил набор / = {/;} независимых задач, i = 1, L, где L — количество задач в наборе. Каждая задача Ii — {Pi, ct) описывается вектором параметров Pi - (р}-рЬ ■ • ■, pf) и величиной штрафа Ci за задержку её решения в единицу времени, & — количество элементов в векторе р,, qt > 1, Cj > 0. Элемент вектора параметров pkL — озна-

чает, что с приоритетом uf для решения г-той задачи требуется выделить подсистему из г* ЭМ на время if, 0 < tf < N, tf[ > 0, wf > 0,k = 1

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

две ЭМ могут взаимодействовать через сеть связи. Зависимости между величинами Г;', и)?, С; ОТСУТСТВУЮТ.

Требуется для каждой задачи /,: определить время начала её решения, выбрать кг — номер элемента вектора р1 и выделить множество ЭМ Ji (подсистему ЭМ необходимого размера). В результате должен быть сформирован вектор 5 = {(кг, вь Л), (к2,э2, -Л), • • •, {кь^ь^ь)), называемый расписанием решения задач набора на распределённой ВС. Расписание должно быть сформировано так, чтобы значение некоторого критерия (или нескольких критериев) было наилучшим. О критериях, используемых в данной диссертации, бздет сказано ниже.

Выбор значений к е {1,.. •,</;} определяет «удовлетворённость» пользователей сформированным расписанием решения задач набора

ги:

шах

'-1

В работе предложена следующая схема формирования расписаний решения масштабируемых задач (рисунок 1). В основу этой схемы положена идея формирования расписаний решения фиксированных задач с использованием «укрупнённых» задач, предложенная в середине XX века в работах Д. А. Поспелова и В. Г. Хорошевского, и в дальнейшем получившая широкое распространение.

• ! формирование; ^

задача ; ■' «укрупнённых» ■

задача; !>' задача;.,] НАВОР ЗАДАЧ

задач

определение последовательности

решения «укрупнённых» задач

расписание | решения задач! набора !

ЭТАП 1

ЭТАП 2

ЭТАП 3

Рисунок 1 - Процедура формирования расписаний решения масштабируемых задач

Формирование расписаний решения задач набора предложено осуществлять в три этапа. На первом этапе формируются «укрупнённые» задачи — подмножества задач набора, одновременно запускаемые на решение на распределённой ВС и разделяющие её ресурсы. Ранг «укрупнённой» задачи не превышает количество ЭМ в распределённой ВС, а время её решения определяется максимальным временем решения входящих в неё задач набора. На втором этапе определяется последовательность запуска «укрупнённых» задач на решение. На третьем этапе, исходя из сформированных «укрупнённых» задач и последовательности их запуска на решение, строится итоговое расписание решения задач набора.

Этап 1. Формирование укрупнённых задач.

Постановка задачи первого этапа имеет следующий вид. Решением задачи будет тройка 51 = (К, М, Э), где К - (кг,к2, ■■ ■, кь) — вектор выбранных для задач значений кг, М = — количество формируемых «укрупнённых» задач, 9 — {9т} — множество «укрупнённых» задач, 3>п = {Л € /}, г 6 {1,2,...,Ь}. Время решения «укрупнённых» задач определяется как

м

гп—1

Требуется определить решение такое, чтобы:

ад?) = ш адо, (1)

при ограничениях:

г?' < ЛГ, т = ТТМ, (2)

/,еэг„

м м

|Эт| = Ь, р] Зт = 0. (3)

т=1 т=1

где П1 — область допустимых решений 5ь Ограничение (2) определяет, что суммарный ранг задач, входящих в каждую «укрупнённую» задачу, не превосходит количество ЭМ распределённой ВС. Ограничение (3) гарантирует, что все задачи набора распределены по «укрупнённым» задачам, и каждая из задач набора находится только в одной «укрупнённой» задаче и пустых «укрупнённых» задач не сформировано.

В работе предложено два способа учёта «удовлетворённости» пользователей при формировании «укрупнённых» задач.

Способ 1. Задано ограничение на значение средней <гудовлетворённости» пользователей.

В систему ограничений вводится дополнительное условие, определяющее минимальную допустимую среднюю «удовлетворённость» пользователей е

Щ51)>е. (4)

Для формирования «укрупнённых» задач с учётом ограничения (4) предложены следующие алгоритмы.

Эвристический алгоритм 1 (однократный случайный выбор значений кг). Алгоритм заключается в случайном выборе для всех задач набора значений ^ так, чтобы удовлетворялось ограничение (4), и использовании известных алгоритмов формирования «укрупнённых» задач для наборов фиксированных задач.

Представим набор задач / в следующем виде: ^U-^1 гЛе ~ множество задач набора с одним элементом вектора рц I1 ~ подмножество задач набора, у которых все элементы вектора р; имеют одинаковый приоритет; I2 — остальные задачи набора; /° fV1 iV2 = Очевидно, что на выполнение ограничения (4) влияет лишь выбор кг для задач подмножества I2. В работе определено условие возможности случайного выбора для задач значений кг.

min min w.'f ^ 1

Утверждение 1. Если + > eL или tllxwk > то

liCl? к '

ограничение (4) выполняется при любом выборе параметров (конфигураций ресурсов) для задач набора.

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

Шаг 0. Считаем, что для каждой задачи набора уже было выбрано значение ki таким образом, что удовлетворялось ограничение (4). Например, для каждой задачи может быть выбран параметр с наивысшим приоритетом.

Шаг 1. Для задач подмножества 71 значения к{ выбираются произвольно.

Шаг 2. Вычисляется значение средней «удовлетворённости» пользователей при решении задач набора согласно текущему выбору их параметров.

Шаг S. Произвольно выбирается задача из подмножества I2 и новое значение к{ для неё.

Шаг 4- Если изменение h не приводит к нарушению условия (4), то кг фиксируется и осуществляется переход к шагу 2; в противном случае значение ki не изменяется.

Шаг 5. Процедура продолжается до тех пор, пока не будут перебраны все задачи подмножества I2.

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

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

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

В терминах генетических алгоритмов в работе предложено следующее кодирование решения задачи (1)-(4):

- ген — это задача с выбранным значением к,\

- особь — это совокупность генов. При этом, у каждого гена значение выбрано так, чтобы удовлетворялось ограничение (4);

- популяция — это множество особей;

- функция приспособленности — это значение функции (1), получаемое после разбиения задач набора с выбранными значениями k на «укрупнённые» задачи.

Начальная популяция формируется с помощью алгоритма 1 (однократного случайного выбора значений к{). Родительские пары выбираются случайным образом. Предложен следующий многоточечный оператор кроссингове-ра (количество точек задаётся одним из входных параметров оператора).

Шаг 1. Для каждой точки кроссинговера случайным образом выбирается позиция между генами особи.

Шаг 2. Гены особи последовательно просматриваются слева направо. Достигая точки кроссинговера, родители начинают обмениваться друг с другом генами. Обмены продолжаются, пока не будет достигнута следующая точка кроссинговера.

Оператор мутации случайным образом изменяет значения kt для некоторого (случайного) количества генов у особи.

В новую популяцию попадают особи с наилучшим значением функции приспособленности. Размер популяции (количество особей) в процессе эволюции не меняется.

Итоговое решение формируется из особи, имеющей наилучшее значение функции приспособленности.

Случай 2. Средняя <sудовлетворённость* пользователей является целевой функцией.

Функция W(Si) средней «удовлетворённости» пользователей рассматривается как вторая целевая функция для задачи (1)-(4):

H'(Si) = max W(Si) (5)

Si€I1J

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

Q(Si) = aW(Si)/Wm«x + PTmuJTiSi), (6)

где \¥тах —• максимальная суммарная «удовлетворённость» пользователей; £

Ттгп = N "1 ^ 1шп {г^ ■ — нижняя оценка времени решения задач на-

¿=1 кй1,Ч1

бора; а, Р — весовые коэффициенты (значения определяются методом экспертных оценок или экспериментальным путём). Требуется найти такое, чтобы

(?(5Г) = тах 0(50, (7)

¿1€Н1

при ограничениях (2)-(3).

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

- ген — «укрупнённая» задача, состоящая из задач, для каждой из которых выбрано значение к¿;

- особь — множество «укрупнённых» задач;

- функция приспособленности — это значение функции (6).

Начальная популяция формируется с применением случайного выбора значений кг и формирования «укрупнённых» задач алгоритмом Вев^Е^-Весгеайп^-Н^Ы; (ВГБН).

На основе известного метода перетасовки генов предложен следующий оператор кроссинговера:

Шаг 1. Гены родительских особей помещаются в общий контейнер и сортируются по критерию «загрузки вычислительных ресурсов» (ЯтТт)"1 2 {'"¡"'Ф где Нгп. — ранг «укрупнённой» задачи т, а Тт -

- время её решения.

Шаг 2. Если в контейнере имеются гены, содержащие одинаковые задачи, но с разными значениями /:г, то из двух генов удаляется тот, которому соответствует меньшее значение критерия «загрузки вычислительных ресурсов».

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

Шаг 4- Оставшиеся гены контейнера расформировываются. Из получившихся задач удаляются повторяющиеся или присутствующие в нерасформи-рованных генах.

Шаг 5. Из оставшихся задач по алгоритму ВРБН создаются новые гены и помещаются обратно в контейнер.

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

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

Проведено моделирование предложенных алгоритмов формирования «укрупнённых» задач. Предложенные алгоритмы реализованы с использованием языка программирования С++. Компиляция программ осуществлялась ОМи\ОСС с указанием максимально возможной степени оптимизации. Наборы задач генерировались для систем с количеством ЭМ от 21 до 220. Рассматривались наборы с количеством задач 10, 100, 1000 и 10000. Приоритеты значениям параметров задач задавались путём их простой нумерации. Моделирование показало, что алгоритмы эффективны, они обеспечивают субминимум времени решения задач набора, который отличается от нижней грани в среднем на 15 — 20% (рисунок 2).

11.111.1

ftll-.ll.!

.11

; 5 6 ' Ю 4;5;6 10! 32 256 32768 1048576

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

в)

б)

* . . .. | # <-.« II! ||!|ш1!1|||1!1 н1 Ц||Ц|

4 5 6Ю4 5бг0 4 5 6Ю«ТбК> | 456 1С456 10 4 5ь10«56

5 6:10 < 5 ■ 6;Ю| 3! ?56 32768 1048576

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

г)

Рисунок 2 - Влияние параметров алгоритмов 2 (а и б) и 3 (в и г) на качество их работы. (Ь = 10000, е = 0.50 (а и в), е = 0.95 (б и г) )

Этап 2. Определение последовательности запуска «укрупнённых* задач на решение.

На втором этапе определяется последовательность решения «укрупнённых» задач, позволяющая получить минимум штрафа за задержку решения задач набора. Состав «укрупнённых» задач не меняется.

Постановка задачи второго этапа следующая. Пусть задана некоторая последовательность 52 = (ть...,ть... ,т?гм) решения «укрупнённых» задач, где т1 — номер «укрупнённой» задачи, которая будет решаться в 1-ю очередь, I = {1,..., М). Штраф за решение задач при выбранной по-

следовательности решения пакетов определяется как

М 1-1

= (8) (=2 т=1

где СП1 = Е ~ штраф за задержку решения задач, входящих в тщ-й

пакет, Ттг — время решения тг-ой «укрупнённой» задачи.

Требуется найти такую последовательность чтобы достичь минимума функции (8).

Утверждение 2. Для того чтобы последовательность решения «укрупнённых» задач обеспечивала минимум функции (8), необходимо и достаточно, чтобы выполнялись неравенства:

Тт.1 ^ Тт2 ^ ^ ^пч < .,. < Ст\ СгП2 Ст,

Последовательность может быть найдена любым известным методом сортировки.

Этап 3. Формирование итогового расписания решения задач.

Итоговое расписание б* = {{къ з1,.11),...,{кь,-и, Л)), формируется исходя из 55е и следующим образом.

1. Для Ь используются значения из .

2. Время начала решения задачи определяется временем начала решения «укрупнённой» задачи в* , в которую она была помещена. Время в,* определяется найденной последовательностью решения «укрупнённых» за-

1-1

дач: = 0, = X! Ттг.

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

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

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

Рисунок 3 - Схема функционирования распределённой ВС в режиме обслуживания потоков задач

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

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

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

В диссертации с использованием методов теории игр разработаны алгоритмы поиска стратегий случайного выбора: 1) ранга «укрупнённых», задач; 2) времени решения «укрупнённых» задач и 3) последовательности опроса распределённой очереди «укрупнённых» задач.

Выбор рангов «укрупнённых» задач.

Если диспетчер сформировал «укрупнённую» задачу ранга г, а для её решения планировщиком будет выделено г ЭМ, то издержки диспетчера могут быть оценены как:

где Сх — цена эксплуатации одной ЭМ в единицу времени; сз — величина штрафа, выплачиваемого диспетчером в единицу времени за одну простаивающую ЭМ; сз — величина штрафа, налагаемого на диспетчера в единицу времени, если он сформировал «укрупнённую» задачу с рангом, большим на единицу числа выделенных ЭМ, т.е. г = г + 1, г,г — О,ТУ; N — число ЭМ в вычислительной подсистеме.

Рассматриваемая математическая модель относится к классу многоходовых антагонистических игр с нулевой суммой. Издержки диспетчера при формировании «укрупнённых» задач различных рангов и выделении подсистем для их решения составляют матрицу платежей: С = ||с,г|).

На практике часто встречается ситуация, при которой в потоке имеются задачи различных рангов. Поэтому алгоритм функционирования диспетчера, состоящий в формировании «укрупнённых» задач только одного ранга, представляется неэффективным. Следовательно, рассматриваемая модель не должна иметь решения в чистых стратегиях, т.е. матрица С = ||с*г|| не должна иметь седловых точек. В работе доказано следующее утверждение.

Утверждение 3. Матрица С = ||<^г|| не имеет седловых точек тогда и только тогда, когда:

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

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

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

гс-1 + (г — т)с% при г > г, гсг + (г — г)сз при г < г,

(10)

С1 < с2, С3 > Л'С! - (ТУ - 1)с2.

(11)

\ режиме работы в системе имеется к исправных ЭМ может быть найдена | известными методами теории вычислительных систем.

I = п, р„

£ ii"= 1

2. !

I ; ч •

' |Cqq Coi""Cpn | I Сю

Рисунок 4

2 (2; | С,» C«-Q», CMC„--C0n : | CooCpi—Con- С00 C01--C0n О» Coi--Ca,

-ическое де; «укрупнённых» задач

Первый ход осуществляется планировщиком. Он выделяет подсистему из i ЭМ, 0 <г< к. Второй ход делает диспетчер. Независимо от состояния системы и хода, который сделал планировщик, он выбирает для формирования «укрупнённой» задачи ранг г, 0 < г < N.

Для «сокрытия» информации о состоянии системы в работе предложено изменить коэффициенты платёжной матрицы следующим образом:

(12)

Cir = drPi,

где р\ = £ рк. Очевидно, что р\ > р'р при г < э, г,] е {0,1,... ,п}. Та-

к=г

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

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

Утверждение 4. Матрица С" = ¡|с-г|| не имеет седловых точек тогда и только тогда, когда:

(13)

С2 > С3,

где а = г = j + 1.

Np', P'n~

ca £ [а,Ь] U [c2,oc), ip'i-jp'i

:ci -(N- 1)C2, b = c2 m^{(Af-jpj-^-iR^ ^ -Ü-

j=0,N

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

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

Получен«*« ц»ча ягрм

Зффэкткигюсгь мою до« по числу шт>с

Рисунок о - Некоторые результаты моделирования алгоритмов выбора рангов «укрупнённых» задач

Определение времени решения «укрупнённых» задач.

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

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

Выбрав ранг «укрупнённой» задачи, диспетчер формирует ее из т задач и выставляет в очередь. По мере освобождения ресурсов готовые «укрупнённые» задачи выбираются из очереди, им выделяется подсистема ЭМ и назначается квант времени решения ©, © е [0,6+], где - максимально допустимое время решения «укрупнённой» задачи. Если назначенное время равно 0, это значит, что «укрупнённая» задача просто удаляется из очереди без решения её на ВС. Она расформировывается, и исходные задачи помещаются обратно во входную очередь.

Если диспетчер каждый раз создаёт «укрупнённые» задачи из т задач потока, а планировщик назначает им время решения, равное в, то средние издержки на решение одной «укрупнённой» задачи оцениваются как:

_ f тТсг + (© - тпТ)сг если © > тпТ\ (14)

Стй ~ \©с2 + (тпТ - ©)с4, если тпТ < ©,

где с4 - штраф за превышение времени решения «укрупнённой» задачи на единиц}' времени, Т - математическое ожидание величины

Предложенная математическая модель относится к классу непрерывных (бесконечных) игр. Издержки при формировании «укрупнённых» задач из разного количества задач и назначении им разного времени решения составляют матрицу платежей С = ¡|сте||-

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

Утверждение 5. Матрица С = ||с,„е|| не имеет решения в чистых стратегиях, если выполняются следующие условия:

т~Тс\ + (©+ -т-Г-е-)с2 /15л

с2>сь <*>-т-Т - ©- ' ^ '

!@+ если т+Т > 0

arg max Cfm+.Ö), еслит+Т<@+, ве!о,а+)

ш+ - максимально допустимое число задач в пакете. Запись [х] означает целую часть от х.

В качестве инструментария решения поставленной задачи предлагается использовать метод е-разбиения, который заключается в приведении непрерывной игры к конечной путём разбиения интервала [0, ©+] на отрезки длиной с. В работе экспериментально показано, что уже при величине е, равной

0,01, возможно получить решение задачи. С уменьшением е увеличивается размер получаемой матрицы платежей, а результаты решения отличаются меньше чем на 10%.

Определение последовательности опроса распределённой очереди «укрупнённых» задач.

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

Как только планировщику распределённой ВС выделена подсистема для решения задач, он формирует запросы на приобретение «укрупнённых» задач из распределённой очереди. Время, которое он затратит на поиск «укрупнённых» задач, зависит от:

• порядка опроса диспетчеров ВС Мг«з • ■

• «состояния» распределённой очереди «укрупнённых» задач (в очередях каких диспетчеров есть «укрупнённые» задачи) г'^г^ ...;

• структуры связей между планировщиками и диспетчерами, т.е. расстояния (¡1 до опрашиваемого (г-ого) диспетчера;

• объёма передаваемых данных а; и /г от диспетчера с номером г, соответственно в случаях успешного и неуспешного запросов.

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

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

С — ИСйЫз...,»;»'^...!!. (16)

Г-1

где = + /¡.^ — время, затрачиваемое плани-

з=1

ровщиком на поиск «укрупнённых» задач при выборе последовательности опроса Мзгз ... и нахождения системы в состоянии г^г^з • • •> 3" ~~ номер в последовательности опроса диспетчеров такой, что во всех опрошенных до

этого диспетчеров не оказывается «укрупнённых» задач в очереди, другими

словами ¿k • • -i Ч' е • • J = . ■ ■, j*.

Если имеется возможность оценить вероятность нахождения распределённой очереди «укрупнённых» задач в каждом из её состояний (например, с использованием методов теории массового обслуживания или экспертных оценок), то решение поставленной задачи сводится к поиску минимума функции:

Л'г'з-

где P{i'ii'2i'3...) — вероятность нахождения системы в состоянии ...,

запись TI означает, что суммирование ведётся по всем возможным со-Í\Í'2Í'3:. стояниям очереди.

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

F{i1hh...)=a шах CiiÍ2Í3...¿Av3... + (1 - a) min (18)

¿1г213'- «l'a'.V

где q — коэффициент, определяющий степень риска менеджера, 0 < а < 1, при а = 0 менеджер максимально рискует при выборе последовательности, а при а = 1 рискует наименьшим образом (критерий крайнего пессимизма).

В работе показано, что применение критерия Гурвица при а = 0 возможно только при условии, что /г < s¿ , а при а = 1 — только для не полносвязанных систем (т.е. если структура связей отлична от полного графа).

В четвёртой главе описана архитектура пространственно-распределённой мультикластерной ВС Центра параллельных вычислительных технологий ФГОБУ ВПО "СибГУТИ1' и Лаборатории ВС ИФП СО РАН (рисунок 6). Актуальная информация о конфигурации системы представлена на сайте ЦПВТ ФГОБУ ВПО "СибГУТИ" (http://cpct.sibsutis.ru).

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

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

Рисунок 6 - Конфигурация пространственно-распределённой мультикластерной вычислительной системы (январь 2012 года)

языке ANSI С для операционной системы GNU\Limix. В состав пакета входят нижеследующие компоненты: \

1. Подсистема генерирования задач. Задачи генерируются на основе известных статистик поступления задач в распределённые ВС или с использованием моделей потоков задач. Масштабирование задач производится с использованием модели Downey. Приоритеты запросов задаются псевдослучайно с равномерным распределением.

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

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

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

В приложениях приведены сводные данные о предложенных алгоритмах, исходные коды основных модулей разработанной системы MOJOS и I

Средства разработки параллельных программ

Ii g §> MPl: МР1СН2, OpenMPI, TopoMPI PGAS: Unified Parallel С OpenMP: GNU GCC, Intel Compilers, Oracle Compilers Средства анализа параллельных программ: MPIPerf, VampirTrace

g CD s s 3 £8 Средства организации распределённой очереди задач (Gbroker, dqueued, GridWay)

o « 'S о go if q CO го со Подсистема параллельного мультипрограммирования (MOJOS,TORQUE, MAUI, mpiexec)

Подсистема самоконтроля, самодиагностики ВС и организации отказоустойчивого выполнения параллельных программ (HBICT, DMTCP)

Операционная система GNU/Linux

Подсистема параллельного мультипрограммирования

Рисунок 7 - Программное обеспечение пространственно-распределённой мультикластерной вычислительной системы (жирным шрифтом выделены оригинальные компоненты)

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

2.2. Построены теоретико-игровые модели и алгоритмы для децентрализованных диспетчеров очередей задач и планировщиков ресурсов распределённых ВС. Алгоритмы позволяют формировать «укрупнённые» задачи из задач потока и сокращают простои ресурсов распределённых ВС. Они учитывают топологию логических связей между планировщиками и диспетчерами, стохастическую природу потоков задач и отказы ресурсов распределённых вычислительные систем.

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

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

3. При непосредственном участии диссертанта создана пространственно-

распределённая мультикластерная ВС.

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

3.2. Создан программный пакет MOJOS для моделирования и анализа алгоритмов организации функционирования распределённых ВС,

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ а) Публикации в рецензируемых журналах из списка ВАК:

1. Хорошевский В. Г., Курносов М. Г., Мамойленко С. Н., Павский К. В., Ефимов A.B., Пазников A.A., Перышкова E.H. Масштабируемый инструментарий параллельного мультипрограммирования пространственно-распределённых вычислительных систем // Вестник СибГУТИ. - Новосибирск: Изд-во ФГОБУ ВПО «СибГУТИ», 2011. - № 4. - С. 3 — 18. - ISSN 19986920.

2. Мамойленко С.Н., Ефимов A.B., Перышкова E.H.. Организация функционирования распределённых вычислительных систем при обработке масштабируемых задач // Вестник Томского государственного университета. Серия «Управление, вычислительная техника и информатика». - Томск: Изд-во Томского государственного университета, 2011. - № 2(15). - С. 51 —

60. - ISSN 1998-5605.

3. Хорошевский В. Г., Курносов М.Г., Мамойленко С.Н.. Пространственно-распределённая мультикластерная вычислительная система: Архитектура и программное обеспечение // Вестник Томского государственного университета. Серия «Управление, вычислительная техника и информатика». - Томск: Изд-во Томского государственного университета, 2011. -

№ 1(14). - С. 79-84. - ISSN 1998-5605.

4. Хорошевский В. Г., Курносов М. Г., Мамойленко С. Н., Поляков А. Ю. Архитектура и программное обеспечение пространственно-распределённых вычислительных систем // Вестник ГОУ ВПО «СибГУТИ». - Новосибирск: Изд-во ГОУ ВПО "СибГУТИ", 2010. - №2. - С. 112 - 122. - ISSN 1998-6920.

5. Мамойленко С.Н., Ефимов A.B. Алгоритмы планирования решения масштабируемых задач на распределённых вычислительных системах // Вестник ГОУ ВПО "СибГУТИ". - Новосибирск: Изд-во ГОУ ВПО "СибГУТИ", 2010. - N 2. - С. 66-78. - ISSN 1998-6920.

6. Хорошевский В. Г., Мамойленко С. Н., Майданов Ю. С., Смирнов С. В. Об организации функционирования кластерных вычислительных систем // Автометрия, Новосибирск, 2004, Т.40, N 1, С. 41-50.

7. Хорошевский В. Г., Мамойленко С.Н. Стратегии стохастически оптимального функционирования распределённых вычислительных систем / / Автометрия. - 2003. - N 2. - С. 81-91.

8. Khoroshevsky V. G., Mamoilenko S. N., Maidanov Yu. S., Smirnov S. V. On cluster computer functioning // Optoelectronics, Instrumentation and data processing, Vol. 40, No. 1, 2004, pp. 35-42.

9. Khoroshevsky V.G., Mamoilenko S.N. Stochastically optimal functioning strategies of distributed computing systems // Optoelectronics, Instrumentation and data processing, Vol. 39, No. 2, 2003, pp. 68-76.

б) Публикации в материалах научных мероприятий (международных и российских конференциях):

10. Мамойленко С. Н,, Перышкова Е. Н., Ефимов А. В. Две модификации генетического алгоритма формирования расписаний решения масштабируемых заданий на распределённых вычислительных системах // Информатика и проблемы телекоммуникаций: материалы Российской научно-технический конференции. - Новосибирск: Изд-во ГОУ ВПО «СибГУТИ», 2011, 21-22 апреля 2011 года. - Т. 1. - С. 207-208.

11. Мамойленко С. Н., Перышкова Е. Н., Ефимов А. В. Сравнение методов кодирования решений генетического алгоритма формирования решений выполнения масштабируемых программ на распределённых вычислительных системах // Материалы XLIX международной научной студенческой конференции "Студент и научно-технический прогресс": Информационные технологии / НГУ. Новосибирск, 2011. - С. 229.

12. Ефимов A.B., Мамойленко С.Н., Максимова E.H. Моделирование алгоритмов формирования расписаний решения масштабируемых задач на распределённых вычислительных системах [Электронный ресурс] // Распределенные информационные и вычислительные ресурсы (DICR-2010): доклады XIII Российской конференции с участием иностранных ученых. - Электрон. данные. - Новосибирск, 2010, 30 ноября - 03 декабря 2010 г. - Режим доступа: http://conf.nsc.ru/files/conferences/dicr2010/fulltext/29970 /29971/maksimova-mamo ilenko.pdf.

13. Мамойленко C.H., Кожушко Р. И. Формирование расписаний решения масштабируемых задач на распределённых вычислительных системах модифицированными методами 1.5D и 2D упаковки объектов в полосу // Информатика и проблемы телекоммуникаций: материалы Российской научно-технический конференции. - Новосибирск: Изд-во ГОУ ВПО «СибГУТИ», 2011, 21 - 22 апреля 2011 года. - Т. 1. - С. 205.

14. Мамойленко С.Н., Крамаренко К.Е. Нейросетевой алгоритм составления расписаний решения задач на распределённых вычислительных системах // Информатика и проблемы телекоммуникаций: материалы Российской научно-технический конференции. - Новосибирск: Изд-во ГОУ ВПО «СибГУТИ», 2011, 21 — 22 апреля 2011 года. - Т. 1. - С. 200-201.

15. Мамойленко С.Н., КожушкоР.И. Модифицированные алгоритмы 2D упаковки для формирования расписания выполнения набора адаптирующихся задач на распределённых вычислительных системах // Информатика и проблемы телекоммуникаций: материалы Российской научно-технический конференции. - Новосибирск: Изд-во ГОУ ВПО «СибГУТИ», 2010, 27 - 28

апреля 2010 года. - Т. 1. - С. 156.

16. Крамаренко К.Е., Мамойленко С.Н. Нейросетевой алгоритм формирования расписания выполнения набора адаптирующихся задач // Информатика и проблемы телекоммуникаций: материалы Российской научно-технический конференции. - Новосибирск: Изд-во ГОУ ВПО "СибГУТИ", 2010, 27 - 28 апреля 2010 года. - Т. 1. - С. 157.

17. Максимова E.H., Мамойленко С.Н., Ефимов A.B. Параллельный генетический алгоритм формирования расписания решения параллельных адаптирующихся задач на распределённых вычислительных системах // Информатика и проблемы телекоммуникаций: материалы Российской научно-технический конференции. - Новосибирск: Изд-во ГОУ ВПО «СибГУТИ», 2010, 27 - 28 апреля 2010 года. - Т. 1. - С. 163.

18. Мамойленко С. Н., Великородний И.М. Алгоритм организации функционирования очередей задач в распределённых вычислительных системах // Информатика и проблемы телекоммуникаций: материалы Российской на-^ учно-технической конференции. - Новосибирск: Изд-во ГОУ ВПО "СибГУТИ", 2010, 27 - 28 апреля 2010 года. - Т. 1. - С. 164.

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

- Новосибирск: Изд-во ГОУ ВПО "СибГУТИ", 2010, 27 - 28 апреля 2010 года.

- Т. 1. - С. 166.

20. Максимова E.H., Ефимов A.B., Мамойленко С.Н. Параллельный генетический алгоритм формирования расписания решения параллельных адаптирующихся задач на распределённых вычислительных системах // Научная студенческая конференция Лаборатории НГУ-Интел 2010. - Новосибирск: НГУ, 2010, 22 мая 2010 года.

21. Хорошевский В. Г., Курносов М. Г., Мамойленко С. Н. Научно-учебный центр параллельных вычислительных технологий ГОУ ВПО "СибГУТИ" // Суперкомпьютерные технологии. Разработка, программирование, применение: материалы международной научно-технической конференции. - Таганрог: Изд-во ТТИ ЮФУ, 2010, 27 сентября - 02 октября 20Ю. - Т.2. - С. 306 - 208.- 1 электрон, опт. диск (CDROM).- ISBN 978-5-8327-0383-1.

22. Хорошевский В. Г., Курносов М. Г., Мамойленко С. Н. Научно-учебный центр параллельных вычислительных технологий ГОУ ВПО "СИБГУТИ" // Высокопроизводительные вычислительные системы (ВПВС-

2010): материалы седьмой международной научной молодежной школы. -Таганрог: Изд-во ТТИ ЮФУ, 2010, 27 сентября - 02 октября 2010. - С. 146 -148. - ISBN 978-5-8327-0382-4

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

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

25. Хорошевский В. Г., Курносов М. Г., Мамойленко С. Н. Пространственно-распределенные мультикластерные вычислительные системы: архитектура и программное обеспечение //' Материалы Всероссийской научно-технической конференции "Научное и технические обеспечение исследований и освоения шельфа Северного Ледовитого океана", 2010. - С. 54-59.

26. Ситников С. Г., Хорошевский В. Г., Курносов М.Г., Мамойленко С. Н. Архитектура, анализ и организация функционирования распределенных вычислительных систем // Программа «Университетский кластер»: материалы конференции «Облачные вычисления: образование, научные исследования, разработки». - Москва: Hewlett-Packard Development Company, L.P., 15-16 апреля 2010. - С. 51.

27. Хорошевский В.Г., Курносов М.Г., Мамойленко С.Н. Инструментарий параллельного мультипрограммирования большемасштабных распределённых гетерогенных вычислительных систем // Материалы конференции "Результаты ориентированных целевых фундаментальных исследований и их использование в российской промышленности". - Таганрог: НИИ МВС ЮФУ, 2010.

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

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

для «Распределённые информационные и вычислительные ресурсы» (DICR-2010): программа и тезисы докладов с участием иностранных ученых. - Новосибирск, 2010, 30 ноября - 03 декабря 2010 г. - С. 24. - 1 электрон, опт. диск (CDROM).

30. Максимова E.H., Ефимов A.B., Мамойленко С.Н. Эволюционный подход к формированию расписаний выполнения адаптирующихся программ на распределённой вычислительной системе // Новые информационные технологии в исследовании сложных структур: тезисы докладов Восьмой Российской конференции с международным участием. - Томск: Изд-во: HTJ1, 2010, 05 - 08 октября 2010 года. - С. 17. - ISBN 978-5-89503-440-8.

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

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

33. Хорошевский В.Г., Курносов М.Г., Мамойленко С.Н. Пространственно-распределенная мультикластерная вычислительная система: архитектура и программное обеспечение // Новые информационные технологии в исследовании сложных структур: тезисы докладов Восьмой Российской конференции с международным участием. - Томск: Изд-во: НТЛ, 2010, 05 -08 октября 2010 года. - С. 27. - ISBN 978-5-89503-440-8.

34. Максимова Е. Н-, Мамойленко С. Н. Генетический алгоритм распределения наборов параллельных задач с нефиксированными параметрами по машинам распределенной вычислительной системы // Материалы Российской научно-технической конференции «Информатика и проблемы телекоммуникаций», Новосибирск: ГОУ ВПО «СибГУТИ», 27-28 апреля 2009 года, С. 127-128.

35. Мамойленко С.Н., Крамаренко К.Е. Применение нейросетевых алгоритмов для распределения наборов параллельных задач по машинам распределенной вычислительной системы // Материалы Российской научно-технической конференции «Информатика и проблемы телекоммуникаций», Новосибирск: ГОУ ВПО «СибГУТИ», 27-28 апреля 2009 года, С. 128-129

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

технической конференции "Информационные технологии и математическое моделирование систем 2008-2009", Москва, 2009, С. 74-79.

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

38. Хорошевский В. Г., Мамойленко С.Н., Курносов М.Г., Поляков А.Ю. Параллельные вычислительные технологии в учебном процессе // Сборник тезисов докладов 50-й (L) научно-методической конференции ГОУ ВПО «СибГУТИ», Новосибирск: ГОУ ВПО «СибГУТИ», 6 февраля 2009 года, С. 63

39. Мамойленко С.Н., Ефимов A.B. Генетический алгоритм распределения параллельных задач с нефиксированными параметрами по машинам распределенной вычислительной системы // Сборник тезисов пятой сибирской конференции по параллельным и высокопроизводительным вычислениям, Томск: Изд-во Томского университета, 1-3 декабря 2009, С.69-68

40. Мамойленко С. Н., Медведева H.A.. Поляков А.Ю., Ефимов A.B. Применение эволюционных алгоритмов для распределения набора задач с нефиксированными параметрами по машинам распределенной вычислительной системы // Материалы Российской научно-технической конференции "Информатика и проблемы телекоммуникаций 2008, с. 144-145.

41. Хорошевский В. Г., Мамойленко С. Н., Курносов М. Г. О центре параллельных вычислительных технологий ГОУ ВПО «СибГУТИ» // Журнал «Инфосфера», N 40, 2008, С.43-44.

42. Мамойленко С. Н., Медведева H.A., Поляков А.Ю., Ефимов A.B. Применение эволюционных алгоритмов для распределения набора задач с нефиксированными параметрами по машинам распределенной вычислительной системы, // Тезисы докладов Седьмой Российской конференции с международным участием "Новые информационные технологии в исследовании сложных структур (ICAM-2008)". - Томск : НТЛ, 2008. - с. 71.

43. Мамойленко С.Н., Павский К.В., Курносов М.Г., Посохов A.C., Медведева H.A., Поляков А.Ю. Использование мультикластерной вычислительной системы для подготовки специалистов в области параллельных вычислительных технологий // Тезисы докладов XLIX научно-методической конференции "Проблемы перехода на многоуровневую систему образования". - Новосибирск: Изд-во СибГУТИ, 2008. - С. 38.

44. Мамойленко С.Н., Медведева H.A., Поляков А.Ю. Применение генетических алгоритмов для распределения наборов задач по машинам вычислительной системы // Материалы международной научно-технической

конференции «Многопроцессорные вычислительные и управляющие системы», пос. Дивноморское, Геленджик, 24 - 29 сентября, 2007, С. 70-25.

45. Хорошевский В. Г., Мамойленко С. Н., Медведева Н. А. Применение генетических алгоритмов для распределения наборов задач по машинам вычислительной системы // Материалы 8-й Международной научно-технической конференции «Искусственный интеллект. Интеллектуальные и многопроцессорные системы - 2007», 2007.

46. Мамойленко С.Н., Медведева Н. А. Современные средства организации функционирования распределённых вычислительных систем // Материалы Российской научно-технической конференции "Информатика и проблемы телекоммуникаций", Новосибирск, Т1, 2007, с.274-275

47. Мамойленко С.Н., Медведева Н. А. Опыт применения мультикла-стерной вычислительной системы для преподавания курса «Распределённые операционные системы» // Сборник тезисов докладов XLVIII Научно-методической конференции, Новосибирск, СибГУТИ, 2007 г., С. 33

48. Хорошевский В. Г., Мамойленко С. Н., Медведева Н. А. Алгоритмы распределения набора задач с нефиксированными параметрами по машинам вычислительной системы // Материалы третьей международной научной молодежной школы «Высокопроизводительные вычислительные системы», Таганрог: Изд-во ТРТУ, 2006, с. 33-36.

49. Мамойленко С. Н., Медведева Н. А. Алгоритмы организации функционирования вычислительных систем при обслуживании задач с нефиксированными параметрами // Материалы Российской научно-технической конференции "Информатика и проблемы телекоммуникаций", Новосибирск, 2006, с. 77-78.

50. Мамойленко С. Н. Об организации функционирования вычислительных систем при обслуживании задач с нефиксированными параметрами // Материалы Российской научно-технической конференции "Информатика и проблемы телекоммуникаций", Новосибирск, 2006, с. 75-76.

51. Khoroshevsky V.G., Mamoilenko S.N., Kurnosov M.G., Medvedeva N. A. Space-distributed multi-cluster computer system for training in parallel computational technologies // Proceedings of 7th International Siberian Workshop and Tutorial EDM'2006, Erlagol, Russia.

52. Мамойленко C.H., Седельников M.C., Медведева H. А. Опыт использования распределённой мультикластерной вычислительной системы для подготовки специалистов в области сетевых технологий // Сборник тезисов докладов XLVII Научно-методической конференции, Новосибирск, СибГУТИ, 2006 г., С. 32

53. Хорошевский В. Г.,Мамойленко С. Н., Седельников М. С. Распределенная система управления заданиями для кластерных вычислительных систем // Материалы Международной научно-технической конференции «Ин-

теллектуальные и многопроцессорные системы - 2005», пос. Дивноморское, 26 сентября - 1 октября, 2005 г., том 1, С. 65-69.

54. Хорошевский В. Г., Майданов Ю. С., Мамойленко С.Н., Седельников М. С. Организация мультипрограммных режимов функционирования распределенных кластерных вычислительных систем // Труды Второй Всероссийской научно конференции «Методы и средства обработки информации - 2005», Москва, МГУ, 5-7 октября, 2005 г., стр. 295-301.

55. Khoroshevsky V. G., Mamoilenko S. N., Maidanov Y.S., Sedelnikov M. S. Space-distributed multicluster computer system with multiprogramme regimes supporting // International science conference ACIT - Software Engineering, June 20-24. 2005, Novosibirsk, Russia, 136-138 p.p.

56. Мамойленко С. H., Седельников M. С. Распределенная кластерная вычислительная система как средство подготовки специалистов в области параллельных вычислительных процессов // Сборник тезисов докладов XLVI Научно-методической конференции, Новосибирск, СибГУТИ, 2005 г., С. 45

57. Хорошевский В. Г., Мамойленко С. Н., Майданов Ю. С. Живучие кластерные вычислительные системы // Материалы первой Всероссийской научной конференции «Методы и средства обработки информации», Москва, 2003, стр. 148-150.

58. Мамойленко С. Н. Непрерывная теоретико-игровая модель функционирования распределенных вычислительных систем // Материалы Международной научно-технической конференции «Информатика и проблемы телекоммуникаций», Новосибирск, 2003, 151-152

59. Мамойленко С.Н. Многоходовая теоретико-игровая модель функционирования распределённых большемасштабных вычислительных систем в условиях отказов ресурсов // Материалы Международной научно-технической конференции «Информационные системы и технологии», Новосибирск, 2003, Т.2. С. 147.

60. Мамойленко С.Н. Теоретико-игровая модель функционирования распределенной очереди задач в кластерных вычислительных системах // Материалы Всероссийской научной конференции «Наука. Технологии. Инновации.», Новосибирск, 2003, 4.2, С. 18-19.

61. Мамойленко С. Н., Кузнецов Д. В. Применение методов теории непре рывных игр в организации функционирования вычислительных систем // Материалы Международной научно-технической конференции "Информатика и проблемы телекоммуникаций", Новосибирск, 2002, С. 131-132

62. Мамойленко С. Н. Многоходовая игровая модель функционирования вычислительных систем // Материалы Международной научно-технической конференции "Информатика и проблемы телекоммуникаций", Новосибирск, 2002, С. 132-133.

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

Материалы Региональной научной конференции студентов, аспирантов и молодых учебных "Наука. Техника. Инновации.", Новосибирск, 2002, 4.2, С. 10-12.

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

Результаты диссертационной работы, выносимые на защиту, принадлежат автору, что подтверждено публикациями в научных изданиях. В работах опубликованных в соавторстве автору принадлежат: способы и алгоритмы организации функционирования распределённых ВС в режиме обработки наборов задач [1-5] и обслуживании потоков задач [6-9]. В работах [10-20, 2831, 34, 35, 37, 39, 40, 42, 44, 45-47, 61] представлены постановки задач исследования, авторские алгоритмы и результаты их моделирования. В работах [23-25, 36, 48, 49, 50] автором написаны разделы, отражающие результаты по организации функционирования распределённых ВС в мультизадачных режимах. В работах [6, 8, 26, 43, 53-57] представлено участие автора в создании пространственно-распределённой мультикластерной вычислительных системы. Работы [21, 22, 27, 32, 33, 38, 41, 51, 52, 56] подтверждают внедрение результатов, полученных автором, в практические разработки и учебный процесс Центра параллельных вычислительных технологий и Кафедры вычислительных систем ФГОБУ ВПО "СибГУТИ". Во всех совместных работах авторство неделимое.

Мамойленко Сергей Николаевич

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

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

Подписано в печать 14 марта 2012, Формат бумаги 60x84/16, отпечатано на ризографе, шрифт № 10, изд. л. 2.25, заказ № 17, тираж 180 экз., ФГОБУ ВПО "СибГУТИ". 630102, г. Новосибирск, ул. Кирова, д. 86.

Сокращения и обозначения

Введение

Глава 1. ОБЪЕКТ И ПРЕДМЕТ ИССЛЕДОВАНИЙ.

1.1. Понятие «вычислительная система». Модель коллектива вычислителей

1.2. Принципы технической реализации модели коллектива вычислителей

1.3. Архитектурные свойства вычислительных систем.

1.4. Классификация вычислительных систем.

1.5. Распределённые вычислительные системы.

1.6. Примеры современных распределённых ВС

1.6.1. Система К Computer.

1.6.2. Система МВС-ЮОК.

1.6.3. Система СКИФ-Сибирь

1.6.4. Система НКС-ЗОТ

1.7. Параллельные алгоритмы и программы

1.8. Понятие «задача». Классификация задач.

1.9. Режимы функционирования распределённых вычислительных систем.

1.10. Программное обеспечение распределённых ВС.

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

1.12. Основные сведения из теории игр.

1.12.1. Методы решения конечных антагонистических игр

1.12.1.1. Метод Брауна-Робинсон.

1.12.1.2. Симплекс-метод.

1.12.2. Решение бесконечных антагонистических игр.

1.12.3. Решение игровых ситуаций с «природой»

1.13. Выводы.

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

2.1. Постановка задачи.

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

2.3. Этап 1. Формирование «укрупненных» задач

2.3.1. Случай 1. Задано ограничение на значение средней «удовлетворённости» пользователей.

2.3.1.1. Эвристический алгоритм «Однократный случайный выбор значений кр>

2.3.1.2. Стохастический алгоритм «Многократный случайный выбор значений кр>

2.3.1.3. Генетический алгоритм формирования «укрупнённых» задач.

2.3.2. Случай 2. Средняя «удовлетворённость» пользователей является целевой функцией.

2.3.2.1. Генетический алгоритм поиска решения многокритериальной задачи.

2.3.2.2. Параллельный генетический алгоритм поиска решения многокритериальной задачи

2.4. Этап 2. Определение последовательности запуска «укрупнённых» задач на решение.

2.5. Этап 3. Формирование итогового расписания решения задач набора.

2.6. Моделирование алгоритмов.

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

2.6.2. Сравнение эффективности алгоритмов.

2.7. Выводы.

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

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

3.2. Определение рангов «укрупнённых» задач.

3.2.1. Определение рангов «укрупнённых» задач при условии выделения для их решения всех ЭМ подсистем распределённой ВС.

3.2.2. Выбор рангов «укрупненных» задач с учётом отказов ресурсов распределённых ВС.

3.2.3. Параллельная версия алгоритма Брауна,-Робинсон

3.2.4. Параллельная версия симплекс-метода.

3.3. Определение времени решения «укрупнённых» задач.

3.4. Определение последовательности опроса диспетчеров для поиска «укрупнённых» задач.

3.5. Моделирование предложенных алгоритмов.

3.5.1. Определение рангов «укрупнённых» задач.

3.5.2. Определение времени решения «укрупнённых» задач

3.5.3. Определение последовательности опроса диспетчеров . 141 3.6. Выводы.

Глава 4. Пространственно-распределённая мультикластерная вычислительная система.

4.1. Архитектура пространственно-распределённой мультикластерной вычислительной системы.

4.2. Программное обеспечение пространственно-распределённой муль-тикластерной ВС

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

4.4. Разработка диспетчера распределённой очереди задач.

4.5. Выводы.

Актуальность работы. Распределённые вычислительные системы (ВС) являются современным инструментарием обработки информации (список Тор500 (Ноябрь, 2011) суперкомпьютеров мира). В Российской Федерации технологии и программное обеспечение распределённых и высокопроизводительных ВС относят к критически важным (указ Президента Российской Федерации от 7 июля 2011 г. № 899) [311].

Исследования в области распределённых ВС ведутся с середины XX столетия. С тех пор в нашей стране и за рубежом выполнен ряд фундаментальных работ, посвященных проблемам организации высокопроизводительных вычислительных средств: проведены исследования по теории функционирования и построению оптимальных (макро)структур ВС, проработаны многие аспекты создания программного обеспечения, исследован широкий круг задач, допускающих их эффективную реализацию на распределённых ВС. Построены отечественные вычислительные системы с программируемой структурой: «Минск 222», СУММА, МИНИМАКС, МИКРОС, МВС, СКИФ и др.

Фундаментальный вклад в теорию и практику вычислительных систем и параллельных вычислительных технологий внесли советские, российские и зарубежные учёные, среди которых [36, 37, 39, 115, 117, 118, 123, 125. 126, 133, 143, 146, 153-159, 170, 173, 174, 178-180, 200, 212-215, 253, 255. 259, 284286, 289, 290, 293, 295, 296, 300, 307, 309, 315, 318, 319, 321, 342, 344, 346, 350]: Е.П. Балашов, В. В. Бетелии, B.C. Бурцев, В. В. Васильев, В.М. Глушков, В.Ф. Евдокимов, Э.В. Евреинов, A.B. Забродин, В. П. Иванников, М.Б. Игнатьев, А. В. Каляев, И. А. Каляев, J1. Н. Королёв, С. А. Лебедев, А. О. Лацис, В. К. Левин, И. И. Левин, Г. И. Марчук, Ю. И. Митропольский, Д. А. Поспелов, И. В. Прангишвили, Д. В. Пузанков, Г. Е. Пухов, Г. Г. Рябов, A.A. Самарский, В. Б. Смолов, А. Н. Томилин, Я. А. Хетагуров, В. Г. Хорошевский, Б.Н. Четверушкин, Ю. И. Шокин, H.H. Яненко, S. Cray, М. Flynn, D. Feit-elson, I. Foster, D. Hillis, C. Kesselman, DL. Slotnick, А. ТапепЬаити другие.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов работы. Основные результаты исследований нашли применение в работах по созданию и развитию пространственно-распределённой мультикластерпой ВС ЦПВТ ФГОБУ ВПО "СибГУТИ" и Лаборатории ВС ИФП СО РАН. Диссертационные исследования выполнялись в рамках федеральных целевых программ «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 годы» (ГК №02.514.11.0002 «Разработка программных технологий для развития российского сегмента Грид, систем параллельного программирования, систем компьютерной графики») и «Научные и научно-педагогические кадры инновационной России» (ГК №02.740.11.0006 «Проведение исследований в области распределённых вычислительных систем и развитие научно-учебного центра параллельных вычислительных технологий ФГОБУ ВПО "СибГУТИ"»). Работа поддержана грантами Российского фонда фундаментальных исследований (№ 00-01-00126, 02-07-06099, 02-07-09380, 03-07-06008, 08-07-00022, 09-07-00095, 11-07-00109), грантами Президента РФ по поддержке молодых российских учёных и ведущих научных школ (№НШ-2121.2008.9, НШ-5176.2010.9, НШ-2175.2012.9,

МК-2317.2012.9), атак же грантами ФГОБУ ВПО"СибГУТИ" (2008-2011 гг.). Результаты работы внедрены в учебный процесс Сибирского государственного университета телекоммуникаций и информатики. Практическое использование результатов диссертационных исследований подтверждается соответствующими актами о внедрении.

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

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

• Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы» (2003 г., г. Геленджик);

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

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

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

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

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

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

• Международной научно-технической конференции «Информатика и проблемы телекоммуникаций» (2001-2011 гг., г. Новосибирск);

• Международной научно-технической конференции «Информационные системы и технологии» (2003 г., г. Новосибирск);

• Первой Всероссийской научной конференции «Методы и средства обработки информации» (2003 г., г. Москва);

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

• Школе-семинаре «Распределённые кластерные вычисления» (2001 г. г. Красноярск).

• Научно-техническом семинаре ФГОБУ ВПО "СибГУТИ" (ежегодно);

Публикации. По теме диссертации опубликовано 63 работы, в том числе 9 — в изданиях из перечня ВАК.

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

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

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

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

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

4.5 Выводы

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

2. Система оснащена инструментарием параллельного мультипрограммирования, разрабатываемом Сибирской научной школой распределённых вычислительных систем и параллельного моделирования (руководитель — член-корреспондент РАН В.Г. Хорошевский).

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

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

Заключение

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

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

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

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

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

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

2.2. Построены теоретико-игровые модели и алгоритмы для децентрализованных диспетчеров очередей задач и планировщиков ресурсов распределённых ВС. Алгоритмы позволяют формировать «укрупнённые» задачи из задач потока и сокращают простои ресурсов распределённых ВС. Они учитывают топологию логических связей между планировщиками и диспетчерами, стохастическую природу потоков задач и отказы ресурсов распределённых вычислительных систем.

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

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

3. При непосредственном участии диссертанта создана пространственнораспределённая мультикластерная ВС.

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

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

Результаты диссертационной работы, выносимые на защиту, принадлежат автору, что подтверждено публикациями в изданиях из списка ВАК [64, 74, 114, 167, 228, 254, 270, 332, 333] и трудах конференций [91, 92, 128-130, 164-166, 168, 175, 183, 203, 204, 220-224, 226, 227, 229-250, 266, 273, 280, 282, 287, 288, 292, 310, 324-331, 334-339].

В работа,х опубликованных в соавторстве автору принадлежат: способы и алгоритмы организации функционирования распределённых ВС в режиме обработки наборов задач [114, 167, 228, 254, 332] и обслуживании потоков задач [64, 74, 270, 333]. В работах [64, 91, 92, 114, 128-130, 164-168, 175, 183, 203, 204, 220-224, 226-250, 254, 266, 273, 280, 282, 287, 288, 292, 325-339] представлены постановки задач исследования, авторские алгоритмы и результаты их моделирования. В работах [64, 128-130, 254, 273, 280, 292, 325-332, 334-339] автором написаны разделы, отражающие результаты по организации функционирования распределённых ВС в мультизадачных режимах. В работах [91, 92, 114, 128-130, 168, 231, 238, 246, 250, 254, 292, 325-332, 336] представлено участие автора в создании пространственно-распределённой мультикластерной вычислительных системы. Работы [64, 91, 92, 114, 128-130, 175, 183, 203, 204, 220-224, 226-250, 254, 266, 273, 280, 282, 287, 288, 292, 310, 324-332, 334-339] подтверждают внедрение результатов, полученных автором, в практические разработки и учебный процесс Центра параллельных вычислительных технологий и Кафедры вычислительных систем ФГОБУ ВПО "СибГУТИ".

Во всех совместных работах авторство неделимое.

1. Allinea DDT.— URL: http://www.allinea.com (online; accessed: 24.02.2011).

2. Ansel J., Arya K., Cooperrnan G. DMTCP: Transparent Checkpointing for Cluster Computations and the Desktop // Proc. of IEEE International Parallel and Distributed Processing Symposium (IPDPS'09).— IEEE Press, 2009.- Pp. 1-12.

3. Baker M. Cluster Computing White Paper. — UK, Portsmouth: University of Portsmouth, 2000. 119 pp.

4. Baptiste Ph., Le Pape С., Nwijten W. Constraint-based scheduling: applying constraint programming to scheduling problems. — Kluwer Academic Publishers, 2001. 198 pp.

5. Barsanti L., Sodan A. Adaptive job scheduling via predictive job re-source allocation // Lecture Notes in Computer Science. — 2007. — Vol. 437G. — Pp. 115-140.

6. The Beowulf Project. — 2012.— URL: http://beowulf.es.embnet.org/ beowulf.html (дата обращения: 29.02.2012).

7. Berkeley Unified Parallel С (UPC) Project. 2010.- URL: http://upc. lbl.gov (дата обращения: 12.04.2010).

8. Bin Packing in Multipl Dimensions: Inapproximability Results and Approximation Schemes / L. Bansal, J.R. Correre, C. Kenyon, M. Sviridenko // Mathematics of Operations Research. — 2006. — Vol. 31. — Pp. 31-49.

9. Dlazewicz J., Lenstra J.K. Scheduling subject to resource con-straints:classication and complexity // Discrete Applied Mathematics. — 1983,- Vol. 5,- Pp. 11-24.

10. Doctor F.F. Some efficient multi-heuristic procedures for resourcecon-strained project scheduling // European journal of operational research.— 1990.-Vol. 49(1).- Pp. 3-13.

11. Dortfeldt A. Hermann G. A Parallel Genetic Algorithm for Solving the Container Loading Problem International Transactions in Operational Research. Issue 4, July 2002. — Vol. 9. — 497 pp.

12. Bortfeldt A.; Gehring H. Two metaheuristics for strip packing problems /7 5-th International Conference of the Decision Sciences Institute. — Athen, Griechenland: 4.-7. Juli 1999.

13. Brown G. W. Iterative Solutions of Games by Fictious Play // Activity Analysis of Production and Al-loca,tio, Cowles Commission for Research in Economics. — 1951. — Pp. 374-376.

14. Brucker P. Scheduling Algorithms. — Springer-Verlag, 2001. — 365 pp.

15. Brucker P. Knust S. Complex scheduling. — Berlin, Heidelberg, Germany: Springer-Verlag, 2006. — pp.

16. Burke E.K., Kendall G., Whitwell G. A New Placement Heuristic for the

17. Orthogonal Stock-Cutting Problem // Operations Research. — 2004. — Vol. 52(4).- Pp. 655-671.

18. CEMon. — URL: http://vdt.cs.wisc.edu/components/cemon.html (online; accessed: 24.02.2011).

19. Chapel Programming Language Homepage: Overview. — 2010. — URL: http://chapel.cray.com (дата обращения: 12.04.2010).

20. Characterization of backlling strategies for parallel job scheduling / S. Srini-vasan, R. Kettimuthu, V. Subramani, S. Sadayappan //In proceedings of the International Conference on Parallel Processing Workshops. — Los Alamitos: 2002. Pp. 514-519.

21. Characterizing the Performance of "Big Memory" on Blue Gene Linux / K. Yoshii, K. Iskra, H. Naik et al. // Proceedings of the 2009 International Conference on Parallel Processing Workshops.— Washington, DC, USA: IEEE Computer Society, 2009.- Pp. 65-72.

22. Cirne W., Berman F. A model for moldable supercomputer jobs // 15th Intl. Parallel and Distributed Processing Symp. — Apr. 2001.— URL: http : //www. lsd. dsc. uf pb. br/papers/moldability-model. pdf (online; accessed: 12.04.2010).

23. Cirne W., Grande C., Berman F. When the herd is smart aggregate behavior in the selection of job request // IEEE Transactions in Parallel and Distributed Systems. 2003. - Vol. 14. - Pp. 181-192.

24. Cluster Resources Inc. Moab workload manager administrator's guide ver.45. — 2012. — URL: http: //www. clusterresources. com/products/mwm/ docs/ (online; accessed: 24.02.2011).

25. Cluster resources : Products Maui Cluster Scheduler. — URL: http: //www. clusterresources. com/pages/products/ maui-cluster-scheduler .php (online; accessed: 25.06.2010).

26. Co-Array Fortran. — 2010. — URL: http: //www. co-array. org (дата обращения: 12.04.2010).

27. Computing | Oracle Grid Engine | Software | Sun Microsystems. — URL: http://www.sun.com/software/sge (online; accessed: 25.06.2010).

28. Davis L. Job shop scheduling with genetic algorithms // In proceedings of an International Conference on Genetic Algorithms and their Applications. — Pittsburgh: Lawrence Erlbaum Associates, 1985. — Pp. 136-140.

29. Davis L. Genetic Algorithms and Simulated Annealing. — San Mateo: Morgan Kaufman Publisher, 1987. — 216 pp.

30. Debugging on Intel(R) Platforms.— URL: http: //software . intel. com/ еп-us/articles/debugging-intel-platf orms/ (online; accessed: 24.02.2011).

31. Decentralized job scheduling on computational Grids using distributed back lling / W. Qingjiang, G. Xiaolin, Z. Shouqi, L. Yang // Concurrency and Computation: Practice and Experience.— 2006.— Vol. 18(14).— Pp. 1829-1838.

32. Devis E. W.; Heidorn J.H. An algorithm for optimal project scheduling under multiple resource constraints // Management Science. — 1971,— Vol. 17(12).- Pp. 803-817.'

33. Devis E. W., Patterson J.H. A Comparison of Heuristic and Optimum Solutions in Resource-Constrained Project Scheduling // Management Science. 1975. - Vol. 21(8). - Pp. 944-955.

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

35. Drozdowski M. Scheduling for paralell processing. — London: Springer London, 2009. 256 pp.

36. Fcitclson D.G., Jettc M.A. Improved utilization and responsiveness with gang scheduling in Job Scheduling Strategies for Parallel Processing // Lecture Notes in Computer Science. 1997. - Vol. 1291. - Pp. 238-261.

37. Feitelson D.G., Rudolph L. Metrics and benchmarking for parallel job scheduling // Lecture Notes in Computer Science. — 1998.— Vol. 1459.— Pp. 1-24.

38. Flynn M. Some Computer Organisations and Their Effectiveness // IEEE Trans. Computers. 1972. - Vol. 21, no. 9. - Pp. 948-960.

39. Flynn M. Very high-speed computing system /'/ Proc. of IEEE. — 1996. — no. 54,- Pp. 1901-1909.

40. The Fortress Language Specification. — 2010.— URL: http://research. sun.com/projects/plrg/fortress.pdf (дата обращения: 12.04.2010).

41. Fox M.S., Smith S.F. ISIS a Knowledge-based system for factory scheduling // Expert Systems. 1984. - Vol. 1(1). - Pp. 25-49.

42. GDB: The GNU Project Debugger.- URL: http://www.gnu.org/ software/gdb (online; accessed: 24.02.2011).

43. Ganglia Monitoring System.— URL: http://ganglia.sourceforge.net (online; accessed: 24.02.2011).

44. Gantt Henry L. A graphical daily balance in manufacture // Transactions of the American Society of Mechanical Engineers. — T. XXIV. — ACME, 1903. C. 1322-1336.

45. Garey M., Graham R. Bounds for multiprocessor scheduling with resource constraints // S1AM Journal on Computing. — 1975.— Vol. 4(2).— Pp. 187-200.

46. Garey M., Johnson D. Computers and intractability: a guide to the theory of NP-Completeness. — New York: W. H. Freeman and Co., 1990. — 338 pp.

47. Goldberg D.E. Genetic algorithms in Search, Optimization and Machine Learning, Reading. — MA: Addison-Wesley Publishing Company, 1989.

48. Hargrove P.H., Duell J.C. Berkeley Lab Checkpoint/Restart (BLCR) for Linux Clusters // In Proceedings of SciDAC 2006. 2006.

49. Harvey W.D., Ginsberg M.L. Limited discrepancy search / University of Oregon. CIRL, 1995. - 80 pp.

50. Havanki W.A., Danerjia S., Conte T.M. Treegion Scheduling for Wide Issue Processors // In proceedings of 4th Intl. Symp. on High Performance Computer Architecture. 1998. - Pp. 266-276.

51. Hildum D. Flexibility in a knowledge-based system for solving dynamic resource-constrained scheduling problems / University of Massachusetts. — Amherst, 1994.

52. Hopper E., Turton D.C.H. An Empirical Investigation of Meta-Heuristic and Heuristic Algorithms for a 2D Packing Problem // European Journal of Operational Research. 2001. - Vol. 128(1). - Pp. 34-57.

53. Husbands P. Genetic algorithms for scheduling / AISB Quarterly. — 1996.

54. IBM Redbooks Workload Management with LoadLeveler. — URL: http : //www. redbooks. ibm. com/abstracts/sg246038. html (online; accessed: 25.06.2010).

55. Intel Trace Analyzer и Intel Trace Collector версии 7.2 для Linux или Windows. — URL: http://www.intel.com/cd/software/products/ emea/rus/379896.htm (online; accessed: 24.02.2011).

56. Jackson D., Snell Q., Clement M. Core algorithms of the Maui scheduler // Lecture Notes in Computer Science. 2001. - Vol. 2221. - Pp. 87-102.

57. Jansen Klaus, Mastrolilli Monaldo. Approximation schemes for parallel machine scheduling problems with controllable processing times // Computers & OR. 2004. - Vol. 31, no. 10. - Pp. 1565-1581.

58. Job Submission Description Language (JSDL). Specification, Version 1.0. — 2005. — URL: http://www.gridforum.org/documents/GFD.56.pdf (дата обращения: 08.02.2012).

59. Johnson T.J. An algorithm for the resource-constrainted project scheduling problem. Doctoral Thesis /' Massachusetts Institute of Technology. — Cambridge, 1967.

60. KOJAK. — URL: http://www.fz-juelich.de/zam/kojak (online; accessed: 24.02.2011).

61. Kelly S.M., Brightwell R. Software architecture of the light weight kernel, Catamount // in Proceedings of the 2005 Cray User Group Annual Technical Conference. — 2005.

62. Khoroshevsky V.G., Mamoilenko S.N. Stochastically optimal functioning strategies of distributed computing systems // Optoelectronics, Instrumentation and da,ta processing. — 2003. — Vol. 39, no. 2. — Pp. 68-76.

63. Krallmann J., Schwiegelshohn U., Yahyapour R. On the Design and Evaluation of Job Scheduling Systems // Lecture Notes in Computer Science.— 1999. Vol. 1659. - Pp. 17-42.

64. Land A.H. Doig A.G. An autmatic method of solving discrete programming problems // Economctrica. 1960. - Vol. 28. - Pp. 497-520.

65. Lawler E.L., Wood D.E. Branch and Bound methods: a survey // Operations Research. 1966. - Vol. 14(4). - Pp. 699-719.

66. Lodi A., Martello S., M. Monaci. Two-dimensional packing problems: a survey // European Journal of Operational Research. — 2002.— Vol. 141). — Pp. 241-252.

67. MPICH2: High-performance and Widely Portable MPI. 2012. — URL: http://www.mcs.anl.gov/research/projects/mpich2 (дата обращения: 29.02.2012).

68. MonALISA.— URL: http://monalisa.caltech.edu (online; accessed: 24.02.2011).

69. Mualem A.W., Feitelson D.G. Utilization, Predictability, Workloads, and User Runtime Estimates in Scheduling the IBM SP2 with Backlling // In proc. 12th Intl. Parallel Processing Symposium. — Vol. 141).— 1998. — Pp. 542-546.

70. Nagios The Industry Standard in IT Infrastructure Monitoring. — URL: http://www.nagios.org (online; accessed: 24.02.2011).

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

72. On cluster computer functioning / V.G. Khoroshevsky, S.N. Mamoilenko, Yu. S. Maidanov, S.V. Smirnov // Optoelectronics, Instrumentation and data processing. — 2004. — Vol. 40, no. 1. — Pp. 35-42.

73. Open MPI: Open Source High Performance Computing. — 2012,— URL: http://www.open-mpi.org (дата обращения: 29.02.2012).

74. PBS Works Enabling On-Demand Computing.— URL: http://www. openpbs.org (online; accessed: 25.06.2010).

75. PVM: Parallel Virtual Machine. — 2012.— URL: http://www.csm.ornl. gov/pvm/ (дата обращения: 29.02.2012).

76. Panwalker S., Iskander W. A survey of scheduling rules // Operations Research. 1997. - Vol. 25(1). - Pp. 45-61.

77. Parallel workloads archive. — 2012.— URL: http://www.cs.huji.ac.il/ labs/parallel/workload/ (online; accessed: 08.02.2012).

78. Patterson J.H. A comparison of exact approaches for solving the multiple constrained resource, project scheduling problem // Management Science. — 1984. Vol. 30(7). - Pp. 854-867.

79. Performance bounds for level-oriented two-dimensional packing algorithms / E.G. Coffman Jr, M.R. Garey, D.S. Johnson, R.E. Tarjan // S1AM Journal on Computing. — 1980. — Vol. 9. — Pp. 808-826.

80. Queyranne M., Schultz A.S. Polyhedral approaches to machine scheduling. Preprint N 408/1994,— Berlin: Technical University of Berlin, Department of Mathematics, 1994. — 61 pp.

81. R. Bellman. Mathematical aspects of scheduling theory // Journal of the Society of Industrial and Applaid Mathematics.— Vol. 4,— 1956. — Pp. 168-205.

82. Robinson J. An Itertive Method of Solving a Game // Ann. Math. — 1951. — no. 54,- Pp. 295-301.

83. Rohifshagen P., Bullinaria J.A. A genetic algorithm with exon shuffling crossover for hard bin packing problems // Proceedings of the 9th annual conference on Genetic and evolutionary computation. — NY, USA: ACM NewYork, 2007. Pp. 1365-1371.

84. Scheduling parallel tasks to minimize average response time / J.J. Turek, U. Schwiegelshohn, J.L. Wolf, P. Yu // In Proceedings of the 5th SIAM Symposium on Discrete Algorithms. — 1994. — Pp. 112-121.

85. Schwiegelshohn U., Yahyapour R. Analysis of First-Come-First-Serve Parallel Job Scheduling // In proceedings of the 9th SIAM Symposium on Discrete Algorithms. Vol. 4. - 1998. - Pp. 629-638.

86. Shmueli E., Feitelson D. G. Backfilling with lookahead to optimize the packing of parallel jobs // J. Parallel and Distributed Comput.— Sep. 2005,— Vol. 65(9).- Pp. 1090-1107.

87. Smith S.F., Ow P. The use of multiple problem decompositions in time constrained planning tasks // In proceedings of the ninth international joint conference on artificial intelligence. — Vol. 2. — 1985. — Pp. 1013-1015.

88. Space-distributed multi-cluster computer system for training in parallel computational technologies / V.G. Khoroshevsky, S.N. Mamoilenko,

89. M.G. Kurnosov, N.A. Medvedeva // Proceedings of 7th International Siberian Workshop and Tutorial EDM'2006. Erlagol, Russia: 2006.

90. Steuer R.E. Multiple Criteria Optimization, Theory, Computation and Application. — Krieger Pub Co, 1986. — 546 pp.

91. TAU Tuning and Analysis Utilities. — URL: http://www.cs.uoregon. edu/research/tau/home.php (online; accessed: 24.02.2011).

92. TORQUE.— URL: http://www.clusterresources.com/pages/ products/torque-resource-manager .php (online; accessed: 25.06.2010).

93. Team T.B. An overview of the BlueGene/L supercomputer // Proceedings of SC2002: High Performance Networking and Computing. — Baltimore: MD, 2002.

94. Theory and practice in parallel job scheduling / Dror G. Fcitelson, Larry Rudolph, Uwe Schwiegelshohn, Kenneth C. Parkson Sevcik, Kenneth C.and Wong // Job Scheduling Strategies for Parallel Processing. — 1997. — Vol. 1291,- Pp. 1-34.

95. Titanium Project Home Page.— 2010.— URL: http://titanium.cs. berkeley.edu (дата обращения: 12.04.2010).

96. Top500. — URL: http://www.top500.org (online; accessed: 25.06.2010).

97. TotalView — Dynamic source code and memory debugging for С, CH— and Fortran applications. — URL: http: //www. roguewave. com/products/ totalview-family/totalview.aspx (online; accessed: 24.02.2011).

98. Turek J., Wolf J., Yu P. Approximate algorithms for scheduling paralleliz-able tasks // In 4th Annual ACM Symposium on Parallel Algorithms and Architectures. 1992. - P. 323-332.

99. VAMPIR.- URL: http://www.vampir.eu (online; accessed: 24.02.2011).

100. VMScluster. — 2012,- URL: http://en.wikipedia.org/wiki/ VMScluster (дата обращения: 29.02.2012).

101. Valgrind Home.— URL: http://valgrind.org (online; accessed: 24.02.2011).

102. VampirTrace. — URL: http://www.vampir.eu/flyer/Flyer VampirTraceSC09.pdf (online; accessed: 24.02.2011).

103. Vasupongayya Sangsurec. Parallel Computer Job Scheduling Policies: A Review // PDPTA / Ed. by Hamid R. Arabnia. Las Vegas, NV.: IEEE Computer Society Press, 2009. — Pp. 166-172.

104. Wang P. Y., Valenzuela C.L. Data set generation for rectangular placement problems // European Journal of Operational Research. — 2001,— Vol. 134,- Pp. 378-391.

105. Windows HPC Server 2008 Microsoft Supercomputing - Supercomputers. — URL: http://www.microsoft.com/hpc/ (online; accessed: 25.06.2010).

106. X10 Programming Language. — 2010. — URL: http://xl0-lang.org (дата обращения: 12.04.2010).

107. A. Таха Хэмди. Введение в исследование операций / Под ред. А.А. Минь-ко. — 7-е изд., пер. с англ. изд.— М.: Издательский дом «Вильяме», 2005.- 912 с.

108. Архитектура и программное обеспечение пространственно-распределённых вычислительных систем / В.Г. Хорошевский, М.Г. Курносов, С.Н. Мамойленко, А.Ю. Поляков // Вестник ГОУ ВПО «СибГУТИ».-2010. — № 2.- С. 112-122.

109. Архитектура цифровых процессоров обработки сигналов / В.Б. Бетелин, Е.В. Грузипова, А.А. Кольцова и др.— М.: РАН. Научный совет по комплексной проблеме «Кибернетика», 1994. — 20 с.

110. Бабаян Б.А., Бочаров А.В., Волин А.С. Многопроцессорные ЭВМ и методы их проектирования. — М.: Высшая школа, 1990. — 143 с.

111. Балашов Е.П., Григорьев В.Л., Петров Г.А. Микро и мини-ЭВМ. Уч. пос. для ВУЗов,— J1.: Энергоатом-издат. Ленинградское отд., 1984.— 376 с.

112. Балашов Е.П., Пузпаков Д.В., Смолов В.Б. Микропроцессоры и микропроцессорные системы: уч. пособие для ВУЗов / Под ред. В.Б. Смолов. — М.: Радио и связь, 1981. — 326 с.

113. Барский А.Б. Планирование параллельных вычислительных процессов и организация. — М.: Машиностроение, 1980.— 192 с.

114. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. — М.: Радио и связь, 1990. — 256 с.

115. Бахтин В.А. Гибридная модель параллельного программирования DVM/OpenMP: Автореф. дис. на соиск. научн. ст. к.ф.-м.н. (05.13.11) / Институт прикладной математики им. М.В. Келдынта РАН,— М. 2008.- 20 с.

116. Берзии Е.А. Оптимальное распределение ресурсов и теория игр / Под ред. Е.В. Золотова. — М.: Радио и связь, 1983. — 216 с.

117. Бетелин В. Б. и др.. Архитектура цифровых процессоров обработки сигналов. — М.: РАН, 1993. — 20 с.

118. Боровков A.A. Вероятностные процессы в теории массового обслуживания. М.: ГИФМЛ, 1971. - 368 с.

119. Бурцев B.C. Супер-ЭВМ. Сборник научных трудов, — М.: АН СССР, отдел вычислительной математики, 1992. — 95 с.

120. Бур-цев B.C. Параллелизм вычислительных процессов и развитие архитектур суперЭВМ. М.: ИВВС РАН, 1997.

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

122. В.Г. Хорошевский, Мамойленко С.Н., Майданов Ю.С. Живучие кластерные вычислительные системы // Материалы первой Всероссийской научной конференции «Методы и средства обработки информации». — Москва: 2003. С. 148-150.

123. В.Г. Хорошевский, Мамойленко С.Н., Майданов Ю.С. Распределенные кластерные вычислительные системы // Материалы Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы». — Т. 1. — Геленджик: 2003. — С. 36-38.

124. В.М. Курейчик. Генетические алгоритмы. Монография. — Таганрог: ТР-ТУ, 1998. 242 с.

125. Вальковский В.А. Распараллеливание алгоритмов и программ. Структурный подход. — М.: Радио и связь, 1989. — 176 с.

126. Васильев В.В., Додонов А.Г. Многопроцессорные вычислительные структуры для анализа задач на сетях // Проблемы электроники и вы-чис.лите.льной техники. — 1976. — С. 85-97.

127. Вишневский В.М. Задачи оптимального управления в телеавтоматических системах массового обслуживания: Автореф. дис. на соиск. научн. ст. к.т.н. (05.13.01) / 1.-М., 1974.- 23 с.

128. Водяхо А.И., Горпец H.H., Пузанков Д.В. Высокопроизводительные системы обработки данных: уч. пос. для ВУЗов. — М.: Высшая шк., 1997. — 304 с.

129. Воеводин В.В. Математические модели и методы в параллельных процессах. — М.: Наука, 1986. — 296 с.

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

131. Воробьев H.H. Бесконечные антагонистические игры. Сб. статей, — М.: Физматгиз, 1963. — 504 с.

132. Воробьев H.H. Теория игр. Лекции для экономистов-кибеирпетиков.— Л.: ЛГУ, 1974.- 245 с.

133. Гер г ель В. П. Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. — Нижний Новгород: Изд-во ННГУ, 2003. 184 с.

134. Гершуни Д. С. Планирование вычислений в системах жесткого реального времени (обзор и перспективы) // Вычислительная техника. Системы, управления. — 1991. — Т. 6. — С. 4-51.

135. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы / Под ред. В.М. Курейчика. — 2-е изд., испр. и доп. изд. — М.: ФИЗМАТ-ЛИТ, 2006. 320 с.

136. Глушков В.М., Ющенко Е.Л. Вычислительная машина «Киев». Математическое описание. — Киев: Гос. тех. изд-во УССР, 1962. — 183 с.

137. Гнеденко В.В., Беляев Ю.К., Соловьев А.Д. Математические методы в теории надежности. — М.: Наука, 1965. — 524 с.

138. Головистиков A.B. Задачи двумерной упаковки и раскроя: обзор. // Информатика. — 2008. Т. 20. - С. 18-33.

139. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. — М.: Радио и связь, 1983. — 272 с.

140. Головкин Б.А. Параллельные вычислительные системы, — М.: Наука, 1990.- 520 с.

141. Гэри М., Дэ!сонсон Д. Вычислительные машины и труднорешаемые задачи, пер. с англ. — М.: Мир, 1982. — 416 с.

142. Дмитриев Ю.К., Хорошевский В. Г. Вычислительные системы из мини-ЭВМ / Под ред. Э.В. Евреинов. — М.: Радио и связь, 1982. — 304 с.

143. Додонов А.Г., Кузнецова М.Г., Горбачик Е.С. Введение в теорию живучести вычислительных систем. — Киев: Наукова думка, 1990. — 180 с.

144. Дрешер М. Стратегические игры. Теория и приложения / пер. с англ. — М.: Советское радио, 1964. — 351 с.

145. Дроздов Е.А., Пятибратов А.П. Основы построения и функционирования вычислительных систем. — М.: Энергия, 1973. — 368 с.

146. Евдокимов В.Ф. Вопросы исследования и применения электронных моделей систем с распределёнными параметрами: Автореф. дис. на соиск. уч. ст. к.т.н. / -. — Киев, 1968. — 23 с.

147. Евдокимов В.Ф., А.И. Сгпасюк. Параллельные вычислительные структуры па основе разрядных методов. — К.: Наукова думка, 1987. — 311 с.

148. Евреииов Э.В. О возможности построения вычислительных систем в условиях запаздывания сигналов // Вычислительные системы. — 1962. — № 3.- С. 3-16.

149. Евреииов Э.В. Однородные вычислительные системы, структуры и среды. — М.: Радио и связь, 1981. — 208 с.

150. Евреинов Э.В., Косарев Ю.Г. Однородные универсальные вычислительные системы высокой производительности. — Новосибирск: Наука. Сибирское отд-е, 1966. — 308 с.

151. Евреинов Э.В., Прангишвили И. В. Цифровые автоматы с настраиваемой структурой. — М.: Энергия, 1974. — 240 с.

152. Евреинов Э.В., Хорошевский В. Г. Однородные вычислительные системы / Под ред. С.Д. Пашкевич. — Новосибирск: Изд-во "Наука", Сибирское отделение, 1978. — 319 с.

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

154. Ефимов A.B., C.H. Мамойленко C.H., Перыгикова E.H. Организация функционирования распределенных вычислительных систем при обработке масштабируемых задач // Вестник ТГУ: Управление, вычислительная техника и информатика. — 2011. — 2(15). — С. 51-60.

155. Живучая кластерная вычислительная система / В.Г. Хорошевский, Ю.С. Майданов, С.Н. Мамойленко и др. // Труды школы-семинара «Распределенные кластерные вычисления»,— Красноярск: 2001. — С. 109-113.

156. Жук С.Н. Онлайновый алгоритм упаковки прямоугольников в несколько полос с гарантированными оценками точности // Материалы XLVII международной научно-технической конференции «Студент и научно-технический прогресс». — Т. 12. — 2007. — С. 7-16.

157. Забродин A.B. Параллельные вычислительные технологии. Состояние и перспективы. — М., 1995.

158. Заварыкин В.М., Житомирский В.Г., Лапчик М.П. Численные методы: уч. пос. для студ. физ.-мат. спец. пед. ун-тов. — М.: Просвещение, 1990.

159. Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения /

160. A.C. Мухачева, A.B. Чиглинцев, М.А. Смагин, Э.А. Мухачева /'/' Машиностроение. — 2001. — № 10. — С. 24.

161. Иванников В.П. Операционная система НД-70 для БЭСМ-6: Автореф. дис. на соиск. уч. ст. к.ф.-м.н. / -. — М., 1971.

162. Игнатьев М.Б. Управление вычислительными процессами. — JI.: ЛГУ, 1973. 296 с.

163. Итеративные методы в теории и программировании / В.З. Беленький,

164. B.А. Волконский, С.А. Иваников и др. — М.: Наука, 1974.

165. Каган Б.М., Мкртумян И.Б. Основы эксплуатации ЭВМ, — М.: Энер-гоатомиздат, 1983. — 376 с.

166. Каляев A.B. Параллельный компьютер с программируемой под структуру задачи архитектурой // Труды Шестого Мео/сдународного семинара «Распределённая обработка информации». — 1998.— С. 25-29.

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

168. Каляев A.B., Левин И.И. Модулыю-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений.— М.: Янус-К, 2003.- 380 с.

169. Кластер НКС-ЗОТ. 2012,- URL: http://www2.sscc.ru/HKC-30T/ HKC-30T.htm (дата обращения: 08.02.2012).

170. Клейнрок Л. Вычислительные системы с очередями. — М.: Мир, 1979. — 600 с.

171. Колесник Г.В. Теория игр. — 2-е, исп. и доп. изд. — М.: Книжный дом «ЛИБРОКОМ», 2010.- 152 с.

172. Конвей Р.В., В.Л. Максвелл В.Л., Миллер Л.В. Теория расписаний. — М.: Наука, 1975.- 360 с.

173. Корбут A.A., Сигал И.Х., Фиикельштейн Ю.Ю. Методы ветвей и границ. Обзор теорий, алгоритмов, программ и приложений // Operations Forsch. Statist., Ser. Optimiz. Т. 8. - 1977. - С. 253-280.

174. Корбут A.A., Сигал И.Х., Финкелъштейн Ю.Ю. Гибридные методы в дискретном программировании // Изв. АН СССР. Техн.кибернет. — 1988,- С. 65-77.

175. Корбут A.A., Финкелъштейн Ю.Ю. Приближенные методы дискретного программирования // Изв. АН СССР. Техн. кибернет. — 1983. — С. 165-176.

176. Корнеев В.В. О подключении внешних устройств к однородным вычислительным системам // Вычислительные системы. — 1975. — С. 103-108.

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

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

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

180. Корнеев В.Д. Параллельное программирование в MPI. — Новосибирск: Изд-во ИВМиМГ : СО РАН, 2002. 215 с.

181. Корнеев В.В. и др. Об организации коммуникаций между процессами в вычислительной системе МИКРОС /7 Вычислительные системы. — 1985. С. 70-84.

182. Корнеев В. В. и др. Операционная система микромашиной вычислительной системы с программируемой структурой МИКРОС // Микропроцессорные средства и системы. — 1988. — № 4. — С. 41-44.

183. Корнеев В.В., Монахов О.Г. Графы межмашинных связей однородных вычислительных систем // Вычислительные системы. — 1979. — С. 3-17.

184. Корнеев В.В., Монахов О.Г. Организация межмашинных взаимодействий в вычислительных системах с программируемой структурой / / Электронное моделирование. — 1980. — № 5. — С. 16-22.

185. Корнеев В.В., Хорошевский В.Г. Вычислительные системы с программируемой структурой // Электронное моделирование. — 1979. — № 1. — С. 42-53.

186. Корнеев В.В., Хорошевский В.Г. Структура и функциональная организация вычислительных систем с программируемой структурой. Препринт. — Новосибирск: 1, 1979. — 47 с.

187. Королев Л.Н. Микропроцессоры, микро- и мини-ЭВМ: уч. пособ. для ВУЗов. М.: МГУ, 1988. - 211 с.

188. Косарев Ю.Г. Распараллеливание по циклам // Вычислительные системы. 1967. - С. 3-20.

189. Костевич Л.С., Лапко A.A. Теория игр. Исследование операций: Уч. пос. для эк. спец. ВУЗов. — Минск: Вышэйшая школа, 1982. — 231 с.

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

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

192. Лазарев В.Г. Распределённые управляющие и вычислительные системы: сб. ст. — Киев: Наукова думка, 1987. — 167 с.

193. Лазарев A.A., Гафаров Е.Р. Теория расписаний. Задачи и алгоритмы. — М.: МГУ им. A.B. Ломоносова, 2011. 256 с.

194. Ларионов A.M., Майоров С.А., Новиков Г.И. Вычислительные комплексы, системы и сети: учебник для ВУЗов по спец. "ЭВМ". — Л.: Энерго-атомиздат, 1987. — 288 с.

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

196. Лебедев С.А. Быстродействующие универсальные вычислительные машины. — М.: Наука, 1956. — 15 с.

197. Левик В. К. Некоторые вопросы реализации высокопроизводительных вычислительных систем // Кибернетика и вычислительная техника. — 1991. — № 5.- С. 27-35.

198. Левин В.К. Современные суперкомпьютеры семейства МВС. — URL: http://www.parallei.ru/mvs/levin.html.

199. Липаев B.B. Распределение ресурсов в вычислительных системах. — М.: Статистика, 1979. — 242 с.

200. МСЦ РАН Суперкомпьютер "МВС-ЮОК". - 2012. - URL: http: //www. jscc.ru/hard/mvslOOk.shtml (дата обращения: 08.02.2012).

201. Майоров С.А., Новиков Г.И., Алиев Т.И. Основы теории вычислительных систем, — М.: Высшая школа, 1978.

202. Мак-Кинси Дою. Введение в теорию игр / пер. с англ.— М.: ГИФЛ, 1960. 420 с.

203. Малышкин В.Э., Корнеев В.Д. Параллельное программирование муль-тикомпыотеров. — Новосибирск: НГТУ, 2006. — 296 с.

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

205. Мамойленко С.Н. Кластерные вычислительные системы // Материалы Международной научно-технической конференции «Информатика и проблемы телекоммуникаций». — Новосибирск: 2001. — С. 88-90.

206. Мамойленко С.Н. Многоходовая игровая модель функционирования вычислительных систем // Материалы Международной научно-технической конференции «Информатика и проблемы телекоммуникаций». — Новосибирск: 2002. С. 132-133.

207. Мамойленко С.Н. Непрерывная теоретико-игровая модель функционирования распределенных вычислительных систем /'/' Материалы Международной научно-технической конференции «Информатика и проблемы телекоммуникаций». — Новосибирск: 2003. — С. 151-152.

208. Мамойленко С.Н. Теоретико-игровая модель функционирования распределенной очереди задач в кластерных вычислительных системах //' Материалы Всероссийской научной конференции «Наука. Технологии. Инновации.». — Т. 2. — Новосибирск: 2003. — С. 18-19.

209. Мам.ойленко С.Н. Опыт преподавания курсов по операционным системам // Тезисы докладов XLIX научно-методической конференции "Проблемы перехода на многоуровневую систему образования". — Новосибирск: Изд-во СибГУТИ, 2008.

210. Мамойленко С.Н. Microsoft IT Academy инновационная программа для ВУЗов // Сборник тезисов докладов 50-й (L) научно-методической конференции ГОУ ВПО «СибГУТИ». - Новосибирск: ГОУ ВПО «СибГУТИ», 6 февраля 2009 года. - С. 14.

211. Мануэль Т. Новые модели суперкомпьютеров // Электроника. — 1989. — № 11,- С. 13-14.

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

213. Марчук Г.И. Введение в методы вычислительной математики. Курс лекций. — Новосибирск, 1971. — 233 с.

214. Масштабируемый инструментарий параллельного мультипрограммирования пространственно-распределенных вычислительных систем / В.Г. Хорошевский, М.Г. Курносов, С.Н. Мамойленко и др. // Вестник ГОУ ВПО «СибГУТИ». 2011. - № 1. - С. 3-18.

215. Мельников В.А., Митропольский Ю.И. Комплексное проектирование элементно-конструкторской базы суперЭВМ. — 1988.— 128 с.

216. Миллер Р., Боксер JI. Последовательные и параллельные алгоритмы: Общий подход. — М.: БИНОМ. Лаборатория знаний, 2006. — 406 с.

217. Миренков H.H. Параллельное программирование для многомодульных вычислительных систем. — М.: Радио и связь, 1986. — 319 с.

218. Миренков H.H., Симонов С.А. Выявление параллелизма в циклах методом имитационного их выполнения // Кибернетика. — 1981.— № 3.— С. 28-33.

219. Многофункциональные регулярные вычислительные структуры / Е.П. Балашев, В.Б. Смолов, Г.А. Петров, Д.В. Пузанков. — М.: Советское радио, 1978. — 288 с.

220. Монахов О.Г. Параметрическое описание структур однородных вычислительных систем // Вычислительные системы. Вопросы теории и построения вычислительных систем. — 1979. — С. 3-17.

221. Монахов О. Г. Оптимизация распределения управления ресурсами в вычислительных системах с программируемой структурой // Автоматика и вычислит,ел,ьная, техника,. — 1984. — № 3. — С. 9-17.

222. Монахов О.Г., Монахова Э.А. Организация межмашинных взаимодействий в вычислительных системах с программируемой структурой МИК-РОС // Вычислительные системы. — 1984. — № 105. — С. 85-104.

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

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

225. Монахова Э.А. Синтез оптимальных дофантовых структур /'/ Вычислительные системы. — 1979. — С. 18-35.

226. Москвитин A.A., Мамойленко С.Н. Контроль знаний студентов и тестирование // Сборник тезисов докладов 50-й (L) научно-методической конференции ГОУ ВПО «СибГУТИ». Новосибирск: ГОУ ВПО «СибГУТИ», 6 февраля 2009 года. - С. 38.

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

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

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

230. Об организации функционирования кластерных вычислительных систем / Хорошевский В.Г., С.Н. Мамойленко, Ю.С. Майданов, C.B. Смирнов // Автометрия. 2004. - Т. 40, № 1. - С. 41-50.

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

232. Оуэн Г. Теория игр: Пер. с англ. М.: Мир, 1971. - 231 с.

233. Оуэн Гилъермо. Теория игр: Пер. с англ. / Под ред. A.A. Корбута. — 5-е изд. М.: Издательство ЛКИ, 2010. - 216 с.

234. Павский В.А., Иванова С.А. Расчет показателей живучести распределенных вычислительных систем // Инновационные недра Кузбасса. IT-технологии: сб. науч. тр. — Кемерово: ИНТ, 2007. — С. 334-338.

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

236. Павский В.А., Хорошевский В.Г. Вычисление показателей надежности вычислительных систем // Материалы 7 Межд. научно-техн. конф. «Искусственный интеллект. Интеллектуальные и многопроцессорные системы». Таганрог: Изд-во ТРТУ, 2006. - С. 17-11.

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

238. Партхасаратхи Т., Рагхаваи Т. Некоторые вопросы теории игр двух лиц. — М.: Изд-во Мир, 1974. — 295 с.

239. Полищук Л.И. Анализ многокритериальных экономико-математических моделей. — Новосибирск: Наука, Сиб. отд-ние, 1989. — 352 с.

240. Поспелов Д.А. Введение в теорию вычислительных систем. — М.: Советское радио, 1972. — 280 с.

241. Прангишвили И.В., Виленкин С.Я., Медведев И.Л. Параллельные вычислительные системы с общим управлением, — М.: Энергопромиздат, 1983.- 313 с.

242. Прангишвили И.В., Резанов В.В. Многопроцессорные управляющие вычислительные комплексы с перестраиваемой структурой.— М.: АН СССР, Институт точной механики и вычислительной техники, № 10, 1977.

243. Пузанков Д.В. Микропроцессорные системы.— СПб.: Политехника, 2002.- 935 с.

244. Пухов Г.Е., Евдокимов В.Ф., М.В. Синъков. Разрядно-аналоговые вычислительные системы. — М.: Советское радио, 1978. — 255 с.

245. Пятибратов А.П., Гудыно Л.П., Кириченко A.A. Вычислительные системы, сети и телекоммуникации: Учебник. — 2-е изд. изд. — М.: Финансы и статистика, 2001. — 512 с.

246. Распределенная кластерная вычислительная система / Хорошевский В.Г., Ю.С. Майданов, С.Н. Мамойленко, М.С. Седельников // Материалы Компьютерные и информационные технологии в науке, инженерии и управлении. — Таганрог: ТРТУ, 2004.

247. Рекурсивная машина и вычислительная техника /' В.М. Глушков, М.В. Игнатьев, В.А. В.А. Мясников, В.А. Торгашев,— Киев: Препринт АН УССР Институт кибернетики, 74-75, 1974. — 120 с.

248. Робинсон Дою. Итеративный метод решения игр // Матричные игры. — 1964,- С. 110-117.

249. Рябов Г.Г., Чупаев B.C. и др. Выбор интегральных схем узлов ЭВМ для интегрального исполнения. — М.: Наука, 1969. — 83 с.

250. Самарский A.A. Языки и параллельные ЭВМ: сб. ст.— М.: Наука, 1990.- 91 с.

251. Севастьянов C.B. Геометрические методы и эффективные алгоритмы в теории расписаний: Дис. на соиск. уч. ст. д.ф.-м.н. /' -. — Новосибирск, 2000. 280 с.

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

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

254. Смолов В.В., Фомичев B.C. Аналогово-цифровые и цифро-аналоговые нелинейные устройства. — JI.: Энергия, 1974. — 264 с.

255. Киреев С.Е., Гоничев M.А., Калгин К.В., Перепёлкин В.А. Совместное использование MPI и ОрепМР на кластерах. — URL: http://www2. s see.ru/S0RAN-INTEL/paper/2010/MPI0penMP100325.pdf (дата обращения: 08.02.2012).

256. Сысоев В.В., Сербулов Ю.С., Сипко В.В. Теоретико-игровые модели принятия решений многоцелевого управления в задачах выбора и распределения ресурсов. — Воронеж: ВГТА, 2000. — 60 с.

257. Танаев B.C., Гордон B.C., Шафраиский Я.М. Теория расписаний. Одностадийные системы. — М.: Наука. Гл. ред. физ.-мат. лит., 1984. — 384 с.

258. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. — М.: Наука. Гл. ред. физ.-мат. лит., 1989. — 328 с.

259. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. — М.: Наука, 1975.-- с.

260. Танаев B.C. Ковалев М.Я. Шафраиский Я.М. Теория расписаний. Групповые технологии. — Минск: Институт технической кибернетики HAH Беларуси, 1998. 290 с.

261. Таненбаум Э., Ван Стеен М. Распределенные системы: принципы и парадигмы. — СПб.: Питер, 2003. — 877 с.

262. Теория расписаний и вычислительные машины / Дж. JI. Бруно, Р.Л. Грэхем, В.Г. Коглер и др.; Под ред. пер. с англ. В.М. Амочкина Б.А. Головкина. — М.: Наука, 1984. — 336 с.

263. Томилин А.Н. Применение метода математичесжиого моделирования к выбору структурной схемы машины БЭСМ-6 и разработки программыдиспетчера машины БЭСМ-6: Автореф. дис. на соиск. уч. ст. к.ф.-м.н. /

264. Управление параллельными заданиями в гриде с неотчуждаемыми ресурсами / В.Н. Коваленко, Е.И. Коваленко, Д.А. Корягин, Д.А. Семяч-кин. Москва: ИПМ РАН, 2007. - С. 1-28. - Препринт № 63.

265. Фернбах С. Супер ЭВМ. Аппаратная и программная реализация: пер. с англ. — М.: Радио и связь, 1991. — 320 с.

266. Фурсиков A.B. Оптимальное управление распределенными системами. Теория и приложения. — Новосибирск, 1999. — 40 с.

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

268. Хокни Р., Дэ/сессоуп К. Параллельные ВС. Архитектура, программирование и алгоритмы. — М.: Радио и связь, 1986. — 392 с.

269. Хорошевский В.Г. Об алгоритмах распределения задач по ЭЦВМ // Труды СФТИ. Вып. 47. Томск: изд. ТГУ, 1965. - С. 29-34.

270. Хорошевский В.Г. Об алгоритмах функционирования однородных вычислительных систем // Вычислительные системы, — 1970.— С. 3-25.

271. Хорошевский В.Г. Исследование функционирования однородных вычислительных систем: Автореферат дис. на соиск. уч. ст. д.т.н. / -.— Л., 1973.- 32 с.

272. Хорошевский В. Г. Состояние и перспективы работ в области вычислительных систем с программируемой структурой // ЭВМ. Перспективы и гипотезы. — 1981. — № 46. — С. 90.

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

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

275. Хорошевский В.Г., Власюк В.В. Теоретико-игровой подход к организации стохастически оптимального функционирования распределенных вычислительных систем // Автометрия. — 2000. — № 3. — С. 17-25.

276. Хорошевский В.Г., Мамойленко С.Н. Стратегии стохастически оптимального функционирования распределенных вычислительных систем // Автометрия. — 2003. — № 2. — С. 81-91.

277. Хорошевский В.Г., Мамойленко С.Н., Курносое М.Г. О центре параллельных вычислительных технологий ГОУ ВПО «СибГУТИ» // Инфосфера. 2008. — № 40. — С. 43-44.

278. Хорошевский В.Г., Талныкин Э.А. Теоретико-игровой подход к проблеме функционирования однородных вычислительных систем //' Вычислительные сист,емы. — 1972. — С. 20-37.

279. Хорошевский В.Г., Усенко О.И. Об одном подходе к оптимизации функционирования распределенных вычислительных систем // Автоматика и вычислительная техника. — 1989. — № 2. — С. 40-46.

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

281. Черномаров Т.А., Ковалевский Ю.Е. Теоретико игровые модели взаимодействия экономических субъектов производственной системы. — М.: ВЦ РАН, 1994.- 48 с.

282. Четверушкин Б.Н. Математическое моделирование задач динамики излучающего газа. — М.: Наука, 1985. — 304 с.

283. Шаповалов Т.С. Пересветов В.В. Генетический алгоритм составления расписаний для распределенных гетерогенных вычислительныхсистем // Вычислительные методы и программирование. — 2009. — Т. 10. С. 159-167.

284. Шокин Ю.И. Численные методы газовой динамики и инвариантные разностные схемы. — Новосибирск, 1977. — 84 с.

285. Элементы параллельного программирования / В.А. Вальковский, В.Е. Котов, А.Г. Марчук, H.H. Миренков; Под ред. В.Е. Котов, — М.: Радио и связь, 1983. — 240 с.

286. Эпдрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования./пер. с англ. — М.: Вильяме, 2003. — 512 с.

287. Энслоу Ф. пер. с англ. Мультипроцессорные системы и параллельные вычисления. — М.: Мир, 1976. — 326 с.

288. Яненко H.H., Хорошевский В.Г., Рычков А. Д. Параллельные вычисления в задачах математической физики на вычислительных системах с программируемой структурой // Электронное моделирование. — 1984.-Т. 6, № 1,- С. 3-8.