LEX (664761), страница 2
Текст из файла (страница 2)
ЭТАП ПРОЕКТИРОВАНИЯ - условно выделенная часть процесса проектирования, состоящая из одной или нескольких проектных процедур. Обычно этап включает процедуры, которые связаны с получением описания в рамках одного аспекта и одного или нескольких уровней абстрагирования. Иногда в процессе проектирования выделяют ту или иную последовательность процедур под названием "маршрут проектирования".
Этапы, в свою очередь, делятся на процедуры и операции.
ПРОЦЕДУРА - формализованная совокупность действий, выполнение которых заканчивается проектным решением.
ПРОЕКТНОЕ РЕШЕНИЕ - промежуточное или окончательное описание объекта проектирования, необходимое и достаточное для рассмотрения и определения дальнейшего направления или окончательного проектирования.
При проектировании возможны различные последовательности выполнения процедур и этапов.
Различают два способа проектирования (два типа маршрутов):
- восходящее проектирование,
- нисходящее проектирование.
Восходящее проектирование (снизу-вверх) имеет место, если проектируются типовые объекты, предназначенные для использования в качестве элементов во многих объектах на более высоких уровнях иерархии (например, серийные микросхемы, стандартные ячейки матричных больших интегральных схем).
Нисходящее проектирование охватывает те уровни, на которых проектируются объекты, ориентированные на использование в качестве элементов в одной конкретной системе.
Проектированию свойственен итерационный характер. При этом приближение к окончательному варианту осуществляется путем многократного выполнения одной и той же последовательности процедур с корректировкой исходных данных. Итерации могут охватывать различные части проектирования, включающие как несколько операций, так и несколько этапов.
ПРИМЕР 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 |
| 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 при заданных:
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
