Home
Authors Papers Year of conference Themes Organizations To MES conference
Designing on FPGA and SoC highperformance 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 performance 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 highspeed performance.
The twolevel hierarchical structure of comparators consists of the first level comparators and the combinational 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 twolevel structure in fig. 1, in turn, can appear as comparators of the first level.
Generally the hierarchical multilevel structure of comparators can be provided as in fig. 1, where comparators are at the first level and the combinational circuit CL realizes hierarchical connections of functions "greater" and "equal".
The hierarchical twolevel structure can represent itself as comparators of the first level. Continuing in a similar way further, it is possible to build the multilevel hierarchical structure of comparators of the big dimensionality. The generalized multilevel hierarchical structure of comparators 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= , Nt1 is the number of comparators on the previous level t1 (from which the comparators of level t are constructed).
In the formula (3) the conditions (4) should be satisfied.
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 2bit comparators.
Let A = (a2, a1) and B = (b2, b1) are the input words of the 2bit comparator. The Boolean function "equal" for the 2bit comparator can be written as (5) and (6).
The Boolean function "greater" for the 2bit comparator after minimization has the following view:
Thus, the specific hierarchical structure of the comparator 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 combinational 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 highspeed 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 highperformance 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 language 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 coincide with the results that formed at an implementation of the comparators by means of parametrized Altera’s function 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 highspeed 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, highperformance, programmable logic devices, FPGA, SoC. 
Library reference 
 Salauyou V.V. Designing on FPGA and SoC highperformance 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. 198205. 
URL of paper 
 http://www.mesconference.ru/data/year2016/pdf/D016.pdf 

