Реферат: Системное автоматизированное проектирование

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

Различают два способа проектирования (два типа маршрутов):

- восходящее проектирование,

- нисходящее проектирование.

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

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

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

ПРИМЕР 1.

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

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

- конструкторское проектирование ( выбор формы, компоновка и размещение конструктивов, трассировка межсоединений, изготовление конструкторской документации);

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

ПРИМЕР 2.

Этапы восходящего проектирования БИС:

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

- схемотехническое проектирование ( синтез принципиальной электрической схемы, оптимизация параметров элементов, статистический анализ применительно к типовым ячейкам БИС);

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

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

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

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

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

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

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

Таблица 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
N 1	100*N1	1000*N1
N 2	10*N2	31,6*N2
N 3	4,64*N3	10*N3
N 4	2,5*N4	3,9*N4
N 5	N 5 + 6,64	N 5 +9,97
N 6	N 6 + 4,19	N 6 + 6,29

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

сложности

n2

n2

n2

n2

2n

3n

N P -задачи