Инструменты представления, анализа и оптимизации логических схем

Актуальность

Одним из основных этапов проектирования цифровой микроэлектронной аппаратуры является логический синтез. Данный этап объединяет разные задачи, связанные с представлением, анализом и оптимизацией логических схем. К их числу относятся:

• трансляция HDL-описания (на языке Verilog или VHDL) в схему (в некотором внутреннем представлении);
• выбор промежуточного базиса и преобразование схемы к выбранному базису;
• оптимизация схемы (минимизация числа вентилей и/или глубины);
• технологическое отображение (выражение функциональности схемы через элементы технологической библиотеки);
• проверка эквивалентности полученной схемы и схемы до применения оптимизации и технологического отображения.

В настоящее время в РФ отсутствуют средства САПР, реализующие логический синтез и применимые для проектов промышленного уровня сложности, что представляет угрозу для технологической безопасности страны. Разработка таких средств является актуальной задачей.

Цель проекта

Разработка инструментов представления, анализа и оптимизации логических схем промышленного уровня сложности.

Задачи проекта

Изучение подходов к решению задач логического синтеза:

• трансляция формальных языков;
• генерация арифметических схем;
• преобразование базиса логических схем;
• оптимизация логических схем;
• технологическое отображение;
• проверка эквивалентности;

Проектирование инструментов (подсистем САПР) и разработка прототипов:

• подсистема трансляции;
• функциональная библиотека;
• подсистема преобразования базиса;
• подсистема оптимизации схемы;
• подсистема технологического отображения;
• подсистема проверки эквивалентности;
• уточнение интерфейсов и оптимизация алгоритмов;
• реализация инструментов и их интеграция в Utopia EDA (ИСП РАН);
• тестирование и анализ эффективности инструментов;
• разработка комплекта документации.

Исходные данные проекта

• язык промежуточного представления RTL-моделей;
• прототип внутреннего представления RTL-моделей;
• прототип внутреннего представления логических схем;
• прототип подсистемы трансляции;
• прототип подсистемы оптимизации;
• прототип подсистемы топологического отображения;
• прототип подсистемы проверки эквивалентности.

Этапы работы над проектом

• изучение подходов к решению задач логического синтеза;
• проектирование инструментов (подсистем САПР) и разработка прототипов;
• уточнение интерфейсов и оптимизация алгоритмов;
• реализация инструментов и их интеграция в Utopia EDA (ИСП РАН);
• тестирование и анализ эффективности инструментов;
• разработка комплекта документации.

Текущие результаты

 Исследованы следующие подходы к решению задач логического синтеза:

• методы лексического и синтаксического анализа:

конечные автоматы и рекурсивный спуск;

• генерация префиксных сумматоров:

алгоритм Ладнера-Фишера;

• преобразование базиса логических схем;

представления AIG, XAG, MIG и XMG;

• технологическое отображение:

покрытие графов/деревьев;

• проверка эквивалентности:

SAT-решатели и двоичные решающие диаграммы (BDD);

Спроектированы следующие подсистемы и разработаны прототипы:

• подсистема трансляции:

входные языки: Verilog, BLIF, Liberty

используемые средства: Yosys;

• функциональная библиотека:

генератор сумматора;

• подсистема преобразования базиса:

конструкторы AIG, XAG, MIG (частично);

• подсистема технологического отображения:

предварительная обработка библиотеки;

• подсистема проверки эквивалентности:

проверка с помощью SAT-решателя;

используемые средства: MiniSAT.

Планируемые результаты (на учебный год)

Разработать прототипы следующих подсистем:

• подсистема трансляции:

входные языки: Verilog, BLIF, BENCH, Liberty

• функциональная библиотека:

генераторы сумматоров;

генераторы умножителей;

• подсистема преобразования базиса:

конструкторы AIG, XAG, MIG, XMG;

• подсистема технологического отображения:

покрытие графов/деревьев для AIG;

• подсистема проверки эквивалентности:

проверка с помощью SAT-решателя;

идентификация внутренних точек эквивалентности.

Используемые технологии

• C++
• Yosys
• Генераторы трансляторов (Flex/Bison)
• SAT-решатели (MiniSAT)
• BDD (CUDD)

Заказчик проекта

Федеральное государственное бюджетное учреждение науки Институт системного программирования им. В.П. Иванникова Российской академии наук (ИСП РАН)

Команда проекта

Вершков Максим, программист-стажер (синтез)

Грицун Тимофей, программист C++

Кашинцев Илья, программист C++

Красов Артём, программист C++

Онищенко Елизавета, Программист C++

Романов Никита, программист-стажер (синтез)

Рябов Георгий, программист-стажер (парсеры)

Тюхтяев Гавриил, программист-стажер (парсеры)

Ушаков Александр, программист C++

Ягжов Алексей, Программист-стажер (синтез)

Штокман Алексей, программист-стажер (синтез)