Higher accuracy of non-volatile memory-based vector multiplication

Abstract

A multiplication device for performing a matrix-vector-multiplication may be provided. The multiplication device comprises a memristive crossbar array comprising a plurality of memristive devices. The device comprises a decomposition unit adapted for decomposing a matrix into a partial sum of multiple sub-matrices, and decomposing a vector into a sum of multiple sub-vectors, a programming unit adapted for programming the plurality of the memristive devices with values representing elements of the sub-matrices such that each one of the memristive devices corresponds to one of the elements of the sub-matrices, an applying unit adapted for applying elements of one of the multiple sub-vectors as input values to the memristive crossbar array to input lines of the memristive crossbar array resulting in partial results at output lines of the memristive crossbar array, and a summing unit adapted for scaling and summing the partial results building the product of the matrix and the vector.

Claims

1. A multiplication device for performing a matrix-vector-multiplication, the multiplication device comprising a memristive crossbar array comprising a plurality of memristive devices, the multiplication device comprising: a programming unit adapted for programming the plurality of the memristive devices with values representing elements of the sub-matrices such that each one of the memristive devices corresponds to one of the elements of the sub-matrices; an applying unit adapted for applying elements of one of the multiple sub-vectors as input values to the memristive crossbar array to input lines of the memristive crossbar array resulting in partial results at output lines of the memristive crossbar array; and a summing unit adapted for scaling and summing the partial results building the product of the matrix and the vector.

2. The multiplication device according to claim 1, wherein the groups of input values are voltage values at constant duration times.

3. The multiplication device according to claim 1, wherein the groups of input values are duration times of constant voltage.

4. The multiplication device according to claim 1, wherein the scaling and summing the partial results is performed in a software module.

5. The multiplication device according to claim 1, further comprising: an integrated analogue/digital on-chip circuitry; wherein the scaling and summing the partial results is performed by the analogue/digital on-chip circuitry.

6. The multiplication device according to claim 1, wherein the programming unit is also adapted for programming the plurality of the memristive devices with values, representing elements of the sub-matrices is performed one sub-matrix at a time.

7. The multiplication device according to claim 1, wherein the memristive crossbar array is divided into a plurality of independent sub-crossbar arrays; and wherein the programming the plurality of the memristive devices with values representing elements of the sub-matrices is performed such that each sub-matrix relates to a different one of the plurality of independent sub-crossbar arrays.

8. The multiplication device according to claim 1, wherein a scaling factor .sub.l for one of the sub-matrixes A.sub.l and a scaling factor .sub.m for one of the sub-vectors is selected such that $P {.Math._{l^{}}_{m^{}} e_{l^{} m^{}} .Math. > .Math. \underset{l l^{} .Math. m m^{}}{.Math.}_{l}_{m} w_{lm} .Math.} < .Math. l^{}, m^{}$ is satisfied, wherein: e.sub.lm is an error value defined as difference between an exact result vector element w.sub.lm of the product of one of the sub-matrices and one of the sub-vectors and an actually measured related product value, P is the probability that the norm value of .sub.l.sub.me.sub.lm is larger than the norm value of the sum .sub.ll,mm.sub.l.sub.mw.sub.lm, and is a predefined probability tolerance value.

9. The multiplication device according to claim 1, wherein a scaling factor .sub.l for one of the sub-matrixes A.sub.l and a scaling factor .sub.m for one of the sub-vectors is selected such that $P {.Math. \underset{l .Math. m}{.Math.}_{l}_{m} e_{lm} .Math. > .Math._{l^{}}_{m^{}} w_{l^{} m^{}} .Math.} < .Math. l^{}, m^{}$ is satisfied, wherein: e.sub.lm is an error value defined as difference between an exact result vector element w.sub.lm of the product of one of the sub-matrices and one of the sub-vectors and an actually measured related product value, P is the probability that the norm value of the sum .sub.l,m.sub.l.sub.me.sub.lm is larger than the norm value .sub.l.sub.mw.sub.lm, and is a predefined probability tolerance value.

10. The multiplication device according to claim 1, wherein the memristive device is selected from the group consisting of a phase change memory, a metal oxide resistive random-access memory, a conductive bridge random access memory, a magnetic random access memory, an optical memory element, a ferroelectric random access memory, and a system device, comprising transistors, resistors, capacitors, and/or inductors, jointly emulating a behavior of a memristive device.

11. A method for performing a matrix-vector-multiplication, the method comprising: providing a memristive crossbar array comprising a plurality of memristive devices; programming the plurality of the memristive devices with values representing elements of a sub-matrices such that each one of the memristive devices corresponds to one of the elements of the sub-matrices; applying elements of one of the multiple sub-vectors as input values to the memristive crossbar array to input lines of the memristive crossbar array resulting in partial results at output lines of the memristive crossbar array; and scaling and summing the partial results building the product of the matrix and the vector.

12. The method according to claim 11, wherein the groups of input values are voltage values at constant duration times.

13. The method according to claim 11, wherein the groups of input values are duration times of constant voltage.

14. The method according to claim 11, wherein the scaling and summing the partial results is performed in a software module.

15. The method according to claim 11, wherein the scaling and summing the partial results is performed by an analogue/digital on-chip circuitry.

16. The method according to claim 11, further comprising; programming the plurality of the memristive devices with values, representing elements of the sub-matrices is performed one sub-matrix at a time.

17. The method according to claim 11, further comprising; dividing the memristive crossbar array into a plurality of independent sub-crossbar arrays; and wherein the programming the plurality of the memristive devices with values, representing elements of the sub-matrices is performed such that each sub-matrix relates to a different one of the plurality of independent sub-crossbar arrays.

18. The method according to claim 11, wherein a scaling factor .sub.l for one of the sub-matrixes A.sub.l and a scaling factor .sub.m for one of the sub-vectors is selected such that $P {.Math._{l^{}}_{m^{}} e_{l^{} m^{}} .Math. > .Math. \underset{l l^{} .Math. m m^{}}{.Math.}_{l}_{m} w_{lm} .Math.} < .Math. l^{}, m^{}$ is satisfied, wherein: e.sub.lm is an error value defined as difference between an exact result vector element w.sub.lm of the product of one of the sub-matrices and one of the sub-vectors and an actually measured related value; P is the probability that the norm value of .sub.l.sub.me.sub.lm is larger than the norm value of the sum .sub.ll,mm.sub.l.sub.mw.sub.lm; and is a predefined probability tolerance value.

19. The method according to claim 11, wherein a scaling factor .sub.l for one of the sub-matrixes A.sub.l and a scaling factor .sub.m for one of the sub-vectors is selected such that $P {.Math. \underset{l .Math. m}{.Math.}_{l}_{m} e_{lm} .Math. > .Math._{l^{}}_{m^{}} w_{l^{} m^{}} .Math.} < .Math. l^{}, m^{}$ is satisfied, wherein: e.sub.lm is an error value defined as difference between an exact result vector element w.sub.lm of the product of one of the sub-matrices and one of the sub-vectors and an actually measured related product value; P is the probability that the norm value of the sum .sub.l,m.sub.l.sub.me.sub.lm is larger than the norm value .sub.l.sub.mw.sub.lm; and is a predefined probability tolerance value.

20. A computer implemented method for a matrix-vector-multiplication by a memristive crossbar array comprising a plurality of memristive devices, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions being executable by a computer system to cause the computer systems to: program the plurality of the memristive devices with values representing elements of a sub-matrices such that each one of the memristive devices corresponds to one of the elements of the sub-matrices; apply elements of one of the multiple sub-vectors as input values to the memristive crossbar array to input lines of the memristive crossbar array resulting in partial results at output lines of the memristive crossbar array; and scale and sum the partial results building the product of the matrix and the vector.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) It should be noted that embodiments of the disclosure are described with reference to different subject-matters. In particular, some embodiments are described with reference to method type claims, whereas other embodiments have been described with reference to apparatus type claims. However, a person skilled in the art will gather from the above and the following description that, unless otherwise notified, in addition to any combination of features belonging to one type of subject-matter, also any combination between features relating to different subject-matters, in particular, between features of the method type claims, and features of the apparatus type claims, is considered as to be disclosed within this document.

(2) The aspects defined above, and further aspects of the present disclosure are apparent from the examples of embodiments to be described hereinafter and are explained with reference to the examples of embodiments, but to which the disclosure is not limited.

(3) Preferred embodiments of the disclosure will now be described, by way of example only, and with reference to the following drawings:

(4) FIG. 1 shows a block diagram of an embodiment of the inventive multiplication device for performing a matrix-vector-multiplication.

(5) FIG. 2 shows a diagram how a matrix-vector-multiplication may be mapped to a crossbar of memristive devices according to embodiments.

(6) FIG. 3 shows a diagram of a way for decomposing the matrix A and the vector v according to embodiments.

(7) FIG. 4 shows a block diagram of an embodiment of the inventive method for performing a matrix-vector-multiplication according to embodiments.

(8) FIG. 5 shows an embodiment of a computing system comprising the multiplication device according to embodiments.

DETAILED DESCRIPTION

(9) In the context of this description, the following conventions, terms and/or expressions may be used:

(10) The term matrix-vector-multiplication may denote a multiplication of a matrix of the disclosure N*M with a vector of dimension N resulting in a vector of dimension M using known mathematical principles. In special caseswhich are favored as part of this documentthe dimension of the matrix may be N*N.

(11) The term memristive deviceswhich is a portmanteau of memory resistormay denote a hypothetical non-linear passive two-terminal electrical component relating to electric charge and magnetic flux linkage. According to the characterizing mathematical relations, the memristor would hypothetically operate in the following way: The memristor's electrical resistance is not constant but depends on the history of current that had previously flowed through the device, i.e., its present resistance depends on how much electric charge has flowed in what direction through it in the past; the device remembers its historythe so-called non-volatility property. When the electric power supply is turned off, the memristor remembers its most recent resistance until it is turned on again.

(12) The term memristive crossbar array may denote an array with crossed non-connected lines in an x-direction and a y-direction. At every cross point of the crossbar array, a memristive device is connected between an x-line and a crossing y-line.

(13) The term decomposing a matrix into a partial sum may denote the process of expressing a matrix as a sum of sub-matrices. Each sub-matrix may be multiplied with a scaling factor. Diverse mathematical decomposition methods are known. If in the context of this document the term sub-matrices may be used, one should keep in mind that the sub-matrix is one of a group of sub-matrices derived from a source matrix.

(14) The term integrated analogue/digital on-chip circuitry may denote a converter for translating an analog signal into a digital signal. A variety of such translation techniques is known. The ADC may be implemented as a component of a larger chip or as a separate device. This device may be integrated with other chips in the same package.

(15) The term plurality of independent sub-crossbar arrays may denote a group of memristive crossbar arrays which may each be a component of a larger crossbar array of memristive devices. The memristive devices between the individual sub-crossbar arrays are not overlapping.

(16) In the following, a detailed description of the figures will be given. All instructions in the figures are schematic. Firstly, a block diagram of an embodiment of the inventive multiplication device for performing a matrix-vector-multiplication is given. Afterwards, further embodiments, as well as embodiments of the method for performing a matrix-vector-multiplication, will be described.

(17) FIG. 1 shows a block diagram of an embodiment of the inventive multiplication device 100 for performing a matrix-vector-multiplication according to embodiments. The multiplication device 100 comprises a memristive crossbar array 102 comprising a plurality of memristive devices. All of the memristive devices may be integrated together with related control circuitry, buffers and read-out logic on one chip. Alternatively, individual sub-chips may be integrated in one package.

(18) The multiplication device comprises a decomposition unit 104 adapted for decomposing a matrix into a partial sum of multiple sub-matrices and decomposing a vector into a sum of multiple sub-vectors. The controller may be outside the chip of crossbar array or integrated together with it.

(19) A programming unit 106 is adapted for programming the plurality of the memristive devices with valuese.g. conductance valuesrepresenting (e.g., proportional or otherwise dependent) elements of the sub-matrices such that each one of the memristive devices corresponds to one of the elements of the sub-matrices. In a first embodiment, the sub-matrices and sub-vectors may be processed one after the other; alternatively, they may be processed in parallel. For this, the crossbar array may be sub-divided into logical sub-arrays.

(20) An applying unit 108 is adapted for applying elements of one of the multiple sub-vectors as input values to the memristive crossbar array to input lines of the memristive crossbar array resulting in partial results at output lines of the memristive crossbar array. Controller circuits may enable a proper and secure function of the multiplication process.

(21) A summing unit 110 is adapted for scaling and summing the partial results building the product of the matrix and the vector. Thus, the sum of the partial results of the products of the matrix-vector-multiplication of the sub-matrices with the sub-vectors represents the result of the original matrix with the original vector at a significantly higher precision if compared to a simple matrix-vector-multiplication of the original matrix with the original vector using a straight memristive crossbar array.

(22) FIG. 2 shows a diagram 200 how a matrix-vector-multiplication 202 may be mapped to a crossbar 204 of memristive devices according to embodiments. The formula 208 (Ohm's law) i=U*v, wherein i=current, U=conductance and v=voltage, together with Kirchhoff's laws build the basis of the core concept. For demonstration purposes, a 33 matrix is used here. However, any other dimension is as good as they here used example. The matrix elements A.sub.11 to A.sub.33 are mapped to the conductance values of the memristive devices as shown in 204. The vector component values v.sup.k.sub.1 to v.sup.k.sub.3 are used as input values for the memristive crossbar devices whereas the w.sup.k.sub.1 to w.sup.k.sub.3 values are the elements of the vector result of the performed multiplication.

(23) The device 206 shows an amorphous and a crystalline area between a top and a bottom electrode of a memristive device. Depending on the mixture of the amorphous (lower half-sphere) and a crystalline area (atop and surrounding the half-sphere), the conductance of the device is changed. Ohm's law is shown by reference numeral 208 using the conductance instead of the potentially better known version using the resistance (U=R*I). The required read power (or required energy) of such devices can be as low as 1 to 100 fJ per device. It may perform multiplication several times given the almost unlimited read endurance. Additionally, the read-time is pretty fast, e.g., in the range of about 100 ns which means that a complete matrix-vector-multiplication may be performed in only 100 ns. Hence, no additional serialized multiplication and edition operations are required. The multiplication is basically executed instantly.

(24) From a speed and power consumption perspective, this approach is already quite clever. However, in practical applications, the precision of the conductance programmed into the memristive devices in the crossbar and the limited dynamic range of the memristive devices limit the practical usability.

(25) Therefore, the problem to solve the equation
w=A*v,
wherein A is a matrix, w and v are vectors, is solved by decomposing the matrix A and the vector v as shown in FIG. 3, diagram 300.

(26) The matrix A is decomposed into the matrices A.sub.1, A.sub.2, . . . A.sub.L. The same may apply to the vector v which may be decomposed into the vectors v.sub.1, v.sub.2, . . . v.sub.M. As result, the vector w may then be given by the sum shown in box 304 using scaling factors .sub.1, .sub.2, . . . .sub.L and .sub.1, .sub.2, . . . , .sub.M, compare 302. With this, a higher precision and a higher dynamic range may be achieved. Additionally, several embodiments as to how the memristive array decomposition has to be done may be implemented.

(27) In other words: besides device-level improvements, the here proposed way to improve the precision is to encode single elements of the matrix A on multiple devices. The vector v can also be decomposed and applies as multiple sequential read voltages. In general, one can write
A=.sub.1A.sub.1+.sub.2A.sub.2+.sub.3A.sub.3+ . . . +.sub.LA.sub.L
V=.sub.1v.sub.1+.sub.2v.sub.2+.sub.3v.sub.3+ . . . .sub.Mv.sub.M.

(28) Here, .sub.l and .sub.l are scaling factors and A.sub.l and v.sub.m encode different levels of information of A and v. The matrix-vector-product w=Av is then calculated as
w=.sub.1.sub.1w.sub.11+.sub.2.sub.1w.sub.21+.sub.1.sub.2w.sub.12+ . . . =.sub.l,m(.sub.l.sub.mw.sub.lm)
w.sub.lm=A.sub.lv.sub.m.

(29) A preferred embodiment, the scaling factors .sub.l and .sub.m should not lead to additional multiplication operations. In floating-point arithmetic, .sub.l and .sub.m can be implemented by changing only the exponent. In fixed-point environment, .sub.l and .sub.m can be implemented as bit-shifts for improved efficiency.

(30) Thus, the new memristive crossbar array architectureinstead of a single A matrixcodes A.sub.l on multiple (L) crossbar arrays. The L arrays can only be sub-arrays of a larger array which and are physically located on the same (larger) array. The elements of A.sub.l are coded or programmed (as conductance values) on individual devices on multiple devices averaged.

(31) Instead of a single read voltage vector, multiple read voltage vectors are applied sequentially in time. The voltages v.sub.m can be implied as M consecutive reads on all arrays. Only a re-scaling by .sub.l and .sub.m and summing the partial results would be done in software of with some dedicated circuitry (mainly one or more analogue/digital converters).

(32) In the following, two examples of mappings may be given:

Example 1

(33) For improving the dynamic range, one can choosefor a first decomposition.sub.l=a.sup.l and .sub.m=b.sup.m. , a, and b can be either in decimal basis (powers of 10) or binary (powers of 2).

(34) An example in decimal basis could be ==10, a=b=10.sup.1 and
A=A.sub.1+10.sup.1A.sub.2+10.sup.2A.sub.3+ . . . +10.sup.L+1A.sub.L
v=v.sub.1+10.sup.1v.sub.2+10.sup.2v.sub.3+ . . . +10.sup.M+1v.sub.M
A.sub.1 contains the elements of A that are in [0.1,1[, A.sub.2 the elements of A that are in [0.01,0.1[(multiplied by 10), etc. The same may apply for v.sub.1, v.sub.2, etc.

(35) The elements of A.sub.l and v.sub.m are bounded in [0.1,1[, Assuming that A and v are normalized such that none of their elements are larger than 1, the above gives a complete representation of A and v for certain values of L and M.

(36) A concrete example in binary basis could be ==2.sup.4, a=b==2.sup.4 and

(37) $A = A_{1} + 2^{- 4} A_{2} + 2^{- 8} A_{3} + .Math. + 2^{- 4 (L - 1)} A_{L}$ $v = v_{1} + 2^{- 4} v_{2} + 2^{- 8} v_{3} + .Math. + 2^{- 4 (M - 1)} v_{M}$

(38) A.sub.1 contains the elements of A that are in [2.sup.4,1[, A.sub.2 the elements of A that are in [2.sup.8, 2.sup.4[(multiplied by 2.sup.4), etc. The same applies to v.sub.1, v.sub.2, etc. It may be noted that if the computation of w is done in binary floating point arithmetic, no additional multiplications are introduced by the scaling factors .sub.l and .sub.m. Indeed, numbers in binary floating point are represented as s/2.sup.p-12.sup.e, thus .sub.l and .sub.m are implemented only by changing the exponent e.

(39) As explicit matrices one gets:

(40) $A = [\begin{matrix} 0.9 & 0.03 & 0.6 \\ 0.0004 & 0.12 & 0.02 \\ 0.007 & 0.054 & 0.35 \end{matrix}]$
and thus

(41) $A = [\begin{matrix} 0.9 & 0 & 0.6 \\ 0 & 0.12 & 0 \\ 0 & 0 & 0.35 \end{matrix}] + 10^{- 1} [\begin{matrix} 0 & 0.3 & 0 \\ 0 & 0 & 0.2 \\ 0 & 0.54 & 0 \end{matrix}] + 10^{- 2} [\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0.7 & 0 & 0 \end{matrix}] + 10^{- 3} [\begin{matrix} 0 & 0 & 0 \\ 0.4 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}]$

(42) In this decomposition (last equation), the first matrix is A.sub.1, the second matrix is A.sub.2, the third matrix is A.sub.3 and the fourth matrix is A.sub.4.

(43) In this example, only a limited dynamic range is needed to code both the conductance values (A.sub.l) and voltage values (v.sub.m) because they are bounded. This method effectively allows to code matrices A and vectors v having unlimited dynamic range. However, the elements of A.sub.l and v.sub.m have an unlimited number of digits. In practice, it is likely that the numbers beyond the first digit (in decimal basis) will be lost due to noise or other sources of inaccuracy.

(44) In order to address this potential issue, a second example for improving both, the dynamic range and the precision of the matrix-vector-multiplication, is given:

(45) Firstly, selected digits of A and v are coded into A.sub.l and v.sub.m. E.g., using the first example above, but coding only the l-th digit of A in A.sub.l, results in

(46) $A = [\begin{matrix} 0.9 & 0.03 & 0.6 \\ 0.0004 & 0.12 & 0.02 \\ 0.007 & 0.054 & 0.35 \end{matrix}]$
and thus,

(47) $A = [\begin{matrix} 0.9 & 0 & 0.6 \\ 0 & 0.1 & 0 \\ 0 & 0 & 0.3 \end{matrix}] + 10^{- 1} [\begin{matrix} 0 & 0.3 & 0 \\ 0 & 0.2 & 0.2 \\ 0 & 0.5 & 0.5 \end{matrix}] + 10^{- 2} [\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0.7 & 0.4 & 0 \end{matrix}] + 10^{- 3} [\begin{matrix} 0 & 0 & 0 \\ 0.4 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}]$

(48) Again, in this decomposition (last equation), the first matrix is A.sub.1, the second matrix is A.sub.2, the third matrix is A.sub.3 and the fourth matrix is A.sub.4.

(49) The same can be done for the vector v. This way, we need only 1 digit of precision for each element of A.sub.l and v.sub.m.

(50) As a result: More than 1 digit can be coded in A.sub.l and v.sub.m if the hardware allows it.

(51) For example, one could have 0.3698=0.36+10.sup.20.98, e.g. two-digits precise coding. Here, 0.3698 is A. 0.36 is A.sub.1 0.98 is A.sub.2.

(52) The concept can be also applied to binary fixed-point representations in the same manner, i.e., 01101001=00000110<<4+00001001. Here, 01101001 is A, 0110 is A.sub.1 and 1001 is A.sub.2. The 4 most significant bits 0110 and the 4 least-significant bits 1001 can be coded separately. The left-shift<<4 represents the scaling factor ().

(53) All the above is applicable to v as well. Many more examples based on the same principles are possible.

(54) A third example can make this more transparent:

(55) One codes in A.sub.l and v.sub.m only relevant elements of A and v, as required for the specific problem to be solved (e.g. solving the linear equation). E.g., one can code only the elements of A above a certain threshold, and/or up to a certain digit in A.sub.l. One can code only a fixed number of elements per row/column of A (works for both, sparse and dense A). One can drop elements or digits of A depending on the resulting sparsity level of A.sub.l (i.e. drop A.sub.l is if A.sub.l is very sparse, for i=1, . . . , L).

(56) Some elements can be coded with more digits than others. Some parts of the matrix can also be coded less precisely than others (e.g. higher threshold for drop-off or/and less digits). Those parts could be for example selected based on physical principles that led to the matrix A, or based on the right-hand side b when solving the linear equation Ax=b.

(57) The splitting can be done based on the structure of A (e.g. code only a band around the main diagonal for diagonally-dominant matrices). All the above examples are applicable to v, as well.

(58) In a more concrete form, and based on the second example, code A as in Embodiment 2, but up to the second digit only.

(59) $A = [\begin{matrix} 0.9 & 0.03 & 0.6 \\ 0.0004 & 0.12 & 0.02 \\ 0.007 & 0.054 & 0.35 \end{matrix}]$
and hence

(60) $\tilde{A} = [\begin{matrix} 0.9 & 0 & 0.6 \\ 0 & 0.1 & 0 \\ 0 & 0 & 0.3 \end{matrix}] + 10^{- 1} [\begin{matrix} 0 & 0.3 & 0 \\ 0 & 0.2 & 0.2 \\ 0 & 0.5 & 0.5 \end{matrix}]$
wherein the first matrix is A.sub.1 and the second matrix is A.sub.2.

(61) The computation of w is then given by the summation
w=.sub.1.sub.1w.sub.11+.sub.2.sub.1w.sub.21+.sub.2w.sub.12+ . . . .

(62) It may be that some elements of this sum fall out of range of the arithmetic format used to calculate it (due to large differences across the scaling factors .sub.l and .sub.m, e.g. .sub.1 could be 1 whereas .sub.16 is 10.sup.16).

(63) To avoid those errors, compensated summation algorithms, such as those given in Sec. 4.3 of N. J. Higham, Accuracy and stability of numerical algorithms (Siam, 2002), can be used.

(64) FIG. 4 shows an embodiment of a formal flowchart of the inventive method 400 for performing a matrix-vector-multiplication according to embodiments. The method comprises providing, 402, a memristive crossbar array comprising a plurality of memristive devices, decomposing, 404, a matrix into a partial sum of multiple sub-matrices, and decomposing, 406, a vector into a sum of multiple sub-vectors.

(65) Additionally, the method comprises programming, 408, the plurality of the memristive devices with values representingin particular, being proportional toelements of the sub-matrices such that each one of the memristive devices corresponds to one of the elements of the sub-matrices, applying, 410, elements of one of the multiple sub-vectors as input values to the memristive crossbar array to input lines of the memristive crossbar array resulting in partial results at output lines of the memristive crossbar array, and scaling and summing412the partial results building the product of the matrix and the vector.

(66) Embodiments of the disclosure may be implemented together with virtually any type of computer, regardless of the platform being suitable for storing and/or executing program code. FIG. 5 shows, as an example, a computing system 500 suitable for executing program code related to the proposed method according to embodiments.

(67) The computing system 500 is only one example of a suitable computer system and is not intended to suggest any limitation as to the scope of use or functionality of embodiments of the disclosure described herein. Regardless, computer system 500 is capable of being implemented and/or performing any of the functionality set forth hereinabove. In the computer system 500, there are components, which are operational with numerous other general purpose or special purpose computing system environments or configurations. Examples of well-known computing systems, environments, and/or configurations that may be suitable for use with computer system/server 500 include, but are not limited to, personal computer systems, server computer systems, thin clients, thick clients, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputer systems, mainframe computer systems, and distributed cloud computing environments that include any of the above systems or devices, and the like. Computer system/server 500 may be described in the general context of computer system-executable instructions, such as program modules, being executed by a computer system 500. Generally, program modules may include routines, programs, objects, components, logic, data structures, and so on that perform particular tasks or implement particular abstract data types. Computer system/server 500 may be practiced in distributed cloud computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed cloud computing environment, program modules may be located in both local and remote computer system storage media including memory storage devices.

(68) As shown in the figure, computer system/server 500 is shown in the form of a general-purpose computing device. The components of computer system/server 500 may include, but are not limited to, one or more processors or processing units 502, a system memory 504, and a bus 506 that couples various system components including system memory 504 to the processor 502. Bus 506 represents one or more of any of several types of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnects (PCI) bus. Computer system/server 500 typically includes a variety of computer system readable media. Such media may be any available media that is accessible by computer system/server 500, and it includes both, volatile and non-volatile media, removable and non-removable media.

(69) The system memory 504 may include computer system readable media in the form of volatile memory, such as random access memory (RAM) 508 and/or cache memory 510. Computer system/server 500 may further include other removable/non-removable, volatile/non-volatile computer system storage media. By way of example only, storage system 512 may be provided for reading from and writing to a non-removable, non-volatile magnetic media (not shown and typically called a hard drive). Although not shown, a magnetic disk drive for reading from and writing to a removable, non-volatile magnetic disk (e.g., a floppy disk), and an optical disk drive for reading from or writing to a removable, non-volatile optical disk such as a CD-ROM, DVD-ROM or other optical media may be provided. In such instances, each can be connected to bus 506 by one or more data media interfaces. As will be further depicted and described below, memory 504 may include at least one program product having a set (e.g., at least one) of program modules that are configured to carry out the functions of embodiments of the disclosure.

(70) The program/utility, having a set (at least one) of program modules 516, may be stored in memory 504 by way of example, and not limitation, as well as an operating system, one or more application programs, other program modules, and program data. Each of the operating system, one or more application programs, other program modules, and program data or some combination thereof, may include an implementation of a networking environment. Program modules 516 generally carry out the functions and/or methodologies of embodiments of the disclosure as described herein.

(71) The computer system/server 500 may also communicate with one or more external devices 518 such as a keyboard, a pointing device, a display 520, etc.; one or more devices that enable a user to interact with computer system/server 500; and/or any devices (e.g., network card, modem, etc.) that enable computer system/server 500 to communicate with one or more other computing devices. Such communication can occur via Input/Output (I/O) interfaces 514. Still yet, computer system/server 500 may communicate with one or more networks such as a local area network (LAN), a general wide area network (WAN), and/or a public network (e.g., the Internet) via network adapter 522. As depicted, network adapter 522 may communicate with the other components of computer system/server 500 via bus 506. It should be understood that although not shown, other hardware and/or software components could be used in conjunction with computer system/server 500. Examples, include, but are not limited to: microcode, device drivers, redundant processing units, external disk drive arrays, RAID systems, tape drives, and data archival storage systems, etc.

(72) Additionally, the multiplication device 100 for performing a matrix-vector-multiplication can be attached to the bus system 506.

(73) The descriptions of the various embodiments of the present disclosure have been presented for purposes of illustration, but are not intended to be exhaustive or limited to the embodiments disclosed. Many modifications and variations will be apparent to those of ordinary skills in the art without departing from the scope and spirit of the described embodiments. The terminology used herein was chosen to best explain the principles of the embodiments, the practical application or technical improvement over technologies found in the marketplace, or to enable others of ordinary skills in the art to understand the embodiments disclosed herein.

(74) The present disclosure may be embodied as a system, a method, and/or a computer program product. The computer program product may include a computer readable storage medium (or media) having computer readable program instructions thereon for causing a processor to carry out aspects of the present disclosure.

(75) The medium may be an electronic, magnetic, optical, electromagnetic, infrared or a semi-conductor system for a propagation medium. Examples of a computer-readable medium may include a semi-conductor or solid state memory, magnetic tape, a removable computer diskette, a random access memory (RAM), a read-only memory (ROM), a rigid magnetic disk and an optical disk. Current examples of optical disks include compact disk-read only memory (CD-ROM), compact disk-read/write (CD-R/W), DVD and Blu-Ray-Disk.

(76) The computer readable storage medium can be a tangible device that can retain and store instructions for use by an instruction execution device. The computer readable storage medium may be, for example, but is not limited to, an electronic storage device, a magnetic storage device, an optical storage device, an electromagnetic storage device, a semiconductor storage device, or any suitable combination of the foregoing. A non-exhaustive list of more specific examples of the computer readable storage medium includes the following: a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), a static random access memory (SRAM), a portable compact disc read-only memory (CD-ROM), a digital versatile disk (DVD), a memory stick, a floppy disk, a mechanically encoded device such as punch-cards or raised structures in a groove having instructions recorded thereon, and any suitable combination of the foregoing. A computer readable storage medium, as used herein, is not to be construed as being transitory signals per se, such as radio waves or other freely propagating electromagnetic waves, electromagnetic waves propagating through a waveguide or other transmission media (e.g., light pulses passing through a fiber-optic cable), or electrical signals transmitted through a wire.

(77) Computer readable program instructions described herein can be downloaded to respective computing/processing devices from a computer readable storage medium or to an external computer or external storage device via a network, for example, the Internet, a local area network, a wide area network and/or a wireless network. The network may comprise copper transmission cables, optical transmission fibers, wireless transmission, routers, firewalls, switches, gateway computers and/or edge servers. A network adapter card or network interface in each computing/processing device receives computer readable program instructions from the network and forwards the computer readable program instructions for storage in a computer readable storage medium within the respective computing/processing device.

(78) Computer readable program instructions for carrying out operations of the present disclosure may be assembler instructions, instruction-set-architecture (ISA) instructions, machine instructions, machine dependent instructions, microcode, firmware instructions, state-setting data, or either source code or object code written in any combination of one or more programming languages, including an object-oriented programming language such as Smalltalk, C++ or the like, and conventional procedural programming languages, such as the C programming language or similar programming languages. The computer readable program instructions may execute entirely on the user's computer, partly on the user's computer as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider). In some embodiments, electronic circuitry including, for example, programmable logic circuitry, field-programmable gate arrays (FPGA), or programmable logic arrays (PLA) may execute the computer readable program instructions by utilizing state information of the computer readable program instructions to personalize the electronic circuitry, in order to perform aspects of the present disclosure.

(79) Aspects of the present disclosure are described herein with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the disclosure. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer readable program instructions.

(80) These computer readable program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. These computer readable program instructions may also be stored in a computer readable storage medium that can direct a computer, a programmable data processing apparatus', and/or other devices to function in a particular manner, such that the computer readable storage medium having instructions stored therein comprises an article of manufacture including instructions which implement aspects of the function/act specified in the flowchart and/or block diagram block or blocks.

(81) The computer readable program instructions may also be loaded onto a computer, other programmable data processing apparatus', or another device to cause a series of operational steps to be performed on the computer, other programmable apparatus or other device to produce a computer implemented process, such that the instructions which execute on the computer, other programmable apparatus', or another device implement the functions/acts specified in the flowchart and/or block diagram block or blocks.

(82) The flowcharts and/or block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods, and computer program products according to various embodiments of the present disclosure. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of instructions, which comprises one or more executable instructions for implementing the specified logical function(s). In some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or act or carry out combinations of special purpose hardware and computer instructions.

(83) The terminology used herein is for the purpose of describing particular embodiments only and is not intended to limit the disclosure. As used herein, the singular forms a, an and the are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will further be understood that the terms comprises and/or comprising, when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof.

(84) The corresponding structures, materials, acts, and equivalents of all means or steps plus function elements in the claims below are intended to include any structure, material, or act for performing the function in combination with other claimed elements, as specifically claimed. The description of the present disclosure has been presented for purposes of illustration and description, but is not intended to be exhaustive or limited to the disclosure in the form disclosed. Many modifications and variations will be apparent to those of ordinary skills in the art without departing from the scope and spirit of the disclosure. The embodiments are chosen and described in order to best explain the principles of the disclosure and the practical application, and to enable others of ordinary skills in the art to understand the disclosure for various embodiments with various modifications, as are suited to the particular use contemplated.

Higher accuracy of non-volatile memory-based vector multiplication

Assignee

Inventors

Cpc classification

Classification Explorer

G06F2207/4814

PHYSICS

Classification Explorer

G11C2213/77

PHYSICS

Classification Explorer

G11C13/0069

PHYSICS

Classification Explorer

G06F7/5443

PHYSICS

Classification Explorer

G06F2207/4828

PHYSICS

Classification Explorer

G06F17/16

PHYSICS

Classification Explorer

G11C13/003

PHYSICS

Classification Explorer

G11C13/0007

PHYSICS

Classification Explorer

G06F2207/4824

PHYSICS

Classification Explorer

G11C7/1006

PHYSICS

Classification Explorer

G06F7/523

PHYSICS

International classification

Classification Explorer

G06F17/16

PHYSICS

Classification Explorer

G06F7/523

PHYSICS

Classification Explorer

G11C7/10

PHYSICS

Classification Explorer

G06F7/544

PHYSICS

Classification Explorer

G11C13/00

PHYSICS

Abstract

Claims

Description