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

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

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

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

Введение

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

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

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

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

Пусть Y* = {y1,...,yN,¯y1,...,¯yN} - расширенная СБФ, представляющая множество исходных функций с их инверсиями; K(ýi) - множество элементарных конъюнкций в ДНФ функции ýi, где ýi € {yi,y¯i}, i = ¯1,¯N.

Напомним, что функция ýi является подфункцией функции ýj (частью функции ýj, фактор-функцией функции ýj), если выполняется:

K(ýi)\K(ýj) = Ø, (1)

где Ø - пустое множество.

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

d(ýi,ýj) = |K(ýi)| √ 1.

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

(2)

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

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

r(Ýi) n + k √ 1, для всех i = ¯1,¯N, (3)

где r(ýi) = min(r(yi),r(¯yi)); ýi € {yi,¯yi}, i = ¯1,¯N; r(yi) и r(¯yi) - максимальный ранг (число литералов) конъюнкций в представлении yi функций и ¯yi, соответственно; при реализации на универсальных PAL k = = m + m2, при реализации на "классических" PAL k = m; m - число двунаправленных выводов PAL с одной обратной связью, m2 - число двунаправленных выводов PAL с двумя обратными связями.

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

r(ýi) n, для всех i = ¯1,¯N, (4)

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

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

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

Алгоритм 1

Строится расширенное представление СБФ Y* = {y1,...,yN,¯y1,...,¯yN}. Из множества Y* исключаются функции, для которых нарушено условие (3). Если условие (3) нарушено сразу для обеих функций yi и ¯yi, то реализация СБФ Y одноуровневой схемой на PAL с заданными параметрами невозможна, переход к пункту 5. Последовательно просматриваются функции множества Y*. Если функция ýi, ýi € Y*, имеет только одну форму представления (yi или ¯yi), рассматривается следующая функция. Иначе для функций yi и ¯yi, согласно (2), определяются значения D(yi) и D(¯yi) эффективности их использования в качестве подфункций для других функций. Из функций yi и ¯yi в множество Y* выбирается такая функция, для которой D(ýi) больше. В случае равенства значений D(yi) и D(¯yi) выбирается функция, для которой r(ûi) имеет наименьшее значение. В случае равенства значений r(yi) и r(¯yi) выбирается функция, для которой |K(ýj)| имеет наименьшее значение. Функция ýi, выбранная в пункте 3, сохраняется в множестве Y*, а е╦ инверсия исключается из множества Y*.

Пункты алгоритма 3 и 4 выполняются для всех i = ¯1,¯N.

Конец.

Пусть множество реализуемых функций Y* представляется в виде двух матриц: троичной A и булевой B; K = {k1,...,kP} - множество различных элементарных конъюнкций в представлении функций множества Y*; X(ki) - множество аргументов, определяющих конъюнкцию ki, i = ¯1,¯P. Для каждой функции ýi, ýi € Y*, определим число С(ýi) других функций, для которых функция ýi или е╦ часть потенциально может выступать в качестве подфункции.

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

|Yt {ýj}| k;
|Xt X(ki)| n + k √ |Yt {ýj}|, (5)

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

Qjt + 1 qs, (6)

причем различным yj, yj € Yt, должны соответствовать различные qs, qs € Q.

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

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

Алгоритм 2

Полагается t := 0. Полагается t := t + 1, Q* := Q; определяются значения K(ûj), D(ûj) и С(ýj) для всех реализуемых функций.
Начинается формирование очередного минора BT. В качестве опорных в минор Bt включается пара (i,j) по следующим критериям:
1) C(ýj) = max (функция ýj является подфункцией для большего числа других функций);
2) D(ýj) = max (функция ýj наиболее эффективна в качестве подфункции);
3) |X(ki)| = max (выбирается функция с наибольшим числом аргументов);
4) |K(ýj)| = min (выбирается самая простая функция, тем самым создаются предпосылки для полной реализации функции ýj);

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

Kt := {ki};
Xt := X(ki);
Yt := {ýj};
Qjt :=1. Осуществляется покрытие единиц матрицы B минором Bt. Для этого среди непокрытых единиц матрицы B отыскивается единица, для которой выполняются условия (5) и (6). При наличии альтернативы выбора пара (i,j) выбирается в соответствии со следующим порядком рассмотрения критериев: 1) C(ýj) = max;
2) |Xt X(ki)| = max;
3) |X(ki) \ Xt| = min;
4) D(ýj) = max;
5) |K(ýj)| = min.

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

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

Kt := Kt {ki};
Yt := Yt {ýj};
Xt := Xt X(ki);
Qjt := Qjt + 1.

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

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

Выполняется назначение макроячеек PAL реализуемым функциям. С этой целью для каждой функции ýj, ýj € Yt, среди свободных макроячеек PAL с числом промежуточных шин, удовлетворяющих условию (6), выбирается макроячейка с минимальным значением qs. Функция ýj, ýj € Yt, назначается для реализации на s-ю макроячейку t-й PAL, полагается Q* := Q*\{qs}. Вводятся все возможные фактор-функции. Для этого последовательно просматриваются функции zj, zj € Yt, где zj - это либо функция ýj, либо е╦ часть. Проверяется, если функция zj является подфункцией хотя бы одной ещ╦ не реализованной функции, то вводится фактор-функция wj и соответствующая ей промежуточная переменная gj, и выполняется корректировка представления СБФ. В матрице В обнуляются единицы, покрытые минором Bt. Если в матрице B остались единицы, то выполняется переход к пункту 2; иначе выполняется переход к пункту 7. Конец.

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

X := X {gj};
X(kP) := {gj}. Замечание

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

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

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

Пример

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

y1 = x1╥x2 + x2╥¯x3 + x1╥¯x3 + ¯x1╥¯x2╥x3;

y2 = ¯x4 + ¯x5╥x6 + x5╥¯x6;

y3 = ¯x1╥¯x2╥x3╥¯x4╥¯x5╥¯x6 + ¯x1╥¯x2╥x3╥¯x4╥x5╥x6 + x1╥¯x2╥¯x3╥x4╥¯x5╥x6 + ¯x1╥¯x2╥x3╥x4╥x5╥¯x6 + ¯x1╥x2╥¯x3╥¯x4╥¯x5╥¯x6 + ¯x1╥x2╥¯x3╥¯x4╥x5╥x6 + ¯x1╥x2╥¯x3╥x4╥¯x5╥x6 + ¯x1╥x2╥¯x3╥x4╥x5╥¯x6 + x1╥¯x2╥¯x3╥¯x4╥¯x5╥¯x6 + x1╥¯x2╥¯x3╥¯x4╥x5╥x6 + x1╥¯x2╥¯x3╥x4╥¯x5╥x6 + x1╥¯x2╥¯x3╥x4╥x5╥¯x6 + x1╥x2╥x3╥¯x4╥¯x5╥¯x6 + x1╥x2╥x3╥¯x4╥x5╥x6 + x1╥x2╥x3╥x4╥¯x5╥x6 + x1╥x2╥x3╥x4╥x5╥¯x6;

y4 = ¯x2╥¯x3╥¯x4╥¯x5 + ¯x2╥¯x3╥¯x4╥x6 + ¯x2╥¯x3╥¯x5╥x6 + ¯x2╥¯x3╥x4╥x5╥¯x6 + ¯x1╥x2╥¯x4╥¯x5 + ¯x1╥x2╥¯x4╥x6 + ¯x1╥x2╥¯x5╥x6 + ¯x1╥x2╥x4╥x5╥¯x6 + x1╥x3╥¯x4╥¯x5 + x1╥x3╥¯x4╥x6 + x1╥x3╥¯x5╥x6 + x1╥x3╥x4╥x5╥¯x6.

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

¯y1 = ¯x1╥¯x2╥¯x3 + x1╥¯x2╥x3 + ¯x1╥x2╥x3;

¯y2 = x4╥¯x5╥¯x6 + x4╥x5╥x6;

¯y3 = ¯x1╥¯x2╥¯x3 + x1╥¯x2╥x3 + ¯x1╥x2╥x3 + x1╥x2╥¯x3 + x4╥¯x5╥¯x6 + ¯x4╥¯x5╥x6 + x4╥x5╥x6 + ¯x4╥x5╥¯x6;

¯y4 = ¯x1╥¯x2╥x3 + x1╥x2╥¯x3 + x4╥¯x5╥¯x6 + x4╥x5╥x6 + ¯x4╥x5╥¯x6.

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

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






Рекомендуемый контент




Copyright © 2010-2020 housea.ru. Контакты: info@housea.ru При использовании материалов веб-сайта Домашнее Радио, гиперссылка на источник обязательна.