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

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

Абдулрадх Одай Абдуллатиф

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

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

АВТОРЕФЕРАТ

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

Москва - 2005

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

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

Дзегеленок Игорь Игоревич

Официальные оппоненты: доктор технических наук, профессор,

заслуженный деятель науки РФ Мамзелев Игорь Александрович

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

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

Московская государственная академия

приборостроения и информатики, г. Москва

Защита состоится «17» июня 2005 г. в 16 час. 00 мин. на заседании Диссертационного совета Д 212.157.01 при Московском энергетическом институте (Техническом университете) по адресу: 111250, г. Москва, ул. Красноказарменная, д. 13 (ауд. М704).

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

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

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

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

Диссертационного совета Д 21 ¡Г.Г*1"""

к. т. н., профессор

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

Актуальность темы.

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

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

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

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

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

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

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

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

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

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

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

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

Основные задачи диссертационного исследования.

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

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

• Аналитическое исследование эффективности ПМК-сетей в зависимости от структурно-топологических характеристик декомпозиционной модели и параметров вычислительной среды.

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

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

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

декомпозиционных моделей, методы анализа электрических сетей, методы линейной алгебры, теория оптимизации, языки программирования. Для проверки эффективности предложенных принципов организации вычислений использовался действующий макет параллельной мультикомпьютерной сети КУРС-2000, разработанный на кафедре Вычислительных машин, систем и сетей (ВМСиС) МЭИ (ТУ), а для проверки достоверности результатов - программы MathCAD и Electronic Workbench.

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

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

2. Получено семейство аналитических оценок потенциальной эффективности ПМК-сетей в зависимости от структурно-топологических характеристик декомпозиционной модели и параметров вычислительной среды;

3. Определенны варианты организации ПМК-сети, предусматривающие согласованное масштабирование вычислительного ресурса.

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

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

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

3. Работоспособность и высокая эффективность декомпозиционной модели организации вычислений подтверждена экспериментально в результате программной реализации метода декомпозиционных эквивалентов на действующем макете ПМК-сети «КУРС-2000», а также на примере анализа применимости модели для фрагмента ЭЭС Ирака.

4. Полученные результаты нашли применение на практике. Так, материалы, содержащие рекомендации по компьютерной реализации декомпозиционных моделей управления ЭЭС, включены в отчет государственного научного центра Всероссийского электротехнического института (гос. per. №01200305827). Методика проведения натурного эксперимента на ПМК-сети с использованием разработанной распределённой параллельной программы использована на кафедре ВМСиС МЭИ (ТУ) при выполнении госбюджетной НИР (гос. per. №1200001482) и в учебном процессе. Практикум по освоению метода декомпозиционных эквивалентов принят в эксплуатацию и установлен на сервере МЭИ (ТУ) (http: / /twt. mpei .ac.ru /MAS /worksheets /others

/CREAT EQUI CCT DBE.mcd). Отмеченные результаты подтверждены официально соответствующими актами.

Апробация работы. Отдельные результаты и положения диссертационной работы докладывались и обсуждались на научно-технических семинарах научной группы и кафедры ВМСиС, на международных форумах информатизации МФИ-2002 и МФИ-2003 «Информационные средства и технологии» и международной научно-технической конференции РАСО'2004 «Параллельные вычисления и задачи управления».

Публикации. Основное содержание диссертационной работы отражено в 11 публикациях, в том числе 2- в электронном журнале.

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

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

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

В ПЕРВОЙ ГЛАВЕ рассматриваются недостатки централизованного подхода к управлению сложными объектами и показана необходимость децентрализованного управления, практическое осуществление которого требует разработки новых методов и алгоритмов. Перспективный путь в этом направлении заключается: во-первых, в переходе от последовательных к параллельным вычислениям, во-вторых, в переходе от централизованной к распределенной иерархической организации вычислений.

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

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

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

Рисунок 1. Среда для организации распределенных вычислений

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

Основной моделью выполнения распределенной параллельной программы на ПМК-сети является модель передачи сообщений.

Существуют три основных варианта организации распределенных параллельных вычислении:

- параллельная обработка. Все исходные данные появляются на центральном вычислителе в центре обработки данных (ЦОД), далее центральный вычислитель распределяет данные между локальными вычислителями в локальные центры (ЛЦ). На всех вычислителях происходит обработка распределенных данных. Обработанные данные собираются на центральном вычислителе.

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

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

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

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

♦ недостаточный параллелизм (insufficient parallelism);

♦ разбалансировка нагрузки процессоров (load unbalancing);

♦ синхронизация процессоров (processor synchronization);

♦ коммуникации (communications).

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

Представлены основные показатели эффективности реализации распределенных параллельных программ, среди которых:

ЦОД.

ЭЭС).

центр

распр

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

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

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

ВО ВТОРОЙ ГЛАВЕ рассматривается декомпозиция решаемых задач как основной принцип повышения эффективности распределенных параллельных вычислений при решении задач большой размерности.

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

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

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

♦ распределенность исходных данных;

♦ крупноблочностъреализуемыхпрограмм;

♦ однородность распределения данных по ветвям;

♦ регулярность структуры обменов.

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

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

Конструктивным воплощением этой модели является разработанный автором метод декомпозиционных эквивалентов.

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

Нижний уровень обеспечивается вычислительными системами локальных центров, а верхний уровень - вычислительной системой главного центра управления (ГЦУ).

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

" Отметим два способа представления эквивалентной схемы. В предлагаемом методе используется эквивалентная схема, состоящая из источника напряжения (УШ) и комплексного сопротивления ^Ш).

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

где п-число граничных узлов, значения напряжения загруженных гра-

ничных узлов.

Процесс вычисления а^О^ъП, происходит следующим образом:

1) вычисляется ао^ путем "соединения" всех граничных узлов с базовым узлом, кроме узла к, который не соединяется не с каким узлом. Значение а0к равно значению напряжения узла к.

2) определяются а,^, 0<1<п, путем "соединения" всех граничных узлов с базовым узлом, кроме узлов к и 1, которые не соединяются не с каким узлом. Затем необходимо определить напряжения узлов к и 1. Значение а,^ вычисляется следующим образом:

Для определения достаточно вычислить один из Ь,^.

(5)

(6)

Процесс вычисления " , происходит следующим образом:

1) вычисляется Ь0к путем "соединения" всех граничных узлов с базовым узлом. Значение Ь0к равно значению тока, протекающего между к -ым и базовым узлами.

2) вычисляются Ьу(, 0<1<п, путем соединения всех граничных узлов с базовым узлом, кроме узла ^ который не соединяется не с каким узлом. Затем необходимо определить значения напряжения узла i и тока, протекающего между к -ым и базовым узлами. Значение Ь ^ вычисляется следующим образом:

После построения эквивалентных схем подсети, локальный центр передает значения УШ и Zth каждого граничного узла в ГЦУ.

Вторая стадия алгоритма начинается в ГЦУ после получения всех значений У(Ь и Zth со всех граничных узлов сети. При осуществлении данной стадии строится простая обобщенная абстрактная модель замещения всей сети. Исходя из этой модели, решается система линейных уравнений для того, чтобы найти напряжения в граничных узлах. Число линейных уравнений равно половине числа граничных узлов. После вычисления значений напряжения в граничных узлах, ГЦУ передает полученные значения локальным центрам.

Рисунок 2. Схема реализации метода декомпозиционных эквивалентов

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

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

(в нашем случае ЭЭС) и параметров вычислительной среды, определяемое следующим выражением:

(8)

где Тор - время выполнения одной операции в [с];

Укан - скорость канала связи в [бит/с];

N число определяемых подсистем;

*яШах " наибольшее число внутренних узлов подсистемы; - максимальное число граничных узлов подсистем.

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

ла подсетей (подсистем) ¡У=3,4, 5. Как видно из рисунка, существует некоторое "критическое" число узлов, начиная с которого достигает наибольшей величины и далее асимметрически приближается к насыщению, когда

Eff -

~ _N_

т +т+1

(9)

/ / --- --- 5 подсш тем

/ / 4 подсш темы

1 .• I . tf 3 подсш темы

□ 20 40 60 80 1Ш

Число узлов

Рисунок 3. Зависимость эффективности от числа узлов ЭЭС

На рисунке 4 представлено семейство зависимостей Еff=f(T0P, оттах) при задании тшах={100, 200, 400}; Укаи=12 Кбит/с; Лтшг^; N=4. Из полученных графиков видна тенденция резкого увеличения Uff при уменьшении времени выполнения арифметических операций.

'исунок 4. Зависимость эффективности от скорости выполнения арифметических

операций

На рисунке 5 представлено семейство зависимостей Шш>) ПРИ

задании 100, 200, 400}; Т^Ю"6; ИтаХ=4; N=4 для различных скоростей

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

Î ! i

\ | 400 узлов

i V ■ \ 7\ 200 узлов

\ / ~ 100 узлов

V

------- ---

шо 400 боо an lirai

Скорость пики сипи 1 бет/с

Рисунок 5.3ависимость эффективности от скорости канала связи

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

со

П>

¡э К Л о а х се о

3

Рисунок 6. Соответствие «метод декомпозиции- архитектура вычислительных систем»

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

В ТРЕТЬЕЙ ГЛАВЕ рассматриваются возможности дальнейшего повышения эффективности распределенных вычислений с использованием декомпозиционной модели.

Идеологии распределенных вычислений, обеспечивающих решение задач управления в реальном масштабе времени, в наибольшей степени отвечает схема МШ (по классификации М.Флинна). Вместе с тем для задач управления характерно многократное применение одних и тех же алгоритмов к различным потокам исходных данных. Этому требованию в наибольшей степени удовлетворяет идеология объединения вычислительных модулей в конвейерные вычислительные системы (схема MISD). Логическое тактирование вычислений ориентировано на решение таких задач, когда на вход системы периодически поступают непрерывные исходные данные. Тогда можно организовать их муль-тиконвейерную обработку. Мультиконвейерность заключается в том, что на каждом такте работы системы в нее поступают новые задания и обрабатываются конвейером, состоящим из нескольких ступеней. Но в отличие от привычного конвейера, где каждой ступени соответствует одно вычислительное устрой-

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

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

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

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

Непосредственное применение метода декомпозиционных эквивалентов не дает ожидаемого эффекта по следующим причинам:

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

2. Времена выполнения слоев конвейера различны, поэтому конвейер является несбалансированным.

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

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

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

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

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

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

-Иерархически-параллельный способ преобразования конвейера Данный способ является усовершенствованием гибридного способа. Он основан на том факте, что на одном уровне иерархии расчета установившегося режима можно вычислять коэффициенты уравнений (2) и (3) параллельно и независимо друг от друга. На рисунке 7 представлена иллюстрация данного способа.

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

(10)

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

Рисунок 7. Схема расчета установившегося режима ЭЭС с использованием иерархически-параллельного способа преобразования конвейера

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

250 Число звдач

Рисунок 8. Зависимость Е(Г от кратности решаемых задач для простого способа преобразования конвейера

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

125Э

Й 1008

75& 500 25»

и 1-й спо соб —

-^ \

у.- 3 и спос об -

У

! /

/' /'

( -Р— 2-й способ

н—

Г 1.... .

1

1000

500

Число задач

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

В ЧЕТВЕРТОЙ ГЛАВЕ рассматривается методика регламентирования процесса проведения экспериментальных исследований по определению преимуществ декомпозиционного подхода к практическому осуществлению параллельных распределенных вычислений (рисунок 10).

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

кннрп таЫШЩШшт

Определение аппарашых и программных средств

Рисунок 10. Обобщенная схема предлагаемой методики

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

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

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

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

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

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

4. Результат Eff > N, где JV-число вычислителей, подтверждает, что декомпозиционная модель вносит дополнительный «математический» вклад в ускорение, наряду с эффектом "чисто" параллельных вычислений. С увеличением числа узлов в электрической сети выявленные зависимости асимптотически стремятся

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

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

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

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

8. Полученные результаты нашли применение на практике. Так, материалы, содержащие рекомендации по компьютерной реализации декомпозиционных моделей управления ЭЭС, включены в отчет государственного научного центра Всероссийского электротехнического института (гос. per. №01200305827). Методика проведения натурного эксперимента на ПМК-сети с использованием разработанной распределённой параллельной программы использована на кафедре ВМСиС МЭИ (ТУ) при выполнении госбюджетной НИР (гос. per. №1200001482) и в учебном процессе. Практикум по освоению метода декомпозиционных эквивалентов принят в эксплуатацию и установлен на сервере МЭИ (ТУ) (http://www.mpei.ac.ru/MAS/worksheets/others

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

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

1. Oday A.L.A. Ridha, Titov V.S., Zotov I.V. Distributed hardware-level model for barrier synchronization in multiprocessor system // 5-я международная конференция «Распознавание-2001»: Тез. докл. - Часть II. Курск, 2001. - С. 203205.

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

3. Абдулрадх О.А. Аппаратная поддержка барьерной синхронизации параллельных процессов // Сб. тр. 9-й международной конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика». М.: МЭИ, 2003.-С.314-316.

" 4. Абдулрадх О.А. Метод декомпозиционных эквивалентов для управления электроэнергетическими системами // Сб. тр. МФИ-2003, Международный форум информатизации 2003. Информационные средства и технологии. М.: МЭИ, 2003. - С. 45-48.

5. Дзегеленок И.И., Абдулрадх О.А. Эффективность реализации декомпозиционной модели на ПМК-сети // Сб. тр. МФИ-2003, Международный форум информатизации 2003. Информационные средства и технологии. М.: МЭИ, 2003. - С. 95-98.

6. Абдулрадх О.А. Варианты конвейеризации процессов расчета установившегося режима электроэнергетических систем // Сб. тр. 11-й международной конференции студентов и аспирантов «Радиоэлектроника, электротех-

- ника и энергетика». М.: МЭИ, 2005. - С. 366-367.

7. Абдулрадх О.А. Распределенно-параллельный метод для вычисления расчета установившегося режима электрической сети // Сб. тр. 10-й международной конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика». М.: МЭИ, 2004. - С. 356-357.

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

9. Дзегеленок И.И., Абдулрадх О.А. Эффективность метода декомпозиционных эквивалентов, реализуемого на параллельной мультикомпьютерной сети / Электронный журнал «Вычислительные сети»: Теория и практика, 2003, № 1(3), http://network-journal.mpei.ac.ru.

10. Абдулрадх О.А. Сетевая модель расчета установившегося режима в электроэнергетических системах / Электронный журнал «Вычислительные сети»: Теория и практика, 2003, № 1(3), http://network-journal.mpei.ac.ru.

11. Дзегеленок И.И., Оцоков Ш.А., Абдулрадх О. А., Ильин П.Е. и Ильин И. В. «Декомпозиционный подход к осуществлению GRID-технолог^р» х

/ «Информационная математика». М.: АСТ-физико-математическая ли^ераира; \

2005, №1(5). - С. 139-149. О 9 ИЮЛ 2005'" vJ^A а

Подписано в печать^. ШГ, Зак. (93 Тир. 7СО Пл. -f, 2,6 /

Полиграфический центр МЭИ (ТУ) \ ^Dfrry

СПИСОК ОСНОВНЫХ СОКРАЩЕНИЙ И ОБОЗНАЧЕНИЙ.

ВВЕДЕНИЕ.

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

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

1.2. Модели и языки параллельного программирования.

1.2.1. Модель передачи сообщений (MPI).

1.2.2. Модель параллелизма по данным (HPF).

1.2.3. Гибридная модель параллелизма по управлению с передачей сообщений (OpenMP+MPI).

1.2.4. Модель параллелизма по данным и управлению (DVM).

1.2.5. Модель КУРС-2000.

1.3. Технологии созданий распределенных параллельных приложений.

1.4. Проектирование распределенных параллельных алгоритмов.

1.5. Средства распределенного параллельного программирования.

1.6. Схема управления распределенным объектом (на примере ЭСС).

1.7. Показатели эффективности реализации распределенных программ.

1.8. Цели и задачи проводимого исследования.

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

ГЛАВА 2. РАЗРАБОТКА ДЕКОМПОЗИЦИОННОЙ МОДЕЛИ ПРОБЛЕМНОЙ СРЕДЫ.

2.1. Декомпозиционный подход к повышению эффективности управления распределенным объектом.

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

2.2.1. Декомпозиция алгоритма оптимизации по "шагам".

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

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

2.3. Разработка декомпозиционной модели.

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

2.3.2. Обобщение метода Тевенена для решения задачи расчета установившегося режима ЭЭС.

2.4. Оценка эффективности реализации декомпозиционной модели.

2.5. Сравнительный анализ методов декомпозиции.

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

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

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

3.2. Организация мультиконвейерных вычислений (на примере схемы расчета установившегося режима ЭЭС).

3.2.1. Простой способ преобразования конвейера.

3.2.2. Иерархический способ преобразования конвейера.

3.2.3. Гибридный способ преобразования конвейера.

3.2.4. Иерархически-параллельный способ преобразования конвейера.

3.3. Анализ эффективности рассмотренных способов организации мультиконвейерных вычислений.

3.3.1. Эффективность 1-го способа организации вычислений.

3.3.2. Эффективность 2-го способа организации вычислений.

3.3.3. Эффективность 3-го способа организации вычислений.

3.3.4. Эффективность 4-го способа организации вычислений.

3.4. Сравнительный анализ вариантов организации мультиконвейерных вычислений.

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

ГЛАВА 4. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ И ПРИМЕНЕНИЕ РАЗРАБОТАННЫХ МОДЕЛЕЙ И ПРОГРАММНЫХ СРЕДСТВ.

4.1. Методика экспериментального подтверждения ожидаемой эффективности реализации декомпозиционных моделей.

4.2. Программная реализация метода декомпозиционных эквивалентов.

4.2.1 .Локальная реализация на сервере МЭИ.

4.2.2. Реализация в виде распределенной параллельной программы.

4.3. Подтверждение работоспособности декомпозиционной модели (на примере фрагмента ЭЭС Ирака).

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

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

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

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

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

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

Распределенные параллельные вычисления в настоящее время представляют собой одну из наиболее передовых концепций в области решения задач большого объема [1-3].

Использование вычислительных сетей (ВС) для достижения указанной цели не представляется возможным, так как ВС обеспечивает лишь преимущественно информационное взаимодействие вычислителей [4-7]. Перспективным для реализации компьютерной поддержки распределенного управления в этом случае является использование нового класса вычислительных систем - параллельных вычислительных сетей (ПВС) [8-10]. ПВС сочетают положительные свойства локальных вычислительных сетей и параллельных вычислительных систем, открывают значительно более широкие возможности для распределенного децентрализованного управления прежде всего за счет глубокой координации взаимодействия удаленных вычислителей.

Переход к распределенности приводит к возрастанию важности проблемы связи вычислителей с точки зрения общего числа обменов, объемов передаваемой информации и вида структуры обменов. Кардинальное решение отмеченной проблемы возможно лишь на основе изучения "глубинных" свойств решаемых задач, определяющих условия их декомпозиции на подзадачи на уровне математических методов. Для того, чтобы действительно осуществить эту концепцию требуется создание новых математических моделей и соответствующих параллельных алгоритмов. Магистральным направлением развития распределенных параллельных вычислений являются методы декомпозиции проблемных сред [4, 11-17].

В задачах управления характерно многократное применение одних и тех же алгоритмов к различным потокам исходных данных. Этому требованию в наибольшей степени удовлетворяет идеология объединения вычислительных модулей в конвейерные вычислительные системы (схема мгао). Объединить различные схемы реализации параллельных вычислений в рамках единого подхода позволяет мультиконвейерная технология вычислений (МКТВ). МКТВ является достаточно общей формой структуризации вычислительного процесса, основывается на развитии и уточнении модели коллектива вычислителей [5-7].

Конвейеризация задачи на макро уровне позволяет упростить организацию вычислительного процесса, обеспечить высокую производительность. Но чтобы обеспечить отмеченные преимущества при организации любого конвейерного вычисления, важнейшую роль играет балансировка его стадий. Эффективным является сбалансированный конвейер. Балансировка заключается в разделении на равные по времени стадии [18-22].

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

ОБЪЕКТОМ ИССЛЕДОВАНИЯ является класс мультикомпьютерных систем в виде ^параллельных^) мультикомпьютерных сетей (ПМК-сетей), предусматривающих согласованное взаимодействие в общем случае удаленных вычислителей, осуществляющих обработку данных по месту их возникновения.

ПРЕДМЕТ ИССЛЕДОВАНИЯ. Поиск закономерностей повышения эффективности ПМК-сетей различной конфигурации в зависимости от структурно-топологических характеристик декомпозиционной модели организации распределенных вычислений.

ЦЕЛЬ ДИССЕРТАЦИОННОЙ РАБОТЫ заключается в определении вариантов организации и эффективного применения параллельных мультикомпьютерных сетей, проблемно-ориентированных на решение объемных задач, допускающих возможность декомпозиции.

ОСНОВНЫЕ ЗАДАЧИ ДИССЕРТАЦИОННОГО ИССЛЕДОВАНИЯ.

1) Анализ принципов декомпозиции объемных задач для обеспечения управления сложными территориально-распределенными объектами.

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

3) Аналитическое исследование эффективности ПМК-сетей в зависимости от структурно-топологических характеристик декомпозиционной модели и параметров вычислительной среды.

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

5) Подтверждение работоспособности разработанных методов и средств на примерах решения модельных задач, включая натурные испытания на действующем макете ПМК-сети.

МЕТОДЫ ИССЛЕДОВАНИЯ. В диссертации используются методы системного анализа, основные положения теории параллельного программирования, принципы организации сетевых распределенных вычислений, методы построения декомпозиционных моделей, языки программирования, методы анализа электрических сетей, линейной алгебры, теории оптимизации. Для проверки эффективности предложенных принципов организации вычислений использовался макет параллельной мультикомпьютерной сети КУРС-2000, разработанный на кафедре Вычислительных машин, систем и сетей (ВМСиС)

МЭИ (ТУ), а для проверки достоверности результатов - программы MathCAD и Electronic Workbench.

НАУЧНАЯ НОВИЗНА работы заключается в следующем: . /

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

2) Определены варианты организации ПМК-сети, предусматривающие согласованное масштабирование вычислительного ресурса;

3) Получено семейство аналитических оценок потенциальной эффективности ПМК-сети в зависимости от структурно-топологических характеристик декомпозиционной модели и параметров вычислительной среды.

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ п олученных результатов заключается в следующем:

1. Проведено сопоставление возможных подклассов мультикомпьютерных систем рассмотренным методам осуществления декомпозиционной модели (на примере РУР ЭЭС) с точки зрения эффективности её реализации по введённому показателю качества.

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

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

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

5. Полученные результаты нашли применение на практике. Так, материалы, содержащие рекомендации по компьютерной реализации декомпозиционных моделей управления ЭЭС, включены в отчет государственного научного центра Всероссийского Электротехнического института (гос. per. №01200305827). Методика проведения натурного эксперимента на ПМК-сети с использованием разработанной распределённой параллельной программы использована на кафедре ВМСиС МЭИ при выполнении госбюджетной НИР (гос. per. №1200001482) и в учебном процессе. Практикум по освоению метода декомпозиционных эквивалентов принят в эксплуатацию и установлен на сервере МЭИ (http://twt.mpei.ac.ru/MAS/worksheets/others/CREATEQUICCTDBE.mcd). Отмеченные результаты подтверждены официально соответствующими актами.

АПРОБАЦИЯ РАБОТЫ. Отдельные результаты и положения диссертационной работы докладывались и обсуждались на научно-технических семинарах научной группы и кафедры ВМСиС, на международных форумах информатизации МФИ-2002 и МФИ-2003 «Информационные средства и технологии» и международной научно-технической конференции РАСО'2004 «Параллельные вычисления и задачи управления».

НАУЧНЫЕ ПУБЛИКАЦИИ. Основные результаты отражены в 13 работах, в том числе в 11 печатных работах и отчетах о НИР (гос. регистрации № 01200001482 и №001200305827). Остальные представлены в виде 2 публикаций в электронном журнале «Вычислительные сети».

СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИИ

Диссертационная работа состоит из введения, 4 глав, заключения, списка литературы и приложения. Она изложена на 142 страницах основного машинописного текста, содержит 40 рисунков, 1 таблицу, включает библиографию из 113 наименований. Общий объем диссертации составляет 206 страниц.

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

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

2. Проведенные оценки возможной эффективной реализации декомпозиционной модели на ПМК-сети на примере РУР фрагмента ЭЭС Ирака Проведенное сопоставление расчета по декомпозиционной модели и «на прямую» подтверждает целесообразность предлагаемого способа организации вычисления.

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

4. Высокая эффективность программной реализации метода декомпозиционных эквивалентов подтверждена экспериментально на действующем макете ПМК -сети «КУРС-2000».

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

МЭИ (http://twt.mpei.ac.ru/MAS/worksheets/others/CREATEQUICCTDBE.mcd), что подтверждено официально соответствующими актами.

ЗАКЛЮЧЕНИЕ

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

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

2. Краткий обзор тенденций осуществления и развития компьютерных систем и технологий, в частности CORBA, .NET, и J2EE, позволяет сделать вывод, что в обозримом будущем одним из важнейших требований к разрабатываемым методам и алгоритмам будет определение необходимости реализации распределенных параллельных вычислений в пределах глобальной сети. Этому требованию отвечает приведенное определение ПМК-сети.

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

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

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

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

7. Результат Е// > N. где //-число вычислителей, подтверждает, что декомпозиционная модель вносит дополнительный «математический» вклад в ускорение, наряду с эффектом "чисто" параллельных вычислений. С увеличением числа узлов в электрической сети выявленные зависимости асимптотически стремятся т.е., ускорение зависит лишь от топологии декомпозиционной модели ЭЭС. Кроме того, еще вклад в ускорение, может быть, достигнут на относительно медленных компьютерных сетях за счет сокращения передаваемых данных.

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

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

10. Рассмотрены возможные варианты организации мультиконвейерных систем, обеспечивающих повышенную эффективность реализации метода декомпозиционных эквивалентов ( Е#5>1) в зависимости от вида исходных данных решаемых задач и параметров вычислительной среды.

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

12. Проведена оценка возможной эффективной реализации декомпозиционной модели на ПМК-сети на примере РУР фрагмента ЭЭС Ирака Проведенные сопоставление расчета по декомпозиционной модели и «на прямую» подтверждает целесообразность предлагаемого способа организации вычисления.

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

14. Высокая эффективность программной реализации метода декомпозиционных эквивалентов подтверждена экспериментально на действующем макете ПМК-сети «КУРС-2000».

15. Полученные результаты нашли применение на практике: материалы, содержащие рекомендации по компьютерной реализации декомпозиционных моделей управления ЭЭС включены в отчет ВЭИ (№ гос. per. №01200305827), использованы при выполнении госбюджетной НИР и в учебном процессе кафедры ВМСиС МЭИ (ТУ) (гос. per. №1200001482), практикум по освоению метода декомпозиционных эквивалентов принят в эксплуатацию и установлен на сервере МЭИ (ТУ) (http://twt.mpei.ac.ru/MAS/worksheets/other^CREATEQUICCTDBE.mcd), что подтверждено официально соответствующими актами.

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

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

2. Цимбал A.A., Аншина М. Л «Технологии создания распределенных систем» . Для профессионалов. -СПб.:Питер, 2003. -576 с. ^^

3. Управление в распределенных системах, Сб. статьи, -М.: Наука, 1993, -170 с.

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

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

6. Прангишвили И.В., Подлазов B.C., Стецюра Г.Г. Локальные микропроцессорные вычислительные сети. -М.: Наука 1984. -с.

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

8. Афанасьев А. В., Вигуль В. А. и др. Особенности локальных вычислительных сетей, используемых в распределенных системах управления процессами// Тез. 15 Всесоюзной шк.-сем. По вычислительным сетям, ч.З, -М.:Л, 1990. с.263-268.

9. Гаврилов A.C., Тюленева Л. А. Проектирование и реализация тактируемой локальной сети // Тез. 15 Всесоюзной шк.-сем. По вычислительным сетям, ч.1,-М.:Л, 1990. с.181-185.

10. Желнов О.В., Бастов A.M. и др. Организация межпрограммной связи в локальных вычислительных сетях персональных ЭВМ. // Тез. 15 Всесоюзной шк.-сем. По вычислительным сетям, ч.1,-М.:Л, 1990. с.191-196.

11. Абдулрадх O.A. Метод декомпозиционных эквивалентов для управления электроэнергетическими системами / Сб. научных докладов «информатизации МФИ-2003». М.: Издательство МЭИ, 2003, с. 45-48.

12. Дзегеленок И.И., Абдулрадх O.A. Эффективность реализации декомпозиционной модели на ПМК-сети,/ Сб. научных докладов «информатизации МФИ-2003». М.: Издательство МЭИ, 2003, с. 95-98.

13. Габриэль Крон, «Тензорные анализ сетей», перевод с английского, под редакцей JI.T. Кузина и П.Г. Кузнецова, М.: Советское радио, 1978, -719 с.

14. Гераский О.Т. Декснис Г.К. Декомпозиция большой электроэнергетической системы и выбор формы уравнений установившихся режимов при реализация итерационного метода Ньютона-Рофсона.// известия латвийской АН, серия физич. Технич. Наук. 1990, № 4.

15. Шамаева О.Ю. Разработка методов и организация процессов параллельных вычислений для задач большой размерности на основе диакоптических принципов декомпозиции/ Дисс. на соиск. уч. ст. к.т.н.- М.:МЭИ, 1990,-295 с.

16. Дзегеленок И.И., Оцоков Ш.А., Абдулрадх О. А., Ильин П.Е., и Ильин И. В. «Декомпозиционный подход к осуществлению GRID-технологий», ж.

17. Информационная математика», М.:Издательство АСТ-физико-математическая литература, 2005, №1(5), с. 139-149.

18. Дзегеленок И.И. Мультиконвейерные вычислительные системы на базе микро ЭВМ-М.: Моск.энерг. ин-т, 1985.-60 с.

19. Дзегеленок И.И., Кондрат A.B. Организация программируемых обменов мультиконвейерных системах. В кн. «конвейерные ВС». Тез. докл. Всесоюзного НТ совещаная, Киев, 1988. -с. 67.

20. Дзегеленок И.И., Волков Е.Г., Якуба Н.В. и др. Режимы параллельной обработки информации в мультиконвейерных ВС // 5-ая всесоюзная шк. сем. «распараллеливание обработки информации РОИ-85», Тез. докл. и сообщ. ч.З. Львов, 1985. с.247-248.

21. Дзегеленок И.И., Бурцев А.Б., Якуба Н.В. и др. Регуляризация взаимодействия микро-ЭВМ вычислительных системах конвейерного типа // Сб. научных трудов №151, -М.: Моск. Энерг. Ин-т, 1987. с36-46.

22. Абдулрадх O.A. Сетевая модель расчета установившегося режима в электроэнергетических системах, Электронный журнал Вычислительные сети, теория и практика, 2003, № 1(3), http://network-journal.mpei.ac.ru.

23. Миренков H.H. Параллельное программирование для многомодульных вычислительных систем. М.: Радио и связь. 1989. - 320с.

24. Soukhanov О.А, Shil S.C., Application of functional modeling to the solution of power system optimization problems, Electrical power & energy systems, № 22, 2000, p. 119-127.

25. Суханов O.A. Тимофеев B.A., Чандра Ш.С. Применение принципов функционального (кибернетического) моделирования для решения задач управления и проектирования электрических систем., Электричество, № 4, 1997, с. 2-6.

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

27. Бурцев А.Б., Волков Е.Г., Родина Н.В., и др. Распределенная обработка задач АСУТП дальнего Транспорта газа .// Сб. научных трудов №195, -М.: Моск. Энерг. ин-т, 1989. с19-23.

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

29. Дзегеленок И.И., Барабанова Ю.В., Корлякова М.О.Определение параметров параллельной компьютерной сети /Вопросы радиоэлектроники.

30. Серия"Электронно-вычислительная техника (ЭВТ)".-М.: Изд-во НИИ им.М.А.Карцева, 1999, с.20-25.

31. Дзегелёнок И.И. Кузнецов А.Ю. Параллельные мультикомпьютерные сети как направление развития супер-ЭВМ/.

32. Walker D.W. The design of a standard message-passing interface for distributed memory concurrent computers // Parallel Computing. 1994 - Vol. 20(4), pp. 657-673.

33. Материалы на сайте www.parallell.ru

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

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

36. Кораблин Ю.П. Методические указания по курсу «структуры вычислительных машин и вычислительных систем», параллельная и распределенная обработка информации. -М.:, 1989.

37. Дзегеленок И.И., Климов Ю.Н., Кондарт А.В. Архитектура параллельной сети «КУРС-90»// Тез.док. 15 Всесоюзной шк.-сем. По вычислительным сетям, ч.1, -М.:Л, 1990, с. 19-24.

38. Дзегеленок И.И., Кондрат А.В., Родина Н.В. Архитектура локальной сети микро-ЭВМ для испытания параллельных программ V Сб. научных трудов №154, -М.: Моск. Энерг. Ин-т, 1988. с20-23.

39. Крюков В.А., Разработка параллельных программ для вычислительных кластеров и сетей //Информационные технологии и вычислительные системы, 2003, №1-2, с. 42-59.

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

41. Системы параллельной обработки: пер. от английского / Под редакцией Д. Ивенса. -М.: Мир 1985. -416 с.

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

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

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

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

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

47. Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar, Introduction to Parallel Computing, Second Edition, Addison Wesley, 2003, c. 856.

48. Ian Foster, Bill Gropp, Carl Kesselman, Charles Koelbel, "Designing and Building Parallel Programs", Addison-Wesley, URL http://www.mcs.anl.gov/dbpp/, 1995.

49. Angus I., G. Fox C., Kim J., and Walker D. W. Solving Problems on Concurrent Processors: Software for Concurrent Processors: Volume II. Prentice-Hall, Englewood Cliffs, NJ, 1990.

50. Aho V., Hopcroft J. E., and Ullman J. D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974.

51. Akl S. G. The Design and Analysis of Parallel Algorithms. Prentice-Hall, Englewood Cliffs, NJ, 1989.

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

53. Ben-Ari M. Principles of Concurrent Programming. Prentice-Hall, Englewood Cliffs, NJ, 1982.

54. Babb R. G Programming Parallel Processors. Addison-Wesley, Reading, MA, 1988.

55. Carey G. F. Parallel Supercomputing: Methods, Algorithms and Applications. Wiley, New York, NY, 1989.

56. Chandy K. M. and Taylor S. An Introduction to Parallel Programming. Jones and Bartlett, Austin, TX, 1992.

57. Zomaya A. Parallel and Distributed Computing Handbook. McGraw-Hill, 1996.

58. Bar-Noy A. and Kipnis S. Designing broadcasting algorithms in the postal model for message-passing systems. In Proceedings of 4th ACM Symposium on Parallel Algorithms and Architectures, 13-22, 1992.

59. Bertsekas D. P. and Tsitsiklis J. N. Parallel and Distributed Computation: Numerical Methods. Athena Scientific, 1997.

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

61. H. Sullivan and T. R. Bashkow. A large scale, homogeneous, fully distributed parallel machine. In Proceedings of Fourth Symposium on Computer Architecture, 105— 124, March 1977.

62. Tim S. Axelrod, "Effects of synchronization barriers on multiprocessor performance", Parallel computing, 3(1986), pp 129-140.

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

64. Гончуков В.В., Горинштейн В.М., Крумм JI.A. и др. Автоматизация управления энергообъединениями / Под ред. С. А. Совалова. -М.: Энергия, 1979. -432 с.

65. Арзамасцев Д.А., Бартоломей П. И., Холян А. М. АСУ и оптимизация режимов энергосистем: учеб. Пособие для студентов : под ред. Д.А.' Арзамасцева. -М.: Высшая школа. 1983. -208 с.

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

67. Allen J. Wood, Bruce F. Wollenberg, "Power generation, operation, and control", Second edition, Wiley, New York, 1996, -565 c.

68. Evans J.W., Energy management system survey of architectures, IEEE computer application in power, 1989, vol.2 no.l, pp 11-16.

69. Fathi E.T., Bose E., and Caseault, A distributed system for real-time applications, IEEE micro, 1987, vol. 7, no. 6, pp. 21-28.

70. Брамеллер А. и др. Слабозаполненные матрицы: Анализ электроэнергетических систем /пер. с английского. -М.: Энергия 1979. -192 с.

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

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

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

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

75. Описание метода Тевинена ЬЦр://ЬурефЬу51с8.рЬуа51г^5и.еёиЛгЬа8е/е1ес1псД11еуеп1п.111т1

76. Описание метода Тевинена http://www.ee.umd.edu/courses/enee206.F97/2061ab08.html

77. Татур Т.А., Татур В.Е. Установившиеся и переходные процессы в электрических цепях, Высшая школа, 2001.

78. Гераскин О.Т, Основы теории и методов расчета режимов больших электроэнергетических систем: Монография. -М.:ИПК госслужбы, 1996. -166 с.

79. Дзегеленок И.И., Абдулрадх O.A. Эффективность метода декомпозиционных эквивалентов реализуемого на параллельной мультикомпьютерной сети, Электронный журнал Вычислительные сети, Теория и практика, 2003, № 1(3), http://network-iournal.mpei.ac.ru.

80. Мамзелев И. А. Вычислительные системы в технике связи. -М.: Радио и связь. 1987. -240 с.

81. Wesley W. Chu, Leslie J. Holloway, Min-Tsung I.an, and Kemal Efe, "Task allocation in distributed data processing, IEEE computing, 1980, pp57-69.

82. Matthew T. O'keefe and Henry G. Dietz," Hardware barrier synchronization: Static barrier MIMD(SBM)" International Conference on parallel processing 1990.

83. Matthew T. O'keefe and Henry G. Dietz, "Hardware barrier synchronization: Dynamic barrier MIMD(DBM)" International Conference on parallel processing 1990.

84. Norbert S. ARENSTORF and Налу F. JORDAN, "Comparing barrier algorithms" Parallel Computing 12(1989), ppl57-170.

85. Jordan H.F. "д special purpose architecture for finite element analysis", Proc. Int. Conference parallel processing, 1978, pp 263-266.

86. Burroughs corp. Federal and special systems, final report, numerical aerodynamic simulation facility feasibility study, NASA CR-152284 and CR-152285, Paoli,PA,1979.

87. Polychronopolous C. D. "Compiler optimizations for enhancing parallelism and their impact on architecture design", IEEE trans. Comput. Vol.37, no.8, 1988, pp. 991-1004.

88. Yitzhak Birk Philip B. Gibbons Jorge L.C. Sanz Danny Soroker," A simple mechanism for efficient barrier synchronization in MIMD machines", International conference on Parallel processing 1990, part II, pp 195-198.

89. Shisheng Shang, and Kai Hwang, "Distributed hardwire barrier synchronization for scalable multiprocessor clusters", IEEE transactions on parallel and distributed systems, Vol. 6, No. 6., 1995, pp. 591-604.

90. Hwang K. and Shang s. " Wired-NOR barrier synchronization for designing large shared-memory multiprocessor," Proc. International conference on parallel processing, St. Charles, IL, Aug. 13-15,1991, pp. II71-1175.

91. Davis M.H. and Ramachandran U. "A Distributed hardware barrier in an optical Bus-based Distributed shared memory multiprocessor", Proc. 1992 Int'l Conference parallel processing, Vol.1, pp. 228-231, Aug. 1992.

92. William E. Cohen, David W. Hyde, and Rhonda K Gaede, "An Optical Bus-Based Distributed Dynamic Barrier Mechanism", IEEE Transactions on Computers, Vol.49, No. 12, December 2000, pp. 1354-1365.

93. Michael L. Scott and John M Mellor-Crummey, "Fast, Contention-Free Combining Tree Barriers for Shared-memory multiprocessors", Int. Journal of parallel programming, Vol. 22, No. 4, 1994.

94. Brooks E. D. A Multitasking kernel for the C and for FORTRAN programming languages, UCID-20167, Lawrence Livermore National Laboratory, 1984.

95. Gupta R. and Hill C. R. "A scalable implementation of barrier synchronization using an adaptive combining tree", Int. Journal of parallel programming, Vol.18, No.3, 1989.

96. Shun Yan Cheung and Vaidy S. Sunderam, "Performance of barrier synchronization methods in a multiaccess network", IEEE transactions on parallel and Distributed systems, Vol. 6, No. 8, 1995.

97. Fan K.B. and king C.T. "Turn grouping for efficient barrier synchronization in wormhole mesh network", Proc. 25th int'l Conf. Parallel processing, aug.1997.

98. Panda D.K. "Fast barrier synchronization in Wormhole K-array n-cube networks with multidestination worms", Proc. 1995 Int'l symp. High performance computer architecture, pp. 200-209, 1995.

99. Jenq Shyan Yang and Chung ta King, "Designing Tree-based barrier synchronization on 2D mesh networks", IEEE Trans. On Parallel and distributed systems, Vol. 9, No. 6, 1998.

100. Duato J., Yalamanchili S., and L.M. Ni, "Interconnections networks :An Engineering approach", Los Alamitos, Calif. IEEE CS Press, 1997.

101. Oday A.L.A Ridha, Titov V.S, Zotov I.V. Distributed hardware-level model for barrier synchronization in multiprocessor system /Сб. Материалов 5-й международной конференции «распознавание-2001», часть II, Курск 2001. с. 203205.

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

103. Очкова В.Ф. MathCAD Application Server: новые возможности в сфере открытого образования, Электронный журнал «Единая образовательная информационная среда» № 3, 2004, http://emag.integro.ministiy.ru

104. Воскобойников Ю.Е., Очков В.Ф. "Программирование и решение задач в пакете Mathcad" Издательство НГАСУ, 2002.

105. Статьи и книги В.Ф.Очкова по Mathcad http://twt.mpei.ac.ru/ochkov.

106. Cegrell Т., Power system control technology, Prentice hall international,1986.

107. Abdul Sahib R.A. Performance evaluation and improvement of computerized system of Iraqi control center for Electricity, MSc. Thesis, University of technology, 1992.

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