С развитием микропроцессорной и телекоммуникационной техники появилась возможность размещать средства обработки информации вблизи мест зарождения исходных данных и их использования [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]. Задачаопределения числа станций и их размещения, ставится как задача линейного программирования, но уже для территории размещения станций, представленной сеткой размерностью 20×50, число переменных достигает одного миллиона. Задача получения плана использования ресурсов в [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] обусловлена тем, что она совмещена с задачей размещения станций и распределения по ним терминальных точек. Совместное решение этих задач продиктовано стремлением минимизировать суммарную стоимость станций и кабеля для подключения терминальных точек. Однако есть ряд сомнений в целесообразности такого подхода. В частности, минимально возможное число станций определяется не только необходимостью подключения всех терминальных точек, но и способностью выполнять программную нагрузку в установленное время. Число станций, определяемое вторым условием, очевидно, может не совпадать с числом, полученным ранее по первому условию. В этом случае совместное решение задач теряет смысл.
В диссертации минимальное число станций, способных подключить все терминальные точки, определяется с помощью задачи покрытия, для решения которой имеется эффективный алгоритм. Далее осуществляется проверка способности данной совокупности станций своевременно выполнять программную нагрузку. При необходимости число станций увеличивается и после этого решается задача их размещения по критерию минимальной суммарной длины кабеля на подключение терминальных точек. Центральное место здесь занимает транспортная задача, которая также имеет эффективный алгоритм решения.
Что касается задачи распределения программной нагрузки по станциям, то учитывать топологию сети при ее решении и, тем самым, существенно усложнять задачу, по-видимому, не имеет смысла. Во-первых, общий объем данных, передаваемых между станциями сети, не зависит от ее топологии, а во-вторых, заведомо предполагается, что в этом случае топология сети должна быть определена до решения задачи распределения программной нагрузки. Но это противоречит естественной последовательности задач, в которой топология зависит от объема передаваемых данных, а объем в свою очередь — от распределения программной нагрузки.
Такая последовательность решения задач реализована в диссертации. Предварительно условия функционирования объекта управления отображаются на ТПД. В итоге строится информационный граф, который отражает объем всех передач данных между модулями ГПД. Задача распределения программной нагрузки рассматривается как задача разрезания информационного графа на минимально связанные подграфы. Вариант разрезания определяет объем передаваемых данных, на основе которого осуществляется выбор топологии сети. При этом, как показано в диссертации, сокращение общего времени на передачу данных достигается за счет изменения топологии сети так, чтобы данные в сети могли передаваться параллельно.
Методика решения данной задачи позволяет осуществлять выбор топологии сети и привязку станций к магистралям сети, обеспечивающие максимальный объем параллельно передаваемых данных, что соответствует сокращению общего времени на передачу данных. Несмотря на наличие ряда недостатков, таких как использование сравнительно простых вариантов топологии и применение схем перебора, ценность методики заключается в том, что она дает возможность формализованного перехода от программной нагрузки к топологии сети.
