Получены выражения для оценок сложности и быстродействия декомпозиции многоразрядного LUT на LUT меньшей разрядности Выполнено сравнение сложности и задержки в количестве транзисторов при декомпозиции многоразрядного LUT в системе компьютерной математики Mathcad. Установлены особенности построения многоразрядных LUT и оценены различные варианты декомпозиции при дальнейшем увеличении размерности LUT с последующим выбором оптимального варианта адаптивного логического модуля.
Выпуск #9/2018Греков Артем Владимирович, Тюрин Сергей Феофентович Совершенствование логики FPGA на основе увеличения разрядности LUT и создания адаптивных логических модулей
Получены выражения для оценок сложности и быстродействия декомпозиции многоразрядного LUT на LUT меньшей разрядности Выполнено сравнение сложности и задержки в количестве транзисторов при декомпозиции многоразрядного LUT в системе компьютерной математики Mathcad. Установлены особенности построения многоразрядных LUT и оценены различные варианты декомпозиции при дальнейшем увеличении размерности LUT с последующим выбором оптимального варианта адаптивного логического модуля.
ВВЕДЕНИЕ Логические элементы ЛЭ программируемых логических интегральных схем (ПЛИС) типа FPGA (field-programmable gate array) [1–4] — это постоянные запоминающие устройства ПЗУ (называемые часто LUT — Look Up Table), реализованные на мультиплексоре, входы данных которого настраиваются константами. Для настройки на заданную логическую функцию в ячейки ОЗУ (SRAM) загружается соответствующая таблица истинности. При активации одного из 2n путей в дереве транзисторов переменными значение логической функции считывается из соответствующей ячейки ОЗУ и передается на выход OUT. Инверторы по переменным обеспечивают реализацию всех членов совершенной дизъюнктивной нормальной формы (СДНФ). Оптимальным по быстродействию и сложности представления типовых логических функций является использование LUT на четыре переменных (рис. 1). Такой LUT для входных переменных х4, х3, х2, х1 (настройка — 16 бит) описывается выражением: Eqn001.eps(1) ПОСТАНОВКА ЗАДАЧИ Дано: адаптивные логические модули ПЛИС Stratix III на семь переменных.
В литературе [3–4, 6–7] не в полной мере освещены вопросы декомпозиции многоразрядных LUT. Необходимо оценить сложность и быстродействие при декомпозиции многоразрядного LUT с целью выявления особенностей построения адаптивных логических модулей и перспектив дальнейшего повышения разрядности. ОБЗОР ЛИТЕРАТУРЫ В ПЛИС Stratix III имеются адаптивные (перестраиваемые под требуемую задачу) логические блоки, которые объединяются в логические блоки (Logic Array Block, LAB) [2, 3], которые, как утверждается, реализуют функции даже семи переменных. Вызывают интерес особенности реализации таких LUT. Дело в том, что в силу ограничений Мида и Конвей на число последовательно соединенных транзисторов [5], дерево передающих транзисторов не может содержать более четырех транзисторов в цепочке. Необходима декомпозиция многоразрядного LUT на LUT меньшей разрядности, то есть построение дерева из поддеревьев. ПЛИС Stratix III описана в достаточном количестве источников [3, 4, 6, 7]. Имеются данные о возможном производстве таких ПЛИС на Воронежском заводе полупроводниковых приборов ВЗПП-Микрон, ОАО «КТЦ «Электроника» [8]. В структуру таких ПЛИС входят так называемые блоки LAB (logic array blocks), содержащие адаптивные логические модули ALM (adaptive logic modules), которые могут быть конфигурированы для реализации комбинационной логики, в том числе арифметических операций, а также для реализации автоматов с памятью. Архитектура ALM совместима с архитектурой 4-входовых LUT, а один ALM может также реализовывать любые функции до шести переменных и определенные функции семи переменных. Отмечается, что такая архитектура выигрывает по быстродействию и эффективности (вероятно, речь идет об аппаратных затратах и площади кристалла) — рис. 2. На рис. 2 указано восемь входов адаптивной LUT, что может создать впечатление о возможности реализации 8-LUT. Более подробная структура АЛМ0, АЛМ1, представленная на рис. 3, не вносит ясности в особенности реализации дерева 6-LUT. Еще более запутывает информация, содержащаяся в презентации [9], где указано, что для реализации k-LUT необходимо 2k бит SRAM и мультиплексор также 2k:1. Это попросту невозможно! Различные режимы использования ALM не проясняют деталей (рис. 4). Рассмотрим первоисточник — документацию на ПЛИС Stratix III [10], где приведена детализация ALM (рис. 5). Таким образом, выясняется, что ALM построен не только на двух 4-LUT, но имеются еще четыре LUT на 3 переменных (3-LUT), то есть из двух 3-LUT можно получить один 4-LUT. Следовательно, всего четыре 4-LUT, и тогда становится понятно, как строится 6-LUT — двумя старшими переменными e, f выбирают один из четырех! На рис. 5 не указаны управляющие сигналы на ряде мультиплексоров, обозначенных трапециями (LUT 1–6 тоже являются мультиплексорами, но изображены с управляющими сигналами, настройка подразумевается). МЕТОДЫ Пусть k — это размерность основного (базового) LUT (k ∈ {1, 2, 3, 4}). Для 1-LUT в принципе до n = 4 нет необходимости в выходном инверторе. Больше 4 по указанным ограничениям k в настоящий момент пока не практикуется. Оценим сложность LUT без декомпозиции («идеальная» сложность, поскольку такое может быть только до n = 4, не более): Eqn003.eps,(2) где 2n · 8 — количество элементов настройки (по каждому входу настройки необходимо шесть транзисторов SRAM и два транзистора для реализации инвертора на входе дерева передающих транзисторов); 2n — количество инверторов по n переменным; 2n+1 — количество элементов дерева передающих транзисторов с выходным инвертором. При декомпозиции n-дерева по k LUT, k ∈ {1, 2, 3, 4}, n ≥ k, n ≤ 8: Eqn005.eps,(3) где 2k+1 — сложность дерева k LUT; 2k — число транзисторов в k инверторах, таких деревьев необходимо 2n−k, для соединения получаемых при декомпозиции 2n−k деревьев необходимы еще LUT на 2n−k входов (которые тоже можно декомпозировать), соответственно сложность Eqn006.eps, где Eqn007.eps — сложность дерева с выходным инвертором, Eqn008.eps — сложность входных инверторов. Временная задержка при декомпозиции оценивается длиной максимального пути в логическом элементе со входа на выход. При этом без декомпозиции — при «идеальном» варианте (рис. 2) получим: Eqn009.eps.(4) Путь при декомпозиции в передающих транзисторах также оценивается величиной n, но за счет дополнительных инверторов на входе и выходе в цепочке LUT (рис. 5, 6) он будет больше: Eqn010.eps.(5) МОДЕЛИРОВАНИЕ В процессе исследования получены и промоделированы схемы различных вариантов многоразрядного LUT (n>4). Пример синтеза 6-LUT из четырех 4-LUT и одного 2-LUT приведен на рис. 6. На рис. 6 входы 2-LUT имеют инверторы, поэтому, поскольку число инверторов на пути сигнала четное, настройки записываются как обычно. РЕЗУЛЬТАТЫ Ограничимся n = 8, поэтому предполагается, что дополнительный LUT «поместится» в требуемые параметры декомпозиции по k LUT, k ∈ {1, 2, 3, 4}. Используем систему компьютерной математики Mathcad. Графики сравнения сложности декомпозиции по выражению (3) n LUT по k представлены на рис. 7. Результат ожидаемый — чем крупнее строительный блок, тем меньше затрат для реализации сложного LUT на 5, 6, 7 и 8 переменных. Графики изменения (5) при n = 5–8 изображены на рис. 8. Графики изменения (5) при n = 7–10 изображены на рис. 9. ОБСУЖДЕНИЕ Таким образом, в адаптивных логических модулях ПЛИС Stratix III имеется два 4-LUT, как и указано в переводных статьях. Однако, фактически имеются еще два LUT на 3 переменных (3-LUT), из которых можно построить два дополнительных 4-LUT. Всего получается четыре 4-LUT. Тогда понятно, как из них строится и 5-LUT и 6-LUT. Не вызывает затруднений и вопрос получения двух 5-LUT. Следовательно, настройка должна содержать не менее 64 битов для задания любой функции шести переменных. Целесообразно в дальнейшем путем анализа настройки АЛМ получить логическую модель и проверить по ней соответствие заявленных возможностей АЛМ с изображенными в документации вариантами. ВЫВОДЫ Анализ декомпозиции многоразрядных LUT показывает, что наиболее эффективным по сложности и быстродействию является использование в качестве «строительных блоков» 4-LUT, как указано в доступных источниках. Вызывает интерес построение LUT на базе так называемых 3D транзисторов [11–14], уже активно применяемых передовыми фирмами. Имеется информация о смягчении ограничения Мида и Конвей в таких технологиях. Кроме того, целесообразно в дальнейшем исследовать вопрос декомпозиции при введении в LUT средств обеспечения отказоустойчивости, предложенных в [15–20]. ЛИТЕРАТУРА 1. Строгонов А., Цыбин С. Программируемая коммутация ПЛИС: взгляд изнутри [Электронный ресурс]. URL: http://www.kit-e.ru/articles/plis/2010_11_56.php(дата обращения: 16.05.2017). 2. Угрюмов Е. П. Цифровая схемотехника: учебное пособие / Е. П. Угрюмов. — СПб: БХВ-Петербург, 2004. — 518 с. 3. Золотуха Р., Комолов Д. Stratix III — новое семейство FPGA фирмы Altera [Электронный ресурс]. URL: http://kit-e.ru/assets/files/pdf/2006_12_30.pdf (дата обращения 27.06.2017). 4. Использование ресурсов ПЛИС Stratix III фирмы Altera при проектировании микропроцессорных ядер [Электронный ресурс]. URL: http://www.kit-e.ru/articles/plis/2010_2_39.php (дата обращения: 20.05.2017). 5. Ульман Дж. Д. Вычислительные аспекты СБИС. Пер. с англ.: А. В. Неймана. Под ред. П. П. Пархоменко. — М.: Радио и связь, 1990. — 480 с. 6. Давыдов С. И. Проектирование функциональных блоков программируемой логической интегральной схемы, конфигурируемых с использованием метода сканирования пути [Электронный ресурс]. URL: http://www.dslib.net/tverdoteln-elektronika/proektirovanie-funkcionalnyh-blokov-programmiruemoj-logicheskoj-integralnoj.html (дата обращения 15.06.2017). 7. Быстрицкий А. В. Проектирование структуры межсоединений программируемых логических интегральных схем. [Электронный ресурс]. URL:http://www.dslib.net/tverdoteln-elektronika/proektirovanie-struktury-mezhsoedinenij-programmiruemyh-logicheskih-integralnyh.html (дата обращения 24.06.2017). 8. Открытое акционерное общество «Конструкторско-технологический центр «Электроника» [Электронный ресурс]. URL: http://www.edc-electronics.ru/upload/iblock/1cd/1cd2009ffa52599ff023b0843885fad6.pdf (дата обращения: 23.06.2017). 9. Presentation on ALTERA’S FPGA Technology. [Электронный ресурс]. URL: http://www.authorstream.com/Presentation/hsrathore158-1410279-fpga (дата обращения: 29.05.2017). 10. Logic Array Blocks and Adaptive Logic Modules in Stratix III Devices [Электронный ресурс]. URL: https://www.altera.com.cn/content/dam/altera-www/global/zh_CN/pdfs/literature/hb/stx3/stx3_siii51002.pdf (дата обращения: 29.05.2017). 11. Платформа 22i. [Электронный ресурс]. URL: http://www.achronix.ru/technology/22i-platform.html (дата обращения: 12.06.2017). 12. Intel выпустила первые процессоры семейства Ivy Bridge. [Электронный ресурс]. URL: http://www.cybersecurity.ru/pda/149408.html?seccode=pda&ID=149408&last= (дата обращения: 12.06.2017). 13. 3D-компьютерные чипы будут в тысячу раз производительней обычных. [Электронный ресурс]. URL: http://gearmix.ru/archives/22528 (дата обращения: 12.06.2017). 14. TSMC представила маршруты проектирования 16-нм FinFET на основе ядер Cortex-A15. [Электронный ресурс]. URL: http://www.3dnews.ru/762685 (дата обращения: 12.06.2017). 15. Тюрин С. Ф. Программируемое логическое устройство: патент РФ № 2544750; опубл. 20.03.2015, Бюл. № 8. 16. Тюрин С. Ф., Городилов А. Ю., Вихорев Р. В. Программируемое логическое устройство: патент РФ № 2547229; опубл. 10.04.2015, Бюл. № 10. 17. Греков А. В., Успаленко В. Б. Перспективные программируемые логические интегральные схемы FPGA фирмы Altera. «В мире научных открытий. Естественные и технические науки». — Красноярск: Научно-инновационный центр, 2014. — № 6.1(54). — С. 518–534. DOI: 10.12731/wsd-2014-6.1-13. 18. Tyurin S. F., Grekov A. V. The Checked Logic Element ChLUT FPGA. «In the World of Scientific Discoveries». — Krasnoyarsk: Publishing House Science andInnovation Center, 2014, 10 (58), pp. 223–231. DOI: 10.12731/wsd-2014-10-17. 19. Tyurin S. F., Grekov A. V. Functionally Complete Tolerant Elements / International Journal of Applied Engineering Research 10 (14): 34433–34442, 2015. ISSN 0973-4562. Research India Publications, 2015. 20. Tyurin S. F., Grekov A. V. The Decoding of LUT FPGA Configuration of the Finite State Machine with Quartus II / International Journal of Applied EngineeringResearch 11 (20): 10264–10266, 2016. ISSN 0973-4562. Research India Publications, 2016.