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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 1

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

|Yt| k;
|Zt| n + k √ |Yt|, t = ¯1,¯T,

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

|Z(yj)| qs,

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

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

|Z(ýj)| qmax, (2)
|Z(ýj)| n + k √ 1 для всех ýj € Y▓,

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

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

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

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

|Yt| + 1 k; (3)
|Zt Z(ýj)| n + k √ |Yt| √ 1,

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

|Z(ýj)| qs, (4)

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

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

Алгоритм 1 Полагается t := 0. Полагается t := t + 1, Q* := Q, начинается формирование очередного минора WT. В качестве опорного в минор WT включается столбец j, для которого |Z(ýj)| = max,

полагается:

Yt := {ýj};
Zt := Z(ýj);
Qt := |Z(ýj)|,

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

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

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

|Z(ýj) \ Zt| = min.

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

Yt := Yt {ýj};
Zt := Zt Z(ýj);
Qt := Qt + |Z(ýj)|.

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

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

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

Конец. Замечание 1

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

Пример

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

¯y2 = z1 + z2;
¯y4 = z3 + z4;
¯y8 = z5 + z6,

где

z1 = x1╥¯x5╥¯x6╥¯x8 + x1╥x5╥¯x6╥x8;
z2 = ¯x1╥¯x5╥x6╥x8 + ¯x1╥x5╥x6╥x8;
z3 = x3╥¯x7╥x9;
z4 = ¯x2╥¯x3╥x7╥x9 + x2╥¯x3╥x7╥¯x9;
z5 = ¯x5╥x6╥¯x7╥¯x8╥x9 + x5╥¯x6╥¯x7╥x8╥x9;
z6 = x5╥x6╥x7╥x8╥x9 + ¯x5╥¯x6╥x7╥¯x8╥¯x9.

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

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

  y2 y4 y8 z1 1 0 0 z2 1 0 0 z3 0 1 0 z4 0 1 0 z5 0 0 1 z6 0 0 1

Отметим, что значение промежуточной функции z3 на вход матрицы AND PAL7 поступает по внутренним цепям обратных связей. Для реализации функций y2 и y8 необходимо ввести в схему дополнительную PAL8, на которой задействуются все выводы. Окончательная реализация двухуровневой комбинационной схемы показана на рисунке.

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

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

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

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

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

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

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

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

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

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

Задача 2

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

|yt| m;
|Zt| n,
Qt qs,

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

|Z(yj)| qmax,

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

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

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

|Z(yj)| qmax, (6)
|Z(yj)| n для всех yj € Y▓.

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

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

|yt| + 1 m;
|Zt Z(yij)| n; (7)
Qt + |Z(yj)| qs.

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

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

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

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

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

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

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

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

Таблица 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 раза).

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

Литература

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







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




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