ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 1, с. 60-72
ДИСКРЕТНЫЕ СИСТЕМЫ
УДК 519.816
ИСПОЛЬЗОВАНИЕ ПРОДУКЦИЙ ДЛЯ АВТОМАТИЗИРОВАННОГО УПРАВЛЕНИЯ ЛОГИЧЕСКИМ ПРОЕКТИРОВАНИЕМ ДИСКРЕТНЫХ
УСТРОЙСТВ
© 2007 г. П. Н. Бибило, В. И. Романов
Белоруссия, Минск, Объединенный ин-т проблем информатики НАН Белоруссии Поступила в редакцию 28.11.05 г., после доработки 01.06.06 г.
Показывается эффективность использования механизма продукций в управлении процессами логического проектирования в системах автоматизированного проектирования дискретных устройств.
Введение. Возрастание степени интеграции цифровых сверхбольших интегральных схем (СБИС) приводит к резкому увеличению размерностей задач логического проектирования дискретных устройств на элементной базе СБИС. Для компактного изложения проектов используются иерархические представления - как способ борьбы со сложностью реализуемых логических схем. В процессе проектирования иерархия описаний проекта подвергается существенной модификации в результате выполнения многочисленных оптимизационных процедур над функциональными и структурными описаниями логических схем и структур СБИС. Эти проектные процедуры различаются областью их применимости, способами выражения исходных и результирующих данных, критериями оптимизации, ограничениями и т.д. На практике при работе с большими проектами появляется необходимость в обходах дерева иерархии проекта и принятии однотипных решений для выполнения большого числа подобных действий.
Для автоматизации управления в системах автоматизированного проектирования (САПР) применяются программы, в которых операнды соответствуют отдельным объектам проекта, а набор операций определяется применяемым языком программирования. В качестве примера можно сослаться на язык TCL [1], используемый в системе синтеза LeonardoSpectrum [2]. Однако программа, предполагающая выполнение пусть даже однотипных действий для сотен объектов проекта, становится нетривиальной. Поэтому в статье предлагается вариант продукционного определения исполняемого процесса проектирования. В этом подходе доступ к объектам проекта осуществляется путем определения их свойств (атрибутов), а не конкретной ссылкой на имя или позицию в некотором перечне. Собственно программирование заменяется формулировкой ряда логических утверждений (продукций) относитель-
но объектов проектирования вида: "Если рассматриваемый объект обладает свойствами у1, у2, ..., у„, то необходимо выполнить действие г". Именно такого рода рассуждениями манипулирует на практике специалист проблемной области (проектировщик) в процессе проектирования. Представлено уточнение предложенных в [3, 4] правил записи продукций и установлен порядок их выполнения, а также приведены практические примеры реализованных стратегий проектирования и некоторые результаты экспериментов по их использованию.
1. Задачи логического проектирования. Традиционными задачами в системах автоматизированного проектирования дискретных устройств являются стнтез, анализ, верификация.
Задача синтеза логической схемы формулируется следующим образом. Дано функциональное описание блока и библиотека логических элементов (целевая библиотека синтеза, базис синтеза). Требуется построить логическую схему из элементов библиотеки, поведение (функционирование) которой эквивалентно задаваемому исходным описанием. Трудность решения задачи синтеза заключается в том, что необходимо найти оптимальную по тем или иным критериям (площадь кристалла, быстродействие) схему.
Задачами анализа выступают: вычисление реакции схемы на заданное входное воздействие (тест), поиск входного сигнала, вызывающего нужную реакцию, и др. Для синтезированных логических схем основная задача анализа - вычисление реакций схемы на заданные входные воздействия - решается в системах моделирования, например в системе ModelSim с входным языком VHDL [2].
Задача верификации логических схем конкретизируется так: даны две логические схемы, функциональную эквивалентность которых нужно подтвердить. В настоящее время разработка средств формальной верификации представляет
собой одну из важнейших проблем в логическом проектировании [2].
Предлагаемый подход продемонстрируем на примере синтеза и верификации комбинационных схем. В этом случае модификация иерархии проекта может быть достигнута последовательностью действий, подобных разбиению или слиянию вершин дерева иерархии, смене типа описаний вершин и т.д.
2. Язык SF иерархического описания дискретных устройств. В работе в качестве языка описания логических схем (проектируемых дискретных устройств) используется язык SF [5, 6], который существенно ориентируется на иерархическое представление проекта, при этом уровень вложенности компонент не ограничивается. Дискретное устройство (схема) на языке SF определяется последовательностью функционально-структурных описаний подсхем (блоков), из которых состоит схема. Иерархия проекта (схемы) представляется в виде дерева, где каждой вершине соответствует отдельный блок.
Любой блок, отвечающий узлу дерева иерархии, выражается заданием связей входящих в него подсхем. Допускается использование двух форматов: CONNECT_2 - двухуровневая схема в виде соединения элементов (листовых блоков), CONNECT_N - общий случай иерархии (N - число уровней иерархического описания). Функциональные описания листовых блоков содержат либо логические уравнения - скобочные формы в базисе И, ИЛИ, НЕ (LOG-формат), либо матричную форму записи системы дизъюнктивных нормальных форм (ДНФ) булевых функций (SDF-формат). Если головной блок описан на функциональном уровне, то в этом случае весь проект представляет собой один листовой блок.
Пример. На рис. 1а дана логическая схема VLSI_1, состоящая из трех блоков adder_2, mult_2, YY_mux. Блок adder_2 (рис. 16) объединяет пару элементов (листовых блоков) - addl и add2, в подсхему mult_2 (рис. 1, в) входят шесть листовых блоков (четыре блока типа (TYPE) and2 и два -типа addl). Дерево D подчиненности блоков в иерархии проекта изображено на рис. 2. Корню дерева D соответствует блок VLSI_1, листовыми описаниями являются блоки and2, addl, add2, YY_mux.
Описание схемы VLSI_1 на языке SF представлено в Приложении. Заметим, что при задании логических уравнений (в LOG-формате) символы операций имеют следующую интерпретацию: через "*" обозначено логическое И (конъюнкция), через "+" - логическое ИЛИ (дизъюнкция), через "л" - логическое НЕ (отрицание).
Блоки and2, addl, add2 описаны в LOG-форма-те, блок YY_mux - в SDF-формате. Эквивалентное представление функций блока YY_mux имеет вид
d 1 = (x л s 1) v (x л 11), d 2 = (X л s 2 )v( x л 12), d3 = (X л c2) v (x л t3), d 4 = x л 14.
Отображение соединений элементов в разделе CONNECT осуществляется "по входам": для каждого входного полюса P элемента указывается входной полюс схемы (или выходной полюс элемента), с которым соединен полюс P. Так как в схеме могут присутствовать несколько элементов одного и того же типа, то они различаются именами. Например, спецификацию связей элемента типа mult_2 (рис. 1, а), имеющего имя circ2, в разделе CONNECT представим как
circ2
s0=b1 r0=b2 s1=a1 r1=a2, т.е. на полюс s0 подается входная переменная b1, на полюс r0 входная переменная b2, на полюс s1 -входная переменная a1, на полюс r1 - входная переменная a2.
Язык SF близок к языку VHDL на уровне RTL-описаний [2]. Основное отличие заключается в том, что комбинационная логика в языке SF отделена от представления элементов памяти, в то время как на языке VHDL в RTL-описаниях соединения элементов памяти и функциональные описания комбинационных элементов задаются совместно.
3. Атрибуты. Выбор того или иного проектного решения всегда основан на оценке некоторых характеристик текущего состояния проекта, в дальнейшем называемых атрибутами.
Атрибуты представляются произвольными именами и разделяются по типу на символьные (строковые), числовые и логические (булевы). В качестве значения символьных атрибутов выступают строки произвольного текста (например, имена объектов). Значения числовые атрибутов - целые или вещественные числа. Логические атрибуты задаются на множестве значений TRUE/FALSE. По содержанию атрибуты могут быть классифицированы как атрибуты описаний объектов проектирования (SF-описаний), программных модулей (далее просто модулей), вспомогательные атрибуты для управления выполнением продукций.
Приведем лишь те несколько атрибутов (табл. 1), которые будут использованы в примерах стратегий. Напомним, что под стратегией понимается упорядоченная совокупность продукций [3]. Формирование продукций осуществляется с использованием атрибутов и программных модулей и будет рассмотрено после описания некоторых модулей.
4. Модули. Фактически процесс логического проектирования связан с выполнением проектных процедур, реализуемых при помощи соответ-
а1 Ь1 а2 Ь2
а1 Ь1 а2 Ь2
tз
скс2
s1
Ь1
Ь2
12
d4 d3 d2 d1
s2
с2
а1
а2
to
80
г1 г0
Рис. 1. Иерархический проект УЬ8!_1: а - головной модуль УЬ8!_1; б - модуль adder_2; в - модуль mult_2.
ствующих программных модулей. В табл. 2 представлена некоторая совокупность модулей, комбинация которых позволяет решать задачи синтеза и преобразовывать иерархические описания проектов в описания, пригодные для выполнения программ верификации.
5. Примеры процессов логического синтеза и верификации. Конвейерная минимизация систем функций. Для матричных представлений систем полностью определенных функций широко известна задача совместной минимизации системы функций в классе ДНФ [7]. Результаты экспери-
а
а
81
ментального исследования программ, предназначенных для решения данной задачи, приводятся в [8]. Для систем функций с десятками и сотнями переменных минимизация всей системы, содержащей тысячи элементарных конъюнкций, может быть неприемлемой по времени. На практике применим способ конвейерной минимизации, когда исходная система разбивается на дизъюнкцию подсистем (декомпозиция "по термам" [7]), каждая из которых минимизируется независимо от других, затем выполняется операция дизъюнкции минимизированных подсистем. Очевидно, ка
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.