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

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

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

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

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

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

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

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

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

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

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

Вопрос №16