микспромо отзывы

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

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

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

В настоящей статье рассматриваются два метода синтеза на ПЛИС двухуровневых комбинационных схем: метод М3 и метод М4. В методе М3 второй уровень ПЛИС используется для реализации логических функций ИЛИ, которые в методе М2 реализуются с помощью монтажного соединения выходов ПЛИС. Метод М3 при незначительном увеличении стоимости устраняет основной недостаток метода М2 и обеспечивает ряд дополнительных положительных качеств. Однако при этом время формирования выходных сигналов на первом и втором уровнях ПЛИС различно. Метод М4 также за счёт увеличения стоимости обеспечивает построение двухуровневых комбинационных схем с одинаковым временем формирования выходных сигналов.

Пусть, как и в [1], комбинационная схема задана системой булевых функций (СБФ), представленных в дизъюнктивной нормальной форме (ДНФ). СБФ будем характеризовать числом N выходных функций (выходных переменных) множества Y = {y₁,...,y_N} и числом L аргументов функций (входных переменных) множества X = {x₁,...,x_L}. Кроме того, каждая функция y_i характеризуется числом Q(y_i) слагаемых (элементарных конъюнкций) в ДНФ функции y_i, i = ¯1,N.

В предлагаемых методах синтеза рассматриваются три архитектурные модели ПЛИС: "классические" PAL (Programmable Array Logic), универсальные PAL и CPLD (Complex Programmable Logic Device) [1]. "Классические" PAL характеризуются числом входов n, числом выходных макроячеек m и числом q промежуточных шин, подсоединяемых к каждой макроячейке. Универсальные PAL характеризуются числом входов n, числом выходных макроячеек с одной обратной связью m, числом выходных макроячеек с двумя обратными связями m₂, а также множеством Q = {q₁,...,q_k}, где q_s - число промежуточных шин, подсоединяемых к макроячейке MC_s, q_s € Q, s = ¯1,k, k = m + m₂. Функциональный блок CPLD характеризуется числом входов n, выходных макроячеек m, суммарным числом промежуточных шин функционального блока q_E и максимальным числом промежуточных шин q_max, которые могут быть подсоединены к одной макроячейке.

Синтез двухуровневых комбинационных схем с различным временем формирования выходных сигналов (метод М3)

Вначале рассмотрим метод М3 для универсальных PAL, а затем метод уточним для "классических" PAL и CPLD.

Метод М3 синтеза двухуровневых комбинационных схем состоит из трёх этапов. На первом этапе определяется множество Y* реализуемых функций; на втором этапе выполняется второй этап метода М2 синтеза одноуровневой комбинационной схемы с использованием монтажного соединения выходов ПЛИС по ИЛИ [1]; на третьем этапе логические функции ИЛИ реализуются вторым уровнем PAL.

Поскольку в двухуровневой схеме каждая функция y_i, y_i € Y, реализуется на отдельной макроячейке PAL, то для каждой функции можно выбирать прямое или инверсное представление функции, а требуемый вид на выходе определять путём программирования логического уровня выходного сигнала макроячейки PAL.

Необходимым и достаточным условием построения первого уровня PAL является выполнение неравенств:

r_i n + k – 1, для всех i = ¯1,¯N, (1)

где r_i = min(r(y_i),r(¯y_i)); ý_i € {y_i,¯y_i}; r(y_i) и r(¯y_i) - максимальный ранг (число литералов) конъюнкций в представлении функций y_i и ¯y_i, соответственно, i = ¯1,¯N.

Пусть условия (1) выполняются для всех функций СБФ Y. Из двух функций y_i и ¯y_i, i = ¯1,¯N, в множество Y* выбирается функция ý_i, для которой выполняются условия (1) и значение Q(y_i) для которой меньше. В случае равенства значений Q(y_i) и Q(¯y_i) в множество Y* выбирается функция ý_i, для которой меньше значение r(ý_i).

Второй этап синтеза выполняется в полном соответствии с алгоритмом 1 из [1].

Пусть в результате выполнения второго этапа синтеза некоторые функции СБФ Y реализованы на PAL первого уровня, а для оставшихся функций Y’, Y’ Y, определено множество Z = {z₁,...,z_G} частей функций, которые необходимо объединить по ИЛИ с помощью PAL второго уровня. Обозначим через Z(ý_i) множество частей функции ý_i, Z(ý_i) Z, ý_i € Y’.

Для выполнения третьего этапа синтеза построим булеву матрицу W следующим образом. Строкам матрицы W поставим в соответствие части z₁,...,z_G, а столбцам - реализуемые функции ý₁,..., ý_N. На пересечении строки i и столбца j матрицы W ставится единица, если z_i € Z(ýj). Отметим, что нулевые столбцы матрицы W будут соответствовать функциям, реализованным на PAL первого уровня.

Теперь задачу синтеза второго уровня PAL можно сформулировать следующим образом.

Задача 1

Найти минимальное столбцовое покрытие матрицы W минорами W₁,...,W_T таким образом, чтобы для каждого минора выполнялись условия:

|Y_t| k;
|Z_t| n + k – |Y_t|, t = ¯1,¯T,

а также для каждого столбца j минора W_T нашлось значение q_s, q_s € Q, такое, что выполняется

|Z(y_j)| q_s,

причём различным столбцам минора W_T должны соответствовать различные значения q_s, q_s € Q; где Y_t - множество функций, соответствующих столбцам минора W_T; Z_t - множество частей функций (промежуточных функций), соответствующих строкам минора W_T, t = ¯1,¯T.

Отметим, что в задаче 1 находится столбцовое покрытие матрицы W минорами W₁,...,W_T, то есть если в минор W_T включается некоторый столбец, то он включается со всеми своими единицами. Поэтому задача 1 имеет решение только при выполнении следующих неравенств (достаточные условия реализации СБФ Y двухуровневой схемой на универсальных PAL):

|Z(ý_j)| q_max, (2)
|Z(ý_j)| n + k – 1 для всех ý_j € Y’,

где q_max - максимальный элемент множества Q.

Первое неравенство в (2) обеспечивает достаточное число промежуточных шин, подсоединяемых к одной макроячейке PAL, для объединения по ИЛИ всех частей каждой функции ý_j, ý_j € Y’. Второе неравенство в (2) обеспечивает достаточное число входов PAL второго уровня для приёма значений всех промежуточных функций, из которых состоит функция ý_j, ý_j € Y’.

Таким образом, необходимыми и достаточными условиями реализации СБФ Y двухуровневой схемой на универсальных PAL является выполнение неравенств (1) и (2).

Пусть в формируемый минор W_T уже включено некоторое количество столбцов матрицы W. Столбец j матрицы W может быть включен в минор W_T при выполнении неравенств:

|Y_t| + 1 k; (3)
|Z_t Z(ý_j)| n + k – |Y_t| – 1,

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

|Z(ý_j)| q_s, (4)

причём различным ý_j, ý_j € Y_t, должны соответствовать различные q_s, q_s € Q.

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

Алгоритм 1

1. Полагается t := 0.
2. Полагается t := t + 1, Q* := Q, начинается формирование очередного минора W_T. В качестве опорного в минор W_T включается столбец j, для которого

   |Z(ý_j)| = max,

   полагается:

   Y_t := {ý_j};
   Z_t := Z(ý_j);
   Q_t := |Z(ý_j)|,

   где Q_t - число задействуемых промежуточных шин t-й PAL.

3. Осуществляется покрытие столбцов матрицы W минором W_T. Для этого среди ненулевых столбцов матрицы W отыскивается столбец j, для которого выполняются условия (3) и (4). Если таких столбцов может быть выбрано несколько, то среди них выбирается столбец, для которого

   |Z_t Z(ý_j)| = max,

   а среди них столбец, для которого

   |Z(ý_j) \ Z_t| = min.

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

   Y_t := Y_t {ý_j};
   Z_t := Z_t Z(ý_j);
   Q_t := Q_t + |Z(ý_j)|.

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

4. Выполняется назначение макроячеек PAL реализуемым функциям. Для каждой функции ý_j, ý_j € Y_t, среди свободных макроячеек PAL с числом промежуточных шин, удовлетворяющих условию (4), выбирается макроячейка с минимальным значением q_s. Функция ý_j назначается для реализации на s-ю макроячейку t-й PAL, полагается Q* := Q* \ {q_s}.

   Обнуляются столбцы, вошедшие в минор W_T. Если в матрице W остались ненулевые столбцы, то выполняется переход к пункту 2; иначе - к пункту 5.

5. Конец.

Замечание 1

Для реализации второго уровня комбинационной схемы могут также задействоваться свободные ресурсы PAL первого уровня.

Пример

Рассмотрим реализацию СБФ для примера 2 из [1] двухуровневой схемой на универсальных PAL, имеющих те же параметры, что и в примере 2 из [1]. Синтез первого уровня схемы полностью совпадает с примером 2 из [1]. Необходимость введения PAL второго уровня возникает для реализации значений функций y₂, y₄ и y₈. В данном случае имеем:

¯y₂ = z₁ + z₂;
¯y₄ = z₃ + z₄;
¯y₈ = z₅ + z₆,

где

z₁ = x₁·¯x₅·¯x₆·¯x₈ + x₁·x₅·¯x₆·x₈;
z₂ = ¯x₁·¯x₅·x₆·x₈ + ¯x₁·x₅·x₆·x₈;
z₃ = x₃·¯x₇·x₉;
z₄ = ¯x₂·¯x₃·x₇·x₉ + x₂·¯x₃·x₇·¯x₉;
z₅ = ¯x₅·x₆·¯x₇·¯x₈·x₉ + x₅·¯x₆·¯x₇·x₈·x₉;
z₆ = x₅·x₆·x₇·x₈·x₉ + ¯x₅·¯x₆·x₇·¯x₈·¯x₉.

Матрица W, построенная для синтеза второго уровня комбинационной схемы, приведена в табл. 1. В результате синтеза первого уровня комбинационной схемы на PAL7 реализуется только одна часть (z₃) функции ¯y₄ и остаются свободными два двунаправленных вывода. Поэтому, если на один свободный вывод PAL7, согласно замечанию 1, подать значение подфункции z₄, то на другом свободном выводе PAL7 можно сформировать значение функции y₄.

Таблица 1. Матрица W для синтеза второго уровня комбинационной схемы

Отметим, что значение промежуточной функции z₃ на вход матрицы AND PAL₇ поступает по внутренним цепям обратных связей. Для реализации функций y₂ и y₈ необходимо ввести в схему дополнительную PAL₈, на которой задействуются все выводы. Окончательная реализация двухуровневой комбинационной схемы показана на рисунке.

Не смотря на то, что число PAL, по сравнению с [1], увеличилось на единицу, двухуровневая комбинационная схема имеет ряд преимуществ:

• отпадает необходимость в монтажном соединении выходов ПЛИС по ИЛИ;
• для каждой реализуемой функции допускается программирование логического уровня выходного сигнала;
• для реализации может быть выбрана любая из функций y_i или ¯y_i, i = ¯1,¯N, в зависимости от того, какая из функций лучше подходит для реализации;
• синтезированная комбинационная схема может использоваться во встроенных цифровых системах, поскольку выходы комбинационной схемы не обязательно должны быть выходами ПЛИС.

Рисунок 1. Реализация СБФ одноуровневой схемой на универсальных PAL с использованием монтажного объединения выходов по ИЛИ

Поскольку "классические" PAL не позволяют программировать логический уровень выходных сигналов, то при синтезе двухуровневых комбинационных схем в качестве множества y_i* реализуемых функций выбирается одно из множеств y_i = {y_i1,...,y_iN} или ¯y_i = {¯y_i1,..., ¯y_iN} в зависимости от того, в какой логике (прямой или инверсной) функционирует цифровая система.

Если принять k := m и q_s := q, s = ¯1,¯k, то метод М3 для "классических" PAL полностью совпадает с рассмотренным методом М3 для универсальных PAL.

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

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

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

Выбор множества y_i* реализуемых функций при синтезе двухуровневой комбинационной схемы на CPLD выполняется в полном соответствии с выбором множества y_i* для универсальных PAL, только вместо условий (1) рассматриваются условия (5).

Синтез второго уровня комбинационной схемы на CPLD сводится к решению следующей задачи.

Задача 2

Найти минимальное столбцовое покрытие матрицы W минорами W₁,...,W_T таким образом, чтобы для каждого минора выполнялись условия:

|y_t| m;
|Z_t| n,
Q_t q_s,

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

|Z(y_j)| q_max,

где y_t - множество функций, соответствующих столбцам минора W_T; Z_t - множество частей функций (промежуточных функций), соответствующих строкам минора W_T;

q_s - суммарное число промежуточных шин одного функционального блока CPLD; q_max - максимальное число промежуточных шин, которое может быть подключено к одной макроячейке CPLD.

Задача 2 имеет решение только при выполнении следующих неравенств (достаточные условия реализации СБФ Y двухуровневой схемой на CPLD):

|Z(y_j)| q_max, (6)
|Z(y_j)| n для всех y_j € Y’.

Таким образом, необходимыми и достаточными условиями реализации СБФ Y двухуровневой схемой на CPLD является выполнение неравенств (5) и (6).

При решении задачи 2 некоторый столбец j может быть включен в минор W_T при выполнении неравенств:

|y_t| + 1 m;
|Z_t Z(y_ij)| n; (7)
Q_t + |Z(y_j)| q_s.

Для решения задачи 2 может быть использован алгоритм 1. Для этого вместо условий (3) и (4) следует рассматривать условия (7), а в пункте 4 каждая реализуемая функция y_j, y_j € y_it, может назначаться на любую свободную выходную макроячейку t-го функционального блока CPLD.

Синтез двухуровневых комбинационных схем с одинаковым временем формирования выходных сигналов (метод М4)

Существенным недостатком рассмотренного метода М3 синтеза двухуровневых комбинационных схем на ПЛИС является то, что время формирования значений функций, реализуемых на первом и втором уровнях схемы, различно. Чтобы устранить данный недостаток, необходимо, чтобы длина пути сигналов от входа до выхода схемы для каждой функции была одинакова. В данном случае этого можно добиться, если значение каждой функции будет формироваться на втором уровне схемы.

Безусловно, обеспечение одинакового времени формирования значений функций связано с увеличением стоимости реализации (числа используемых макроячеек ПЛИС) комбинационной схемы. Однако в отдельных случаях увеличение стоимости реализации вполне оправдано. На практике, например, для того, чтобы обеспечить одинаковое время формирования выходных сигналов комбинационной схемы, на её выходы устанавливают регистры, то есть программируют выходы ПЛИС как регистровые. Это приводит к общему снижению быстродействия комбинационной схемы, а также необходимости формирования сигналов синхронизации и управления регистром, что в итоге приводит к усложнению проекта.

Чтобы обеспечить одинаковое время формирования выходных сигналов, достаточно в методе М3 считать, что после выполнения второго этапа синтеза на первом уровне схемы не реализована ни одна из функций множества y_i. Для этого при выполнении третьего этапа синтеза в множество Z включаются функции, реализованные на первом уровне. В матрице W, построенной для выполнения третьего этапа синтеза, подобным функциям будут соответствовать столбцы, содержащие только одну единицу.

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

Методы М3 и М4 реализованы программно в пакете ZUBR. В качестве эталонных примеров для проверки предлагаемых методов синтеза использовались комбинационные схемы, разработанные в центре MCNC [3]. Экспериментальные исследования проводились только для метода М3 в сравнении с методом синтеза, реализованном в пакете MAX+PLUSII версии 10.1 фирмы Altera. В качестве ПЛИС рассматривались универсальные PAL семейства CLASSIC. Эффективность метода оценивалась по двум параметрам: стоимости и быстродействию. В качестве стоимости было принято число макроячеек ПЛИС, затрачиваемых на реализацию комбинационной схемы, а в качестве быстродействия - максимальная задержка прохождения сигналов со входа на выход синтезированной схемы.

Результаты экспериментальных исследований приведены в табл. 2, где C_A - стоимость реализации СБФ с помощью метода пакета MAX+PLUSII; C₃ - стоимость реализации СБФ с помощью метода М3; C_A/C₃ - отношение C_A к C₃; D_A - максимальная задержка, измеряемая в наносекундах, прохождения сигналов со входа на выход комбинационной схемы, синтезированной с помощью метода пакета MAX+PLUSII; D₃ - то же, но для комбинационной схемы, синтезированной с помощью метода М3; D_A/D₃ - отношение D_A к D₃.

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

Name	L	N	P	CA	C3	CA/C3	DA	D3	DA/D3
9sym	9	1	87	27	11	2,45	44	44	1,00
Alu4	14	8	1028	554	94	5,89	270	44	6,14
Apex1	45	45	206	(1)	192	-	(1)	44	-
Apex2	39	3	1035	(1)	96	-	(1)	44	-
Apex3	54	50	280	333	227	1,47	108	44	2,45
Apex4	9	19	438	564	144	3,92	106	44	2,41
B12	15	9	431	9	9	1,00	20	20	1,00
Cps	24	109	654	235	173	1,36	44	44	1,00
Ex1010	10	10	1024	770	96	8,02	304	44	6,91
Inc	7	9	34	14	14	1,00	32	44	0,73
Pdc	16	40	1280	(1)	48	-	(1)	20	-
Seq	41	35	1459	407	288	1,41	122	44	2,77
Table3	14	14	175	114	100	1,14	54	44	1,23
Table5	17	15	158	101	108	0,94	42	42	1,00
Z9sym	9	1	420	230	10	23	272	44	618
					1616	51,6		634	32,82
mid					107,7	4,3		42,27	2,76

Анализ полученных результатов показывает, что применение метода М3, по сравнению с методом пакета MAX+PLUSII, при синтезе комбинационных схем на ПЛИС семейства CLASSIC позволяет значительно снизить стоимость реализации (в среднем, в 4,3 раза, а для отдельных примеров - в 23 раза) и повысить быстродействие (в среднем, в 2,76 раза, а для отдельных примеров - в 6,91 раза).

Выводы

1. К положительным качествам методов М3 и М4 синтеза двухуровневых комбинационных схем относятся:
   • методы применимы, в отличие от метода М2, в цифровых системах как с отрицательной, так и с положительной логикой, а также для любых ПЛИС (не требуется наличия программируемых опций open-drain и pull-up);
   • метод М4 обеспечивает одинаковое время формирования выходных сигналов.
2. К недостаткам методов М3 и М4 относится:
   • снижение быстродействия в два раза, по сравнению с методами М1 и М2;
   • увеличение стоимости реализации, по сравнению с методом М2, особенно для метода М4;
   • различное время формирования значений выходных функций при использовании метода М3.
3. Методы М3 и М4 представляют собой альтернативу методу М2, а также могут использоваться в ситуациях, когда метод М2 не применим, например, когда цифровая система функционирует в положительной логике, ПЛИС не допускает монтажное соединения выходов и др.

Литература

1. Соловьев В.В., Климович А. Синтез на ПЛИС одноуровневых комбинационных схем // Chip News. 2003. № 6. С. 20–27.
2. Соловьев В.В., Климович А. Введение в проектирование на ПЛИС комбинационных схем // Chip News. 2003. № 5. С. 16–22.
3. Yang S. Logic synthesis and optimization benchmarks user guide. Version 3.0. Technical Report, Microelectronics Center of North Carolina, 1991. 43 p.