STUDY OF THE MULTI-INPUT LUT COMPLEXITY

S. F. Tyurin, A. V. Grekov

Abstract


Сontex. The programmable logic integrated circuits FPGA (field-programmable gate array) used realization of the generator of
functions LUT (Look Up Table), which is configured by loading a configuration memory for calculating a logic function in perfect
disjunctive normal form (PDNF). The LUT dimension determines the technological limitations of Mead and Conway on the number of
series-connected MOS transistors. The standard number of LUT inputs for many years was 3 or 4, and 4-LUT is constructed from two 3-
LUTs with an additional 1-LUT. However, in many projects, it is required to calculate functions of a large number of arguments. This
requires a multi-input LUT, which is built as a decomposition of 3-LUT, 4-LUT. The speed of computing logic functions determines by the
delay in the coupling matrices, so this decomposition leads to a decrease in performance. In recent years, the direction of adaptive logical
modules (ALM) has been actively developing, in which the user has access to various versions of logical elements for five, six and even
seven, eight variables, which leads to an increase in performance. However, the manufacturer’s documentation does not provide a detailed
description of the features of such multi-input LUTs, taking into account the Meade-Conway constraints. In addition, there are no estimates
of complexity and speed of multi-input LUTs. The analysis of sources allows suggests a further increase in the LUT bit capacity and the
convergence of FPGA and CPLD (complex programmable logic devices) capabilities in terms of bit depth. Therefore, studies of the features
of constructing multi-input LUTs are relevant and the authors attempted to analyze the implementation of such prospective multi-bit logic
Objective. The purpose of this work is to estimate the complexity and speed of the decomposition of a multi-bit LUT.
Method. Obtaining expressions for estimating the complexity and speed of decomposition of a multi-bit LUT on a LUT of a lower bit
length.
Results. A comparison of the complexity and delay in the number of transistors in the decomposition of a multi-bit LUT in the
computer mathematics system Mathcad is performed.
Conclusions. The conducted researches made it possible to establish the features of constructing multi-bit LUTs and to evaluate
various variants of decomposition with further increase in the LUT dimension with the subsequent choice of the optimal ALM variant.

Keywords


logic element; FPGA; LUT; transistor; adaptive logic module; decomposition; complexity; speed.

References


Kharchenko V. Green IT Engineering / V. Kharchenko,

Y. Kondratenko, J. Kacprzyk (Eds.) // Concepts, Models, Complex Systems Architectures, Studies in Systems, Decision and Control. – Berlin, Springer. – 2017. – Vol. 74. DOI: 10.1007/978-3-319-44162-7.

Kharchenko V. Concepts of Green IT Engineering: Taxonomy, Principles and Implementation / [Kharchenko V., Illiashenko O.]

// Green IT Engineering: Concepts, Models, Complex Systems

Architectures, Studies in Systems, Decision and Control. – 2017. – Vol. 74. – P. 3–20. DOI: 10.1007/978-3-319-44162-7_1.3. Kondratenko Y. P. PLC-Based Systems for Data Acquisition and

Supervisory Control of Environment-Friendly Energy-Saving

Technologies / Y. P. Kondratenko, O. V. Korobko, O. V. Kozlov

// Green IT Engineering: Concepts, Models, Complex Systems

Architectures, Studies in Systems, Decision and Control. – 2017. – Vol. 74. – P. 247–267. DOI:10.1007/978-3-319-44162-7_13.

Stratix III Device Handbook, Volume 1 [electronic resource],

access mode: https://www.altera.com/content/dam/altera-www/

global/en_US/pdfs/literature/hb/stx3/ stratix3_ handbook.pdf

Intel HyperFlex FPGA Architecture Overview [electronic resource], access mode: https://www.altera.com/products/fpga/stratix-series/stratix-10/features.html#hyperflexarchitecture

Understanding How the New Intel HyperFlex FPGA Architecture Enables NextGeneration High-Performance Systems [electronic resource], access mode: https://www.altera.com/products/fpga/stratix-series/stratix 10/features.html#hyperflexarchitectur.

Tyurin S. F. The decoding of LUT FPGA configuration of the finite state machine with Quartus II / S. F. Tyurin, A. V. Grekov // International Journal of Applied Engineering Research. – 2016. – Vol. 11, No. 20. – P. 10264–10266.

Tyurin S. Green Logic: Models, Methods, Algorithms / S. Tyurin, A. Kamenskih // Green IT Engineering: Concepts, Models, Complex Systems Architectures, Studies in Systems, Decision and Control. – 2017. – Vol. 74. – P. 69–86. DOI: 10.1007/978-3-319-44162-7_13.

Presentation on ALTERA’S FPGA Technology [electronic

resource], Access mode: http://www.authorstream.com/

Presentation/hsrathore158-1410279-fpga

Tyurin S. Green Logic: Green LUT FPGA Concepts, Models and Evaluations / S. Tyurin // Green IT Engineering: Concepts, Models, Complex Systems Architectures, Studies in Systems, Decision and Control. – 2017. – Vol. 74. – P. 241–261. ISBN: 978-3-319-55594-2.


GOST Style Citations


1. Kharchenko V. Green IT Engineering / V. Kharchenko,
Y. Kondratenko, J. Kacprzyk (Eds.) // Concepts, Models, Complex Systems Architectures, Studies in Systems, Decision and Control. – Berlin, Springer. – 2017. – Vol. 74. DOI: 10.1007/978-3-319-44162-7.
2. Kharchenko V. Concepts of Green IT Engineering: Taxonomy, Principles and Implementation / [Kharchenko V., Illiashenko O.]
// Green IT Engineering: Concepts, Models, Complex Systems
Architectures, Studies in Systems, Decision and Control. – 2017. – Vol. 74. – P. 3–20. DOI: 10.1007/978-3-319-44162-7_1.3. Kondratenko Y. P. PLC-Based Systems for Data Acquisition and
Supervisory Control of Environment-Friendly Energy-Saving
Technologies / Y. P. Kondratenko, O. V. Korobko, O. V. Kozlov
// Green IT Engineering: Concepts, Models, Complex Systems
Architectures, Studies in Systems, Decision and Control. – 2017. – Vol. 74. – P. 247–267. DOI:10.1007/978-3-319-44162-7_13.
4. Stratix III Device Handbook, Volume 1 [electronic resource],
access mode: https://www.altera.com/content/dam/altera-www/
global/en_US/pdfs/literature/hb/stx3/ stratix3_ handbook.pdf
5. Intel HyperFlex FPGA Architecture Overview [electronic resource], access mode: https://www.altera.com/products/fpga/stratix-series/stratix-10/features.html#hyperflexarchitecture
6. Understanding How the New Intel HyperFlex FPGA Architecture Enables NextGeneration High-Performance Systems [electronic resource], access mode: https://www.altera.com/products/fpga/stratix-series/stratix 10/features.html#hyperflexarchitectur.

7. Tyurin S. F. The decoding of LUT FPGA configuration of the finite state machine with Quartus II / S. F. Tyurin, A. V. Grekov // International Journal of Applied Engineering Research. – 2016. – Vol. 11, No. 20. – P. 10264–10266.
8. Tyurin S. Green Logic: Models, Methods, Algorithms / S. Tyurin, A. Kamenskih // Green IT Engineering: Concepts, Models, Complex Systems Architectures, Studies in Systems, Decision and Control. – 2017. – Vol. 74. – P. 69–86. DOI: 10.1007/978-3-319-44162-7_13.
9. Presentation on ALTERA’S FPGA Technology [electronic
resource], Access mode: http://www.authorstream.com/
Presentation/hsrathore158-1410279-fpga
10. Tyurin S. Green Logic: Green LUT FPGA Concepts, Models and Evaluations / S. Tyurin // Green IT Engineering: Concepts, Models, Complex Systems Architectures, Studies in Systems, Decision and Control. – 2017. – Vol. 74. – P. 241–261. ISBN: 978-3-319-55594-2.





DOI: https://doi.org/10.15588/1607-3274-2018-1-2



Copyright (c) 2018 S. F. Tyurin, A. V. Grekov

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
Zaporizhzhya National Technical University, 
Zhukovskiy street, 64, Zaporizhzhya, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.