Вероятностная аппроксимация задачи размещения

Ложкин, Сергей Андреевич; Романов, Д.С.; Готманов, Александр Николаевич; Дайняк, А.Б.; Западинский, А.Б.; Шуплецов, Михаил Сергеевич

Главная Авторы Статьи Год проведения Тематика Организации Конференция МЭС

Авторы

Год публикации

2008

УДК

621.38

Аннотация

Рассматривается задача размещения комбинационных логических сетей на плоскости при условии минимизации задержки на критическом пути.
Узлы сети моделируются точками на плоскости, а соединения – отрезками прямых линий. Задержка пути
определяется, как сумма квадратов длин соединений
(отрезков), его составляющих. Поскольку даже в столь упрощенной форме задача размещения остается вычислительно сложной, для ее решения авторы предлагают перейти к приближенной постановке, в которой комбинаторный функционал задержки замещается многочленами от координат узлов сети на плоскости. Для построения аппроксимации используется вероятностная модель распространения сигнала, при который каждый путь может быть критическим с некоторой вероятностью. В качестве целевых функций выбираются математическое ожидание и дисперсия задержки на случайном
критическом пути. Предлагаемая аппроксимация существенно снижает требования к вычислительным ресурсам и обладает рядом других интересных свойств. Авторы полагают, что алгоритмы на ее основе могут применяться на начальной фазе физического синтеза для предварительного размещения логических сетей и вычисления оценок задержки.

Ключевые слова

задача размещения

Ссылка на статью

Ложкин С.А., Романов Д.С., Готманов А.Н., Дайняк А.Б., Западинский А.Б., Шуплецов М.С. Вероятностная аппроксимация задачи размещения // Проблемы разработки перспективных микро- и наноэлектронных систем - 2008. Сборник научных трудов / под общ. ред. А.Л.Стемпковского. М.:ИППМ РАН, 2008. С. 132-135.

Адрес статьи

http://www.mes-conference.ru/data/year2008/20.pdf