Method and system for efficient matrix multiplication in a SIMD processor architecture

[0001] This application is related to co-pending U.S. patent application Ser. No. 10/357,805, filed on Feb. 3, 2003 by Tibet Mimar entitled “Flexible Vector Modes of Operation”, and to co-pending U.S. patent application Ser. No. 10/441,336, filed on May 20, 2003 by Tibet Mimar entitled “Method For Efficient Handling Of Vector High-Level Language Conditional Constructs In A SIMD Processor”.

[0002] 1. Field of the Invention

[0003] The invention relates generally to the field of processor chips and specifically to the field of Single-Instruction Multiple-Data (SIMD) processors. More particularly, the present invention relates to matrix operations in a SIMD processing system.

[0004] 2. Background

[0005] Matrix multiplication operations are used often in many digital signal-processing operations, because linear operations could be expressed as matrix operations. For example, 4×4 transformation matrix is used to perform any color space to another color space transformation. The four-color components could be Red, Green, Blue, and Alpha, or any three-color component types and an Alpha channel typically used for keying applications. Color space transformation is used often in video, image and graphics applications. Another application of the matrix multiplication is in the implementation of Discrete Cosine Transform (DCT) for H.264 video compression standard (also known as AVC and MPEG-4 Part 10), which requires multiplication of multiple 4×4 matrices.

[0006] Existing SIMD processor architectures try to use SIMD instructions to speed up the implementation of these matrix operations by parallelizing multiple operations. SIMD instructions work on vectors consisting of multiple elements at the same time. An 8-wide SIMD could operate on eight 16-bit elements concurrently, for example. Even though SIMD architecture and instructions could be very efficient in implementing Finite Impulse Response (FIR) filters and other operations, the implementation of matrix operations are not efficient because matrix operations require cross mapping of vector elements for arithmetic operations. SIMD processors that are on the market at the time of this writing work with intra vector elements, which mean one-to-one fixed mapping of vector elements are used for vector operations. For example, when we use vector-add instruction, this instruction adds element-0 of source-1 vector register to element-0 of source-2 vector register and stores it to element-0 of output vector register; adds element-1 of source-1 to element-1 of source-2 and stores it to element-1 of output vector register, and so forth. In contrast, inter-mapping of source vector elements refers to any cross mapping of vector elements. Most SIMD processors provide little or no support for inter-element arithmetic operations. Motorola's AltiVec provides only two inter element vector instruction for arithmetic operations: sum of products and sum across (vector sum of elements). The other SIMD processors, such as MMX/SSE from Intel, or ICE from SGI does not even provide support for inter element operations other than vector sum operations. Silicon Graphics' ICE provides a broadcast mode, whereby one selected element of a source vector could operate across all elements of a second vector register. Intra element operation and broadcast modes of SIMD operation of prior art are shown in FIG. 1.

[0007] Some processors like the AltiVec provides a non-arithmetic vector permute instructions, whereby vector elements could be permuted prior to arithmetic operations. However, this requires two vector-permute instructions followed by the vector arithmetic instruction, which reduces the efficiency significantly for core operations such as DCT or color space conversion. It is conceivable that a SIMD processor has multiple vector units, where two vector permute units and vector arithmetic unit could operate concurrently in a super scalar processor executing two or more vector instructions in a pipelined fashioned. However, this requires the results of one instruction to be immediately available to the other unit by bypassing of intermediate vector results before these are written to the vector register file. Such bypassing of intermediate results becomes increasingly costly in terms of die area or number of gates, as the number of SIMD elements is increased over eight elements or 128-bit wide data paths.

[0008] The following describes how the above two example applications are handled by prior art.

Color Space Conversion

[0009] A transformation between color spaces requires multiplication of a 4×4 matrix with 4×1 input color matrix, as shown below converting input vector {I0, I1, I2, I3} to output vector of {Q3, Q2, Q1, Q0}, as shown in FIG. 8. The values of 4×4 matrix, M0 to M15, depend on the color space conversion being performed and consist of constant values. First, let us assume we have a 4-wide SIMD processor, and we are trying to calculate this matrix. First, we could pre-arrange the constant values of 4×4 matrix so that values are in column sequential, as we have done in this example. One could implement the matrix operations in two different ways. The classic approach is to multiply the first row of matrix with the first column of second matrix (only one in this case) and vector sum the results to obtain the first value. Similarly, second value is obtained by multiplying second row of 4×4 with the input vector and vector-summing the intermediate results. The second approach, that is more appropriate for SIMD implementation, is to calculate the partial sums of four output values at the same time. In other words, we would first multiply I0 with all the values of the first column of 4×4 matrix and store this vector of four values in a vector accumulator register. Next, we would multiply I1 with all the second column values of 4×4 matrix, and add this vector of four values to the vector accumulator values, and so forth for the remaining two columns of 4×4 matrix. This partial-product approach minimizes inter-element operations, and avoids the use of vector-sum operations. Column sequential ordering of 4×4 matrix allows us to load vectors of {m0, m1, m2, m3}, {m4, m5, m6, m7}, and others as vector load of sequential data elements into a vector register without the need to re-shuffle them. The arithmetic operations to be performed are shown in the table shown in FIG. 9

[0010] A 4-wide SIMD could calculate such matrix operations very efficiently, assuming there is a broadcast mode where one element could operate across all other elements of a second vector. A somewhat less efficient approach used by SIMD processors is to first use a “splat” instruction, which operates to copy any element from one vector register into all elements of another register. This would reduce the performance by 50 percent in comparison to a SIMD with broadcast mode, since all multiply or multiply-accumulate operations has to be proceeded by a splat vector instruction. MMX from Intel does not have such an instruction, and therefore, it takes four instructions, whereas SSE from Intel has a packed-shuffle instruction, which could implement the splat operation. In summary, other than 50 percent performance reduction due to splat operation, 4-wide SIMD processors could perform matrix operations about twice as fast as their scalar counter parts. But, the performance of these processors are not close to meeting high performance requirements of video, graphics, and other digital signal processing applications, because their level of parallelism is small due to small number of parallel processing elements. Furthermore, AltiVec and Pentium class processors do not meet the low cost and low power requirements of embedded consumer applications.

[0011] Let us look at an 8-wide SIMD to exemplify what happens when SIMD processor has higher potential “data crunching” power. In this case, we could process two input pixels at the same time, i.e., we would load eight values {I0, I1, I2, I3, I4, I5, I6, I7} where I0-3 is color components of the a pixel and I4-7 is the color components of adjacent pixel. In this case, we could preconfigure 4×4 matrix columns as {m0, m1, m2, m3, m0, m1, m2, m3} and so forth, and prestore these in memory so that we could access any column as a vector of eight values by a single vector load instruction. This is equivalent to multiplying the same 4×4 matrix with an input matrix of 4×2, resulting in a 4×2 matrix. FIG. 10 illustrates the operations in four steps of partial-product accumulation. The problem is, however, how we form a vector of {I0, I0, I0, I0, I4, I4, I4, I4} from input vector of {I0, I1, I2, I3, I4, I5, I6, I7}. Intel's MMX and SSE do not offer any direct help to resolve this, not to mention they are also 4-wide SIMD. Motorola's AltiVec Vector permute instruction could be used, but again this reduces performance by 50 percent, because during the permute step arithmetic unit remains idle, or we face complicated and costly bypassing of intermediate variables between concurrent vector computational units.

[0012] As shown in FIG. 11, multiplying matrix A 1110 and matrix B 1120 may be calculated by first decomposing matrix A to its columns, and matrix B to its rows, and performing a series of matrix multiplication of columns of A with respective rows of B and summing the partial results. The columns of matrix A 1110 is shown by A1 1130, A2 1131, and An 1132. Similarly, rows of B 1120 are decomposed as B1 1160, B2 1161, and Bn 1162. Then, matrix multiplication of A and B matrices could be expressed summation of A1·B1 1170, A2·132 1171, and An·Bn 1172, where symbol “·” denotes matrix multiplication. Matrix multiplication of a column matrix of Ax with a row matrix Bx, where “x” denotes column or row number before decomposition, generates an m-by-p matrix 1180. For above example of 4-by-4 A matrix 1110 and 4-by-2 B matrix, output matrix has 8 elements. Calculating 8 of these parallel will require an 8-wide SIMD, which could iterate over four columns to calculate the result in four clock cycles. However, such a calculation is not possible with that efficiency because pairing of input vectors requires the following mapping of input vectors:

{1, 2, . . . 4, 1, 2, . . . , 4} and {1, 1, . . . , 1, 2, 2, . . . , 2}. The requirement for mapping is further compounded for wider SIMD architectures and for larger input matrices.

DCT Calculation

[0013] H.264 video compression standard frequently uses a DCT based transform for 4×4 blocks in residual data. This transformation requires the calculation of the following operation:

[0014] Y=A·X·B where A and B are constant 4×4 matrices and X is the input as a 4×4 data matrix. We could first calculate A·X or X·B, because this is a linear operation. Since X matrix is the input data, it is typically in row-sequential order. This means the mapping of elements required for multiplication or multiply-accumulation cannot be pre-arranged, as in the previous example, and requires a cross mapping of inter elements. Let us take the case of Q=X·B, and let us assume that all input and output matrices are stored in row-sequential order.

[0015] This matrix multiplication could be done in four steps, as illustrated in FIG. 12, using the multiply accumulate feature of a SIMD processor to accumulate partial results. The first step is a multiply operation of two vectors:

[0016] {X0, X0, X0, X0, X4, X4, X4, X8, X8, X8, X8, X12, X12, X12, X12} and

[0017] {B0, B1, B2, B3, B0, B1, B2, B3, B0, B1, B2, B3, B0, B1, B2, B3}.

[0018] This step would require a single vector-multiple instruction, if we had the input vectors mapped as required, but this mapping would require two additional vector-permute instructions. The second step is a vector multiply-accumulate operation of the following two vectors:

[0019] {X1, X1, X1, X1, X5, X5, X5, X5, X9, X9, X9, X9, X13, X13, X13, X13} and

[0020] {B4, B5, B6, B7, B4, B5, B6, B7, B4, B5, B6, B7, B4, B5, B6, B7}

[0021] This step could also be done with a single vector-multiply accumulate instruction, if we had the input matrix elements already mapped as follows. To get this mapping, the prior art such as AltiVec from Motorola requires two additional vector-permute instructions.

[0022] The requirement of two additional vector permute instructions reduces the performance to about one third, because the duty cycle of arithmetic operations where vector arithmetic unit is used is one-third. A super scalar implementation would require two concurrent vector permute units, in parallel with the vector arithmetic unit, which also would complicate the intermediate bypassing due to wide data widths, for example for a 32-wide SIMD using a 512-bits wide data path. A scalar processor typically bypasses results so that result of one instruction becomes immediately useable by the following instruction. Even though each instruction takes several cycles to execute in a pipeline fashion, such as Instruction Read, Instruction-Decode/Register Read, Execute-1, Execute-2 and Write-Back stages in a five stage pipelined RISC processor, this becomes costly with regard to gate count in a wide data path processor such as SIMD. That is why SIMD processors and some VLIW processors from Texas Instruments (TMS3206000 series) do not employ bypass, and it is left to the user to put enough instruction padding, by the use of interleaving instructions or NOPs, to take care of this.

[0023] The present invention provides a method by which any element of a source-1 vector register may operate in combination with any element of a source-2 vector register. This provides the ultimate flexibility in pairing vector elements as inputs to each of the arithmetic or logical operation units of a vector processor, such as a SIMD processor. This flexible mapping of any inter element support provides support to implement matrix multiplications very efficiently. A 4×4 matrix multiplication requires only one vector multiply and three vector multiply-accumulate instructions in a 16-wide embodiment. H.264 requires multiplication of two 4×4 matrices for DCT transform, which could be implemented using a total of only eight vector arithmetic instructions, as opposed to the 24 vector instructions of prior art. The mapping of input elements is controlled by a third vector source register, wherein certain bit-fields within each element of the control vector register select the source mapping for both source vectors.

[0040] The present invention decomposes a first matrix to its columns and a second matrix to its rows, and performs matrix multiplication of respective columns and rows. Vector multiply is used as the first step for first column of said first matrix and said first row of second matrix, and vector multiply-accumulate operation is used for the rest of the respective columns and rows. In each step, elements of column of first matrix and elements of row of second matrix is mapped according to matrix multiplication requirements.

[0041] The present invention uses a control vector register to control the mapping of one or both source vector elements on a per-element basis, as shown in FIG. 2. For each element position of the output vector, different bit-fields of the corresponding element of control vector register 200 provides mapping for a given vector instruction. There are two-vector mapping logic blocks, one for each of the two source vectors. The mapping logic 230 maps elements of source-1 vector register 210, and the mapping logic of 240 maps elements of source-2 vector register 220. Thus, units 230 and 240 constitute a means for mapping of a first and second source vector elements. The outputs of mapping logic 230 and 240 constitute paired source vector elements as inputs to each of plurality of computational blocks of vector computational unit 250. Each computational unit (shown as “OP”, or OPeration) 251 can perform arithmetic or logical operations on said paired source vector elements. The output of vector computational unit is stored or added to respective elements of vector accumulator 260, in accordance with a given vector operation. The contents of vector accumulator elements are clamped by clamp logic 270 and stored into selected destination vector register 280 in one embodiment. As we have seen in the above examples, efficient multiplication of matrices requires mapping of both source vectors. Each vector element mapping logic consists of multiple select logic, as shown in FIG. 3. An option to override a zero value is also provided for other vector operations of the preferred embodiment of present invention, but is not really needed for matrix operations. Each select unit, SEL-0 through SEL-(N−1) can select any one of the elements of a source vector. One of three operating modes is selected by the format logic that controls these select logic units to map elements of source vectors to be paired in accordance with a instruction format defined by a vector instruction and also control vector register element values. Table of FIG. 3 shows three different instruction formats: prior art respective elements of two source vectors and one element to be broadcast to all element positions (both shown in FIG. 1), and the general mapping of any-element of first source vector to be paired with any-element of second source vector. The opcode coding of a vector instruction determines which of the instruction formats is chosen.

[0042] The preferred embodiment maps the fields of each control vector element as follows to control the select logic for each vector element:

• • [0043] Bits 5-0: Select source element from VRs-1 vector register;
  • [0044] Bit 6: When set to one, selects zero for VRs-1
  • [0045] Bit 7: Reserved.
  • [0046] Bits 13-8: Select source element from VRs-2 vector register;
  • [0047] Bit 14: When set to one, selects zero for VRs-2
  • [0048] Bit 15: Mask bit, when set to one disables writing output for that element.
    This mapping supports up to 64 vector elements, i.e., 64-wide SIMD. If there are fewer elements, then the unused bits could be reserved as zero for possible future extension. FIG. 4 shows the operation of condition codes and mask bit. The paired elements of two source vectors are used as inputs of element-J operation unit, which shows further details of OP unit 251 from FIG. 2. The condition flag select bits are selected as part of an Opcode condition field The mask bit for a given vector element position is also provided from control vector register respective element field. The selector chooses one or combination of condition flags for each element position. The result of the condition flag selector is a binary true or false, which is logically AND'ed with the inverted mask (disable) bit. If the result of this is logical zero, then the write-back for that element position is disabled, which leaves the output element for that element position unchanged. Mask bit is not used for matrix multiplication. Condition flags could be used if the matrix multiplication we have is a conditional matrix multiplication, i.e., if we multiply under certain condition only. For example, we could specify matrix multiplication, if the input is YUV stream to change it to RGB, but leave it unchanged if the input stream is RGB.

[0049] In the preferred embodiment of present invention, the vector instruction has the following format:

<Vector Inst>[.CC] VRd, VRs-1, VRs-2, VRs-3

[0050] Where “CC” indicates one of condition flags selected as determined by the “Condition” field of opcode, and {VRd, VRs-1, VRs-2, VRs-3} are vector register designators. VRd represents a destination vector register, and VRs-1 and VRs-2 represent source vector registers. VRs-3 represents a selected control vector register as third source operand.

[0051] All vector registers sourced from a common pool of vector registers, or from an alternate vector register file. The advantage of using a separate vector register file is that it allows a single-ported register file to be use while expanding the number of available registers. The disadvantage of the using a separate vector file for control vector is that overall gate count is increased. Assembly syntax determines which format is used or chosen. If third source vector is specified as VRA, then it is sourced from alternate vector register file, and if it is specified as VR, it is sourced from primary vector register file.

[0052] The programming model of vector register for a preferred embodiment is shown in FIG. 5. VR0-VR31 is the primary vector register file. For the embodiment with 16 vector elements with 16-bits for each vector element, each vector register is 256-bits wide. Each vector element represents a 16-bit fixed point number. In other embodiments, each vector element can have more bits, or can be a floating-point number. VRA0-VRA31 is the alternate vector register file, which may or may not exist in different embodiments. VRA vector register could be used as control vector registers, or as second source operands, but not as destination vector registers. Vector Condition Flag (VCF) register contains 16 condition flags for each vector element in one embodiment, and for 16-wide SIMD VCF is 256-bits wide. One of the 16 condition flags for each vector element position is chosen by the condition field (Condition) of opcode.

[0053] The vector accumulator of preferred embodiment is 48-bits per vector element, but could have other bit widths also. The 48-bit vector element of vector accumulator is concatenated from the respective elements of three vector accumulator registers. These three components of vector accumulator are shown as high, middle, and low accumulator, where each of these is 256-bits wide for the 16-element embodiment. For the embodiment of 16-bits for each vector element, multiplication of two vectors will result in 32-bits per vector element, and summing these 32-bit interim values with a vector multiply-accumulate will require resolutions higher that 32-bits, which is within the 48-bit resolution. This allows accumulation of many interim results before a result is clamped and written into a destination vector register with 16-bit vector elements.

[0054] The two instructions of special interest for matrix multiplication are vector-multiply and vector-multiply-accumulate. The details of these instructions are given in FIGS. 6 and 7. The 32-bit Opcode for a preferred embodiment of SIMD processor consists of the following fields:

[0055]

Opcode	This is a 6-bit field that selects of the SIMD operations. This
	limits the maximum number of SIMD instructions to 64.
Dest	Specifies the destination vector register, which is
	part of the primary vector register file. This field
	selects one of the 32 primary vector registers. Not
	all instructions may require a destination vector register,
	in which case this field may be used for other purposes.
Source-1	This 5-bit field selects one of the 32 vector registers
	from primary vector register file as one of the
	source operands to a SIMD operation.
Source-2	This 5-bit field selects the second source operand for
	dual operand operations. This source operand
	could be read from either primary or alternate
	vector register file, depending upon the FORMAT
	field setting of Opcode. It is allowed to have both source-1
	and source-2 operands to be the same. This is
	useful for vector or array operations within a vector or
	array. For example, this means we could operate on
	different elements of a vector as intra vector/array operations.
Source-3	This 5-bit field specifies one of the vector
	registers from primary or alternate vector register
	file as the third source operand. Typically, the third
	source operand is used as a control vector for mapping of
	vector elements and other control of SIMD operations.
Format	This two-bit field determines the type of instruction,
	as given by table of FIG. 13.
Condition	All SIMD instructions are conditional. This 4-bit field
	determines which of the plurality of condition flags is to
	be used for each vector element for a given instruction.

[0056] The full-mapping format of vector multiply (VMUL) instruction has the format without the use of conditional operation:

[0057] VMUL VRd, VRs-1, VRs-2, VRs-3.

[0058] VRs-3 select one of the vector register as the control vector, which defines the mapping of first and second source vectors stored in vector registers defined by operand fields VRs-1 and VRs-2, respectively. The operation of VMUL instruction using pseudo c-type code for the embodiment with N vector elements per vector register and N vector operation units per vector computational unit is shown in the operation section of FIG. 6. Even though this shows sequential operation from element 0 through N−1, in actuality, operations on all vector elements are performed in parallel. The index “i” signifies a destination or output vector element position. For each destination vector element position, depending upon the format field, the type of mapping is chosen. For the full-mapping mode, bit fields of [5:0] of VRs-3 specifies the vector element number of first source vector that is mapped to that position. Similarly, bit fields of [13:8] of VRs-3 specifies the vector element number of second source vector that is mapped to that position. If bit number 6 is 1, then mapped first source vector element is treated as zero, and similarly, if bit number 14 is zero, then mapped second source vector element is treated as zero. The paired source vector elements are multiplied and stored into vector element position “i” of vector accumulator if the mask bit is zero and if the condition flag selected is true. Since all vector instructions of preferred embodiment is conditional, leaving out condition codes defaults to selection of hard-wired always-true condition (one bit of VCF is hardwired to 1 for each element). The mask bit is set to value of bit #15 of VRs-3 for position “i” for full mapping mode, and to zero for other instruction formats. The subscript values in FIG. 6 refer to the bit-field values that are used. The symbol “˜” indicates inversion. The multiplication of two 16-bit numbers per vector element of one embodiment results in 32-bit values to be stored in each element of accumulator. If mask value is one for a given vector element position or if the selected condition defined by “Condition” field of opcode of VCF register for the corresponding element is interpreted as false, neither the respective number vector accumulator element nor the respective destination vector register element is affected, and both remain unchanged. This is indicated by ˜Mask && VCF[i][Condition] in the operation of VMUL and VMAC instructions, where “&&” indicates a logical AND operation for testing. This means that mask bit has to be zero (˜ indicates bit inversion) and condition flag of VCF selected by vector element number “i” and Condition field of opcode (CC in assembly syntax), which selects one of the condition flags for a given vector element of VCF, has to be true for both respective elements of vector accumulator and respective element of vector destination register to be updated. VMAC instruction shown in FIG. 7 is very similar, except the output of vector multiply is added to the respective element of the vector accumulator.

[0059] Both VMUL and VMAC and other vector instructions support three different instruction formats (as shown in FIGS. 6 and 7 under Format section):

[0060]

	VMAC [.CC]	VRd, VRs-1, VRs-2
	VMAC [.CC]	VRd, VRs-1, VRs-2 [element]
	VMAC [.CC]	VRd, VRs-1, VRs-2, VRs-3

[0061] The first of these refer to prior art mode of vector operations on respective vector elements (see FIG. 1, standard element-to-element mode). This is the default mode, if no third source vector operand is specified. The second one refers to one-element broadcast form (see FIG. 1, one element broadcast mode). In this mode, the field of third source operand in opcode is used to code the element number of second source vector to be mapped to all element positions for pairing. Due to opcode mapping, preferred embodiment allows broadcast of only elements of second source vector. But, due to symmetry this is not a limitation (source-1 could be interchanged with source-2). The third format specifies any-element of first source vector to be paired with any element of second source vector. This is the format used for efficient implementation of matrix multiplication.

[0062] For the embodiment, where each vector element of vector register is 16-bits, and vector accumulator elements are 48-bits each, it is necessary to perform clamping to transfer results from vector accumulator to the destination vector register. Assuming the numbers have two's complement signed format, the maximum and minimum numbers possible are 0x7FFF and 0x8000, where the preamble of “0x” represents hexadecimal notation. Clamping operation is shown as “Signed-Clamp” in FIGS. 6 and 7, where if the value of accumulator is more than 0x7FFF in hexadecimal, then it is clamped to 0x7FFF. This is referred to as using saturated arithmetic. Similarly, if the result is less than 0x8000, then it is clamped to 0x8000.

[0063] The details of both VMUL and VMAC show multiplication of paired elements of first and second source as (Paired_Source_—1*Paired Source_—2])_31..0 where the subscripts of 31..0 signify that the result of two 16-bit operands is 32-bits, and that is moved to the accumulator or summed with accumulator.

[0064] Both VMUL and VMAC instructions execute at a pipelined rate of one clock cycle per instruction. The execution of VMUL and VMAC includes mapping of both source operands, multiplication, accumulation if VMAC, and signed clamping and storing into vector destination register.

[0065] FIG. 15 shows high-level view of embodiment given in FIG. 2 with using a primary vector register file to store all source and destination vector operands. The opcode format given in FIGS. 4, 6, and 7, shows only 5-bit field for source and destination operands. This means one embodiment of present invention is using vector register to vector register model architecture, where all operands have to be in vector registers (as opposed to a location in main memory). The vector register file 1500 have three read ports that correspond to reading first source operand 1510, reading second source operand 1511, and reading third source operand 1512. 5-bit fields, VRs-1, VRs-2, VRs-3, from opcode select one of the vector register VR0-VR31 for each of these read ports. Control vector is read from VRs-3 port 1512, which consists of 5-bit field for mapping first source operand, 5-bit field for mapping second source operand, and a mask bit value for each vector element position. The output of vector operation unit 250 has potentially output of 512 bits for the case of vector multiplication. Write port 1513 is used to write destination vector selected by opcode field VRd.

[0066] The two additional ports, read port 1514 and write port 1515 are used for transferring vector register values between vector register file 1500 and main memory (not shown here). In one embodiment such transfer operations are performed concurrently with vector operation of source vectors of vector register file. In another embodiment, special load and store instructions could be used without concurrency with vector operations, and in this case the ports of 1514 and 1515 could be shared with other read and write ports.

[0067] Another embodiment of present invention does not require a separate vector accumulator. If each vector element has enough resolution to store interim resolution of multiplied and accumulated vector values, then a selected vector destination register could also act as the vector accumulator. Such a case is when each vector element is, for example, capable of storing a 40-bit or larger number or a floating-point number of sufficient resolution. In this case, no separate vector accumulator is needed, as shown in FIG. 14. Also, no clamping logic is required for use of saturated arithmetic before contents of vector accumulator is transferred to selected vector destination register. The vector adder 1470 in this case either passes through the results for the case of vector-multiply, or adds the results of vector multiply to respective elements of destination vector register for the case of vector multiply-accumulate operation.

[0068] A processor typically has many stages of pipeline operation. The preferred pipelining of present invention has the following five stages of pipeline for each SIMD instruction:

• • [0069] 1. Instruction Fetch (IF);
  • [0070] 2. Instruction Decode and Register Decode (ID/RD);
  • [0071] 3. Execute-1: Contains vector arithmetic or logical operations;
  • [0072] 4. Execute-2: Stage where intermediate results are stored into vector accumulator;
  • [0073] 5. Write-Back (WB): Stage where signed-clamped and saturated vector accumulator values are stored back into the vector register file.
  • [0074] Multiplexing of both source elements are done as part of the ID/RD stage. Alternatively, we could add another stage for the mapping operation for increased pipeline clock rate.
    Implementation of H.264 DCT Operation

[0075] Let us assume we have a 16-wide embodiment of SIMD processor. Then it would take four SIMD arithmetic instructions as shown below to implement the multiplication of two 4×4 matrices. In this case, multiplying a column vector of 4 elements with a corresponding row vector of 4 values generate 16 values in a 4-by-4 matrix (refer back to FIG. 11, 1180). But, since SIMD has 16 vector arithmetic units, we could calculate partial products for all 16 output element positions in parallel. If this were not the case, such as with a 8-wide SIMD, we would have to divide the output matrix into 4-by-2 or 2-by-4 matrices and use a different mapping of for each step.

[0076] The mapping for operation on each decomposed column changes because we assumed all elements of both matrices are preloaded in one step and only once, thereby requiring a different mapping for each step of decomposition (instead of loading new values for each column and row at each step). Since four mapping vectors could be preloaded in four different vector register and can remain unchanged, this is more optimal. Assuming one vector load instruction to load first matrix into vector register VR1, and one vector load instruction to load second matrix into VR2, DCT operation would require a total of eight SIMD arithmetic instructions (vector load instructions not shown here).

[0077]

	VMUL	VR0, VR1, VR2, VR3;
	VMAC	VR0, VR1, VR2, VR4;
	VMAC	VR0, VR1, VR2, VR5;
	VMAC	VR0, VR1, VR2, VR6;

Where VR1 contains all the 16 values of first 4×4 matrix, and VR2 contains all the values of second 4×4 matrix. The last instruction adds the last partial product to the vector accumulator, and then clamps the accumulator values to 16-bits and stores in VR0. Loading a vector register requires a single vector load instruction. We have not shown the loading of VR1, VR2 and the VRA0-3 here. We assume VR3-6 are preloaded with the mapping values as follows:

[0078]

VR3 =	{0, 0, 0, 0, 4, 4, 4, 4, 8, 8, 8, 8, 12, 12, 12, 12} +
	{0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3} << 8;
VR4 =	{1, 1, 1, 1, 5, 5, 5, 5, 9, 9, 9, 9, 13, 13, 13, 13} +
	{4, 5, 6, 7, 4, 5, 6, 7, 4, 5, 6, 7, 4, 5, 6, 7} << 8;
VR5 =	{2, 2, 2, 2, 6, 6, 6, 6, 10, 10, 10, 10, 14, 14, 14, 14} +
	{8, 9, 10, 11, 8, 9, 10, 11, 8, 9, 10, 11, 8, 9, 10, 11} << 8;
VR6 =	{3, 3, 3, 3, 7, 7, 7, 7, 11, 11, 11, 11, 15, 15, 15, 15} +
	{12, 13, 14, 15, 12, 13, 14, 15, 12, 13, 14, 15, 12, 13, 14, 15} << 8;

It is important to note that each step of mapping involves mapping only four values (a column or row vector) into 16 output matrix positions. We used a shifted sum of two vector values for the purpose of readability that is calculated at assembly time (“<<” denotes shifting left by number of bits following it). The mapping values were derived from Table of FIG. 11 assuming row-sequential ordering of both matrices in memory.

[0079] The outputs of the first three vector instructions in VR0 is not important, as they are only partial results, and vector accumulator has the full resolution interim value. Only at the last step that final vector accumulator value clamped and stored into VR0, which carries final result, and at this point vector accumulator values could be discarded or overwritten in subsequent vector operations.