Главная
страница 1
УДК 681.5;519.16;519.68
ПРОЕКТИРОВАНИЕ САПР КАК РАСПРЕДЕЛЕННОЙ ИНФОРМАЦИОННО-ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ

В.В. Малыгин, В.Б. Силин
В статье обосновывается необходимость построения САПР в виде вычислительной сети, проектирование которой приводит к комбинаторной задаче распределения вычислительного процесса САПР по множеству взаимосвязанных компьютеров. Предлагается схема формализации задачи распределения, производится анализ ее основных свойств и указываются возможные методы решения.
Внутреннее содержание проектной деятельности в системах автоматизированного проектирования (САПР) разделяют, с одной стороны, на «формальную постановку задачи проектирования с методами поиска решения», а, с другой стороны, на «...организацию вычислительных процессов» [1], анализу основных характеристик и задач которой в большей степени и посвящена данная статья.

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

В соответствии с каноническим определением ГОСТов (комплекс стандартов системы 23501 и более позднего комплекса ГОСТ34) основным назначением систем автоматизации проектирования является со­про­во­ж­де­ние ка­ж­до­го проектного дей­ст­вия сред­ст­ва­ми ма­те­ма­ти­че­ско­го, про­грамм­но­го, ин­фор­ма­ци­он­но­го, организационного и про­чих обес­пе­че­ний. Однако со времени своего появления претерпевали изменения не только техника реализации САПР, но и представления о роли и задачах самого автоматизированного проектирования. Сегодняшний список требований, предъявляемых к САПР, сложился под влиянием перехода к комплексному или сквозному проектированию, основной задачей которого является уменьшение сроков выхода новой продукции на рынок и снижение косвенных проектных расходов. Их основой является вывод о необходимости интеграции в САПР различных «computer-aided» инструментов систем управления проектом, жизненным циклом, составом работ организации типа CALS, PDM и т.д [2].

Разнородность предъявляемых к САПР требований, охватывающих в этом случае как непосредственное проектирование, так и вопросы управления документацией, ответственности исполнителей, контроля качества, обеспечения и поставок и т.д., оз­на­ча­ет рост чис­ла и раз­но­род­но­сти це­ле­вых и кри­те­ри­аль­ных функ­ций системы, что обу­слав­ли­ва­ет рас­пре­де­лен­ный ха­рак­тер вы­чис­ли­тель­но­го про­цес­са САПР. Основанием этому, с одной стороны, служит то, что увеличение числа и разнородности це­ле­вых и кри­те­ри­аль­ных функций, вызывающее рост пространств их аргументов и параметров, приводит к чрезмерно большому размеру совместной системы их уравнений, ее сильной разряженности и определенным трудностям работы с ней, обуславливающим ее декомпозицию и рас­пре­де­лен­ный ха­рак­тер решения. С другой стороны, эту же тенденцию отмечает М. Холстед, который, опираясь на теорию алгоритмов, информации, и такие критерии, как безошибочность программного обеспечения (ПО), минимальность его объема, психология программиста и т.д., делает вывод о необходимости деления сложного ПО на модули и определяет соотношения для разбиения программ, которые «легче всего составлять, отлаживать, понимать и поддерживать» [3].

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

Вопросы общей постановки задачи синтеза структуры распределенной вычислительной системы зависят, прежде всего, от выбираемых критериев ее оценки, существенное влияние на которые в САПР должна оказывать минимизация удельных затрат на передачу в ней информации. Это объясняется, во-первых, значительностью объемов циркулирующей в распределенной вычислительной системе информации содержания операндов (переменные, данные), которые вместе с операторами (команды, приказы) составляют основу любой программы и находятся в четкой функционально-метрической зависимости [3]. Во-вторых, к аналогичному выводу можно прийти, рассматривая проектирование по Ю.Х. Вермишеву как «процесс преобразования данных технологического задания и базовой нормативно-справочной информации в требуемую техническую документацию на проектируемый объект» [1], а САПР как канал без шума, пропускная способность которого по основной теореме Шеннона есть (Н – энтропия получаемого проектного решения, Т – время проектирования, k – отношение объема ТЗ, справочной, нормативной, директивной и другой информации к объему полученного проектного решения), которая, при очевидном значении k>>1, определяет величину нагрузки на сеть передачи данных в САПР. Вышеперечисленные аргументы и итеративность вычислительного процесса проектирования не только определяют объемность передаваемой в САПР информации, но и показывают, что на непосредственное проектирование (расчеты, моделирование и прочее) инженер в среднем тратит только 20% рабочего времени, тогда как остальное время уходит на создание, изменение и поиск различной информации [4].

Вопросы минимизации объемов сетевого трафика или его удельной стоимости, как правило, исследуются в рамках теории расписаний, потоковых и топологических задач, в различных разделах математического программирования. Однако основной чертой постановок задач в этих работах является фиксированное расположение источников и приемников информации, которыми в вычислительной сети являются отдельные элементы вычислительного процесса (процессы или нити в каждой вычислительной машине и т.п. – смотри, например, формальную модель в работе [5, 7]), решающие частные задачи (ЧЗ), а варьируемыми параметрами становятся параметры сети, путей в ней и т.п. Обратный подход, наиболее естественный для проектирования крупномасштабных САПР (см. различные Grid-проекты [8]) и возможности вариации в ней места решения частных задач, в литературе практически не рассмотрен, что делает исследование способа регулирования информационного обмена путем должного распределения ЧЗ важным и актуальным.

Основой применения наиболее строгих математических методов решения любой задачи является предварительная формализация ее элементов, декомпозиционный характер которых в задачи распределения (по крайней мере, – частных задач) делает целесообразным использовать в этих целях аналог агрегативного описания, предложенного Н.П.Бусленко [4], что позволяет описать задачу следующим, относительно «стандартным», образом. Перед распределенной вычислительной системой Q, состоящей из конечной, N-узловой вычислительной сети, поставлена общая задача F, которая в силу сложности не может быть решена ни на одной из ее отдельных узловых машин. Решение общей задачи предполагается провести после декомпозиции F ее на конечное число m менее сложных частных задач (ЧЗ) fi(Xi,Yi), где i(1,m) -индекс частной задачи, Xi – мно­же­ст­во не­за­ви­си­мых вход­ных пе­ре­мен­ных – ар­гу­мен­тов частной за­да­чи fi, Yi – мно­же­ст­во ее выход­ных пе­ре­мен­ных. Количественные характеристики совокупности частных задач – сложность fi и объем ее операндов Xi,Yi опишем на основе муль­ти­гра­фа об­щей за­да­чи FГF(F,T), где F – мно­же­ст­во ча­ст­ных за­дач fi чис­лом M, вы­пол­не­ние ко­то­рых тре­бу­ет в лю­бом уз­ло­вом вы­чис­ли­те­ле ВС вы­чис­ли­тель­но­го ре­сур­са |fi| ; Т – мно­же­ст­во ин­фор­ма­ци­он­ных от­но­ше­ний, ка­ж­дое из ко­то­рых яв­ля­ет­ся пе­ре­да­чей эле­мен­тов пе­ре­мен­ных из Х или Y ча­ст­ных за­дач. Свойства вы­чис­ли­тель­ной среды предлагается формализовать как граф ГN(N, L), где N – мно­же­ст­во уз­лов гра­фа или мно­же­ст­во се­те­вых вы­чис­ли­те­лей чис­лом N, вы­чис­ли­тель­ный ре­сурс ко­то­рых |ni|, L – мно­же­ст­во вет­вей гра­фа или мно­же­ст­во се­те­вых со­еди­не­ний «точ­ка-точ­ка» с удель­ной стои­мо­стью пе­ре­да­чи от­но­ше­ний ls, s(1-L).

Надежность и удобство операций управления и общего ввода-вывода системной информации накладывает на вычислительную сеть САПР ограничение в том, что только один из ее N уз­лов может осу­ще­ст­в­ля­ть ввод ин­фор­ма­ции в сис­те­му из внеш­ней сре­ды, а дру­гой (мо­жет быть тот же узел) осу­ще­ст­в­ля­ет вы­вод ин­фор­ма­ци­он­ных эле­мен­тов ре­ше­ния из сис­те­мы. С другой стороны, индивидуальные особенности поставленной задачи позволяют сделать ряд допущений. Допущение 1 - основываясь на общности соотношений для максимального размера модуля программы по Холстеду, зададимся одинаковой сложностью |fi| всех частных задач системы. Допущение 2 - основываясь на соображениях удешевления общей стоимости системы, зададимся равенством вы­чис­ли­тель­ных ре­сурсов |ni| всех узлов сети. Допущение 3 - основываясь на допущение 1, и наличии объективных соотношений между сложностью, размером программы и числом ее операндов, зададимся тем, что все значения Т находятся в диапазоне от 0 (отсутствие всякого обмена) до tMAX. (Можно показать, что допущения 1 и 2 формируют наиболее сложную оптимизационную задачу и являются предельным случаем для иных постановок задач, сведение которых к данной происходит при увеличении размерности задачи). Наконец учитывая использование в структурной функции алгоритмов поиска наикратчайших путей исключающих из использования сильнонагруженные каналы сети и практику ценообразования в IP-сетях связи сделаем последнее Допущение 4 на равенство веса дуги в ГN либо 1 (присутствие канала связи), либо 0 (его отсутствие).

Произведенные допущения позволяют записывать ГF матрицей информационных потоков (МИП), совпадающей с матрицей инцидентности графа, метка связи в которой описывает количество передаваемой между ЧЗ информацией, а ГN матрицей вычислительной сети (МВС), совпадающей с матрицей инцидентности графа, метка связи в которой описывает удельную стоимость информации, передаваемой между инцидентными вершинами. Искомое распределение R определяется как объединение (комбинация) бинарных отношений r, в соответствии с которыми каждому элементу множества вершин графа ГN ставится в соответствие единственная вершина графа ГN, причем каждой вершине графа ГN соответствует от одной до К вершин графа ГF, где К – округленное до ближайшего целого частное от деления М на N. Множество взаиморазличных распределений R формирует комбинаторное пространство Z. Решением задачи является такое подпространство zZ, все точки которого приводят структурную функцию (СФ) в минимум, где значение СФ рассчитывается как сумма удельной стоимости всех информационных потоков в сети, объем которых определяется графом задачи, а наиболее дешевый путь в сети и его суммарная стоимость – графом сети.

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

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

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

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


Список литературы

1. Вермишев Ю.Х. Методы автоматического поиска решений при проектировании сложных технических систем. - М.: Радио и связь, 1982. - 152 с.

2. Bill Gascoigne. PDM: The Essential Technology for Concurrent Engineering. - http://www.pdmic.com/articles/artetfce.html (22.02.2001).

3. Холстед М.Х. Начала науки о программах. - М.: Финансы и статистика, 1981. - 128 с.

4. Бусленко Н.П. Моделирование сложных систем. - М.: Наука, 1978. – 400 с.

5. Месарович М., Такахара Я. Общая теория систем: математические основы. - М.: Мир, 1978.-312 с.

6. Цвиркун А.Д. Основы синтеза структуры сложных систем. - М.: Наука, 1982. – 200 с.

7. Смелянский Р.Л. Модель функционирования распределённых вычислительных систем // Вестник МГУ. Сер.15, Вычислительная математика и кибернетика, 1990. - №3.

8. I. Foster, C. Kesselman. The Grid. Blueprint for a New Computing Infrastructure. - Hardback, 1998. – 701 р.

СВЕДЕНИЯ ОБ АВТОРАХ



Силин Владимир Борисович, профессор кафедры радиоэлектроники Московского авиационного института (государственного технического университета), д.т.н., Телефон: 158-42-01

Малыгин Владимир Вячеславович, аспирант кафедры радиоэлектроники Московского авиационного института (государственного технического университета),

e-mail: v_malygin@hotmail.com






Смотрите также:
Проектирование сапр как распределенной информационно-вычислительной системы
93.03kb.
1 стр.
Вопросы коллоквиума 2 по курсу «Проектирование распределенных баз данных»
19.77kb.
1 стр.
Статья посвящена реализации мероприятия «разработка общероссийской системы информационно-маркетинговых центров» федеральной целевой программы «Электронная Россия»
209.36kb.
1 стр.
Этапы развития вычислительной техники и программного обеспечения. Структура вычислительной системы
40.41kb.
1 стр.
Швейная промышленность, №5, 2005 Критерии оценки сапр
114.7kb.
1 стр.
Курсовая работа «Проектирование вычислительной системы»
320kb.
1 стр.
Классификация сапр в зависимости от отраслевого назначения выделяют: mcad
27.43kb.
1 стр.
Лекционного курса по дисциплине «сапр в отрасли»
46.47kb.
1 стр.
Лекция Нулевое администрирование Windows (zaw)
218.42kb.
1 стр.
Визуальный пользовательский интерфейс в распределенной вычислительной сатурн-среде
57.65kb.
1 стр.
Изучение информационной системы Solidworks
342.13kb.
1 стр.
Информационно-измерительные и управляющие системы (промышленность) Формула специальности
39.77kb.
1 стр.