Автоматизированное проектирование СБИС на базовых матричных кристаллах — страница 10

существующие алгоритмы размещения и трассировки могут не найти полную реализацию объекта проектирования на БМК. Возможна ситуа- ция, когда алгоритм не находит размещение всех элементов на крист- алле, хотя суммарная площадь элементов меньше площади ячеек на кристалле. Это положение может быть обусловлено как сложностью формы элементов, так и необходимостью выделения ячеек для реализа- ции транзитных трасс. Задача

определения минимального числа макро- ячеек для размещения элементов сложной формы представляет собой известную задачу покрытия. Возможность отсутствия полной трассировки обусловлена эврист- ическим характером применяемых алгоритмов. Кроме того, в отличие от печатных плат навесные проводники в матричных БИС запрещены. Поэтому САПР матричных БИС обязательно включает средства корректи- ровки топологии. При этом в процессе

корректировки выполненяются следующие операции: выделение линии содиняемых фрагментов; измене- ние положения элементов и трасс с контролем вносимых изменений; автоматическая трассировки указанных соединений; контроль соот- ветствия результатов трассировки исходной схеме. Уже сейчас акту- альной является задача перепроектирования любого фрагмента тополо- гии. Для матричных БИС таким фрагментом может быть канал для трас-

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

контролируется соот- ветствие топологии исходной принципиальной (логической) схеме. Не- обходимость данного вида контроля обусловлена корректировкой топо- логии, выполненной разработчиком, поскольку этог процесс может сопровождаться внесением ошибок. В настоящее время известны два способа решения рассматриваемой задачи. Первый сводится к восста- новлению схемы по топологии и дальнейшему сравнению ее с исходной. Эта задача

близка к проверке изоморфизма графов. Однако на практи- ке для ее решения может быть получен приемлемый по трудоемкости алгоритм ввиду существования фиксированного соответствия между не- которыми элементами сравниваемых объектов. Дополнительная слож- ность данной задачи связана с тем, что в процессе проектирования происходит распределение инвариантных объектов (например, логичес- ки эквивалентных выводов элементов),