саит)

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

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

1 2 3 4 5

1. Непрерывно дискретные алгоритмы

Градиентные методы.

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

Нахождение экстремума целевой функции с помощью градиентного метода.

Достоинства:

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

Недостатки:

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

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

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

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

Достоинства:

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

Недостатки:

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

Эти методы наиболее эффективны для размещения разногабаритных элементов.

2. Дискретные алгоритмы.

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

Алгоритмы случайного поиска

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

Достоинства:

Последовательный быстрее, но не найдет целевого экстремума.

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

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

Достоинства:

Много стандартных методов для решения подобных задач.

Недостатки:

Трудоемкость решений при большой размерности

Эвристические методы.

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

Достоинства:

небольшое время решения задач.

Недостаток:

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

III. Трассировка сигнальных соединений.

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

Классификация алгоритмов трассировки

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

Наиболее простой подход реализует метод ортогональной трассировки.

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

Процесс повторяется до достижения контактом приемника.

Замечание: преимущественным направлением может быть не только вертикальное и горизонтальное, но любое другое.

Достоинства: очень высокое быстродействие.

Недостаток: он применим для плат с невысокой плотностью сигнальных соединений.

Эвристический алгоритм трассировки

Волновой алгоритм трассировки

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

λ_пп= λ_имсη_имс+ λη+ λ_мпη_мп, где λ - …, η

4	Х	Х	7	6
3	2	3	•В	5
2	1	2	3	4
1	А•	Х	Х	5
2	1	Х	Х	6

Blog

Обеспечение производства ЭВМ базовые понятия (сапр/астпп/саит)