Оптимизационные задачи на СБИС

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