Задание
Разработать программную реализацию алгоритма размещения: последовательный метод.
Цель работы
Целью настоящей работы является изучение и исследование задачи оптимизации размещения последовательными методами, применяемыми в САПР ЭВА и БИС и использующими универсальные модели для формального задания структуры соединений объектов и топологических характеристик монтажного пространства.
Введение
В настоящее время во всём мире наблюдается резкое увеличение производства электронно-вычислительной аппаратуры (ЭВА) и повышение её возможностей. Особенно это связано с последними успехами в области микроэлектроники. Препятствием повышения качества ЭВА и сокращения сроков её создания является несоответствие между возрастающей сложностью микроминиатюризации ЭВА и устаревшими методами и средствами её конструирования. Разрешить это несоответствие способна новая технология проектирования, связанная с использованием и применением систем автоматизированного проектирования (САПР).
Важнейшую часть ЭВА составляют интегральные схемы, а также большие и сверхбольшие интегральные схемы (БИС и СБИС), процесс проектирования которых становится всё более трудоёмким из-за большого числа (104 – 105) компонентов, расположенных на кристалле микросхемы. В связи с этим разрабатываются и применяются САПР БИС и СБИС, ориентированные на решение задач большой размерности. Важны ми преимуществами САПР БИС и СБИС являются бездефектность и быстрота проектирования интегральных схем, а также невысокие требования к квалификации проектировщика.
Основными этапами проектирования матричных БИС являются: функционально-логическое проектирование, синтез топологии и комплексный контроль (верификация) полученного проекта.
Размещение элементов – одна из основных задач синтеза топологии БИС. При её решении стремятся, с одной стороны, обеспечить условия 100% трассировки соединений, а с другой – минимизировать искажения сигналов в межэлементных связях.
Высокая плотность размещения элементов БИС и СБИС создаёт большие трудности при реализации соединений между элементами. Оптимальное размещение элементов обеспечивает повышение надёжности ЭВА, уменьшение размеров конструктивных единиц, минимизацию взаимных наводок, задержек сигналов, уменьшение общей длины соединений и т.п.
Как известно, в основе матричных БИС лежит специальная заготовка – базовый матричный кристалл (БМК), на котором расположены регулярно повторяющиеся полупроводниковые структуры, представляющие собой группы нескомутированных транзисторов. Таким образом, БИС, отличаются только слоями коммутации. В связи с этим важной задачей при проектировании БИС является оптимальное размещение элементов БИС при заданных внутрисхемных связях.
Основными этапами решения задачи размещения элементов топологии БИС являются: выбор критериев размещения, начальное размещение элементов на БМК, итерационная оптимизация начального размещения. Из-за условности разделения задач размещения и трассировки построить критерий размещения, достаточно точно отражающий условия прокладки соединений, очень трудно.
Единственным "идеальным" в этом смысле критерием является собственно трассировка соединений, как это, например, происходит при ручном проектировании топологии. К сожалению, громадная вычислительная сложность совместного решения задач размещения и трассировки даже для небольших БИС заставляет применять при их конструировании эвристические критерии качества размещения.Это прежде всего различные приближённые оценки тех интегральных параметров трассировки, изменение которых косвенно характеризует условия её проведения при заданном размещении элементов на КП.
К таким параметрам относятся:
- суммарная длина соединений БИС;
- суммарная площадь областей реализации её цепей;
- число трасс, длина которых больше заданной;
- наибольшая длина соединительной трассы на КП;
- число пересечений трасс, принадлежащих различным цепям БИС;
- число соединений простейшей конфигурации и т.д.
В большинстве существующих алгоритмов размещения производится оценка суммарной длины соединений. Разработка новых эффективных математических моделей и алгоритмов размещения также ориентированы на исследование данного критерия.
Существующие алгоритмы оптимального размещения делят на два класса: непрерывно-дискретные и дискретные методы.
При использовании непрерывно-дискретных методов оптимизации задача размещения решается в два этапа: на первом этапе определяют координаты местоположения центров элементов, при которых целевая функция имеет экстремальное значение; на втором – полученные координаты "округляются" в фиксированные целочисленные значения координатной сетки, нанесённой на поверхность коммутационной платы.
Данные методы включают в себя: алгоритмы, использующие градиентные методы; алгоритмы, использующие динамические модели.
В дискретных методах оптимизации модель коммутационного пространства представляют в виде множества фиксированных координат позиций. Задача размещения сводится к сравнению различных вариантов закрепления элементов в этих позициях и выбору того из них, который обеспечивает экстремальное значение целевой функции.
Алгоритмы случайного поиска, алгоритмы назначения относятся к классу дискретных методов оптимизации.
Практическая реализация всех перечисленных алгоритмов размещения связана со значительными затратами машинного времени и памяти ЭВМ. Поэтому для размещения большого числа конструктивных элементов часто используют эвристические алгоритмы (из группы дискретных методов), позволяющие сократить время решения задачи при вполне приемлемом для практики качестве получаемого результата.
В данной работе будет рассмотрен последовательный метод, относящийся к алгоритмам размещения.
Алгоритм размещения: Последовательный метод