Introduction

Nowadays, the creation and widespread use of modern supercomputers in various fields of knowledge and mathematics has made it possible to successfully solve complex mathematical and algorithmic problems offline, and in some cases online. Such supercomputers were developed by leading global companies (Intel, IBM, DEC, Motorola, ARM, SPARC, MIPS, PowerPC) [1][2][3][4]. Logical and computational operations in known supercomputers are usually implemented in binary arithmetic of the Rademacher number system. Supercomputers with 64-bit architecture, including EM64T, Turion 64, Xeon, Core2, Corei3, Corei5, Intel (IA-64 (Itanium)), UltraSPARC (Sun Microsystems), MIPS64 (MIPS) [4] can be applied in all branches of industry and in military field (special equipment).

Modern supercomputers, which include thousands of parallel processors, allow performing Teraflops (TFLOPS) of arithmetic and logical operations in one second in real time. Multi-bit supercomputers can also be used as system components of complex distributed CPS [5,6]. Through deep parallelization of computational operations, such supercomputers make it possible to solve multi-bit matrices in algebraic equations, simulate complex physical processes, perform pattern recognition and solve 3D digital holography problems. An important structural feature of well-known scalar and vector superprocessors is the large width of the processed digital data within the range of 128-2048 bits. This leads to the high level of relevance of the development of high-performance MSPs that execute arithmetic and logical operations of comparison, addition, multiplication, division, exponentiation and finding residues modulo in various number systems.

For the creation of such MSPs synchronized binary adders (SBA) can be beneficially used [7,8].

Recently, the problem of data crypto protection and cryptanalysis in computer networks and CPS has become relevant. Such data is also processed on the basis of multi-bit binary codes (1024-4096 bits) [9].

In particular, efficient and fast-acting solutions to such problems are needed in the conditions of military operations and modern information front, for example, data reprogramming of the functions of drones, missiles, unmanned aerial vehicles, ground launchers and high-performance processors of air defense systems.

A promising solution to these problems and applied data problems is the development and application of a new class of MSP based on binary arithmetic and synchronized binary adders (SBA) [10]. An example of such solutions is the development and use of multi-bit carry-look-ahead adders [11,12] and adder-accumulators [13] as components of ALU in supercomputers. Such SBAs are important components of multi-bit high-performance parallel and flow multipliers [12].

Related works

Multi-bit adder-accumulators are the basic components of ALUs of supercomputers. The main criterion of such components is the maximum speed of performing addition of multi-bit binary numbers, which determines the corresponding performance of supercomputer cores.

In [1][2][3][4][5]11,24], structural microelectronic implementations of classic combinational adders and adder-accumulators built on the basis of binary arithmetic were presented. The main shortcoming that does not allow significantly increasing the speed of such components in modern computer systems and superprocessors is the use of binary arithmetic, which involves ripple-carry overs between bits, which is a particularly negative factor in increasing the speed of multi-bit computing devices.

A structure of a single-bit binary full adder was shown in [7], in which the delay of ripple carry overs (Сout) is 2 clock cycles, and generation of the sum bit (Si) is 6 clock cycles (Fig. 1).

Figure 1: Microelectronic structure of a single-bit binary full adder

For example, when performing addition of two n-bit mono binary codes (MBC), signals are delayed in the computing device, respectively, by n clock cycles. That is, performing an addition operation with classic multi-bit binary adders (MBA) with direct information inputs and outputs, the register capacity of ALU of supercomputer core is from 128 to 2048 bits and the signal delay is from 256 to 4096 clock cycles, respectively.

At the same time, the relevant problem, which is presented in this article, is the development of improved structural solutions of adder-accumulators, which allow increasing the speed by 1-2 orders compared to known structures, according to the proposed binary arithmetic, which does not include ripple-carry overs, when performing addition operations and accumulation of the sums of binary codes. A deep comparative analysis of the proposed structures in relation to the classical ones is presented by the authors in [12,15,17].

Criteria and system characteristics of the synchronized ALU components of multi-bit supercomputers

Synchronized ALU components of supercomputer cores are memory registers and adder matrices (fig. 2) [14,12,15]. 1.

1 1 n m k i j i j S X Y = = = + ∑ ∑ ; 2. 1 m j j τ τ = = ∑ ; 3.1 1

;

n m j i input i output i i f f f β λ = = = × + × ∑ ∑ 4. 1 n П i i A А = = ∑ ; 5.1 1

.

m n П ij j i A А = = = ∑∑

The main system characteristics of the ALU matrix components are the following ones: 1. SK -is determined by the total number of inputs/outputs of the microelectronic structure according to Quine's criterion;

2. τ -time complexity is determined by the total number of clock cycles of signal delay in the longest chain of logical or functional series connected components between the corresponding inputs/outputs of the device, where m is the number of series connected components; tj -signal delay in each j-th component, υ -a number of clock cycles;

3. fj -functional completeness of the device inputs/outputs, which is determined by the overall estimate, where fj is the functional and informational characteristic of the device structure; B, J are the information coefficients of the input/output functions; m, n -the number of inputs and outputs; finput, foutput -functions of inputs/outputs, e.g., input/output channel (x/y), input/output buses (n/m), sync input, crystal selection (c/s), power supply (+/-); 4. A -hardware complexity of the device, which is calculated as the total number of logic elements and gates in the microelectronic structure of the devices, where AП is the overall estimate of the hardware complexity, i, j, k are the types of components or levels of the device structure m, n, l.

Functional structures and circuitry of single-bit synchronized binary adders

A functional feature of the SBA is the ability to store bits of sum (Si) and carry (Cout) until the clock cycle of their use by the MSP in the microcycles of streaming data processing algorithms.

In microelectronics, well-known synchronized logic elements (AND, OR, NAND, NOR, XOR, NOT) and triggers of RS, D, T and JK types are used as components of special-purpose processors (SP) [7,8].

At the same time, single-bit SBA and multi-bit adders, which are characterized by minimax characteristics of speed and hardware complexity, are not fully presented and studied nowadays in literature in the field of computer circuitry and microelectronics.

Fig. 3 shows the developed functional and microelectronic structures of a single-bit synchronized adder-accumulator (SAA) based on a single-bit full binary adder [10]. They are characterized by enhanced functionality compared to known structures. ) sum and store the qubits of the output ripple carry-overs, which makes it possible to apply it in the structures of quantum computers [16]. Such a SAA has the following system characteristics:

1. Structural complexity of an adder: 4 3 7

k S = + = . 2. Input/output speed parameters: 1 ( ) 2 i i i a b S τ ν → =; 2 ( 3 7 9 ) 4 i i out a b C τ ν → → → → = ; 3 (8 9

) SAA2 includes data inputs and outputs: Si -data bit; Cin -ripple carry input; Sx -synchronization; R -reset of D-triggers to the zero state; Cout -the output of the ripple carry; NSi -the output of the accumulated sum.

3 i i out a b C τ ν → → → = ; 4 (7

The structure of such SAA2 includes a single-bit binary full adder based on two series connected XOR logic elements (indicated by dashed borders) and two D-triggers that store the ripple carry bit (Cout) and the accumulated sum bit (NSi).

Such SAA2 has the following system characteristics: 1. Structural complexity of the adder: 4 2 6 k S = + = .

2. Input and output speed parameters:

1 ( 1 4 2 ) 4 i j S T NS τ ν → → → → = ; 2 ( 1 6 1 ) 4 i out S T C τ ν → → → → = ; 3 ( 6 1) 3 in C T τ ν → → = ; 4 ( 4 2) 3 in C T τ ν → → = .

3. fi -input and output functional completeness: 4 2 6 i f = + = .

4. A -hardware complexity:

2 2 6 4 10

SAA T A A A + = = + = (logical elements).

Adder-accumulators SAA1 and SAA2 are the basic components of multi-bit synchronized adderaccumulators (MSAA), which are functional special-purpose processors of multi-bit supercomputer cores. Such components are prioritized by the characteristics of maximum speed, when solving complex computational problems including determination of one-dimensional and two-dimensional sums.

Fields of applications and circuit structure of multi-bit synchronized adder-accumulators (MSAA)

MSAAs are widely used as processor components for statistical, correlation, spectral, and entropy data processing [15]. When calculating these characteristics, the following algorithms are used:

∑ = = n i i x X n M 1 1 ; ∑ + + = + = j n j i j i j X n M 1 1 ; ∑ + + = + − = j n j i j i j i v X V n M 1 1 ; ∑ = − = n i x i x M X n D 1 2 ) ( 1 ,(1)

where, -variance and standard deviation, respectively.

In Figures 6 -12, the analytics and asymptotics of basic autocorrelation functions (ACF), which include multiple sum accumulation operations and are widely used in practice for correlation analysis and pattern recognition. Euclidean and Hamming distances are estimated in pattern recognition based on RGB color image processing [15] according to the following expressions:

, ) ( H xx 1 0 + = 0 = ∞ ) ( H xx o j i n i o i xx x sign x sign n j H + = ∑ ⋅ = 1 1 ) (      < − ≥ + = 0 , 1 0 , 1 o i o i o i x x x signxx x K M ∞ = ∑ = + ⋅ = n i j i i xx x x n j K 1 1 ) ( Figure 8: Covariance ACF x xx D ) ( R = 0 , 0 = ∞ ) ( R xx ∑ = + ⋅ = n i j i o o i xx x x n j R 1 1 ) ( Figure 9: Correlation ACF , ) ( xx 1 0 + = ρ 0 = ∞ ρ ) ( xx x xx xx D j R j ) ( ) ( = ρ , ( ) ∑ = − = n i x i x M x n D 1 2 1 Figure 10: Normalized ACF 0 0 = ) ( C xx , x xx D ) ( C = ∞ ∑ = + − = n i j i i xx x x C n j 1 2 ) ( 1 ) ( Figure 11: Structural ACF 0 0 = ) ( G xx , x xx M ) ( G = ∞ ∑ = + − ⋅ = n i j i i xx x x G n j 1 1 ) (

1. Euclidean distance: 2 ( , ) ( )

i j d i j x x = − ∑ ; (3)

where, , i j

x x -image features.

Manhattan distance:

1 1

( , )

M N m i j i j d i j x y = = = − ∑ ∑ . (4)

Static distance:

1 2 1 1 ( , ) ( )

P M N S i j i j d i j x y = = = − ∑ ∑ , P → ∞ . (5)

4. Chebyshev distance:

( , ) max

c i j d i j x x = − ∑ . (6)

5. The distance of the least ( 1 D ) and most ( 2 D ) remote cluster neighbors:

{ } 1 ( , ) min ij D A B d = ; i A → ; j B → ; { } 2 ( , ) max ij D A B d = . (7)

6. Pairwise average:

1 1 1 ( , ) ( , ) A B S S j D A B d i j A B i = = = ∑ ∑ × . (8)

7. Centroid method:

( , ) ( ( , ))

S S D A B d ic jc = , (9)

where, , ic jc -centroids of image clusters A and B.

8. Ward's method: ( , ) ( )

S e D A B d A B = × , (10)

where, 2 ( )

e k d x x = − ∑ , k

x -pixel coordinates, x -mathematical expectation of coordinates.

Calculation of the cumulative histogram of a two-dimensional color image as the sum of the probabilities of separate colors is as follows [18,19]: (11) Probabilistic entropy is estimated according to C. Shannon in the following way [20]: ( )

n S i n S P i V S ∈ = ∑ 0 log , S k j k j j p p H k = = − ∑(12)

where, x H -entropy estimate; k -coefficient of the algorithm base (2,10,e,..); i P -the probability of a random process.

For each image segment, the variance of the deviations of Pi(i) and P2(i) values from the arithmetic mean value is calculated as an iterative procedure.

The given list of analytical expressions and corresponding algorithms for digital data processing allow us to solve the important problems of applied mathematics and microelectronic circuits to provide the conditions for minimax criterion of speed and hardware complexity of MSAA structures.

The developed MSAA microelectronic circuitry (Fig. 13) is implemented on the basis of the series connection of single-bit full SAAs1 (Fig. 4) and half SAAs2 (Fig. 4). The n-bit group of such an adder includes SAAs2, and more significant bits contain SAAs1 [21]. The application of such MSAA as a component of MSP is presented in Fig. 13. Addition and accumulation of the n-sum of k-bit binary numbers is performed in each microcycle during 4 clock cycles, regardless of their bitness.

For example, when adding n=256 of k-bit numbers, the total number of microcycles is

1 4 1024 N n = =

, that is, in comparison with known devices of this class, in which ripple carry-overs are available in each microcycle, the total number of microcycles for the considered example, with the number capacity of ( ,..., ,...,

n n j j S S S C C C • • • • • • , (13)

where, j C

• is a bit of a ripple carry, j S

• -a bit of a sum in j-th position of the MSAA output code, correspondingly.

Theoretical background and examples of computational operations on binary codes are given in Section 4 of this paper.

In case, when the results of accumulating the sum of many binary numbers are practically used in mono binary codes, the resulting binary code is converted into a mono binary code using a multi-bit binary carry-look-ahead adder [22]. The functional structure of such a multi-bit carry-lookahead adder is shown in Fig. 14. The delay of ripple carry signals in the structure of a multi-bit carrylook-ahead adder in the first and final modules is 2 clock cycles, and in other modules it is 1 clock cycle. Each component of a multi-bit carry-look-ahead adder (∑) in Fig. 14 is presented by the microelectronic structure of a multi-bit binary adder, which is shown in Fig. 15. An example of a 4-bit functional structure of the carry-look-ahead adder, which is a component of the decoder of the MSAA output binary code, is shown in Fig. 15 [22,23]. The performance of such components of the binary code decoder [22] is 2 clock cycles, respectively. That is, when the capacity of the input binary code is n=256, the total signal delay is 48 clock cycles.

According to the example shown in Fig. 6, it can be seen that when the binary number position is (k=128) and taking into account that the sequentially generated bits of ripple carry (Cj) and bit sums (Sj) are to be converted, then the output mono binary code of the accumulated sum is generated in 2 24 48 × =clock cycles. That is, increasing the speed of accumulating the sum by multi-bit adderaccumulators (MAA) and presenting calculation results by mono binary code is, respectively, (133120 48) /1024 130 sm k = ÷ = times. In this case, the MAA performance improving coefficient practically decreases by 0.01%. More in-depth studies of the system performance characteristics and hardware complexity of this class of microelectronic binary accumulative codes should take into account the existing circuit design technologies developed by well-known companies (Texas Instruments, Analog Devices), which is beyond the scope of this work.

Application of MSAA as the ALU component of multi-bit vector and scalar supercomputers

Binary arithmetic of the ALU in multi-bit supercomputer is based on registration of bits of sum ( . j S ) and bits of ripple carry-overs ( . j C ) in each position.

An example of generating a binary code as a result of adding two mono binary codes (x and у) is presented in the following graph.

1 1 0 1 1 0 1 1 2 1 1 0 ( , ... , , ... , , ) , ... , , ... , , ( , .

.. , , ... , ) ( )

n i n i n n i i x a a a a b b b b C S C S C S C S y d • − − • • • • • • • • − + = = < < < < + = ,(14) where, 1 0 ;

2

n i i i x a • − = = ∑ 1 0 ; 2 n i i i y b • − = = ∑ 1 1 1 0 0 . 2 2 n n i i i i i d S C i • • • − − + = = = + ∑ ∑

Thus, each position of a binary number is presented by two bits that correspond to quaternary arithmetic according to Table 1.

Notation of a binary code (BC) position in binary arithmetic Table 1 Truth table of binary code

0 0 0 0 1 S 1 0 2S 1 1 3S

A simplified demonstration of the operation of generating a binary code is shown as an example of adding two 8-bit Fermat and Mersenne numbers, which correspond to the following numbers in the decimal and mono binary number systems 255(10) = 11111111(2); 129(10) = 10000001(2). Let us notate these numbers as a binary code and perform the operation of addition on them. The use of binary codes in the ALU structures of supercomputers makes it possible to increase the speed of calculations and the performance of digital data processing by 1-3 orders. Such computational operations on the data are implemented according to the analytical expressions presented in Section 3 (1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12). It is especially efficient when solving complex mathematical and algorithmic problems in the field of cryptography, holography and pattern recognition by processing images represented by RGB pixels of digital video cameras.

Conclusion

The proposed new functional and microelectronic structures of synchronized binary adders make it possible to significantly expand the scope of applications of multi-bit adders of digital data, and to increase their speed by 1-3 orders compared to known structures.

The presented theoretical and applied solutions of binary arithmetic significantly expand the possibilities of using ALU coprocessors in the computing environment of vector and scalar supercomputers.