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

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

УДК 681.324

МАМОЙЛЕНКО Сергей Николаевич

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

Специальности:

05.13.13 - 'Телекоммуникационные системы и компьютерные сети"' 05.13.15 - "Вычислительные машины и системы"'

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

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

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

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

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

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

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

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

Водяхо Александр Иванович

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

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

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

Новосибирский государственный технический университет,

Министерства образования Российской федерации, г. Новосибирск

Защита состоится

в_часов на заседании

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

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

Автореферат разослан

Учёный секретарь

диссертационного совета Д219.005.01 кандидат технических наук, профессор

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

2004-4 3

24124

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

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

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

Разработки распределенных вычислительных систем ведутся с середины XX столетия. С тех пор, в нашей стране и за рубежом выполнен ряд фундаментальных работ, посвященных проблемам организации высокопроизводительных вычислительных средств: проведены исследования по построению оптимальных (мак-ро)структур ВС, проработаны многие аспекты разработки программного обеспечения, исследован широкий крдач, допускающийлф<^!е1П^вк>торсализаци[о на распределённых ВС. Построены отечecreeiih ькРQSktfó.UilооддододПи микроЭВМ: СУММА, МИНИМЛКС,МИКРОС, семейств«} систё$^ШТ.ЕК№С-100, МВС-1000, МВС- ЮООМит.д.

Фундаментальный вклад в теорию и практику вычислительных и телекоммуникационных систем, компьютерных сетей и параллельных вычислительных технологий внесли советские и российские учёные, среди которых: Е.П. Балашов, В.Б. Бетелин, B.C. Бурцев, В.В. Васильев, В.М. Вишневский, В.В. Воеводин, В.М Глушков, В.В. Губарев, В.Ф. Евдокимов, Э.В. Евреинов, Л.В. Забродин, В.П. Иванников, М.Б. Игнатьев, А. В. Каляев, М.А. Карцев, J1.H. Королев, Н.А. Кузнецов, В.Г. Лазарев, С.А. Лебедев, В.К. Левин, Г.И. Марчук, Ю.И. Митропольский, В.К.Попков, Д.А.Поспелов, И.В. Прангишвили, Д.В. Пузанков, Г.Е. Пухов, Г.Г. Рябов, А.А. Самарский, В.Б. Смолов, А.Н. Томилин, A.M. Федотов, ЯЛ. Хетагуров, В.Г. Хорошевский, Б.Н. Четверушкин, Ю.И. Шокин, Н.Н. Яненко и другие.

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

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

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

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

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

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

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

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

• создания распределённой в пространстве кластерной вычислительной

системы (Grid-системы).

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

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

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

• разработаны математическая модель и алгоритм выбора последовательности опроса ЭМ с целью выравнивания загрузки вычислительной системы;

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

Практические результаты работы состоят в том, что:

• создана и введена в эксплуатацию распределённая в пространстве кластерная Grid-система;

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

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

Апробация работы. Основные результаты работы докладывались на Международных, Всероссийских и Региональных научных конференциях, в том числе: • Международной научно-технической конференции «Информатика и проблемы телекоммуникаций» (2001,2002,2003 гг., г. Новосибирск);

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

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

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

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

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

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

ваний (РФФИ) № 02-07-09380, 02-07-06099, 03-07-06008, 00-01-00126, 02-07-09379. Основные положения диссертационной работы использовались автором при разработке и чтении учебных курсов на Кафедре вычислительных систем СибГУТИ по дисциплинам «Операционные системы», «Распределённые операционные системы» и «Организация ЭВМ и систем».

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

Основные положения, выносимые на защиту:

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

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

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

Публикации. По теме диссертации опубликовано 14 работ.

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

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

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

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

В распределённых ВС все основные ресурсы (не только арифметико-логические устройства, но память и средства управления) являются логически и технически распределёнными. Число ЭМ в распределённых ВС допускает варьирование от нескольких единиц до 106 и более. Компьютерными сетями называется композиция персональных компьютеров, соединенных в сеть с использованием стандартных телекоммуникационных технологий (например, технология Ethernet, стек протоколов TCP/IP и т.п.). Такие сети могут быть программным способом настроенных на решение параллельных задач. В этом случае они называются кластерными вычислительными системами или просто кластерами. Grid-системы образуются путем объединения различных вычислительных ресурсов по средствам стандартных телекоммуникационных технологий (протоколов, сетей, и т.п.), например всемирной сети Интернет. По сути, кластеры и Grid-системы являются распределенными ВС.

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

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

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

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

• планирование ресурсов - определение кому, когда и в каком количестве следует выделять ресурсы;

• удовлетворение запросов на ресурсы;

• отслеживание состояния и учет использования ресурсов - сбор и поддержание оперативной информации о том, заняты или свободны ресурсы и какая доля ресурсов уже распределена;

• разрешение конфликтов доступа к ресурсам.

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

Система параллельного программирования (Р-программирования) предназначена для разработки программного обеспечения и включает в себя различные трансляторы (компиляторы), библиотеки программ и средства отладки и анализа эффективности.

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

В первом случае параллельная программа выполняет одну и ту же операцию над различными частями исходных данных. При разработке таких программ часто используются специализированные языки программирования и трансляторы для них, например HPF, Cilk, С*, ZPL, FORTRAN M, МрС и т.д.

Вторая парадигма предусматривает разбиение вычислительной задачи на несколько относительно самостоятельных подзадач. Каждая подзадача при этом выполняется на своей ЭМ. Для координации процесса вычислений подзадачи обмениваются между собой сообщениями. Практически такой обмен осуществляется вызовом процедур специализированных библиотек, которые являются дополнением к обычным последовательным языкам программирования. Примерами стандартов по разработке библиотек передачи сообщений служат MPI (Message Passing Interface) и PVM (Parallel Virtual Machine). По сути, эти библиотеки воплотили в жизнь основные способы обмена информацией при разработке параллельных программ, предложенные в 60-е годы в ИМ АН СССР.

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

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

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

Режим решения сложной задачи - монопрограммный. Для решения одной задачи используются ресурсы всей ВС.

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

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

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

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

(¿1' ) , где tl - время решения / -ой задачи, а г1 - её ранг (число параллельных

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

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

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

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

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

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

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

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

где С - цена эксплуатации одной ЭМ в единицу времени; С2 - величина штрафа,

выплачиваемого диспетчером в единицу времени за одну простаивающую ЭМ; С3 -величина штрафа, налагаемого на диспетчер в единицу времени, если он сформировал пакет с рангом, большим на единицу числа выделенных ЭМ, т.е. г = \ + 1 ,

/, Г Е Е — {0,1,2,..., л} ; П - число ЭМ в вычислительной системе.

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

Алгоритм функционирования диспетчера ЭМ при формировании пакетов задач может быть представлен в виде топологического дерева (рис. 2). Нулевой ход осуществляется случайным механизмом и определяет текущее состояние системы (наличия k исправных ЭМ). Как известно (из теории вычислительных систем), вероятность того, что система в стационарном режиме работы находится в состоянии к определяется как:

(2)

где - интенсивность потока отказов в одной ЭМ, а - интенсивность восстановлений отказавших ЭМ.

Первый ход осуществляется диспетчером ВС, который, зная состояние системы, выделяет подсистему из i ЭМ. Второй ход делает диспетчер ЭМ (не зная состояния системы и какая подсистема будет выделена для решения) - формирует пакет ранга г .

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

С«г - СгР1 '

(3)

измене-

где р1 ~ /^ Рк . Очевидно, что р'. > р^ , при / < ], Е Е . Такое ] ние коэффициентов справедливо потому, что ВС может выделить / ЭМ только в

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

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

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

Рис.2. Топологическое дерево алгоритма формирования пакетов задач.

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

Теорема 1. Матрица С — Цс^. |, не имеет седловых точек тогда и только тогда, когда:

Теорема 2. Матрица С —|с(л |, не имеет седловых точек тогда и только тогда, когда:

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

0 £ [0,0+ ], где 0* - максимально допустимое время решения пакета задач.

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

Если диспетчер ЭМ каждый раз создает пакеты из т задач, а диспетчер ВС назначает им время решения пакета, равное 0, то средние издержки на решение одного пакета оцениваются как:

(4)

где С4 - штраф за превышение времени пакета задач на единицу времени, Т - математическое ожидание величины t¡.

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

С = \\с

разного времени решения составляют матрицу платежей

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

игры к конечной путём разбиения интервала [0,0+ ] на отрезки длинной Е . В работе экспериментально показано, что уже при величине £ равной 0,01 возможно получить решение задачи. С уменьшением увеличивается размер получаемой матрицы платежей, а результаты решения отличаются меньше, чем на 10%.

Теорема 3. Матрица С ~ Цс^ | ли выполняются следующие условия:

не имеет решения в чистых стратегиях, ес-

где

m+ - максимально допустимое число задач в пакете. Запись - означает целую часть от X.

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

• порядка опроса элементарных машин • • ■»

• в очередях каких ЭМ есть задачи («состояния» системы)^^

• структуры системы, т.е. расстояния й1 до опрашиваемой ( 1 -ой) ЭМ;

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

Рис. 3. Результаты моделирования методов формирования пакетов задач

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

ная математическая модель поиска оптимальной последовательности опроса ЭМ относится к классу игр с «природой».

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

(5)

где

время, затрачиваемое диспетчером на

поиск пакетов при выборе последовательности опроса и нахождения сис-

темы в состоянии - номер в последовательности опроса ЭМ такой,

что во всех опрошенных до этого ЭМ не оказывается пакетов в очереди, другими словами ^ {¡^2 ...}, / , Е {ц^ , ] = } .

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

{'М-}

(6)

ц/ •(•( •» \ •! •!

где гуЦ^з •••) - вероятность нахождения системы в с о с т о яну.и., запись - означает, что суммирование ведется по всем возможным состояниям

системы.

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

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

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

В третей главе описана архитектура и программное обеспечение созданной распределённой в пространстве кластерной вычислительной Grid-системы. Эта система эксплуатируется Центром параллельных вычислительных технологий Сибирского государственного университета телекоммуникаций и информатики совместно с Институтом физики полупроводников СО РАН.

В архитектурном плане система состоит из двух сосредоточенных кластеров, один из которых располагается в помещении Лаборатории параллельных вычислений ЦГШТ СибГУТИ, а другой - в Лаборатории вычислительных систем ИФП СО РАН.

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

Кластеры созданы на основе стандартных персональных компьютеров (ПК) на базе процессоров семейства Intel. Все ПК оборудованы собственной оперативной памятью, сетевым адаптером стандарта Fast Ethernet (максимальная скорость передачи данных 100 Мбит/с), клавиатурой, манипулятором типа «мышь», жестким диском, видеоадаптером и монитором. Для организации сети передачи данных используются четыре коммутатора (switch) фирмы 3COM, использована топология типа "звезда", соединение организовано с помощью медного кабеля «витой пары» категории 5.

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

Кластерная ВС допускает масштабирование и, естественно, способна взаимодействовать с множеством другим кластеров. Таким образом, она является основой для формирования распределённой в пространстве конфигурации (Grid-модели).

Все персональные компьютеры функционируют под управлением ОС Linux (дистрибутив ASPLinux v.7.3, ядро 2.4.19). Для разработки и реализации параллельных программ используется технология MPI (реализация LAM v.6.5.9 или MPICH v. 1.2.0).

Для межкластерных взаимодействий через телефонный канал используется пакет программ, реализующий протокол взаимодействия Point-to-Point (PPP). В состав программного обеспечения также входят компоненты (ssh, telnet), позволяющие получить удаленный доступ к кластеру.

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

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

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

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

Производительность созданной кластерной Grid-системы определяется двумя характеристиками: производительностью персональных компьютеров и пропускной способностью телекоммуникационной системы.

Рис. 4. Архитектура пространственно распределённой кластерной ВС

17

[прикладные программы'

ДИСПЕТЧЕР РАСПРЕДЕЛЕННЫХ РЕСУРСОВ

J

Г

" Диагностические 1

! средства

средства ■<">> —i

параллельного , программирования

ПОДСИСТЕМА I

___ _ " ! анализа !

ГЕКШФИГУРАТОр] | ЭФФЕКТИВНОСТИ ] г-. СИСТЕМЫ I

zl "Т: i с г' X

СРЕДСТВА МЕЖМАШИННОГО ВЗАИМОДЕЙСТВИЯ j •lm* •»< n.»«i '

__________________________________

СЕТЕВЫЕ ПРОТОКОЛЫ | 1

ОПЕРАЦИОННАЯ СИСТЕМА 1

С

СТАНДАРТНЫЕ СРЕДСТЪА 1

СРЕДСТВА ОПТИМАЛЬНОЙ ОРГАНИЗАЦИИ «ЛЯСЦИОнИРОвАНИя

Рис. 5. Структура ПО кластерной системы

В настоящее время существует множество программ для тестирования производительности вычислительных систем (Benchmarks). Наибольшее распространение получил тест Linpack, реализующий решение системы линейных алгебраических уравнений. Для измерения производительности кластерных систем используется его параллельная версия: ScaLAPACK.. По результатам теста ScaLAPACK реальная максимальная производительность 32 процессорной кластерной системы получилась равной 5,5 GFLOPS.

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

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

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

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

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

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

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

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

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

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

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

6. Проведено тестирование производительности созданной кластерной вг1ё-системы, включающее оценку возможностей персональных компьютеров и телекоммуникационной системы.

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

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

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

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

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

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

6. Мамойленко С.Н., Майданов Ю.С. Разработка аппаратно-программного инструментария для моделирования болыпемасштабных вычислительных систем // Тезисы Научно-методической конференции СибГУТИ «Основы и сущность междисциплинарной организации образования». - Новосибирск. - 2002. - С. 36-37.

7. Мамойленко С.Н., Майданов Ю.С. Развитие кластерной вычислительной системы // Тезисы Научно-методической конференции.СибГУТИ «Основы и сущность междисциплинарной организации образования». - Новосибирск. - 2003. -С. 19-20.

8. Мамойленко С.Н. Параллельные методы функционирования распределённых вычислительных систем // Тезисы Региональной научной конференции студентов, аспирантов и молодых ученых «Наука. Техника. Инновации». - Новоси-бирск.-2002.-С. 10-12.

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

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

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

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

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

14. 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. 81-91.

МАМОЙЛЕНКО Сергей Николаевич

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

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

Подписано в печать "12" января 2004 г.

Формат бумаги 62x84/16, отпечатано на ризографе, шрифт № 10, изд. л.1,3, заказ № 12, тираж 150 экз., ГОУ ВПО «СибГУТИ». 630102, г. Новосибирск, ул. Кирова, 86.

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

ВВЕДЕНИЕ.б

ГЛАВА 1. ОСОБЕННОСТИ ОРГАНИЗАЦИИ БОЛЫИЕМАСШТАБНЫХ

РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ И СЕТЕЙ

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

1.2. Классификация ВС. Распределенные ВС. Компьютерные сети и кластерные ВС. Gridсистемы.

1.3. Цели создания распределенных ВС и Grid-систем

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

1.4.1. Структура элементарных машин

1.4.2. Структура телекоммуникационной системы

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

1.5.1. Структура программного обеспечения

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

1.6. Живучесть распределённых ВС и Grid-систем

1.7. Обзор существующих систем управления распределенными ВС и Grid-системами

1.8. Выводы.

ГЛАВА 2. СРЕДСТВА ОРГАНИЗАЦИИ ФУНКЦИОНИРОВАНИЯ

РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ И СЕТЕЙ

GRID-СИСТЕМ)

2.1. Обзор существующих подходов к организации функционирования распределенных ВС и Grid-систем

2.2. Понятия «вычислительный центр», «очередь задач» и «диспетчер ОС».

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

2.4.1. Выбор ранга задач для формирования пакетов при условии выделения всех доступных ЭМ системы для решения задач

2.4.2. Выбор ранга задач для формирования пакетов при условии выделения части доступных ЭМ системы для решения задач

2.5. Формирование пакетов задач и определение времени их решения на ВС.

2.6. Определение последовательности опроса ЭМ для выравнивания загрузки системы

2.7. Решение теоретико-игровых проблем

2.7.1. Основные определения теории игр

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

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

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

2.8. Выводы.

ГЛАВА 3. ПРОСТРАНСТВЕННО РАСПРЕДЕЛЕННАЯ КЛАСТЕРНАЯ

ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА (GRID-СИСТЕМА)

3.1. Классификация кластерных ВС

3.2. Пространственно распределённая кластерная ВС (Grid-система)

3.2.1. Архитектура пространственно распределённой кластерной ВС (Grid-системы)

3.2.2. Оценка производительности кластерной ВС

3.3. Моделирование решения поставленных задач управления распределёнными ВС на кластерной системе.

3.4. Разработка диспетчера распределенной очереди задач в кластерных ВС.

3.5. Выводы.

Актуальность работы. Потребность в высокопроизводительных средствах обработки информации привела к созданию параллельных вычислительных систем (ВС) с массовым параллелизмом[10, 29,30, 124] . В общем случае, ВС суть композиция элементарных машин (ЭМ), соединённых телекоммуникационной сетью. Построение таких систем основывается на принципах: параллельности выполнения операций, программируемости структуры и конструктивной однородности. Одним из типов архитектур вычислительных систем являются распределённые ВС. Все основные ресурсы таких систем (не только арифметико-логические устройства, но память и средства управления) являются логически и технически распределёнными. Число ЭМ в распределённых ВС допускает варьирование от нескольких единиц до 10б и более (например, в МВС-1000М это число равно 7 68, а в создаваемой системе IBM Blue Gene - 1 ООО ООО). Для решения задач могут использоваться как все ЭМ (вся система целиком), так и часть из них. В последнем случае возможно одновременное решение нескольких задач, путём организации параллельного мультипрограммного режима. Опыт применения распределённых ВС показал [см., например, 37, 38,44-57], что, чаще всего, для решения задач не требуются ресурсы всей системы. Поэтому проблема создания децентрализованных средств организации функционирования распределенных ВС в мультипрограммных режимах на сегодняшний день является актуальной.

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

Идея объединения различных пространственно распределённых вычислительных ресурсов, начиная от простых ПК и заканчивая суперкомпьютерами, с использованием стандартных телекоммуникационных средств (сетей, протоколов и т.п.) получила название Grid-технологии [15].

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

МИКРОС, семейство систем МВС: МВС-100, МВС-1000, МВС-1000М и т.д.

Фундаментальный вклад в теорию и практику вычислительных и телекоммуникационных систем, компьютерных сетей и параллельных вычислительных технологий внесли советские и российские учёные, среди которых: Е.П. Балашов [1,2], В.В. Бетелин [8], B.C. Бурцев [10,119], В.В. Васильев [12], В.М. Вишневский [13,31], В.В. Воеводин [15], В.М. Глушков [17,106], В.В. Губарев [19], В.Ф. Евдокимов [26], Э.В. Евреинов [27-30],

A.В. Забродин [94, 160], В.П. Иванников [34], М.Б. Игнатьев [35], А.В. Каляев [37], М.А. Карцев [39], JT.H. Королев [57], Н.А. Кузнецов [61], В.Г. Лазарев [62,105], С.А. Лебедев [64], В.К. Левин [65,160], Г.И. Марчук [76], Ю.И. Митропольский [43], В.К. Попков [100,101], Д.А. Поспелов [102], И.В. Прангишвили [103,104], Д.В. Пузанков [2,14,80,81], Г.Е. Пухов [105], Г.Г. Рябов [111], А.А. Самарский[152],

B.Б. Смолов[116], А.Н. Томилин[128] , A.M. Федотов[129], Я.А. Хетагуров[132] , В.Г. Хорошевский [135-145, 157], Б.Н. Четверушкин [148], Ю.И. Шокин [149], Н.Н. Яненко [153] и другие.

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

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

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

Учитывая все сказанное выше, рассматриваемый в данной работе подход к организации функционирования распределённых вычислительных систем и сетей в мультипрограммных режимах (с использованием континуального подхода [23, 136] и методов теории игр [6, 7, 22, 24, 60, 93, 95, 110, 121, 147, 154,158]) видится перспективным.

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

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

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

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

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

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

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

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

• разработаны математическая модель и алгоритм выбора последовательности опроса ЭМ с целью выравнивания загрузки вычислительной системы;

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

ВС при обслуживании интенсивных потоков параллельных задач.

Практические результаты работы состоят в том, что:

• создана и введена в эксплуатацию распределённая в пространстве кластерная Grid-система;

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

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

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

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

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

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

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

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

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

Реализация результатов работы. Результаты диссертационной работы нашли применение в работах по созданию и развитию распределённой кластерной вычислительной системы Центра параллельных вычислительных технологий Сиб-ГУТИ. Работа поддержана грантами Российского фонда фундаментальных исследований (РФФИ) № 02-07-09380, 02-0706099, 03-07-06008, 00-01-00126, 02-07-09379. Основные положения диссертационной работы использовались автором при разработке и чтении учебных курсов на Кафедре вычислительных систем СибГУТИ по дисциплинам «Операционные системы», «Распределённые операционные системы» и «Организация ЭВМ и систем».

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

Основные положения, выносимые на защиту:

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

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

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

Публикации. По теме диссертации опубликовано 14 работ .

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

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

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

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

- формирование пакетов задач. Предлагаемая модель позволяет упростить процедуру формирования пакетов, что дает возможность её использования для динамического управления системой;

- организации опроса ЭМ в целях выравнивания загрузки системы.

Рассмотрены методы их решения и предложены параллельные версии этих методов.

В третьей главе описана архитектура и программное обеспечение созданной распределённой в пространстве кластерной вычислительной Grid-системы. Эта система эксплуатируется Центром параллельных вычислительных технологий Сибирского государственного университета телекоммуникаций и информатики совместно с Институтом физики полупроводников СО РАН.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

6.Проведено тестирование производительности созданной кластерной Grid-системы, включающее оценку возможностей персональных компьютеров и телекоммуникационной системы.

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

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

3. B.Б.Смолов. М.: Радио и связь, 1981. - 326 с.

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

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

6. Беленький В.З., Волконский В.А., Иваников

7. C.А., Поманский А.Б., Шапиро А.Д. Итеративные методы в теории и программировании. М.: Наука, 1974.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

22. Губарев В.В. Концептуальные вопросы информатики. Новосибирск: НГТУ, 2002. - 120 с.

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

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

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

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

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

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

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

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

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

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

33. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. -М.:Радио и связь, 1988. 191 с.

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

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

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

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

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

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

40. Каранчук В.П., Усенко О.И., Марамыгина Т.А., Авдеенко И.Н. Архитектурные концепции создания микромашинных вычислительных систем. Отчет НЭИС. - Новосибирск, 1986. - 49 с.

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

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

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

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

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

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

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

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

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

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

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

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

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

54. Корнеев В. В., Монахов О. Г. и др. Ядро операционной системы ЭМ вычислительной системы с программируемой структурой // Однородные вычислительные системы. Новосибирск, 1981. - С. 22-42.

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

56. Корнеев В.В., Хорошевский В.Г. Архитектура вычислительных систем с программируемой структурой. -Препринт. Новосибирск, 1979. - 48 с. (ИМ СО АН СССР, ОВС-Ю) .

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

58. Корнеев В.В., Хорошевский В. Г. Структура и функциональная организация вычислительных систем с программируемой структурой. Препринт. - Новосибирск, 1979. - 47. (ИТПМ, СО АН СССР, ОВС-11).

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

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

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

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

63. Кузнецов Н.А., Кульба В.В., Ковалевский С.Е. Методы анализа синтеза модульных информационно управляющих систем. М.: Физмалит, 2002. - 797 с.

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

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

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

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

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

69. Майданов Ю.С. Подходы к организации контроля, диагностики и реконфигурации структуры вычислительных систем. // Материалы Международной научно-техническойконференции «Информатика и проблемы телекоммуникаций»,- Новосибирск, 2001. С. 86-88.

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

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

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

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

74. Мамойленко С.Н. Параллельные методы организации функционирования распределенных вычислительных систем. // Материалы докладов региональной научной конференции студентов, аспирантов и молодых ученых. Новосибирск, 2002. - С. 10-12.

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

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

77. Матрчные игры. Сб. переводов / Н.Н. Воробьев. ФИЗМАТГИЗ, 1961.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

94. Параллельные вычислительные технологии. Состояние и перспективы / А.В. Забродин. М., 1995\ -(Препр. / РАН, Ин-т прикл. матем. им. М.В. Келдыша, 9971) .

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

96. Пашкевич С. Д. Основы мультипрограммирования для специализированных вычислительных систем. М. : Советское радио, 1978. - 183 с.

97. Пискунов С. В. Построение микропрограммных описаний однородных вычислительных структур. Тез. докл. III Всесоюзн. семинара «Моделирование дискретных управляющих и вычислительных систем». Свердловск, 1981. - С. 55-57.

98. Пискунов С.В. разработка микропроцессорных методов синтеза структур параллельных вычислительных устройств. Авторефер. дис. на соиск. уч. ст. к.т.н. (05.13.13). М.: 1985. - 22 с.

99. Пискунов С.В. Язык микропрограммного описания моделей однородных параллельных вычислительных устройств. В кн.: Архитектура вычислительных систем с программируемой структурой (Вычислительные системы, вып. 82). - Новосибирск, 1980. - С. 26-40.

100. Попков В.К. Моделирование информационных сетей. Новосибирск: ВЦ СО РАН, 1994. - 163.

101. Попков В.К., Мухопад Ю.Ф. Специализированные вычислительные среды / В.Б. Смолов. Улан-Уде: Бурятское книжн. изд-во, 1982. - 189 с.

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

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

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

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

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

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

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

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

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

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

112. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наукова думка, 1985. - 384 с.

113. Сергиенко И.В., Гульницкий Л.Ф. Фронтальные алгоритмы оптимизации для многопроцессорных систем // Кибернетика. 1981. - № 6. - С. 1-4.

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

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

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

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

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

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

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

121. Таненбаум Э. Многоуровневая организация ЭВМ. М. : Мир, 1979. - 547 с.

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

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

124. Таха Хэмди А. Введение в исследование операций / б-е изд., пер. с англ. М.: Вильяме, 2001. - 921 с.

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

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

127. Федотов A.M. Некорректные задачи со случайными ошибками в данных / М.М. Лаврентьев. Новосибирск: Наука. Сибирск. отдел., 1990. - 279 с.

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

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

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

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

132. Хокни Р., Джессоуп К. Параллельные ЭВМ. М.: Радио и связь, 1986. 390 с.

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

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

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

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

137. Хорошевский В. Г. и др. Архитектура вычислительных систем для управления в электроэнергетике // Труды пятого международного семинара «Распределенная обработка информации». Новосибирск. - 1995. - С. 5363.

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

139. Ядро операционной системы вычислительных систем с программируемой структурой / Отчет ИМ СО АН СССР; Руководитель темы: В. Г. Хорошевский. Исполнители: Корнеев В. В., Такров М.С., Задорожные А.Ф. № ГР 0.182.5008588. - Новосибирск, 1982. - 182 с.

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

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

142. Brown G.W., Iterative Solutions of Games by Fictious Play, Activity Analysis of Production and Allocatio, Cowles Commission for Research in Economics, Monograph 13, John Wiley & Sons, Inc., New York (1951), 374 376.

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

144. Foster I., Karonis N. and others. A Resource Management Architecture for Metacomputing Systems. Proc. IPPS/SPDP '98 Workshop on Job Scheduling Strategies for Parallel Processing, pg. 62-82, 1998. ftp://ftp.globus.org/pub/globus/papers/gram97.pdf

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

146. Robinson J., An Itertive Method of Solving a Game, Ann. Math. 54 (1951), 295 301.

147. Uwe M. Borghoff Catalogue of Distributed File/Operating systems. Springer-Verlag New York Berlin Heidelberg, 1992