Алгоритм трассировки соединений по каналам

Эта трассировка обеспечивает одновременную трассировку всех соединений.
Предполагается регулярное расположение элементов на монтажном поле и наличие как вертикальных, так и горизонтальных каналов (пример - ПЛИС). Изделия, на которых применяется данный алгоритм, должны иметь квадратную структуру (например, матричные БИС). Пропускной способностью канала будем называть ограничение на количество магистралей в канале.

Этапы: 1. Предварительная трассировка
Цель: равномерно распределить соединения по каналу, не допуская их перегруженности.
Для каждой цепи строится минимальное остовное дерево. Все полученные конфигурации накладываются на сеть каналов, затем подсчитывается загруженность каждого участка канала. Если некоторые участки оказываются перегруженным, то...
а) (итерационный подход) для тех цепей, вследствие которых произошла перегрузка, строят минимальное остовное дерево с исключением этого участка (обычно хватает двух-трех итераций).
б) (динамический подход) обозначим через γ_i коэффициент загрузки i-го участка канала (количество назначенных проводников), а через β_i - текущую пропускную способность на i-ом участке (таким образом, γ_i+ β_i - изначальная пропускная способность канала). Для каждой цепи определяют сеть каналов, по которой может быть осуществлено соединение. Создав такую сеть для каждой цепи, они (сети) накладываются на основную сеть каналов. Определяется верхняя граница загруженности каждого канала. Для каждого участка рассчитывается весовая функция следующим образом:

, где индекс is относится к участку s канала i, l_a,b - длина участка, k ∈ [0, 1] - коэффициент. Далее для каждой цепи при помощи волнового алгоритма строится трасса соединений с учетом весовых значений P(a, b).

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

Все проводники соединений, назначенные на i-й канал, сортируются по начальной координате. Первый отрезок фиксируется на магистрали, следующим на эту же магистраль помещается тот отрезок, у которого начальная точка ≥ конечной точки первого отрезка, и так далее. Закрепленные отрезки удаляются из списка, после чего процесс повторяется с новой магистралью.

m₂: