close

Вход

Забыли?

вход по аккаунту

?

Отчёт 2 [kto](1)

код для вставкиСкачать
Федеральное агентство по образованию
Государственное Образовательное Учреждение Высшего Профессионального Образования
Тверской Государственный Технический Университет
Кафедра Электронных Вычислительных Машин
Лабораторная работа №2
по дисциплине: Конструкторско-Технологическое Обеспечение
Решение задачи покрытия схемы БИС эвристическим алгоритмом при компоновке
Выполнил: Селянкин В.О., ВМКСС - 0603
Проверил: Лебедев В.В.
Тверь, 2009
Задание
Представлена следующая исходная схема:
Она содержит в себе ряд часто повторяющихся участков схем (подсхем), которые можно реализовать в виде отдельных одинаковых модулей, хранящихся в какой-либо базе типовых элементов компоновки (ТЭК). Для реализации задачи покрытия предлагается воспользоваться приложением Euristic. Данное приложение уже содержит некоторую базу ТЭК, но студенту необходимо будет добавить свой ТЭК в существующую базу и затем произвести покрытие данной схемы.
Следующая подсхема должна быть представлена типовым элементом замены, реализованным на отдельной микросхеме (Combi)
Выполнение работы
Результат
Ответы на контрольные вопросы
1. Можно ли отнести эвристический алгоритм к классу последовательных? Обоснуйте ответ
Можно, т.к. эвристический алгоритм моделирует процесс поиска в схеме подсхемы аналогичной модулю заданного набора элементов. При этом элементы схемы просматриваются и включаются в подсхемы последовательно один за другим. Покрываемая схема представляется взвешенным ориентированным мультиграфом , множество элементов которого сопоставляется вершинам А-связи между элементами множества рёбер.
Каждый модуль заданного набора является совокупностью связанных элементов (i-1)-уровня. При этом интерпретируется ориентированным графом , который называется эталоном. Таким образом, заданным наборам элементов сопоставляется множество ориентированных графов , где n - число типов, используемых модулей.
Т.е. при решении задачи покрытия эвристических алгоритмов для каждого эталонного графа , решает задачу его вложения в графсхему G. Если же такой подграф найти не удаётся, то переходим к поиску следующего подграфа . Процесс повторяют до тех пор, пока вся схема не будет покрыта модулями заданного набора или выяснится невозможность этого.
При положительном результате получают вариант состава модулей в виде следующего множества , где - число модулей, используемых для покрытия схемы.
2. Объяснить смысл задачи покрытия
Задача компоновки
Содержательно задача компоновки заключается в определении схемного состава типовых конструкций каждого уровня. Эта задача обычно решается "снизу-вверх", т.е. известна схема соединения элементов i-1-го уровня, необходимо распределить их по типовым конструкциям следующего i-го уровня. Можно выделить два варианта постановки этой задачи: компоновка схемы в типовые конструкции, не имеющие схемной унификации; компоновка схем в модули заданного схемно-унифицированного набора.
Компоновка схем в схемно-унифицированные типовые конструкции называется покрытием. Примером ее может служить задача перехода от схемы электрической функциональной к схеме электрической принципиальной, реализованной на наборе ИС, СИС и СБИС. Покрытие - более сложная задача, чем разрезание, особенно в тех случаях, когда модули набора состоят из связанных элементов. Основной проблемой здесь является установление идентичности модуля и некоторой части схемы (подсхемы).
Алгоритмы покрытия
При описании алгоритмов покрытия будем считать, что в модулях заданного набора имеются все типы элементов покрываемой схемы. Модули наборов (рис. 1) условно разбивают на два класса:
1) модули, состоящие из несвязанных элементов, все входы и выходы которых являются внешними выводами модулей;
2) модули, состоящие из связанных элементов.
Модули, состоящие из несвязанных (а) и связанных (б) элементов.
Эвристический алгоритм моделирует процесс поиска в схеме подсхемы, аналогичной модулю заданного набора. Элементы схемы просматриваются и включаются в подсхему последовательно один за другим, поэтому алгоритм относится к классу последовательных.
3. Объяснить результат работы программы
Покрытая схема представлена шестью элементами, два из которых: Остальные участки схемы заменяются при помощи ТЭК из основной базы:
4. Объяснить смысл целевой функции относительной избыточности реализации (Кизб)
При использовании эвристического алгоритма для каждого графа Hl решают задачу его вложения в граф схемы G. Найденный подграф Glr удаляют из графа G. Если в графе схемы не удается найти подграф Gl, то переходят к поиску подграфа Gl+1 Hl+1. Процесс повторяют до тех пор, пока вся схема не будет покрыта модулями заданного набора или выяснится невозможность этого. При положительном результате получают вариант состава в виде множества Q={ql/l = 1,nреал}, каждый элемент которого ql равен числу модулей l-го типа в схеме, поэлементный состав этих модулей и списки межмодульных и внешних связей. Очевидно, что результат покрытия зависит от порядка вложения Hl в G. Задавая различный порядок вложения графов {Hl/l = 1,n} в граф схемы G, можно сформировать несколько вариантов состава. Выбирают тот из них, который обеспечивает экстремум одной из целевых функций:
,
где kповт-повторяемость модулей; |Yср| - среднее число элементов в модуле; |Yl| - число элементов в модуле l-го типа; kизб - относительная избыточность реализации; |Хlr| - число используемых элементов модуля l-го типа (если Glr Hl); Nреал - число модулей в реализации.
Документ
Категория
Рефераты
Просмотров
94
Размер файла
353 Кб
Теги
лабораторная работа, kto, лаба, отчет, лабораторная
1/--страниц
Пожаловаться на содержимое документа