В.Соловьев, А.Климович

Синтез на ПЛИС многоуровневых комбинационных схем

Рассматривается метод синтеза на ПЛИС многоуровневых комбинационных систем. Отмечаются положительные и отрицательные качества многоуровневых комбинационных схем, по сравнению с одноуровневыми. Метод М5 подробно описывается для универсальных PAL, а затем уточняется для "классических" PAL и CPLD. Проведенные экспериментальные исследования показали высокую эффективность метода, который, по сравнению с методами пакета MAX+PLUSII, позволяет для отдельных примеров снизить стоимость реализации почти в 21 раз и повысить быстродействие в 4,5 раза.

Введение

В некоторых случаях, когда требование одновременного формирования выходных сигналов комбинационной схемы не критично, можно применить методы синтеза многоуровневых комбинационных схем. Главным недостатком методов синтеза многоуровневых комбинационных схем является возможное значительное различие времени формирования значений выходных сигналов. Это связано с тем, что отдельные функции могут быть реализованы на первом уровне схемы, а некоторые — на последнем. Преимущество многоуровневых схем, по сравнению с одноуровневыми [1], заключается в меньшей стоимости реализации, измеряемой числом используемых макроячеек ПЛИС.

Отметим, что при синтезе комбинационных схем на ПЛИС для реализации промежуточных функций могут использоваться скрытые макроячейки, а для реализации межуровневых соединений — внутренние цепи обратных связей. Кроме того, при реализации многоуровневых комбинационных схем макроячейки универсальных PAL с двумя обратными связями могут одновременно использоваться для реализации промежуточных функций и приема значений входных переменных. Таким образом, при синтезе многоуровневых комбинационных схем наиболее полно используются архитектурные возможности ПЛИС.

В данной статье сохраняются обозначения работы [1]. Основные положения предлагаемого метода М5 синтеза на ПЛИС многоуровневых комбинационных схем заключаются в следующем:

• значения реализованных функций и их частей используются в качестве подфункций (фактор-функций) при синтезе других функций;
• для передачи значений уже реализованных функций или их частей на вход матрицы AND используются внутренние цепи обратных связей ПЛИС;
• реализуется только одна из функций у или , у₁ О Y, а необходимый вид функции на выходе ПЛИС образуется путем программирования логического уровня выходного сигнала.

Пусть - расширенная СБФ, представляющая множество исходных функций с их инверсиями; К() — множество элементарных конъюнкций в ДНФ функции у, где О {у_i,}, i = 1, N. Напомним, что функция является подфункцией функции [частью функции , фактор-функцией функции ), если выполняется:

где f — пустое множество.

Пусть Y*() — множество функций расширенной СБФ, для которых функция у является подфункцией, Y*() Н Y*. Очевидно, что функцию имеет смысл использовать в качестве подфункции функции , О Y*, только в том случае, когда при этом значение |К()| уменьшается по крайней мере на единицу. Поэтому эффективность использования функции , О Y*, в качестве подфункции функции , О Y*(), можно выразить, при выполнении условий (1), следующим образом:

Тогда общую эффективность функции , О Y*, в качестве подфункции всего множества Y* можно представить в виде:

Предлагаемый подход состоит из трех этапов. На первом этапе для каждой функции у_i, у_i О Y, выбирается вид реализуемой функции: у_i или у_i. На втором этапе осуществляется реализация выбранных функций и их частей, а на третьем — объединение по ИЛИ с помощью ПЛИС отдельных частей функций, реализованных на втором этапе.

Необходимым и достаточным условием реализации СБФ с помощью предлагаемого подхода является выполнение ограничений на максимальный ранг конъюнкций:

где ; r(у_i) и r() — максимальный ранг (число литералов) конъюнкций в представлении у_i функций и , соответственно; при реализации на универсальных PAL k = = m + m₂, при реализации на "классических" PAL k = m; m — число двунаправленных выводов PAL с одной обратной связью, т₂ — число двунаправленных выводов PAL с двумя обратными связями.

При реализации СБФ на CPLD условия (3) примут вид:

где п — число входов матрицы AND функциональных блоков CPLD.

Синтез многоуровневых комбинационных схем на универсальных PAL

Пусть для реализуемой СБФ выполняются условия (3). На первом этапе для определения множества Y* реализуемых функций выполняется следующий алгоритм.

Алгоритм 1

1. Строится расширенное представление СБФ .
2. Из множества Y* исключаются функции, для которых нарушено условие (3). Если условие (3) нарушено сразу для обеих функций у_i и , то реализация СБФ Y одноуровневой схемой на PAL с заданными параметрами невозможна, переход к пункту 5.
3. Последовательно просматриваются функции множества Y*. Если функция , О Y*, имеет только одну форму представления (у_i или ), рассматривается следующая функция. Иначе для функций у_i и , согласно (2), определяются значения D(y_i) и D() эффективности их использования в качестве подфункций для других функций. Из функций у_i и в множество Y* выбирается такая функция, для которой D() больше. В случае равенства значений D(y_i) и D() выбирается функция, для которой r() имеет наименьшее значение. В случае равенства значений r(у_i) и r() выбирается функция, для которой |К()| имеет наименьшее значение.
4. Функция , выбранная в пункте 3, сохраняется в множестве Y*, а её инверсия исключается из множества Y*. Пункты алгоритма 3 и 4 выполняются для всех .
5. Конец.

Пусть множество реализуемых функций Y* представляется в виде двух матриц: троичной А и булевой В; К = = {k₁,...,k_p} — множество различных элементарных конъюнкций в представлении функций множества Y*; X(k₁) — множество аргументов, определяющих конъюнкцию к, . Для каждой функции , О Y*, определим число С() других функций, для которых функция у или её часть потенциально может выступать в качестве подфункции.

Второй этап метода синтеза сводится к решению задачи 2, рассмотренной в [1]. Для решения задачи 2 из [1] используется алгоритм, аналогичный алгоритму 2 из [1], когда последовательно формируются миноры В₁,...,В_Т, при этом покрытие некоторой единицы матрицы В на пересечении строки i и столбца j (пары (i,jj) формируемым минором В( возможно при выполнении неравенств:

а также, если среди свободных макроячеек t-й PAL найдется макроячейка с числом промежуточных шин q_s такая, что выполняется неравенство:

причем различным у_i, у_i О Y(, должны соответствовать различные q_s, q_s О Q.

Главным отличием предлагаемого подхода от алгоритма 2 из [1] является то, что если некоторая реализованная функция , О Y*, является подфункцией для других функций, то вводится фактор-функция w_i = и соответствующая промежуточная переменная g_i с целью упрощения функций, для которых w_i является подфункцией, а также выполняется корректировка матриц А и В в представлении исходной СБФ. В последующем каждый минор В( будет определять реализацию функций или их частей на t-й PAL первого уровня.

С учетом сделанных замечаний, второй этап метода синтеза выполняется в соответствии со следующим алгоритмом.

Алгоритм 2

1. Полагается t := 0.
2. Полагается t := t + 1, Q* := Q; определяются значения К(), D() и С() для всех реализуемых функций.

   Начинается формирование очередного минора В (В_i качестве опорных в минор В_i включается пара (i,j) по следующим критериям:

   1)С() = max (функция является подфункцией для большего числа других функций);

   2)D() = max (функция наиболее эффективна в качестве подфункции);

   3)|X(k_i)| = max (выбирается функция с наибольшим числом аргументов);

   4)|К()| = min (выбирается самая простая функция, тем самым создаются предпосылки для полной реализации функции );

   Выбранные строка i и столбец j включаются в минор В_t, полагается:

   

3. Осуществляется покрытие единиц матрицы В минором В_t. Для этого среди непокрытых единиц матрицы В отыскивается единица, для которой выполняются условия (5) и (6). При наличии альтернативы выбора пара (i,j) выбирается в соответствии со следующим порядком рассмотрения критериев:

Если всё ещё осталась альтернатива выбора, то предпочтение отдается единице, расположенной в столбцах минора В( (создаются предпосылки для полной реализации функций множества YJ.

Строка i и столбец j, на пересечении которых находится выбранная единица, включается в минор В_t, полагается:

Если в результате включения пары (i,j) все единицы столбца j покрыты минором В_t и С() > 0, то вводится фактор-функция w_j = и соответствующая ей промежуточная переменная g_j, а также выполняется корректировка представления СБФ.

Пункт 3 повторяется до тех пор, пока минором В_t может быть покрыта хотя бы одна единица матрицы В.

4. Выполняется назначение макроячеек PAL реализуемым функциям. С этой целью для каждой функции , О Y_t, среди свободных макроячеек PAL с числом промежуточных шин, удовлетворяющих условию (6), выбирается макроячейка с минимальным значением q_s. Функция , О Y_t назначается для реализации на s-ю макроячейку t-й PAL, полагается Q* := Q*\{q_J}.
5. Вводятся все возможные фактор-функции. Для этого последовательно просматриваются функции z, z_j О Y_t, где z — это либо функция , либо её часть. Проверяется, если функция z является подфункцией хотя бы одной ещё не реализованной функции, то вводится фактор-функция w_j и соответствующая ей промежуточная переменная g_j, и выполняется корректировка представления СБФ.
6. В матрице В обнуляются единицы, покрытые минором В_j. Если в матрице В остались единицы, то выполняется переход к пункту 2; иначе выполняется переход к пункту 7.
7. Конец.

Выполняемая в пунктах 3 и 5 корректировка представления СБФ, связанная с введением фактор-функции w_j и соответствующей ей промежуточной переменной g_j, заключается в следующем. Полагается Р := Р + 1, в матрицу А добавляется столбец, соответствующий промежуточной переменной g_j. В строке Р матрицы А ставится единица на пересечении с введенным столбцом. В строке Р матрицы В единицы ставятся в тех столбцах, для которых функция w_j является подфункцией. В этих же столбцах матрицы В обнуляются единицы, покрываемые столбцом j матрицы В. Полагается

Замечание

В общем случае, некоторая фактор-функция w_j, реализуемая на t-й PAL, может использоваться для реализации других функций, которые реализуются как на t-й, так и на других PAL. При определении значения |X_j² промежуточная переменная g_j не учитывается, если соответствующая ей фактор-функция w_j реализуется на t-й PAL, поскольку значение g_j поступает на вход матрицы AND по внутренним цепям обратных связей PAL Если же фактор-функция w_j реализуется на других PAL, то при определении значения |X_j² промежуточную переменную g_j следует рассматривать как обычную входную переменную, поскольку для подачи её значения на вход t-й PAL используется внешняя цепь обратной связи.

Рассмотрим решение задачи третьего этапа. Пусть Z = {z_i...,z_Q} — множество промежуточных функций, представляющих собой отдельные части нереализованных функций. Выполнение третьего этапа начинается с построения булевой матрицы В, столбцы которой соответствуют выходным функциям СБФ, а строки — промежуточным функциям z_i...,z_Q. На пересечении строки i и столбца j матрицы В ставится единица, если функция z_i является частью функции . Для реализованных на первом этапе функций столбцы матрицы В будут нулевыми, и их из дальнейшего рассмотрения можно исключить. Теперь задача третьего этапа практически совпадает с задачей 2 из [1]. Поэтому для её решения может быть применен алгоритм 2 из [1].

В последующем каждый минор В_t, t = 1 ,Т, будет определять t-ю PAL второго уровня, которая осуществляет объединение по ИЛИ не реализованных частей функций. При этом строки минора определяют входные переменные PAL, а столбцы — реализуемые функции.

Необходимые значения функций на выходах всех PAL формируются путем программирования логического уровня выходного сигнала.

Пример

Пусть универсальные PAL имеют следующие параметры: п = 3, m = 2, m₂= 1 и Q = {2,2,3}. Рассмотрим синтез комбинационной схемы,заданной следующей системой логических уравнений:

Инверсные представления функций имеют вид:

Исходные данные для выполнения алгоритма 1 на первом этапе синтеза представлены в табл. 1. При выполнении пункта 2 алгоритма 1 из множества Y* исключаются функции у₃ и у₄, так как для них нарушено условие (3). В пункте 3 алгоритма 1 для реализации выбираются функции и у₂, так как для этих функций D() > D(y). Таким образом, в результате выполнения алгоритма 1 для реализации выбираются инверсные представления всех функций, а реализуемая СБФ показана в табл. 2.

Таблица 1. Исходные данные для работы алгоритма 1

Таблица 2. Реализуемая система булевых функций

Исходные данные для работы алгоритма 2 представлены в табл. 3. В пункте 2 алгоритма 2 в минор В_о в качестве опорной включается пара (5,2), поскольку С() = 2 = max. Затем в минор В_о добавляется единица, соответствующая паре (6,2). В результате минором В_о покрываются все единицы столбца 2. Поскольку С() > 0 (функция является подфункцией для функций и то вводится фактор-функция w₂ = , соответствующая ей промежуточная переменная п₂ и выполняется корректировка матриц А и В.

Таблица 3. Исходные данные для работы алгоритма 2

Скорректированные матрицы А и В приведены в табл. 4. Затем в минор В_о последовательно добавляются единицы, соответствующие парам (8,3), (9,3), (10,3), (9,4) и (10,4). Больше минором В, не может быть покрыта ни одна единица без нарушения условий (5). Система булевых функций после покрытия матрицы В минором В! приведена в табл. 5. Аналогичным образом формируется минор В2. При этом вводится фактор-функция W_j (и соответствующая ей промежуточная переменная g_j, являющаяся подфункцией для функции . На этом второй этап синтеза заканчивается, поскольку все единицы матрицы В покрыты минорами.

Таблица 4. Представление системы булевых функций после реализации функции

Таблица 5. Представление системы булевых функций после покрытия матрицы В минором В_j

На третьем этапе синтеза в схему вводится одна дополнительная PAL, на входы которой подаются значения реализованных частей функций и , а на выходах формируются функции у₃ и у₄. Прямые значения всех функций образуются путем программирования логического уровня выходных сигналов. В итоге логические уравнения реализуемых функций выглядят следующим образом:

Окончательная реализация комбинационной схемы показана на рисунке.

Рисунок. Реализация СБФ многоуровневой системой на универсальных PAL

Синтез многоуровневых комбинационных схем на классических PAL

Поскольку "классические" PAL не позволяют программировать логический уровень выходных сигналов, то при синтезе комбинационных схем с использованием внутренних цепей обратных связей ПЛИС в качестве множества Y* реализуемых функций выбирается одно из множеств = {,...,} или Y = = {y_i,...,y_N}. Если в неравенствах (5) принять k = m + b, где m — число двунаправленных, в b — комбинационных выходов "классических" PAL, то рассмотренный выше метод синтеза комбинационных схем с использованием внутренних цепей обратных связей ПЛИС на универсальных PAL может быть применен и для синтеза комбинационных схем на "классических" PAL

Синтез многоуровневых комбинационных схем на CPLD

Необходимым и достаточным условием применения метода синтеза комбинационных схем с использованием внутренних цепей обратных связей CPLD является выполнение неравенств (4). Первый этап метода синтеза выполняется точно так же, как при синтезе комбинационных схем на универсальных PAL. На втором этапе задача сводится к покрытию матрицы В минимальным числом Т миноров В₁,...,В_Т таким образом, чтобы для каждого минора выполнялись условия:

где

а также для каждого столбца j минора В_t выполнялось

где m — число выходных макроячеек CPLD; Y_t — множество функций, соответствующих столбцам минора В_t; Х_t — множество аргументов, соответствующих строкам минора В_t,

К_t — множество конъюнкций, соответствующих строкам минора В_t; Q_t^' — число единиц в столбце j минора B_t, . Каждый минор В_t определяет подмножество выходных функций или их частей, реализуемых на одном функциональном блоке CPLD.

При построении очередного минора B_t, , некоторая единица матрицы В на пересечении строки i и столбца j может быть покрыта минором В_t при выполнении неравенств:

а также, если выполняется неравенство:

Второй этап синтеза комбинационных схем на CPLD с использованием внутренних цепей обратных связей совпадает с алгоритмом 2, за исключением того, что в вместо условий (5) и (6) рассматриваются соответственно условия (9) и (10).

Третий этап синтеза выполняется аналогично третьему этапу синтеза для универсальных PAL

Результаты экспериментальных исследований

Метод М5 синтеза многоуровневых комбинационных схем реализован программно в пакете ZUBR. Экспериментальные исследования проводились для сравнения метода М5 с методом пакета MAX+PLUSII версии 10.1 фирмы ALTERA. В качестве ПЛИС рассматривались универсальные PAL семейства CLASSIC.

Анализ полученных результатов (табл. 6) показывает, что метод М5, по сравнению с методами пакета MAX+PLUSII, при синтезе комбинационных схем на ПЛИС семейства CLASSIC позволяет значительно снизить стоимость реализации (в среднем, в 6,14 раза, а для отдельных примеров — в 20,91 раза) и повысить быстродействие (в среднем, в 1,43 раза, а для отдельных примеров — в 4,53 раза).

Таблица 6. Результаты сравнения метода М5 с методом пакета MAX+PLUSII для семейства CLASSIC

Литература

1. Соловьев В. В., Климович А. Синтез на ПЛИС одноуровневых комбинационных схем // ChipNews. 2003. № 6. С. 20-27.