Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

Designing on FPGA and SoC high-performance binary comparators of a big dimensionality
Authors
	Salauyou V.V.
Date of publication
	2016
Abstract
	A design method of comparator hierarchical structures on FPGAs and SoCs with big dimensionality and high per-formance is offered. The method allows to change the number of levels of the comparator hierarchical structure in a wide range. As a result the user can select a compromise between the implementation cost and the performance. The synthesis circuit of the comparator is a completely combinational circuit and it does not contain clock signals therefore the comparator does not require additional circuits for creation of the clocks (unlike known methods). Besides, in the offered approach there are no cascaded carries, all computations are executed by parallel operations that provides very high-speed performance. The two-level hierarchical structure of comparators consists of the first level comparators and the combina-tional circuit CL. Each first level comparator CMPn is the binary comparator on M1 bits, which realizes functions "greater" gn and "equal" en, n= . The combinational circuit CL from the values of the functions generated by the first level comparators forms the values of the output functions "greater" G and "equal" E for the whole hierarchical structure. by means of the following logical equations (1) and (2). The hierarchical two-level structure in fig. 1, in turn, can appear as comparators of the first level. Generally the hierarchical multi-level structure of comparators can be provided as in fig. 1, where compara-tors are at the first level and the combinational circuit CL realizes hierarchical connections of functions "greater" and "equal". The hierarchical two-level structure can represent itself as comparators of the first level. Continuing in a similar way further, it is possible to build the multi-level hierar-chical structure of comparators of the big dimensionality. The generalized multi-level hierarchical structure of com-parators we will designate by means of the formula (3), where Mt is the width of words in bits for the comparators of the level t, t= , Nt-1 is the number of comparators on the previous level t-1 (from which the comparators of level t are constructed). In the formula (3) the conditions (4) should be satis-fied. The number T in the formula (3) defines the number of logic levels (a depth) of the comparator hierarchical structure. The synthesis of hierarchical structures of comparators is executed on the basis of the formula (3) under fulfillment of (4). Note that the various hierarchical structures, with different depths, with various the numbers of units, and the various widths of binary words at each level can be constructed for the same comparator. As the number of LUT’s inputs for the majority of FPGA families it is equal 4, it is offered for all hierarchical structures of comparators on the first level to use 2-bit comparators. Let A = (a2, a1) and B = (b2, b1) are the input words of the 2-bit comparator. The Boolean function "equal" for the 2-bit comparator can be written as (5) and (6). The Boolean function "greater" for the 2-bit compara-tor after minimization has the following view: Thus, the specific hierarchical structure of the compar-ator is defined by the formula (3) under fulfillment of (4). Comparators of the first level are implemented on the basis of the logical equations (5) and (6), and combina-tional circuit CL on each level is defined by means of the logical equations (1) and (2). The hierarchical structure by the nature has the least delay the signal propagation in comparison with sequential decomposition. Therefore it is possible hope for that hierarchical structure of the designed comparator will have small of an implementation cost and a high high-speed performance. The logical equations (1) and (2), describing combinative circuits CL of hierarchical structure, and also the equation (5) and (6) comparators of the first level are rather simple. Therefore it is possible hope for that by means of hierarchical structures it is possible to build binary comparators of enough big dimensionality. Hypothesis. The offered technique of the hierarchical structures synthesis of binary comparators allows to build on FPGA and SoC high-performance comparators of the big dimensionality. Open there is a question: what the formula (3) of the comparator hierarchical structure best approaches for an implementation of the certain dimensionality comparator on the specific family FPGA or SoC. The answer to this question in the offered approach is defined empirically by a performance of a great number of experimental researches. The hierarchical structures of binary comparators were researched on FPGA and SoC of Altera by using Quartus II design software. All projects of the comparators were described in lan-guage Verilog. The synthesis results of the hierarchical structures of the comparators were compared to a traditional implementation of the comparator in language Verilog, When functions “greater” also are “equal” described by means of appropriate operations in forms: assign G = (A>B) and assign E = (A==B). Let us mark that thus received results completely coin-cide with the results that formed at an implementation of the comparators by means of parametrized Altera’s func-tion lpm_compare. The experiments were executed as follows. All possible hierarchical structures have been constructed for the comparators on 4, 8, 16, 32, 64, 128, and 256 bits, thus 128 comparators projects have been constructed (together with the comparator on 2 bits). For building of the comparators on 512 bits, the best (or close to the best) structures at least for one family FPGA were selected from the earlier constructed structures. The implementation cost (the number of used logical elements) and a high-speed performance (the maximum signal delay) were considered as criteria of an optimization. The hierarchical structures of the comparators on 1024, 2048, 4096 and 8192 bits have been constructed similarly. The analysis of the experimental research results shows that the offered method allows to increase performance, in comparison with the traditional approach, for comparators on 512 bits by 3.409 times, on 1024 bits by 4.987 times, on 2048 bits by 27.339 times, on 4096 bits by 65.596 times, and on 8192 bits by 127.395 times. The method also allows (for separate FPGA families) by 16 times to increase the dimension of input words for comparators which can
Keywords
	binary comparators, hierarchical structure, big dimensionality, high-performance, programmable logic de-vices, FPGA, SoC.
Library reference
	Salauyou V.V. Designing on FPGA and SoC high-performance binary comparators of a big dimensionality // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2016. Proceedings / edited by A. Stempkovsky, Moscow, IPPM RAS, 2016. Part 3. P. 198-205.
URL of paper
	http://www.mes-conference.ru/data/year2016/pdf/D016.pdf