System to perform horizontal additions
Summary by NHIP
Horizontal Addition Processor System
The system executes instructions to add paired data elements from two source operands and store the resulting sums in a destination operand. The processor accesses a first source operand containing N data elements and a second source operand containing N data elements to generate the output.
Claim Score by NHIP
Abstract
A method and apparatus for including in a processor instructions for performing intra-add operations on packed data. In one embodiment, a processor is coupled to a memory. The memory has stored therein a first packed data. The processor performs operations on data elements in the first packed data to generate a plurality of data elements in a second packed data in response to receiving an instruction. At least two of the plurality of data elements in the second packed data store the result of an intra-add operation on data elements in the first packed data.
Term
Term ended
Expired 31 March 2018, 8.5 years ago.
- Priority
- Filed
- Granted
- Expired
- Today
50 claims: 7 independent, 43 dependent
- 1Broadest claimClaim Score 44, average(NHIP)A system comprising:a storage device to store an executable code;a processor coupled with the storage device to execute said executable code, being responsive to said executable code comprising a first instruction specifying a first source operand having a first plurality of N data elements and a second source operand having a second plurality of N data elements, said processor: to access the first source operand to add at least a first pair of elements of the first plurality of N data elements producing a first sum, to access the second source operand to add at least a second pair of elements of the second plurality of N data elements producing a second sum, and to access a destination operand to store a third plurality of N data elements comprising the first sum and the second sum.
- 5An animation graphics system comprising:a storage device to store an executable code;a processor coupled with the storage device to generate transformed graphical objects responsive at least in part to executing said executable code, being responsive to said executable code comprising a first instruction specifying a first source operand having a first plurality of N data elements and a second source operand having a second plurality of N data elements, said processor: to access the first source operand to add at least a first pair of elements of the first plurality of N data elements producing a first sum, to access the second source operand to add at least a second pair of elements of the second plurality of N data elements producing a second sum, to access a destination operand to store a third plurality of N data elements comprising the first sum and the second sum;and a display device coupled with the processor to store transformed graphical objects for animation graphics responsive at least in part to the processor executing said executable code.
- 15A still image processing system comprising:a storage device to store an executable code;a processor coupled with the storage device to generate graphical objects responsive at least in part to executing said executable code, being responsive to said executable code comprising a first instruction specifying a first source operand having a first plurality of N data elements and a second source operand having a second plurality of N data elements, said processor: to access the first source operand to add at least a first pair of elements of the first plurality of N data elements producing a first sum, to access the second source operand to add at least a second pair of elements of the second plurality of N data elements producing a second sum, to access a destination operand to store a third plurality of N data elements comprising the first sum and the second sum;and a hard copy device coupled with the processor to print graphical objects of still images responsive at least in pail to the processor executing said executable code.
- 27A digital motion video system comprising:a storage device to store an executable code;a processor coupled with the storage device to process digital motion video data elements responsive at least in part to executing said executable code, being responsive to said executable code comprising a first instruction specifying a first source operand having a first plurality of N data elements and a second source operand having a second plurality of N data elements, said processor: to access the first source operand to add at least a first pair of elements of the first plurality of N data elements producing a first sum, to access the second source operand to add at least a second pair of elements of the second plurality of N data elements producing a second sum, to access a destination operand to score a third plurality of N data elements comprising the first sum and the second sum;and a video digitizing device coupled with the processor to transfer digital motion video data elements responsive at least in part to the processor executing said executable code.
- 39A graphical workstation system comprising:a storage device to store an executable code;a processor coupled with the storage device to transform a graphical object at least in part by executing said executable code, being responsive to said executable code comprising a first instruction specifying a first source operand having a first plurality of N data elements and a second source operand having a second plurality of N data elements, said processor: to access the first source operand to add at least a first pair of elements of the first plurality of N data elements producing a first sum, to access the second source operand to add at least a second pair of elements of the second plurality of N data elements producing a second sum, to access a destination operand to store a third plurality of N data elements comprising the first sum and the second sum;and a cursor control coupled with the processor, the processor responsive at least in part to said cursor control and said executable code to transform a graphical object.
- 40A transformation system comprising:a storage medium to store a digital graphics data;a machine-accessible medium having an executable code;a conversion unit to access the machine-accessible medium and responsive at least in part to said executable code comprising a first instruction, the first instruction specifying a first operand and a second operand, to: multiply each data element of a first row of a matrix source to each respective data element of a vector source to generate a first plurality of N data elements of the first operand, multiply each data element of a second row of the matrix source to each respective data element of the vector source to generate a second plurality of N data elements of the second operand, add at least a first pair of elements of the first plurality of N data elements to generate a first data element of a packed result responsive to said first instruction, and add at least a second pair of elements of the second plurality of N data elements to generate a second data element of the packed result responsive to said first instruction.
- 45A computer system comprising:a first machine-accessible medium having stored thereon a first plurality of control signals and when accessed by a machine, causing said machine to access a first control signal specifying a first source operand having a first plurality of data elements and a second source operand having a second plurality of data elements and to generate one or more control signals to enable a horizontal addition operation;a second machine-accessible medium to store a second plurality of control signals to enable operations of a packed instruction set including said one or more control signals to enable a horizontal addition operation;at least one execution unit to access said one or more control signals to enable a horizontal addition operation of the second machine-accessible medium causing said at least one execution unit to: add at least a first pair of elements of the first plurality of data elements to generate a first sum element of a first packed result, and add at least a second pair of elements of the second plurality of data elements to generate a second sum element of the first packed result.
Independent claims7
61 paragraphs in 5 sections, as filed
0001This application is a continuation and claims the benefit of application Ser. No. 09/053,401, filed Mar. 31, 1998, now U.S. Pat. No. 6,418,529.
BACKGROUND OF THE INVENTION
00021. Field of the Invention
0003The present invention relates in general to the field of computer systems, and in particular, to an apparatus and method for performing multi-dimensional computations based on an intra-add operation.
00042. Description of the Related Art
0005To improve the efficiency of multimedia applications, as well as other applications with similar characteristics, a Single Instruction, Multiple Data (SIMD) architecture has been implemented in computer systems to enable one instruction to operate on several operands simultaneously, rather than on a single operand. In particular, SIMD architectures take advantage of packing many data elements within one register or memory location. With parallel hardware execution, multiple operations can be performed on separate data elements with one instruction, resulting in significant performance improvement.
0006Currently, the SIMD addition operation only performs “vertical” or inter-register addition, where pairs of data elements, for example, a first element Xn (where n is an integer) from one operand, and a second element Yn from a second operand, are added together. An example of such a vertical addition operation is shown in <figref idref="DRAWINGS">FIG. 1</figref>, where the instruction is performed on the sets of data elements (X<sub>3</sub>, X<sub>2</sub>, X<sub>1 </sub>and X<sub>0</sub>) and (Y<sub>3</sub>, Y<sub>2</sub>, Y<sub>1</sub>, and Y<sub>0</sub>) accessed as Source<b>1</b> and Source<b>2</b>, respectively to obtain the result (X<sub>3</sub>+Y<sub>3</sub>, X<sub>2</sub>+Y<sub>2</sub>, X<sub>1</sub>+Y<sub>1</sub>, and X<sub>0</sub>+Y<sub>0</sub>).
0007Although many applications currently in use can take advantage of such a vertical add operation, there are a number of important applications which would require the rearrangement of the data elements before the vertical add operation can be implemented so as to provide realization of the application.
0008For example, a matrix multiplication operation is shown below. <maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mrow><mrow><mi>MATRIX</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>A</mi><mo>*</mo><mi>VECTOR</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>X</mi></mrow><mo>=</mo><mrow><mi>VECTOR</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>Y</mi></mrow></mrow></math></maths><maths id="MATH-US-00001-2" num="00001.2"><math overflow="scroll"><mrow><mrow><mrow><mo></mo><mtable><mtr><mtd><msub><mi>A</mi><mn>14</mn></msub></mtd><mtd><msub><mi>A</mi><mn>13</mn></msub></mtd><mtd><msub><mi>A</mi><mn>12</mn></msub></mtd><mtd><msub><mi>A</mi><mn>11</mn></msub></mtd></mtr><mtr><mtd><msub><mi>A</mi><mn>24</mn></msub></mtd><mtd><msub><mi>A</mi><mn>23</mn></msub></mtd><mtd><msub><mi>A</mi><mn>22</mn></msub></mtd><mtd><msub><mi>A</mi><mn>21</mn></msub></mtd></mtr><mtr><mtd><msub><mi>A</mi><mn>34</mn></msub></mtd><mtd><msub><mi>A</mi><mn>33</mn></msub></mtd><mtd><msub><mi>A</mi><mn>32</mn></msub></mtd><mtd><msub><mi>A</mi><mn>31</mn></msub></mtd></mtr><mtr><mtd><msub><mi>A</mi><mn>44</mn></msub></mtd><mtd><msub><mi>A</mi><mn>43</mn></msub></mtd><mtd><msub><mi>A</mi><mn>42</mn></msub></mtd><mtd><msub><mi>A</mi><mn>41</mn></msub></mtd></mtr></mtable><mo></mo></mrow><mo></mo><mi>∞</mi><mo></mo><mrow><mo></mo><mtable><mtr><mtd><msub><mi>X</mi><mn>4</mn></msub></mtd></mtr><mtr><mtd><msub><mi>X</mi><mn>3</mn></msub></mtd></mtr><mtr><mtd><msub><mi>X</mi><mn>2</mn></msub></mtd></mtr><mtr><mtd><msub><mi>X</mi><mn>1</mn></msub></mtd></mtr></mtable><mo></mo></mrow></mrow><mo>=</mo><mrow><mo></mo><mtable><mtr><mtd><mrow><mrow><msub><mi>A</mi><mn>14</mn></msub><mo></mo><msub><mi>X</mi><mn>4</mn></msub></mrow><mo>+</mo><mrow><msub><mi>A</mi><mn>13</mn></msub><mo></mo><msub><mi>X</mi><mn>3</mn></msub></mrow><mo>+</mo><mrow><msub><mi>A</mi><mn>12</mn></msub><mo></mo><msub><mi>X</mi><mn>2</mn></msub></mrow><mo>+</mo><mrow><msub><mi>A</mi><mn>11</mn></msub><mo></mo><msub><mi>X</mi><mn>1</mn></msub></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mrow><msub><mi>A</mi><mn>24</mn></msub><mo></mo><msub><mi>X</mi><mn>4</mn></msub></mrow><mo>+</mo><mrow><msub><mi>A</mi><mn>23</mn></msub><mo></mo><msub><mi>X</mi><mn>3</mn></msub></mrow><mo>+</mo><mrow><msub><mi>A</mi><mn>22</mn></msub><mo></mo><msub><mi>X</mi><mn>2</mn></msub></mrow><mo>+</mo><mrow><msub><mi>A</mi><mn>21</mn></msub><mo></mo><msub><mi>X</mi><mn>1</mn></msub></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mrow><msub><mi>A</mi><mn>34</mn></msub><mo></mo><msub><mi>X</mi><mn>4</mn></msub></mrow><mo>+</mo><mrow><msub><mi>A</mi><mn>33</mn></msub><mo></mo><msub><mi>X</mi><mn>3</mn></msub></mrow><mo>+</mo><mrow><msub><mi>A</mi><mn>32</mn></msub><mo></mo><msub><mi>X</mi><mn>2</mn></msub></mrow><mo>+</mo><mrow><msub><mi>A</mi><mn>31</mn></msub><mo></mo><msub><mi>X</mi><mn>1</mn></msub></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mrow><msub><mi>A</mi><mn>44</mn></msub><mo></mo><msub><mi>X</mi><mn>4</mn></msub></mrow><mo>+</mo><mrow><msub><mi>A</mi><mn>43</mn></msub><mo></mo><msub><mi>X</mi><mn>3</mn></msub></mrow><mo>+</mo><mrow><msub><mi>A</mi><mn>42</mn></msub><mo></mo><msub><mi>X</mi><mn>2</mn></msub></mrow><mo>+</mo><mrow><msub><mi>A</mi><mn>41</mn></msub><mo></mo><msub><mi>X</mi><mn>1</mn></msub></mrow></mrow></mtd></mtr></mtable><mo></mo></mrow></mrow></math></maths>
0009To obtain the product of the matrix A with a vector X to obtain the resulting vector Y, instructions are used to: 1) store the columns of the matrix A as packed operands (this typically requires rearrangement of data because the rows of the matrix A coefficients are stored to be accessed as packed data operands, not the columns); 2) store a set of operands that each have a different one of the vector X coefficients in every data element; 3) use vertical multiplication where each data element in the vector X (i.e., X<sub>4</sub>, X<sub>3</sub>, X<sub>2</sub>, X<sub>1</sub>) has to be first multiplied with data elements in each column (for example, [A<sub>14</sub>, A<sub>24</sub>, A<sub>34</sub>, A<sub>44</sub>]) of the matrix A. The results of the multiplication operations are then added together through three vertical add operations such as that shown in <figref idref="DRAWINGS">FIG. 1</figref>, to obtain the final result. Such a matrix multiplication operation based on the use of vertical add operations typically requires 20 instructions to implement, an example of which is shown below in Table 1.
0000Exemplary Code Based on Vertical-Add Operations:
0010<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0" pgwide="1"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="280pt" align="left" /><thead><row><entry namest="1" nameend="1" rowsep="1">TABLE 1</entry></row><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row><row><entry>Assumptions:</entry></row><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>1/X stored with X1 first, X4 last</entry></row><row><entry>2/transposed of A sotred with A11 first, A21 second, A31 third, etc.</entry></row><row><entry>3/availability of:</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="266pt" align="left" /><tbody valign="top"><row><entry /><entry>-DUPLS: duplicate once</entry></row><row><entry /><entry>-DUPLD: duplicate twice</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="140pt" align="left" /><colspec colname="2" colwidth="140pt" align="left" /><tbody valign="top"><row><entry>MOVD mm0, <mem_X></entry><entry>// [0, 0, 0, X1]</entry></row><row><entry>DUPLS mm0, mm0</entry><entry>// [0, 0, X1, X1]</entry></row><row><entry>DUPLD mm0, mm0</entry><entry>// [X1, X1, X1, X1]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="112pt" align="left" /><colspec colname="2" colwidth="140pt" align="left" /><tbody valign="top"><row><entry /><entry>PFMUL mm0, <mem_A></entry><entry>// [A41*X1, A31*X1, A21*X1, A11*X1]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="140pt" align="left" /><colspec colname="2" colwidth="140pt" align="left" /><tbody valign="top"><row><entry>MOVD mm1, <mem_X + 4></entry><entry>// [0, 0, 0, X2]</entry></row><row><entry>DUPLS mm1, mm1</entry><entry>// [0, 0, X2, X2]</entry></row><row><entry>DUPLD mm1, mm1</entry><entry>// [X2, X2, X2, X2]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="112pt" align="left" /><colspec colname="2" colwidth="140pt" align="left" /><tbody valign="top"><row><entry /><entry>PFMUL mm1, <mem_A + 16></entry><entry>// [A42*X2, A32*X2, A22*X2, A12*X2]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="140pt" align="left" /><colspec colname="2" colwidth="140pt" align="left" /><tbody valign="top"><row><entry>MOVD mm2, <mem_X + 8></entry><entry>// [0, 0, 0, X3]</entry></row><row><entry>DUPLS mm2, mm2</entry><entry>// [0, 0, X3, X3]</entry></row><row><entry>DUPLD mm2, mm2</entry><entry>// [X3, X3, X3, X3]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="112pt" align="left" /><colspec colname="2" colwidth="140pt" align="left" /><tbody valign="top"><row><entry /><entry>PFUML mm2, <mem_A + 32></entry><entry>// [A43*X3, A33*X3, A23*X3, A13*X3]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="140pt" align="left" /><colspec colname="2" colwidth="140pt" align="left" /><tbody valign="top"><row><entry>MOVD mm3, <mem_X + 12></entry><entry>// [0, 0, 0, X4]</entry></row><row><entry>DUPLS mm3, mm3</entry><entry>// [0, 0, X4, X4]</entry></row><row><entry>DUPLD mm3, mm3</entry><entry>// [X4, X4, X4, X4]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="112pt" align="left" /><colspec colname="2" colwidth="140pt" align="left" /><tbody valign="top"><row><entry /><entry>PFMUL mm3, <mem_A + 48></entry><entry>// [A44*X4, A34*X4, A24*X4, A14*X4]</entry></row><row><entry /><entry>PFADD mm0, mm1</entry><entry>// [A42*X2 + A41*X1, A32*X2 + A31*X1,</entry></row><row><entry /><entry /><entry>// A22*X2 + A21*X1, A12*X2 + A11*X1]</entry></row><row><entry /><entry>PFADD mm2, mm3</entry><entry>// [A44*X4 + A43*X3, A34*X4 + A33*X3,</entry></row><row><entry /><entry /><entry>// A24*X4 + A23*X3, A14*X4 + A13*X3]</entry></row><row><entry /><entry>PFADD mm0, mm2</entry><entry>// [A44*X4 + A43*X3 + A42*X2 + A41*X1,</entry></row><row><entry /><entry /><entry>// A34*X4 + A33*X3 + A32*X2 + A31*X1,</entry></row><row><entry /><entry /><entry>// A24*X4 + A23*X3 + A22*X2 + A21*X1,</entry></row><row><entry /><entry /><entry>// A14*X4 + A13*X2 + A12*X2 + A11*X1]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="140pt" align="left" /><colspec colname="2" colwidth="140pt" align="left" /><tbody valign="top"><row><entry>MOVDQ <mem_Y>, mm0</entry><entry>// store [Y4, Y3, Y2, Y1]</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>
0011Accordingly, there is a need in the technology for providing an apparatus and method which efficiently performs multi-dimensional computations based on a “horizontal” or intra-add operation. There is also a need in the technology for a method and operation for increasing code density by eliminating the need for the rearrangement of data elements and the corresponding rearrangement operations.
BRIEF SUMMARY OF THE INVENTION
0012A method and apparatus for including in a processor instructions for performing intra-add operations on packed data is described. In one embodiment, a processor is coupled to a memory. The memory has stored therein a first packed data. The processor performs operations on data elements in the first packed data to generate a plurality of data elements in a second packed data in response to receiving an instruction. At least two of the plurality of data elements in the second packed data store the result of an intra-add operation on data elements in the first packed data.
BRIEF DESCRIPTION OF THE DRAWINGS
0013The invention is illustrated by way of example, and not limitation, in the figures. Like reference indicate similar elements.
0014<figref idref="DRAWINGS">FIG. 1</figref> illustrates the vertical or inter-add operation of the prior art.
0015<figref idref="DRAWINGS">FIG. 2</figref> illustrates the horizontal or intra-add operation in accordance with one embodiment of the present invention.
0016<figref idref="DRAWINGS">FIGS. 3A-3C</figref> illustrate matrix multiplication based on horizontal or intra-add operations in accordance with one embodiment of the present invention.
0017<figref idref="DRAWINGS">FIGS. 4A-4G</figref> illustrate matrix multiplication based on horizontal or intra-add operations in accordance with another embodiment of the present invention.
0018<figref idref="DRAWINGS">FIG. 5</figref> illustrates an exemplary computer system in accordance with one embodiment of the invention.
0019<figref idref="DRAWINGS">FIG. 6</figref> illustrates packed data-types in accordance with one embodiment of the invention.
0020<figref idref="DRAWINGS">FIG. 7</figref> illustrates one embodiment of a floating point packed data format.
0021<figref idref="DRAWINGS">FIG. 8</figref> is a flow diagram illustrating a method for performing the intra-add operation of <figref idref="DRAWINGS">FIG. 2</figref> in accordance with one embodiment of the invention.
0022<figref idref="DRAWINGS">FIG. 9</figref> illustrates a circuit for performing the intra-add operation of <figref idref="DRAWINGS">FIG. 2</figref> in accordance with one embodiment of the invention.
0023<figref idref="DRAWINGS">FIG. 10</figref> is a general block diagram illustrating the use of matrix multiplication based on horizontal or inter-add operations, in rendering graphical objects in animation.
DETAILED DESCRIPTION OF THE INVENTION
0024In the following description, numerous specific details are set forth to provide a thorough understanding of the invention. However, it is understood that the invention may be practiced without these specific details. In other instances, well-known circuits, structures and techniques have not been shown in detail in order not to obscure the invention.
Overview
0025One aspect of the present invention is a processor including instructions for performing horizontal or intra-addition operations on packed data. In one embodiment, two pairs of data elements (e.g., X<sub>3 </sub>and X<sub>2</sub>, and X<sub>1 </sub>and X<sub>0</sub>) located within a single storage area (e.g., Source<b>1</b>) are added together using a horizontal or a intra-add operation. In an alternate embodiment, data elements from each of two storage areas (e.g., Source<b>1</b> and Source<b>2</b>) are added and stored as data elements of a resulting packed data, as shown in FIG. <b>2</b>.
0026Another aspect of the present invention involves a method and apparatus for performing matrix multiplication using a horizontal or intra-addition operation. In one embodiment, each 32-bit data element from a 1×2 vector is multiplied with corresponding 32-bit data elements from each row of a 2×2 matrix, as shown in <figref idref="DRAWINGS">FIGS. 3A and 3B</figref>, generating two pairs of 64-bit intermediate results, each pair of which are stored in separate storage areas. An intra-add operation is performed on each pair of the intermediate results to generate a pair of data elements, which are stored as a packed result, as shown in FIG. <b>3</b>C. The example on <figref idref="DRAWINGS">FIGS. 3A-3C</figref> illustrate the application of one embodiment of the present invention using an integer data format in which the full width of the result is stored in a result register. In alternative embodiments, the result register is the same size as the source register.
0027The operation of a further example of a matrix multiplication operation based on intra-add operations is shown in <figref idref="DRAWINGS">FIGS. 4A through 4G</figref>, and is representative of a multiplication operation between a 4×4 matrix and a 4×1 vector (such as the multiplication of a 4×4 matrix A with a 4×1 vector X to provide a 4×1 vector Y as described earlier). In particular, each data element from a 4×1 vector is multiplied with the corresponding data elements from each row of a 4×4 matrix, as shown in <figref idref="DRAWINGS">FIGS. 4A through 4D</figref>.
0028A first pair of intra-add operations are then performed on the initial resulting data elements (IResult<b>1</b>+IResult<b>2</b>, IResult<b>3</b>+IResult<b>4</b>), as shown in <figref idref="DRAWINGS">FIG. 4E and 4F</figref>; followed by a second single intra-add operation on the results of the first intra-add operations (IAResult<b>1</b>+IAResult<b>2</b>), to obtain the final result (Result) as shown in FIG. <b>4</b>G.
0029Although the examples illustrated in <figref idref="DRAWINGS">FIGS. 4A-4G</figref> are floating point examples, the present invention may also be applied to packed integer data. Matrix multiplication based on horizontal add or intra-add operations only requires 12 instructions, as compared to the typical 20 instructions required when the same matrix multiplication is performed using vertical add or intra-add operations. Exemplary code for implementing matrix multiplication based on horizontal add or intra-add operations is shown in Table 2:
0000Exemplary Code Based on Horizontal-Add Operations
0030PFADDM represents the Intra-add instruction of the present invention.
0031<tables id="TABLE-US-00002" num="00002"><table frame="none" colsep="0" rowsep="0" pgwide="1"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="280pt" align="left" /><thead><row><entry namest="1" nameend="1" rowsep="1">TABLE 2</entry></row><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row><row><entry> Assumptions:</entry></row><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>1/X stored with X1 first, X2 second, . . . , X4 last</entry></row><row><entry>2/A stored with A11 first, A12 second, A13 third, etc.</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="140pt" align="left" /><colspec colname="2" colwidth="140pt" align="left" /><tbody valign="top"><row><entry>MOVDQ mm0, <mem_X></entry><entry>// [X4, X3, X2, X1]</entry></row><row><entry>MOVDQ mm3, mm0</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="112pt" align="left" /><colspec colname="2" colwidth="140pt" align="left" /><tbody valign="top"><row><entry /><entry> PFMUL mm0 <mem_A></entry><entry> // [A14*X4, A13*X3, A12*X2, A11*X1]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="280pt" align="left" /><tbody valign="top"><row><entry> MOVDQ mm1, mm3</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="112pt" align="left" /><colspec colname="2" colwidth="140pt" align="left" /><tbody valign="top"><row><entry /><entry> PFMUL mm1 <mem_A + 16></entry><entry>// [A24*X4, A23*X3, A22*X2, A21*X1]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="280pt" align="left" /><tbody valign="top"><row><entry> MOVDQ mm2, mm3</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="112pt" align="left" /><colspec colname="2" colwidth="140pt" align="left" /><tbody valign="top"><row><entry /><entry> PFMUL mm2 <mem_A + 32></entry><entry> // [A34*X4, A33*X3, A32*X2, A31*X1]</entry></row><row><entry /><entry>PFMUL mm3 <mem_A + 48></entry><entry>// [A44*X4, A43*X3, A42*X2, A41*X1]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="140pt" align="left" /><colspec colname="2" colwidth="140pt" align="left" /><tbody valign="top"><row><entry> PFADDM mm0, mm1</entry><entry>// [A24*X4 + A23*X3, A22*X2 + A21*X1,</entry></row><row><entry /><entry>// A14*X4 + A13*X3, A12*X2 + A11*X1]</entry></row><row><entry>PFADDM mm2, mm3</entry><entry>// [A44*X4 + A43*X3, A42*X2 + A41*X1,</entry></row><row><entry /><entry>// A34*X4 + A33*X3, A32*X2 + A31*X1]</entry></row><row><entry>PFADDM mm0, mm2</entry><entry>// [A44*X4 + A43*X3 + A42*X2 + A41*X1,</entry></row><row><entry /><entry>// A34*X4 + A33*X3 + A32*X2 + A31*X1],</entry></row><row><entry /><entry>// A24*X4 + A23*X3 + A22*X2 + A21*X1,</entry></row><row><entry /><entry>// A14*X4 + A13*X3 + A12*X2 + A11*X1]</entry></row><row><entry>MOVDQ <mem_Y>, min0</entry><entry>// store [Y4, Y3, Y2, Y1]</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>
0032Although the discussions above pertain to a horizontal-add or inter-add instruction, alternative embodiments could in addition to, or in place of the intra-add instruction, have an inter-subtract instruction or element operation. In this case, one of a pair of data elements within a packed data will be subtracted from a second element of the pair of data elements to accomplish the inter-subtract operations.
0033In addition, although the discussions above pertain to packed operands that have four data elements, alternative embodiments may involve packed operands that have at least two data elements (i.e., that are double wide).
Computer System
0034<figref idref="DRAWINGS">FIG. 5</figref> illustrates one embodiment of a computer system <b>100</b> which implements the principles of the present invention. Computer system <b>100</b> comprises a bus <b>102</b> for communicating information, and a processor <b>110</b> for processing information. In one embodiment, the bus <b>102</b> may be any communications hardware and/or software for communicating information. The processor <b>110</b> represents a central processing unit of any type of architecture, examples of which include a CISC, a RISC or a VLIW type architecture. Computer system <b>100</b> further comprises a main memory <b>104</b> that is coupled to bus <b>102</b>, for storing information and instructions to be executed by the processor <b>110</b>. Computer system <b>110</b> also comprises a read only memory (ROM) <b>106</b> and/or other status storage device, coupled to the bus <b>102</b> for storing information and instructions for access and execution by processor <b>110</b>. In addition, computer system <b>110</b> comprises a data storage device <b>108</b> that is coupled to the bus <b>102</b> for storing information and instructions.
0035As shown in <figref idref="DRAWINGS">FIG. 5</figref>, processor <b>110</b> comprises an execution unit <b>120</b>, a set of register file(s) <b>130</b>, a cache memory <b>140</b>, a decoder <b>150</b> and an internal bus <b>160</b>. The processor <b>110</b> also includes additional circuitry (not shown) which is not necessary to the understanding of the present invention.
0036Execution unit <b>120</b> is used for executing instructions received by processor <b>110</b>. In addition to recognizing instructions typically implemented in general purpose processors, execution unit <b>120</b> recognizes instructions in packed instruction set <b>122</b> for performing operations on packed data formats. Packed instruction set <b>122</b> includes instructions for supporting intra-add and multiply operations. In addition, packed instruction set <b>122</b> may also include other packed instructions.
0037Execution unit <b>120</b> is coupled to register file <b>130</b> by internal bus <b>160</b>. Register file <b>130</b> represents a storage area on processor <b>110</b> for storing information, including data. It is understood that the aspects of the invention are the described intra-add instruction set and a code sequence for performing matrix multiplication for operating on packed data. According to these aspects of the invention, the storage area used for storing the packed data is not critical. Execution unit <b>120</b> is coupled to cache <b>140</b> and decoder <b>150</b>. Cache <b>140</b> is used to cache data and/or control signals (such as instructions) from, for example, main memory <b>104</b>. Decoder <b>150</b> is used for decoding instructions received by processor <b>110</b> into control signals and/or microcode entry points. In response to these control signals and/or microcode entry points, execution unit <b>120</b> performs the appropriate operations. Decoder <b>150</b> may be implemented using any number of different mechanisms (e.g., a look-up table, a hardware implementation, a PLA, etc.).
0038<figref idref="DRAWINGS">FIG. 5</figref> additionally shows a data storage device <b>108</b>, (e.g., a magnetic disk, optical disk, and/or other machine readable media) coupled to computer system <b>100</b>. In addition, the data storage device <b>108</b> is shown including code <b>195</b> for execution by the processor <b>110</b>. The code <b>195</b> can be written to cause the processor <b>110</b> to perform matrix multiplication with the intra-add instruction for any number of purposes (e.g., 3-D graphics multiplication, 3-D transformation, 3-D rotation, 3-D scaling, etc.). Computer system <b>100</b> can also be coupled via bus <b>102</b> to a display device <b>170</b>, a user input device <b>172</b>, a hard copy device <b>176</b>, a sound recording and/or playback device <b>178</b>, a video digitizing device <b>180</b>, and/or a communications device <b>190</b> (e.g., a serial communications chip, an ethernet chip or a modem, which provides communications with an external device or network).
Data and Storage Formats
0039Generally, a data element is an individual piece of data that is stored in a single register (or memory location) with other data elements of the same length. The number of data elements stored in a register is the number of bits supported by the packed data format (e.g., 64 bits for integer packed data) divided by the length in bits of a data element. While any number of packed data formats can be used, <figref idref="DRAWINGS">FIGS. 6-7</figref>, respectively, illustrate integer and floating-point packed data-types according to one embodiment of the invention.
0040Three integer packed data formats are illustrated in FIG. <b>6</b>: packed byte <b>401</b>, packed word <b>402</b>, and packed doubleword <b>403</b>. While in one embodiment, each of the packed data formats in <figref idref="DRAWINGS">FIG. 6</figref> can be either signed or unsigned formats, alternative embodiments support only signed or unsigned formats. Packed byte <b>401</b>, in one embodiment of the invention, is sixty-four bits long containing eight data elements. Each data element is one byte long. Packed word <b>402</b> is sixty-four bits long and contains four word <b>402</b> data elements. Each word <b>402</b> data element contains sixteen bits of information. Packed doubleword <b>403</b> is sixty-four bits long and contains two doubleword <b>403</b> data elements. Each doubleword <b>403</b> data element contains thirty-two bits of information.
0041<figref idref="DRAWINGS">FIG. 7</figref> shows one floating point packed data format having four 32-bit data elements. While one floating point packed data format is illustrated, alternative embodiments could support a different and/or additional floating point packed data formats.
Intra-Add Operations(s)
0042In one embodiment of the invention, the SRC<b>1</b> register contains packed data (Source<b>1</b>), the SRC<b>2</b> register contains packed data (Source<b>2</b>) and the DEST register will contain the result (Result) of performing the horizontal add instruction on Source<b>1</b> and Source<b>2</b>. In the first step of the horizontal add instruction, one or more pairs of data elements from Source<b>1</b> are summed together. Similarly, one or more pairs of data elements from Source<b>2</b> are summed together. The results of the instruction are then stored in the DEST register.
0043<figref idref="DRAWINGS">FIG. 8</figref> is a flow diagram illustrating a process S<b>800</b> for performing the intra-add operation of <figref idref="DRAWINGS">FIG. 2</figref> according to one embodiment of the present invention. The process S<b>800</b> begins from a start state and proceeds to process step S<b>802</b>, where the decoder <b>150</b> decodes the control signal received by processor <b>110</b>. In particular, the decoder <b>150</b> decodes the operation code for the intra-add instruction.
0044The process S<b>800</b> then advances to process step S<b>804</b>, where the device <b>150</b> accesses registers in register file <b>130</b> given the SRC<b>1</b><b>602</b> and SRC<b>2</b><b>603</b> addresses. Register file <b>130</b> provides the execution unit <b>120</b> with the packed data stored in the SRC<b>1</b><b>602</b> register (Source<b>1</b>), and the packed data stored in SRC<b>2</b><b>603</b> register (Source<b>2</b>).
0045The process S<b>800</b> proceeds to process step S<b>806</b>, where the decoder <b>150</b> enables the execution unit <b>120</b> to perform the instruction. Next, the process S<b>800</b> performs the following series of steps, as shown in process step S<b>808</b> and FIG. <b>2</b>. Source<b>1</b> bits thirty-one through zero are added to Source<b>1</b> bits sixty-three through thirty-two, generating a first 32-bit result (Result[<b>31</b>:<b>0</b>]). Source<b>1</b> bits ninety-five through sixty-four are added to Source<b>1</b> bits one hundred-and-twenty-seven through ninety-six, generating a second 32-bit result (Result[<b>63</b>:<b>32</b>]). Source<b>2</b> bits thirty-one through zero are added to Source<b>2</b> bits sixty-three through thirty-two, generating a first 32-bit result (Result[<b>95</b>:<b>64</b>]). Source<b>2</b> bits ninety-five through sixty-four are added to Source<b>1</b> bits one hundred-and-twenty-seven through ninety-six, generating a second 32-bit result (Result[<b>127</b>:<b>96</b>]).
0046The process S<b>800</b> advances to process step S<b>810</b>, where the results of the intra-add instruction are stored in DEST. The process S<b>800</b> then terminates. Of course, the method of <figref idref="DRAWINGS">FIG. 8</figref> can be easily altered to describe the horizontal addition of other packed data formats.
Exemplary Intra-add Circuit
0047In one embodiment, the intra-add instructions can execute on multiple data elements in the same number of clock cycles as an inter-add operation on unpacked data. To achieve execution in the same number of clock cycles, parallelism is used.
0048<figref idref="DRAWINGS">FIG. 9</figref> illustrates a circuit <b>900</b> for performing intra-add operation of <figref idref="DRAWINGS">FIG. 2</figref> according to one embodiment of the invention. Operation control <b>910</b> processes the control signal for the intra-add operations. Operation control <b>910</b> outputs signals via signal line <b>920</b> to control intra-adder <b>930</b>.
0049The intra-adder <b>930</b> receives inputs from Source<b>1</b>[<b>127</b>:<b>0</b>], Source<b>2</b>[<b>127</b>:<b>0</b>], and Enable <b>920</b>. The intra-adder <b>930</b> includes four adder circuits <b>932</b>, <b>934</b>, <b>936</b> and <b>938</b>. Adder <b>932</b> receives inputs from Source<b>2</b>[<b>127</b>:<b>64</b>], adder <b>934</b> receives inputs from Source<b>2</b>[<b>63</b>:<b>0</b>], adder <b>936</b> receives inputs from Source<b>1</b>[<b>127</b>:<b>64</b>], while adder <b>938</b> receives inputs from Source<b>1</b>[<b>63</b>:<b>0</b>]. When enabled, the adders <b>932</b>, <b>934</b>, <b>936</b> and <b>938</b> sum their respective inputs, and each generates a 32-bit output. The results of the addition by adder <b>932</b> (i.e., Result[<b>127</b>:<b>96</b>]), adder <b>934</b> (i.e., Result[<b>95</b>:<b>64</b>], by adder <b>936</b> (i.e., Result[<b>63</b>:<b>32</b>]), and by adder <b>938</b> (i.e., Result[<b>31</b>:<b>0</b>]) are combined into the 128-bit Result and communicated to the Result Register <b>940</b>.
Matrix Multiplication Using Intra-Add Operation(S)
0050<figref idref="DRAWINGS">FIG. 10</figref> is a general block diagram illustrating the use of matrix multiplication based on a horizontal or intra-add operation for rendering graphical objects in animation according to one embodiment of the invention. <figref idref="DRAWINGS">FIG. 10</figref> shows a computer system <b>1000</b> containing digital data <b>1010</b> representing 3-dimensional (3D) graphics. The digital data <b>1010</b> may be read from a storage medium or generated real time. At sometime, the conversion unit <b>1020</b> alters data using 3D geometry (e.g., by performing a 3D transformation) through the implementation of matrix multiplication based on a horizontal add operation to rotate a 3D object in providing animation. The resulting graphical object <b>1030</b> (e.g., see <figref idref="DRAWINGS">FIGS. 4A-4G</figref>) is then displayed on a screen display <b>1040</b> using well known techniques. While <figref idref="DRAWINGS">FIG. 10</figref> shows that the resulting graphical object <b>1030</b> is displayed, the resulting graphical object may alternatively be stored, transmitted, etc.
0051In one embodiment, the computer system <b>100</b> shown in <figref idref="DRAWINGS">FIG. 5</figref> is used to implement the computer system <b>1000</b> from FIG. <b>10</b>. In this embodiment, the digital data <b>1010</b> from <figref idref="DRAWINGS">FIG. 10</figref> is any data stored in the storage device <b>110</b> representing 3D graphics. In one embodiment, the conversion unit <b>1020</b> from <figref idref="DRAWINGS">FIG. 8</figref> is implemented using the processor <b>110</b> and the code <b>195</b> to alter data using 3D geometry. For example, data is altered to perform a transformation. In this embodiment, the processor <b>110</b>, executing the code <b>195</b>, performs the transformation and stores the transformed data <b>1030</b> for display.
CONCLUSION
0052The intra-add operation facilitates the efficient performance of multi-dimensional computations. It further increases code density by eliminating the need for the rearrangement of data elements and the corresponding rearrangement operations.
0053The present invention may be embodied in other specific forms without departing from its spirit or essential characteristics. The described embodiments are to be considered in all respects only as illustrative and not restrictive. The scope of the invention is, therefore, indicated by the appended claims rather than the foregoing description. All changes which come within the meaning and range of equivalency of the claims are to be embraced within their scope.
Contents5
15 sheets
Sheet 1 Sheet 2 Sheet 3 Sheet 4 Sheet 5 Sheet 6 Sheet 7 Sheet 8 Sheet 9 Sheet 10 Sheet 11 Sheet 12 Sheet 13 Sheet 14 Sheet 15
Every citation, both ways
| Document | Relation | Office | Cited during |
|---|---|---|---|
| US2022318009A1 | Cited by | United States of America | Search report |
| US2014129801A1 | Cited by | United States of America | Pre-grant |
| US9557998B2 | Cited by | United States of America | Applicant |
| US2011314254A1 | Cited by | United States of America | Pre-grant |
| US11704124B2 | Cited by | United States of America | Search report |
| US7395302B2 | Cited by | United States of America | Applicant |
| US2004059889A1 | Cited by | United States of America | Pre-grant |
| US7392275B2 | Cited by | United States of America | Search report |
| US8856492B2 | Cited by | United States of America | Search report |
| CN104025025A | Cited by | China | Search report |
| US9465612B2 | Cited by | United States of America | Search report |
| US10037209B2 | Cited by | United States of America | Applicant |
| US9965282B2 | Cited by | United States of America | Applicant |
| US2004078404A1 | Cited by | United States of America | Pre-grant |
| US10671392B2 | Cited by | United States of America | Applicant |
| US11221849B2 | Cited by | United States of America | Search report |
| EP0318957A2 | Cites | European Patent Office (EPO) | Applicant |
| US3711692A | Cites | United States of America | Applicant |
| US3723715A | Cites | United States of America | Applicant |
| US4161784A | Cites | United States of America | Applicant |
| US4189716A | Cites | United States of America | Applicant |
| US4393468A | Cites | United States of America | Applicant |
| US4418383A | Cites | United States of America | Applicant |
| US4498177A | Cites | United States of America | Applicant |
| US4630192A | Cites | United States of America | Applicant |
| US4707800A | Cites | United States of America | Applicant |
| US4771379A | Cites | United States of America | Applicant |
| US4785393A | Cites | United States of America | Applicant |
| US4785421A | Cites | United States of America | Applicant |
| US4901270A | Cites | United States of America | Applicant |
| US4989168A | Cites | United States of America | Applicant |
| US5095457A | Cites | United States of America | Applicant |
| US5187679A | Cites | United States of America | Applicant |
| US5201056A | Cites | United States of America | Applicant |
| US5327369A | Cites | United States of America | Applicant |
| US5339447A | Cites | United States of America | Applicant |
| US5390135A | Cites | United States of America | Applicant |
| US5418736A | Cites | United States of America | Applicant |
| US5442799A | Cites | United States of America | Applicant |
| US5448703A | Cites | United States of America | Applicant |
| US5517626A | Cites | United States of America | Applicant |
| US5530661A | Cites | United States of America | Applicant |
| US5537601A | Cites | United States of America | Applicant |
| US5586070A | Cites | United States of America | Applicant |
| US5677862A | Cites | United States of America | Applicant |
| US5678009A | Cites | United States of America | Applicant |
| US5721697A | Cites | United States of America | Applicant |
| US5721892A | Cites | United States of America | Applicant |
| US5815421A | Cites | United States of America | Applicant |
| US5819117A | Cites | United States of America | Applicant |
| US5822232A | Cites | United States of America | Applicant |
| US5859790A | Cites | United States of America | Applicant |
| US5862067A | Cites | United States of America | Applicant |
| US5875355A | Cites | United States of America | Applicant |
| US5880984A | Cites | United States of America | Applicant |
| US5880985A | Cites | United States of America | Applicant |
| US5883824A | Cites | United States of America | Applicant |
| US5887186A | Cites | United States of America | Applicant |
| US5901301A | Cites | United States of America | Applicant |
| US5918062A | Cites | United States of America | Applicant |
| US5983257A | Cites | United States of America | Applicant |
| US6006316A | Cites | United States of America | Applicant |
| US6014684A | Cites | United States of America | Applicant |
| US6014735A | Cites | United States of America | Applicant |
| US6041404A | Cites | United States of America | Applicant |
| US6115812A | Cites | United States of America | Applicant |
| US6122725A | Cites | United States of America | Applicant |
| US6211892B1 | Cites | United States of America | Applicant |
| US6212618B1 | Cites | United States of America | Applicant |
| US6230253B1 | Cites | United States of America | Applicant |
| US6230257B1 | Cites | United States of America | Applicant |
| US6288723B1 | Cites | United States of America | Applicant |
| WO9723821A1 | Cites | World Intellectual Property Organization (WIPO) | Applicant |
| EP318957 | Cites | European Patent Office (EPO) | Third party observation |
| WO9723821 | Cites | World Intellectual Property Organization (WIPO) | Third party observation |
| MIPS Extension for Digital Media with 3D, MIPS Technology, Inc., Mar. 12, 1997, pp 0-26. | Non-patent | – | Applicant |
| A Procesor Architecture for 3D Graphics Calculations, Yulun Wang, Amante Manager, Partha Srinivasan, Computer Motion, Inc., pp 1-23. | Non-patent | – | Applicant |
| Parallel Computers for Graphics Applications (Proceedings: Second International Conference . . . ), Levinthal, et al., 1987, pp 193-198. | Non-patent | – | Applicant |
| MIPS Extension for Digital Media with 3D, MIPS Technology, Inc., Mar. 12, 1997, pp 0-26. | Non-patent | – | Third party observation |
| A Procesor Architecture for 3D Graphics Calculations, Yulun Wang, Amante Manager, Partha Srinivasan, Computer Motion, Inc., pp 1-23. | Non-patent | – | Third party observation |
| Parallel Computers for Graphics Applications (Proceedings: Second International Conference . . . ), Levinthal, et al., 1987, pp 193-198. | Non-patent | – | Third party observation |
187 members in 19 offices
Priority claims6
| Document | Office | Kind | Date |
|---|---|---|---|
| 5340198 | United States of America | A | |
| 5340198 | United States of America | A | |
| 19364502 | United States of America | A | |
| 09053401 | – | – | – |
| US19980053401 | – | – | – |
| US20020193645 | – | – | – |
Members187
| Document | Office | Kind | |
|---|---|---|---|
| CA2230108A1 | Canada | A1 | |
| WO9708610A1 | World Intellectual Property Organization (WIPO) | A1 | |
| AU6951196A | Australia | A | |
| US5721892A | United States of America | A | |
| NO980873D0 | Norway | D0 | |
| NO980873L | Norway | L | |
| MX9801571A | Mexico | A | |
| EP0847552A1 | European Patent Office (EPO) | A1 | |
| PL325231A1 | Poland | A1 | |
| IL123241A0 | Israel | A0 | |
| CN1200821A | China | A | |
| US5859997A | United States of America | A | |
| BR9610285A | Brazil | A | |
| HU9900030A2 | Hungary | A2 | |
| HUP9900030A2 | Hungary | A2 | |
| KR19990044305A | Republic of Korea | A | |
| HK1012513A | Hong Kong, China | A | |
| HK1012513A1 | Hong Kong, China | A1 | |
| JPH11511577A | Japan | A | |
| RU2139564C1 | Russian Federation | C1 | |
| US5983256A | United States of America | A | |
| HU9900030A3 | Hungary | A3 | |
| HUP9900030A3 | Hungary | A3 | |
| EP0847552A4 | European Patent Office (EPO) | A4 | |
| US6035316A | United States of America | A | |
| AU717246B2 | Australia | B2 | |
| CA2230108C | Canada | C | |
| IL123241A | Israel | A | |
| US6385634B1 | United States of America | B1 | |
| US2002059355A1 | United States of America | A1 | |
| KR100329339B1 | Republic of Korea | B1 | |
| US6418529B1 | United States of America | B1 | |
| EP0847552B1 | European Patent Office (EPO) | B1 | |
| DE69624578D1 | Germany | D1 | |
| US2003050941A1 | United States of America | A1 | |
| US2003084082A1 | United States of America | A1 | |
| CN1107905C | China | C | |
| WO03038601A1 | World Intellectual Property Organization (WIPO) | A1 | |
| US2003123748A1 | United States of America | A1 | |
| US2003131030A1 | United States of America | A1 | |
| DE69624578T2 | Germany | T2 | |
| US2004054877A1 | United States of America | A1 | |
| US2004054878A1 | United States of America | A1 | |
| US2004054879A1 | United States of America | A1 | |
| US2004059889A1 | United States of America | A1 | |
| US2004073589A1 | United States of America | A1 | |
| US2004078404A1 | United States of America | A1 | |
| KR20040038922A | Republic of Korea | A | |
| WO2004040439A2 | World Intellectual Property Organization (WIPO) | A2 | |
| US2004098556A1 | United States of America | A1 | |
| AU2003301718A1 | Australia | A1 | |
| US2004117422A1 | United States of America | A1 | |
| CN1506807A | China | A | |
| DE10297000T5 | Germany | T5 | |
| US2004133617A1 | United States of America | A1 | |
| US2004139138A1 | United States of America | A1 | |
| CN1522401A | China | A | |
| US2004210616A1 | United States of America | A1 | |
| US2004220992A1 | United States of America | A1 | |
| CN1549106A | China | A | |
| NO317739B1 | Norway | B1 | |
| WO2004040439A3 | World Intellectual Property Organization (WIPO) | A3 | |
| WO2005006183A2 | World Intellectual Property Organization (WIPO) | A2 | |
| JP2005508043A | Japan | A | |
| TW200515279A | Taiwan Province of China | A | |
| HK1068985A | Hong Kong, China | A | |
| HK1068985A1 | Hong Kong, China | A1 | |
| US2005108312A1 | United States of America | A1 | |
| RU2003137531A | Russian Federation | A | |
| HK1072989A | Hong Kong, China | A | |
| HK1072989A1 | Hong Kong, China | A1 | |
| US6961845B2This record | United States of America | B2 | |
| WO2005006183A3 | World Intellectual Property Organization (WIPO) | A3 | |
| JP3750820B2 | Japan | B2 | |
| RU2273044C2 | Russian Federation | C2 | |
| EP1639452A2 | European Patent Office (EPO) | A2 | |
| JP2006107463A | Japan | A | |
| KR20060040611A | Republic of Korea | A | |
| RU2006102503A | Russian Federation | A | |
| HK1083657A | Hong Kong, China | A | |
| HK1083657A1 | Hong Kong, China | A1 | |
| CN1801082A | China | A | |
| KR100602532B1 | Republic of Korea | B1 | |
| US7085795B2 | United States of America | B2 | |
| CN1813241A | China | A | |
| CN1269027C | China | C | |
| TWI270007B | Taiwan Province of China | B | |
| JP2007526536A | Japan | A | |
| US7272622B2 | United States of America | B2 | |
| CN100338570C | China | C | |
| RU2316808C2 | Russian Federation | C2 | |
| US7340495B2 | United States of America | B2 | |
| JP4064989B2 | Japan | B2 | |
| KR100831472B1 | Republic of Korea | B1 | |
| DE10297000B4 | Germany | B4 | |
| US7392275B2 | United States of America | B2 | |
| US7395298B2 | United States of America | B2 | |
| US7395302B2 | United States of America | B2 | |
| US7424505B2 | United States of America | B2 | |
| US7430578B2 | United States of America | B2 |
53 transactions on the USPTO file
Allowed after 2 non-final rejections, 1 final rejection and 1 RCE.
- Non-final rejections
- 2
- Final rejections
- 1
- RCEs
- 1
- Appeals
- 0
Over time
Point at a mark for the transactionTransactions
| Event | Code | |
|---|---|---|
| Expire PatentEXP. | EXP. | |
| Issue Fee Payment ReceivedIFEE | IFEE | |
| Post Issue Communication - Certificate of CorrectionN423 | N423 | |
| Recordation of Patent Grant MailedPGM/ | PGM/ | |
| Patent Issue Date Used in PTA CalculationAllowedPTAC | PTAC | |
| Issue Notification MailedAllowedWPIR | WPIR | |
| Receipt into PubsR1021 | R1021 | |
| Dispatch to FDCD1935 | D1935 | |
| Application Is Considered Ready for IssuePILS | PILS | |
| Issue Fee Payment VerifiedN084 | N084 | |
| Issue Fee Payment ReceivedIFEE | IFEE | |
| Workflow - File Sent to ContractorSENT | SENT | |
| Mail Notice of AllowanceAllowedMN/=. | MN/=. | |
| Mail Notification of Terminal Disclaimer - AcceptedMN574 | MN574 | |
| Notice of Allowance Data Verification CompletedAllowedN/=. | N/=. | |
| Case Docketed to Examiner in GAUDOCK | DOCK | |
| Paralegal or electronic terminal disclaimer approvedP574 | P574 | |
| Notification of Terminal Disclaimer - AcceptedN574 | N574 | |
| IFW TSS Processing by Tech Center CompleteTSSCOMP | TSSCOMP | |
| Date Forwarded to ExaminerFWDX | FWDX | |
| Response after Non-Final ActionA... | A... | |
| Request for Extension of Time - GrantedXT/G | XT/G | |
| Terminal Disclaimer FiledDIST | DIST | |
| Mail Non-Final RejectionNon-final rejectionMCTNF | MCTNF | |
| Non-Final RejectionNon-final rejectionCTNF | CTNF | |
| Date Forwarded to Examiner | – | |
| Date Forwarded to Examiner | – | |
| Disposal for a RCE / CPA / R129AbandonedABN9 | ABN9 | |
| Request for Continued Examination (RCE)RCEX | RCEX | |
| Request for Extension of Time - GrantedXT/G | XT/G | |
| Workflow - Request for RCE - BeginBRCE | BRCE | |
| Workflow incoming amendment IFWWAMD | WAMD | |
| Mail Final Rejection (PTOL - 326)Final rejectionMCTFR | MCTFR | |
| Final RejectionFinal rejectionCTFR | CTFR | |
| Date Forwarded to ExaminerFWDX | FWDX | |
| Response after Non-Final ActionA... | A... | |
| Mail Supplemental Non-Final ActionMSRNF | MSRNF | |
| Supplemental Non-Final ActionSRNF | SRNF | |
| Preliminary AmendmentA.PE | A.PE | |
| Mail Non-Final RejectionNon-final rejectionMCTNF | MCTNF | |
| Non-Final RejectionNon-final rejectionCTNF | CTNF | |
| Case Docketed to Examiner in GAUDOCK | DOCK | |
| Transfer Inquiry to GAUTI1050 | TI1050 | |
| Transfer Inquiry to GAUTI1050 | TI1050 | |
| Application Dispatched from OIPEOIPE | OIPE | |
| Application Is Now CompleteCOMP | COMP | |
| Payment of additional filing fee/PreexamFLFEE | FLFEE | |
| Reference capture on IDSRCAP | RCAP | |
| Information Disclosure Statement (IDS) Filed | – | |
| Information Disclosure Statement (IDS) Filed | – | |
| Notice Mailed--Application Incomplete--Filing Date AssignedINCD | INCD | |
| IFW Scan & PACR Auto Security Review | – | |
| Initial Exam Team nnIEXX | IEXX |
7 legal events, as the office reported them to INPADOC
Over the term
Point at a mark for the eventEvents
| Event | Code | |
|---|---|---|
| Lapsed due to failure to pay maintenance feeLapsedFP | FP | |
| Lapse for failure to pay maintenance feesLapsedPATENT EXPIRED FOR FAILURE TO PAY MAINTENANCE FEES (ORIGINAL EVENT CODE: EXP.)LAPS | LAPS | |
| Information on status: patent discontinuationPATENT EXPIRED DUE TO NONPAYMENT OF MAINTENANCE FEES UNDER 37 CFR 1.362STCH | STCH | |
| Maintenance fee reminder mailedREMI | REMI | |
| Fee paymentFPAY | FPAY | |
| Fee paymentFPAY | FPAY | |
| Certificate of correctionCC | CC |
Numbers
- Publication
- 06961845
- Publication, DOCDB
- 6961845
- Publication, EPODOC
- US6961845
- Application
- 10193645
- Application, DOCDB
- 19364502
- Application, EPODOC
- US20020193645
Titles
- English
- System to perform horizontal additions
Patent term adjustment
- Applicant delay
- −142 days
- Net adjustment
- 0 days
Classification
- CPC, 2
- G06F9/30036
- G06F9/3001
- IPC, 1
- G06F9 302
- USPC, 3
- 712221000
- 712222000
- 712E09017