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

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

Ильин Павел Евгеньевич

Организация территориально-распределенных вычислений с использованием Декомпозиционных

моделей

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

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

Научный руководитель: д.т.н., профессор И.И. Дзегеленок

1 1 ДЕК *

Москва, 2008

003457748

Работа выполнена на кафедре Вычислительных машин, систем и сетей Московского энергетического института (Технического университета).

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

доктор технических наук, профессор Дзегеленок Игорь Игоревич

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

доктор технических наук, профессор, Хетагуров Ярослав Афанасьевич

^дигпислпл Ч/. XI. С1..

Бурцев Александр Борисович

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

ФГУП НИИ «Квант»

Защита состоится «19» декабря 2008 г. в 18 час. 00 мин. на заседании Диссертационного совета Д 212.157.16 при Московском энергетическом институте (Техническом университете) по адресу: 111250, г. Москва, ул. Красноказарменная, д. 17 (ауд. Г-306).

С диссертацией можно ознакомиться в библиотеке Московского энергетического института (Технического университета).

Отзывы в двух экземплярах, заверенные печатью организации, просьба направлять по адресу: 111250, г. Москва, Красноказарменная ул., д. 14, Ученый совет МЭИ (ТУ).

Автореферат разослан «18» ноября 2008. Ученый секретарь

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

к. т. н., доцент _ Чернов СЛ.

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

Актуальность темы исследования Увеличение производительности процессоров сделало возможным применение неспециализированных персональных компьютеров в области управления территориально распределенными объектами. Здесь получают все большее признание территориально-распреде-ленные вычисления для задач, решаемых с применением методов декомпозиции с обработкой данных непосредственно по месту их возникновения. Такой подход дает ряд преимуществ: 1) стоимость нескольких десятков (или сотен) типовых компьютеров ниже, чем стоимость суперкомпьютера, который осуществлял бы централизованную обработку, 2) существенно уменьшается объем передаваемых данных, 3) в случае отказа каналов связи управление соответствующей частью объекта может осуществляться локально, 4) устраняется необходимость собирать все данные в одном месте.

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

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

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

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

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

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

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

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

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

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

7. Подтвердить практическую применимость предложенной вычислительной среды в региональной сети.

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

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

Методы исследования При выполнении работы применяются методы

теории параллельного программирования, методы теории графов, методы системного анализа, натурный эксперимент.

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

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

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

3. Архитектура ТРВС, которая позволила удовлетворить выявленные в работе требования к организации территориально-распределенных вычислений.

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

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

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

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

Апробация результатов Основные результаты диссертации докладывались и обсуждались на следующих конференциях: Тринадцатая международная научно-техническая конференция «Информационные средства и технологии». 18—20 октября 2005, МЭИ; Двенадцатая международная научно-техническая конференция студентов и аспирантов. 2—3 марта 2006, МЭИ; III Международная конференция «Параллельные вычисления и задачи управления» РАСО'2006 памяти И.В. Прангишвили. Москва, 2—4 октября 2006 г. Инситут проблем управления им. В.А. Трапезникова РАН; Пятнадцатая международная научно-техническая конференция «Информационные средства и технологии». 16—18 октября 2007, МЭИ.

Публикации Результаты данной работы отражены в 8 печатных публи-кацях, и в 5 публикациях в электронном журнале.

Структура и объем диссертационной работы состоит из введения, 4 глав, заключения, списка литературы и приложения. Она изложена на 113 страницах основного машинописного текста, содержит 12 рисунков, 5 таблиц, включает библиографию из 101 наименования. Общий объем диссертации равен 181 странице.

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

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

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

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

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

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

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

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

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

Рассмотрено три направления развития распределенных вычислений: клиент-серверное распределение, метакомпьютинг, GRID, и произведен сравнительный анализ следующих решений: стандарта MPI и его реализаций MPICH, OpenMPI, среды PVM, системы пакетного планирования Torque, пакета реализации G/Ж-вычислений GlobusTookit, пакета реализации Giî/D-вычислений Sun GRID Engine #1. Выявлено, что эти решения не удовлетворяют полностью требованиям, перечисленным выше из-за ограниченных возможностей по учету различий во времени передачи данных по каналам связи и отсутствия средств описания расположения источников и получателей данных. Результаты анализа представлены в таблице.

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

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

Клиент- Мета- GRID ТРВС

сервер компьютинг

Отслеживание доступных вычис- + - + +

лительных ресурсов

Адресация на уровне номеров - + + +

процессов задачи

Асинхронные обмены + + + +

Удаленный запуск параллельных - + + +

процессов

Обработка ошибочных ситуаций - + + +

Мониторинг хода выполнения - + + +

задачи

Учет ненадежности каналов связи и времени передачи данных - - - +

Учет расположения источников и получателей данных - - - +

Обеспечение независимости от особенностей аппаратных ресурсов - - + -

Наличие инфраструктуры разграничения доступа - - + -

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

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

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

ТРВС представляется в виде графа С0=<Р0,У0>, вершинам РО соответствуют вычислители ТРВС, а ребрам УО - каналы связи между вычислителями Граф взвешенный: веса вершин — производительность вычислителей, веса ребер — затраты на передачу данных по каналу связи. Источники и получатели данных, которые не являются вычислителями, представляются как вершины с

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

Построенный граф называется представлением аппаратной составляющей ТРВС нулевого уровня (или просто представлением ТВРС нулевого уровня). Далее производится построение представлений ТРВС верхних уровней: вычислители, затраты на передачу данных между которыми ниже величины Ду, объединяются в вычислительные регионы, которые обозначаются (где / — уровень представления, / — номер региона), регионы соответствуют вершинам /-ого уровня представления в/. При построении представления следующего уровня /+1 шаг увеличивается на Ду, построение заканчивается тогда, когда получен граф из одной вершины, соответствующий ТРВС в целом. В работе описан алгоритм построения таких представлений.

Под задачей, решаемой на ТРВС, подразумевается совокупность параллельных процессов, которые выполняются на одном или нескольких вычислителях и осуществляют обмены Данными в ходе вычислений. Предлагается следующее представление: изначально имеется ярусно-параллельная форма (ЯПФ) задачи, где веса вершин равны объемам вычислений, а веса дуг — объемам передаваемых данных. Далее выполняется коррекция объемов на некоторую штрафную величину, которая определяется латентностью и объемом накладных расходов в каналах связи.

Далее производится процесс преобразования графа задачи Т в граф параллельных процессов ТТ=<С,и>: из каждого яруса Т выбирается некоторое количество вычислительных этапов, которые будут выполняться в рамках одного параллельного процесса, и им ставится в соответствие вершина в графе ТТ. Затем добавляются вершины, соответствующие источникам и получателям данных для задачи. Вес таких вершин равен нулю, вес дуг, соединяющих их с вершинами паралелльных процессов — объему передаваемых данных. Для каждой из этих добавленных вершин указывается, в каком вычислительном регионе ТРВС она должна находиться.

Далее производится аналитическая оценка времени решения задачи при

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

Если сопоставить время решения задачи при централизованной (Треш.Чентр) и территориально-распределенной (Трешраспр) организации вычислений, получаем следующее соотношение:

АГ,_

тах{]£ с1т1Ртраспр+^{и^1ратр)+^ {^красп^к)+Тожт)

у _ решраспр_ т 1-1__¿ = 1_

~~ Л',_ Л')

тах(£ с, т/ртчентр+^ (иуУ^^+Х (™крап1р^к)+Тожп^

™ 1=1 ^=1 4=1

где т=\.М — номер рассматриваемого параллельного процесса задачи, М — количество параллельных процессов задачи,

с,,т —■ объем вычислений на г-ом этапе вычислений в т-ом параллельном процессе, выполняемом на вычислителе Рт,

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

Ляап,™ — количество этапов вычисления для «г-ого параллельного процесса, и, — объем передаваемых данных на 7-ом обмене между двумя параллельными процессами,

^ ч,нтР, ^рмг.р — затраты времени на передачу данных при 7-ом обмене при централизованном и распределенном подходах соответственно, и'к ца1тр, ^1рссПр — объем данных, доставляемых от источника данных до вычислителя, на котором выполняется параллельный процесс задачи анализа или объем данных, доставляемых от параллельного процесса к получателю данных при централизованном и распределенном подходах соответственно, дк — затраты на передачу данных при доставке данных от ¿-ого источника или к

¿-ому приемнику,

Л^обм,». — количество обменов для т-ого параллельного процесса, Л'исх т — количество источников и получателей данных, с которыми взаимодействует т-ът параллельный процесс,

Таж,т — время простоя из-за ожидания подготовки данных, получаемых от других параллельных процессов,

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

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

у _ ргшраспр_ т 1__к= 1_

Куск-у - ■

тах(^ с1:т1ртченЩ!+^ (и/^^+Е {*2-<1к)+Т0Ж,т)

М 1=1 ]=1 £ = 1

Если производительность узла кластера равна производительности вычислителя ТРВС, получаем упрощенный критерий оценки целесообразности применения территориально-распределенных вычислений:

(3)

/=1 у2 центр

Из условий (2) и (3) следует, что применение территориально-распределе-нных вычислений целесообразно для задач, объем данных д для взаимодействия с источниками и получателями данных которых существенно выше, чем объем данных н, передаваемых в ходе обменов, причем чем больше разность затрат на передачу данных в каналах связи между филиалами и внутри

филиалов, тем быстрее происходит рост эффективности.

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

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

Ключевым моментом при распределении задачи является выбор, что выгоднее — назначить параллельный процесс на более производительный (или менее загруженный) вычислитель или на менее производительный, но с меньшими затратами на взаимодействие с источниками или получателями данных. Для этого используются две вспомогательные величины: время ожидания завершения параллельного процесса Т„ж, время освобождения вычислительного ресурса 7'ссв. Время ожидания завершения параллельного процесса Тсж можно определить по следующей формуле:

н„

Tox:=:Tem+To(kl+Tdocm-Tetm=c/p+Y,UfVj+Ywk-<]k-Tebm , (4)

7=1 J=i

где с — объем вычислений во всем параллельном процессе, а величины р, а,, у,, Щ, Чк, Nos«, Госв соответствуют величинам pmpacnp, Щ, v]pac„p, wipacnp, qк, No6«,m, Лисхт, Toce из формулы (1), при этом m равно номеру распределяемого в данный момент параллельного процесса.

В терминах описанного представления ТРВС и задач планирование задач представляет собой процесс построения графа распределения задачи GT/, который получается в результате «наложения» графа параллельных процессов ТТ на граф текущего уровня представления ТРВС G1 следующим образом: весом вершины графа GT/ является время, затрачиваемое на вычисления (отношение

с1р), а весом ребер — время, затрачиваемое на обмены и взаимодействие с

Я*. лг„

источниками (величина '£uJ■Vj+'£Jwk■qk )•. В работе предложен алгоритм,

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

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

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

Производится классификация вариантов реализации архитектуры ТРВС по следующим признакам:

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

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

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

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

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

Архитектура ТРВС предусматривает сбор отладочной информации и автоматизированное обнаружение типовых ошибок разработчиков прикладных задач: 1) попытка передать пакет несуществующему вычислителю, 2) наличие отправленных, но не полученных данных после завершения задачи, 3) попытка обмена с несуществующим процессом, 4) попытка передать с нулевой длиной или с длиной, превышающей предельно-допустимый размер, 5) превышение предельно-допустимого интервала ожидания данных.

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

Особенностью территориально-распределенных вычислений является не-

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

Для автоматизации процесса учета затрат времени на передачу данных и учета ненадежности каналов связи была предложена методика измерения затрат на передачу данных средствами самой ТРВС между двумя произвольными вычислителями: первый вычислитель посылает два пакета данных разного размера (¿1 и ¿2) и фиксирует время отправления. Второй вычислитель получает эти пакеты и отправляет обратно. Первый получает эти пакеты и фиксирует время, которое потребовалось для их доставки {Та и ГД2 соответственно). Далее производится решение следующей системы уравнений:

и определяются две величины: латентность Глат (учитываемая на этапе коррекции объема передаваемых данных в представлении задачи в виде ЯПФ) и собственно затраты на передачу данных V.

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

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

В четвертой главе производится программная реализация ТРВС в соответствии с определенными в третьей главе принципами построения, произво-

дится экспериментальная проверка применимости ТРВС в электроэнергетике и проверка достоверности соотношения (1).

Экспериментальная версия ТРВС, получившая название КУРС-2004, предназначенная для исследования эффективности применения терри-ториально-распределенных вычислений и использования в учебном процессе, реализована в среде программирования Delphi с использованием коммуникационной библиотеки Indy Sockets. При реализации проведен сравнительный анализ направлений развития современных протоколов высокого уровня протокольного стека TCP/IP и предложен собственный протокол взаимодействия компонентов ТРВС.

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

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

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

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

1. Территориально-распределенный с применением метода декомпозиционных эквивалентов, при котором локальный источник данных находится на самом вычислителе.

2. Территориально-распределенный с применением метода декомпозиционных эквивалентов, при котором источник данных находится в одном сегменте локальной сети с вычислителем.

3. Централизованный (решение задачи методом Гаусса) с доставкой исходных данных по медленным каналам связи.

4. Централизованный (решение задачи методом декомпозиционных эквивалентов) с доставкой исходных данных по медленным каналам связи.

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

Реализация ТРВС КУРС-2004 нашла свое применение в учебном процессе по курсу «Поисковое проектирование вычислительных систем».

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

реализации. Это сделало возможным создать промышленно применимую версию ТРВС на основе существующих программных продуктов.

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

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

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

3. Разработана обобщенная архитектура ТРВС, учитывающая определенные выше требования к реализации распределенных вычислений.

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

5. Произведена программная реализация ТРВС, что позволило провести экспериментальное исследование ТРВС и применить ее в учебном процессе.

6. Определена и экспериментально подтверждена аналитическая зависимость эффективности применения распределенных вычислений.

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

СПИСОК ПУБЛИКАЦЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Ильин П.Е. Многозадачная территориально-распределенная вычислительная среда с учетом эффективности передачи данных. / П.Е. Ильин // Вестник МЭИ. - 2008. - №2. - М.: Изд-во МЭИ. - С. 95—99.

2. Ильин П.Е. Декомпозиционный подход к осуществлению GRID-технологий / И.И. Дзегеленок, П.Е. Ильин, Ш.А. Оцоков и др. // Научно-технический журнал «Информационная математика».-2005,-№1 (5).-С. 110-119.

3. Ильин П.Е. Архитектура параллельной сети для реализации GRID-

Iß

%/э

технологии. / И.И. Дзегеленок, П.Е. Ильин // Труды международной научно-технической конференции «Информационные средства и технологии», 18—20 октября 2005 г.: в 3-х т. Т. 3. - М.: Янус-К, 2005. - С. 100-103.

4. Ильин П.Е. Проект глобально-распределенной мультикомпьютерной среды для реализации декомпозиционных моделей управления. / И.И. Дзегеленок, П.Е. Ильин // Труды III Международной конференции «Параллельные вычисления и задачи управления» РАСО'2006, Москва, 2—4 октября 2006 г.

- М.: Институт проблем управления им. В.А. Трапезникова, 2006. - С. 400-406.

5. Ильин П.Е. Стратегия распределения параллельных процессов в глобально-распределенной мультикомпьютерной среде с учетом многозадачности. / П.Е. Ильин // Труды III Международной конференции «Параллельные вычисления и задачи управления» РАСО'2006, Москва, 2—4 октября 2006 г.

- М.: Инситут проблем управления им. В.А. Трапезникова, 2006. - С. 407-412.

6. Ильин П.Е. Организация мультизадачного выполнения параллельных программ в территориально ' распределенной сети. / И.И. Дзегеленок, П.Е. Ильин, A.M. Титов // Сборник научных трудов: К 85-летию ВЭИ / Под ред. В.Д. Ковалева. - М.: ГУП ВЭИ, 2006. - С. 107-112.

7. Ильин П.Е. Архитектура параллельной сети для реализации GRID-технологий. / П.Е Ильин // Радиоэлектроника, электротехника и энергетика. Двенадцатая Международная научно-техническая конференция студентов и аспирантов. Тезисы докладов. 2-3 марта 2006 г.: в 3-х т. Т. 1. - М.: Янус-К, 2006.-С.439-441.

8. Ильин П.Е. Варианты расширения архитектуры параллельной мультикомпьютерной сети. / Дзегеленок И.И., Ильин П.Е. // Труды международной научно-технической конференции «Информационные средства итехнологии». 16-18 октября 2007 г.: в 3-х т. Т. 2. -С. 155-158.

Подписало в печать

& It, WS г. Полиграфический центр МЭИ (ТУ) Красноказарменная ул., д. 13

Аннотация.

Список ключевых понятий, обозначений и сокращений.

Введение.

Глава 1. Предпосылки к осуществлению территориально- распределенных вычислений.

1.1 Введение в проблематику распределенных вычислений.

1.2 Требования к реализации территориально-распределенной вычислительной среды (ТРВС).

1.3 Обзор существующих технологий.

1.3.1 Интерфейс MPI и его реализации.

1.3.2 Интерфейс PVM.

1.3.3 Пакет реализации GRID-вычислений GlobusTook.it.

1.3.4 Система пакетного планирования Torque.

1.3.5 Пакет реализации GRID-вычислений Sun GRID Engine #1.

1.4 Цель и задачи диссертационного исследования.

Глава 2. Модель представления территориально-распределенной вычислительной среды (ТРВС).

2.1 Формализованное представление ТРВС.

2.2 Представление задач.

2.3 Сравнение централизованного и территориально-распределенного подходов с точки зрения времени решения задач.

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

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

2.6 Выводы по главе.

Глава 3. Определение архитектурных принципов построения ТРВС.

3.1 Разработка архитектуры ТРВС.

3.1.1 Выбор режима многозадачной работы ТРВС.

3.1.2 Разработка общих принципов организации архитектуры ТРВС.

3.1.3 Классификация и сравнительный анализ возможных вариантов построения ТРВС.

3.2 Динамическое управление приоритетами задач.

3.3 Обработка ошибочных ситуаций.

3.4 Выбор средств синхронизации процессов выполняемых задач.

3.5 Методика измерения затрат времени на передачу данных.

3.6 Выводы по главе.

Глава 4. Реализация и практическое применение ТРВС.

4.1 Реализация экспериментальной версии ТРВС.

4.1.1 Определение требований к экспериментальной версий ТРВС и выбор структуры программного проекта.

4.1.2 Разработка протокола взаимодействия компонентов ТРВС.

4.1.3 Особенности многопоточного режима.

4.2 Экспериментальная проверка применимости ТРВС.

4.2.1 Цель эксперимента и методика его проведения.

4.2.2 Результаты эксперимента.

4.3 Применение ТРВС в учебном процессе.

4.4 Возможность реализации ТРВС на базе существующих технологий.

4.5 Рекомендации по использованию и дальнейшему развитию ТРВС.

4.6 Выводы по главе.

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

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

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

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

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

1. Постоянное отслеживание доступных вычислительных ресурсов.

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

3. Обеспечение возможности асинхронного обмена данными.

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

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

6. Сбор отладочной информации о ходе выполнения параллельных процессов задачи.

7. Учет ненадежности каналов связи и существенных различий в их пропускной способности.

8. Наличие средств описания расположения источников и получателей данных.

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

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

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

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

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

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

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

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

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

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

7. Подтвердить практическую применимость предложенной вычислительной среды.

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

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

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

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

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

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

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

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

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

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

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

• Тринадцатая международная научно-техническая конференция «Информационные средства и технологии». 18—20 октября 2005, МЭИ.

• Двенадцатая международная научно-техническая конференция студентов и аспирантов. 2—3 марта 2006, МЭИ.

• III Международная конференция «Параллельные вычисления и задачи управления» РАСО'2006 памяти И.В. Прангишвили. Москва, 2—4 октября 2006 г. Институт проблем управления им. В.А. Трапезникова РАН.

• Пятнадцатая международная научно-техническая конференция «Информационные средства и технологии». 16—18 октября 2007, МЭИ. Структура диссертации Диссертация содержит 181 страницу, из них 45 страниц — приложения, 12 рисунков и 5 таблиц и состоит из четырех глав, введения и заключения.

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

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

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

В четвертой главе осуществляется выбор инструментальных средств для программной реализации ТРВС, производится разработка протокола взаимодействия компонентов ТРВС. Далее описывается методика проведения эксперимента по оценке эффективности практического применения ТРВС на примере задачи расчета установившегося режима электроэнергетической системы и приводятся результаты эксперимента. Затем рассматривается возможность реализации промышленной версии ТРВС на базе существующих технологий: среды OpenMPI, являющейся одной из реализаций стандарта МР/, системы пакетного планирования Torque и протокола SNMP. Также дается ряд рекомендаций по использованию экспериментальной версии ТРВС и ее дальнейшему развитию.

4.6 Выводы по главе

В главе 4 были получены следующие результаты:

1. Сформулированы требования к экспериментальной версии ТРВС. Для ее реализации произведен выбор среды разработки Borland Delphi, коммуникационной библиотеки Indy Sockets, структура программного проекта, и обоснована целесообразность применения объектно-ориентированного программирования, что позволило избежать дублирования общей части кода различных компонент ТРВС, повысить его структурированность и упростить отладку. В результате была реализована экспериментальная версия ТРВС, соответствующая выбранной в главе 3 архитектуре и использующая разработанную в главе 2 модель представления ТРВС и алгоритмы распределения задач.

2. Изучены основные способы построения протоколов высокого уровня на основе протокольного стека TCP/IP, и разработан протокол взаимодействия компонентов ТРВС. Это позволило реализовать универсальные процедуры приема и передачи команд протокола, что существенно упростило обнаружение ошибок и обработку отказов вычислителей.

3. Для проверки работоспособности предложенной реализации ТРВС и оценки эффективности применения распределенных вычислений была разработана методика проведения эксперимента. В ходе проведения эксперимента было установлено, что применение распределенных вычислений для задачи расчета установившегося режима электро-энергетической сети позволяет получить ускорение как за счет декомпозиции и распараллеливания (минимальный полученный ХуСк=1,36), так и за счет обработки данных по месту их возникновения (/£уСК=4,3 при скорости доставки данных для централизованной обработки 256 Кбит/с).

4. Сфорумлированы требования к промышленной версии ТРВС. На основе этих требований была предложена реализация ТРВС на основе существующих решений OpenMPI в качестве клиентской библиотеки, пакетного планировщика Torque в качестве локального диспетчера и протокола SNMP для сбора информации о вычислителях и измерения затрат на передачу данных, и определены доработки, которые требуется осуществить для реализации модели представления ТРВС, разработанной в главе 2 и учитывающей . В результате возникла возможность существенно уменьшить объем тестирования и осуществлять разработку прикладных программ с использованием общепринятого стандарта MPI.

5. Дан ряд рекомендаций по практическому применению ТРВС и ее дальнейшему развитию.

Заключение

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

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

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

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

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

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

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

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

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

1. Назаров А.В. Современная телеметрия в теории и практике: учебный курс. /

2. A.В. Назаров. — СПб.: Наука и техника. — 2007. — 627 с.

3. Суханов О.А. Иерархические модели в анализе и управлении режимаим электроэнергетических систем / О.А. Суханов. — М.: Издательский дом МЭИ, 2007.-312 с.

4. Шенборт И.М. Проектирование вычислительных систем распределенных АСУ ТП / И.М. Шенборт, В.М. Алиев. М.: Энергоатомиздат, 1989. - 88 с.

5. Автоматизация управления энергообъединениями / В.В. Гончуков,

6. B.М. Горинштейн, JI.A. Крумм и др.; под ред. С.А. Совалова. -М.: Энергия, 1979. -432 с.

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

8. О.А. Суханов, В.А. Тимофеев, Ш.С. Чандра // Электричество. 1997. - № 4.- С. 2-6.

9. Суханов О.А. Управление режимами электроэнергетических систем на основе принципов кибернетического моделирования. Экономия электроэнергии в электроэнергетических системах. / О.А. Суханов // Сб. научных трудов МЭИ.- 1988.-№ 187.-С. 104-109.

10. Распределенная обработка задач АСУТП дальнего транспорта газа /

11. А.Б. Бурцев, Е.Г. Волков, Н.В. Родина, и др. // Сб. научных трудов МЭИ. 1989. -№ 195.-С. 19-23.

12. Бурцев А.Б. Принципы организации противоаварийного управления электроэнергетическими системами с использованием параллельных вычислений / А.Б. Бурцев, И.И. Дзегеленок, С.В. Ковалёв // Электротехника.- 1996. -№9. С. 18-23.

13. Родина Н.В. Организация параллельных вычислений в распределённых управляющих системах: 05.13.15: дисс. . канд. техн. наук: /Н.В. Родина. -М.,1991,-173 с.

14. Fathi Е.Т. A distributed system for real-time applications / E.T. Fathi, E. Bose. // IEEE micro. 1987, - # 6, vol. 7. - P. 21 -28.

15. Абдулрадх О.А. Потенциальная эффективность метакомпьютерных вычислений для управления электроэнергетическими системами /

16. О.А. Абдулрадх, И.И. Дзегеленок. // Труды II международной конференции «Параллельные вычисления и задачи управления РАСО 2004». М.: Институт проблем управления им. В.А. Трапезникова, 2004. — С. 1104-1116.

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

18. Цимбал А.А. Технологии создания распределенных систем для профессионалов / А.А. Цимбал, M.JI. Аншина. СПб.: Питер», 2003. - 576 с.

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

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

21. Топорков В.В. Модели распределенных вычислений /В.В. Топорков.- М.: Физматлит, 2004. 320 с.

22. Кутепов В.П. Организация параллельных вычислений на системах / В.П. Кутепов. М.: Изд-во МЭИ, 1988. - 64 с.

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

24. Dally W. J. Network and processor architecture for message-driven computers / W.J. Dally; editors: R. Sauya, G. Birtwistle. VLSI and Parallel Computation. San Mateo, С A: Morgan Kaufmann, 1990.

25. Reed D. A. Multicomputer Networks: Message-Based Parallel Processing / D.A. Reed, R.M. Fujimoto. Cambridge, MA'.MIT Press, 1989.

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

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

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

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

30. Akl S. G. Parallel Computation Models and Methods / S. G. Akl. — Englewood Cliffs, NJ, Prentice-Hall, 1997.

31. ZomayaA. Parallel and Distributed Computing Handbook / A. Zomaya. McGraw-Hill, 1996.

32. Buyya R. High Performance Cluster Computing: Architectures and Systems / R. Buyya. Prentice Hall, 1999.

33. Валях E. Последовательно-параллельные вычисления / E. Валях; пер. с англ. -М.: Мир, 1985.-456 с.

34. Meliksetian D.S. Design and implementation of an enterprise grid. / D.S. Meliksetian II IBM Systems Journal. 2004 - #4, vol. 43.

35. MPI: A Message-Passing Interface Standard 1.1 Электронный ресурс.- Электрон, текстовые дан. — University of Tennessee, Knoxville, Tennessee, 1995.- Режим доступа: http://ww\v.mpi-forum.org/docs/mpi-l 1-html/mpi-report.html, свободный.

36. MPI-2: Extensions to the Message-Passing Interface Электронный ресурс.- Электрон, текстовые дан. — University of Tennessee, Knoxville, Tennessee, 1997.- Режим доступа: http://www.mpi-forum.org/docs/mpi-20-html/mpi2-report.html, свободный.

37. Шпаковский Г.И. Программирование для многопроцессорных систем в стандарте MPI / Г.И. Шпаковский, Н.В. Серикова. Минск.: БГУ, 2002. - 323 с.

38. Антонов А.С. Параллельное программирование с использованием технологии MPI. I А.С. Антонов. М.: Изд-во МГУ, 2004. - 71 с.

39. Корнеев В.Д. Параллельное программирование в MPI / В.Д. Корнеев.- Новосибирск: Изд-во СО РАН, 2000. 213 с.

40. Букатов А.А. Программирование многопроцессорных вычислительных систем / А.А. Букатов, В.Н. Дацюк, А.И. Жегуло. Ростов-на-Дону: ООО "ЦВВР", 2003. -208 с. (Многопроцессорные системы и параллельное программирование.)

41. MPI: The Complete Reference. / Marc Snir, Steve Otto, Steven Huss-Lederman, David Walker, Jack Dongarra. Cambridge, MA: MIT Press, 1996.

42. Средства параллельного программирования в ОС Linux / Р.Х. Садыхов, Л.П. Поденок, А.В. Отвагин, И.И. Глецевич, Д.А. Пынькин; под ред. Р.Х. Садыхова. Минск: ЕГУ, 2004. - 475 с.

43. PVM: Parallel Virtual Machine. A Users' Guide and Tutorial for Networked Parallel Computing/ Al Geist, Adam Beguelin, Jack Dongarra, Weicheng Jiang, Robert Manchek, Vaidy Sunder am. Cambridge, MA: MIT Press, 1993.

44. Grimshaw A.S. A philosophical and technical comparison of Legion and Globus. / Grimshaw A. S. II IBM Journal of Research and Development. — 2004 — Mar.

45. From Open Grid Services Infrastructure to WSResource Framework: Refactoring & Evolution Электронный ресурс. / К. Czajkowski, D. Ferguson, I. Foster, J. Frey,

46. S. Graham, T. Maguire, D. Snelling, S. Tuecke. Электрон, дан. - Режим доступа: http://www.globus.org/wsrf/specs/ogsitowsrfLO.pdf, свободный.

47. Появление нового ПО грид. Электронный ресурс.: GRIDCLUB.RU. Интернет-портал по (ТЛЮ-технологиям / Институт прикладной математики им. М.В. Келдыша РАН. — Электрон, дан. Режим доступа: http://gridclub.ru/practice/newsoftware.html, свободный.

48. Globus Toolkit Homepage. Электронный ресурс. / Globus Alliance, University of Chicago. Режим доступа: http://www.globus.org/toollcit/, свободный.

49. TORQUE Resource Manager Электронный ресурс. Cluster Resources Inc., 2004. - Электрон, дан. - Режим доступа:http://www.clusterresources.com/pages/products/torque-resource-manager.php, свободный.

50. Анпи П. Этот Grid — неспроста. Электронный ресурс. / Анни П. // Открытые системы. Электрон, журн. - 2003. - #1. - Режим доступа:http://www, osp. ru/os/2003/01/1824057, свободный.

51. Sun Grid Engine 6.1 Overview Электронный ресурс. / Sun Microsystems, Inc. — Электрон, дан. Режим доступа: http://www.sun.com/software/gridware/, свободный.

52. Топорков В.В. Декомпозиционные схемы синтеза стратегий планирования в масштабируемых системах. / В.В. Топорков // Изв. РАН Сер. Теория и системы управления. 2006. - № 1. - С. 82-93.

53. Топорков В.В. Потоковые и жадные алгоритмы согласованного выделения ресурсов в распределенных системах. / В.В. Топорков //Изв. РАН. Теория и системы управления. 2007. - № 2. - С. 109-119.

54. Котляров Д.В. Граф-схемное потоковое параллельное программирование и его реализация на кластерных системах. / Д.В. Котляров, В.П. Кутепов,

55. М.А. Осипов. // Теория и системы управления. — 2005, — №1.

56. Task allocation in distributed data processing I Wesley W Chu, Leslie J. Holloway, Min-Tsung I.an, andKemal Efe II IEEE computing. — 1980. — P. 57-69.

57. Коротаев K.C. Многоуровневый планировщик процессорного времени для групп процессов, обеспечивающий гарантии в обслуживании / К.С. Коротаев, П.В. Емельянов // Информационные технологии. — 2006. № 6. - С. 58-63.

58. Трубецкой А.И. Принципы построения модели распределенно-параллельных вычислений / А.И. Трубецкой, С.Г. Ермаков, Н.А. Шаменков // Информация и Космос 2006.-№1.

59. Ильин П.Е. Многозадачная территориально-распределенная вычислительная среда с учетом эффективности передачи данных / П.Е. Ильин // Вестник МЭИ.- 2008. №2. - М.: Изд-во МЭИ. - С. 95—99.

60. Ильин П.Е. Организация мультизадачного выполнения параллельных программ в территориально распределенной сети. / П.Е. Ильин, И.И. Дзегеленок , A.M. Титов // Сборник научных трудов: К 85-летию ВЭИ / Под ред. В.Д. Ковалева. -М.: ГУПВЭИ, 2006. С. 107-112.

61. Олифер Н.А. Компьютерные сети /Н.А. Олифер, В.Г. Олифер. СПб.: Питер, 2005.-804 с.

62. Митягин О.В. Распределенная обработка информации в системах диспетчерского контроля и управления / О.В. Митягин // Промышленные АСУ и контроллеры 2002. - №5.

63. Ильин П.Е. Декомпозиционный подход к осуществлению GRID-технологий / П.Е. Ильин, И.И. Дзегеленок, Ш.А. Оцоков и др. // Информационная математика. -2005,-№1 (5).-С. 110-119.

64. Ильин П.Е. Проект глобально-распределенной мультикомпьютерной среды для реализации декомпозиционных моделей управления. / П.Е. Ильин,

65. И.И. Дзегеленок // Труды III Международной конференции «Параллельные вычисления и задачи управления» РАСО'2006, Москва, 2—4 октября 2006 г. -М.: Институт проблем управления им. В.А. Трапезникова, 2006. С. 400-406.

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

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

68. Кузнецов А.Ю. Параллельные мультикомпьютерные сети как направление развития распределенных супер-ЭВМ / И.И. Дзегеленок, А.Ю. Кузнецов // Сб. "Системы управления и силовая электроника"; под общ. ред. В.Д. Ковалёва. -М.:ВЭИ, 2001.-С. 62-67.

69. Дзегеленок И.И. Разработка распределённой параллельной программы / ИИ. Дзегеленок, А.Ю. Кузнецов, Ю.В. Аляева. -М.:Изд-во МЭИ, 2002. 24 с.

70. ArenstorfN.S. Comparing barrier algorithms /Norbert S. Arenstorf, Harry F. Jordan//Parallel Computing. 1989. - #12. -P. 157-170.

71. Shun Yan Cheung. Performance of barrier synchronization methods in a multiaccess network" / Shun Yan Cheung, Vaidy S. Sunderam II IEEE transactions on parallel and Distributed systems. — 1995. — #8, vol 6.

72. Duato J. Interconnections networks :An Engineering approach / J. Duato, S. Yalamanchili, L.M. Ni. Los Alamitos, CA: IEEE CS Press, 1997.

73. Абдулрадх О.А. Эффект барьерной синхронизации параллельных вычислений. / О.А. Абдулрадх. // Сб. научных докладов МФИ-2002. М.: Изд-во МЭИ, 2002. - С. 58-62.

74. Роджерсон Д. Основы COMI Дейл Роджерсон. -М.: Русская Редакция, 2000. -400 с.

75. Жуков А. Изучаем Delphi / А. Жуков. СПб.: Питер, 2001. - 352 с.

76. Тейбор Р. Реализация XML Web-служб на платформе Microsoft .NETI Роберт Тейбор. М.: Вильяме, 2002. - 464 с.

77. Петзолд Ч. Программирование для Windows ® 95: в 2 т. / Чарльз Петзолд.- СПб.: BHV-Санкт-Петербург, 1997. 752 е., ил.

78. Абдулрадх О.А. Исследование эффективности мультикомпьютерных систем с использованием декомпозиционной модели организации распределенных вычислений: 05.13.15: дис. канд. техн. наук / О.А. Абдулрадх. -М., 2005. -206 с.

79. Отчет ВЭИ о НИР «Создание иерархических алгоритмов функционального моделирования для управления энергетическими системами» / Научный руководитель, д.т.н. В.Д. Ковалев (гос. per. №01200305827). -М: ВЭИ, 2003.

80. Веников В.А. Электрические системы электрические сети / В.А. Веников, В.А. Строев //- М: Высшая школа, 1998.

81. Автоматизация управления энергообъединениями / В.В. Гончуков,

82. В.М. Горинштейн, JI.A. Крумм и др.; под ред. С. А. Совалова. -М.: Энергия, 1979. -432 с.

83. Бятец B.C. Расчеты установившихся электрических режимов сложных энергосистем при эквивалентировании исходной схемы до заданного-объема / B.C. Бятец. Киев: Науков думка, 1979.

84. Воропай Н.И. О проблеме эквивалентирования при построении математических моделей / Н.И. Воропай. Иркутск: СЭИ СО АН СССР, 1970.

85. Веников В.А. Кибернетические модели электрических систем / В.А. Веников, О.А. Суханов. -М.: Энергоиздат, 1982.

86. Soukhanov О.А. Application of functional modeling to the solution of power system optimization problems. / O.A. Soukhanov, S. C. Shil II Electrical power & energy systems. 2000. - #22. - P. 119-127.

87. Суханов O.A. Управление режимами электроэнергетических систем на основе принципов кибернетического моделирования, Экономия электроэнергии в электроэнергетических системах / О.А. Суханов // Сб. научных трудов МЭИ.- 1988.-№ 187.-С. 104-109.

88. Арзамасцев Д.А. АСУ и оптимизация режимов энергосистем: учеб. пособие для студентов / Д.А. Арзамасцев, П.И. Бартоломей, A.M. Холян; под ред.

89. Д.А. Арзамасцева. М.: Высшая школа. - 1983. - 208 с.

90. Методы оптимизации режимов энергосистем / В.М. Горинштейн, Б.П. Мирошниченко, А.В. Пономарев и др.; под ред. В.М Горнштейна. -М.: Энергия. 1981.-336 с.

91. Open MPI: Open Source High Performance Computing Электронный ресурс.- Open MPI Team, 2004. Электрон, дан. - Режим доступа: http://www.openmpi.org, свободный.