Содержание к диссертации
Введение
ГЛАВА 1. Проблема эффективной реализации распределенных параллельных вычислений 16
1.1. Проблемные среды, определяющие необходимость развития мультикомпьютерных систем 16
1.2. Модели и языки параллельного программирования 19
1.2.1. Модель передачи сообщений (MPI) 21
1.2.2. Модель параллелизма по данным (HPF) 23
1.2.3. Гибридная модель параллелизма по управлению с передачей сообщений (OpenMP+MPI) 24
1.2.4. Модель параллелизма по данным и управлению (DVM) 24
1.2.5. Модель КУРС-2000 27
1.3. Технологии созданий распределенных параллельных приложений 27
1.4. Проектирование распределенных параллельных алгоритмов 29
1.5. Средства распределенного параллельного программирования 32
1.6. Схема управления распределенным объектом (на примере ЭСС) 36
1.7. Показатели эффективности реализации распределенных программ 41
1.8. Цели и задачи проводимого исследования 42
Выводы по главе 1 45
ГЛАВА 2. Разработка декомпозиционной модели проблемной среды 46
2.1. Декомпозиционный подход к повышению эффективности управления распределенным объектом 46
2.2. Задачи оптимизации нормальных режимов ЭЭС, допускающие возможность их декомпозиции 48
2.2.1. Декомпозиция алгоритма оптимизации по "шагам" 54
2.2.2. Декомпозиция задач оптимизации с использованием принципа оптимальности 58
2.2.3. Декомпозиция задач оптимизации на основе метода функциональных характеристик 60
2.3. Разработка декомпозиционной модели 65
2.3.1. Разработка модели распределённых параллельных вычислений для решения задачи расчета установившегося режима ЭЭС 67
2.3.2. Обобщение метода Тевенена для решения задачи расчета установившегося режима ЭЭС 67
2.4. Оценка эффективности реализации декомпозиционной модели 76
2.5. Сравнительный анализ методов декомпозиции 83
Выводы по главе 2 88
ГЛАВА 3. Определение вариантов реализации мультиконвеиерных вычислений на базе метода декомпозиционных эквивалентов 92
3.1. Схема мультиконвейерных вычислений 92
3.2. Организация мультиконвеиерных вычислений (на примере схемы расчета установившегося режима ЭЭС) 95
3.2.1. Простой способ преобразования конвейера 97
3.2.2. Иерархический способ преобразования конвейера 98
3.2.3. Гибридный способ преобразования конвейера 100
3.2.4. Иерархически-параллельный способ преобразования конвейера 101
3.3. Анализ эффективности рассмотренных способов организации мультиконвеиерных вычислений 101
3.3.1. Эффективность 1-го способа организации вычислений 102
3.3.2. Эффективность 2-го способа организации вычислений 106
3.3.3. Эффективность 3-го способа организации вычислений 108
3.3.4. Эффективность 4-го способа организации вычислений 108
3.4. Сравнительный анализ вариантов организации мультиконвеиерных вычислений 109
Выводы по главе 3 109
ГЛАВА 4. Практическая реализация и применение разработанных моделей и программных средств 111
4.1. Методика экспериментального подтверждения ожидаемой эффективности реализации декомпозиционных моделей 111
4.2. Программная реализация метода декомпозиционных эквивалентов 116
4.2.1 .Локальная реализация на сервере МЭИ 116
4.2.2. Реализация в виде распределенной параллельной программы 117
4.3. Подтверждение работоспособности декомпозиционной модели (на примере фрагмента ЭЭС Ирака) 119
Выводы по главе 4 124
Заключение 126
Список литературы
- Модели и языки параллельного программирования
- Задачи оптимизации нормальных режимов ЭЭС, допускающие возможность их декомпозиции
- Организация мультиконвеиерных вычислений (на примере схемы расчета установившегося режима ЭЭС)
- Реализация в виде распределенной параллельной программы
Введение к работе
Качество управления функционированием и развитием больших систем в значительной степени зависит от эффективности решения соответствующих задач. Существует большое количество объектов, которые характеризуются значительной территориальной распределенностью пунктов контроля и управления. К таким объектам относятся магистральные нефте- и газопроводы, электроэнергетические системы (ЭЭС) и другие крупно масштабные объекты. Сложность управления такими объектами обуславливается, прежде всего большими объемами обрабатываемых данных, необходимостью оперативного контроля за состоянием объекта по результатам анализа параметров отдельных подсистем, значительной территориальной рассредоточенностью контрольно-измерительной аппаратуры.
В настоящее время характерно использование централизованного подхода к решению такого рода задач, что является «узким» звеном, ведущим к снижению качества управления, прежде всего за счет большой временной реактивности системы, чрезмерной сложности программного обеспечения (ПО) управления данными, вынужденного использования приближенных расчетов (для уменьшения объемов обрабатываемой информации), малой живучести системы. Поэтому разработка новых перспективных подходов для повышения эффективности управления большими системами является в настоящее время весьма важным.
Объединение локальных центров управления и установленных на них вычислительных средств в единую систему управления создает возможности значительного повышения эффективности управления такими системами.
К основным показателям рассматриваемой эффективности относятся быстродействие, надежность получения решения и организация процессов передачи исходных и промежуточных данных по коммуникационной сети.
Перспективный путь в этом направлении заключается: во-первых, в переходе от последовательных к параллельным вычислениям, во-вторых, в переходе от централизованной к распределенной иерархической организации вычислений.
Распределенные параллельные вычисления в настоящее время представляют собой одну из наиболее передовых концепций в области решения задач большого объема [1-3].
Использование вычислительных сетей (ВС) для достижения указанной цели не представляется возможным, так как ВС обеспечивает лишь преимущественно информационное взаимодействие вычислителей [4-7]. Перспективным для реализации компьютерной поддержки распределенного управления в этом случае является использование нового класса вычислительных систем - параллельных вычислительных сетей (ПВС) [8-10]. ПВС сочетают положительные свойства локальных вычислительных сетей и параллельных вычислительных систем, открывают значительно более широкие возможности для распределенного децентрализованного управления прежде всего за счет глубокой координации взаимодействия удаленных вычислителей.
Переход к распределенности приводит к возрастанию важности проблемы связи вычислителей с точки зрения общего числа обменов, объемов передаваемой информации и вида структуры обменов. Кардинальное решение отмеченной проблемы возможно лишь на основе изучения "глубинных" свойств решаемых задач, определяющих условия их декомпозиции на подзадачи на уровне математических методов. Для того, чтобы действительно осуществить эту концепцию требуется создание новых математических моделей и соответствующих параллельных алгоритмов. Магистральным направлением развития распределенных параллельных вычислений являются методы декомпозиции проблемных сред [4, 11-17].
В задачах управления характерно многократное применение одних и тех же алгоритмов к различным потокам исходных данных. Этому требованию в наибольшей степени удовлетворяет идеология объединения вычислительных модулей в конвейерные вычислительные системы (схема MISD). Объединить различные схемы реализации параллельных вычислений в рамках единого подхода позволяет мультиконвейерная технология вычислений (МКТВ). МКТВ является достаточно общей формой структуризации вычислительного процесса, основывается на развитии и уточнении модели коллектива вычислителей [5-7].
Конвейеризация задачи на макро уровне позволяет упростить организацию вычислительного процесса, обеспечить высокую производительность. Но чтобы обеспечить отмеченные преимущества при организации любого конвейерного вычисления, важнейшую роль играет балансировка его стадий. Эффективным является сбалансированный конвейер. Балансировка заключается в разделении на равные по времени стадии [18-22].
Однако, в настоящее время отмеченные моменты пока не принимаются во внимание при реализации суперкомпьютерных технологий. Вместе с тем, уже имеются предпосылки для реализации распределенных вычислений с использованием декомпозиционного подхода на что как раз и направлена данная работа.
ОБЪЕКТОМ ИССЛЕДОВАНИЯ является класс мультикомпьютерных систем в виде /параллельных) мультикомпьютерных сетей (ПМК-сетей), предусматривающих согласованное взаимодействие в общем случае удаленных вычислителей, осуществляющих обработку данных по месту их возникновения.
ПРЕДМЕТ ИССЛЕДОВАНИЯ. Поиск закономерностей повышения эффективности ПМК-сетей различной конфигурации в зависимости от структурно-топологических характеристик декомпозиционной модели организации распределенных вычислений.
ЦЕЛЬ ДИССЕРТАЦИОННОЙ РАБОТЫ заключается в определении
вариантов организации и эффективного применения параллельных
мультикомпьютерных сетей, проблемно-ориентированных на решение объемных задач, допускающих возможность декомпозиции.
ОСНОВНЫЕ ЗАДАЧИ ДИССЕРТАЦИОННОГО ИССЛЕДОВАНИЯ.
Анализ принципов декомпозиции объемных задач для обеспечения управления сложными территориально-распределенными объектами.
Разработка декомпозиционной модели в классе распределенных параллельных вычислений на уровне взаимосвязанной совокупности выделяемых подзадач.
Аналитическое исследование эффективности ПМК-сетей в зависимости от структурно-топологических характеристик декомпозиционной модели и параметров вычислительной среды.
Разработка методики согласованного масштабирования вычислительных ресурсов ПМК-сети, обеспечивающих повышенную эффективность реализации декомпозиционной модели.
Подтверждение работоспособности разработанных методов и средств на примерах решения модельных задач, включая натурные испытания на действующем макете ПМК-сети.
МЕТОДЫ ИССЛЕДОВАНИЯ. В диссертации используются методы системного анализа, основные положения теории параллельного программирования, принципы организации сетевых распределенных вычислений, методы построения декомпозиционных моделей, языки программирования, методы анализа электрических сетей, линейной алгебры, теории оптимизации. Для проверки эффективности предложенных принципов организации вычислений использовался макет параллельной мультикомпьютерной сети КУРС-2000, разработанный на кафедре Вычислительных машин, систем и сетей (ВМСиС)
12 МЭИ (ТУ), а для проверки достоверности результатов - программы MathCAD и Electronic Workbench.
НАУЧНАЯ НОВИЗНА работы заключается в следующем:
\ ..
' У
Разработана декомпозиционная модель в классе распределенных параллельных вычислений на уровне взаимосвязанной совокупности вьщеляемых подзадач;
Определены варианты организации ПМК-сети, предусматривающие согласованное масштабирование вычислительного ресурса;
Получено семейство аналитических оценок потенциальной эффективности ПМК-сети в зависимости от структурно-топологических характеристик декомпозиционной модели и параметров вычислительной среды.
ПРАКТИЧЕСКАЯ ЦЕННОСТЬ п олученных результатов заключается в следующем:
Проведено сопоставление возможных подклассов мультикомпьютерных систем рассмотренным методам осуществления декомпозиционной модели (на примере РУР ЭЭС) с точки зрения эффективности её реализации по введённому показателю качества.
Показано, что декомпозиционная модель вносит дополнительный "математический" вклад в ускорение, наряду с эффектом "чисто" параллельных вычислений. В свою очередь потенциальная эффективность метода декомпозиционных эквивалентов может быть достигнута и на относительно медленных каналах связи коммуникационной сети МКС в силу отсутствия итерационной схемы приближения к искомому результату.
Разработана методика экспериментального подтверждения ожидаемой эффективности реализации декомпозиционных моделей на определенных в работе конфигурациях ПМК-сетей, что позволяет принимать конкретные архитектурные решения.
Работоспособность и высокая эффективность декомпозиционной модели организации вычислений подтверждена экспериментально в результате программной реализации метода декомпозиционных эквивалентов на действующем макете ПМК-сети «КУРС-2000», а также на примере анализа применимости модели для фрагмента ЭЭС Ирака.
Полученные результаты нашли применение на практике. Так, материалы, содержащие рекомендации по компьютерной реализации декомпозиционных моделей управления ЭЭС, включены в отчет государственного научного центра Всероссийского Электротехнического института (гос. per. №01200305827). Методика проведения натурного эксперимента на ПМК-сети с использованием разработанной распределённой параллельной программы использована на кафедре ВМСиС МЭИ при выполнении госбюджетной НИР (гос. per. №1200001482) и в учебном процессе. Практикум по освоению метода декомпозиционных эквивалентов принят в эксплуатацию и установлен на сервере МЭИ (). Отмеченные результаты подтверждены официально соответствующими актами.
АПРОБАЦИЯ РАБОТЬГ Отдельные результаты и положения диссертационной работы докладывались и обсуждались на научно-технических семинарах научной группы и кафедры ВМСиС, на международных форумах информатизации МФИ-2002 и МФИ-2003 «Информационные средства и технологии» и международной научно-технической конференции РАСО'2004 «Параллельные вычисления и задачи управления».
НАУЧНЫЕ ПУБЛИКАЦИИ. Основные результаты отражены в 13 работах, в том числе в 11 печатных работах и отчетах о НИР (гос. регистрации № 01200001482 и №001200305827). Остальные представлены в виде 2 публикаций в электронном журнале «Вычислительные сети».
14 СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИИ
Диссертационная работа состоит из введения, 4 глав, заключения, списка литературы и приложения. Она изложена на 142 страницах основного машинописного текста, содержит 40 рисунков, 1 таблицу, включает библиографию из 113 наименований. Общий объем диссертации составляет 206 страниц.
В ПЕРВОЙ ГЛАВЕ рассматриваются недостатки централизованного
подхода к управлению сложными объектами и показана необходимость
децентрализованного управления, практическое осуществление которого требует
разработки новых методов и алгоритмов. Описываются языки и модели
параллельного программирования и представлены основные показатели
эффективности реализации распределенных параллельных программ.
Рассматривается комплекс задач оперативного управления нормальными режимами ЭЭС и проанализированы методы их решения и основные характеристики задач. Сформулированы основные задачи диссертации.
ВО ВТОРОЙ ГЛАВЕ рассматривается декомпозиция как основной принцип повышения эффективности распределенных параллельных вычислений при решении задач большой размерности. Рассматриваются три варианта декомпозиции алгоритмов оптимизации режимов ЭЭС. Предложен аналитический метод, позволяющий эффективно решить одну из базовых задач управления ЭЭС-задачу расчета установившегося режима. Получена аналитическая оценка эффективности предложенного метода.
В ТРЕТЬЕЙ ГЛАВЕ рассматриваются вопросы организации мультиконвейерных вычислений. Разработаны четыре способа организации мультиконвейера для решения задачи РУР на основе метода декомпозиционных эквивалентов. Проведён аналитический анализ эффективности каждого способа.
15 Анализ показывает, что наилучшим способом организации мультиконвейера является иерархически-параллельный способ.
В ЧЕТВЕРТОЙ ГЛАВЕ рассматривается методика регламентирования процесса проведения экспериментальных исследований по определению преимуществ декомпозиционного подхода к практическому осуществлению параллельных распределенных вычислений. Все основные положения методики будут проиллюстрированы на уже знакомом примере осуществления упрощенной схемы расчета установившегося режима (РУР) электроэнергетической системы (ЭЭС), представляемой в виде большой электрической сети. Описывается программа, реализующая метод декомпозиционных эквивалентов. Проведены эксперименты по реализации предложенного метода с целью проверки его эффективности и корректности.
В ПРИЛОЖЕНИИ I представлены архитектура и языковые конструкции ПМК-сети «КУРС-2000», используемые для реализации распределенных параллельных программ.
В ПРИЛОЖЕНИИ II представлено результаты установки разработанных программных средств в среде MathCAD, установленные на сервере MAS МЭИ (ТУ) mttp://twt.mpei.ac.ru/MAS/worksheets/others/CREAT EOVI ССТ DBE.mcd).
В ПРИЛОЖЕНИИ III содержится листинг распределенной параллельной программы для реализации метода декомпозиционных эквивалентов.
В ПРИЛОЖЕНИИ IV приведён листинг программы реализации метода декомпозиционных эквивалентов в среде MathCAD.
В ПРИЛОЖЕНИИ V приведён пример для иллюстрации хода вычислений по методу декомпозиционных эквивалентов.
ПРИЛОЖЕНИЕ VI содержит акты о внедрении результатов диссертационной работы.
Модели и языки параллельного программирования
В модели параллелизма по данным отсутствует понятие процесса и, как следствие, явная передача сообщений или явная синхронизация. В этой модели данные последовательной программы распределяются программистом по процессорам параллельной машины. Последовательная программа преобразуется компилятором в параллельную программу, выполняющуюся в модели передачи сообщений. При этом вычисления распределяются по правилу собственных вычислений: каждый процессор выполняет только вычисления собственных данных, т.е. данных, распределенных на этот процессор.
Модель параллелизма по данным имеет следующие достоинства.
Параллелизм по данным является естественным параллелизмом вычислительных задач, поскольку для них характерно вычисление по одним и тем же формулам множества однотипных величин - элементов массивов.
В модели параллелизма по данным сохраняется последовательный стиль программирования. Программист не должен представлять программу в виде взаимодействующих процессов и заниматься низкоуровневым программированием передач сообщений и синхронизации.
Распределение вычисляемых данных между процессорами - это не только самый компактный способ задать распределение работы между процессорами, но и способ повышения локализации данных. Чем меньше данных требуется процессору для выполнения возложенной на него работы, тем быстрее она будет выполнена (лучше используется кэш-память, меньше подкачек с диска страниц виртуальной памяти, меньше пересылок данных с других процессоров).
Обобщение и стандартизация моделей параллелизма по данным привели к созданию в 1993 году стандарта HPF (High Performance Fortran) - расширения языка Фортран 90. Аналогичные расширения были предложены для языка Си и Си++.
Модель параллелизма по управлению (в западной литературе используется и другое название - модель разделения работы, work-sharing model) возникла уже давно как модель программирования для мультипроцессоров. На мультипроцессорах в качестве модели выполнения используется модель общей памяти. В этой модели параллельная программа представляет собой систему нитей, взаимодействующих посредством общих переменных и примитивов синхронизации. Нить (по-английски "thread") - это легковесный процесс, имеющий с другими нитями общие ресурсы, включая общую оперативную память.
Основная идея модели параллелизма по управлению заключалась в следующем. Вместо программирования в терминах нитей предлагалось расширить языки специальными управляющими конструкциями - параллельными циклами и параллельными секциями. Создание и уничтожение нитей, распределение между ними витков параллельных циклов или параллельных секций (например, вызовов процедур) - все это брал на себя компилятор.
Эта модель, положенная в основу языков параллельного программирования Fortran-DVM и C-DVM, объединяет достоинства модели параллелизма по данным и модели параллелизма по управлению.
В отличие от модели параллелизма по данным, в системе DVM программист распределяет по процессорам виртуальной параллельной машины не только данные, но и соответствующие вычисления. При этом на него возлагается ответственность за соблюдение правил собственных вычислений. Кроме того, программист определяет общие данные, т.е. данные, вычисляемые на одних процессорах и используемые на других процессорах. И, наконец, он отмечает точки в последовательной программе, где происходит обновление значений общих данных.
При построении системы DVM был использован подход, который характеризуется следующими принципами.
1. Система должна базироваться на высокоуровневой модели выполнения параллельной программы, удобной и понятной для программиста, привыкшего программировать на последовательных языках. Такая модель (DVM-модель) была разработана в 1994 году.
2. Языки параллельного программирования должны представлять собой стандартные языки последовательного программирования, расширенные спецификациями параллелизма. Эти языки должны предлагать программисту модель программирования, достаточно близкую к модели выполнения. Знание программистом модели выполнения его программы и ее близость к модели программирования существенно упрощает для него анализ производительности программы и проведение ее модификаций, направленных на достижение приемлемой эффективности.
Задачи оптимизации нормальных режимов ЭЭС, допускающие возможность их декомпозиции
Как было отмечено в п. 1.6, для задач диспетчерского управления ЭЭС особое место занимают оптимизационные математические методы. Обусловлено это тем, что основной целью создания Автоматизированных систем диспетчерского управления (АСДУ) является повышение эффективности управления сложными энергообъектами, и для достижения этой цели целесообразно многие технологические задачи ставить и решать как оптимизационные.
Важной составной частью АСДУ являются методы расчета оптимальных режимов. Цель применения этих методов состоит, прежде всего, в отыскании допустимых режимов, т.е. удовлетворяющих условиям надежности электроснабжения и надлежащего качества энергии. Не меньшее значение имеет выбор из числа допустимых режимов наиболее экономичного, т. к. в условиях работы современных ЭЭС это позволяет практически без дополнительных затрат обеспечить экономию за счет снижения расхода топлива и потерь в электрических сетях.
При этом следует иметь в виду, что современные ЭЭС имеют сложные энергетические и топологические структуры, и решение оптимизационных задач сопряжено с целым рядом трудностей, обусловленных большой размерностью задачи, необходимостью учета большого числа ограничений, связывающих переменные. Так как все элементы ЭЭС в той или иной степени нелинейные (в частности связи между параметрами режима, определяющие значения переменных минимизируемой функции), то задачи оптимизации режимов ЭЭС относятся к классу задач нелинейного программирования.
Цель решения задачи оптимизации режима ЭЭС заключается в минимизации эксплуатационных затрат на производство, передачу и распределение электрической энергии. Эксплуатационные затраты зависят не только от внешних факторов, главными из которых являются характеристика и значение подключенной нагрузки, но и от режима электрической системы, на который можно воздействовать через систему управления. Связь между эксплуатационными затра тами 3 и управлением режимами электрической системы, можно охарактеризовать следующим соотношением [66-68 ]: r/ /tC ot.:r,-,,.,_/, л. з = з0+з(р), где первой составляющей Зо можно пренебречь, так как она мало зависит от режима электрической системы. В нее входят такие компоненты, как затраты на заработную плату эксплуатационного персонала, затраты на комплекс мероприятий по повышению надежности и экономичности работы электроэнергетического оборудования за счет повышения КПД устройств преобразования и передачи энергии (парогенераторов, турбин, генераторов и т. д.). Эти затраты почти не зависят от нагрузки и их уменьшение достигается усилиями эксплуатационного персонала электростанций и сетевых предприятий.
Вторая составляющая 3(Р) характеризует затраты на энергоресурсы и зависит от режима энергосистемы, состава и загрузки включенного в работу оборудования. При этом основными носителями энергии являются топливо для тепловых электростанций (ТЭС) и вода для гидроэлектрических станций (ГЭС). Нетрудно видеть, что величина 3(Р) определяется затратами на топливо с учетом его добычи и транспортировки. Решение задачи управления режимами энергосистемы заключается в определении управляющих воздействий, обеспечивающих минимум народнохозяйственных затрат на производство, передачу и распределение электроэнергии. Эта задача сводится к минимизации затрат на энергоресурсы 3(Р). В свою очередь, минимум затрат на топливо может быть достигнут лишь при полном оптимальном использовании ограниченных запасов гидроресурсов [66-68].
Значение активной суммарной нагрузки энергосистемы Рн определяется поведением потребителей электроэнергии и рассматривается в энергосистеме как заданный параметр, характеризующий внешнее воздействие. С учетом потерь мощности в элементах сети для каждого момента времени должно выполняться условие баланса мощности [66-68] ±Р;-Р -АР =О, (2Л) Р? где J / -активная мощность 1-го источника в момент времени /; Рн -активная мощность потребители в момент времени t; Аг -суммарные потери активной мощности в электрической системе. Условие (2-1) должно выполняться при поддержании номинальной частоты напряжения или тока.
Оптимальное управление нормальными режимами энергосистемы заключается в экономичном распределении нагрузки системы между источниками, т. е. в определении значений Р/, обеспечивающих минимум затрат на энергоресурсы. При этом располагаемый запас гидроресурсов 0у определяется природными условиями водотока (площадью бассейна, количеством осадков и др.), а также дополнительными условиями судоходства, сплава леса, прохождения рыбы и т. д. [66-68]
Нельзя израсходовать гидроэнергии больше, чем это позволяет ресурс r а меньше — невыгодно, так как его недоиспользование приводит к холостому сбросу воды на ГЭС и означает, что заданная для системы выработка электроэнергии достигается за счет дополнительного сжигания топлива на ТЭС. Расход топлива В. на любой і-й ТЭС зависит от ее активной мощности и состава включенного в работу оборудования; при этом оба параметра могут быть переменными во времени, а следовательно, суммарные затраты на топливо за время Т определяются функционалом вида:
Организация мультиконвеиерных вычислений (на примере схемы расчета установившегося режима ЭЭС)
Как уже известно, на первой стадии (фазе) по методу декомпозиционных эквивалентов строятся абстрактные схемы замещения. Каждая из них состоит из источника напряжения и эквивалентного комплексного сопротивления. На первой стадии требуется определить значения эквивалентных напряжений Тевинена (Vth) и эквивалентных токов Нортона (Isc). Как было показано (раздел 2.3), для того чтобы определить Vth и Isc необходимо вычислить все коэффициенты ( ark, b0 k, r=0,1 ..n, k=l,2..n ) следующих систем уравнений: v,hk = au + v\ -ax,k +-+ -1 -ak-hk +УЫ -aMk +-Vn -ank, k=l,2..n, (3.1) 4 = \A + VX A +-+ -1 A-u +V A+u +-K A, , k=l,2..n, (3.2) где n- число граничных узлов в подсети.
Если выделить один процессор или компьютер для каждой стадии, то коэффициенты можно вычислять в пределах одного слоя конвейера (рисунок 3.2). Причем вычисление каждого коэффициента требует решения системы уравнений вида (2.11), число которых определяется количеством внутренних узлов подсети.
По данному способу разбиения получается конвейер, состоящий из более мелких слоев. Причем общий объем вычислений не изменяется. Число слоев получаемого конвейера равно числу коэффициентов уравнений (3.1) и (3.2) плюс два. Как уже сказано в разделе 2.4, число коэффициентов равно m(m+l), где т- число граничных узлов в подсети.
При таком способе разбиения первой стадии метода декомпозиционных эквивалентов число слоев получаемого конвейера увеличилось, но конвейер ещё не является сбалансированным. Так, по одним слоям решаются системы линейных уравнений, в которых количество неизвестных равно числу внутренних узлов. В то время как по другим слоям решаются системы, у которых число неизвестных равно числу граничных узлов. Поскольку отношение между количествами граничных и внутренних узлов в реальной сети составляет 3%-10%, время, необходимое для решения системы линейных уравнений методом Гаусса пропорционально кубу размерности системы [48]
Второй способ разбиения первой и третьей стадии метода декомпозиционных эквивалентов основан на принципе рекурсивного разбиения подсетей, до тех пор, пока число внутренних узлов не станет равным (или близким к) числу граничных узлов. Процесс разбиения подсетей происходит логически, а не физически (рисунок 3.3). Цель рекурсивного разбиения сделать процесс вычислений иерархическим и, следовательно, получить конвейер, состоящий из многих стадий. При разбиении сети и подсетей необходимо соблюдать условие, чтобы число граничных узлов между подсетями было минимальным.
По этому способу на первой стадии вычисляется эквивалентная схема наименьшей подсети. На каждой следующей стадии вычисляется общая эквивалентная схема подсетей предыдущих стадий. Процесс вычислений продолжается до тех пор, пока не будет построена эквивалентная схема полной сети.
Иллюстрация принципа иерархического разбиения большой электрической сети После окончания стадий вычисления эквивалентных схем (ход верх), начинаются стадии, на которых определяются значения граничных узлов (ход вниз). Граничные узлы подсети на уровне і представляют собой внутренние узлы подсети на уровне i-l, где уровень i-l выше уровня і. Процесс определения значения граничных узлов начинается с верхнего уровня до самого низкого уровня, где есть только внутренние узлы, см. рисунок 3.4.
Этот способ разбиения имеет некоторые преимущества по сравнению с первым. Во-первых, получаемый конвейер является, близким к сбалансированному. Балансировка конвейера зависит от способа разбиения сети и подсетей. Во-вторых, иерархическая структура процесса вычислений подобна структуре реальной системы управления большой электроэнергетической системой, которая состоит из пяти уровней. Это подобие облегчает процесс логического разбиения сети и подсетей.
С использованием второго способа на каждом уровне вычисляется эквивалентная схема подсетей предыдущего уровня, т.е. на каждой стадии вычисляется mk(mk+l) коэффициентов (ход верх). В дальнейших стадиях вычисляются значения граничных узлов (ход вниз).
Гибридный способ представляет собой смешивание первого и второго способа. По этому способу, на каждой стадии конвейера вычисляется только один коэффициент, а не mk(mk+l) коэффициентов как во втором способе (рисунок 3.5).
Реализация в виде распределенной параллельной программы
Алгоритм программы можно представить в виде последовательности нескольких стадий. В первой стадии вызывается одна из функций библиотеки КУРС2000 или MPI, которая получает все эквивалентные схем от программ первой группы. На второй стадии формируются матрица D и вектор с. Размерность D и с зависит от топологии подсетей и числа граничных узлов. В приложении III представлен листинг программы, в которой матрица D и вектор с формируются по схеме 4.2.
После формирования Due вызывается функция sol_equ_cmp( ), чтобы определить значения граничных узлов. Получив решение системы уравнений (4.1), программа посылает значения напряжения в граничных узлах всем программам первой группы. Dx=c (4.1)
На этом завершается работа программы главного вычислителя для расчета схемы устанавливающего режима. В приложении III представлен листинг программ для локальных и главного вычислителей Ирак - это одна из стран с большим потреблением электрической энергии. Среднее потребление мощности в Ираке около четырех тысяч мегаватт. Ирак имеет теплоэнергетические и гидроэнергетические станции.
Электроэнергетическая система Ирака распространяется на сотни километров. Системой управления ЭЭС Ирака состоит из трех локальных центров, северного (Karkuk), среднего (Baghdad), южного (Basra). Каждый центр управляет электроэнергетическими сетями своего региона, см. рисунок 4.4. Средней центр управления - национальный центр управления ЭЭС Ирака управляет всеми остальными. Национальный центр управления обменивается данными с другими центрами через канал связи с пропускной способностью до 1200 бит/сек[111-113].
При оценке коэффициента эффективности метода декомпозиционных эквивалентов используется упрощенная формула, так как, во-первых, нет конкретных данных о компьютерах управляющих центров Ирака, во-вторых, формула даёт хорошее приближение. Применяя упрощенную формулу Eff =- -, Получаем Keff равен 1.6. Рисунок 4.5. Электрическая сеть фрагмента ЭЭС
Для проверки корректности метода декомпозиционных эквивалентов рассматривалась электрическая сеть, которая представлена на рисунке 4.5. Эту сеть разбили на три подсети. Определили граничные узлы, (1-1,1-4) для подсети 1, (2-1,2-4) для подсети 2, и (3-1,3-4) для подсети 3. Вычислили напряжения во всех узлах сети по методу декомпозиционных эквивалентов, обычным методом, с использованием MathCAD и Electronics Workbench .
Сопоставляя рисунки 4.9 и 4.10 нетрудно убедиться в полном совпадении результатов счета и, тем самым, в реализуемости декомпозиционной модели на параллельной мультикомпьютерной сети. В приложении V приведён пример для иллюстрации хода вычислений по методу декомпозиционных эквивалентов.
Выводы по главе 4
1. Описана методика экспериментального подтверждения ожидаемой эффективности реализации декомпозиционных моделей на определенных в работе (глава 3) конфигурациях ПМК- сетей, что позволяет принимать конкретные архитектурные решения.
2. Проведенные оценки возможной эффективной реализации декомпозиционной модели на ПМК-сети на примере РУР фрагмента ЭЭС Ирака Проведенное сопоставление расчета по декомпозиционной модели и «на прямую» подтверждает целесообразность предлагаемого способа организации вычисления.
3. Предложный способ организации вычислений доведен до работающей распределенной программы, которая может найти применения для проведения натурных испытаний на действующих макетах ПМК-сети.
4. Высокая эффективность программной реализации метода декомпозиционных эквивалентов подтверждена экспериментально на действующем макете ПМК -сети «КУРС-2000».
5. Полученные результаты нашли применение на практике: материалы, содержащие рекомендации по компьютерной реализации декомпозиционных моделей управления ЭЭС включены в отчет ВЭИ (гос. per. №01200305827), использованы при выполнении госбюджетной НИР и в учебном процессе кафедры ВМСиС МЭИ ((гос. per. №1200001482), практикум по освоению метода декомпозиционных эквивалентов принят в эксплуатацию и установлен на сервере МЭИ (http://twt.mpei.ac.ru/MAS/worksheets/others/CREAT_EQUI_CCT_DBE.mcd), что подтверждено официально соответствующими актами.
