Размещено на http://www.allbest.ru/

Алгоритм синтеза цифровых микросхем на основе разложения Э.Н. Гильберта

C.И. Гуров, Д.И. Рыжова

Проблема оптимизации синтеза комбинационных частей цифровых интегральных микросхем (ИМС) продолжает оставаться актуальной. При автоматизации проектирования методы, ориентированные на регулярные представления комбинационных частей схем, представляются предпочтительными с точки зрения надежности на логическом уровне и легкости тестирования. Такие представления логических блоков микросистем можно получить непосредственно из разложения Э. Гильберта. В статье описан алгоритм синтеза комбинационной схемы, реализующий произвольные булевы функции, основанный на представлении частичной булевой функции f в виде где- монотонные функции, а F - оптимальное в некотором смысле доопределение f. Для часто используемой на практике системы приоритетов значений таблично заданных функций предложен эффективный способ нахождения их отрицаний. На основе указанного разложения реализован алгоритм синтеза схемы, вычисляющей f в реальных проектных базисах микроэлектронных БИС. Приведён пример работы алгоритма в составе системы автоматического синтеза комбинационных логических блоков БИС.

Ключевые слова -- булева функция, комбинационная схема, функция Шеффера.

В статье [1] показано, что любая полностью определенная булева функция (ПБФ) может быть представлена в виде

(1)

где-- некоторые монотонные булевы функции. Эти функции мы предлагаем называть функциями Э. Гильберта, а формулу (1) -- разложением Э. Гильберта для БФ f. Хотя по тексту указанной статьи можно восстановить алгоритм нахождения функций прямое использование его во многих практически важных случаях может вызвать серьезные затруднения из-за операции взятия отрицания от функции [2-4].

На практике же булевы функции (БФ) и их системы часто задаются таблицами специального вида [5], строки которых описывают значения функций на гранях булева n-мерного единичного куба. В этом случае получение таблицы для инверсной функции может оказаться весьма трудоемким. Это связано с тем, что указанные таблицы допускают наличие пересекающихся интервалов, на которых функция может принимать различные значения. При этом для определения значения БФ в области пересечения интервалов необходимо учитывать приоритеты значений функции, с учётом которых построена таблица. При неравных приоритетах значений 0 и 1 инвертирование функции от n переменных и заданной на l интервалах требует, как будет видно, выполнения O(n·l) операций. Указанное обстоятельство, как и опыт работы авторов, показывают, что от того, насколько удачно реализована операция инвертирования таблично заданных функций, в значительной степени зависит эффективность работы алгоритма в целом.

Кроме того, на практике обычно приходится иметь дело с частичными БФ (ЧБФ). Ясно, что можно получить разложение вида (1) для некоторого доопределения ЧБФ, причём функции Э. Гильберта будут определяться, очевидно, неоднозначно. Поэтому желательно иметь алгоритм, генерирующий монотонные функциитакие, что:

(2)

для ПБФявляющейся одним из возможных и, желательно, в некотором смысле простейших, доопределений f. То, что ПБФесть (некоторое) доопределение f, будем отмечать как

Легко заметить, что на основе разложения Э. Гильберта можно предложить простой алгоритм синтеза ПБФв классе схем из функциональных элементов. Действительно, (2) эквивалентно:

(3)

где | - символ функции Шеффера (отрицание конъюнкции). Ясно, что в указанном классе формула (3) может быть реализована регулярной каскадной схемой, которая будет выглядеть особенно простой при наличии в базисе элемента функции Шеффера.

Наиболее привлекательным представляется использование алгоритма получения представления (3) для автоматического синтеза цифровых комбинационных логических схем. Во-первых, построение схемы из функциональных элементов является первым этапом синтеза в реальных проектных базисах (т.н. этап «абстрактного синтеза»). Во-вторых, условие наличия в базисе элемента функции Шеффера не является обременительным. В-третьих, среди всех функциональных элементов (исключая инвертор) элемент функции Шеффера имеет простейшую реализацию в виде микроэлектронной электрической транзисторной схемы. И, наконец, функции могут быть заданы программируемой логической матрицей (ПЛМ), минимизированной с использованием известных эффективных методов и имеющей дополнительный выигрыш в площади за счёт монотонности представляемых функций (т.к. отсутствует необходимость представления их в парафазном виде).

Основные определения и обозначения

В статье используются стандартные обозначения величин и основные понятия, ставшие уже общепринятыми в кругу специалистов в области дискретной математики [6].

Множество единиц и нулей БФ f обозначается как иеслито БФ f является частичной. Под взятием отрицания (инвертированием) ЧБФ f будем понимать переход к функцииу которойЕслито функция ц называется доопределением ?, что обозначается Если при этом ц - ПБФ (ЧБФ), то ц - полное (частичное) доопределение ?; обозначение для полных доопределений:Множество всевозможных полных доопределений ? обозначимФункции констант (произвольного множества фиктивных переменных) обозначаются 1 и 0. Обозначения двуместных функций традиционны.

Граньнаименьшей размерности, содержащую вершиныибудем называть верхним (нижним) конусом и обозначатьВерхним (нижним) конусом совокупности вершинизбудем называть объединение верхних (нижних) конусов всех вершини обозначать его

Единичный набор БФ f есть нижняя единица f, если его нижний конус не содержит других единиц f. Множество нижних единиц f обозначается LU (f). Нулевой набор БФ f есть верхний нуль f, если его верхний конус не содержит других нулей f. Множество верхних нулей f обозначается UZ (f).

Множество монотонных функций известного числа аргументов обозначим M. Ясно, что любое из множеств LU (f) и UZ (f) полностью определяет f, если(при этоми). Заметим, что, например, функция 1 может быть задана либо пустым множеством верхних нулей, либо множеством нижних единиц, а функция 0 - либо пустым множеством нижних единиц, либо множествомверхних нулей. Для (возможно частичной) БФ ц ее мажорантаесть монотонная функция, определяемая соотношением

Алгоритм синтеза цифровых микросхем на основе разложения Гильберта

Нахождение функции Гильберта

Пусть дана ЧБФ f. Будем искать разложение Э. Гильберта для некоторой функцииФункция F будет построена в процессе нахождения указанного разложения, поэтому мы сразу можем пользоваться формулой (2):

Последнее соотношение эквивалентно совокупности равенств:

…

Отсюда ясно, что функции Э. Гильберта могут быть получены в ходе итерационного процесса, на каждом шаге которого для некоторой ЧБФнаходится разложение:

(4)

где Me и Mo - некоторые подходящие монотонные БФ.

Пусть Me и Mo, удовлетворяющие (4) найдены. Определим функциюТогда в качестве ? можно взять функцию, задаваемую множествами своих единиц и нулей следующим образом:

(5)

В данном процессе на первом шаге ц = f и далее Me и Mo - суть функции Э. Гильберта соответствующего чётного и нечётного индексов. Если окажется, чтоилито итерации следует прервать, в противном случае,есть ц для следующего шага. Ясно, что выполнениеобеспечит последовательность строгих вложений множеств единичных наборов разлагаемых функций на каждом шаге и, следовательно, конечность указанного процесса. Ясно также, что в результате описанного процесса будет найдено разложение Э. Гильберта для некоторой функции

Множестваиесть объединение верхних конусов нижних единиц [нижних нулей] соответствующих функций на каждом этапе алгоритма.

Кратко опишем алгоритм нахождения разложения Э. Гильберта, который определяет функции Me и Mo из предельных условий ииз возможных. Введём обозначение для множества единичных координат булева вектора:

Обозначим символами LU(f) и UZ(f) соответственно множества нижних единиц и верхних нулей ЧБФ

Если в множествеокажутся только единицы ЧБФ f, то удалим их из спискаи дальнейшего рассмотрения и аналогично поступим с нулями f из. Данный шаг приводит к минимизации сложности получаемого представления. Далее переопределяем функции Me и Mo по формулам (5), пока соответствующие множества не станут пусты. Например, для ЧБФ сна первом этапе получимна втором -и алгоритм даста для ЧБФсполучим

Табличное задание систем частичных булевых функций

Значения БФ будем задавать на интервалах (гранях)Интервалызадаются наборамигде Как известно, каждая граньбулева куба соответствуют некоторой элементарной конъюнкциитак, что вершинаизпринадлежиттогда и только тогда, когдаЗдесь J - подмножество таких индексов изчтоТаким образом переменная x_j присутствует в конъюнкциив прямой (инверсной) форме, еслии отсутствует в последней при Это, в свою очередь, означает следующую трактовку символа в записи интервала: интервалможет быть заменен двумя интервалами, отличающимися отналичием 1 и 0 в соответствующей позиции.

Для того чтобы покоординатная конъюнкция интервалов соответствовала их теоретико-множественному произведению, доопределим функции() над интервалами. Введём на множествечастичный порядок с помощью рефлексивного несимметричного отношения «»:1 и 0 несравнимы. Будем трактовать функцииикак max и min соответственно на множествес указанным частичным порядком.

Частичная БФ принимает значения из множествапри этом значениетрактуется как неопределенное. Будем определять ее через множество значения конъюнкцийна некоторой совокупности интерваловИнтервалыбудем называть задающими. Если на всех наборах интервалаконъюнкцияпринимает значението будем писатьЗначения упорядоченного набора конъюнкцийучаствующих в определении ЧБФна некотором интервалебудем задавать кортежемТаким образом, в записисимволозначает, что он может быть заменён на 1 или 0 при соответствующем доопределении данной функции. цифровая интегральная микросхема гильберт

Систему из m частичных булевых функций от n переменных (СЧБФ), заданную на l интервалах будем задавать в табличной форме в виде совокупности l строк:

(6)

где N - номер строки,- интервал из- кортеж значений функций. Совокупностиииз указанного задания будем называть соответственно левой и правой частью таблицы, аи- левой и правой частью соответствующей строки. Заметим, что еслито (5) определяет систему ПБФ заданием соответствующей системы дизъюнктивных нормальных форм. Возможность заменына 0 или 1 в правой части таблицы (5) есть одна из дополнительных степеней свободы при минимизации ПЛМ, отличающих указанный процесс от задачи минимизации БФ (или систем БФ) в классической постановке.

При указанном задании СЧБФ в случае, если некоторые из задающих интервалов пересекаются, а правые части соответствующих строк не совпадают, возникает неоднозначность в определении значений функций на грани, общей для обоих интервалов. Поэтому таблицы (5) строятся с учётом выбранной системы приоритетов значений составляющих функций. Точнее, на множествес помощью несимметричного рефлексивного отношения, трактуемого как «приоритет … больше, чем приоритет …» или «… подавляет …», вводится тот или иной (возможно частичный) порядок. Указанное отношение будем записывать как «>» (правильнее было бы«», однако принятое обозначение уже стало традиционным и не приводит к затруднениям, поскольку используется лишь при обнаружении коллизии значений функций).

Если для некоторых интерваловиучаствующих в задании данной функции, имеют место следующие равенства:

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

Систему a = b = c (приоритеты всех значений равны) обычно называют инвариантной. В построенных по данной системе таблицах строки, соответствующие пересекающимся интервалам, должны иметь совпадающие правые части. Название системы связано с тем, что алгоритмы преобразования СЧБФ (например, поглощения и склеивания интервалов) и реализации элементарных операций с таблицами, разработанные для других систем приоритетов, будут применимы и для инвариантных систем. По этой причине инвариантная система используется, например, для того, чтобы обеспечить возможность выполнения алгоритмов, предназначенных для работы с таблицами, записанными в различных системах приоритетов и избежать при этом преобразовании таблиц из одной системы в другую (ясно, что такое преобразование есть переборная задача). С другой стороны, легко видеть, что таблицы, построенные по инвариантной системе, требуют наибольшего числа задающих интервалов, по сравнению с таблицами, использующими другие системы приоритетов.

Три системы вида a > b = c (значение a подавляет значения b и c, приоритеты которых равны) не интересны с точки зрения задания функций таблицами, не используются и, по-видимому, никогда не будут использоваться на практике. Причина заключается в наличии двух значений с наименьшим приоритетом. Наличие лишь одного такого значения (для определённости, c), как во всех других типах систем, исключая инвариантную, даёт возможность не включать в таблицу строки видачто часто приводит к существенному сокращению числа задающих интервалов. Заметим, что принятый порядок на множестве задающих интервалов мог бы быть записан как

Из систем приоритетов типа a = b > c и a > b > c практически исключительно используются(так называемая «листопадовская», примененная в системе синтеза ПЛМ «Листопад» [7]) и(так называемая «со слабым нулём»). Последняя система удобна тем, что соответствующие таблицы, как и все таблицы, построенные по системам типа a > b > c, не требуют проверки на наличие противоречий в определении значений. Недостатком системы со слабым нулём является невозможность быстрого получения инверсных значений функций. Действительно, в этом случае некоторые нули той или иной функции будут подавляться её неопределёнными или единичными значениями и не будут представлены в таблице явно, так же как и интервалы с нулевыми значениями всех функций (строки).

Алгоритм нахождения разложения Э. Гильберта использует две основных операции: определение мажоранты и взятия отрицания от функции. Его реализация для таблично заданных функций имеет свои особенности: если алгоритм определения мажоранты функции элементарен для любой системы приоритетов значений, то инвертирование функции в системе приоритетов a > b > c может вызвать трудности в силу трудоёмкости явного определения соответствующих задающих интервалов и неоднозначности представления результата.

Для получения совокупности нулевых интервалов функции необходимо найти множество в явном виде. Это можно сделать, если имеется возможность выполнять операцию «вычитания интервалов», т.е. явного определения множества

Результат такой операции может быть записан в различной форме. Мы предлагаем записывать его в виде совокупности p интервалов возрастающей размерностигде p - мощность множества а r - размерность интервалаНаш опыт показывает, что такое представление обеспечивает, с одной стороны, компактность представления, а с другой стороны, необходимое быстродействие алгоритма. Единичные интервалы функции получаются как результат вычитания всех строк видаитаблицы функции f из строки

Применение разложения Гильберта к задаче синтеза комбинационных блоков ИМС

Описанный алгоритм нахождения функций Э. Гильберта, преобразованной для СЧБФ был запрограммирован и в качестве одного из методов был включён в состав системы LORD автоматического многоуровневого синтеза комбинационно-логических схем цифровых блоков интегральных микросхем. Система LORD создавалась авторами в НИИ молекулярной электроники МЭП СССР как одна из компонент САПР БИС «Arc/ws» [8].

Алгоритм был реализован в виде отдельного программного модуля, при этом монотонные функции представлялись в простейшем виде «сумма произведений» с некоторой минимизацией представляющих интервалов. В целях исследования свойств алгоритма были проведены численные эксперименты на наборе тестовых схем программного комплекса SIS [9-10]. Было проведено сравнение результатов синтеза комбинационных схем средствами SIS с выходными данными алгоритма Гильберта по занимаемой площади S и величине критического пути T (в условных единицах). Результат сравнения приведен в таблице 1 [11].

Таблица 1

Сравнение результатов синтеза схем средствами SIS и результатов, полученных с помощью алгоритма Гильберта

Данные в таблице имеют демонстрационный характер, поскольку при апробировании метода вне реальной практической системы синтеза ИС не проверялись другие способы доопределения ЧБФ, не проводились ни минимизация представления монотонных функций, ни использование так называемого «фазирования» входных и выходных векторов систем (работа с инверсными представлениями некоторых аргументов всех функций и значений некоторых функций). Применение этих подходов в сочетании с предложенным приводит к значительному улучшению параметров синтезируемых схем.

Ниже приведён пример работы алгоритма автоматического синтеза в произвольной логике схемы цифрового блока по его функциональному (поведенческому) описанию. Монотонные функции Э. Гильберта реализованы в виде сумм логических произведений.

На рис. 1 представлен файл kluch.fdt, задающий поведенческое описание работы некоторого разрабатываемого устройства (в данном случае, ключа видеоконтроллера). Работа устройства описывается системой двух частичных булевых функций от восьми переменных (строки kinp и kout), которая задаётся в табличной форме. Для описания логики работы данного устройства заданы значения соответствующих функций на 36 интервалах (строка klin) 8-мерного единичного булева куба. Интервалы и значения функций на них указаны 36 строками таблицы; каждая строка предваряется порядковым номером. Принятая интерпретация коллизий значений функций на интервалах указана в строке Interpretation. Она указывает на равные приоритеты значений 1, 0 и - (инвариантная кодировка). Это, в частности, означает, что непустое пересечение могут иметь лишь те интервалы левой части таблицы, которые имеют идентичные правые части (например, интервалы 1 и 2). Строка Phase показывает, что все аргументы и все функции заданы в прямой форме, т.е. указаны их значения, а не отрицания.

Рис. 1. Фрагмент файла kluch.fdt

Рис. 2. Листинг файла kluch.rm

На рис. 2 представлен листинг файла kluch.rm, содержащий табличное задание системы из двух ДНФ, являющихся возможными доопределениями исходных функций из файла kluch.fdt. Интерпретация коллизий значений правых частей таблицы производится в соответствии с приоритетомЧисло задающих интервалов сократилось до двух.

Рис. 3. представляет собой листинг файла kluch.sht, описывающего схемное решение логики разрабатываемого ключа контроллера в виде списка цепей (netlist).

Строки списка цепей имеют следующий вид:

Имена цепей состоят из буквы и нескольких (не менее одной) цифр, разделённых точками. Входы схемы имеют имена от x.1 до x.8, выходы - y.0 и y.1, все остальные цепи - внутренние. Мнемоника букв имён:

1) nc означает, что данная цепь есть выход элемента NAND,

2) m означает, что данная цепь реализует монотонную функцию (одну из функций Э. Гильберта),

3) z - прочие цепи.

В схеме использовались ключи (функциональные элементы) с именами NAND («многоместный» штрих Шеффера, т.е. отрицание конъюнкций входов) и NOT (отрицание). Список цепей, заключённый в скобки после имени ключа, есть перечисленные через запятую имена цепей, являющиеся входами для данного ключа (список имён аргументов функционального элемента).

Рис. 3. Листинг файла kluch.sht

В результате для схемной реализации ключа видеоконтроллера, фрагмент описания которого приведен на рис.1. в виде таблицы размером (8+2)·36потребовалось всего 18 функциональных элементов при «прямой» реализации на элементах NOT и NAND. Учитывая реализацию данной схемы в КМОП-технологии, где (в простейшем случае) приходится по 2 транзистора на каждый вход элемента, функция ключа видеоконтроллера может быть реализована с использованием только 40 транзисторов. Столь значимое сокращение числа задающих интервалов в примере - с 36 до 2 - получено за счёт разработанного авторами алгоритма минимизации СЧБФ для крайне удобной системы приоритетов «со слабым нулём» (исходная система задана в самой неэкономной - «инвариантной» системе).

Заключение

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

Литература

[1] Gilbert E.N. Lattice theoretic properties of frontal switching functions // J. Math. Phys. 33, 1954. No. 1. Pp. 57-67 (Русск. пер.: Э.Н. Гильберт. Теоретико-структурные свойства замыкающих переключательных функций // Кибернетический сборник, 1960. - №1. - С. 175-188).

[2] George Grдtzer, B.A. Davey, R. and other. General Lattice Theory: Second edition // Springer Science & Business Media, 2002. 663 p.

[3] Касим-Заде О.М. Об одном методе получения оценок сложности схем над произвольным бесконечным базисом // Дискретный анализ и исследование операций, 2004. Сер. 1. С. 41-65.

[4] Kochergin V.V., Mikhailovich A.V. Some Extensions of the Inversion Complexity of Boolean Functions // Cornell University Library, 2015.

[5] Закревский А.Д. Логический синтез каскадных схем / М.: Наука, 1981. 416 с.

[6] Дискретная математика и математические вопросы кибернетики / Под ред. С.В. Яблонского и О.Б. Лупанова. - М.: Наука, 1974. - Т. I. - 313 с.

[7] Бобошко Ю.Г. Об одном подходе к алгоритмам минимизации не полностью определённых булевых функций и его применение к кодированию программируемых логических матриц // Микроэлектроника и полупроводн. приборы, 1979. С. 33-38.

[8] Авдеев Ю.В., Гаврилов С.В., Гуров С.И. и др. САПР заказных БИС на открытых вычислительных системах // Электронная техника. Сер. 3. «Микроэлектроника», 1992. №1. - С. 12-21.

[9] Sentovich E.M., Singh K.J., Lavagno L., Moon C., Murgai R., Saldanha A., Savoj H., Stephan P.R., Brayton R.K. and Sangiovanni-Vincentelli A.L. SIS: A System for Sequential Circuit Synthesis // EECS Department University of California, Berkeley. 1992. P. 52.

[10] Vasicek Z., Sekanina L. A global postsynthesis optimization method for combinational circuits // Design, Automation & Test in Europe Conference & Exhibition (DATE), 2011. Pp. 1-4.

[11] Гуров С.И., Долотова Н.С., Фатхутдинов И.Н. «Некомпактные» задачи распознавания. Синтез схем по Э. Гильберту // Spectral and Evolution Problems (International scientific journal). Международный научный журнал. Simferopol: Taurida National V. Vernadsky University, 2007. Т. 17. С. 37-44.

Размещено на Allbest.ru