Классификация параметров проектируемых объектов.

 

В описаниях проектируемых объектов фигурируют переменные и их параметры. Среди переменных выделяют:

           - фазовые переменные - характеризуют физическое или информационное состояние объекта.

Параметры разделяют на ряд групп. К их числу можно отнести следующие:

           - внешние параметры - характеризуют свойства внешней по отношению к исследуемому объекту Сравнение нескольких полиномиальных и экспоненциальных функций

 

Таблица 1 позволяет сравнить скорости роста нескольких типичных среды;

Полиномиальные алгоритмы и труднорешаемые задачи

 

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

· полиномиальный алгоритм;

· экспоненциальный алгоритм.

Полиномиальный алгоритм (полиномиальной временной сложности) - это алгоритм, временная сложность которого определяется выражением O[p(n)], где p(n) - полиномиальная функция, n - входная длина.

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

 

Таблица 1.

 

Функция временной	Размерность,n
сложности	10	20	30	40	50	60
n	10-5 с	2*10-5 с	3*10-5 с	4*10-5 с	5*10-5 с	6*10-5 с
n2	10-4 с	4*10-4 с	9*10-4 с	16*10-4 с	25*10-4 с	36*10-4 с
n3	10-3 с	8*10-3 с	27*10-3 с	64*10-3 с	125*10-3 с	216*10-3 с
n5	0,1 с	3,2 с	24,3 с	1,7 мин	5,2 мин	13,0 мин
2n	0,001 с	1 с	17,9 мин	12,7 дней	35,7 лет	366 столетий
3n	0,059 с	58 мин	6,5 лет	3855 столетий	2*108 столетий	1,3* 1013 столетий

 

Быстродействие ЭВМ 1000000 операций в секунду.

 

Таблица 2.

Быстродействие ЭВМ
106	108	109
N1	100*N1	1000*N1
N2	10*N2	31,6*N2
N3	4,64*N3	10*N3
N4	2,5*N4	3,9*N4
N5	N5+6,64	N5+9,97
N6	N6+4,19	N6+6,29

 

полиномиальных и экспоненциальных функций. Различие между типичных полиномиальными и экспоненциальными алгоритмами проявляется более убедительно, если проанализировать влияние увеличения быстродействия ЭВМ на время работы алгоритма. Таблица 2 показывает, насколько увеличится размер задач, решаемой за 1 час, если быстродействие возрастет в 100 и 1000 раз. Видно, что для функции 2n увеличение скорости вычислений в 1000 раз приводит лишь к тому, что размер задачи, решаемой на ней за 1 час возрастет на 10. Функция временной

сложности

n2

n2

n2

n2

2n

3n

 

NP-задачи

 

Выделено 2 класса трудно решаемости:

1. Для отыскания решения требуется экспоненциальное время.

2. Искомое решение настолько велико, что не может быть представлено в виде выражение, длина которого ограничена некоторым полиномом. Эти задачи в курсе рассматриваться не будут.

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

NP-полная задача - это задача, к которой сводится за полиномиальной время любая задача из класса NP-задач. Фундаментальные исследования и теорию NP-задач разработал С.Кук в 1971 году. Им определено понятие сводимости за полиномиальное время. Если одна задача сводится за полиномиальное время к другой, то любой полиномиальный алгоритм - решение другой задачи может быть превращен в полиномиальный алгоритм первой задачи.

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

 

Существуют 6 основных классов NP-полных задач:

1. Задачи выполнимости.

2. Трехмерное сочетание.

3. Вершинное покрытие.

4. Поиск клики.

5. Гамильтонов цикл.

6. Разбиение.

 

           - внутренние параметры - характеризуют свойства элементов ;

           - выходные параметры - характеризуют свойства систем;

           - ограничения выходных параметров.

 

ПРИМЕР 3.

 

Применительно к операционному усилителю:

а) переменные

           - фазовые переменные - напряжение и токи всех ветвей (рассматриваются как функции времени или частоты);

б) параметры

           - внешние параметры - напряжения источников питания, параметры входных сигналов и нагрузки, температура окружающей среды;

           - внутренние параметры - номиналы резисторов, барьерные емкости и тепловые токи переходов в транзисторах, емкости конденсаторов;

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

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

 

Применительно к вычислительной системе:

а) переменные

           - фазовые переменные - состояния отдельных устройств;

б) параметры

           - внешние параметры - параметры входных источников заявок;

           - внутренние параметры - емкости запоминающих устройств, быстродействие процессоров, число каналов;

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

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

При блочно-иерархическом подходе внутренние параметры k -го уровня являются выходными параметры (k+1) -го уровня. При многоаспектном рассмотрении систем, включающих физически разнородные подсистемы, роль внешних переменных для данной подсистемы играют фазовые переменные других подсистем. Они влияют на рассматриваемую подсистему.

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

 

4. Классификация проектных процедур.

 

Классификация проектных процедур приведена в табл.1.

 

ТАБЛИЦА 1. ПРОЕКТНЫЕ ПРОЦЕДУРЫ

АНАЛИЗ	СИНТЕЗ
Одновариантный               Многовариантный	Параметрический     Структурный
Статики                                Чувствительности     Динамики                             Статистический   В частной области               Расчет зависимостей                                                         выходных параметров Стационарных режимов    от внутренних и внешних                                                        параметров Устойчивости	Расчет внутренних параметров   Оптимизация параметров   Оптимизация допусков   Оптимизация технических требований

 

В процедурах анализа оцениваются варианты построения объектов, а в процедурах синтеза - разрабатываются.

Одновариантный анализ заключается в определении вектора выходных параметров Y при заданных:

           - структуре системы,

           - значениях векторов параметров элементов X,

           - значениях внешних параметров Q.

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

Приемлемость полученных значений выходных параметров из вектора Y определяется путем сопоставления их со значениями параметров из вектора T, указанных в техническом задании (ТЗ).

Требуемое по ТЗ соотношение между значениями параметров y_i и t_i , i=1,n называют условием работоспособности по параметру y_i.

Условия работоспособности могут быть представлены в следующем виде:

         y_i <= t _i,     (1)

         у_i >= t _i,     (2)

              

         t_нi <= y _i <= t_вi (3)

 

Задачи многовариантного анализа заключаются в определении изменений вектора Y при заданных изменениях векторов X и Q.

К типовым процедурам многовариантного анализа относятся следующие:

           - анализ чувствительности - оценка влияния внутренних и внешних параметров на выходные. При этом осуществляется расчет коэффициентов чувствительности;

           - статистический анализ - оценка закона и (или) числовых характеристик распределения вектора Y при заданных статистических сведениях о распределении случайного вектора Х.

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

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

В большинстве маршрутов проектирования процедуры синтеза и анализа находятся во взаимосвязи. На рис. 2 показана схема типового маршрута проектирования.

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

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

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

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

Если не удается получить удовлетворительные результаты, ставится вопрос относительно коррекции ТЗ.

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

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

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

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

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

 

Формирование или корректировка ТЗ

Выполнены требования ТЗ

Изменять параметры элементов

Изменять структуру

Синтез варианта структуры

Изменение параметров X

АНАЛИЗ

 

Выбор исходных значений параметров

                                                         
                                                          От предыдущего этапа проектирования

 

                                                                                   СИНТЕЗ

 

                                                                                   ОПТИМИЗАЦИЯ

 

                                                                                   Оформление технической документации и переход
                                                                                   к следующему этапу проектирования

 

           Рис.2. Схема типового маршрута проектирования

 

СТРУКТУРА САПР

 

Подсистемы САПР

 

проектирующих подсистем.

          - подсистема проектирования деталей и сборочных единиц,

           - подсистема проектирования топологии БИС ,

           - подсистема технологического проектирования.

Примеры обслуживающих подсистем:

           - подсистема графического отображения объектов проектирования,

           - подсистема документирования,

           - подсистема информационного поиска.

В зависимости от отношения к объекту проектирования проектирующие подсистемы делят на:

           - объектно-ориентированные,- объектно-независимые.

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

 

Виды обеспечения САПР

 

В САПР выделяют следующие виды обеспечения:

           - методическое,

           - математическое,

           - программное,

           - техническое,

           - лингвистическое,

           - информационное,

           - организационное.

Методическое обеспечение - документы , в которых определены состав, правила отбора и эксплуатации средств автоматизации проектирования.

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

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

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

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

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

 

 

Уровни САПР

Техническое обеспечение современных САПР имеет иерархическую структуру. Принято выделять следующие уровни:

           - центральный вычислительный комплекс (ЦВК ),

           - автоматизированные рабочие места ( АРМ ),

           - комплекс периферийного программно-управляющего оборудования.

 

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

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

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

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

 

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

В двухуровневых САПР возможны сочетания ЦВК-АРМ, ЦВК-ТК, АРМ-ТК.

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