The fields of applications of multi-bit special-purpose processors for data processing in cyber-physical systems (CPS) are analyzed. Structures of multi-bit special-purpose processors (MSP) based on synchronized adders, which are used as components of arithmetic logic units (ALU) in multi-core vector and scalar supercomputers are classified. New efficient structures of MSPs, which process data given in mono binary and binary number systems, are proposed according to the criteria of maximum speed and reduced hardware complexity. The results of studies of the functional and structural, time and hardware characteristics of such MSPs are presented. Promising areas of their applications in scientific and industrial computerized systems are identified.
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-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.
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].
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-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.
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]. 3. 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].
System characteristics of combinational components of ALU: n m 1. Sk =∑ X i + ∑Yj ; i =1 j =1 m 2. τ = ∑τ j ; j=1
n m 3. f j = ∑ β i × finput + ∑λi × foutput ; i =1 i =1 n 4. AП = ∑ Аi ; i=1 m n 5. AП = ∑ ∑ Аij .
j=1 i=1
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.
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.
SAA includes data inputs (ai,bi,Cin,Sx) and outputs (Si,Cout, Cout ) and consists of two components, i.e., a combinational adder and D- trigger.
The combinational binary adder contains two series connected logic elements XOR (3,4), which are implemented on the basis of the proposed logical function "Exclusive AND" according to the expression:
Parallel generation of the output paraphase (qubit) ripple carry (Cout, Cout ) is implemented on the direct and inverse outputs of the D-trigger. Thus, the given structure of the SHAA allows us to generate the data output of ( Si =ai + bi ) 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: Sk = 4 + 3 = 7 .
parameters: τ 1(aibi → Si ) τ 3 (aibi → 8 → 9 → Cout ) =3ν ; τ 4 (Cin → 7 → 9 → Cout ) =4ν ; τ 5 (Sx → 9 → Cout ) = 2ν . 3. fi – functional completeness of inputs/outputs: fi = 4 + (2 + (1× 2)) = 4 + 4 = 8 . 4. A – hardware complexity: A = ASAA + AT = 6 + 2 = 8 (logical elements).
The described structure of the SAA is not characterized by the functional completeness for its use as a component of the adder-accumulator. =2ν ; τ 2 (aibi → 3 → 7 → 9 → Cout ) =4ν ;
SAA1 includes data inputs: Cinj – ripple carry, Sx – synchronization, R – reset of D-triggers to the zero state; data outputs (Coutj, NCj, NSj), and consists of a single-bit increment adder and two Dtriggers. This SAA1 has the following system characteristics: 1. Structural complexity of the adder: Sk = 3 + 3 = 6 .
2. Input and output speed parameters: τ 1(Cin → 3 → T1 → Cout ) =3ν ; τ 2 (Cin → 1 → T 2 → NS j ) =3ν ; τ 3 (Sx → T1)
=2ν . 3. fi - input and output functional completeness: fi = 3 + 3 = 6 . 4. A – hardware complexity: A = ASAA1 + 2 AT = 3 + 4 = 7 (logical elements).
The functional and developed microelectronic structures of a single-bit full adder-accumulator (SAA2) based on a single-bit full binary combinational adder are presented in Fig. 5.
a) b) Figure 5: Functional structure of a single-bit full adder-accumulator (SAA2) (а), microelectronic structure of a single-bit full adder-accumulator (SAA2) (b)
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.
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).
1. Structural complexity of the adder: Sk = 4 + 2 = 6 . 2.
Input and output speed parameters: τ 1(Si → 1 → 4 → T 2 → NS j ) =4ν ; τ 2 (Si → 1 → 6 → T1 → Cout ) =4ν ; τ 3 (Cin → 6 → T1) =3ν ; τ 4 (Cin → 4 → T 2) =3ν . 3. fi - input and output functional completeness: fi = 4 + 2 = 6 . 4. A – hardware complexity: A = ASAA2 + 2 AT = 6 + 4 = 10 (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. 5. 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: M x = 1 n
∑ X i ; M j = n i=1 1 n+ j
∑ X i+ j ; n i=1+ j
M v = 1 n+ j
∑Vi− j X i+ j ; n i=1+ j
Dx = 1 ∑n ( X i − M x ) 2 , n i=1 (1) where, i ∈1, n - sample size; j ∈ 0, m - discrete shift of data array, M x , M j , M v - respectively, selective, sliding and weighted mathematical expectations, which are calculated according to the expressions, ( X i − M x ) =Xi - centered digital data; Dx ,δ x - 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.
H xx ( j) = 1 n o o
∑ sign xi ⋅ sign xi+ j n i=1
o o + 1, xi ≥ 0 sign xi = o − 1, xi < 0
H xx ( 0 ) = +1, H xx ( ∞ ) = 0
Kxx( 0 ) = Dx + M x2 , Kxx(∞) =Mx2 Pxx( j) = 1 n o o
∑ xi⋅ sign xi+ j n i=1 Kxx( j) = 1 n
∑ xi ⋅ xi+ j n i=1 1 n o o Rxx( j) = ∑ xi⋅ xi+ j
n i=1 ρ xx( j) = Rxx( j) ,
Dx Dx = 1 ∑n (xi − M x )2
n i=1 Cxx( 0 ) = 0 , Cxx( ∞ ) = Dx C xx( j) = 1 ∑n(xi − xi+ j)2
n i=1 G xx ( j) =
Gxx ( 0 ) = 0 , Gxx ( ∞ ) = M x
=∑ (xi − x j )2 ; dm (i, j)
M N =∑∑ xi − y j .
i=1 j=1
M N P 1 dS (i, j) =(i∑=1 ∑j=1 xi − y j )2 , P → ∞ .
dc (i, j)
=max ∑ xi − x j .
DS ( A, B) = 1 A B
∑ ∑ dS (i, j) .
A × B i=1 j=1 DS ( A, B) = (dS (ic, jc)) , DS ( A, B) =de ( A × B ) , (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) where, xi , x j - image features.
5. The distance of the least ( D1 ) and most ( D2 ) remote cluster neighbors:
D1( A, B) = min {dij } ; i → A ; j → B ; D2 ( A, B) = max {dij } . where, ic, jc - centroids of image clusters A and B.
where, de =∑ (xk − x)2 , xk - 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]: n,S V1(S ) = ∑ P2 (i).
i∈n,S
S Hk = −k ∑ p j logk p j , j=0 (12) where, Hx - entropy estimate; k – coefficient of the algorithm base (2,10,e,..); Pi - 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 N1 =4n =1024 , 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 k =(128 ÷ 4096) , the signal delay in each microcycle, respectively, is N2 =256× ([512 ÷ 8192)] + log2 256 =(133120 ÷ 2099200) . That is, the performance of the improved MSAA, compared to the known one, increases by ksb =N1N2 = (133120 ÷ 2099200) /1024 =(130÷ 2050) times. As the capacity of the accumulated binary numbers increases, the performance increases by 1-3 orders.
It should be noted that the result obtained at the output of such an adder-accumulator is presented • • by a binary code of Cn S n type: • • • • • • Cn S n ,...,C j S j ,...,C1 S1 , (13) • • where, C j is a bit of a ripple carry, S j – 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
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.
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, ksm =(133120 ÷ 48) /1024 =130 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. 6. 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 . . ( S j ) and bits of ripple carry-overs ( C j ) 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.
x = ( an−1, ... , ai , ... , a1, a0 ) + y =( • d = ( bn−1, ...
, bi , ...
, b1, b0 ) , (14) •
• • • • • • •
Cn < Sn−1, ... , Ci+1 < Si , ... C2 < S1, C1 < S0 ) where, x = n∑−1ai •2i ; y = n∑−1bi •2i ; d• =n∑−1 Si • 2i + n∑−1Ci+1 • 2i .
i=0 i=0 i =0 i =0
Thus, each position of a binary number is presented by two bits that correspond to quaternary arithmetic according to Table 1.
Table 1 Truth table of binary code
• Ci+1
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. ... ...
, 0 < 1, , 0 < 0, ,1 < 0, , 0 < 0, ...
,1 < 0,
N-bit binary adder whose structure is presented in Fig. 17, allows us to add two multi-bit binary mono codes in 1 clock cycle, regardless of the input code capacity.
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-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.
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. 8. References [1] MIPS official website. Access mode: https://www.mips.com [2] IBM official website. Access mode: https://www.ibm.com [3] Intel official website. Access mode: https://www.intel.com [4] Arm official website. Access mode: https://www.arm.com [5] Sascha Julian Oks, Max Jalowski, Albrecht Fritzsche, Kathrin M. Moslein Cyber-physical modeling and simulation: A reference architecture for designing demonstrators for industrial cyber-physical systems // Procedia CIRP Design Conference 2019, P.257-264. [6] J. Wan, H. Yan, H. Suo, F. Li, Advances in Cyber-Physical Systems Research, KSII Transaction