Математика \ Дискретная математика

Основные понятия теории графов. Изолированная и висячая вершина. Основные задачи теории графов. Проблемы надежности, страница 8

6.  Окончательная верификация проекта.

7.  Изготовление опытных образцов.

Итого: 1,5 – 3 месяца, а проектирование на стандартных элементах – в несколько раз больше.

Комбинированные БИС.

1.  Цифроаналоговые.

Q400 – состоит из 4х частей (3х цифровых, 1ой аналоговой). Из нее можно собрать ЦАП, АЦП, активные фильтры, генератор функций и т.п.

2.  Кристаллы с изменяемой архитектурой.

На кристалле размещаются несколько крупных функциональных элементов, которые раньше выпускались как самостоятельные ИС (отработанная технология).

Алгоритмы автоматизированного проектирования ,.Алгоритмы компоновки, (алгоритмы покрытия и разрезания)

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

1.  берем 2 куска G1 и G2  Для каждой вершины вычисляем αi;

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

2.  Для каждой пары из разных кусков вычисляем bij

Bij – как изменится число внешних связей, если 2 вершины (I иj) поменяются местами bij=ai+aj-2rij

Если все bij<=0 – смысла переставлять вершины нет.

Если есть bij>0, то выбирается максимальная bij, вершина I и j меняются местами и процесс повторяется до тех пор, пока не рассмотрены все нули и при этом не было ни одной перестановки.

Смешанный

Рассматриваются не 2 отдельных куска а их комбинация

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

Критерии получения наиболее благоприятных условий эвристические:

1.  классический – суммарная длина соединений

2.  Максимальная длина соединения

3.  число пересечений проводников

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

5.  параметры связей между элементами

6.  равномерность распределения проводников

7.  равномерность распределения температуры по полю и т.д.

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

1.  алгоритмы решения математических задач, являются моделями задач размещения.

2.  конструктивные алгоритмы начального размещения.

3.  итерационные алгоритмы улучшения начального размещения.

4.  непрерывно-дискретные алгоритмы размещения.

Метод ветвей и границ

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

Для вычисления нижней границы (достигается, если один вектор(r) упорядочен по невозрастанию, другой (d)по неубыванию. Пусть к к-му шагу размещено g элементов.

Тогда ….. бла юла юла фигня какая-то дальше…

Конструктивные алгоритмы начального размещения

Пошаговый алгоритм

+++ Простота

--- Ищет локальное(только у одного элемента) лучшее решение.

На каждом шаге один элемент обретает одну позицию

Задачи на каждом шаге

1.  выбор элемента

2.  выбор позиции для него

Пусть к к-му шагу размещены Ек, ждля каждого уj не принадлежащему к Ек считаем cj=сумма r по i и j. (число связей его с размещенными).

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

Особо оговариваются правило размещения ядра (максимально связанные элементы помещаются в центр)

Итерационные алгоритмы улучшения начального значения

Алгоритм парных перестановок

Критерий замены мест – мин и максеij. Для каждой пары eiej определяется eij. Для макс eij меняем элемент ei с соседним, чтобы он стал ближе к ej. Если количество максимумов уменьшилось, то берем новое размещение, иначе восстанавливаем предыдущее и пробуем другой вариант. В зависимости от начального расположения удается получить от1 до 50% причем основное улучшение за 5 итераций.

Скачать файл