Matrix operations in an integrated circuit device

Description

FIELD OF THE INVENTION

This invention relates to performing matrix operations in integrated circuit devices, and particularly in programmable integrated circuit devices including, for example, programmable logic devices (PLDs).

BACKGROUND OF THE INVENTION

Matrix operations on large matrices are becoming more common. For some technical problems, solutions may involve matrices as large as 1000-by-1000. One common operation is matrix transposition. For example, it may be necessary to transpose a large matrix to perform a Fast Fourier Transform operation, an interleaving operation, or other linear algebraic operations.

Large transposition operations can be broken down into a series of smaller transposition operations. For example, to transpose an 8-by-8 matrix, one can break down the matrix into four 2-by-2 matrices. Each of the 2-by-2 matrices can be transposed individually in a series of “inner transposition” operations, after which the larger matrix can be treated as a 2-by-2 matrix, each of whose elements is one of the smaller 2-by-2 matrices. Transposing the positions of the smaller matrices in an “outer transposition” operation, after each of the smaller matrices has been transposed individually, results in a transpose of the larger 8-by-8 matrix.

Such a cascaded transposition technique can be used to transpose any size matrix. However, when the technique is implemented in hardware, memory speed limitations may come into play. For example, some types of memory, such as DDR SDRAM (Double Data Rate Synchronous Dynamic RAM) may be read much faster in one direction (vertically or horizontally) than in the other direction. Thus, for large matrices, performing the transposition within an acceptable duration may require fast memories that are expensive in terms of both price and power consumption. For example, if the remainder of the system uses double-data-rate (DDR) memory, it may be necessary to use quad-data-rate (QDR) memories for the transposition operation.

SUMMARY OF THE INVENTION

In accordance with the present invention, there is provided matrix operations circuitry for performing operations on submatrices of an input matrix. The matrix operations circuitry includes a first working memory in which individual ones of the submatrices are operated on. The first working memory has a first submatrix size. The matrix operations circuitry also includes a second working memory in which a collection of the submatrices, that have been operated on in the first working memory, is operated on. The second working memory has an optimum burst size, and the first submatrix size is matched to the optimum burst size.

A method of configuring such circuitry on a programmable device, and a machine-readable data storage medium encoded with software for performing the method, are also provided.

BRIEF DESCRIPTION OF THE DRAWINGS

Further features of the invention, its nature and various advantages will be apparent upon consideration of the following detailed description, taken in conjunction with the accompanying drawings, in which like reference characters refer to like parts throughout, and in which:

FIG. 1 shows an example of the definition of a matrix transposition;

FIG. 2 shows an example of transposition of elements within submatrices of a matrix;

FIG. 3 shows an example of transposition of submatrices considered as elements of a matrix;

FIG. 4 shows an example of a circuit structure 400 according to an embodiment of the invention;

FIG. 5 is a cross-sectional view of a magnetic data storage medium encoded with a set of machine-executable instructions for performing a method according to the present invention;

FIG. 6 is a cross-sectional view of an optically readable data storage medium encoded with a set of machine executable instructions for performing a method according to the present invention; and

FIG. 7 is a simplified block diagram of an illustrative system employing a programmable logic device incorporating the present invention.

DETAILED DESCRIPTION OF THE INVENTION

The present invention may be used to transpose, at acceptable speed, a matrix of any size, provided at least one of its dimensions is a non-prime number, by optimizing the size of the inner transposition operation to the burst speed of the memory being used. In practice, the non-prime number restriction may not come into play often, because most matrices that are operated on are large enough that it becomes unusual to find one with a prime dimension.

FIG. 1 shows an example of the definition of a matrix transposition. Although this example depicts the case of a 4×4 matrix, any size matrix may be transposed. As seen in FIG. 1, transposition involves reading each column 111 of a source matrix 101, and writing that column 111 as a row 122 of a transposed matrix 102. This can also be thought of as reading each row 121 of source matrix 101, and writing that row 121 as a column 112 of a transposed matrix 102. When performed electronically in a memory, one of the two orthogonal directions will be slower than (as slow as 5% of the speed of) the other direction. Whether one reads rows and write columns, or reads columns and writes rows, either the reading or the writing will be in the slow direction.

As seen in FIG. 1, for a square matrix, transposition results in the flipping of source matrix 101 about its upper-left-to-lower-right diagonal. However, any shape matrix can be transposed by writing each column, in order, as a row (or each row, in order, as a column). For a non-square matrix, this results in changing the dimensions of the matrix from m×n to n×m. (Technically, the same is true for a square matrix, except that for a square matrix m×n and n×m are the same.)

Matrix transposition can be cascaded—i.e., performed by breaking down the source matrix into smaller submatrices, and transposing each submatrix. Then, treating the submatrices as the elements of the source matrix, the positions of the submatrices can be transposed. FIGS. 2 and 3 show an example of transposition of a 4×4 matrix as a cascaded transposition of 2×2 submatrices.

As seen in FIG. 2, a 4×4 source matrix 201 may be broken down into four 2×2 submatrices 211, and each submatrix 211 may be transposed to yield an intermediate matrix 202 composed of transposed submatrices 212. Next, as shown in FIG. 3, treating transposed submatrices 212 as elements of matrix 202, the positions of transposed submatrices 212 are transposed within matrix 202 to yield transposed matrix 301. Comparison with FIG. 1 shows that source matrix 201 is identical to source matrix 101, and transposed matrix 301, derived using the cascaded transposition technique, is identical to transposed matrix 102, derived using the straightforward transposition technique.

As noted above, matrix transposition is used in many mathematical operations, including, but not limited to, Fast Fourier Transforms (FFTs), back-substitution for QR decomposition, interleaving, and various linear algebraic techniques.

For example, a 1-million-point FFT requires a 1,000×1,000 transposition with 32 bit I and Q data. In such a case, involving complex numbers each of which has a 32-bit real component and a 32-bit imaginary component, each element includes 64 bits. With 1 million elements, the total memory required may exceed 64 Mb, exclusive of buffering. That storage requirement may not present substantial difficulties with available DDR densities, but the data access may be very irregular. Depending on the type of memory used, as noted above, reading and writing may be substantially slower in one direction than in the direction orthogonal to the one direction. To maintain the desired throughput, this may require performing the transposition operation entirely in small, expensive, power hungry QDR external memories.

In accordance with embodiments of the present invention, the size of the submatrices is chosen to jointly optimize the amount of internal memory required (in this case, optimization may be minimization), and the burst length of the “external,” or main matrix, memory, which may be DDR memory (in this case, optimization may be maximization).

For example, if DDR memory has an optimal burst length of B=64 words, then the 1-million-point FFT described above may be optimized by selecting an inner (i.e., submatrix) transposition size of 8×8=64 words. With an inner square size of 8×8, a 1 Mb DDR memory (containing 2²⁰ bits) can be broken down into 128×128 8×8 submatrices (2⁷×2⁷×2³×2³=2²⁰). If the transposition were performed using the straightforward technique, for a burst length of 1 the memory efficiency is less than 5%. However, for a DDR memory with a burst length of 64, the memory efficiency may exceed 90% with effective bank interleaving.

Thus, a submatrix size of 8×8 in such a case improves efficiency by a factor of more than 18. The optimum submatrix size may vary depending on the particular type of memory involved, and similarly the efficiency improvement will depend on not only the efficiency of the particular memory at the optimum submatrix size for that memory, but also on the efficiency for a burst length of 1 for that memory. However, the ability to use DDR memory (e.g., DDR3 memory) instead of QDR memory reduces power consumption by at least 50%, reduces cost by up to 90%, reduces the amount of board space consumed, and increases the total aggregate bandwidth.

As noted above, the cascading technique will work with any size matrix, whether square nor non-square, as long at least one of its dimensions is not a prime number. Therefore, when implementing the technique in hardware, a series of identical reusable blocks can be provided regardless of the size of the matrix to be transposed (although the external memory for storing the input and output matrix, and the scratchpad memory, may be of different sizes). This is particularly advantageous when the technique is implemented in a programmable logic device such as a field-programmable gate array (FPGA) which is built as a series of identical reusable blocks. Moreover, programming software for such an FPGA implementation can similarly be modular and scalable.

The technique also may extended beyond two-dimensional matrices. For example, a Super Sample Rate Fast Fourier Transform (SSFFT) can involve transposition of a second vector, which effectively is a rotation of a three-dimensional structure. Indeed, the transposition technique can be extended generically to n-dimensional structures, where it is more commonly referred to as permutation. For example, an N×M×P matrix can become an M×P×N matrix or a P×M×N or some other variant.

FIG. 4 shows an example of a circuit structure 400 according to an embodiment of the invention for implementing a two-dimensional transposition. Circuit structure 400 may be implemented in any dedicated circuitry—e.g., in an application-specific integrated circuit (ASIC)—or may be configured in a programmable device as discussed above. Either way, transposition engine 401 includes an “internal” or scratchpad memory 411 which is sized according to the size of the submatrices to be transposed in the first, or inner, transposition step, as well as an external memory interface 412. Internal address generator 421 generates the addressing for performing the inner transposition in internal memory 411, while external address generator 422 generates the addressing for external memory interface 412 to control the outer transposition. The actual memory write operations for the outer transposition are performed in external memory 402, which is external to transposition engine 401, and may be completely external to whatever device transposition engine 401 is implemented in.

Source memory 441 is external to transposition engine 401, and may be completely external to whatever device transposition engine 401 is implemented in. In operation, data are read into transposition engine 401 from source memory 441 in blocks of the inner transposition size, which are transposed in internal memory 411 under control of internal address generator 421 and transferred at 451 to external memory interface 412. External memory interface 412 transfers the inner transposition results at 452 to external memory 402, and reads them back via 452, under the control of external address generator 422 to perform the outer transposition. The results are read out at 453.

Internal memory 411 operates on single-element words. The size of internal memory 411 is selected with the goal of reducing that size, but also so that the number of elements in internal memory 411 form a larger word of a size for which the burst speed of external memory 402 is improved. For example, in the 1 Mb FFT example above, the size of internal memory 411 may be 64 single-element words, which correlates to the 64-word optimum burst size of external memory 402. Of course, these are only examples. If a particular DDR memory used as external memory 402 has a different optimum burst size, then internal memory 411 can be sized accordingly. The various parameters of a system can be traded off, and a user can select a burst size that allows the most flexible trade-offs.

As a comparison, in previously known matrix transposition architectures (not shown), internal memory 411 and internal address generator 421 would not be present, and the entire transposition operation would be carried out using external memory interface 412 and external memory 402, under the control of external address generator 422. Because in such an architecture there was no internal memory, transfers between external memory interface 412 and external memory 402 would have had to be in the form of single words, at only about 5% efficiency, as compared to 90% efficiency for the embodiment of the invention described above.

As noted above, the structures described above may be provided in fixed logic, in which case the sizes of the various components may be fixed to a particular application. Alternatively, the fixed logic circuitry could allow for limited parameterization.

Again as noted above, another potential use for the present invention may be in programmable integrated circuit devices such as programmable logic devices, where programming software can be provided to allow users to configure a programmable device to perform matrix operations.

Instructions for carrying out a method according to this invention for programming a programmable device to perform matrix transposition may be encoded on a machine-readable medium, to be executed by a suitable computer or similar device to implement the method of the invention for programming or configuring PLDs or other programmable devices to perform addition and subtraction operations as described above. For example, a personal computer may be equipped with an interface to which a PLD can be connected, and the personal computer can be used by a user to program the PLD using a suitable software tool, such as the QUARTUS® II software available from Altera Corporation, of San Jose, Calif.

FIG. 5 presents a cross section of a magnetic data storage medium 800 which can be encoded with a machine executable program that can be carried out by systems such as the aforementioned personal computer, or other computer or similar device. Medium 800 can be a floppy diskette or hard disk, or magnetic tape, having a suitable substrate 801, which may be conventional, and a suitable coating 802, which may be conventional, on one or both sides, containing magnetic domains (not visible) whose polarity or orientation can be altered magnetically. Except in the case where it is magnetic tape, medium 800 may also have an opening (not shown) for receiving the spindle of a disk drive or other data storage device.

The magnetic domains of coating 802 of medium 800 are polarized or oriented so as to encode, in manner which may be conventional, a machine-executable program, for execution by a programming system such as a personal computer or other computer or similar system, having a socket or peripheral attachment into which the PLD to be programmed may be inserted, to configure appropriate portions of the PLD, including its specialized processing blocks, if any, in accordance with the invention.

FIG. 6 shows a cross section of an optically-readable data storage medium 810 which also can be encoded with such a machine-executable program, which can be carried out by systems such as the aforementioned personal computer, or other computer or similar device. Medium 810 can be a conventional compact disk read-only memory (CD-ROM) or digital video disk read-only memory (DVD-ROM) or a rewriteable medium such as a CD-R, CD-RW, DVD-R, DVD-RW, DVD+R, DVD+RW, or DVD-RAM or a magneto-optical disk which is optically readable and magneto-optically rewriteable. Medium 810 preferably has a suitable substrate 811, which may be conventional, and a suitable coating 812, which may be conventional, usually on one or both sides of substrate 811.

In the case of a CD-based or DVD-based medium, as is well known, coating 812 is reflective and is impressed with a plurality of pits 813, arranged on one or more layers, to encode the machine-executable program. The arrangement of pits is read by reflecting laser light off the surface of coating 812. A protective coating 814, which preferably is substantially transparent, is provided on top of coating 812.

In the case of magneto-optical disk, as is well known, coating 812 has no pits 813, but has a plurality of magnetic domains whose polarity or orientation can be changed magnetically when heated above a certain temperature, as by a laser (not shown). The orientation of the domains can be read by measuring the polarization of laser light reflected from coating 812. The arrangement of the domains encodes the program as described above.

A PLD 90 programmed according to the present invention may be used in many kinds of electronic devices. One possible use is in a data processing system 900 shown in FIG. 7. Data processing system 900 may include one or more of the following components: a processor 901; memory 902; I/O circuitry 903; and peripheral devices 904. These components are coupled together by a system bus 905 and are populated on a circuit board 906 which is contained in an end-user system 907.

System 900 can be used in a wide variety of applications, such as computer networking, data networking, instrumentation, video processing, digital signal processing, or any other application where the advantage of using programmable or reprogrammable logic is desirable. PLD 90 can be used to perform a variety of different logic functions. For example, PLD 90 can be configured as a processor or controller that works in cooperation with processor 901. PLD 90 may also be used as an arbiter for arbitrating access to a shared resources in system 900. In yet another example, PLD 90 can be configured as an interface between processor 901 and one of the other components in system 900. It should be noted that system 900 is only exemplary, and that the true scope and spirit of the invention should be indicated by the following claims.

Various technologies can be used to implement PLDs 90 as described above and incorporating this invention.

It will be understood that the foregoing is only illustrative of the principles of the invention, and that various modifications can be made by those skilled in the art without departing from the scope and spirit of the invention. For example, the various elements of this invention can be provided on a PLD in any desired number and/or arrangement. One skilled in the art will appreciate that the present invention can be practiced by other than the described embodiments, which are presented for purposes of illustration and not of limitation, and the present invention is limited only by the claims that follow.