RU2848159C1 - Device for multiplying binary matrices - Google Patents

Abstract

FIELD: computer technology.

SUBSTANCE: device for multiplying matrices, containing a matrix of n×n operational blocks (where n is the size of the square matrices being multiplied), first and second blocks of matrix coefficients, a shift register, a group of n two-stage registers, each operational block comprising a first, second and third trigger, first, second, and third AND elements, first and second OR elements, an inverter, each of the matrix coefficient blocks contains n×n storage blocks, each of the storage blocks contains an AND element, a flip-flop, a group of n AND elements, a group of n OR elements, a first group of n flip-flops is introduced as part of each storage block, a second group of n triggers, a third group of n triggers, included in the coefficient block – a first group of of (n–1) two-stage registers, a second group of (n–1) two-stage registers, a group of n×n triggers, a group of n×(n–1) OR elements.

EFFECT: reduction in the processing time of square binary matrices by means of pipelining the read operation from a specialised multi-port memory.

1 cl, 5 dwg

Description

The device is related to computing technology and can be used to multiply square binary matrices of size n × n elements.

A device for multiplying arbitrary square matrices is known (Patent of the Russian Federation for Utility Model No. 193927. Device for Multiplying Binary Matrices. Claimed on June 26, 2019, published on November 21, 2019, Bulletin No. 33), comprising a matrix of n × n operational blocks (where n is the size of the square matrices being multiplied), first and second blocks of matrix coefficients, a shift register, a group of n two-stage registers, each operational block comprising the first, second, third trigger, the first, second, third AND elements, the first, second OR elements, an inverter, each of the matrix coefficient blocks contains n × n storage blocks, each of the storage blocks contains an AND element, a trigger, a group of n AND elements, a group of n OR elements [1].

The disadvantage of this device is the large time costs involved in multiplying binary matrices and, as a consequence, low performance.

The closest in technical essence to the claimed device is the device (Patent of the Russian Federation for Utility Model No. 157948. Device for matrix multiplication. Class G06F 17/16, declared 07/08/2015, published 12/20/2015, Bulletin No. 35), containing a matrix of n × n operational blocks (where n is the size of the square matrices being multiplied), each of which contains the first, second and third registers, a multiplier and adder, a multiplexer, the first and second blocks of matrix coefficients, a shift register, a group of n two-stage registers, each of the blocks of matrix coefficients contains n × n storage blocks and a group of n output OR elements, each of the storage blocks contains a register, an AND element, a group of n AND elements, a group of n OR elements [2].

The disadvantage of this device is hardware redundancy and, as a result, high hardware complexity.

The technical objective of the proposed invention is to reduce the processing time of square binary matrices by pipelining the read operation from specialized multi-port memory.

The technical problem is solved by the fact that in the device,containingmatrix fromn×noperating blocks (wheren- the size of the square matrices being multiplied), the first and second blocks of matrix coefficients, a shift register, a group ofntwo-stage registers, each operational block contains the first, second, third trigger, first, second, third AND elements, first, second OR elements, inverter, each of the matrix coefficient blocks containsn × nstorage blocks, each of the storage blocks contains an AND element, a flip-flop, a group ofnelements I, group ofnOR elements,andfirst entrance( i,j )-th operating block (wherei=,j=) connected to the first output( i,j-1)-th operating block, second entrance( l,k )-th operating block (wherel=,k=) connected to the second output( l-1,k )-th operating block,-th output of the device output group is connected to the third output( n,k )-th operating unit, the synchronization inputs of all operating units are connected to the synchronization input of the matrix of operating units of the device, the third input( l,k )-th operating block (wherel=,k=) connected to the third output( l- 1,k )-th operating block, first entrance( i, 1)-th operating block (wherei=) connected toi-th output as part of the group of outputs of the first block of matrix coefficients, the second input(1,k )-th operating block (wherek=) connected tok-th output as part of the group of outputs of the second block of matrix coefficients, the control inputs of the operating blocks are connected to the control input of the device, and the reset inputs of the operating blocks are connected to the reset input of the device, which is also connected to the reset inputs of each ofntwo-stage registers, information inputm-th two-stage register (wherem=) connected to the output( m- 1)-th two-stage register, the information input of the first two-stage register is connected to the output of the shift register, the clock input of which is connected to the clock input of the device, which is also connected to the clock inputs of each ofntwo-stage registers, outputk-th (wherek=) two-stage register is connected tok-th input as part of the group of addresses of the reading lines of the second block of matrix coefficients and tok-th input as part of the group of addresses of the columns of reading the first block of matrix coefficients, the sync inputs of the first and second blocks of matrix coefficients are connected to the sync input of the device write, as part of each of the blocks of matrix coefficients, the sync input of the block of matrix coefficients is connected to the sync inputs of each ofn×nstorage blocks,k-th entrance (wherek=) as part of the group of addresses of the reading lines of the matrix coefficient block is connected to the input of the addresses of the reading lines(1, 1)-th storage block, k-th entrance (wherek=) as part of the group of read column addresses of the matrix coefficient block is connected to the input of read column addresses(1, 1)-th storage block, k-th entrance (wherek=) as part of the data input group from the previous line( m,p )-th storage block (wherem=,p=) connected tok-th data output for the next row( m- 1,p )-th storage block, k-th entrance (wherek=) as part of the group of addresses of recording rows of the matrix coefficient block is connected to the input of addresses of recording rows( i,k )-th storage block (wherei=),k-th entrance (wherek=) as part of the group of record column addresses of the matrix coefficient block is connected to the input of record column addresses( k,i )-th storage block (wherei=), the data input of the recording block of matrix coefficients is connected to the data input of the recording of each ofn×nstorage blocks, in each of the storage blocks the first input of the AND element is connected to the input of the column address of the storage block record, the second input is connected to the input of the row address of the storage block record, and the third input is connected to the input of the synchronization of the storage block, the output of the AND element is connected to the synchronization input of the trigger, the information input of the trigger is connected to the input of the data of the storage block record, the output of the trigger is connected to the first inputs of each ofnelements of the group of elements I, outputk-th element (wherek=) groups of elements AND is connected to the first inputk-th (wherek=) element of the OR group of elements, the second inputk-th (wherek=) element of a group of elements OR connected tok-mu (wherek=) the data input from the previous row of the storage block, in each of the operational blocks the input and output of the second trigger are connected respectively to the first input and output of the operational block, the input and output of the first trigger are connected respectively to the second input and output of the operational block, the third output of the operational block is connected to the output of the third trigger, the output of the first trigger is connected to the first input of the first AND element, the output of the second trigger is connected to the second input of the first AND element, the second input of the first OR element is connected to the output of the first AND element, the first and second inputs of which are connected respectively to the first and second outputs of the operational block, the clock input of which is connected to the clock inputs of the first, second and third triggers, the output of the first OR element is connected to the second input of the second AND element, the second input of the third AND element is connected to the third input of the operational block, and the output is connected to the second input of the second OR element, the output of which is connected to the input of the third trigger, the control input of the operational block is connected to the first input of the second AND element and the input of the inverter, the output of which is connected to the first input of the third AND element, and the input reset of the operating unit - with reset inputs of the first, second and third triggers, the output of the second AND element is connected to the first input of the second OR element, the output of the third trigger is connected to the first input of the first OR element,additionally introducedEach storage block contains the first group ofntriggers, the second group ofntriggers, the third group ofntriggers, as part of the coefficient block - the first group of (n- 1) two-stage registers, the second group of (n- 1) two-stage registers, a group ofn×ntriggers, a group ofn ×(n- 1) OR elements,andinformation entrancek-th element (wherek=) the first group of triggers is connected tok-th entrance (wherek=) as part of a group of input addresses of the storage block reading lines, and the outputk-th element (wherek=) the first group of triggers is connected to the second inputk-th element (wherek=) groups of elements I and Kk-th exit (wherek=) as part of the output group of storage block read line addresses, information inputk-th element (wherek=) the second group of triggers is connected tok-th entrance (wherek=) as part of a group of inputs of column addresses of reading a storage block, and the outputk-th element (wherek=) the second group of triggers is connected to the third inputk-th element (wherek=) groups of elements I and Kk-th exit (wherek=) as part of the group of output addresses of the storage block read columns, information inputk-th element (wherek=) the third group of triggers is connected to the outputk-th element (wherek=) groups of OR elements, and the outputk-th element (wherek=) the third group of triggers is connected tok-th exit (wherek=) as part of the group of data outputs of the current storage block, the reset input of the storage block is connected to the reset inputs of the first, second and third groups of triggers, the first element of the first group of two-stage registers is connected to the input of the column addresses of reading the matrix coefficient block, the outputk-th element (wherek=) the first group of two-stage registers is connected tok-th entrance (wherek=) as part of a group of read column address inputs(1,k+ 1)-th storage block (wherek=) and to the entrance( k+ 1)-th (wherek=) of the element of the first group of two-stage registers, the input of the first element of the second group of two-stage registers is connected to the input of the addresses of the reading lines of the matrix coefficient block, the outputk-th element (wherek=) the second group of two-stage registers is connected tok-th entrance (wherek=) as part of a group of inputs of read line addresses( k+ 1, 1)-th storage block (wherek=) and to the entrance( k+ 1)-th (wherek=) element of the second group of two-stage registers,k-th exit (wherek=) as part of a group of read line address outputs( m,p )-th storage block (wherem=,p=) connected tok-th input as part of a group of inputs of read line addresses( m,p+ 1)-th storage block, k-th exit (where) as part of a group of read column address outputs( m,p )-th storage block (wherem=,p=) connected tok-th input as part of a group of inputs of read column addresses( m+ 1, p )-th storage block, the reset input of the device matrix coefficient block is connected to the reset inputs of each ofn × nstorage blocks, to the first and second groups of (n- 1) two-stage registers and to a group ofn × ntriggers,k-th output digit in the data output group( n, 1)-th storage block is connected to the information inputk-th element (wherek=) groups of triggers, andk-th output digit in the data output group( n,p )-th storage block (wherep=) connected to the first input( k,p- 1)-th element (wherek=) groups of OR elements, output( k,p )-th element (wherek=,p=) groups of elements OR connected to the information input( k,p +1)-th element of the trigger group, output( k,p )-th element (wherek=,p=) trigger groups are connected to the second input( k,p+ 1)-th element of the OR group of elements, and the output( k,n )-th element (wherek=) groups of triggers connected tok-th output as part of the group of outputs of the matrix coefficient block.

Fig. 1 shows a functional diagram of the device; Fig. 2 - a diagram of the operational unit; Fig. 3 - a diagram of the matrix coefficient block; Fig. 4 - a diagram of the storage unit; Fig. 5 - the time costs for performing the multiplication operation by the proposed device and the prototype.

The device for matrix multiplication (Fig. 1) contains a matrix of n × n operational units 1, a first unit 2 of matrix coefficients, a second unit 3 of matrix coefficients, a shift register 4, a group of n two-stage registers 5, each operational unit 1 contains (Fig. 2) the first 6, second 7 and third 8 triggers, an AND element 9, an OR element 10, an AND element 11, an AND element 12, an OR element 13, an inverter 14, the first 2 and second 3 blocks of matrix coefficients have the same type of structure (Fig. 3), each of them includes n × n storage blocks 15, each of which (Fig. 4) contains a trigger 16, an AND element 17, a group of AND elements 18, a group of OR elements 19, a group of triggers 28, a group of triggers 29, a group of triggers 30, a synchronization input 20, an input 21 write row address, input 22 write column address, input 23 write data, group of inputs 24 read row addresses, group of inputs 25 read column addresses, group of inputs 26 data from the previous row, group of outputs 27 data for the next row, group of outputs 31 next row addresses, group of outputs 38 next column addresses, reset input, each of blocks 2 and 3 matrix coefficients also includes group of inputs 34 read row addresses, group of inputs 37 read column addresses, input 32 write row address, input 36 write column address, input 35 write data, clock input 33 write, reset input, group of two-stage registers 39, group of two-stage registers 40, group of triggers 41, group of OR elements 42, group of outputs 43, wherein the first input ( i , j ) of the -th operational block 1 (where , ) is connected to the first output of the ( i , j - 1 ) -th operational unit 1, the second input of the ( l , k ) -th operational unit 1 (where , ) is connected to the second output ( l - 1, k ) of the operating unit 1, -th output of the device output group is connected to the third output of the ( n , k ) -th operational block 1, the synchronization inputs of all operational blocks 1 are connected to the synchronization input of the matrix of operational blocks of the device, the third input of the ( l , k ) -th operational block 1 (where , ) is connected to the third output of the ( l - 1, k ) -th operational unit 1, the first input of the ( i , 1 ) -th operational unit 1 (where ) is connected to the i -th output as part of the group of outputs of the first block 2 of matrix coefficients, the second input ( 1, k ) of the operational block 1 (where ) is connected to the k -th output as part of the output group of the second block 3 of the matrix coefficients, the control inputs of the operational blocks 1 are connected to the control input of the device, and the reset inputs of the operational blocks 1 are connected to the reset input of the device, which is also connected to the reset inputs of each of the n two-stage registers 5, the information input of the m -th two-stage register 5 (where ) is connected to the output of the ( m - 1 ) -th two-stage register 5, the information input of the first two-stage register 5 is connected to the output of the shift register 4, the clock input of which is connected to the clock input of the device, which is also connected to the clock inputs of each of the n two-stage registers 5, the output of the k -th (where ) of the two-stage register 5 is connected to the k -th input as part of the group of read row addresses 34 of the second block 3 of matrix coefficients and to the k -th input as part of the group of read column addresses 37 of the first block 2 of matrix coefficients, the sync inputs 33 for writing the first 2 and second 3 blocks of matrix coefficients are connected to the sync input for writing the device, as part of each of the blocks of matrix coefficients, the sync input for writing the block of matrix coefficients 33 is connected to the sync input 20 of each of the n × n storage blocks 15, the k -th input (where ) as part of the group of inputs of the addresses of the reading lines of the 34th block of matrix coefficients is connected to the k -th (where ) to input 24 as part of the group of inputs of read line addresses ( 1, 1 ) of the storage block 15 and to the input of the k -th (where k = ) two-stage register 40, output k -th (where k = ) two-stage register 40 is connected to the k -th (where k = ) input 24 as part of the group of inputs of read line addresses ( 1, k + 1 ) of the storage block 15 (where k = ) and to the input ( k + 1 ) -th (where k = ) two-stage register 40, k -th input (where ) as part of the group of addresses of the columns of reading the 37th block of matrix coefficients is connected to the k -th (where ) to the input of the ( 1, 1 ) -th storage block 15 and to the input of the k -th (where k = ) two-stage register 39, output k -th (where k = ) two-stage register 39 is connected to the k -th (where k = ) input 25 as part of the group of inputs of read column addresses of the ( k + 1, 1 ) -th storage block 15 (where k = ) and to the input ( k + 1 ) -th (where k = ) two-stage register 39, k -th output (where ) as part of the group of outputs 31 of the addresses of the read lines ( m , p ) of the storage block 15 (where m = , p = ) is connected to the k -th input as part of the input group of 24 read line addresses ( m , p + 1 ) of the storage block 15, the k -th output (where ) as part of the output group 38 addresses of read columns ( m , p ) of the storage block 15 (where m = , p = ) is connected to the k -th input in the group of inputs 25 of the read column addresses of the ( m + 1 , p ) -th storage block 15, the reset input of the device matrix coefficient block is connected to the reset inputs of each of the n × n storage blocks 15, to groups of ( n - 1) two-stage registers 39 and 40 and to a group of n × n triggers 41, the k -th input (where ) as part of the input group 26 of data from the previous line ( m , p ) of the storage block 15 (where , ) is connected to the k -th data output 27 as part of the data output group for the next row ( m - 1, p ) of the storage block 15, the k -th input (where ) as part of the group of inputs 32 of the addresses of the recording lines of the matrix coefficient block is connected to the input 21 of the addresses of the recording lines -th storage block 15 (where ), k -th input (where ) as part of the group of inputs 36 of the addresses of the columns of the recording block of the matrix coefficients is connected to the input 22 of the addresses of the columns of the recording ( k , i ) -th storage block 15 (where ), input 35 of the recording data of the matrix coefficient block is connected to input 23 of the recording data of each of the n × n storage blocks 15, the k -th output digit in the group of outputs 27 of the data ( n , 1 ) -th storage block 15 is connected to the information input of the k -th element (where k = ) of the trigger group 41, and the k -th output digit in the output group 27 of the data ( n , p ) of the storage block 15 (where p = ) is connected to the first input of the ( k, p - 1 ) -th element (where k = ) groups of OR elements 42, the output of the ( k, p ) -th element (where k = , p = ) of the OR group of elements 42 is connected to the information input of the ( k, p + 1 ) -th element of the trigger group 41, the output of the ( k, p ) -th element (where k = , p = ) of the group of triggers 41 is connected to the second input of the ( k, p + 1 ) -th element of the group of OR elements 42, and the output of the ( k, n ) -th element (where k = ) of the group of triggers 41 is connected to the k -th output 43 as part of the group of outputs of the matrix coefficient block, as part of each of the storage blocks 15, the information input of trigger 16 is connected to the input 23 of the recording data of the storage block, and the synchronization input of trigger 16 is connected to the output of AND element 17, the first input of which is connected to the input 22 of the recording column address of storage block 15, the second input is connected to the input 21 of the recording row address of storage block 15, and the third input is connected to the synchronization input 20 of storage block 15, the output of trigger 16 is connected to the first inputs of each of the n elements of the group of AND elements 18, the output of the k -th element (where ) of the AND element group 18 is connected to the first input of the k -th element of the OR element group 19, the second input of the k -th element of the OR element group 19 is connected to the k -th input 26 of the data from the previous line of the storage unit 15, and the output of the k -th element of the OR element group 19 is connected to the information input of the k -th element of the trigger group 30, the output of the k -th trigger 30 is connected to the k -th output 27 of the data for the next line of the storage unit 15, the second input of the k -th element of the AND element group 18 is connected to the output of the k -th trigger of the trigger group 28, and the third input of the k -th element of the AND element group 18 is connected to the output of the k -th trigger of the trigger group 29, in each of the operational units 1 the input and output of the second trigger 7 are connected respectively to the first input and output of the operational unit 1, the input and output of the first trigger 6 are connected respectively to the second input and output of the operational unit 1, the third output operating unit 1 is connected to the output of the third trigger 8, the output of the first trigger 6 is connected to the first input of the first AND element 9, the output of the second trigger 7 is connected to the second input of the first AND element 9, the second input of the OR element 10 is connected to the output of the AND element 9, the first and second inputs of which are connected respectively to the first and second outputs of operating unit 1, the clock input of which is connected to the clock inputs of the first 6, second 7 and third 8 triggers, the output of the OR element 10 is connected to the second input of the AND element 11, the second input of the AND element 12 is connected to the third input of operating unit 1, and the output is connected to the second input of the OR element 13, the output of which is connected to the input of the trigger 8, the control input of operating unit 1 is connected to the first input of the AND element 11 and the input of the inverter 14, the output of which is connected to the first input of the AND element 12, and the reset input of operating unit 1 is connected to the reset inputs of the first 6, second 7 and third 8 triggers, the output of AND element 11 is connected to the first input of OR element 12, the output of trigger 8 is connected to the first input of OR element 10.

Operational units 1, combined into a systolic matrix structure, are used to perform multiplication of matrix elements in a parallel pipeline and store the result. The first 2 and second 3 matrix coefficient blocks are used to store the coefficient values. And ,the first and second matrices and selection of the required groups fromncoefficients per clock cycle in each of the blocks in accordance with the operating logic of the matrix of operational blocks 1. Shift register 4 ensures the formation of a sequence of values,, …,,, …,, used in the operation of register group 5. Group 5 of two-stage registers is intended for storing the addresses of a group ofnrows of the first block 2 matrix coefficients and groups ofncolumns of the second block 3 of matrix coefficients; these addresses are necessary for reading the groups of coefficients of the matrices being multiplied in accordance with the logic of the matrix of operational blocks 1. Triggers 6 and 7 are intended for storing the coefficients of the matrices being multiplied during the operation of operational blocks 1. Trigger 8 is used to store intermediate values of the disjunctions of the conjunctions of the coefficients of the matrices being multiplied during the operation of the device, after (3n- 2) steps of the device operation, these triggers contain the values of the coefficients of the resulting matrixCThe AND element 9 is used for logical multiplication of a pair of coefficients And matrices. Element OR 10 is designed to calculate the disjunctions of the conjunctions of the coefficients of the matrices being multiplied. Elements AND 11 and OR 13 ensure that the value of the disjunctions of the conjunctions of the coefficients of the matrices being multiplied is fed to the input of trigger 8 during the operation stage, elements inverter 14 and AND 12 ensure the advancement of the multiplication result (the coefficients of the resulting matrixC) between the triggers of 8 operational units 1 in parallel-pipeline mode at the stage of outputting the result. Storage units 15, combined into a matrixn×n(Fig. 3), form the first 2 and second 3 blocks of coefficients of the matrices being multipliedA And BTriggers 16 are used to store the initial values of the coefficients of the binary matrices being multiplied. Elements AND 17 control the passage of the clock signal 20 to the clock inputs of triggers 16 in accordance with the selected row values.iand columnjas part of matrix coefficient blocks. Blocks of I-elements 18₁- 18 _n control the passage of OR elements to the inputs of the corresponding blocks 19₁- 19 _n groups fromnvalues from the outputs of triggers 16, and the selected values are determined by the coordinates of the desired rows and columns at the inputs 24₁- 24 _n and 25₁- 25 _n in accordance with the logic of the matrix of operating blocks 1. Elements OR 19₁- 19 _n , trigger group 30₁- 30 _n as part of storage blocks 15 in conjunction with a group of triggers 41₁₁- 41 _nn and a group of elements OR 42₁₁- 42 _nn ensure that 43 outputs are obtained₁- 43 _n block of matrix coefficients of the next group of matrix coefficients in accordance with the logic of the operation of the matrix of operational blocks 1 in the pipeline mode, andnpairs of row and column addresses of the sought coefficients are determined by the values at the inputs 24₁- 24 _n and 25₁- 25 _n storage blocks 15. Input 20 synchronization is used when writing the initial values of matrix coefficients into triggers 16. Inputs 21 and 22 row addressesiand columnjrecords provide choiceij-th storage block 15 as part of the matrix coefficient block by controlling the passage of the synchronization signal at the synchronization input 20 through the AND element 17 when recording the required coefficient from the input 23 into the trigger 16 of the selectedij-th storage block 15. Input 23 of the recording data is used for receiving the coefficients of the matrices being multiplied by storage block 15 for the purpose of writing them into triggers 16. Input group 24₁- 24 _n read line addresses and input group 25₁- 25 _n read column addresses in conjunction with a group of triggers 28₁- 28 _n and 29₁- 29 _n are respectively used to control the timely passage of group values fromnmatrix coefficients from 16 triggers, 15 storage blocks to 43 outputs₁- 43 _n matrix coefficient block. Input group 26₁- 26 _n data from the previous line in conjunction with output group 27₁- 27 _n data for the next row is used to form the required values of the disjunction of the group of selected values of matrix coefficients by the columns of storage blocks 15, obtained at the outputs 27₁- 27 _n 15 storage blocksn-th row of the matrix coefficient block. Input 34 of the read row addresses in conjunction with input 37 of the read column addresses are used to obtain the matrix coefficient block of the row and column addresses of the required elements for the purpose of selecting them from triggers 16 and outputting them to outputs 43₁- 43 _n . Input 32 of the record row address in combination with input 36 of the record column address are used to obtain the coefficients of the value matrix by the blocki-th line andj-th column for the purpose of subsequent recording in the selectedij-th operational block of the coefficient value supplied to input 35 of the recording data. Input 33 of the recording synchronization is used to receive the strobe signal for recording data from input 35 of the matrix coefficient block to the selectedij-th storage block 15. Trigger group 41₁₁- 41 _nn and elements OR 42₁₁- 42 _nn used for timely receipt of data and formation at the outputs 43₁- 43 _n block of coefficients of the matrix of disjunctions of values from outputs 27₁- 27 _n storage blocks 15 block of matrix coefficients for the purpose of forming a group ofnthe required matrix coefficients in accordance with their addresses at inputs 34 and 37 and the operating logic of the matrix of operational blocks 1. At outputs 43₁- 43 _n a block of matrix coefficients is used to form a group ofnmatrix coefficients for the purpose of their subsequent transfer to the matrix of operational blocks 1.

The device works as follows. At the stage of loading the initial data, the values , elements of the first matrix are fed one after another to input 35 of the first block 2 of matrix coefficients by an external device, the addresses of row i and column j in unitary code are fed to inputs 32 and 36 of the first block 2 of matrix coefficients, respectively, the recording of the next element is performed by applying a sync pulse to the sync input 33 of the recording of the first block 2 of matrix coefficients.

The loading of initial values is performed in a similar manner to that discussed above. , elements of the second matrix by feeding their values to input 35 of the second block of 3 matrix coefficients by an external device, feeding addresses i and j in unitary code to inputs 32 and 36 of the second block of 3 matrix coefficients, respectively, and a sync pulse to the sync input 33 of the recording of the second block of 3 matrix coefficients. Loading the elements of the first and second matrices can be combined in time.

The value of the coefficient from input 35 of the matrix coefficient block is fed to inputs 23 of storage blocks 15 and then to the information input of trigger 16 in each of the storage blocks. The values of the row and column addresses from inputs 32 and 36 are fed, respectively, to inputs 21 and 22 of storage blocks 15, where the i -th digit from input 32 is fed to inputs 21 of storage blocks 15 of the i -th row of the matrix coefficient block, and the j -th digit from input 36 is fed to inputs 22 of storage blocks 15 of the j -th column of the matrix coefficient block, . The synchronization pulse from the synchronization input 33 of the matrix coefficient block entry goes to the inputs of the 20 operational blocks and then to the input of the AND element 17. The unit values from inputs 21 and 22, corresponding to the selected operational block , are fed to the input of AND element 17 of the operational blocks and open it to allow the clock signal to pass to the clock input of flip-flop 16, ensuring the recording of the next coefficient. In all other storage blocks 15, at least one of the inputs 21 or 22 has a zero value. AND elements 17 are closed to allow the clock signal to pass, and no value is written to flip-flop 16.

During the initialization stage, a reset signal is applied to the reset inputs of two-stage register group 5, triggers 6, 7, 8, trigger groups 28, 29 and 30, two-stage register groups 39 ₁ - 39 _{n -1} , 40 ₁ - 40 _{n -1} , trigger groups 41 ₁₁ - 41 _nn , which ensures that they are set to zero. A value of one is applied to data input 23.

The value 00…01 ₂ is written to the shift register 4. To the inputs the addresses of the reading lines of the first block 2 of the matrix coefficients are respectively supplied with the values 00…01 ₂ , 00…010 ₂ , …, 100…0 ₂ , which subsequently ensures the output of elements , , …, at the corresponding output first block of 2 matrix coefficients, .

To the entrances the addresses of the columns of the reading of the second block 3 of the matrix coefficients are respectively supplied with the values 00…01 ₂ , 00…010 ₂ , …, 100…0 ₂ , which subsequently ensures the output of elements , , …, at the corresponding output the second block of 3 matrix coefficients, . Unit values are fed to the control inputs of all operational blocks 1 in the n × n matrix. Zero values are fed to inputs 26 ₁ - 26 _n of storage blocks 15 ₁ - 15 _{1 n} .

At the operating stage, a recording signal is sent to the first stage at the sync inputs of the two-stage register group 5, which ensures that values are recorded according to the following scheme: , , . After this, in the next clock cycle, a write signal is sent to the second stage of register 5, which ensures that information from the first stage is written to the second, and a signal is sent to the clock input of shift register 4, shifting the register contents toward the most significant bits. In the first step of the operating phase, register 4 receives the value , and registers 5 - respectively, the values 00…01 ₂ , 00…0 ₂ , …, .

Values from the outputs of register group 5₁- 5 _n are sent to the inputs accordinglyblock 2 of matrix coefficients 1, from where to input 25 of storage block 15₁₁. In parallel with this, the values from the outputs of register group 5₁- 5 _n are sent to the inputs accordinglyblock 3 coefficients of matrix 2, from where to the input 24 of storage block 15₁₁.k-th digit of input 37 goes tok-th digit of the input is 25, and k-th digit of input 34 goes tok-th digit of input 24. The same values from input 37 of blocks 2 and 3 of matrix coefficients are sent to the first stage of register 39₁, and the values from inputs 34 go to the first stage of register 40₁, where they are recorded upon arrival of the synchronization signal. Also, upon arrival of the synchronization signal, the values from inputs 24₁- 24 _n are fixed in triggers 28₁- 28 _n , and from the inputs 25₁- 25 _n in triggers 29₁- 29 _n .

The values from the outputs of trigger group 28, the values from the outputs of trigger group 29 are sent to inputs 2 and 3 of AND elements 18 ₁ - 18 _n , ensuring that the signal from the output of triggers 16 passes to the inputs of elements 19 ₁ - 19 _n only in the case of the presence of two single values k = at the 2nd and 3rd inputs of the AND element 18 _k , which ensures that the value of trigger 16 is read only for the selected row and column pair.

The read values are passed through the OR gates , after which they are sent to the information inputs of the triggers , where they are subsequently recorded in the first stage upon arrival of the synchronization signal.

In the first cycle of operation, the required values of the coefficient a ₁₁ of the matrix are formed at the output 27 of the storage block 15 _11. Then, upon receipt of the synchronization signal, information is written from the first stage of registers 39 ₁ - 39 _{n -1} and 40 ₁ - 40 _{n -1} and the group of triggers 28 ₁ - 28 _n , 29 ₁ - 29 _n and 30 ₁ - 30 _n to the second stages, respectively.

So, at the first step, at the stage of working on the inputs the first block of 2 matrix coefficients contains values , , …, (1, 2, …, n in decimal form taking into account the unitary coding used), at the inputs first block 2 matrix coefficients - values , , …, (1, 0, …, 0 in decimal form).

At the next cycle of operation, the values are written from the second stages of registers 39 _{k -1} to the first stage of registers 39 _k , and from the second stages of registers 40 _{k -1} to the first stage of registers 40 _k , where k = . In parallel with this, the values from the second stages of the trigger group 28 ₁ - 28 _n of the storage blocks 15 _{i , j -1} are written to the first stage of the group of triggers 28 ₁ - 28 _n storage blocks 15 _ij , and the values from the second stages of the group of triggers 29 ₁ - 29 _n storage blocks 15 _{i -1, j} are written to the first stage of the group of triggers 29 ₁ - 29 _n storage blocks 15 _ij .

On the second cycle of the device operation, the required information is read at the outputs 38 of storage blocks 15 ₂₁ and 15 _12. On the third cycle of the device operation, the required information is read in a similar manner at the outputs 38 of storage blocks 15 ₃₁ , 15 ₂₂ , 15 ₁₃ and so on. On the n -th cycle of the device operation, the desired value of the matrix coefficient a _ij is formed at the output 27 of storage block 15 _{n 1} , which is subsequently recorded in the first stages of triggers 41 ₁₁ - 41 _{n 1} . Then, the values are written from the first to the second stages of the group of triggers 41 ₁₁ - 41 _{n n} . On the ( n + 1) cycle, the value of the matrix coefficient a _ij is similarly formed at the output 27 of storage block 15 _{n 2 .} The specified pair of values is fed to the group of OR elements 42 ₁₁ - 42 _{n 1} from the outputs of which it is fed to the first stage of the group of triggers 41 ₁₂ - 41 _{n 2} , where it is recorded upon arrival of the clock signal. Over the next ( n - 2) clock cycles, the data passes through the groups of OR elements 42 ₁₃ - 42 _{n 3} , …, 41 _{1 n} - 42 _{n n} and the groups of triggers 41 ₁₃ - 41 _{n 3} , …, 41 _{1 n} - 41 _{n n} and ends up at the outputs 43 ₁ - 43 _n of the matrix coefficient block.

Further, in each new clock cycle, the required values of the matrix coefficients are generated at outputs 43 ₁ - 43 _n in accordance with the addresses that were previously supplied to inputs 34 and 37 of the matrix coefficient block.

The generated values from the outputs 43 of the first block 2 of the matrix coefficients are fed to the inputs of the corresponding triggers 7 of the first column of the matrix of the operational blocks 1, and from the outputs 43 of the second block 3 of the matrix coefficients - to the inputs of the corresponding triggers 6 of the first row of the matrix of the operational blocks 1, where they are recorded upon arrival of the corresponding synchronization signal; the values from the first stage of the triggers 8 of the operational blocks 1 are written to the second stage.

Each operating unit 1 implements the functions \/ , where t is the device's operating step number. The coefficient values of the resulting matrix C are calculated using the following recurrence formulas:

,

\/ ,

.

From the outputs of triggers 6 and 7 the values And are fed to the inputs of the AND element 9, at the output of which their conjunction is formed , arriving at the second input of the OR element 10. The value from trigger 8 is fed to the first input of the OR element 10, from the output of which the formed value is fed to the second input of the AND element 11. The AND element 12 is closed to the passage of the signal from the third input of the operational unit due to the presence of a zero signal at the first input of the AND element 12, coming from the output of inverter 14. The value from the second input of the AND element 11 passes to its output due to the fact that the first input of the AND element 11 contains a unity value of the control signal from the control input of the operational unit. The value from the output of the AND element 11 passes through the OR element 13 to the input of the first stage of trigger 8, where it is fixed upon arrival of the corresponding synchronization signal, which ensures the formation of the desired values in the triggers 8 of the operational units 1.

Next, a write signal is sent to the first stage of the two-stage register group 5, and the device's operation is repeated as described above. Thus, in the second step, register 4 receives the value , and registers 5 are the values, respectively , , , …, At the outputs 43 of the first block 2 of the matrix coefficients, values are formed , which are fed to the first column of operational elements 1 and are recorded in the corresponding triggers 7; at the outputs 43 of the second block 3 of the matrix coefficients, values are formed which arrive at the first line of operational elements 1 and are recorded in the corresponding triggers 8.

At the stage of obtaining the multiplication result, the AND element 11 is closed to the signal from the output of the flip-flop 8, due to the presence of a zero signal at the first input of the AND element 11, coming from the control input of the operational unit. The value from the second input of the AND element 12 passes to its output, due to the fact that the first input of the AND element 12 contains a unity value of the control signal coming from the output of the inverter 14. The value from the output of the AND element 12 passes through the OR element 13 to the input of the first stage of the flip-flop 8, where it is fixed upon arrival of the corresponding clock signal, which ensures the formation of the desired values in the flip-flops 8 of the operational units 1. After this, the output of clock pulses is performed, alternately ensuring writing first to the first, and then to the second stage of the flip-flops 8, which in n steps ensures the row-by-row output of the resulting elements of the matrix C from the bottom row of the matrix of operational elements 1 in a parallel-pipeline mode.

Let us evaluate the advantages of the proposed device in terms of reducing the time costs for multiplying binary matrices.

The operating time of the device is defined as

t _general = t _in + t _slave ,

where t _in is the device initialization time; t _rab is the data processing time.

When the device is initialized , the values of the group of two-stage registers 5, triggers 6, 7, 8, groups of triggers 28, 29, 30, groups of two-stage registers 39, 40, group of triggers 41 are reset, which requires time t _in = 2 t ₀ .

The device's operating stage consists of (2 n - 1) iterations. At each iteration, the operating unit operates as a group of linear synchronous pipelines under the control of a common clock signal. The pipeline clock t _k is determined by the maximum of the data read time from the dedicated memory and the operating time of operating unit 1:

t _k =max (t _{k Thu} , t _{k ABOUT} ).

At the start of operation, the line address from one of the inputs 34 of the read line addresses of the matrix coefficient block is written into the first stage of the two-stage register 40 ₁ and from input 24 into the first stage of the group of triggers 28 ₁ - 28 _n of the storage block 15 ₁₁ , which takes time , in parallel with this, the column address from one of the inputs 37 of the address of the rows for reading the matrix coefficient block is written into the first stage of the two-stage register 39 ₁ from input 25 into the first stage of the group of triggers 29 ₁ - 29 _n of the storage block 15 ₁₁ , then the data is rewritten from the first to the second stages of the group of triggers 30 ₁ - 30 _n , which takes time .

Next, information is recorded from the second stages of the two-stage registers 40 _{i -1}in the first stages of registers 40 _i And from the second stages of two-stage registers 39 _{i -1}in the first stages of registers 39 _i , Wherei = , what time is spent on 2t ₀, and from the second stages of triggers 28₁-28 _n 15 storage blocks _{i j} in the first stages of triggers 28₁- 28 _n 15 storage blocks _{i , j + 1}, Where i = , j = , and from the second stages of triggers 29₁- 29 _n 15 storage blocks _{i j} in the first stages of triggers 29₁- 29 _n 15 storage blocks _{i+ 1, j} , Where i = , j = , what time is spent on 2t ₀ .

Next, the signals from the outputs of the second stages of trigger groups 28 ₁ - 28 _n and 29 ₁ - 29 _n open the three-input AND elements 18 ₁ - 18 _n (the required time is 2 t ₀ ) to allow the signal from the output of trigger 16 to pass to the inputs of OR elements 19 (the required time is ) and then recorded in the first stage of the trigger group 30, which takes time .

In parallel with the recording of information into the second stages of the two-stage registers 39, 40 and triggers 28, 29, the signal passes through the OR elements 42 (the required time is ), then recording information in the first stage of triggers 41 (the required time is 2 t ₀ ) and then recording information from the first stage in the second stage of triggers 41 (the required time is 2 t ₀ ).

The time to read a portion of data from memory in pipeline mode is

t _{k Thu .} = max (,,,,) + max (max(,,,) ++ ++,++) = 2t ₀+ max (7t ₀, 5t ₀) = 9t ₀.

During the operation of the cell of the operating unit of the device for processing binary matrices based on systolic structures, the signal passes through a two-stage trigger 7 in time , in parallel with this, the signal similarly passes through a two-stage trigger 6. Initially, the signals are recorded And occurs in the first stage of triggers 6 and 7, respectively, during the time . Next, the signals move to the second stage of these triggers, in a time equal to .

The longest path that occurs when a signal passes through the logic elements according to the circuit of the operational block 1 is represented by the elements: triggers 6, 7, 8, AND elements 9, 11, OR elements 10, 13, which requires time

t _{k ABOUT} = max (,) +++++= 10t ₀,

recording into the second stage of trigger 8 is carried out in parallel with recording into the first stages of triggers 6 and 7.

The pipeline cycle can be defined as

t _k = max (9 t ₀ , 10 t ₀ ) = 10 t ₀ .

The data processing time t _work = t _k × (2 n - 1) due to the fact that with the selected matrix multiplication algorithm, the coefficients are supplied in (2 n - 1) iterations, and the total operating time of the device is determined as

t _total = 2 t ₀ + 10 t ₀ × (2 n - 1) = 2 t ₀ + 20 t ₀ n - 10 t ₀ = (20 n - 8) t ₀ .

Let's estimate the time costs of the prototype for multiplying binary matrices.

The prototype running time is defined as

t _{general . prot.} = t _{in . prot.} + t _{rab . prot .} ,

where t _{in . prot.} is the initialization time; t _{rab . prot.} is the data processing time.

The initialization time and operating time of the operating units are the same for the proposed device and the prototype:

t _{in. prot.} = t _in. ;

t _{k ABOUT Archpriest} = t _{k ABOUT} .

The prototype's operating stage consists of (2 n - 1) iterations. At each iteration, the operating unit operates as a group of linear synchronous pipelines controlled by a common clock signal. The pipeline clock is determined by the maximum of the data read time from specialized memory and the operating time of operating unit 1:

t _{to the arch.} =max (t _{to thu prot.} ,t _{k OB prot.} ).

When reading data, the signal from the output of trigger 16 passes through one of the three-input AND elements 18, which takes 2 t ₀ (all AND elements 18 in the storage blocks operate in parallel), through one of the two-input OR elements 19, which takes t ₀ , and through the n -input OR element 34, which, using a pyramidal circuit of two-input elements, takes time , Where - rounding up operation. Thus, the total time to read the data is

t _{Thu . prot.} = 2t ₀+t ₀ n+ .

The pipeline cycle can be defined as

t _{k Archpriest} = max (10t ₀, 2t ₀+t ₀ n+ ).

For practically important cases ( n > 4)

t _{k Archpriest} = 2t ₀+t ₀ n+ ,

That is, the prototype's operating time is limited by the rate at which input data arrives from the specialized multiport memory. The data processing time twork _{. prot. = tkprot} . _× ( 2 n - 1) due to the fact that, with the chosen matrix multiplication algorithm, the coefficients are supplied in (2 n - 1) iterations.

t _{general . prot.} = 2t ₀ + (2t ₀ + t ₀ n+)×(2n- 1)=2t ₀+ 4t ₀ n+ 2t ₀ n ²+ 2n - 2t ₀-t ₀ n-= 2t ₀ n ²+ 3t ₀ n+ 2n -= (2n ²+ 3n+ 2n -)t ₀.

The gain in processing time is defined as

η = .

The time cost values for the proposed device and the prototype, calculated for different n , t ₀ = 1 ns, are shown in Fig. 5.

From the presented data it follows that the proposed device allows to reduce the processing time by up to 206.3 times when performing the multiplication of square binary matrices of size n ≤ 2048 .

Sources of information

1. Russian Federation Patent for Utility Model No. 193927. Device for Binary Matrix Multiplication. Claimed June 26, 2019, published November 21, 2019, Bulletin No. 33.

2. Russian Federation Patent for Utility Model No. 157948. Matrix Multiplication Device. Class G06F 17/16, filed July 8, 2015, published December 20, 2015, Bulletin No. 35.

Claims (1)

A device for multiplying binary matrices, comprising a matrix of n×n operational units, where n is the size of the square matrices being multiplied, first and second matrix coefficient units, a shift register, a group of n two-stage registers, each operational unit comprising a first, second, third trigger, a first, second, third AND elements, a first, second OR elements, an inverter, each of the matrix coefficient units contains n×n storage units, each of the storage units contains an AND element, a trigger, a group of n AND elements, a group of n OR elements, and the first input of the (i, j)th operational unit, where connected to the first output of the (i, j-1)-th operational unit, the second input -th operating block, where connected to the second output -th operational unit, the k-th output of the device output group is connected to the third output of the (n, k)-th operational unit, the synchronization inputs of all operational units are connected to the synchronization input of the matrix of operational units of the device, the third input -th operating block, where connected to the third output -th operating unit, the first input of the (i, 1)-th operating unit, where connected to the i-th output as part of the group of outputs of the first block of matrix coefficients, the second input of the (1, k)-th operational block, where connected to the k-th output as part of the output group of the second block of matrix coefficients, the control inputs of the operational blocks are connected to the control input of the device, and the reset inputs of the operational blocks are connected to the reset input of the device, which is also connected to the reset inputs of each of the n two-stage registers, the information input of the m-th two-stage register, where connected to the output of the (m-1)-th two-stage register, the information input of the first two-stage register is connected to the output of the shift register, the clock input of which is connected to the clock input of the device, which is also connected to the clock inputs of each of the n two-stage registers, the output of the k-th, where the two-stage register is connected to the k-th input as part of the group of read row addresses of the second block of matrix coefficients and the k-th input as part of the group of read column addresses of the first block of matrix coefficients, the sync inputs of the first and second blocks of matrix coefficients are connected to the sync input of the device write, as part of each of the blocks of matrix coefficients, the sync input of the block of matrix coefficients is connected to the sync inputs of each of the n×n storage blocks, the k-th input, where as part of the group of read line addresses of the matrix coefficient block, it is connected to the input of the read line addresses of the (1, 1)-th storage block, the k-th input, where as part of the group of read column addresses of the matrix coefficient block, it is connected to the input of the read column addresses of the (1, 1)-th storage block, the k-th input, where as part of a group of data inputs from the previous row of the (m, p)-th storage block, where connected to the k-th data output for the next row of the (m-1, p)-th storage block, the k-th input, where as part of the group of addresses of recording rows of the matrix coefficient block, it is connected to the input of the addresses of recording rows of the (i, k)-th storage block, where k-th input, where as part of the group of column addresses of the recording block of matrix coefficients, it is connected to the input of the column addresses of the recording block of the (k, i)-th storage block, where the write data input of the matrix coefficient block is connected to the write data input of each of the n×n storage blocks, within each of the storage blocks the first input of the AND element is connected to the input of the column address of the write storage block, the second input is connected to the input of the row address of the write storage block, and the third input is connected to the synchronization input of the storage block, the output of the AND element is connected to the synchronization input of the trigger, the information input of the trigger is connected to the write data input of the storage block, the output of the trigger is connected to the first inputs of each of the n elements of the group of AND elements, the output of the k-th element, where group of elements AND is connected to the first input of the k-th, where element of the OR group of elements, the second input of the k-th, where element of the group of elements OR is connected to the k-th, where the data input from the previous row of the storage block, in each of the operational blocks the input and output of the second trigger are connected respectively to the first input and output of the operational block, the input and output of the first trigger are connected respectively to the second input and output of the operational block, the third output of the operational block is connected to the output of the third trigger, the output of the first trigger is connected to the first input of the first AND element, the output of the second trigger is connected to the second input of the first AND element, the second input of the first OR element is connected to the output of the first AND element, the first and second inputs of which are connected respectively to the first and second outputs of the operational block, the clock input of which is connected to the clock inputs of the first, second and third triggers, the output of the first OR element is connected to the second input of the second AND element, the second input of the third AND element is connected to the third input of the operational block, and the output is connected to the second input of the second OR element, the output of which is connected to the input of the third trigger, the control input of the operational block is connected to the first input of the second AND element and the input of the inverter, the output of which is connected to the first input of the third AND element, and the reset input operational block - with reset inputs of the first, second and third triggers, the output of the second AND element is connected to the first input of the second OR element, the output of the third trigger is connected to the first input of the first OR element, additionally introduced in each storage block are the first group of n triggers, the second group of n triggers, the third group of n triggers, in the coefficient block - the first group of (n-1) two-stage registers, the second group of (n-1) two-stage registers, a group of n×n triggers, a group of n×(n-1) OR elements, and the information input of the k-th element, where the first group of triggers is connected to the k-th input, where as part of the input group of addresses of the reading lines of the storage block, and the output of the k-th element, where the first group of triggers is connected to the second input of the k-th element, where groups of elements and to the k-th output, where as part of the group of output addresses of the storage block read lines, the information input of the k-th element, where the second group of triggers is connected to the k-th input, where as part of the input group of the storage block read column addresses, and the output of the k-th element, where the second group of triggers is connected to the third input of the k-th element, where groups of elements and to the k-th output, where as part of the group of output addresses of the storage block read columns, the information input of the k-th element, where the third group of triggers is connected to the output of the k-th element, where groups of OR elements, and the output of the k-th element, where the third group of triggers is connected to the k-th output, where as part of the group of data outputs of the current storage block, the reset input of the storage block is connected to the reset inputs of the first, second and third groups of triggers, the first element of the first group of two-stage registers is connected to the input of the read column addresses of the matrix coefficient block, the output of the k-th element, where the first group of two-stage registers is connected to the k-th input, where as part of the input group of read column addresses of the (1, k+1)-th storage block, where and to the input of the (k+1)th, where element of the first group of two-stage registers, the input of the first element of the second group of two-stage registers is connected to the input of the addresses of the reading lines of the matrix coefficient block, the output of the k-th element, where the second group of two-stage registers is connected to the k-th input, where as part of the input group of read line addresses of the (k+1, 1)-th storage block, where and to the input of the (k+1)th, where element of the second group of two-stage registers, k-th output, where as part of the output group of read line addresses of the (m, p)-th storage block, where connected to the k-th input as part of the group of inputs of the read line addresses of the (m, p+1)-th storage block, the k-th output, where as part of the output group of read column addresses of the (m, p)-th storage block, where is connected to the k-th input in the group of inputs of the read column addresses of the (m+1, p)-th storage block, the reset input of the device matrix coefficient block is connected to the reset inputs of each of the n×n storage blocks, to the first and second group of (n-1) two-stage registers and to a group of n×n triggers, the k-th output digit in the group of data outputs of the (n, 1)-th storage block is connected to the information input of the k-th element, where groups of triggers, and the k-th output digit is part of the data output group of the (n, p)-th storage block, where connected to the first input of the (k, p-1)-th element, where groups of OR elements, the output of the (k, p)-th element, where group of OR elements is connected to the information input of the (k, p+1)-th element of the trigger group, the output of the (k, p)-th element, where group of triggers is connected to the second input of the (k, p+1)-th element of the group of OR elements, and the output of the (k, n)-th element, where The group of triggers is connected to the k-th output as part of the group of outputs of the matrix coefficient block.