Математические и программные средства построения архитектуры и топологии сети вычислительной системы для управления территориально распределенными объектами тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Погребной, Александр Владимирович

• Погребной, Александр Владимирович
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Погребной, Александр Владимирович

ВВЕДЕНИЕ.2

ГЛАВА 1. ОПРЕДЕЛЕНИЕ ЧИСЛА СТАНЦИЙ ВЫЧИСЛИТЕЛЬНОЙ

СИСТЕМЫ.17

1.1. Описание предметной области.17

1.2 Выбор минимального числа станций для подключения терминальных точек топологического поля.!.22

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

1.4. Анализ параллельного выполнения программной нагрузки на заданной совокупности станций.31

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

ГЛАВА 2. РАЗМЕЩЕНИЕ СТАНЦИЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ НА ТОПОЛОГИЧЕСКОМ ПОЛЕ.39

2.1. Алгоритмы получения исходных вариантов размещения станций.41

2.2. Оптимизационная постановка задачи размещения станций.50

2.3 Алгоритм решения задачи размещения станций по схеме метода ветвей и границ.59

2.4 Оптимизация распределения терминальных точек по станциям.67

2.5. Исследование некоторых свойств компактных разбиений.73

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

ГЛАВА 3. ПОСТРОЕНИЕ ТОПОЛОГИИ СЕТИ ВЫЧИСЛИТЕЛЬНОЙ

СИСТЕМЫ ПРИ ЗАДАННОМ РАЗМЕЩЕНИИ СТАНЦИЙ.97

3.1. Анализ параметров программной нагрузки, определяющих структуру локальной сети.97

3.2 Выбор структуры локальной сети вычислительной системы.107

3.3. Согласование моделей программной нагрузки и алгоритма функционирования объекта управления с учетом топологии сети вычислительной системы.118

3.4. Построение плана обслуживания оборудования вычислительной системы и объекта управления.125

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

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

4.1. Формирование исходных вариантов размещения станций (программное средство «Полюс»).135

4.2. Оптимизация распределения терминальных точек по станциям и получение ЛК - разбиения (программное средство «Топология»).140

4.3. Выбор структуры локальной сети вычислительной системы (программное средство «Сеть»).144

4.4. Построение модели архитектуры вычислительной системы (программное средство «Редактор архитектур»).147

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

Введение диссертации (часть автореферата) на тему «Математические и программные средства построения архитектуры и топологии сети вычислительной системы для управления территориально распределенными объектами»

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

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

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

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

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

Мягкие СРВ отличаются тем, что задержка реакции не столь критична, хотя и может привести к увеличению стоимости результатов и снижению производительности системы в целом. Отличие между жесткими и мягкими СРВ в [9] сформулировано так: «система жесткого реального времени никогда не опаздывает с реакцией на событие, система мягкого реального времени - не должна опаздывать с реакцией на событие».

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

Теоретические основы методов проектирования СРВ к настоящему времени разработаны слабо [10]. Основные научные интересы разработчиков СРВ были сосредоточены на создании операционных систем реального времени (ОС РВ) и инструментальной среды программирования. К настоящему времени разработаны десятки коммерческих и специализированных ОС РВ. Наиболее популярными среди них являются OS 9 и QNX, а также Lynx OS, созданная на основе заимствования и переработки функций ядра ОС UNIX (пользовательский интерфейс, концепция процессов и др.). ОС РВ реализует развитые механизмы обмена информацией между запущенными процессами, развитые средства работы с таймерами, средства управления ресурсами системы [11 — 14].

В последние 20 лет стали интенсивно развиваться объектно-ориентированные методологии разработки программного обеспечения [15 — 17]. В 1997 г. принят стандарт языка объектно-ориентированного моделирования UML (Unified Modeling Language) [18]. Другим объектно-ориентированным подходом является методология ROOM (Real-Time Object-Oriented Modeling), созданная для разработки СРВ [19]. Появились также стандарты SDL, 8Т^для разработки телекоммуникационных систем [20 -22].

На основе UML, SDL, ROOM разработана объектно-ориентированная методология Real, которая отражает интеграционные тенденции и применима для разработки информационных систем и систем реального времени [23].

В качестве примера технологии программирования встроенных систем реального времени можно привести RTST — технологию (Real-Time Software Technology) [9]. Технология RTST использует объектно-ориентированный подход и язык SDL — диаграмм. Предусматривается статическое распределение ресурсов и функций по объектам, синхронная организация параллелизма на процессах короткого действия.

Для поддержки инструментальных средств разработки программного обеспечения СРВ и принятия решений по системе управления в целом широкое применение получили методы моделирования [24 — 27]. Для оценки производительности используются модели в форме сетей массового обслуживания [28, 29]. Показатели надежности оцениваются на.основе цепей Маркова [30]. При разработке СРВ особо важное место занимают исследования по взаимодействию параллельных процессов, [31 — 33]. Здесь широкое применение получили сети Петри [34, 35] и их развитие [36; 37], в том числе Е-сети [38, 39], а также сети Керка [40 - 42]. В последние годы большой интерес стал проявляться к использованию нейронных сетей? для обработки информации, в том числе' для: обработки сигналов в реальном времени [43 — 45].

Поскольку, в последнее время; все большее число СРВ разрабатывается как; распределенные и сетевые, в составе, инструментальных средств: для разработки таких систем возросла роль задач, связанных с определением структуры сети и ее топологической привязки к оборудованию распределенного объекта. • .'

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

• • число микропроцессорных станций, которое понадобится'; для своевременного выполнения- прикладных функций' проектируемой системы; ' ' " .

• как эти станции размещены на;территории расположения^ объекта и какие терминальные точки (датчики и исполнительные механизмы) подключены к ним;

• как связаны между собой станции в единую, локальную сеть.

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

Независимо от частных критериев, которые могут сопровождать выполнение проектных процедур, проблема сокращения затрат времени на выполнение любых действий при функционировании СРВ (выполнение функций ОС РВ, модулей программной нагрузки, передач данных в сети), всегда является актуальной. Вместе с тем стремление сократить затраты времени при выполнении; одних действий системы может привести к ухудшению этого показателя при выполнении других действий. Так, снижение затрат времени, на выполнение прикладных функций за счет распараллеливания и увеличения числа станций приводит к росту объемов передач данных в сети вычислительной системы [37, 43, 31, 4]. Если число микропроцессорных станций вычислительной системы задано, то объем передаваемых данных между станциями сети зависит от следующих факторов - условий функционирования объекта управления, значений параметров программных модулей, реализующих прикладные функции СРВ и составляющих основную часть программной нагрузки на систему, . распределения программной нагрузки по станциям. 7

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

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

Для многих других приложений, не связанных с проектированием жестких СРВ (автоматизация проектных и научных работ, управление производством и т. п.), число станций и топология сети предопределяется объектом и принимается заданной. В' этих случаях основной становится задача распределения программной нагрузки по станциям сети и получение плана использования ресурсов [46, 47]. Известно много работ, в которых задача получения плана использования ресурсов формулируется как нелинейная задача математического программирования с булевыми переменными, например [43]. Такие задачи можно решать, используя метод линеаризации [48], но как отмечено в [49] для распределения 25 программных модулей по 15 станциям получается линейная задача на 2500 переменных и 8000 ограничений.

Применительно к распределенным СРВ обе задачи подробно изложены в* [43]. Задача- определения числа станций и их размещения, ставится как задача линейного программирования, но уже для территории размещения станций, представленной сеткой размерностью 20x50, число переменных достигает одного миллиона. Задача получения плана использования ресурсов в [43] сформулирована как нелинейная задача математического программирования с булевыми переменными для двух вариантов, топологии сети.

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

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

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

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

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

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

Для достижения цели диссертации были поставлены и решены следующие задачи:

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

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

• распределение (подключение) терминальных точек по станциям по критерию минимума суммы расстояний от точек до станций, на которые они распределены;

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

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

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

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

• Восьмой Российско - Корейский международный симпозиум по науке и технологии (The 8 Russian-Korean International Symposium on Science and'Technology) «KORUS 2004» (г. Томск, ТПУ, 2004r).

• Конференция «Молодежь и современные информационные технологии» (г. Томск, ТПУ,2004г).

• Девятый Российско-Корейский международный симпозиум по науке и технологии (The 9 Russian-Korean International Symposium on Science and Technology) «KORUS-2005» (г. Новосибирск, НГТУ, 2005r).

• Международная' конференция «Современная техника и технологии» (г. Томск, ТПУ ,2006г).

• Международная конференция «Современная техника и технологии» (г. Томск, ТПУ ,2007г>

По результатам исследований опубликовано 5 докладов на конференциях и 5 статей, 3 из них в журнале «Известия Томского политехнического университета», рекомендованном ВАК.

Диссертационная рабрта изложена в четырех главах.

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

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

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

Рассмотрены условия функционирования объектов управления," представленных моделью программной нагрузки СРВ в форме ГПД.

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

Первый этап сопоставляет суммарные ресурсы выбранного числа станций (процессорное.время и память) и потребности модулей ГИД в этих ресурсах.

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

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

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

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

Стратегия решения задачи размещения станций основана' на . формировании расширенной совокупности «хороших» множеств терминальных точек с последующим выбором предпочтительных множеств, для:размещения в них станций. Задача выбора предпочтительных, множеств, из расширенной совокупности сформулирована* как задача? линейного математического программирования с булевыми переменными. Для ее решения предложен алгоритм по схеме метода ветвей и границ.

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

Приводятся исследования ЛК - разбиений и вводится граничная оценка для идеального разбиения, которая позволяет оценить отклонение решения задачи размещения станций от идеального.

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

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

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

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

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

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

Научную новизну имеют следующие результаты.

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

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

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

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

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

Практическая ценность результатов работы.

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

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

• определения числа станций (задача покрытия);

• формирования полюсов (алгоритмы ах,а2,а3);

• размещения станций (алгоритм по схеме метода ветвей и границ); распределения терминальных точек по станциям (транспортные задачи Т и Т*);

• получения ЛК - разбиений (процедура, включающая задачу Т);

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

• построения контуров обхода станций^при их обслуживании^

3. Результаты исследований позволили построение архитектуры и топологии сети вычислительной системы поставить в зависимость от значений параметров модели программной нагрузки и условий • * > функционирования объекта управления. Здесь также важно то обстоятельство, что эту зависимость удалось установить аналитическими методами на начальной стадии проектирования до привлечения трудоемких. систем моделирования.

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

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

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

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

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

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

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

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

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

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Погребной, Александр Владимирович

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Погребной, Александр Владимирович, 2008 год

1. Ларионов A.M., Майоров С.А., Новиков Г.И. Вычислительные комплексы, системы и сети. Л.: Энергоатомиздат, 1987. — 288 с.

2. Каган Б.М. Электронные вычислительные машины и системы: Учебное пособие для вузов. -М.: Энергоатомиздат, 1991.

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

4. Вальков В.М., Вершинин В.Е. Автоматизированные системы управления технологическими процессами. — 3-е изд., перераб. и доп. Л.: Политехника, 1991г.

5. Шенброт И.М., Антропов М.В., Давиденко К.Я. Распределенные АСУ технологическими процессами. М.: Энергоатомиздат, 1985г.

6. Сонькин М.А., Слядников Е.Е., Русановский С.А. Информационная технология интеграции компонентов многоуровневых систем с пакетной передачей данных // Известия Томского политехнического университета, 2006. - Т.309, - №6. - С. 158-164.

7. Терехов А.Н. RTST-технология программирования встроенных систем реального времени. Записки семинара кафедры системного программирования «CASE средства RTST++». Вып.1. - СПб, изд-во С-Петербургского университета, 1998.

8. Айсбари С. Корпоративные решения на базе LINOX. М.: Издательство «Россия», 2001. - 389с.

9. Орлов С.А. Технологии разработки ПО. Разработка сложных программных систем. СПб.: «Питер», 2000. - 682с.

10. Липаев В.В. Проектирование программных средств. Учебное пособие для вузов. -М.: Высшая школа, 1990. — 303с.

11. Шелухин О.И., Тенякшев A.M., Осин A.B. Моделирование информа-циооных систем. — M.: Радиотехника, 2005.

12. Скотт,Кендалл. UML. Основные концепции.: Пер. с анг. М.: Издательский дом «Вильяме», 2002. - 144с.

13. Selic В. Gullekson G. Ward Р.Т. Real-time object oriented modeling. John Wiley & Sons. Inc, 1994. - 525p.

14. Бардзинь Я.М., Калкинып A.A., Строде Ю.Ф., Сыцко В.А. Язык спецификаций SDL/PLUS и его применения. Рига, 1988, 313с.

15. ITU. Recommendation Z. 100: Specification and Description Language (SDL). 1993.-204p.

16. ITU. SDL nethodology guidelines and bibliography. Appendices : to recommendation Z100, 1993,-107p.

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

18. Шеннон Р. Имитационное моделирование систем искусство и наука.1. М.: Мир, 1978.-422с.

19. Дыхненко Л.И., Кузьмин И.В. и др. Основы моделирования сложных систем. Киев: Высшая школа. 1981. — 359с.

20. Советов Б.Я., Яковлев С.А. Моделирование систем. М.: Высшая школа, 1998.-319с.

21. Советов Б.Я. Моделирование систем. М.: Высшая школа, 2001. -343с.

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

23. Шрайбер Т.Дж. Моделирование на GPSS: Пер. с англ. М.: Машиностроение, 1980.-592с.

24. Альянах И.Н. Моделирование вычислительных систем. Л.: Машиностроение, 1988.-223с.

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

26. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. - 296с.

27. Погребной Д.В. Моделирование работы параллельных процессов на основе виртуальной машины // Математическое и программное обеспечение проектирования систем. Вып.2. — Томск: Изд-во ТПУ, 2002, — с. 105-109.

28. Питерсон Дж. Теория сетей Петри и моделирование систем. Пер. с англ. М.: Мир, 1984. - 264 с.

29. Котов В.Е. Сети Петри. -М.: Наука, 1984, 158с.

30. Лобков С.Н., Фатхи В.А., Климович Г.И., Дуднакова О.В. Стохастиче-ско-детерминированные временные сети Петри как средство описания моделей многопроцессорных вычислительных систем // УСиМ. — 1991.- №8. 60-68с.

31. Слепцов А.И., Юрасов A.A. Автоматизация проектирования управляющих систем гибких автоматизированных производств. — К.: Техника, 1986. 110с.

32. Костин А.Е., Савченко JI.B. Модифицированные E-сети для исследования систем распределённой обработки информации // Автоматика и вычислительная техника. — 1988. — №6. — С. 27—35.

33. Баев В.В., Пипетко C.B. Пакет программ моделирования дискретных процессов расширенными сетями Петри // УСиМ. — 1991. — №8. — С. 83-87.

34. Мытус JI. Модель программного обеспечения распределённых вычислительных систем управления // Программирование. — 1983, — №3, — С. 46-54.

35. Мытус Л., Чугунов B.C., Артемьева Н.И. и др. Выбор формального метода спецификации ПО систем управления дискретно-непрерывными производствами // УСиМ. 1985. - №2. - С. 11-15.

36. Мытус J1. Особенности моделирования программного обеспечения многопроцессорных вычислительных систем // Изд. АН СССР. Техническая кибернетика. 1985. - №4. - С. 149-156.

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

38. Круглов В.В., Борисов В.В. Искусственные нейронные сети. Теория и практика. М.: Горячая линия - Телеком, 2001. - 382с.45,Осовский С. Нейронные сети для обработки информации / Перевод с польского. -М.: Финансы и статистика, 2002. 344с.

39. Нореиков И.П., Кузьмик П.К. Информационная поддержка наукоёмких изделий. CALS-технологий. М.: МГТУ им. Н.Э. Баумана, 2002. -304с.

40. Соломенцев Ю.М. Информационно-вычислительные системы в машиностроении. CALS-технологии. М.: Наука, 2003. 292с.

41. Watters L.T. Reduction of integer polynomial programming problems to zeroone programming problems // Operation Res. 1967. — Vol. 15. - №6. — P.l 171—1174.

42. Chu W.W., Holloway L.I., Lan M.T., Efe К. Task allocation in distributed data processing // IEEE Trans, on Computers. — 1980. Vol. 13. — №11. -P. 57-69.

43. Де Мерс Майка Н. Географические информационные системы. Основы. М. : Дата+, 1999. - 490с.

44. Микони C.B. Теория и практика рационального выбора. М.: Маршрут, 2004.

45. Багдасарова Е.П. Применение современных технологий сборка данных с наблюдательной сети. // Метеоспектроскопия. — 2005. №2. - С. 89-93.

46. Погребной A.B. Оптимизация топологии компонентов вычислительной системы при проектировании систем реального времени // Математическое и программное обеспечение проектирования систем. Вып. 2. Томск:. Изд-во ТПУ. 2002, - с.53-55.

47. Погребной В.К., Погребной Д.В. Методы анализа алгоритмов, функционирующих в системах реального времени // Кибернетика и вуз. вып. 28. Томск, ТПУ, 1994, С.98-106.

48. Погребной В.К. Активные модели систем. Определение и область применения // Математическое и программное обеспечение проектирования систем. Вып. 2. Томск.: Изд-во ТПУ. 2002. - С. 4-19.

49. Погребной A.B. Задача определения станций многопроцессорных систем управления // Молодёжь и современные информационные технологии. Томск. 2004. -Т.1.

50. Pogrebnoy V.K., Pogrebnoy A.V., Efficient placement of stations of to-pologicalli distributed multiprocessing computing systems // Proceedings of the 8 Russian-Korean international symposium on science and technology. — Vol.2. Tomsk, 2004.

51. Погребной B.K. Покрытие схем вычислительных устройств блоками унифицированного набора // Известия ТПУ, — 1970. Т.211. - С. 81-87.

52. Дегтярёв Ю.И. Методы оптимизации. Учебное пособие для вузов. М.: Сов. Радио, 1980. - 272с.

53. Пантелеев A.B. Летова Т.А. Методы оптимизации в примерах и задачах. М.: Высшая школа, 2002. - 544с.

54. Ope. О. Теория графов. М.: Наука, 1980. - с.25-34.

55. Трахтенгерц Э.А. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции. — М.: Наука, 1991. — 256с.

56. Погребной A.B. Определения числа и топологии размещения станций МВС // Известия ТПУ. 2006. - Т. 309. - №7.

57. Кристофидес Н. Теория графов, Алгоритмический подход. М.: Мир, 1978.-432с.

58. Галкина В.Н. Дискретная математика: комбинаторная оптимизация на графах. М.: Гелиос АРВ, 2003. - 232с.

59. Погребной A.B. Задача топологической децентрализации в территориально распределённых технических системах // Современные техника и технологии, 2006. - Т.2.

60. Погребной A.B. Определение объёмов передач данных в сети вычислительной системы для заданной модели программной нагрузки // Известия ТПУ, 2007, - Т. 310. - №3. - С. 103-107.

61. Корниенко A.B., Погребной В.К. Модель и алгоритм разбиения схем вычислительных устройств на функциональные блоки // УсиМ. — 1976. — №5. — С. 94-98.

62. Погребной В.К. Матричный алгоритм решения задачи разрезания графов //Известия ТПУ. 2007. - Т. 310. - №5. - С. 91-96.

63. Пападимитру X., Страйглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. — М.: Мир, 1985. — 510с.

64. Новиков Ф.А. Дискретная математика для программистов. Учебник. Санкт-Петербург: Москва, Харьков, Минск: Питер, 2000. - 301с.

65. Яблонский C.B. Введение в дискретную математику. Учебное пособие для вузов, 4-е издание.:-М.: Высшая школа, 2003. 384с.

66. Хаггарти, Род Дискретная математика для программистов. Пер. с англ.: Учебное пособие для вузов. 2-е изд., доп.: — М.: Техносфера, 2005. -393с.

67. Макоха А.Н. Дискретная математика. Учебное пособие для вузов, — М.: Физматгиз, 2005. 368с.

68. Погребной A.B. Выбор архитектуры локальной сети при проектировании распределённой системы реального времени // Современные техника и технологии. — 2006. — Т.2.

69. Погребной A.B., Погребной Д.В., Проектирование структуры локальной сети для распределённой вычислительной системы реального времени // Известия ТПУ. 2007. - Т.310. - №5. - С. 97-101.

70. Смирнов А.Д. Архитектурна вычислительных систем: Учебное пособие для вузов. М.: Наука. 1990. - 320с.

71. Погребной В.К. Об автоматизации модульного проектирования программного обеспечения АСУ ТП // УСиМ. 1978. - №1. - С. 25-34.

72. Погребной В.К. Построение и исследование графовых моделей алгоритмов управления в АСУ. В кН.: Автоматизация проектирования систем управления. -М.: Статистика. 1978. 68-99с.

73. Погребной В.К. ЭФ-технология моделирования и автоматизированного проектирования систем реального времени // УСиМ. — 1988. — №4. — С. 23-30.

74. Емельянов В.В., Курейчик В.М., Курейчик В.В. Теория и практика эволюционного моделирования. — М.: Физматлит, 2003.

75. Черноруцкий И.Г. Методы принятия решений. Учебное пособие. — С.Пб.: БХВ -Петербург, 2005.

76. Погребной A.B. Построение модели для топологически распределённой динамической системы // Кибернетика и вуз. Вып. 30. Изд. ТПУ. Томск. 2003.

77. Погребной В.К., Сонькин М.А., Огородов C.B. Имитационное моделирование информационно-телекоммуникационных систем сопровождения подвижных объектов // Известия вузов. Физика, — 2004. №7. — С. 55-59.

78. Сонькин М.А., Слядников Е.Е. Об одном подходе к оптимизации функционирования многоканальных систем передачи данных для труднодоступных объектов // Вычислительные технологии. — 2007. — Т. 12. — С. 17—22.

79. Струченков В.И. Методы оптимизации. Основы теории, задачи, обучающие компьютерные программы. М.: Экзамен, 2005. 256с.

80. Christofides N., Mingozzi A., Toth P. The" vehicle routing problem. In:Christofides N., Mingozzi A., Toth P., Sandi C., editors. Combinatorial optimization. — London: Wiley, 1979.

81. Минаков И.А. Сравнительный анализ некоторых методов случайного поиска и оптимизации // Известия самарского НЦ РАН. — 1999. — №2. — С.286-293.

82. Столлингс В. Современные компьютерные сети. — С. Пб.: Питер, — 2003.

83. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование. М.: Физматлит, 2007, - 304с.

84. Погребной А.В. Решение многоконтурной задачи Коммивояжера при анализе территориально распределённой технической системы // Proceedings of the 9 Russian-Korean international symposium on science and technology. Novosibirsk, 2005.

85. Сонькин M.A. Информационные технологии в задачах построения микропроцессорных систем с передачей информации по радиоканалу // Трансферные технологии в информатике. Научно-технический сборник. Вып. 1. Томск: Изд. ТПУ. -1999. С. 12-18.

86. Сонькин М.А., Диденко С.В. Способ построения аппартно-программных средств контроля подвижных объектов. В кн.: Математическое и программное обеспечение проектирования систем. Научно-технический сборник. Вып. 2. Томск: Изд. ТПУ, 2002, с. 141—147.

87. Джон Матчо, Давид Р. Фолкнер. Delphi: пер. с англ. -М.: Бином, 1995.

88. Баженова И.Ю. Delphi 6 — Самоучитель программиста. — М.: Кудиц — образ, 2002. 432с.

89. Погребной Д.В. Визуальное проектирование архитектуры многопроцессорной вычислительной системы реального времени. В кН.: Математическое и программное обеспечение САПР. Вып. 1 Томск: ТПУ, 1977.-С. 17-22.