Моделирование длин цепей интегральных схем на этапе размещения элементов
Электроника
Abstract
Так как на этапе размещения элементов интегральных схем (ИС) еще не известны топологические структуры цепей и, следовательно, их длины, то для оценки задержек сигнала в будущих межсоединениях возникает необходимость моделирования длин цепей ИС. Наличие таких моделей позволяет управлять процессом размещения элементов с точки зрения быстродействия. Основными требованиями для таких моделей являются быстрота и точность оценки длин будущих цепей.
С точки зрения точности, наиболее близкие к фактическим длинам цепей оценки выдает модель дерева Штейнера, так как она положена в основу используемых в автоматизированных системах электронного проектирования алгоритмов трассировки. Однако, поскольку модель Штейнера имеет NP сложность и ее решение требует большого машинного времени, ее применение на этапе размещения неэффективно.
В существующих программных инструментах размещения элементов ИС наибольшее применение получила полупериметрическая модель оценки длин цепей. Она является упрощенной моделью Штейнера и основана на построении ограничивающей контакты данной цепи минимальной прямоугольной рамки и определении ее полупериметра. Однако точность этих моделей убывает с ростом количества контактов цепи.
В условиях растущей интеграции ИС появляется необходимость разработки новых и усовершенствованных моделей оценки длин цепей, которые, с одной стороны, повысят точность оценки, с другой - потребуют относительно небольшого времени оценки.
В настоящей работе предложены новый метод и алгоритм моделирования длин цепей ИС, которые, имея O(nlogn) сложность, по точности превышают полупериметрическую модель и приближаются к точности модели минимального дерева Штейнера. Предложенный метод основан на том, что точность полупериметрической модели для цепей, имеющих не более трех контактов, совпадает с точностью модели минимального дерева Штейнера. Предлагается разбить монтажное поле цепи на области, содержащие не более трех контактов, с дальнейшей оценкой длины цепи каждой области по полупериметрической модели и дальнейшим соединением этих областей, применяя известные методы построения минимальных связывающих деревьев.
