Математические и программные средства построения архитектуры и топологии сети вычислительной системы для управления территориально распределенными объектами

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

Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

кандидата технических наук: Погребной, Александр Владимирович
город: Томск
год: 2008
специальность ВАК РФ: 05.13.11
цена: 450 рублей

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

Автореферат диссертации по теме "Математические и программные средства построения архитектуры и топологии сети вычислительной системы для управления территориально распределенными объектами"

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

Погребной Александр Владимирович

Математические и программные средства построения архитектуры и топологии сети вычислительной системы для управления территориально распределенными объектами

05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой оргепъи^ ДО» кандидата технических наук

Томск - 2008

003456323

Работа выполнена в Томском политехническом университете

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

доктор технических наук, профессор Силич Виктор Алексеевич

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

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

кандидат технических наук, доцент Хабибулина Надежда Юрьевна

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

Новосибирский государственный технический университет

Защита состоится «24» декабря 2008 г. в 14-30 часов на заседании Совета по защите докторских и кандидатских диссертаций Д 212.269.06 при Томском политехническом университете по адресу: г. Томск, ул. Советская 84, институт «Кибернетический центр» ТПУ.

С диссертацией можно ознакомиться в Научно-технической библиотеке Томского политехнического университета по адресу: г. Томск, ул. Белинского 55.

Автореферат разослан «/$>. // 2008 г.

Ученый секретарь диссертационного совета кандидат технических наук, доцент

М.А. Сонькин

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Метод решения задачи размещения станций на территории расположения объекта управления.

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

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

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

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

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

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

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

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

управления. Эту зависимость удалось установить аналитическими методами на начальной стадии проектирования до привлечения трудоемких систем моделирования.

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях: Восьмой Российско - Корейский международный симпозиум по науке и технологии (The 8 Russian-Korean International Symposium on Science and Technology) «KORUS 2004» (г. Томск, ТПУ, 2004г). Конференция «Молодежь и современные информационные технологии» (г. Томск, ТПУ,2004г). Девятый Российско-Корейский международный симпозиум по науке и технологии (The 9 Russian-Korean International Symposium on Science and Technology) «KORUS 2005» (г. Новосибирск, НГТУ, 2005г). Международная конференция «Современная техника и технологии» (г. Томск, ТПУ ,2006г). Международная конференция «Современная техника и технологии» (г. Томск, ТПУ ,2007г).

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 96 наименований. Каждая глава сопровождается выводами. Общий объем диссертации составляет 171 страницу машинописного текста, включает 67 рисунков и 6 таблиц.

Основное содержание работы

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

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

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

тех или иных данных. Форма ГТТД используется в работе также для представления модели алгоритма функционирования объекта управления.

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

Совокупность терминальных точек ТП обозначим множеством Е,

Е~{]ЕГ, ПЕг =0, \Ег\ = Ьг,г = ],2.....Я, где Ег - подмножество точек г-го

типа в множестве Е; Ьг - число точек г-го типа в множестве Е; Я- число типов точек на ТП.

Число видов станций, которые могут быть использованы для построения вычислительной системы, обозначим величиной 5. Для станций 5 -го вида введем вектор подключения точек Л = {<?„}> г = 1,2,...,Л, ¿ = 1,2,...,^, где а„- допустимое число мест подключения терминальных точек г-го типа в станции л -го вида.

Способность станций подключать терминальные точки согласно векторам А, представим матрицей Л = ||а„|| , г = 1,2,...,Я, 5 = 1,2.....5.

Введем переменную 5 = 1,2,...,5, которая определяет число станций ^-го вида, используемых при подключении точек множества Е. Тогда задачу определения минимального числа станций необходимых для подключения всех точек множества Е можно записать в виде:

£*,=>гшп; (1)

¿а,л>6г ,г = 1,2,...,Д; (2)

1=1

^-положительное целое число для всех 5 = 1,2,...,5. (3)

Задача (1)-{3) относится к классу задач целочисленного линейного программирования. Величины ап и Ьг в ограничениях (2) - положительные числа, часто и целые, для многих приложений - булевские. Благодаря этой специфики, данная задача стала более известной как задача покрытия. В рассматриваемом приложении задачу можно представить как задачу покрытия терминальных точек множества Е заданного вектором В = {Ьг}, векторами подключения станций А, ={<*„}.

В результате решения задачи (1)—(3) получим вектор X' = {**},5 =1,2,...,5, компоненты х' которого определяют минимальное число

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

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

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

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

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

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

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

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

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

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

Для формирования расширенной совокупности «хороших» множеств предложено три алгоритма а1га2,а3. Каждый из них реализует некоторое эвристическое правило, настроенное на учет определенной специфики ТП конкретного объекта управления. Так, алгоритм а, ориентирован на ТП с множеством точек Е одного типа и относительно равномерным расположением точек. Если множество Е содержит несколько типов точек, то каждое из подмножеств Ег также должно быть распределено на ТП равномерно. Применение алгоритма а2 более эффективно, если число типов точек Л велико и условия равномерности распределения для множества Е и подмножеств Ег не накладываются. Алгоритм а3 занимает промежуточное положение между алгоритмами а, и а2, и отличается способом формирования множеств.

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

max{ £ 4(e„eA)}. ' (4)

Здесь а((е,,ед) - расстояние отточки е, до полюса еЛ. Вторая и все последующие точки ер множества яг, выбираются по условию

d(e',e ) = шах mind(e„e ). (5)

Точка е* принимается в качестве очередного полюса и включается в множество я-,. Число полюсов соответствует числу станций Р либо увеличивается разработчиком в К раз, где К, как правило, принимается равным числу R.

Для каждого р-го полюса в точке ер е кх и станций s-го вида,

s = l,2,...,S, формируется множество Eps, точки которого по типам соответствуют вектору подключения As станции s-го вида и удалены от полюса ер на минимальные расстояния. Здесь S - число видов станций, для которых х* >0. В итоге для всех полюсов будет сформировано множеств Eps,

р = 1,2,.-Kl, J = l,2,...,5.

В алгоритме а2 множества Eps формируются непосредственно после определения очередного полюса ер по выражению (4). Среди множеств £ , s =1,2,...,5 сформированных для данного полюса выбирается множество Е'р, с минимальной оценкой

(I d{enep))lj^ars. (6)

Далее величина x's уменьшается на 1 и из множества Е исключается множество Е'р!. Очередной полюс выделяется на множестве E\E'ps. Последующее формирование множеств Eps и выбор среди них множества с минимальной оценкой (6) осуществляется аналогично. Процесс заканчивается, когда для всех станций будут выделены полюса и соответствующие множества E'ps Заметим, что число полюсов |тг2|, выделяемых алгоритмом а2, равно числу станций Р. При этом для каждого полюса формируется S множеств Eps. Таким образом общее число множеств Е , формируемых алгоритмом а2, составит |тг2|5 .

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

которого принимается равной Множество Ер исключается из множе-

ства Е и процесс выбора второго полюса из точек Е\ер с формированием соответствующего множества Ер повторяется. .

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

Число полюсов ¡л,], полученное по алгоритму а3, совпадает с числом станций Р. Для каждого полюса ерел3, по аналогии с алгоритмами а, и а2, формируются множества Ер! и включаются в расширенную совокупность.

Таким образом с помощью алгоритмов а1га2,а3 можно сформировать расширенную совокупность множеств Ер!. Число множеств в совокупности определяется величиной <т = фг, | + |я"21 + \лъ . Например, если число станций Р = 6, число видов станций 5 с х\ > О равно 4, а коэффициент кратности ЛГ = Д = 3,то а = (ЯР + 2Р)Б = (3*6 + 2*6)4 = 120.

Для каждого множества Е определяется «центр» ес с минимальным суммарным удалением ср! от точек е, е Ерз, ср1 = ¿/(<гс,е,). Величина

с'р1 =тахср5-ср принимается в качестве оценки множества ЕрГ

Р»3

Принадлежность точек е, еЕ, 1 = 1,2,...,т множествам Ер1 представим матрицей = Ца^Ц, I = 1,2,...,/и, /7 = 1,2,...,п, .у = 1,2,Здесь элемент а,^ = 1, если точка е, еЕр!, а1р! = 0, если е,£Ер!, т = \Е\, п = \л\ = \жх\+\7!2\+\7съ\.

Введем переменную хр1=1, если множество Ер, включено в решение, ^=0 в противном случае. Тогда задачу выбора множеств Ер по критерию максимальной суммы их оценок с можно записать в виде:

л Я

та= (7)

р=1 5=1

( = 1,2.....т.-, (8)

я=11=1

^=1,2,...,5.

(9)

р=1

Задача (7) - (9) относятся к классу задач линейного математического программирования с булевыми переменными и имеет специфику. Переменные хр! ограничением (9) разбиваются на 5" групп. Для каждой группы заведомо известно число х* переменных хр!, которые будут выбраны для размещения станций.

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

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

Распределение точек по станциям, полученное в результате решения задачи (7) - (9) не может быть принято окончательным. В частности, условие (8) допускает подключение не всех точек множества Е к станциям. Кроме того возможно перераспределение точек между станциями, улучшающее критерий (7). Исходя из этого после решения задачи (7) - (9) осуществляется оптимизация распределения точек по станциям. Замечено, что решение данной задачи можно выполнять отдельно для точек каждого подмножества Ег.

Число точек в множестве Ег для практических задач может измеряться сотнями. Поэтому в целях дальнейшего сокращения размерности задачи множество Ег предварительно разбивается на подмножества Ег у = 1,2,...,»»;

компактно расположенные на ТП, IЩ = Е, П = 0, Е1 # 0. Компактность множества Е/ будем оценивать величиной ^ = £у/|£;|. Среди возможных алгоритмов формирования множеств Е/ с заданной граничной оценкой компактности воспользуемся способом разбиения, которое получается путем

наложения на ТП регулярной сетки с фиксированным шагом, как это показано на рис. 1.

Рис. 1. Пример ТП с множествами Ер? и наложением сетки

Иллюстративный пример ТП, приведенный на рис. 1, содержит 20 точек трех типов, обозначенных символами ( ). Вектор X содержит три ненулевых компоненты х'2 = 2, х' = = 1. Станции Sj соответствует вектор подключения А{ = { }, станциям s2,s} - {•••▲А}, станции s4 - { }. Совокуп-

ность точек г - го типа в j - ой ячейке принимается компактным множеством Ej. На рис. 1 множества Ej выделены в тех ячейках сетки, которые содержат точки, обозначенные символом (• ). Номера j в таких ячейках проставлены в нижнем правом углу, j = 1,2,...,6.

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

V m

Задача Т': тт/, = ]Г]Г cvjxvj;

v=l >1

£X=öv> v = l,2,...,F;

V—\

Здесь xvj - число точек множества , подключаемых к станции v; cv/ — расстояние между станцией v и центром множества ; av — число мест подключения точек г - го вида в станции v; bj - число точек г - го вида, составляющих множество .

Задача Т' полностью соответствует классической форме записи задачи транспортного типа. Условие равенства объемов производства и объемов по-

V m

требления здесь также соблюдается: = .

j=1

На рис. 2 приведена схема «перевозок» транспортной задачи Т', построенная для примера ТП на рис. 1.

а, = 2 а2 = 3 а3 = 3

Рис. 2. Пример схемы «перевозок» для задачи Т* 13

Пункты производства с объемами а„ соответствуют трем станциям, содержащим точки типа (•) (а, = 2, аг = 3, а3 = 3), а пункты потребления с объемами

шести ячейкам сетки ТП, содержащим точки типа ( • ).

Общее оптимальное решение задачи распределения точек множества Е складывается из решений задач Т* для множеств Ег. Заметим также, что в диссертации данная задача формулируется и для условий, когда сетка на ТП не накладывается. Получаемая при этом задача Т, отличается от Т' тем, что в ней пунктами потребления являются точки множества Ег и, соответственно, величины Ь1=\.

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

Пусть на ТП задано множество точек 0 = {е;},( =1,2,...,«. Разобьем подмножество Q на совокупность множеств <2^ / = 1,2,...,т, так, что:

м=\,2.....т. (ю>

Будем рассматривать разбиения, получаемые для условия = V, то есть \т = п.

Выражение (10) в этом случае задает совокупность УУ разбиений, которые можно сравнивать между собой. Введем оценку разбиения ме^1.

= , К1 = ¿(е(,е°), где ¿(е„е°) - расстояние от точки е, до центра е] М '¡Щ

множества

Разбиение {б}}« назовем компактным, если среди всех разбиений IV ему соответствует величина Я^ = шш . Используются также относительные оцен-

В ряде случаев вместо оценок Л удобнее пользоваться оценками Ь, которые определяются суммами расстояний между точками в множествах QJ:

т _

В относительных величинах данные оценки имеют вид:

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

точек множества Q¡ до его центра. Вторая оценка используется при разбиении

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

Более глубоко исследованы оценки Я и Ь. Экспериментально была показана возможность их совместного применения и взаимозаменяемость. Так на рис. 3, показана зависимость оценок Я н Ь от параметра т, построенная для разбиений на множестве Q с и = 30. Из рис. 3 следует, что разбиение, выбранное как лучшее по оценке £, является лучшим и по оценке Я.

Для получения разбиения м> е1У по критерию минимизации оценки в работе предложен оригинальный алгоритм, который включает следующие операции. По алгоритму а, формируется т полюсов. Полюса принимаются центрами и относительно них решается задача Т, распределяющая точки множества <2 по данным центрам. В результате получается исходное разбиение множества Q на множества Qj, ] = 1,2,...,/я. В каждом множестве QJ определяется

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

1 р«**:: Метрик I

| » Зин, Я ■ Вцаг.иа I "]

Рис. 3. Пример сопоставления оценок Я^ и Ь^

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

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

Качество ЛК - разбиения предложено оценивать относительно некоторого «идеального» разбиения. Вводится понятие «идеального» разбиения и дается алгоритм вычисления для него оценки компактности Д,,. Оценка Яа принимается в качестве граничной оценки компактности. По ней можно судить о степени приближения полученного Ж - разбиения к компактному.

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

Информационный граф задает объемы передач данных между вершинами ГПД за один цикл моделирования и строится на основе ГОД и условий функционирования объекта управления. На рис. 4 приведен пример информационного графа с параметрами, полученными для цикла моделирования в 10 тактов.

Д=5 б

20 20

40 40

10 10 2

Рис. 4. Пример информационного графа и матрицы

Данные с1ч пронумерованы в кружках, а номера модулей /т проставлены рядом с планками. Число на дуге обозначает частоту передаваемых по ней данных за один цикл моделирования. Рядом с входными данными указаны условия их поступления. Для выходных данных указывается число тактов цикла обнов-

ления. На основе указанных параметров для каждого ребра графа определяется вес г - объем данных, передаваемых между вершинами dq и fm за один цикл

моделирования, rqm = pqpmcqm. Здесь pq - размер памяти, занимаемый данным

dq\ рт— частота выполнения модуля fm в цикле моделирования; cqm — число

состояний данных dq, передаваемых между вершинами dq и fn в соответствии

с условиями селекции. Матрица R =||'"?т|| на рис. 46 получена для значений

рт =>{10,5,2,5,1} и ^ =>{2,3,1,2,4,2,1,1,1}, с43 = 5, с5>4 = 2, для остальных дуг

= 1 •

срп

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

Пример графа передач данных для шести станций, построенный для информационного графа, содержащего 26 вершин, показан на рис. 5. Общий объем данных, передаваемых в сети rw, для варианта разрезания weW, в данном примере составляет 155 единиц. Если пропускную способность магистрали сети обозначить величиной <р, определяющей. объем данных, передаваемый за один такт моделирования, то для успешной работы локальной сети на базе одной магистрали, должно выполняться условие rw/(p<pt'k. Здесь р. - число максимальных циклов обновления выходных данных t'k, принятое при задании цикла моделирования.

Рис. 5. Пример графа передачи дан- Минимально необходимое число

ных магистралей в сети определяется от-

ношением (rwl <p)l jut'k с учетом округления результата в большую сторону. Так, для нашего примера, при rw =155, (р = 10, t*k = 12 имеем (155/10)/12= 1,3. Таким образом, в сети должно

быть не менее двух магистралей. Из библиотеки базовых сетей выбирается вариант сети, построенной на двух магистралях. Сеть и вариант подключения к ней шести станций показаны на рис. 6а. На рис. 66 приведена матрица наличия конфликтов Ô = ||<7VJ> полученная для данной сети и графа передач данных (рис. 5).

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

ребром. Элемент 1, если пары станций ребер V и к при передаче данных в сети имеют конфликт по доступу к магистрали, с/л = 0, в противном случае. В матрице Q выделены строки и столбцы, у которых все элементы д„к=1,

13 1

36 45 56

23 24 35 36 45 56

ЙЛ- 1

1 ./1 У 1 1 . Ж; ; и-

1 М'\- 1 1 1 1

1 д 1 1 1

1 1 у. -■■г;;

1 1 1

г-; м-;? 1 1 1

1 / IV 1 1 1

Рис. 6: а - вариант подключения станций к базовой сети; б - матрица наличия конфликтов 9

Диаграмма совмещения передач данных для принятого варианта подключения станций к магистралям сети приведена на рис. 76. Для удобства построения диаграммы матрица <2 представлена графом (рис. 7а). Из диаграммы следует, что общая загрузка сети с учетом совмещения передач данных составляет 90 единиц или 90/10=9 тактов, что укладывается в цикл моделирования ^ =12 тактов.

14 23 35

24.

0 10 20 30 40 50 60 70 80 90

Рис. 7: а - граф матрицы О; б - диаграмма совмещения передач

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

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

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

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

Разработка программных средств выполнена в среде Borland Delphi 7.0 для операционной системы Windows ХР. Суммарный объем исходного текста программ составил более 6000 тысяч строк. Описание программных средств сопровождается окнами с результатами их работы. Подробно изложено применение программных средств для анализа наземной метеорологической наблюдательной сети Росгидромета. Приведены результаты решения задачи выбора первичных и вторичных каналов связи в данной сети.

Основные результаты работы

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

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

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

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

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

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

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

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

Основные публикации по теме диссертации

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

2. Погребной A.B. Построение модели для топологически распределенной динамической системы. - Кибернетика и вуз, вып. 30 , Томск, Изд-во ТПУ,2003.-С. 82-86.

3. V.K.Pogrebnoy, A.V.Pogrebnoy. Efficient placement of stations of topo-logically distributed multiprocessing computing systems. In. Proc. 8th Korean-Russia International Symposium on Science and Technology (KORUS-2004), Vol.. 1, pp.137-141,2004.

Погребной В.К., Погребной A.B. О рациональном размещении станций топологически распределенных многопроцессорных вычислительных систем.

4. Погребной A.B. Задача определения числа станций многопроцессорных систем управления. Доклады II Всероссийской научно-практической конференции студентов «Молодежь и современные информационные технологии». Февраль 2004 г. Томск: изд-во ТПУ, 2004.

5. Pogrebnoy A.V. The solution of a multiplanimetric problem of traveling salesman at the analysis of territorially distributed technical system. Proceedings of the 9 Russian-Korean international symposium on science and technology.— Novosibirsk, 2005.

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

6. Погребной A.B. Выбор архитектуры локальной сети при проектировании распределенной системы реального времени.//Современные техника и технологии: Труды IX Международной научно - практической конференции молодых ученых. - Томск, 2006. - Т.2.

7. Погребной A.B. Определение числа и топологии размещения станций многопроцессорной вычислительной системы.// Известия Томского политехнического университета. - 2006. - Т.309.№7 - С.160-164.

8. Погребной A.B. Задача топологической децентрализации в территориально распределенных технических системах.//Современные техника и технологии: Труды X Международной научно - практической конференции молодых ученых. - Томск, 2007. - Т.2.

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

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

Подписано к печати 19.11.2008. Тираж 110 экз. Кол-во стр. 21. Заказ № 55-08 Бумага офсетная. Формат А-5 Печать RISO. Отпечатано в типографии ОСЮ «РауШмбх» Лицензия Серия ПД № 12-0092 от 03.05.2001г. 634034, г. Томск, ул. Усова 7, ком. 046 . тел. (3822) 56-44-54

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

ВВЕДЕНИЕ.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

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

С развитием микропроцессорной и телекоммуникационной техники появилась возможность размещать средства обработки информации вблизи мест зарождения исходных данных и их использования [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 из них в журнале «Известия Томского политехнического университета», рекомендованном ВАК.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение диссертация на тему "Математические и программные средства построения архитектуры и топологии сети вычислительной системы для управления территориально распределенными объектами"

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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.

Похожие работы

Информатика, вычислительная техника и управление
05.13.00