Algorithms for Functional Correction of Boolean Circuits

 
Avtaikina M.A., Shupletsov M.S. (Lomonosov Moscow State University)
 
Abstract - During the IC design process, functional specifications are often modified late in the design cycle, after placement and routing are completed. However, designers are left either to manually process such modifications by hand or to restart the design process from scratch - a very costly option. Functional correction is an automated way of detecting logic difference between a modified high-level specification and an implemented design and generating patch-circuit to resolve the difference. But analyzing an entire designs is not always practical for large-scale circuits because of their size and complexity. Partitioning the design, based on two designs’ correspondence, can significantly reduce the complexity of the analysis. In this paper, a new algorithm for functional correction is described. With partitioning large designs into corresponding smaller designs, our algorithm is able to identify multiple logic differences and modify the existing design minimally such that the new specification can be realized. The specification change is carried out within minimal time because of small sizes of analyzed designs. Experiments show that this technique successfully implement ECO while preserving the most part of the existing logic. The size of generated patch does not exceed the sum of sizes of small designs, which hold the logic differences. Unlike the most of previous methods, the developed system can process functional correction for a design of around 100K gates in less than half an hour.

Keywords - Boolean circuits, logic synthesis, partitioning, equivalence checking, functional correction, engineering change order, Boolean matching.

Алгоритмы решения задачи функциональной коррекции схем из функциональных элементов

 
Автайкина М.А., Шуплецов М.С. (МГУ им. М.В. Ломоносова, г. Москва)
 
Аннотация - Согласно статистике более 60% ошибок проектирования интегральных схем (ИС) связано с функциональным несоответствием схем их первоначальным спецификациям. При обнаружении таких ошибок на финальных стадиях проектирования ИС, их исправление влечет за собой большие затраты, связанные с восстановлением функциональности и перепроектированием схемы. Исправление схему вручную является очень трудоемкой задачей, а запуск маршрута проектирования с начала требует существенного времени. Функциональная коррекция представляет собой автоматизированный подход к решению данной проблемы. Она заключается в формировании небольшой подсхемы-заплатки, внедрение которой в уже синтезированную схему позволяет исправить все обнаруженные логические несоответствия. При этом не требуется заново повторять все этапы логического синтеза, что существенно сокращает время проектирования схемы. В данной работе представлен алгоритм функциональной коррекции, в основе которого лежит идея разбиения схем на соответствующие друг другу подсхемы. Ввиду того, что описания современных ИС обладают большим размером и сложностью, анализ указанных описаний как единого целого требует значительных вычислительных ресурсов. Разбиение исходных схем на подсхемы меньшего размера позволяет существенно снизить сложность рассматриваемой задачи. Эксперименты показали, что представленный алгоритм успешно справляется с локализацией и исправлением неисправностей в схеме.

Ключевые слова - схемы из функциональных элементов, логический синтез, разбиение схем, функциональная коррекция, поиск функциональных соответствий.