Вопрос №1 Уровни проектирования

Вид материала

Документы

Содержание На системном уровне На схемотехническом уровне Математической моделью Процесс проектирования Проектное решение Проектная операция Этап проектирования Схемотехническое проектирование Функционально-логическое проектирование Задачи многовариантного анализа Статистический анализ Схема типового маршрута проетирования 1. Методическое обеспечение 4. Техническое обеспечение 5. Лингвистическое обеспечение 7. Организованное обеспечение 1. Центральный вычислительный комплекс ЦВК 2. Автоматизированное рабочее место АРМ 3. Рабочие станции РС Конструкторское проектирование ... Полное содержание

Подобный материал:

• Принципы и задачи проектирования 1 Уровни, аспекты и этапы проектирования, 399.58kb.
• Вопрос №3 Принципы проектирования информационного обеспечения программного комплекса, 2541.91kb.
• Методология анализа и проектирования распределительных каналов, 59.46kb.
• Сущность и предмет менеджмента. Различные трактовки менеджмента, их взаимосвязь. Менеджмент, 39.47kb.
• Список билетов для экзамена по курсу Моделирование и исследование систем, 99.07kb.
• Базы данных, 3110.93kb.
• Технология программирования, 643.21kb.
• А. Е. Стешков методология проектирования металлорежущих инструментов, 74.74kb.
• Вопрос Понятие Экономической интеграции. Уровни и предпосылки интеграции, 977.46kb.
• С. П. Колотовкин организация курсового проектирования, преддипломной практики и дипломного, 276.32kb.

Вопрос №1

Уровни проектирования.


Большинство видов аппаратуры относится к сложным системам, их проектирование характеризуется высокому различию задач, наличием высокого числа вариантов решений, необходимостью учета большего количества факторов, влияющих на конституцию и параметры аппаратуры. Проектирование сложных систем основано на блочно и иерархическом подходе, сущность которого состоит в расчленении представления об объекте проектирования, включающем модели постановки проектируемых задач, проектную документацию и т.д. Цель проектирования – замена малого числа проектируемых задач чрезмерной сложности большим числом задач допустимой сложности. Уровни иерархии проектирования различают степенью детализации представлений об объекте и каждому уровню соответствует свое определение элементов. Части объекта, рассматриваемого как элементы на неком k-уровне описываются как системы на соседнем k+1 уровне. Кроме детализации на иерархические уровни применяют расчленение представлений об объекте по характеру отображаемых свойств, на ряд аспектов.

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

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

На системном уровне в качестве систем фигурируют комплексы, например, ЭВМ, РЛС, СУДО, а качестве элементов – блоки аппаратуры.

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

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

На компонентном уровне рассматривают как системы сами компоненты и рассматривают процессы, проектируемые в схематических компонентах.

Конструкторскому аспекту соответствует своя иерархия конструктивов, включающая уровни описания стоек, рам, панелей, типовых элементов замены (ТЭЗ), дискретных компонентов и микросхем, топологических фрагментов и функциональных схем и отдельных компонентов в кристаллах ИМС.

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

Неотъемлемой частью представлений б объекте при САПР являются математические модели.

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

Каждому уровню и аспекту иерархического описания объекта соответствует свой математический аппарат, соответственно характерной для этого уровня математической модели.

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

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

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

Вопрос №2

Этапы пректирования


Этап проектирования – условно выделяемая часть процесса проектирования, состоящая из одной или нескольких проектных процедур.

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

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

1. Восходящее проектирование – это проектирование снизу вверх, осуществляет в случае выполнения процедуры низких иерархических уровней, предшествует выполнению процедур относящимся к более высоким иерархическим уровням.
   
2. Нисходящее проектирование – это проектирование сверху вниз, и характеризуется противоположной последовательностью выполнения процедур и этапов. Типичная последовательность этапов исходящего проектирования радиоэлектронной аппаратуры, включает в себя системно-техническое проектирование – это анализ тактико-технических требований на проектировании комплекс определенных основ принципов функционирования, разработка структурных схем.
   
3. Схемотехническое проектирование – это разработка функциональных и принципиальных схем.
   
4. Конструкторское проектирование – это выбор формы компоновки и размещения конструктивов трассировка межсоединений, изготовления конструктивов документации.
   
5. Технологическое проектирование – это разработка маршрутов и технологической базы выбора оснастки.
   

Типичная последовательность восходящего проектирования БИС включает в себя:

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

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

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

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

В случае матричных БИС первые 2 этапа относят к проектированию БМК, а последние 2 этапа к проектированию к каждой конкретной БИС.

Вопрос №3

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


Проектные процедуры классифицируются:





Статика Чувствительность расчёт внутренних

параметров

динамика статистичность оптимизация

параметров

частотная область расчёт зависимых оптимизация

параметров от внутреннего допусков

и внешнего воздействия оптимизация

технических требований

стационарный

режим колебаний


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

Одновариантный анализ заключается в определении вектора выхода параметров “y” при заданной структуре системы значащих вектора параметров элементов “x” и внешних параметров Q.

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

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



Задачи многовариантного анализа заключаются в определении изменений параметров Y при заданных изменениях X и Q. К задачам многовариантного анализа относится анализ чувствительности – это оценка влияния внутренних и внешних параметров на выходные, которые сводятся к расчёту коэффициента чувствительность.

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

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

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

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

СХЕМА ТИПОВОГО МАРШРУТА ПРОЕТИРОВАНИЯ




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

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

Различают структурную и параметрическую верификацию.

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

Пример структурной верификации – установление изоморфизмов графов и описывающих топологию и принципиальную электрическую схему РЭУ.

Пример параметрической верификации – установления работоспособность РЭУ путём анализа электрических процессов в учётом конструктивов и технологических параметров, определяемых принятым вариантом размещения и трассировки РЭУ.

Вопрос №4

Структура и принципы построения САПР, РЭУиА.

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

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

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

Вопрос №5


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

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

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

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

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

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

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

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

Вопрос № 6


Уровни САПР РЭУиА

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

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

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

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

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

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

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

Связь с гибким автоматизированным производством.

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

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

Вопрос №7


Конструкторское проектирование РЭУиА и топологическое проектирования БИС.

Конструкторское проектирование – один из важнейших этапов проектирования. При проектировании БИС этот этап носит название топологического проектирования.

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

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

Вопрос №8


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

Основными задачами коммутированно-монтажного топологического проектирования для БИС являются следующие задачи:

1. Компоновка конструктивов i в конструктивы i-1 уровня (компановка микросхем в ячейке, ячеек в блоки, элементов И, ИЛИ, НЕ в корпусах микросхем и т.д.)
   
2. Размещение конструктивов i уровня в конструктивы i-1 уровня (размещение микросхем на плате, ячеек в блоки и т.д.)
   
3. Трассировка монтажных соединений между конструктивами на всех уровнях (соединения микросхем на плате, монтажные и межблочные соединения)
   

Каждая из перечисленных задач реализуется отдельным пакетом программ и может решаться отдельной подсистемой САПР.

Если компановка неавтоматизарована, то информация задается принципиальной схемой, и проектируется на ЭВМ начиная с размещения.

Если размещение неавтоматизировано, то информация задается описанием координат соединительной схемой и на ЭВМ выполняется трассировка и выпуск документации.

Если же все проектирование неавтоматизировано и сделан эскиз топологическими схемами исходной информации служит чертеж, который кодируется на кодировщике и вводится на ЭВМ, где выполняется построение и совмещение чертежей, а также формирование и выпуск конструкторской документации, технологической документации для управления техническими автоматами.

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

Вопрос №9


Алгоритмы компановки.

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

1. Типизация – разбиение схемы на конструктивные элементы или топологические компоненты БИС различных типов и определяют тип их номенклатуры.

2. Покрытие – преобразование исходной схемы в схему соединений модулей, номенклатура которых задана. Это покрытие функциональной схемы из элементов И, ИЛИ, НЕ, набора микросхем 155 серии.

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

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

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

Вопрос №10


Исходные алгоритмы компановки условно разбивают на 5 групп:

1. Алгоритмы, использующие методы целочисленного программирования.
   
2. Последовательные алгоритмы.
   
3. Итарационные алгоритмы.
   
4. Смешанные алгоритмы.
   
5. Алгоритмы, основанные на методе ветвей и границ.
   

Алгоритмы 1 группы могут обеспечивать такое решение, но из-за их сложности и больших затрат машинного времени они не нашли практического применения.

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

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

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

Задача компановки чаще всего решается смешанными алгоритмами в два этапа: начальная компановка – последовательными алгоритмами, а улучшение результатов начала компановки – итерационными для удовлетворению принятых критериев.

Вопрос №11


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

Наборы типовых модулей включают в себя:

1) элементные модули, состоящие из логически несвязанных элементов многоцелевого назначения;

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

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

Математическая формулировка задачи покрытия – пусть задан набор модулей T = (t₁, t₂,…t_n), где n – число типов модулей в наборе. Этот набор характеризуется матрицей А, равной [aij]mn, в которой aij – соответствует числу логических элементов i типа в модуле j типа, а m - общее число типов логических элементов во всех модулях, заданного набора.

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

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

В простом случае задачу отыскания покрытия с минимальным количеством модулей.

Тогда целевая функция примет вид: , где X_j – целое число.

Для минимизации стоимости покрытия используют целевую функцию вида: , C_j – стоимость модулей j типа.

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

Обычно логическую схему представляют ориентированным графом, множество вершин которого соответствует элементам схемы, а множество рёбер связям между элементами. Аналогично каждому модулю поставим в соответствие ориентированный подграф и в результате получим некоторое множество m ориентированных подграфов, соответствующим модулем заданного набора. Задача покрытия формулируется как покрытие графа G= (A,X) подграфами из множества M=(G`1,G`2…G`n).

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

Вопрос №12


Задачи разбиения.

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

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

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

Вопрос №13


Для решения задачи разбиения используется приближённые алгоритмы, которые можно разбить на две группы:

1) Последовательный

2) Итарационный

Последовательные алгоритмы. Задачи разбиения.

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

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

Парные перестановки улучшают первоначальное разбиение, но не обеспечивают достижение оптимального разбиения по 2-м причинам:

1) Из-за ограничения числа элементов участвующих в обмене

2) Из-за наличия в узлах сильно связанных элементов

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

Вопрос №15


Алгоритмы. Задачи размещения.

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

Конструктивные параметры компонентов: форма, геометрические размеры, мощность и т.д.

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

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

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

Правило выбора модуля и его установки определяют конкретными алгоритмами.

Итерационные алгоритмы – в них задается вручную случайным образом или с помощью последовательного алгоритма начальный вариант размещения модулей. Затем на каждой итерации получают различные варианты размещения путем парных групповых перестановок или случайным образом каждый вариант оценивается по определенному критерию. Лучший вариант запоминается. Итерация заканчиваются либо по достижении локального минимума критерия оптимизации, либо по заданному числу итераций. Эффективность итерационного алгоритма зависит от начального размещения, т.к. полученное решение приводит к локальному минимуму оптимизированной функции. Эти алгоритмы приводят к большим затратам времени и памяти ЭВМ, чем последние. Непрерывно-дискретного алгоритма – к ним относятся алгоритмы, основанном на механической или электрической интерпретации задач размещения. При механической интерпретации задачи размещения сводятся к задаче движения математических точек, к положению равновесия при действию на них сил притяжения или отталкивания, которая соответственно пропорционально числу связей между модулями и их размеров. Положение равновесия соответствует оптимальному размещению. При электрической интерпретации связи между модуляциями заменяются проводимостями, а модули узлами некоторой электрической схемы. Для такой схемы составляется уравнение по I и II закону Кирхгоффа. Решение этих уравнений можно преобразовать в оптимальное размещение, что означает возможность при решении задач использовать хорошо разработанные методы анализа минимальных электрических цепей.

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

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

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

Вопрос №16


Алгоритмы. Задачи трассировки.

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

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

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

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

Для печатного монтажа – ширина проводников и расстояние между ними, число проводников, проводимых к первому контакту, максимальное число слоев платы и т.д.

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

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

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

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

Вопрос №17


Решение задачи трассировки в многослойной печатной плате предполагает решения следующих этапов:

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

2. Распределение проводников по слоям.

3. Определение последовательной трассировки проводников в каждом слое.

4. трассировка проводников.

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

2-ой этап выполняется двумя способами:

1) Последовательно проводят соединения до заполнения очередного слоя, после чего переходят к заполнению следующего слоя.

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

2) Подсчитав число пересечений проводников, совмещают в первом слое, а затем проводят распределение по слоям.

3-й этап: Определение порядка трассировки успех трассировки очередного проводника существенно зависит от конфигурации уже проведенных трасс. Для решения этой задачи разработаны эвристические алгоритмы, т.к. задача не формализуется теоретическими методами. Наибольшее распространение получили методы упорядочивания, основанные на оценке длины проводников. Здесь возможны два различных подхода: 1) соединение проводников в порядке возвратности длины отдельных проводников (кратчайшее расстояние между соединенными контактами); 2)соединение проводников в порядке убывания их длины, т.к. более длинные проводники труднее трассировать. С точки зрения минимализации суммарной длины соединений оба подхода дают приблизительно одинаковые результаты. Другие методы упорядочивания связаны с учетом степени величины проводников друг на друга по площади перекрытия минимальных прямоугольников, с подсчетом числа контактов, попадающих в минимальный прямоугольник или другими эвристическими критериями.


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

Вопрос №18


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

Волновой алгоритм (алгоритм Ли) позволяет находить кратчайшие трассы оптимальные по целому ряду параметров и являющиеся универсальными. В волновом алгоритме можно выделить 2 этапа: распределение числовой волны и проведение трассы. На первом этапе всё множество квадратов … поля разделяют на две группы:

- под множество свободных квадратов

- под множество занятых квадратов

Трассы могут проходить только по свободным квадратам причём после проведения трассы все её свободные квадраты считаются занятыми.

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

Характеризуется универсальностью и всегда находит кратчайшую трассу. Главный недостаток этого алгоритма большой объем памяти и большие затраты машинного времени. сокращение затрат памяти и времени ЭВМ можно достичь применяя лучевой алгоритм трассировки.

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

В двух лучевом алгоритме от каждого контакта Xi и Xj распространяются по двум лучам и каждый фронт содержит не более четырех элементов.

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

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

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

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

Особенности трассировки соединений в БИС.

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

Главная цель предварительной трассировки – равномерное распределение цепей бес превышения пропускной способности каналов.

Основным алгоритмом нашедшем широкое применение является волновой алгоритм и его модификации.