Сетевая организация структуры САПР

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

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

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

Большое количество и разноплановость требований, предъявляемых к САПР, вместе с распределенностью ее вычислительной системы позволяет отнести САПР к так называемым сложным системам. Известны различные подходы к синтезу сложных систем, использующие методы декомпозиции, координации и агрегации, развиваемые М. Месаровичем, Н. П. Бусленко, А. Д. Цвиркуном и др., которые связывают его в первую очередь со структурным синтезом, что и определило направление исследований диссертационной работы, связанное со структурным проектированием распределенной вычислительной системы САПР.

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

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

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

— Исследование основных свойств САПР с обоснованием комбинаторного характера задачи структурного синтеза ее распределенной информационно-вычислительной сети.

— Разработка формальной модели информационно-вычислительной сети (ВС) САПР.

— Исследование свойств множества возможных вариантов распределения вычислительного процесса САПР.

— Исследование свойств функции качества вариантов распределения вычислительного процесса САПР.

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

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

На научную новизну претендуют:

1. Способ формализации распределенной информационно-вычислительной системы на основе матрицы информационных потоков (МИП) ее информационно-вычислительного процесса, матрицы вычислительной сети (МВС) системы, матрицы точки комбинаторного пространства (МТКП) как искомой структуры системы, структурной функции (СФ) оценки их качества и самого комбинаторного пространства (КП) допустимых структурных решений.

2. Установленные количественные характеристики КП возможных решений задачи распределения — мощность, диаметр и размер единичной шаровой окрестности точек КП.

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

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

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

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

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

Работа состоит из введения, четырех глав и приложения.

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

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

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

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

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

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

4.6. Выводы.

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

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

Исследование свойств сходимости структурной функции позволило:

— исследовать статистические свойства области комбинаторного пространства Э сходимости СФ к глобальному экстремуму;

— установить влияние, оказываемое на статистические свойства 8 таких характеристик, как топология графа сети и плотность МИП графа задачи;

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

— 131 -ЗАКЛЮЧЕНИЕ.

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

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

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

2. Предложен способ формального представления вычислительного процесса САПР как множества взаимодействующих подпрограмм и вычислительной среды их функционирования, основанный на Матрице Информационных Потоков (МИП) и Матрице Вычислительной Сети (МВС), а также предложен способ описания структуры информационно-вычислительной системы в виде Матрицы Комбинаторной Точки (MKT).

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

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

5. Аналитическим путем установлены зависимости определения верхней и нижней границы структурной функции для группы задач с МИП одинаковой плотности и характер их изменения с ростом размерности исследуемой распределенной системы. Предложены.

— 132эмпирические процедуры оценки границ значений структурной функции для каждой задачи этих групп.

6. Установлена экспоненциально возрастающая сложность использования при решении поставленной оптимизационной задачи единственного практически доступного метода точного решения — полного перебора.

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

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

Применение разработанных методов.

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

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

По результатам работы опубликовано 8 статей.

Результаты диссертационной работы обсуждались на 3-й международной конференции «Интерактивные системы: Проблемы человеко-компьютерного взаимодействия» (Ульяновск, 1999), на заседании кафедры «403, Цифровая и вычислительная техника», рабочих группах кафедр «304, Вычислительных машин, систем и сетей», «604, Системный анализ и управление» (МАИ, Москва, 2001), на учебном спецсеминаре «Синтез архитектур вычислительных систем и планирование вычислений» (МГУ, Москва, 2002).

— 133.