Размещение элементов на коммутационном поле кристалла или платы

С точки зрения математической постановки задачи – задача размещения состоит в следующем:

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

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

2. минимум средней длины сигнальных соединений

3. минимум суммарной длины сигнальных соединений

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

5. совместимость с точки зрения минимизации электромагнитных помех

6. рациональное размещение внешних выходов модуля

7. равномерность размещения элементов по полю платы

Пункты 1-3 признаны обеспечить более легкую 100% трассировку сигнальных соединений.

Классификация алгоритмов размещения

1. Непрерывно-дискретные

а) градиентный

б) методы построения динамических моделей

2. Дискретные

а) методы случайного поиска

б) методы назначения

в) эвристические методы

Лекция 7

Непрерывно-дискретные методы

При использовании непрерывно-дискретных методов задача решается в два этапа:

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

2. На втором этапе полученная координата округляется до фиксированного значения координатной сетки (это координата носит дискретный характер)

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

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

Градиент в точке с координатами (x,y,z) – это вектор, длина которого равна наибольшему значению производной по направлению и который направлен так же, как и вектор, соответствующий наибольшему значению производной по направлению в точке с координатами (x,y,z).

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

1. небольшие затраты машинного времени

2. наличие стандартных программ для расчета

Недостатки:

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

2. низкая эффективность при пологом экстремуме

Эффективность этого метода может быть улучшена путем совместного применения с методом случайного поиска (повышает вероятность нахождения глобального экстремума целевой функции).