Full Text

Введение. Программируемые логические интегральные схемы (ПЛИС) являются одним из самых востребованных сегментов рынка элементной базы цифровой аппаратуры, выпускаемой с середины 80-х гг. ХХ в. [1-3]. К ПЛИС в настоящее время относят также и микросхемы систем на кристалле SoC (System-on-a-Chip) [4] и так называемые системы в пакете-SiP (System-in-Package), представляющие собой объёмные сборки разных микросхем [5, 6]. Имеются многочисленные модификации ПЛИС, но их делят на два основных класса: FPGA (field-programmable gate array), в которых логические функции реализуются в СДНФ (совершенной дизъюнктивной нормальной форме) в генераторах функций, представляющих собой дерево транзисторов (LUT-Look Up Table), CPLD (complex programmable logic devices), в которых вычисляются системы логических функций в дизъюнктивной нормальной форме (ДНФ) [7-11]. Так, на сайте фирмы «Интел» [12] указаны следующие продукты: Stratix10 (14 нм), Stratix V (28 нм), Arria 10 (20 нм), Arria V (28 нм), Cyclone10 (20 нм), Cyclone V (28 нм), MAX10 (55 нм), причём MAX 10 одновременно числится и по разряду CPLDs (complex programmable logic devices), в который входят также и MAX V (возможно 90 нм), MAX II (скорее всего 0,15 мкм). По классу SoC проходят ПЛИС Stratix10, Arria 10, Arria V, Cyclone 10, Cyclone V. На сайте другой крупнейшей фирмы производителя ПЛИС-Xilinx [13] представлены микросхемы ПЛИС Spartan-6 (45 нм), Virtex-7, Kintex-7, Artix-7, Spartan-7 (28 нм),Virtex UltraScale, Kintex UltraScale (20 нм), Virtex UltraScale+, Kintex UltraScale+ (16 нм). Имеются так называемые адаптивные логические модули АЛМ [14], оптимально конфигурируемые под требуемое число переменных. Всё начиналось с реализации логических функций до 4 переменных, в АЛМ возможна реализация любых функций 7 переменных и некоторых функций 8 переменных. Использование технологии tri-gate [15-17] позволило достичь нового уровня быстродействия или энергоэффективности. Изобилие ресурсов привело к созданию резервированных структур ПЛИС [18]. В связи с этим вызывает интерес вопрос ускорения вычислений логических функций и автоматных отображений за счёт так называемой декомпозиции по Шеннону [19]. Дело в том, что наличие уже десятков миллионов логических элементов дает возможность комбинационной реализации многих алгоритмов, реализуемых ранее только последовательностыми автоматами. Рассмотрим особенности такой декомпозиции, применяемой в настоящее время, и предложим подход к её дальнейшему развитию. 1. Декомпозиция при выполнении арифметических операций. Дизъюнктивное разложение Шеннона (булева факторизация) по некоторой i-й переменной [20] позволяет разложить логическую (булеву) функцию f на две подфункции в виде дизъюнктивной нормальной формы (ДНФ), в одной из которых i-я переменная равна 0, а в другой - 1. Пусть эта переменная х, которая может быть в выражении f как без инверсии, так и с инверсией, так же, как и другие переменные y,z…w, тогда разложение Шеннона по х имеет вид: (1) Конъюнктивное разложение Шеннона (используется конъюнктивная нормальная форма (КНФ)) по х имеет вид: (2) Разложение Шеннона функций небольшого числа переменных удобно выполнять по таблице истинности. Например, проанализируем функции полного однобитного сумматора (рис. 1). Функция суммы при (верхняя часть таблицы) становится суммой по модулю два , а при (нижняя часть таблицы) - эквиваленцией Функция переноса при - это конъюнкция а при - дизъюнкция Таким образом, при изменении данных (Date 1 = A, Date 2 = B) подфункции вычисляются без учёта переноса, который используется для выбора одной из двух подфункий. Логический элемент ПЛИС содержит генераторы функций LUT-2 (Look Up Table) и мультиплексоры 2-1 (рис. 2). Рис. 1. Дизъюнктивное разложение Шеннона функций полного сумматора Рис. 2. Использование декомпозиции в логическом элементе при динамическом арифметическом режиме (LEin Dynamic Arithmetic Mode) Мультиплексоры на основе передающих транзисторов (Pass Transistors) 2-1, по существу, представляют собой LUT-1 на одну переменную без настройки входов данных. Следовательно, фактически происходит одновременная реализация двух подфункций суммы и двух подфункций переноса, зависящих от Date 1(A), Date 2 (B), которые затем выбираются старшей переменной Carry-In 0, Carry-In 1. 2. Декомпозиция при реализации последовательностного автомата. При реализации последовательностного автомата (автомата с памятью) для увеличения максимальной частоты реализации автоматных отображений за счет разложения Шеннона «укорачивается» петля обратной связи [19]. На рис. 3 показана «длинная» обратная связь, реализующая некоторую функцию переходов: (3) Рис. 3. «Длинная» обратная связь А, В, С - это векторы входных переменных соответствующего автомата. Здесь указан синхронный триггер (T, flip-flop) на выходе реконфигурируемого LUT, входящего в состав так называемого адаптивного логического модуля ALM. Частота синхронизации CLC рассчитывается с учетом задержки в петли обратной связи на трёх последовательных ALM и логике четвертого ALM, поэтому суммарная задержка относительна велика, и она включает задержку в элементах маршрутизации. Эта обратная связь «длинная», потому что проходит через матрицу локальных связей, где возможны значительные задержки сигналов. Одна переменная А, В или С для АLМ, реализующего функции 4 и даже в ряде случаев 7 и 8 переменных, - не показательный случай, поэтому пусть это будут некие векторы: (4) например, (5) Допустим, имеем такую функцию переходов: (6) Выполняем разложение Шеннона (Shannon decomposition or Boolean factorization), получаем: (7) (8) На рис. 4 показана реализация двух этих функций в разных LUT ALM. При этом число переменных уменьшено на одну за счет исключения переменной состояния триггера у. Рис. 4. «Короткая» обратная связь при введении разложения Шеннона Поэтому петля обратной связи короткая, и задержка определяется только задержкой логики последнего АLМ. Такой подход увеличивает аппаратные затраты, но они несущественны для ПЛИС, имеющей уже десятки миллионов таких логических элементов, здесь главное - скорость. Все это называется гипероптимизацией. Поиск возможностей такой оптимизации осуществляется гиперретаймингом. Дальнейшее продвижение этого направления может привести к тому, что такое разложение будет выполнено по всем переменным. 3. Логический элемент, реализующий декомпозицию по старшей переменной. Развитие направления декомпозиции по Шеннону может привести к тому, что задержка на вычисление логических функций будет сведена к минимуму, который определяется выбором одной из конституент всего одним транзистором однорангового дерева. В этом случае целесообразно использовать вектор входного набора в унитарном коде: (9) В выражении (9) позиция в одном из разрядов определяет входной вектор функции (рис. 5). Для уменьшения затрат на реализацию таких «декомпозированных» функций большого числа переменных предлагается использовать модифицированный унитарный код, включающий несколько бит, например три: (10) Тогда, например, определяет группу из двух переменных , которые уже подлежат дешифрации (рис. 6). Рис. 5. Выбор одного из значений функции f унитарным кодом входного вектора Рис. 6. Выбор одного из значений функции f унитарным кодом входного вектора Возникает задача нахождения оптимальной декомпозиции по Шеннону - по нескольким переменным, так, чтобы и трассировка переменных, и LUT были не слишком сложными, с одной стороны, и задержка на вычисление логической функции не слишком увеличилась, с другой. Предлагается также LUT с двумя выходами декомпозиции по старшей переменной (рис. 7). Рис. 7. LUT-3 с двумя предлагаемыми выходами декомпозиции по старшей переменной А, F(ABC) - существующий выход Функционирование предлагаемого LUT-3 в зависимости от значения старшей переменной показано на рис. 8. а б Рис. 8. Функционирование предлагаемого LUT-3: а - старшая переменная А = 0; б - старшая переменная А = 1 В этом случае создается возможность контроля функционирования LUT путём тестирования с использованием математического аппарата булевых производных, описанного, например, в [20]. Для этого необходимо создать тест, т.е. такие функции, в которых изменение старшей переменной приводит к разным значениям подфункций. Выводы. Таким образом, для обеспечения быстродействия ПЛИС разработчики передовых фирм идут по пути усложнения проектов с использованием разложения Шеннона, что позволяет, кроме прочего, уменьшить длину обратной связи в последовательностном автомате. Следует ожидать увеличение возможностей комбинационных реализаций схем конечных автоматов, традиционно реализуемых последовательностно в силу имеющихся ранее ограничений на количество логических элементов и объём памяти. В связи с этим предлагается унитарный LUT, когда активна только одна входная переменная. Похожий принцип используется при маршрутизации связей в ПЛИС. Например, условия для этого создаст унитарное кодирование памяти автомата. Такой LUT будет обладать максимальным быстродействием. Для снижения аппаратурных затрат возможно комбинированное кодирование входного вектора, что, конечно, ухудшит быстродействие вычисления значений логических функций. С целью упрощения контроля таких вычислений предложен LUT с двумя выходами декомпозиции по старшей переменной. Использование модифицированного LUT позволит уменьшить время диагностирования. Целью дальнейших исследований может быть рассмотрение предложенного LUT с встроенным элементом сложения по модулю два.

About the authors

S. F Tyurin

Perm National Research Polytechnic University; Perm State National Research University

M. A Chudinov

Perm National Research Polytechnic University; Morion PJSC

References

Statistics

Views

Abstract - 132

PDF (Russian) - 35

Refbacks

• There are currently no refbacks.