Современная электроника №4/2026

ПРОЕКТИРОВАНИЕ И МОДЕЛИРОВАНИЕ 49 WWW.CTA.RU СОВРЕМЕННАЯ ЭЛЕКТРОНИКА • № 4 / 2026 где n(i) – размер множества S(i). Пред- положим, что имеется булевская функция от любой пары элементов разных множеств: B(e(i,k), e(j,l)) = 0 или 1, где i != j, k = = 1,…,n(i), l = 1,...,n(j). Требуется найти наибольшее семей- ство элементов из разных множеств (т.е. не более одного элемента из каж- дого множества) так, чтобы для любой пары таких элементов функ- ция B принимала значение 0. В такой постановке множество S(i) – это набор вариантов фанаутов для i-го пина, а функция B на паре фанаутов от разных пинов равна 0, если они не находятся в DRC-нарушении друг с другом. Разумеется, эту задачу можно решить полным перебором комбина- ций. Однако количество комбинаций экспоненциально зависит от N (даже если размеры множеств ограничены некоторой константой). Задача же поиска максимального совместимо- го набора, в свою очередь, имеет экс- поненциальную сложность от коли- чества комбинаций. Поэтому такой подход не может применяться на практике. Отметим, что частным случаем этой задачи является «задача о максималь- ной клике»: в заданном графе требу- ется найти клику (подграф, у которого любая пара вершин соединена ребром) максимального размера. Действитель- но, если у каждого пина (= вершины графа) имеется только один вариант фанаутов, мы соединяем его ребром с другим пином, если функция B равна 0 на этой паре фанаутов. Тогда клика – это семейство пинов с фанаутами без нарушений DRC. Применения к постановке фанаутов Поскольку даже задача о макси- мальной клике является NP-полной, у нас нет эффективного решения более общей задачи с гарантированно мак- симальным количеством. Однако нетрудно написать алгоритм, который почти всегда (или достаточно часто) находит оптимальное решение. При этом основные вычисления придут- ся на расчёт функции B, т.е. наличие DRC-нарушения между двумя фанау- тами. Этот расчёт квадратично зави- сит от N (если количество вариантов для одного пина ограничено некото- рой константой). Приведём примеры построения фанаутов с использованием наше- го подхода. На рис. 12 ниже нам уда- лось построить на 2 фанаута больше, чем на рис. 4 с использованием пат- тернов. На рис. 13 все наши фанауты состоят из прямых коротких треков, что предпочтительнее, чем разводка с помощью паттернов на рис. 5. Заметим, что оптимальное решение не обязано быть единственным, и мы можем его улучшать, используя дру- гие параметры. Например, мы можем: ● минимизировать суммарную дли- ну фанаутов; ● минимизировать суммарный штраф за «плохое» пад-энтри; ● минимизировать суммарный штраф за несимметричность дифпарных фанаутов и т.д. Это делается путём минимизации соответствующей положительной функции F на множестве фанаутов. При этом мы меняем варианты фана- утов только для найденного «макси- мального» набора пинов. Разумеет- ся, при этом мы должны соблюдать главное требование: не создавать DRC- нарушений. Применения к эскизному трассировщику пучков Задача построения фанаутов – неиз- бежный шаг в рамках развития ЭТП, а именно: пользователь селектиру- ет некоторый набор нетлайнов меж- ду пинами и рисует эскиз на каком- то слое ПП. Если все пины находятся на этом слое или являются сквозны- ми, можно сразу запускать механизм однослойной трассировки вдоль эски- за. Если же какие-то пины на слое эскиза отсутствуют, нам требуется вначале построить фанауты для таких пинов. При этом оказалось, что мож- но решить более общую проблему, описанную выше. Однако в приложе- нии к ЭТП задача имеет свою специ- фику. Например, появляются допол- нительные требования к семейству фанаутов: ● желательно, чтобы фанауты по воз- можности были направлены в сто- рону эскиза; ● желательно «распутать» имеющие- ся конфликты между нетлайнами; ● желательно не создавать конфлик- ты внутри каждой дифпары. Прокомментируем последние два пункта с помощью рис. 14. Предполо- жим, что нам надо развести пучок из 4 нетлайнов между SMD-пинами на слое Рис. 14. Пучок из четырёх нетлайнов Рис. 16. Разводка четырёх нетлайнов для фанаутов с учётом конфликтов Рис. 18. «Мягкие» конфликты нетлайнов между фанаутами Рис. 15. Разводка четырёх нетлайнов для фанаутов без учёта конфликтов Рис. 17. «Жёсткий» конфликт нетлайнов между фанаутами