Синтез на ПЛИС двухуровневых комбинационных схем.|
В. Соловьев, А. Климович Синтез на ПЛИС двухуровневых комбинационных схемВ [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 где 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▓ Для выполнения третьего этапа синтеза построим булеву матрицу W следующим образом. Строкам матрицы W поставим в соответствие части z1,...,zG, а столбцам - реализуемые функции ý1,..., ýN. На пересечении строки i и столбца j матрицы W ставится единица, если zi € Z(ýj). Отметим, что нулевые столбцы матрицы W будут соответствовать функциям, реализованным на PAL первого уровня. Теперь задачу синтеза второго уровня PAL можно сформулировать следующим образом. Задача 1Найти минимальное столбцовое покрытие матрицы W минорами W1,...,WT таким образом, чтобы для каждого минора выполнялись условия: |Yt| а также для каждого столбца j минора WT нашлось значение qs, qs € Q, такое, что выполняется |Z(yj)| прич╦м различным столбцам минора WT должны соответствовать различные значения qs, qs € Q; где Yt - множество функций, соответствующих столбцам минора WT; Zt - множество частей функций (промежуточных функций), соответствующих строкам минора WT, t = ¯1,¯T. Отметим, что в задаче 1 находится столбцовое покрытие матрицы W минорами W1,...,WT, то есть если в минор WT включается некоторый столбец, то он включается со всеми своими единицами. Поэтому задача 1 имеет решение только при выполнении следующих неравенств (достаточные условия реализации СБФ Y двухуровневой схемой на универсальных PAL): |Z(ýj)| где qmax - максимальный элемент множества Q. Первое неравенство в (2) обеспечивает достаточное число промежуточных шин, подсоединяемых к одной макроячейке PAL, для объединения по ИЛИ всех частей каждой функции ýj, ýj € Y▓. Второе неравенство в (2) обеспечивает достаточное число входов PAL второго уровня для при╦ма значений всех промежуточных функций, из которых состоит функция ýj, ýj € Y▓. Таким образом, необходимыми и достаточными условиями реализации СБФ Y двухуровневой схемой на универсальных PAL является выполнение неравенств (1) и (2). Пусть в формируемый минор WT уже включено некоторое количество столбцов матрицы W. Столбец j матрицы W может быть включен в минор WT при выполнении неравенств: |Yt| + 1 а также, если среди свободных макроячеек t-й PAL найд╦тся макроячейка с числом промежуточных шин qs такая, что выполняется неравенство: |Z(ýj)| прич╦м различным ýj, ýj € Yt, должны соответствовать различные qs, qs € Q. С уч╦том сделанных замечаний, алгоритм решения задачи 1 выглядит следующим образом. Алгоритм 1
Замечание 1Для реализации второго уровня комбинационной схемы могут также задействоваться свободные ресурсы PAL первого уровня. ПримерРассмотрим реализацию СБФ для примера 2 из [1] двухуровневой схемой на универсальных PAL, имеющих те же параметры, что и в примере 2 из [1]. Синтез первого уровня схемы полностью совпадает с примером 2 из [1]. Необходимость введения PAL второго уровня возникает для реализации значений функций y2, y4 и y8. В данном случае имеем: ¯y2 = z1 + z2; где z1 = x1╥¯x5╥¯x6╥¯x8 + x1╥x5╥¯x6╥x8; Матрица W, построенная для синтеза второго уровня комбинационной схемы, приведена в табл. 1. В результате синтеза первого уровня комбинационной схемы на PAL7 реализуется только одна часть (z3) функции ¯y4 и остаются свободными два двунаправленных вывода. Поэтому, если на один свободный вывод PAL7, согласно замечанию 1, подать значение подфункции z4, то на другом свободном выводе PAL7 можно сформировать значение функции y4. Таблица 1. Матрица W для синтеза второго уровня комбинационной схемы
Отметим, что значение промежуточной функции z3 на вход матрицы AND PAL7 поступает по внутренним цепям обратных связей. Для реализации функций y2 и y8 необходимо ввести в схему дополнительную PAL8, на которой задействуются все выводы. Окончательная реализация двухуровневой комбинационной схемы показана на рисунке. Не смотря на то, что число PAL, по сравнению с [1], увеличилось на единицу, двухуровневая комбинационная схема имеет ряд преимуществ:
Поскольку "классические" PAL не позволяют программировать логический уровень выходных сигналов, то при синтезе двухуровневых комбинационных схем в качестве множества yi* реализуемых функций выбирается одно из множеств yi = {yi1,...,yiN} или ¯yi = {¯yi1,..., ¯yiN} в зависимости от того, в какой логике (прямой или инверсной) функционирует цифровая система. Если принять k := m и qs := q, s = ¯1,¯k, то метод М3 для "классических" PAL полностью совпадает с рассмотренным методом М3 для универсальных PAL. Необходимым и достаточным условием синтеза первого уровня комбинационной схемы на CPLD является выполнение неравенств: r(ýi) где n - число входов функциональных блоков CPLD. Выбор множества yi* реализуемых функций при синтезе двухуровневой комбинационной схемы на CPLD выполняется в полном соответствии с выбором множества yi* для универсальных PAL, только вместо условий (1) рассматриваются условия (5). Синтез второго уровня комбинационной схемы на CPLD сводится к решению следующей задачи. Задача 2Найти минимальное столбцовое покрытие матрицы W минорами W1,...,WT таким образом, чтобы для каждого минора выполнялись условия: |yt| а также для каждого столбца j минора WT выполнялось: |Z(yj)| где yt - множество функций, соответствующих столбцам минора WT; Zt - множество частей функций (промежуточных функций), соответствующих строкам минора WT; qs - суммарное число промежуточных шин одного функционального блока CPLD; qmax - максимальное число промежуточных шин, которое может быть подключено к одной макроячейке CPLD. Задача 2 имеет решение только при выполнении следующих неравенств (достаточные условия реализации СБФ Y двухуровневой схемой на CPLD): |Z(yj)| Таким образом, необходимыми и достаточными условиями реализации СБФ Y двухуровневой схемой на CPLD является выполнение неравенств (5) и (6). При решении задачи 2 некоторый столбец j может быть включен в минор WT при выполнении неравенств: |yt| + 1 Для решения задачи 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
Анализ полученных результатов показывает, что применение метода М3, по сравнению с методом пакета MAX+PLUSII, при синтезе комбинационных схем на ПЛИС семейства CLASSIC позволяет значительно снизить стоимость реализации (в среднем, в 4,3 раза, а для отдельных примеров - в 23 раза) и повысить быстродействие (в среднем, в 2,76 раза, а для отдельных примеров - в 6,91 раза). Выводы
Литература
|
n + k √ 1, для всех i = ¯1,¯N, (1)
Y, определено множество Z = {z1,...,zG} частей функций, которые необходимо объединить по ИЛИ с помощью PAL второго уровня. Обозначим через Z(ýi) множество частей функции ýi, Z(ýi) 
Z(ýj)| 
Z(ýj)| = max,
| Ваш комментарий к статье | ||||
