CN103389967B - The device and method of a kind of matrix transposition based on SRAM - Google Patents

Abstract

The invention discloses a device and method for matrix transposition based on SRAM. The device comprises an address decoding module, a read-write bus, a diagonal read control module and n matrix transpose memory bodies. Each matrix transpose memory body is connected by n rows and n columns of matrix memory modules. The ones located on the diagonal from the upper left to the lower right are 14-tube SRAM memory modules, and the ones outside the diagonal are 12-tube SRAM memory modules. . The 14-tube SRAM memory module accesses the elements on the diagonal in the matrix, and the 12-tube SRAM memory module accesses the elements outside the diagonal in the matrix; the method is based on the type of the input matrix and the different access modes. The transpose is done by word, row, column, or diagonal access. The invention has the advantages of simple realization method, simple and compact structure, low cost, fast transposition speed, high efficiency, flexibility and multiple functions.

Description

A device and method for matrix transposition based on SRAM

technical field

The present invention relates to the field of matrix transposition data processing, in particular to a device and method for matrix transposition based on SRAM.

Background technique

Matrix Transposing is widely used in scientific computing, such as matrix decomposition, linear algebra solution, 3G communication algorithm, image video algorithm, radar, underwater acoustic algorithm and other scientific and engineering calculations. For an n×n order (n>1) source matrix A=[a _ij ], the transposition is formed by exchanging each lower triangular element a _ij (i>j) along the main diagonal with its symmetric element a _ji Matrix A ^T [b _ij ]. Formula (1) gives the corresponding relationship between the transposed matrix A ^T [b _ij ] and each matrix element of the source matrix A[a _ij ]:

b _ji =a _ij (i=0,1,…,n-1;j=0,1,…,n-1)(1)

The application of fast and efficient matrix transposition methods and devices will greatly improve the performance and efficiency of various systems. In the past, various matrix transposition methods based on software and hardware have been invented and widely used.

In terms of software methods, the simplest method is to use the main diagonal as the axis to exchange a pair of data at a time. For an n×n order matrix, the time overhead is O(n(n-1)/2), and the efficiency is low. . Eklundh proposed a fast matrix transposition algorithm, which is completely independent of the hardware structure and is based on the divide-and-conquer strategy. The time overhead is O(nlogn). The disadvantage is that for an n×n order matrix, n must It is an integral power of 2, and the real-time performance is poor. PRIM proposes an algorithm that overcomes the limitation that n must be an integral power of 2, and its time overhead is the same as that of Eklundh algorithm. For vector processors, it was proposed to use the Eklundh algorithm to perform matrix transposition operations on SIMD. This method needs to be supported by additional hardware instructions in order to better improve its efficiency. The time overhead is O(logn). In addition, Intel Corporation, MIPS Corporation, and Motorola Corporation each proposed their own matrix transposition methods, although they are not exactly the same, but their time overhead is the same.

In terms of hardware methods, various design schemes have been implemented, such as SystolicArray module, UniversalArrayArchitecture and MemorySkewing.

(1) SystolicArray method

The matrix transposition operation of the SystolicArray method is simple, the data is loaded by columns or rows, and read from the top to realize the matrix transposition operation. For an n×n matrix, it takes 3n-1 steps to complete the matrix transpose. However, using registers and combined switches to implement, the hardware cost is relatively high.

(2) UniversalArrayArchitecture method

The UniversalArrayArchitecture method is simpler and more efficient than the SystolicArray method. Data can be written in a row (column) at a time in the form of rows (columns). ), read all the data, and complete the transposition. For an n×n matrix, it takes 2n+1 steps to complete the matrix transpose operation. However, this method is implemented with registers and combined switches, which has high hardware cost and high power consumption.

(3) MemorySkewing method

The MemorySkewing method uses a parallel memory system to realize the row and column operations of the matrix. It has been used in IlliacIV and BSP computer systems, but this will increase a lot of hardware overhead, thereby reducing the speed of memory access. It is too complicated and has little use value.

At present, the process of large-scale integrated circuits is getting smaller and smaller, and has reached the level of 10nm, and the requirements for integration are getting higher and higher. Whether it is a general-purpose CPU or DSP, it is developing from one core to multi-core. The requirements have been continuously improved, from scalar operation processing to vector operation processing, from vector operation processing to matrix operation processing, and the operation granularity of matrix is also from small granularity to large granularity, and new requirements are constantly put forward. In order to meet the new development requirements, the supercomputer and DSP oriented to vector operation and matrix operation must have a matrix operation unit supported by a matrix register body. One of the most important problems encountered in matrix computing is matrix transposition. In the future matrix computer structure, a matrix transposition component with high performance, low power consumption, flexible structure and multiple functions is firstly needed. In the existing matrix transposition methods, whether it is through software, or through special hardware, or through SIMD (Single Instruction Multiple Data, Single Instruction Multiple Data) network structure, or using existing memory methods to realize the matrix Transposition cannot simply, efficiently, and flexibly meet the requirements of matrix computers.

Contents of the invention

The technical problem to be solved by the present invention is: aiming at the technical problems existing in the prior art, the present invention provides a SRAM-based Apparatus and method for matrix transposition.

In order to solve the problems of the technologies described above, the technical solution provided by the invention is:

A device for matrix transposition based on SRAM, comprising an address decoding module, a read-write bus, a diagonal read control module, and n matrix transposition memory bodies; each matrix transpose memory body consists of n rows and n columns A matrix structure formed by connecting matrix memory modules, in each matrix structure of the matrix transpose memory body, the matrix memory modules located on the diagonal from the upper left to the lower right are all 14-tube SRAM memory modules, and the diagonal The other matrix memory modules are all 12-tube SRAM memory modules; the 14-tube SRAM memory modules are used to access the elements on the diagonal in the matrix to be transposed; the 12-tube SRAM memory modules are used to The elements outside the diagonal in the matrix are accessed; the diagonal read control module is connected with the matrix transpose memory body, and is used to decode the diagonal address and control the elements in the diagonal to be transposed. The read operation performed on the element.

As a further improvement of the device of the present invention: the 14-tube SRAM storage module includes a plurality of sequentially connected 1-bit 14-tube SRAM units, and the number of 1-bit 14-tube SRAM units is the same as the word length w of elements in the matrix to be transposed.

As a further improvement of the device of the present invention: the 1-bit 14-tube SRAM unit has separate control tubes for read and write operations, which respectively control the gating of read and write addresses. The control tubes of the 1-bit 14-tube SRAM unit include: two row read-write row control tubes, two row read-write column control tubes, two column read-write column control tubes, two column read-write row control tubes, and two row control tubes. A diagonal element readout control tube; the diagonal read control tube is used to control the gating of the diagonal element address in the matrix to be transposed; the row read-write row control tube, row read-write column control The tube, column read-write column control tube and column read-write row control tube control the gating of row and column data addresses in the matrix to be transposed.

As a further improvement of the device of the present invention: the 12-tube SRAM storage module includes a plurality of sequentially connected 1-bit 12-tube SRAM units, and the number of 1-bit 12-tube SRAM units is the same as the word length w of elements in the matrix to be transposed;

As a further improvement of the device of the present invention: the 1-bit 12-tube SRAM unit has separate control tubes for read and write operations, which respectively control the gating of read and write addresses. The control tubes of the 1-bit 12-tube SRAM unit include two row read-write row control tubes, two row read-write column control tubes, two column read-write column control tubes, and two column read-write row control tubes; Row read-write row control tube, row read-write column control tube, column read-write column control tube, and column read-write row control tube form row and column data access row and column address signal terminals, and control the row and column data addresses in the matrix to be transposed the strobe.

As a further improvement of the device of the present invention: the address decoding module includes a row reading and writing column address decoding module, a row reading and writing row address decoding module, and a column reading and writing column address decoding module respectively connected to the matrix transposition memory body And column read and write row address decoding module.

The present invention further provides a method for matrix transposition, the steps are:

(1) Input the matrix to be transposed, and judge the matrix type. If it is m×m order and m>n, execute step (2); if it is n×n order or m×m order, and m<n, execute step (3);

(2) Control the combined operation of multiple n-row and n-column registers, set the row and column address decoding of each register to be synchronized, and perform step (3) to access each register;

(3) Configure the access mode through instructions; if it is configured as a single-word access mode, perform step (4); if it is configured as a row write column read access mode, perform step (6) after performing step (5); if configured For column read and row write access mode, perform step (6) and then perform step (5); if configured as diagonal vector access mode, perform step (7);

(4) Access in a row-first manner, after decoding the row address, strobe the corresponding row read and write row address, after decoding the column address, strobe the row read and write column address, and access the single word through the row read and write bus;

(5) Read and write the elements of the row vector at the same time, after decoding the row address, strobe the corresponding row read and write row address, after decoding the column address, all the row read and write column addresses are strobed, through the row read and write bus access the row;

(6) Read and write the elements of the column vector at the same time, and after decoding the row address, select the corresponding column read and write column address. access to the column;

(7) Read and write the elements of the diagonal vector at the same time. After address decoding, all the column read and write row addresses are strobed, and the diagonal is accessed through the column read bus.

As a further improvement of the present invention: the configuration of the access mode in the step (3) is one of single word access, row write column read access, column write row read access and diagonal vector access.

As a further improvement of the method of the present invention: the specific implementation steps of the step (5) include:

(5.1) Determine the size of the row vector of the matrix to be transposed. If it is n rows, perform step (5.2); if it is m rows and m<n, perform step (5.3);

(5.2) Read and write all the elements of the row vector at the same time. After the row address is decoded, the corresponding row read and write row addresses in the 1~n rows are selected. After the column address is decoded, the row, read, write and column addresses are all selected. Rows are accessed through the row read and write bus;

(5.3) Read and write all the elements of the row vector at the same time, after decoding the row address, select the corresponding row read and write row address in the 1~m row, and after decoding the column address, read and write the column address 1~m in the row The column address of the column is strobed, and the row is accessed through the row read and write bus.

As a further improvement of the method of the present invention: the specific implementation steps of the step (6) include:

(6.1) Determine the size of the column vector of the matrix to be transposed. If it is n columns, perform step (6.2); if it is m columns and m<n, perform step (6.3);

(6.2) Read and write the elements of the column vector at the same time, and after the row address is decoded, the corresponding column read and write column addresses in the 1~n columns are strobed. After the column address is decoded, all the column read and write row addresses are strobed. The column read and write bus accesses the column;

(6.3) Read and write the elements of the column vector at the same time. After decoding the row address, select the corresponding column read and write column address in the 1~m columns. After the column address is decoded, all the column read and write row addresses are selected. Pass The column read and write bus accesses the columns.

Compared with the prior art, the present invention has the following advantages:

(1) The present invention separates the read and write operations on the basis of the efficient read and write performance of the SRAM storage unit, and can realize the row, column and diagonal read operations, requiring less time overhead, fast transposition speed, and high efficiency.

(2) The present invention uses multiple 12-tube and 14-tube SRAM storage units to realize matrix transposition, which consumes less equipment and consumes less power.

(3) The present invention can realize the transposition of various types of matrices. Through instructions, the rows and columns of the matrix can be flexibly tailored according to actual application requirements, and the access to elements can be single-word read and write, row read and column write, Row write column read, diagonal read and other forms, flexible structure, diverse functions.

Description of drawings

FIG. 1 is a schematic structural diagram of an SRAM-based matrix transposition device in the present invention.

FIG. 2 is a schematic diagram of the circuit structure of the matrix transpose memory body in this embodiment.

FIG. 3 is a schematic diagram of the circuit interface structure of the matrix transpose memory body in this embodiment.

FIG. 4 is a schematic diagram of the circuit structure of the 14-tube SRAM memory module in this embodiment.

FIG. 5 is a schematic diagram of the circuit interface of the 14-tube SRAM storage module in this embodiment.

FIG. 6 is a schematic diagram of the circuit structure of a 1-bit 14-tube SRAM unit in this embodiment.

FIG. 7 is a schematic diagram of a circuit interface of a 1-bit 14-tube SRAM unit in this embodiment.

FIG. 8 is a schematic diagram of the circuit structure of the 12-tube SRAM storage module in this embodiment.

FIG. 9 is a schematic diagram of the circuit interface of the 12-tube SRAM storage module in this embodiment.

FIG. 10 is a schematic diagram of the circuit structure of a 1-bit 12-tube SRAM unit in this embodiment.

FIG. 11 is a schematic diagram of a circuit interface of a 1-bit 12-tube SRAM unit in this embodiment.

Legend: 1. Matrix transpose memory body; 11. 14-tube SRAM storage module; 111. 1-bit 14-tube SRAM unit; 12. 12-tube SRAM storage module; 122. 1-bit 12-tube SRAM unit; Column address decoding module; 3. Row reading and writing row address decoding module; 4. Column reading and writing column address decoding module; 5. Column reading and writing row address decoding module; 6. Diagonal reading control module.

detailed description

The present invention will be further described in detail below in conjunction with the accompanying drawings and specific implementation.

As shown in FIG. 1 , the SRAM-based matrix transposition device in this embodiment includes an address decoding module, a read-write bus, n matrix transposition memory bodies 1 and a diagonal read control module 6 . The address decoding module and the diagonal reading control module 6 are both connected to the matrix transposition memory body 1 . The address decoding module decodes the address of the row and column where the transposed matrix is located and then selects the corresponding address; the read-write bus is divided into a row read-write bus and a column read-write bus. The decoding result accesses the single word or row vector of the transposed matrix; the column read and write bus accesses the column vector or diagonal elements of the transposed matrix according to the decoding result of the address decoding module; the diagonal read control module 6. Connect with the matrix transposition memory body, decode the diagonal address, and control the read operation of the elements on the diagonal in the matrix to be transposed.

As shown in Fig. 2 and Fig. 3, the structure and interface of the matrix transpose memory body in this embodiment has a matrix structure formed by connecting matrix memory modules in n rows and n columns. In the matrix structure of the matrix transpose memory body 1, the matrix storage modules on the diagonal L from the upper left to the lower right are all 14-tube SRAM storage modules 11, which are used to access the elements on the diagonal in the matrix to be transposed , wherein the diagonal line L is the connection direction from the upper left to the lower right diagonal line; the matrix storage modules other than the diagonal line L are all 12-tube SRAM storage modules 12, which are used to treat the transposed matrix outside the diagonal line element to access.

In this embodiment, the matrix transposition memory body 1 has four row and column data access row and column address signal terminals, which are respectively: row data access column address signal terminal Wr, row data access row address signal terminal Wc, column data Access row address signal end Rc and column data access column address signal end Rr. In the matrix transposition memory body 1, the row data access column address signal terminals Wr of the matrix storage modules of each row are connected to each other, and there are n rows in total, forming row data access column address signals Wr<1:n>; the matrix storage modules of each row The row data access and row address signal terminals Wc are connected, and there are n rows in total, forming a row data access row address signal Wc<1:n>; the column data access row address signal terminals Rc of each column matrix memory module are connected, and a total of n columns are formed. Column data access row address signal Rc<1:n>; the column data access column address signal terminal Rr of the matrix memory module of each column is connected, and there are n columns in total, forming the column data access column address signal Rr<1:n>; each row The row access data terminal wd<w: 1> of the matrix storage module is connected, and there are n rows in total to form the row access data original code signal wd<nw:1>, and the row access data complement signal /wd<w is formed in the same way: 1>; the column access data terminal rd<w:1> of the matrix storage module of each column is connected, and there are n rows in total to form the original code rd<nw:1> of the column access data. <nw:1>.

In this embodiment, the row and column data access row and column address signal terminals are controlled by the instruction of the access mode, and the address decoding module performs address decoding and simultaneously selects the corresponding address to execute the corresponding access operation. Since there are n rows and n columns of matrix storage modules, the operation of the entire row and column of the matrix to be transposed can be performed. Further, the 14-tube SRAM storage module 11 and the diagonal read control module 6 can read the diagonal to be transposed at one time. online data.

If the matrix to be transposed is A, the elements in A can be expressed as aij (i=1,2,3...n,j=1,2,3...n), and the bit refers to the element aij of matrix A, and its word The length is w bits. The 14-tube SRAM storage module 11 is a w-bit bit structure, which is formed by sequentially connecting w 1-bit 14-tube SRAM units 111 . As shown in FIG. 4 and FIG. 5 , the structure and interface of the 14-tube SRAM storage module 11 in this embodiment includes w sequentially connected 1-bit 14-tube SRAM units 111 . In the matrix transposition process, the read and write operations on the bit are consistent, so the row data access column address signal terminal Wr of each 14-tube SRAM memory module 11, the row data access row address signal terminal Wc, and the column data access row address The signal terminal Rc and the column data access column address signal terminal Rr are connected to each other to form the address strobe signal terminal for row, column or diagonal data access, and control the access of row, column or diagonal data; row and column data access The terminals wd and rd are respectively connected to each data bit of the matrix to be transposed, and the data in the matrix to be transposed is read or written.

As shown in Figure 6 and Figure 7, the circuit structure and interface of the 1-bit 14-tube SRAM unit 111 in this embodiment include: two row read-write column control tubes, the first MOS tube n1 and the second MOS tube n2, two row The third MOS tube n3 and the fourth MOS tube n4 of the read-write row control tube, the fifth MOS tube n5 and the sixth MOS tube n6 of the two column read-write column control tubes, the seventh MOS tube n7 of the two column read-write row control tubes and the eighth MOS transistor n8 and two diagonal element readout control transistors, the ninth MOS transistor n9 and the tenth MOS transistor n10. In the row and column address signal terminals of the row and column data access row and column address of the 1-bit 14-tube SRAM unit 111, The row read/write column signal terminal Wr is connected to the first MOS transistor n1 and the second MOS transistor n2 to control the gating of the row read/write column address; the row read/write row signal terminal Wc is connected to the third MOS transistor n3 and the fourth MOS transistor n4 Connect to control the strobe of the row read and write row address; the column read and write column signal terminal Rr is connected to the fifth MOS transistor n5 and the sixth MOS transistor n6 to control the strobe of the column read and write column address; the column read and write row signal terminal Rc It is connected with the seventh MOS transistor n7 and the eighth MOS transistor n8, and controls the strobe of the row address for column reading and writing; the diagonal control terminal Dia is connected with the ninth MOS transistor n9 and the tenth MOS transistor n10, and is connected with the seventh MOS transistor n7 Together with the eighth MOS transistor n8, it controls the gating of the diagonal address. The first MOS transistor n1, the second MOS transistor n2, the third MOS transistor n3, and the fourth MOS transistor n4 jointly support single-word access or row vector access to row operations. The fifth MOS transistor n5, the sixth MOS transistor n6, and the fourth MOS transistor n6 The seventh MOS transistor n7 and the eighth MOS transistor n8 jointly support single-word access or column vector access for column operations.

In this embodiment, the 12-tube SRAM memory module 12 has a bit structure with a word length of w, that is, it is formed by connecting w 1-bit 12-tube SRAM units 122 . As shown in Fig. 8 and Fig. 9, the circuit structure and interface of the 12-tube SRAM memory module of the present invention have the same structure and connection mode as the 1-bit 14-tube SRAM memory unit except for the diagonal control signal terminal Dia. The connection relationship of each 1-bit 12-tube SRAM unit 122 of the w-bit 12-tube SRAM memory module 12 is as follows: each 1-bit 12-tube SRAM unit 122 is connected to the column address signal terminal Wr for row data access, and the row address signal terminal Wc for row data access. Connected, the column address signal terminal Rr for column data access is connected, the row address signal terminal Rc for column data access is connected, the original code and inverse code of row access data are wd<1:w> and /wd<1:w>, row The original code and inverse code of the access data are rd<1:w> and /rd<1:w>.

As shown in Fig. 10 and Fig. 11, the circuit structure and interface of the 1-bit 12-tube SRAM unit 122 in this embodiment include all and 1-bit 14-tube SRAM unit 111 has the same structure, including: two row read-write column control tubes, the first MOS tube n1 and the second MOS tube n2, two row read-write row control tubes, the third MOS tube n3 and the fourth MOS tube Tube n4, two column read-write column control tubes fifth MOS tube n5 and sixth MOS tube n6, two column read-write row control tubes seventh MOS tube n7 and eighth MOS tube n8. The row read/write column signal terminal Wr is connected to the first MOS transistor n1 and the second MOS transistor n2 to control the gating of the row read/write column address; the row read/write row signal terminal Wc is connected to the third MOS transistor n3 and the fourth MOS transistor n4 Connect to control the strobe of the row read and write row address; the column read and write column signal terminal Rr is connected to the fifth MOS transistor n5 and the sixth MOS transistor n6 to control the strobe of the column read and write column address; the column read and write row signal terminal Rc It is connected with the seventh MOS transistor n7 and the eighth MOS transistor n8 to control the strobing of column read and write row addresses.

In this embodiment, corresponding to the 4 row and column data access row and column address signal terminals of the matrix transpose memory body 1, the address decoding module includes 4 corresponding address decoding modules, which are respectively: row, read, write, column address decoding Code module 2, row read-write row address decoding module 3, column read-write column address decoding module 4 and column read-write row address decoding module 5.

The row read-write column address decoding module 2 is connected to the row read-write column signal terminal Wr of the matrix transpose memory body 1, and the row address in the matrix to be transposed is decoded and the column address when the row data is accessed is simultaneously selected; the row read-write row address The decoding module 3 is connected with the row read-write row signal terminal Wc of the matrix transposition memory body 1, and the row address in the transposed matrix is decoded while gating the row data access; the column read-write column address decoding module 4 is connected with the matrix transfer Set the column read-write column signal terminal Rr of the memory body 1 to be connected, and the column address in the column address decoding in the transposed matrix is selected while the column data is accessed; the column read-write row address decoding module 5 is connected to the matrix transpose memory body 1 The column read and write row signal terminal Rc is connected, and the column address in the transposed matrix is to be decoded while the row address is selected when the column data is accessed; the diagonal read control module 6 is connected to the diagonal read control signal terminal of the matrix transpose memory body 1 Dia connection, decoding the diagonal address in the matrix to be transposed and selecting the address of the diagonal element in the matrix to be transposed at the same time.

In this embodiment, multiple flexible access modes can be realized through instructions, including single word access, row vector, column vector or diagonal access mode. Therefore, the n matrix transpose memory body 1 can be used as an on-chip LocalMemory, presenting a one-dimensional linear memory structure, with a storage space of n ³ words, accessed by word address, row by row, or as a two-dimensional on-chip Register RMi (i=1...n) or matrix transposition module can access 1 word at a time, and can also access 1 row/column vector Vi at a time, i=2, 3,...n; it can also be used as n matrix transposition The number of matrix transposition modes that can be formed is: C _n ¹ +C _n ² +C _n ³ +…+C _n ⁿ = 2 ⁿ -1.

In this embodiment, when accessed as a two-dimensional on-chip register RMi, there are n storage planes and wherein every two 2-D storage planes are isomorphic and have the same access mode; each storage plane has n×n bits The word length of each bit unit is w bits; among the n×n bit units of each storage plane, the main diagonal unit is composed of 14-tube SRAM memory modules, and the rest of the units are composed of 12-tube SRAM memory module modules . In each register RMi, RMi_Wr<1:n> performs row access row control, RMi_Wc<1:n> performs row access column control, RMi_Rr<1:n> performs column access column control, RMi_Rc<1:n> performs column access Access row control, RMi_Dia performs main diagonal read control, RMi_wd<nw: 1>, RMi_/wd<nw: 1> are row access data, RMi_rd<nw: 1>, RMi_/rd<nw: 1> are columns Access data where i = 1, 2, ..., n.

In this embodiment, the access mode configuration algorithm for single word, row vector, column vector and diagonal vector in each register RMi is:

1) Algorithm A1 when accessing by word is:

2) Algorithms for accessing A2 by row vector and accessing algorithm A3 by column vector are:

4) According to the diagonal data access algorithm A4 is:

In this embodiment, a matrix transposition can be completed by using the access mode of row writing and column reading, or can be transposed by using the method of column writing and row reading. Various types of matrices such as n×n, m×m, m×n and n×m can be transposed.

When the matrix to be transposed is of order n×n, the working process of transposing is:

1) The transposition of the matrix transposes the matrix through row writing and column reading. When writing a row, read and write n elements of the row vector at the same time. At this time, the corresponding row read and write row address module 3 performs row address Decoding, the row read/write column address signal terminal Wr<i> is strobed, i=1, 2,..., n is the number of rows where it is located, and the corresponding row read/write column address decoding module 2 performs column address decoding, Row read and write row address signal terminals Wc<1:n> are all strobed, and the row is accessed through the row read and write bus; when the column is read, the n elements of the column vector are simultaneously read and written. At this time, the corresponding column The read-write row address module 5 performs row address decoding, the column read-write column address signal terminal Rr<j> is strobed, j=1,2,...,n is the number of columns, and the corresponding column read-write column address module 4 Perform column address decoding, the column read and write row address signal terminals Rc<1:n> are all strobed, and the columns are accessed through the column read and write bus;

2) The transposition of the matrix transposes the matrix through column writing and row reading. When writing columns, n elements of the column vector are read and written at the same time, and the corresponding column address module 4 for column reading and writing performs column address decoding. The column read/write row addresses Rc<1:n> are all strobed, and the corresponding column read/write row address module 5 performs row address decoding, and the column read/write column address signal terminal Rr<j> is strobed.

When the matrix to be transposed is of order m×m and m<n, the working process of transposing is:

1) The transposition of the matrix transposes the matrix through row writing and column reading. When writing a row, the m elements of the row vector are read and written simultaneously. At this time, the corresponding row read and write row address module 3 performs row address Decoding, row read/write row address signal terminal Wc<i> is strobed, i=1, 2,...,m is the number of rows, the corresponding row read/write column address module 2 performs column address decoding, row read The write column address signal terminal Wr<1:n> is all strobed, and the row is accessed through the row read and write bus; when the column is read, the n elements of the column vector are read and written simultaneously, and the corresponding column read and write at this time The row address module 5 decodes the row address, the column address signal terminal Rr<j> is strobed, and j=1, 2,..., m is the number of columns, and the corresponding column read and write column address module 4 performs Column address decoding, column read and write row address signal terminals Rc<1:m> are all strobed, and columns are accessed through the column read and write bus;

2) The transposition of the matrix transposes the matrix through column writing and row reading. When writing columns, n elements of the column vector are read and written at the same time, and the corresponding column address module 4 for column reading and writing performs column address decoding. The column read/write row address Rc<1:m> is all strobed, the corresponding column read/write row address module 5 performs row address decoding, and the column read/write column address signal terminal Rr<j> is strobed.

When the matrix to be transposed is of order m×m and m>n, multiple RM registers composed of multiple matrix transposition memory bodies 1 need to be jointly operated to form a matrix of order m×m logically. The access to rows and columns is the same as the access to an n×n matrix, the difference is that multiple RM registers correspond to the row read and write row address signal terminal Wr, the row read and write column address signal terminal Wc, and the column read and write The row address signal terminal Rr and the column address signal terminal Rc for reading and writing are synchronized, and work together in unison to complete the transposition of the matrix.

When the matrix to be transposed is an m×n or n×m order matrix, where m>n or m<n, the matrix to be transposed is not a square matrix, and its operation process is consistent with the transposition principle of an m×m order matrix ,No longer. In the process of all writing and reading, the reading of columns or rows can only be started when all rows or columns have been written.

With the above structure, the read and write operations are separated while applying the efficient read and write performance of the SRAM storage unit, and the diagonal read operation can also be realized through the 14-tube SRAM diagonal structure, and the row address and column address strobe through the data access It can perform row read, row write, column read, column write and diagonal read operations. Each matrix transpose memory body contains multiple storage units, which can perform serial or parallel read and write, write serial read and parallel, and write parallel Multiple reading and writing methods such as serial reading or diagonal parallel reading or serial reading, generating A ^T from matrix A requires only n+n clock cycles, the implementation method is simple, the transposition speed is fast and efficient. Moreover, the rows and columns can be flexibly tailored according to actual application requirements, making an on-chip LocalMemory flexible in structure, diverse in function, easy to integrate, and low in power consumption.

In this embodiment, using the matrix transposition method of the device of the present invention, the steps are:

(1) Input the matrix to be transposed, and judge the matrix type. If it is m×m order and m>n, execute step (2); if it is n×n order or m×m order, and m<n, execute step (3);

(2) Control the combined operation of multiple n-row and n-column registers, set the row and column address decoding of each register to be synchronized, and perform step (3) to access each register;

(3) Configure the transposition mode through instructions; if it is configured as a single-word access mode, perform step (4); if it is configured as a row read-in column write-out access mode, perform step (5); if it is configured as a column read-in row To write out the access mode, perform step (6); if configured as a diagonal vector access mode, perform step (7);

(4) Access the single word in a row-first manner. At this time, the corresponding row data access row address gating module performs row address decoding, and the row read and write row address Wc<i> is strobed, and i is the row where the word is located. , the corresponding row data access column address decoding module performs column address decoding, the row read-write column address Wr<j> is strobed, j is the column where the word is located, and the word w is accessed through the row read-write bus.

(5) Read and write the elements of the row vector at the same time, after the row address is decoded, the row address is gated for reading and writing, and after the column address is decoded, the column address for reading and writing is strobed, and the row is accessed through the row reading and writing bus;

(6) Read and write the elements of the column vector at the same time, and after decoding the row address, select the column address for reading and writing. ;

(7) Read and write the elements of the diagonal vector at the same time. After address decoding, all the column read and write row addresses are strobed, and the diagonal is accessed through the column read bus.

In this embodiment, it is possible to realize the transposition of the matrix of n×n order, m×m order, m×n, n×m order, etc., where n>1, m>n or 1<m<n .

In this embodiment, the matrix can be transposed by row writing and column reading, and the matrix can also be transposed by row writing and row reading, row writing or reading is performed by row vector access operations, and row vector access operations are performed by column vector access operations. Perform column writing or reading, write and read, and read out columns or rows only after all rows or columns have been written.

The specific steps for performing steps (5) and (6) vary according to the type of matrix to be transposed.

When transposing an n×n order matrix, step (5) is specifically: read and write n elements of the row vector at the same time, the row read and write row address Wc<i> is selected, i=1,2,… , n, the row read/write column address Wr<1:n> is all strobed, and the row is accessed through the row read/write bus; step (6) is: read and write to n elements of the column vector at the same time, column read/write The column address Rr<j> is strobed, j=1, 2,..., n column read and write row addresses Rc<1:n> are all strobed, and the column is accessed through the column read and write bus.

When transposing the matrix of order m×m, when m<n, step (5) is: when writing a row, the row read/write column address Wr<1:m> is all strobed, and the row read/write row address Wc< i> is strobed (i=1,2,...,m); when the column is read, the column address Rr<j> is gated, j=1,2,...,m; step (6) is : Column read and write row address Rc<1:m> is all strobed, column read and write column address Rr<j> is strobed, j=1,2,...,m, transpose when row is read, row read and write The row address Wc<i> is strobed, i=1,2,...,m.

When m>n, step (2) needs to be performed first, that is, multiple n-row and n-column registers are required to participate in the operation. In this embodiment, multiple RM registers composed of multiple matrix transposition memory bodies 1 are controlled to jointly operate. A matrix of m×m order is logically formed, and the row read and write column address signal terminal Wr, the row read and write row address signal terminal Wc, the column read and write row address signal terminal Rr and the column read signal terminal corresponding to multiple RM registers are formed. The pace of writing the column address signal terminal Rc is set to be synchronous, and multiple RM registers cooperate to complete the transposition of the matrix, and its access to rows and columns is the same as that of n×n order matrices.

The reading and writing serial parallel mode can be serial or parallel reading and writing, writing serial reading parallel, writing parallel reading serial or diagonal parallel reading or serial reading, and has a matrix transposition function suitable for various matrices.

For the transposition of m×n and n×m order matrices, the transposition process is consistent with the transposition steps of m×m order matrices.

In the present invention, SDRAM can also be used instead of SRAM, and its principle is consistent with the present invention.

The above descriptions are only preferred implementations of the present invention, and the protection scope of the present invention is not limited to the above-mentioned embodiments, and all technical solutions under the idea of the present invention belong to the protection scope of the present invention. It should be pointed out that for those skilled in the art, some improvements and modifications without departing from the principles of the present invention should also be regarded as the protection scope of the present invention.

Claims (8)

1. a kind of device based on the matrix transposition of SRAM, it is characterized in that: comprise address decoding module, read-write bus, diagonal read control module (6) and n matrix transposition memory bodies (1); The matrix transpose memory body (1) is a matrix structure formed by connecting n rows and n column matrix storage modules. The matrix storage modules on the diagonal are all 14-tube SRAM storage modules (11), and the matrix storage modules outside the diagonal are all 12-tube SRAM storage modules (12); the 14-tube SRAM storage modules (11) are used to treat The elements on the diagonal in the transpose matrix are accessed; the 12-tube SRAM storage module (12) is used to access the elements outside the diagonal in the transposed matrix; the diagonal read control module ( 6) connected with the matrix transposition memory body (1), used to decode the diagonal address and control the read operation of the elements on the diagonal in the matrix to be transposed; the 14-tube SRAM memory module (11 ) includes a plurality of sequentially connected 1-bit 14-tube SRAM units (111), and the number of 1-bit 14-tube SRAM units (111) is the same as the word length w of elements in the matrix to be transposed; The 12-tube SRAM storage module (12) includes a plurality of sequentially connected 1-bit 12-tube SRAM units (122), and the number of 1-bit 12-tube SRAM units (122) is the same as the word length w of elements in the matrix to be transposed . 2. the device based on the matrix transposition of SRAM according to claim 1, is characterized in that: described 1 14 pipe SRAM units (111) have the separate control tube of read and write operation, respectively control the gate of read and write address ; The control tubes of the 1-bit 14-tube SRAM unit (111) include: two row read-write row control tubes, two row read-write column control tubes, two column read-write column control tubes, two column read-write row control tubes A control tube and two diagonal element readout control tubes; the diagonal element readout control tube is used to control the gating of the diagonal element address in the matrix to be transposed; the row read and write row control tube , a row read-write column control tube, a column read-write column control tube and a column read-write row control tube, which are respectively used to control the strobe of the row and column data access addresses. 3. the device based on the matrix transposition of SRAM according to claim 1, is characterized in that: described 1 12 pipe SRAM units (122) have the separate control tube of read and write operation, respectively control the gate of read and write address ; The control tubes of the 1-bit 12-tube SRAM unit (122) include two row read-write row control tubes, two row read-write column control tubes, two column read-write column control tubes, and two column read-write row control tubes. ; The row read-write row control tube, the row read-write column control tube, the column read-write column control tube and the column read-write row control tube are used to control the strobe of row and column data access addresses. 4. the device based on the matrix transposition of SRAM according to claim 1, is characterized in that: described address decoding module comprises the row read-write column address decoding module ( 2), row read-write row address decoding module (3), column read-write column address decoding module (4) and column read-write row address decoding module (5). 5. A matrix transposition method utilizing any one of the devices described in claims 1 to 4, characterized in that the steps are: (1) Input the matrix to be transposed, and judge the matrix type. If it is m×m order and m>n, execute step (2); if it is n×n order or m×m order, and m<n, execute Step (3); (2) control the joint operation of registers of multiple n rows and n columns, set the row and column address decoding of each register to be synchronous, and perform step (3) to access each register; (3) Configure the access mode by instruction; if configured as a single-word access mode, perform step (4); if configured as a row write column read access mode, perform step (6) after performing step (5); if configured For column write row read access mode, perform step (5) after performing step (6); if configured as diagonal vector access mode, perform step (7); (4) Access in a row-first manner, after decoding the row address, strobe the corresponding row read-write row address, after decoding the column address, strobe the row read-write column address, and access the single word through the row read-write bus; (5) Read and write the elements of the row vector at the same time, and after the row address is decoded, the corresponding row read and write row address is selected. After the column address is decoded, all the row read and write column addresses are selected, and the row read and write bus is passed. access the row; (6) Read and write the elements of the column vector at the same time, and after decoding the row address, select the corresponding column read and write column address. access to the column; (7) Read and write the elements of the diagonal vector at the same time, and after address decoding, the column read and write row addresses are all strobed, and the diagonal is accessed through the column read bus. 6. according to the method for matrix transposition described in claim 5, it is characterized in that, the configuration of access mode in the described step (3) is single-word access, row writes column read access, column writes row read access and one of diagonal vector access. 7. according to the method for matrix transposition described in claim 5, it is characterized in that, described step (5) concrete implementation step comprises: (5.1) Determine the size of the row vector of the matrix to be transposed, if it is n rows, perform step (5.2); if it is m rows and m<n, perform step (5.3); (5.2) Read and write all the elements of the row vector at the same time. After the row address is decoded, the corresponding row read and write row addresses in the 1 to n rows are selected. After the column address is decoded, the row, read and write column addresses are all selected. Rows are accessed through the row read and write bus; (5.3) Read and write all the elements of the row vector at the same time, after decoding the row address, strobe the corresponding row read and write row address in 1~m rows, and after the column address is decoded, all the row read and write column addresses are strobed, Rows are accessed through the row read and write bus. 8. according to the method for matrix transposition described in claim 5, it is characterized in that, described step (6) concrete implementation step comprises: (6.1) Determine the size of the column vector of the matrix to be transposed, if it is n columns, perform step (6.2); if it is m columns and m<n, perform step (6.3); (6.2) Read and write the elements of the column vector at the same time. After decoding the row address, select the corresponding column read and write column address in the 1~n columns. After the column address is decoded, all the column read and write row addresses are selected. The column read and write bus accesses the column; (6.3) Read and write the elements of the column vector at the same time, after decoding the row address, strobe the corresponding column read and write column address in the 1~m columns, after the column address is decoded, all the column read and write row addresses are strobed, through The column read and write bus accesses the columns.