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

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

Авторы
 Ложкин С.А.
 Романов Д.С.
 Готманов А.Н.
 Дайняк А.Б.
 Западинский А.Б.
 Шуплецов М.С.
Год публикации
 2008
УДК
 621.38

Аннотация
 Рассматривается задача размещения комбинационных логических сетей на плоскости при условии минимизации задержки на критическом пути.
Узлы сети моделируются точками на плоскости, а соединения – отрезками прямых линий. Задержка пути
определяется, как сумма квадратов длин соединений
(отрезков), его составляющих. Поскольку даже в столь упрощенной форме задача размещения остается вычислительно сложной, для ее решения авторы предлагают перейти к приближенной постановке, в которой комбинаторный функционал задержки замещается многочленами от координат узлов сети на плоскости. Для построения аппроксимации используется вероятностная модель распространения сигнала, при который каждый путь может быть критическим с некоторой вероятностью. В качестве целевых функций выбираются математическое ожидание и дисперсия задержки на случайном
критическом пути. Предлагаемая аппроксимация существенно снижает требования к вычислительным ресурсам и обладает рядом других интересных свойств. Авторы полагают, что алгоритмы на ее основе могут применяться на начальной фазе физического синтеза для предварительного размещения логических сетей и вычисления оценок задержки.
Ключевые слова
 задача размещения
Ссылка на статью
 Ложкин С.А., Романов Д.С., Готманов А.Н., Дайняк А.Б., Западинский А.Б., Шуплецов М.С. Вероятностная аппроксимация задачи размещения // Проблемы разработки перспективных микро- и наноэлектронных систем - 2008. Сборник научных трудов / под общ. ред. А.Л.Стемпковского. М.:ИППМ РАН, 2008. С. 132-135.
Адрес статьи
 http://www.mes-conference.ru/data/year2008/20.pdf

Copyright © 2009-2018 ИППМ РАН. All Rights Reserved.

Разработка сайта - ИППМ РАН