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

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

УДК 681.32

Седельников Максим Сергеевич

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

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

Новосибирск - 2006

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

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

доктор технических наук профессор

член-корреспондент РАН Хорошевский Виктор Гаврилович

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

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

Береснев Владимир Леонидович

кандидат технических наук доцент

Пискунов Сергей Владиславович

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

Институт автоматики и электрометрии Сибирского отделения Российской Академии Наук г. Новосибирск

Защита состоится ьМ&Яя**- 2006 г. В <»/У» часов на заседании

Диссертационного совета Д219.005.02 при ГОУ ВПО «Сибирский государственный университет телекоммуникаций и информатики», по адресу: 630102, г. Новосибирск, ул. Кирова, д. 86, ком. 625.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «СибГУТИ».

Автореферат разослан » ^е&р^Л. 2006 г. Ученый секретарь

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

кандидат технических наук ,

доцент И.И.Резван

XQöGIS

Общая характеристика работы

Актуальность проблемы. Возрастающая потребность в решении сложных задач науки, техники и экономики привела к созданию распределенных вычислительных систем (ВС). В общем случае ВС есть композиция элементарных машин (ЭМ) и сети межмашинных связей, способная осуществлять параллельную обработку информации. Все основные ресурсы распределенных ВС (арифметико-логические устройства, память и средства управления) являются логически и технически рассредоточенными. Число ЭМ в распределённых ВС допускает варьирование от нескольких единиц до сотен тысяч (например, в МВС-15000ВМ это число равно 924, а в создаваемой системе IBM Blue Gene планируется до 1 ООО ООО). Наиболее распространенный режим функционирования ВС - монопрограммный, в нем все ресурсы используются для решения одной сложной задачи. Данный режим не всегда позволяет полностью использовать вычислительные возможности ВС, в силу различия требований задач к ресурсам. Мультипрограммный режим, предполагающий одновременное решение на системе нескольких параллельных задач, позволяет существенно повысить эффективность использования распределенных ВС.

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

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

A.B. Забродин, В.Л. Иванников, М.Б. Игнатьев, A.B. Каляев, Л.Н. Королев,

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

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

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

тальные работы по оптимальному управлению и исследованию операций советских и российских ученых: В.Л.Береснева, Э.Х.Гимади, В.Т.Дементьева, Ю.И. Журавлева, К.В. Рудакова и зарубежных - R. Bellmann, D. Johnson, М. Koffman, Н. Taha и других.

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

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

К основным задачам исследований относятся:

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

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

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

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

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

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

2. Алгоритмы обработки набора задач, позволяющие распределять параллельные задачи с нефиксированными параметрами.

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

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

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

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

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

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

Реализация и внедрение результатов работы. Основные результаты диссертационной работы получены в рамках проекта № 3.2 «Разработка методов анализа и алгоритмов организации функционирования болыиемасштабных распределенных вычислительных систем и создание аппаратно-программного инструментария параллельного моделирования» федеральной целевой программы № 21 фундаментальных исследований Президиума РАН. Диссертационная работа поддержана грантами Российского фонда фундаментальных исследований (РФФИ) № 02-07-90379, 02-07-09380, 05-07-08011, 05-07-90009. Полученные результаты внедрены в распределенную мультикластерную ВС Центра параллельных вычислительных технологий и применены в учебном процессе на Кафедре вычислительных систем СибГУТИ.

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

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

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

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

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

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

-International scientific conference «Automation, Control, and Information Technology - Software Engineering» (2005 г., г. Новосибирск);

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

Публикации. По теме диссертации опубликовано 12 работ, включая 3 статьи в центральных изданиях.

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

Основное содержание работы

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

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

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

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

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

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

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

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

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

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

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

На сегодняшний день в нашей стране и за рубежом проводится ряд работ, направленных на создание программных средств организации функционирования распределенных ВС. Данные средства могут быть также использованы и для организации мультипрограммных режимов. Процесс управления вычислительными ресурсами, в общем случае, осуществляется программами-диспетчерами, которые могут быть централизованными (система МВС, Condor, PBS) и децентрализованными (МИКРОС, Globus Toolkit). В распределенных ВС целесообразно использование децентрализованных методов управления, следовательно, имеется потребность в разработке децентрализованных алгоритмов организации функционирования и создании соответст-

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

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

Пусть имеются множество 7 = {7,,одинаковых элементарных машин, образующих распределенную ВС, и множество 1 = {/,,/2,...,/д} независимых задач. Задача /, е / характеризуется, в общем случае, нефиксированным рангом г~ < г, < г* , (числом параллельных ветвей в ее программе), временем решения tl =tl(r|) и с1 > 0 - штрафом в единицу времени за задержку решения, / = 1, Ь . Другими словами, для решения задачи /, е / требуется число машин г,, которое не меньше г~ и не больше г* , и единиц времени, а за задержку решения /, на единицу времени накладывается штраф в размере с1 денежных единиц. В большинстве случаев при увеличении числа параллельных ветвей в программе, время ее выполнения уменьшается, поэтому справедливо предположить, что ) - невозрастающая функция. Требуется построить алгоритмы распределения задач по ЭМ системы, которые бы обеспечивали минимумы целевых функций, характеризующих эффективность решения задач набора на ВС. В качестве таких функций используется либо время решения задач набора, либо штраф за задержку решения набора.

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

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

Каждая задача /, е /, ¿ = 1,Ь , представлена в виде множества параллельных ветвей

А=1

Примем следующие обозначения:

- время начала решения задачи /,, / = !,£;

^ - ЭМ, выделенная для решения ветви /* задачи /, (если Jk - 0 , то для данной ветви ЭМ не выделена), к = 1, г* , 1 = 1,1;

г - ранг распределяемых задач, / = 1 ,Ь . Необходимо найти вектор

т _ (} ; г г /1 /1+ /"' Тгг /1 7Г7 \

минимизирующий либо

Г(г) = тах(/, + tl (гг)) -> тт

1=1,£ г

при оптимизации времени решения набора, либо

I

при оптимизации штрафа за задержку решения набора.

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

(1) V г* _/, = 1 ,Ь верно, по крайней мере, одно из следующих двух условий:

а) рД+/Дг,))прД+*,(/-, )) = 0;

б) vkl=йт, А2 = й;, ,^ *о)=>(^

(2) = УА, ^к2, кик2 =1^, ^0) =>(./'<

_ ^

(3) У/ = и, =

(4) у/ = й, г-<г,<г;,

(5) = * = У* € У и {0};

(6) >о, г, ек.

Ограничения (1) запрещают одновременное решение двух и более задач на одной ЭМ, (2) - обеспечивают реализацию разных ветвей каждой задачи на разных машинах, (3) и (4) обеспечивают решение задачи на необходимом количестве ЭМ, (5) и (6) - задают область значений переменных.

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

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

различным временем решения преобразуется во множество укрупненных задач также разных рангов, но с одинаковым (заранее заданным) временем решения 0 . Другими словами, множество всех задач ранга г, 1 < г < п, разбивается на подмножества (укрупненные задачи), в каждое из которых входят задачи, суммарное время решения которых близко к ©. Во второй части алгоритма множество всех укрупненных задач также разбивается на подмножества так, что суммарный ранг всех укрупненных задач в каждом подмножестве максимально близок к п - числу машин в ВС.

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

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

Из рис. 1 видно, что предложенный алгоритм Т_РАСК распределяет набор задач эффективнее известного алгоритма Т_МС на 20-30%. Время работы алгоритма Т РАСК меньше времени работы алгоритмы Т МС в 1,5-7,5 раз в зависимости от числа задач в наборе. Преимущество предложенного алгоритма Р РАСК минимизации штрафа за задержку решения набора задач перед известным Р_МС, составляет, в ряде случаев, 6-кратное уменьшение функции штрафа.

Число задач в наборе

Рис. 1. Эффективность алгоритма Т_РАСК по сравнению с Т_МС

РАСК-Ш-Т_МС

Для распределения больших наборов (более 106 задач) по ЭМ разработаны параллельные версии обоих алгоритмов. Распараллеливание применяется при формировании пакетов задач для различных рангов и при определении их оптимальной последовательности решения. Предложенный параллельный алгоритм сортировки позволяет уменьшить время распределения задач по пакетам.

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

^Т_раск = 2а2 ^^ ^'

0

где <7 =-, 1 < а < +оо - относительный размер укрупненной задачи.

шах/ i=i,i

Следует отметить, что при выборе достаточно большого параметра 0 трудоемкость алгоритмов в пределе составит половину квадрата числа задач в наборе.

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

2 а п п

где toS - эквивалентное время передачи одного сообщения между двумя соседними ЭМ (отношение максимального времени передачи единицы данных к максимуму времени выполнения одной арифметико-логической операции

на ЭМ), S = — maxar, 0 < <5 < 1 - максимум доли задач одинакового ранга в L г

наборе (аг - число задач ранга г в наборе).

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

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

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

невозрастающей функцией от ранга и имеет вид

г,

где si > 0, s, € К, i = 1, L - зависимые от задач коэффициенты. Распределение задач по системе осуществляется алгоритмом, варьирующим ранг задач согласно выделяемым вычислительным ресурсам. В общем случае задача решается на максимально возможном количестве ЭМ. Последовательность решения определяется следующим образом:

- при минимизации времени решения набора задачи упорядочиваются по убыванию величин

/( (г*), i = \L - минимальное время решения задач;

- при минимизации штрафа за задержку решения набора задачи сортируются по возрастанию

i(r+) —

-—'■—, i-\,L - величины, обратные удельному штрафу.

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

г Т~Т'

о = -

Т' '

где Т — нижняя оценка времени решения набора, Т - время решения набора, полученное предложенным алгоритмом.

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

Из результатов следует, что предложенный алгоритм "ГОРАСК более эффективен для распределения задач с небольшим рангом (25% и менее от числа ЭМ), либо рангом близким к числу машин в ВС (значение 100%).

Отношение среднего ранга задач набора к числу машин ВС

Рис. 2. Эффективность алгоритма ТЕ)_РАСК.

Число машин ВС -в-8-32-^-256

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

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

Решение о включении соседних машин в создаваемую подсистему основано на критерии

К = К(Т,,Тк,г,А), где Т! - загрузка ЭМ Js, Тк - загрузка ЭМ Jk, инициирующей создание подсистемы, г - требуемый ранг подсистемы (число ЭМ), А - параметр (допустимое отклонение от загрузки ЭМ Jk). В общем случае критерий К

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

Формируемая таким образом подсистема, является, по крайней мере, односвязанной и создается параллельно различными ЭМ.

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

т%мс = *овО(п) + 0(пт 1п т), где п - ранг создаваемой подсистемы, т - максимум числа соседей каждой ЭМ, /о5 - эквивалентное время передачи единицы информации между соседними машинами.

В работе доказано, что в случае наличия в ВС п ЭМ, удовлетворяющих критерию К, и сети связей, представленной -мерной евклидовой решёткой, нижней оценкой трудоемкости алгоритма 8_ПЕС является

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

Работа алгоритма включает две фазы:

- рассылка запросов и начальное формирование подсистемы;

- рассылка подтверждений, фиксация созданной подсистемы.

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

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

1) в расписании текущей ЭМ определяется минимально возможное время запуска очередной задачи;

2) предложенным алгоритмом создается подсистема необходимого ранга с учетом определенного в п. 1 времени запуска;

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

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

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

В четвертой главе описана архитектура и программное обеспечение распределенной мультикластерной ВС, эксплуатируемой Центром параллельных вычислительных технологий Сибирского государственного университета телекоммуникаций и информатики (ЦПВТ СибГУТИ).

Система объединяет 7 сосредоточенных кластеров, часть из которых расположена в ЦПВТ СибГУТИ, часть - в Институте физики полупроводников (ИФП) СО РАН.

Большая часть кластеров системы представляют стандартные персональные компьютеры на базе процессоров Intel, объединенные с помощью сетевой технологии Fast Ethernet. Один из кластеров состоит из четырех узлов, имеющих архитектуру NUMA и включающих по два процессора AMD Opteron 248. Для их объединения используется сетевая технология Gigabit Ethernet.

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

Программное обеспечение распределенной вычислительной системы основано на ОС Linux (дистрибутив ASP Linux 9.2, ядро 2.4.22). Разработка и выполнение параллельных программ осуществляется с помощью технологии MPI (реализация LAM 7.0.4). Для сетевых взаимодействий используются протоколы стека TCP/IP. Удаленный доступ к системе выполняется по протоколу виртуального терминала ssh.

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

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

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

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

о £

L- I Os а IÛ. i

IP I Ш ь- § S' S Е -г-' X -о >

" CS ® §

И 2 81 8 « я о

В ~ о Е ф

а:

«О

>* s

и

О О et

ПРИЛОЖЕНИЯ

ДИСПЕТЧЕР РАСПРЕДЕЛЕННОЙ ОЧЕРЕДИ

ДИСПЕТЧЕР РЕСУРСОВ

Distributed Systems Manager (DSM vi .0)

СРЕДСТВА САМОДИАГНОСТИКИ

ПАР.

СррощАмм-"

¡íqSÁTEffcrtstX ПР0ГВАЙМ".

ПС

ОПЕРАЦИОННАИСИрТЕМА, С^ТЕВЬЕ ПРОТОШЛЫ

СТАНДАРТНЫЕ КОМПОНЕНТЫ

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

Рис. 3. Структура программного обеспечения распределенной мультикластерной ВС

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

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

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

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

Основные результаты работы

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные результаты диссертации опубликованы в работах [1-11].

Список публикаций

1. Хорошевский В.Г., Седельников М.С. Эвристические алгоритмы распределения набора задач по машинам вычислительной системы // Автометрия. - 2004 - Т. 40. - № 4. - С. 76-87.

2. Седельников М.С. О некоторых эвристических алгоритмах распределения задач по машинам вычислительной системы // Материалы Международной научно-технической конференции «Информационные системы и технологии - 2003». - Т. 2. - С. 25-27.

3. Седельников М.С. Параллельный алгоритм сортировки // Материалы Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы - 2003». - Т. 2. - С. 107-109.

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

5. Седельников М.С. Точный алгоритм распределения набора задач по машинам вычислительной системы // Материалы Всероссийской научной конференции молодых ученых «Наука. Техника. Инновации. - 2004». - Ч. 2. - С. 65-66.

6. Мамойленко С.Н., Седельников М.С. Распределенная кластерная вычислительная система как средство подготовки специалистов в области параллельных вычислительных технологий // Проблемы качества образования : сб. научных трудов ХЪУ1 Научно-методической конференции. -Новосибирск: Изд-во Сиб. гос. ун-та телеком, и информат. 2005. - С. 64-66.

7. Седельников М.С. Распределенный диспетчер удаленного запуска параллельных программ на кластерной вычислительной системе // Материалы Российской научно-технической конференции «Информатика и проблемы телекоммуникаций - 2005». - T. 1.-С. 217-218.

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

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

10. 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 2005». - P. 136-138.

11. Khoroshevsky V.G., Sedelnikov M.S. Heuristic algorithms for tasks distribution between computer systems machines // Optoelectronics, instrumentation and data processing. - 2004. - Vol. 40. - № 4. - P. 66-75.

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

Максим Сергеевич Седельников

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

режимах

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

Подписано в печать 01. 02. 2006, формат бумаги 60x84/16, отпечатано на ризографе, шрифт №10, изд. л. 1,6 , заказ № 12 , тираж 140. СибГУТИ 630102, Новосибирск, ул. Кирова, 86

%о осд

»"2 848

/

СПИСОК СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

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

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

1.1.1. Модель коллектива вычислителей

1.1.2. Классификация ВС.

1.1.3. Особенности ВС с программируемой структурой.

1.2. Основные режимы функционирования ВС

1.2.1. Монопрограммный режим

1.2.2. Мультипрограммные режимы

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

1.3.1. Алгоритмы организации функционирования ВС

1.3.2. Обзор средств поддержки мультипрограммных режимов.

1.4. Выводы.

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

2.1. Оптимизация загрузки ВС при обработке задач набора.

2.2. Точный алгоритм распределения задач набора по элементарным машинам ВС

2.3. Эвристические алгоритмы распределения задач набора с фиксированными параметрами

2.3.1. Формирование пакетов задач

2.3.2. Минимизация времени решения задач набора на ВС.

2.3.3. Параллельный алгоритм минимизации времени решения задач набора на ВС

2.3.4. Минимизация штрафа за задержку решения задач набора на ВС.

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

2.4. Эвристические алгоритмы распределения набора задач с нефиксированными параметрами

2.4.1. Минимизация времени решения задач набора на ВС.

2.4.2. Минимизация штрафа за задержку решения задач набора на ВС.

2.5. Выводы.

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

3.1. Создание многопроцессорного расписания для потока параллельных задач

3.2. Децентрализованный алгоритм организации подсистем в ВС.

3.3. Децентрализованный алгоритм создания многопроцессорного расписания

3.4. Механизмы обеспечения отказоустойчивости при формировании подсистем в ВС.

3.6. Выводы.

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

4.1. Архитектура мультикластерной ВС Центра Параллельных Вычислительных Технологий СибГУТИ

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

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

4.4. Моделирование алгоритмов организации подсистем и создания многопроцессорного расписания

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

4.5.1. Состав программного обеспечения. Стандартные компоненты

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

4.6. Выводы.

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

- параллельность выполнения операций;

- программируемость структуры;

- конструктивная однородность.

Одним из типов архитектур вычислительных систем являются распределённые ВС. Все основные ресурсы таких систем (арифметико-логические устройства, память и средства управления) являются логически и технически рассредоточенными. Число ЭМ в распределённых ВС допускает варьирование от нескольких единиц до сотен тысяч и более (например, в МВС-15000ВМ это число равно 924, а в создаваемой системе IBM Blue Gene планируется до 1 ООО ООО).

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

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

Фундаментальный вклад в теорию и практику вычислительных систем и параллельных вычислительных технологий внесли советские и российские учёные, среди которых: Е.П.Балашов [2,3], В.Б. Бетелин [1], B.C. Бурцев [8,9], В.В. Васильев [10], В.В. Воеводин [12], В.М. Глушков [15,16], В.Ф. Евдокимов [25], Э.В.Евреинов [26-29],

A.В. Забродин [32], В.П. Иванников [34], М.Б. Игнатьев [16,35], А.В. Каляев [36,37], Л.Н. Королев [51],

B.Г.Лазарев [54], С.А.Лебедев [56], В.К. Левин [57], Г.И.Марчук[65] , Ю.И.Митропольский[66], С.В.Пискунов[78-80], Д.А. Поспелов [81], И.В. Прангишвили [82, 83], Д.В. Пузанков [3,11], Г.Е. Пухов [84], Г.Г. Рябов [86], А.А. Самарский [133], В.Б. Смолов [3,96], А.Н. Томилин [105], Я.А. Хетагуров [110], В.Г. Хорошевский [23,29, 30,49,50,113-125,134], Б.Н.Четверушкин [128], Ю.И.Шокин [129], Н.Н. Яненко [134], а также зарубежные учёные:

S. Cray [138], M. Flynn [138], I. Foster [135], D. Hillis [144], C. Kesselman [141], DL.Slotnick [155],

A. Tanenbaum [100,101] и другие. При решении проблем оптимизации функционирования распределенных ВС большую роль сыграли фундаментальные работы по оптимальному управлению и исследованию операций советских и российских ученых: B.J1. Береснева [6], Э.Х. Гимади [14],

B.Т.Дементьева [21], Ю.И. Журавлева [31], К.В. Рудакова [85] и зарубежных - R. Bellmann [136], D. Johnson [145], Н. Taha [103] и других.

Возможности ВС могут быть полностью использованы только при применении эффективных методов и средств организации процессов решения задач [5,18,54,55,58] и, в частности, мультипрограммных режимов [116] . Под эффективностью методов понимается не только то, что методы способны получить решение с необходимой точностью, но и то, что реализация этих методов на ВС позволяет выполнить это за достаточно короткое время.

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

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

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

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

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

К основным задачам исследований относятся:

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

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

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

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

Научная новизна. Автором получены нижеследующие научные результаты, которые выносятся на защиту.

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

2. Алгоритмы обработки набора задач, позволяющие распределять параллельные задачи с нефиксированными параметрами .

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

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

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

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

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

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

Реализация и внедрение. Основные результаты диссертационной работы получены в рамках проекта № 3.2 «Разработка методов анализа и алгоритмов организации функционирования большемасштабных распределенных вычислительных систем и создание аппаратно-программного инструментария параллельного моделирования» федеральной целевой программы № 21 фундаментальных исследований Президиума РАН. Диссертационная работа поддержана грантами Российского фонда фундаментальных исследований (РФФИ) № 02-07-90379, 02-07-09380, 05-07-08011, 05-07-90009. Полученные результаты внедрены в распределенную мультик-ластерную ВС Центра параллельных вычислительных технологий СибГУТИ и использовались при разработке и чтении учебных курсов на Кафедре вычислительных систем СибГУТИ по дисциплинам «Теория функционирования распределенных вычислительных систем», «Высокопроизводительные вычислительные системы» и «Сетевое программное обеспечение».

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

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

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

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

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

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

- International scientific conference «Automation, Control and Information Technology - Software Engineering» (2005 г., г. Новосибирск);

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

Публикации. По теме диссертации опубликовано 12 работ, включая 3 статьи в центральных изданиях.

Объем и структура диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы, изложенных на 14 3 страницах, а также приложений на 7 страницах.

Основные результаты диссертации опубликованы в работах [63,89-93,121,123,124,149,154].

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5. Барский, А. Б. Планирование параллельных вычислительных процессов / А.Б. Барский. М.: Машиностроение, 1980. - 192 с.

6. Береснев, B.JI. Целочисленные экстремальные задачи Сб. статей. / Отв. ред. Береснев. Новосибирск: Б. и., 1981. 74 с.

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

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

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

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

11. Водяхо, А.И. Высокопроизводительные системы обработки данных : учеб. пособие для ВУЗов /

12. A.И. Водяхо, Н.Н. Горпец, Д.В. Пузанков. М. : Высшая школа, 1997. - 304 с.

13. Воеводин, В. В. Параллельные вычисления /

14. B.В. Воеводин, Вл.В. Воеводин. СПб.: БХВ-Петербург, 2002. - 608 с.

15. Воробьев, Н.Н. Теория игр. Лекции для экономистов-кибернетиков / Н.Н. Воробьев. Л.: Изд-во Лен. гос. ун-та, 1974. - 245 с.

16. Гимади, Э.Х. Алгоритмы с оценками для задач планирования крупномасштабных проектов : автореф. дис. . док. физ.-мат. наук / Эдуард Хайрутдинович Гимади. Новосибирск, 1975. - 28 с.

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

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

19. Головкин, Б.А. Вычислительные системы с большим числом процессоров / Б.А. Головкин. М. : Радио и связь, 1995. - 320 с.

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

21. Гэри, М. Вычислительные машины и труднорешае-мые задачи / Майкл Гэри, Дэвид Джонсон; пер. с англ. Е.В. Левнера и М.А. Фрумкина. М.: Мир, 1982. - 416 с.

22. Дамке, М. Операционные система микроэвм / М. Дамке. М.: Финансы и статистика, 1985. - 151 с.

23. Дементьев, В.Т. Задачи оптимизации иерархических структур / В. Т. Дементьев. Новосибирск: Изд-во Новосиб. ун-та, 1996. - 167 с.

24. Диалоговые вычислительные комплексы. Обработка программ под управлением операционной системы ОС ДВК : учеб. пособ. Л.Ю. Забелин, Т. А. Марамыгина, О.И. Усенко. Новосибирск: Новосиб. электротех. ин-т связи им. Н.Д. Псурцева 1990. - 50 с.

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

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

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

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

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

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

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

32. Живучая кластерная вычислительная система / В. Г. Хорошевский, Ю.С. Майданов, С.Н. Мамойленко, К.В. Павский и др. // Распределенные кластерные вычисления : труды школы-семинара. Красноярск: Изд-во Краен, гос. тех. ун-та, 2001. - С. 109-113.

33. Журавлев, Ю.И. Локальные алгоритмы решения дискретных экстремальных задач автореф. дис. . док. физ.-мат. наук / Юрий Иванович Журавлев. Новосибирск, 1965. - 24 с.

34. Забродин, А.В. Параллельные вычислительные технологии. Состояние и перспективы : препринт / А.В. Забродин. М. Изд-во Ин-та прикл. матем. им. М.В. Келдыша, 1995. - 34 с.

35. Итеративные методы в теории и программировании / В.З. Беленький, В. А. Волконский, С. А. Иваников, А.Б. Поманский, А.Д. Шапиро. М.: Наука, 1974 - 241 с.

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

37. Игнатьев, М.Б. Управление вычислительными процессами / М.Б. Игнатьев. JI.: Изд-во Лен. гос. тех. ун-та, 1973. - 296 с.

38. Каляев, А. В. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений / А.В. Каляев, И.И. Левин. М.: Янус-К, 2003. - 380 с.

39. Карцев, М.А. Вычислительные системы и синхронная арифметика / М.А. Карцев, В.А. Брик. М. : Радио и связь, 1981. - 359 с.

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

41. Клейнрок, Л. Вычислительные системы с очередями / Леонард Клейнрок; перевод с англ. под ред. Б.С. Цыбакова. М.: Мир, 1979. - 600 с.

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

43. Корнеев, В.В. Об организации коммуникаций между процессами в вычислительной системе МИКРОС /

44. B.В. Корнеев и др. // Вычислительные системы. 1985.1. C. 70-84.

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

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

47. Корнеев, В.В. Способ организации межмашинных обменов в вычислительных системах с программируемой структурой / В.В. Корнеев // Электронное моделирование. 1982. - № б. - С. 17-25.

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

49. Корнеев, В.В. О децентрализованном алгоритме распределения задач в вычислительных системах с программируемой структурой / В.В. Корнеев, О.Г. Монахов // Архитектура вычислительных систем с программируемой структурой.' 1980. - № 2. - С. 3-17.

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

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

52. Корнеев, В. В. Вычислительные системы с программируемой структурой / В.В.Корнеев, В.Г. Хорошевский // Электронное моделирование. 197 9. - № 1. - С. 4253.

53. Корнеев, В.В. Структура и функциональная организация вычислительных систем с программируемой структурой : препринт / В.В. Корнеев, В.Г. Хорошевский.- Новосибирск: Изд-во Ин-та математики СО АН СССР, 1979. 47 с.

54. Королёв, JI.H. Микропроцессоры, микро- и мини-ЭВМ : учеб. пособие для ВУЗов / JI.H. Королёв. М. : Изд-во Мое. гос. ун-та, 1988. - 211 с.

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

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

57. Лазарев, В.Г. Динамическое управление потоками в сетях / В.Г. Лазарев, Ю.В. Лазарев. М. : Радио и связь, 1983. - 216 с.

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

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

60. Левин, В. К. Современные суперкомпьютеры семейства МВС Электронный ресурс. / В.К. Левин. Электрон. текст, дан. - Б. м., 2002. - Режим доступа : http://www.parallel.ru/mvs/levin.html.

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

62. Майоров, С. А. Основы теории вычислительных систем / С.А. Майоров, Г.И. Новиков, Т.И. Алиев. М. : Высшая школа, 197 8. - 408 с.

63. Малышкин, Э.Э. Параллельное программирование мультикомпьютеров : учеб. пособие / Э.Э. Малышкин. Ярославль: ЯГУ, 1999. 135 с.

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

65. Марчук, Г.И. Введение в методы вычислительной математики : курс лекций / Г.И. Марчук. Новосибирск: Изд-во Новосиб. гос. ун-та, 1971. - 233 с.

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

67. Митчелл, М. Программирование для Linux. Профессиональный подход / Марк Митчел, Джефри Оулдем, Алекс Самьюэл; пер. с англ. С.Н. Гинсбурга. М. : Вильяме, 2002. - 287 с.

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

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

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

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

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

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

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

75. Олифер, В. Г. Сетевые операционные системы /

76. B.Г. Олифер, Н.А. Олифер. СПб.: Питер, 2001. - 544 с.

77. Олифер, В.Г. Компьютерные сети. Принципы, технологии, протоколы / В. Г. Олифер, Н.А. Олифер. СПб.: Питер, 2002. 672 с.

78. Пашкевич, С. Д. Основы мультипрограммирования для специализированных вычислительных систем /

79. C.Д. Пашкевич. М.: Советское радио, 1978. - 183 с.

80. Пискунов, С. В. Разработка микропроцессорных методов синтеза структур параллельных вычислительных устройств : авторефер. дис. . канд. тех. наук / Сергей Владиславович Пискунов. М., 1985. - 22 с.

81. Пискунов, С.В. Язык микропрограммного описания моделей однородных параллельных вычислительных устройств / С. В. Пискунов // Вычислительные системы.1980. Вып. 82 - С. 26-40.

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

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

84. Прангишвили, И.В. Многопроцессорные и локальные сети микро-ЭВМ в распределенных системах управления / И.В. Прангишвили. М. : Энергоатомиздат, 1985. - 272 с.

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

86. Рудаков, К.В. Универсальные и локальные ограничения в проблеме коррекции эвристических алгоритмов классификации / К.В. Рудаков // Кибернетика. 1987. -№2. - С. 30-34.

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

88. Самофалов, Г.Е. Основы построения конвейерных ЭВМ / Г.Е. Самофалов, Г.М. Луцкий. Киев: Вища школа, 1981. - 222 с.

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

90. Сергиенко, И.В. Фронтальные алгоритмы оптимизации для многопроцессорных систем / И. В. Сергиенко,

91. Л.Ф. Гульницкий // Кибернетика. 1981. - № б. - С. 14 .

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

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

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

95. Таненбаум, Э. Многоуровневая организация ЭВМ / Эндрю Таненбаум; пер. с англ. В.М. Кисельникова и др. М. : Мир, 1979. - 547 с.

96. Таненбаум, Э. Современные операционные системы : 2-е изд. / Эндрю Таненбаум; пер. с англ. А.Леонтьев. СПб.: Питер, 2002. - 1040 с.

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

98. Таха, X. Введение в исследование операций : б-е изд. / Таха Хэмди А., пер. с англ. В.И. Тюпти,

99. A.А. Минько. М.: Вильяме, 2001. - 911 с.

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

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

102. Фернбах, С. Супер ЭВМ. Аппаратная и программная реализация / Сидней Фернбах; пер. с англ.

103. B.М. Мамочкина. М.: Радио и связь, 1991. - 320 с.

104. Флоренсов, А.Н. Системное программирование в многозадачных ОС. Семантический подход : учеб. пособие / А.Н. Флоренсов. Омск: Изд-во Омского гос. тех. унта, 2000 - 92 с.

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

106. Харари, Ф. Теория графов / Френк Харари; пер. с англ. В.П. Козырева. Москва: Мир, 1973. - 300 с.

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

108. Хокни, Р. Параллельные ВС. Архитектура, программирование и алгоритмы / Роджер Хокни, Карл Джессоуп; пер. с англ. Д.Н. Абашкина. М.: Радио и связь, 1986. - 392 с.

109. Хокни, Р. Параллельные ЭВМ / Роджер Хокни, Карл Джессоуп; пер. с англ. Д.Н. Абашкина. М. : Радио и связь, 1986. - 390 с.

110. Хорошевский, В. Г. Архитектура вычислительных систем / В.Г. Хорошевский. М. : Изд-во Мое. гос. тех. ун-та им. Н.Э. Баумана, 2005. - 512 с.

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

112. Хорошевский, В. Г. Инженерный анализ функционирования вычислительных систем / В.Г. Хорошевский.

113. М.: Радио и связь, 1978. 256 с.

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

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

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

117. Хорошевский, В. Г. Архитектура вычислительных систем для управления в электроэнергетике / В.Г. Хорошевский и др. // Распределенная обработка информации : труды пятого международного семинара. Новосибирск: Б.и., 1995. - С. 53-63.

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

119. Хорошевский, В.Г. Эвристические алгоритмы распределения набора задач по машинам вычислительной системы / В. Г. Хорошевский, М.С. Седельников // Автометрия. 2004. - Том 40. - № 4. - С. 76-87.

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

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

122. Шокин, Ю.И. Численные методы газовой динамики и инвариантные разностные схемы : учеб. пособие / Ю.И. Шокин. Новосибирск: Изд-во Новосиб. гос. ун-та, 1977. - 84 с.

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

124. Эндрюс, Г. Основы многопоточного, параллельного и распределенного программирования / Грегори Эндрюс; пер. с англ. А.С. Подосельника и др. М. : Вильяме, 2003. - 512 с.

125. Ядро операционной системы ЭМ вычислительной системы с программируемой структурой / В.В. Корнеев,

126. О.Г. Монахов и др. // Однородные вычислительные системы. 1981. - № 1. - С. 22-42.

127. Языки и параллельные ЭВМ : сб. ст. /

128. A.А. Самарский. М.:Наука, 1990. - 91 с.

129. Яненко, Н.Н. Параллельные вычисления в задачах математической физики на вычислительных системах с программируемой структурой / Н.Н. Яненко,

130. B.Г. Хорошевский, А.Д. Рычков // Электронное моделирование, 1984. Том б. - № 1 - С. 3-8.

131. Bellmann, R. Dynamic Programming / R. Bellmann.- Princeton University Press. 1957.

132. Chandy, K. Distributed Snapshots: Determining Global States of Distributed Systems / K. Chandy, L. Lamport // ACM Trans. Сотр. Syst. 1985. - Vol. 3.- № 1. P. 63-75.

133. Cray Inc The Supercomputer company Электронный ресурс. / Электрон, текст, и граф. дан. - Б. м., 2005. - Режим доступа : http://www.cray.com.

134. Condor. High Throughput Computing Электронный ресурс. / Электрон, текст, и граф. дан. Б. м., 2005. - Режим доступа : http://www.cs.wisc.edu/condor/.

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

136. Foster, I. Globus: A Metacomputing Infrastructure Toolkit. / I. Foster, C. Kesselman // International Journal of Supercomputer Applications. 1997. - Vol. 11. - № 2. - P. 115-128.

137. Globus Toolkit Электронный ресурс. / Электрон. текст, и граф. дан. Б. м., 2005. - Режим доступа : http://globus.org/toolkit/.

138. Grid Engine Электронный ресурс. / Электрон, текст, и граф. дан. Б. м., 2005. - Режим доступа : http://gridengine.sunsource.net/.

139. Hillis, D. The Connection Machine / D. Hillis // Scientific American. June. - 1987.

140. Johnson, D.S. Near-Optimal Bin Packing Algorithms : Doctoral Thesis / David S. Johnson. Dept. of Mathematics, Massachusetts Institute of Technology, Cambridge. - 1973.

141. Johnson, E.E. Completing an MIMD Multiprocessor Taxonomy / E.E. Johnson // Computer Architecture News. 1988. - V. 16. - № 2. - P. 44-48.

142. LSF Load-Sharing Facility Электронный ресурс. / Электрон, текст, и граф. дан. Б. м., 2004. -Режим доступа : http://www.eos.ncsu.edu/software/lsf/.

143. Khoroshevsky, V.G. MICROS: a family of large-scale distributed programmable structure computer systems / V.G. Khoroshevsky // Proc. Sixth Internat. Workshop on Distributed Data Processing. Novosibirsk: RAS Siberian Branch Publ., 1998. - p. 65.

144. Khoroshevsky, V.G., Sedelnikov, M.S. / V.G. Khoroshevsky, M.S. Sedelnikov Heuristic algorithms for tasks distribution between computer systems machines // Optoelectronics, instrumentation and data processing. Vol. 40. - № 4. - 2004. - P. 66-75.

145. Maui Cluster Scheduler Электронный ресурс. / Электрон, текст, и граф. дан. Б. м., 2005. - Режим доступа : http://www.clusterresources.com/products/ maui/.

146. OSCAR. Open Source Cluster Application Re-sourse Электронный ресурс. / Электрон, текст, и граф. дан. Б. м., 2005. - Режим доступа : http://oscar.openclustergroup.org/.

147. Page, E.S. On Monte-Carlo methods in congestion on problems: Searching for an optimum in discrete situations / E.S. Page // Operation Research. 1965. -Vol. 13. - № 2. - P. 291-299.

148. Portable Batch System Электронный ресурс. / Электрон, текст, и граф. дан. Б. м., 2005. - Режим доступа : http://www.openpbs.org/.

149. The Illiac IV computer / GH. Barnes, RM. Brown, M. Kato, DJ. Kuck,• DL. Slotnick, RA. Stoker // IEEE Trans. Comput. Vol. C-17. - 1968. - P. 746-757.

150. Top500 Supercomputer Sites. Computer classification Электронный ресурс. : June 2005 / Электрон, текст, и граф. дан. Б. м., 2005. - Режим доступа :http://top500.org/sublist/stats/index.php?list=25&type= archtype&submit=l.

151. TORQUE Resource Manager Электронный ресурс. / Электрон, текст, и граф. дан. Б. м., 2005. - Режим доступа : http://www.clusterresources.com/products/ torque/.

152. Worst-case performance bounds for simple one-dimensional packing algorithms / D.S. Johnson, A. Demers, J.D. Ullman, M.R. Garey, R.L. Graham // SIAM J. Comput. 3. 1974. - P. 299-325.

153. Zabrodin, A.V. The massively parallel computer system MBC-100 / A.V. Zabrodin, V.K. Levin, V.V. Korneev // Parallel Computing Technologies : Third International Conference. St.Petersburg, 1995.1. P.341-355.