Method and apparatus for parallel shift right merge of data

Method and device for parallel right shifting and merging of data

This patent application is a continuation of a part of U.S. Patent Application No. 09/952,891 filed on October 29, 2001, entitled "Efficient Filtering and Convolution Apparatus and Method for Content Data".

This patent application is related to a co-pending US patent application No. 10/280,612 named "Fast Full Search Motion Estimation Using SIMD Combining Instructions" filed on October 25, 2002.

Technical field

The present invention generally relates to the field of microprocessors and computer systems. More specifically, the present invention relates to a method and apparatus for parallel right shift and merge of data.

Background technique

With the development of processor technology, people are also creating newer software codes to run on machines with these processors. Users generally expect and need higher performance from their computers, regardless of the type of software used. One such problem may arise from the types of instructions and operations that are actually executed in the processor. Based on the complexity of the operation and/or the type of circuit required, certain types of operations require more time to complete. This provides an opportunity to optimize the way certain complex operations are performed within the processor.

For more than a decade, multimedia applications have been driving the development of microprocessors. In fact, most of the computing progress in recent years has been driven by multimedia applications. These developments are mainly in the consumer sector, although many important developments have also been witnessed in the corporate sector for more entertaining education and communications. However, future multimedia applications will be eager for higher computing requirements. As a result, the personal computing (PC) experience of tomorrow will be richer in audio-visual effects and easier to use, and more importantly, computing will be integrated with communication.

Therefore, the display of images and the playback of audio and video data have become more and more popular applications for current computing devices. Here, the images, audio, and video data are collectively referred to as content. Filtering and convolution operations have entered the list of the most common operations performed on content data such as image, audio, and video data. As is well known by those skilled in the art, filtering and correlation calculations are performed using multiplication-accumulation operations that add the product of data and coefficients. The correlation between the two vectors A and B is formed by the calculation of the sum S: S[k]=1NΣi=0N-1a[i]·b[i+k],]]>Equation (1) always let k =0: S[0]=1NΣi=0N-1a[i]·b[i]]]>Equation (2) If the N-tap filter f is applied to the vector V, the sum S is calculated as follows: S =Σi=0N-1f[i]·V[i]]]>Equation (3) These operations are computationally intensive, but provide a high level of data parallelism, which can be achieved by using various data Efficient implementations of storage devices such as single instruction multiple data (SIMD) registers take advantage of this degree of parallelism.

There are applications of filtering operations in a large number of image and video processing tasks and communications. Animation Expert Group (MPEG) attenuation of mosaic in video, attenuation of noise and audio, decoupling watermark from pixel value to improve watermark detection, used to smooth, sharpen, attenuate the correlation of noise, find image or video frame Edge and scaling its size, up sampling of video frames for sub-pixel motion estimation, improvement of audio signal quality, and pulse shaping and equalization signals in communications are all examples of the use of filters. Therefore, filtering and convolution operations are very important for computing devices that provide playback of content including image, audio, and video data.

Unfortunately, current methods and instructions are not comprehensive in terms of general requirements for filtering. In fact, many architectures do not support efficient filter calculations for multiple filter lengths and data types. In addition, data storage devices such as SIMD registers generally do not support data sorting, and the ability to add adjacent values to the registers and to transfer part of the data between the registers. As a result, the current architecture requires some unnecessary data type changes, which minimizes the number of operations per instruction and greatly increases the number of clock cycles for sorting data for arithmetic operations.

Description of the drawings

In the accompanying drawings, the present invention has been illustrated by way of illustration and not limitation, in which similar reference numerals indicate similar elements, and: Fig. 1 shows a block diagram illustrating a computer system capable of implementing an embodiment of the present invention; Figure 2 shows a block diagram illustrating an embodiment of the processor shown in Figure 1 according to another embodiment of the present invention; Figure 3 illustrates a block diagram illustrating a combination according to another embodiment of the present invention Packed data type; FIG. 4A illustrates a combined byte representation in a register according to an embodiment of the present invention; FIG. 4B illustrates a combined word representation in a register according to an embodiment of the present invention; FIG. 4C illustrates A combined double word representation in a register according to an embodiment of the present invention; Figure 5 shows a block diagram illustrating the operation of a byte shuffling instruction according to an embodiment of the present invention; Figure 6 shows a block diagram, Shows the operation of a byte multiply-accumulate instruction according to an embodiment of the present invention; FIGS. 7A-7C show a plurality of block diagrams, illustrating another embodiment of the present invention, which is similar to that shown in FIG. 6 The byte shuffle instruction of Figure 5 is combined with the byte multiply-accumulate instruction to generate multiple summed-product pairs (summed-product 8A-8D shows multiple block diagrams, illustrating an adjacent-add instruction according to another embodiment of the present invention; Figure 9A-9B shows another embodiment of the present invention Register merge instructions; Figure 10 shows a block diagram illustrating a flow chart of efficient data processing of content data according to an embodiment of the present invention; Figure 11 shows a block diagram illustrating another method, with To process content data according to a data processing operation according to another embodiment of the present invention; Figure 12 shows a block diagram illustrating a flow chart of continuing to process content data according to another embodiment of the present invention; Figure 13 shows A block diagram is shown, illustrating a flow chart, showing a register merging operation according to another embodiment of the present invention;

Fig. 14 shows a flowchart illustrating another method for selecting unprocessed data elements from a source data storage device according to an exemplary embodiment of the present invention; Fig. 15 is a processor of an embodiment Figure 16A is a block diagram of an embodiment of a logic that performs parallel right shift and merge operations on data operands according to the present invention; Figure 16A is a block diagram of an embodiment of logic that performs parallel right shift and merge operations on data operands according to the present invention; Fig. 16B is a block diagram of another embodiment of the logic for executing the right shift merge operation; Fig. 17A illustrates the operation of the parallel right shift merge instruction according to the first embodiment of the present invention; Fig. 17B illustrates the second embodiment according to the present invention Example of the operation of the right shift merge instruction; Figure 18A is a flowchart illustrating an embodiment of the method of parallel right shift and merge data operands; Figure 18B is a flowchart illustrating the right shift and merge data Another embodiment of the method; Figures 19A-B illustrate an example of motion estimation; Figure 20 illustrates an example application of motion estimation and result prediction; Figure 21A-B illustrates an exemplary current process that is processed during motion estimation And the previous frame; FIGS. 22A-D illustrate the operation of performing motion estimation on a frame according to an embodiment of the present invention; and FIGS. 23A-B are a flowchart illustrating an embodiment of a method of predicting and estimating motion.

detailed description

The invention discloses a method and a device for performing parallel right shifting and merging of data. The invention also discloses a method and device for efficient filtering and convolution of content data. The invention also discloses a method and device for fast full search motion estimation by using SIMD merging operation. The embodiments described herein are described in the context of a microprocessor, but are not limited to this context. Although the following embodiments are described for processors, other embodiments are also applicable to other types of integrated circuits and logic devices. The same techniques and teachings of the present invention can be easily applied to other types of circuits or semiconductors, which can benefit from higher pipeline throughput and improved performance. The teachings of the present invention are applicable to any processor or machine that performs data manipulation. However, the present invention is not limited to processors or machines that perform 256-bit, 128-bit, 64-bit, 32-bit, or 16-bit data operations, but can be applied to any processor or machine that needs to right shift and merge data.

In the following description, for the purpose of explanation, a large number of specific details are given to provide a thorough understanding of the present invention. However, those skilled in the art should realize that these specific details are not necessary for implementing the present invention. In other cases, some well-known electrical structures and circuits are not given in detail so as not to unnecessarily obscure the present invention. In addition, the following description provides a number of examples, and the drawings show various examples for explanation. However, these examples should not be construed as restrictive, as they are only used to provide some examples of the present invention, not to provide an exhaustive list of all possible implementations of the present invention.

In the embodiment, the method of the present invention is embodied in machine-executable instructions. These instructions can be used to make a general-purpose or special-purpose processor programmed with these instructions execute the steps of the present invention. Alternatively, the steps of the present invention can be performed by specific hardware components containing hardwareized logic for performing the steps, or by any combination of programmed computer components and customized hardware components.

The present invention can be provided as a computer program product or software. The product or software can include a machine or a computer-readable medium on which is stored a computer (or other electronic device) that can be used to program a computer (or other electronic device) to perform the processing according to the present invention. instruction. These software can be stored in the memory in the system. Similarly, the code can be distributed via a network or other computer-readable media. The computer-readable medium may include, but is not limited to, floppy disks, optical disks, compact disks (CD-ROM), magneto-optical disks, read-only memory (ROM), random access memory (RAM), erasable programmable read-only Memory (EPROM), electrically erasable programmable read-only memory (EEPROM), magnetic or optical card, flash memory, transmission on the Internet, etc.

Correspondingly, the computer-readable medium includes any type of medium/machine-readable medium suitable for storing or transmitting electronic instructions or information in a form readable by a machine (for example, a computer). Moreover, the present invention can also be downloaded as a computer program product. In this manner, the program can be transferred from a remote computer (e.g., server) to a requesting computer (e.g., client). The transmission of the program may be completed via a communication link (for example, a modem, a network connection, etc.) through electricity, light, sound, or other forms of data signals contained in a carrier wave or other media.

In modern processors, multiple different execution units are used to process and execute a variety of codes and instructions. Not all instructions are created the same, because some instructions complete faster, while other instructions may take a lot of clock cycles. The faster the instruction throughput rate, the better the overall performance of the processor. Therefore, it would be advantageous to make as many instructions as possible to execute as quickly as possible. However, some instructions have higher complexity and require more execution time and processor resources. For example, floating-point instructions, load/store operations, data movement, etc.

As more and more computer systems are used in Internet and multimedia applications, some other processor support has also been introduced. For example, single instruction multiple data (SIMD) integer/floating point instructions and SIMD streaming extension (SSE) are instructions that can reduce the total number of instructions required to execute a specific program job. These instructions can improve software performance by operating on multiple data elements in parallel. As a result, performance gains can be obtained in a large number of applications, including video, voice, and image/photo processing. Implementing SIMD instructions in microprocessing and similar types of logic circuits usually involves multiple issues. Moreover, the complexity of SIMD operations often requires additional circuitry to properly process and manipulate data.

The embodiment of the present invention provides a way to implement the parallel right shift instruction as an algorithm using SIMD related hardware. For one embodiment, the algorithm is based on the following idea: shift the expected number of data segments from one operand to the most significant bit side of the second operand, and at the same time shift the same number of data segments out of the least significant side of the second operand Bit side. In theory, the right shift merge operation can be regarded as merging two data blocks into one block, and shifting the combined blocks to align the data segments at the expected positions, thereby forming a new mode of data . In this way, the embodiment of the right shift merge algorithm according to the present invention can be implemented in the processor to efficiently support SIMD operations without severely impairing overall performance.

Computing Architecture Figure 1 shows a computer system 100 on which an embodiment of the present invention can be implemented. The computer system 100 includes a bus 101 for transferring information, and a processor 109 coupled to the bus 101 for processing information. The computer system 100 also includes storage subsystems 104-107, which are coupled to the bus 101 to store information and instructions for the processor 109.

The processor 109 includes an execution unit 130, a register file 200, a cache memory 160, a decoder 165, and an internal bus 170. The cache memory 160 is coupled to the execution unit 130 and stores frequently and/or recently used information for the processor 109. The register file 200 stores information in the processor 109 and is coupled to the execution unit 130 through the internal bus 170. In an embodiment of the present invention, the register file 200 includes multimedia registers, such as SIMD registers, for storing multimedia information. In one embodiment, each multimedia register can store up to 128 bits of combined data. The multimedia register can be a dedicated multimedia register, or a register used to store multimedia information and other information. In one embodiment, the multimedia register stores multimedia data when performing multimedia operations, and stores floating point data when performing floating-point operations.

The execution unit 130 performs an operation on the packed data (packed data) according to the instructions received by the processor 109 and included in the combined instruction set 140. data) to operate. The execution unit 130 also operates on scalar data according to instructions implemented in a general-purpose processor. The processor 109 can support the Pentium(R) microprocessor instruction set and the combined instruction set 140. By including the combined instruction set 140 in the standard microprocessor instruction set such as the Pentium® microprocessor instruction set, the combined data instructions can be easily included in the existing software (software previously written for the standard microprocessor instruction set) . According to the invention described here, other standard instruction sets can also be used, such as PowerPCTM and AlphaTM processor instruction sets. (Pentium® is a registered trademark of Intel Corporation, PowerPCTM is a trademark of IBM, Apple Computer, and Motorola, and AlphaTM is a trademark of Digital Equipment Corporation.) In one embodiment, the combined instruction set 140 includes multiple instructions (below Will be described in detail) for: mobile data (MOVD) operation 143 and data shuffling operation (PSHUFD) 145, used to organize data in a data storage device; for the combination of an unsigned first source register and a signed second source register Type multiplication and accumulation (PMADDUSBW operation 147); combined type multiplication and accumulation operation (PMADDUUBW operation 149), used to perform multiplication and accumulation on the unsigned first source register and the unsigned second source register; used for the signed first and second source registers Combined multiply and accumulate for two source registers (PMADDSSBW operation 151); and standard multiply and accumulate for signed first and second source registers containing 16-bit data (PMADDWD operation 153). Finally, the combined instruction set includes adjacent add instructions for adding adjacent bytes (PAADDNB operation 155), words (PAADDNWD operation 157), double words (PAADDNDWD159), double word values (PAADDWD 161), 2 Words to obtain a 16-bit result (PAADDNWW operation 163), 2 quadwords to obtain a quad word result (PAADDNDD operation 165), and a register merge operation 167.

By including the combined instruction set 140 in the instruction set of the general-purpose processor 109 and related circuit systems for executing the instructions, the combined data in the general-purpose processor can be used to perform many operations used by existing multimedia applications. Therefore, by using the full width of the processor data bus to perform operations on combined data, many multimedia applications can be executed faster and more efficiently. This eliminates the need to transfer smaller data units on the processor bus to perform one or more operations one data element at a time.

Still referring to FIG. 1, the computer system 100 of the present invention may include a display device 121, such as a monitor. The display device 121 may include an intermediate device such as a frame buffer. The computer system 100 may also include an input device 122 such as a keyboard, and a cursor control 123 such as a mouse, or a trackball or trackpad. The display device 121, the input device 122, and the cursor control 123 are coupled to the bus 101. The computer system 100 may also include a network connector 124 so that the computer system 100 is part of a local area network (LAN) or a wide area network (WAN).

In addition, the computer system 100 may be coupled to a device 125 for recording and/or playback, such as an audio digitizer coupled to a microphone for recording sound input used for speech recognition. The computer system 100 may also include a video digitizing device 126 that can be used to capture video images, a hard copy device 127 such as a printer, and a CD-ROM device 128. The devices 124-128 are also coupled to the bus 101.

Processor FIG. 2 shows a detailed schematic diagram of the processor 109. The processor 109 may be implemented on one or more substrates using any of a variety of processing technologies, such as BiCMOS, CMOS, and NMOS. The processor 109 includes a decoder 202 for decoding control signals and data used by the processor 109. The data can then be stored in the register file 200 through the internal bus 205. For the sake of clarity, the registers of the embodiments should not be limited to refer to a specific type of circuit. In contrast, the registers of the embodiments only need to be able to store and provide data, and perform the functions described herein.

Depending on the data type, the data can be stored in the integer register 201, the register 209, the status register 208, or the instruction pointer register 211. Other registers, such as floating point registers, may be included in the register file 200. In one embodiment, the integer register 201 stores 32-bit integer data. In one embodiment, the register 209 includes 8 multimedia registers, R0212a to R7212h, such as SIMD registers containing combined data. The length of each register in the register 209 is 128 bits. R1 212a, R2 212b, and R3 212c are examples of a single register in the register 209. The 32 bits of the register in the register 209 can be moved to an integer register in the integer register 201. Similarly, the value in the integer register can be moved to the 32 bits of one of the registers 209.

The status register 208 indicates the status of the processor 109. The instruction pointer register 211 stores the address of the next instruction to be executed. The integer register 201, the register 209, the status register 208, and the instruction pointer register 211 are all connected to the internal bus 205. Any other registers can also be connected to the internal bus 205.

In another embodiment, some of these registers can be used for two different types of data. The register 209 and the integer register 201 may be combined, where each register may store integer data or combined data. In another embodiment, the register 209 may be used as a floating-point register. In this embodiment, combined data or floating point data can be stored in the register 209. In one embodiment, the length of the combined register is 128 bits, and the integer can be represented as 128 bits. In this embodiment, when storing combined data and integers, the register does not have to distinguish between these two data types.

The function unit 203 performs operations performed by the processor 109. These operations can include shifts, additions, subtractions, multiplications, and so on. The functional unit 203 is connected to the internal bus 205. The cache memory 160 is an optional element of the processor 109 and can be used to cache data and/or control signals from, for example, the main memory 104. The cache memory 160 is connected to the decoder 202 and is connected to receive the control signal 207.

Data and Storage Format FIG. 3 illustrates three combined data types: combined byte 221, combined word 222, and combined double word (dword) 223. The combined word 222 is 128 bits long and contains 16 combined byte data elements. Generally, a data element is a single data segment, and the data element is stored in a single register (or memory unit) together with other data elements of the same length. In a combined data sequence, the number of data elements stored in the register is equal to 128 bits divided by the bit length of the data element.

The combined word 222 is 128 bits long and contains 8 combined word data elements. Each combined word data element contains 16 bits of information. The combined double word 223 is 128 bits long and contains 4 combined double word data elements. Each combined double word data element contains 32 bits of information. The combined four-word is 128 bits long and contains 2 combined four-word data elements.

4A-4C illustrate a combined data storage representation in a register according to an embodiment of the present invention. The representation 310 in the unsigned combined byte register illustrates the storage of the unsigned combined byte 201 in one of the multimedia registers 209, as shown in FIG. 4A. The information of each byte data element is stored as follows: Bits 7 to 0 are used for the 0th byte, bits 15 to 8 are used for the 1st byte, and bits 23 to 16 are used for The second byte, and the last 120th to 127th bits are used for the 15th byte.

In this way, all available bits are used in the register. This storage arrangement improves the storage efficiency of the processor. Moreover, 16 data elements have been accessed, and an operation can now be performed on 16 data elements at the same time. The representation 311 in the signed combined byte register illustrates the storage of the signed combined byte 221. Note that the 8th bit of each byte data element is the sign indicator.

The unsigned combined word register representation 312 illustrates how the 7th to 0th words are stored in the register in the multimedia register 209, as shown in FIG. 4B. The representation 313 in the signed combined word register is similar to the representation 312 in the unsigned combined word register. Note that the 16th bit of each word data element is the sign indicator. The representation 314 in the unsigned combined double word register shows how the multimedia register 209 stores two double word data elements, as shown in FIG. 4C. The representation 315 in the signed combined double word register is similar to the representation 314 in the unsigned combined double word register. Note that the required sign bit is the 32nd bit of the double word data element.

Efficient filtering and convolution of content data as taught by the present invention starts with loading the data and filtering/convolution coefficients to the data source device. In many cases, before performing arithmetic calculations, it is necessary to change the order of data or coefficients in a data storage device such as a single instruction multiple data (SIMD) register. Correspondingly, efficient filtering calculations and convolutions require not only appropriate arithmetic instructions, but also efficient methods for organizing data required for calculations.

For example, using the symbols in the background art section, the image is filtered by replacing the value of pixel I given by S[I], for example. In the filtering calculation of S[I], the values of the pixels on both sides of the pixel I are used. Similarly, the pixels on both sides of the pixel I+1 are needed to calculate S[I+1]. Therefore, in order to calculate the filtering result of more than 1 pixel in the SIMD register, it is necessary to copy and arrange the data in the SIMD register for calculation.

Unfortunately, the current computing architecture lacks an efficient method to arrange all data of the appropriate data size within the computing architecture. Accordingly, as shown in FIG. 5, the present invention includes a byte shuffling instruction (PSHUFB) 145, which efficiently sorts data of any size. During the shuffling operation, by maintaining the relative position of bytes within the larger data, the byte shuffling operation 145 sorts data sizes larger than bytes. In addition, the byte shuffling operation 145 can change the relative position of the data in the SIMD register, and can also copy the data.

Referring again to FIG. 5, FIG. 5 shows an example of a byte shuffling operation 145 for a filter with 3 coefficients. Using conventional techniques, filter coefficients (not shown) are applied to 3 pixels, and then the filter coefficients are transferred to another pixel and applied again. However, in order to perform these operations in parallel, the present invention describes a new instruction for arranging the data. Correspondingly, as shown in FIG. 5, by using the mask 402 to specify the storage address of each data element in the target register 406, the data 404 is organized in the target data storage device 406. The target data storage device 406 is in an embodiment The middle is the source data storage device 404. In one embodiment, the arrangement of the mask is based on the desired data processing operations, which may include, for example, filtering operations, convolution operations, and so on.

Accordingly, using the mask mask 402, the processing of the data 406 and the coefficients can be performed in parallel. In the example described, the source data storage device 404 is a 128-bit SIMD register, which initially stores 16 8-bit pixels. In this way, when a pixel filter with 3 coefficients is used, the fourth coefficient is set to zero. In one embodiment, depending on the number of data elements in the source data storage device 404, the source register 404 may be used as a target data storage device or register, thereby reducing the number of necessary registers compared to usual. In this manner, the overwritten data in the source data storage device 404 can be reloaded from the memory or another register. In addition, multiple registers can be used as the source data storage device 404, with their respective data organized in the target data storage device 406 as desired.

Once the sorting of data elements and coefficients is completed, the data and corresponding coefficients must be processed according to data processing operations. Those skilled in the art can recognize that different precision calculations are required for filter calculations and convolution calculations using different numbers of filter coefficients and data sizes. The most basic filter operation is to multiply two pairs of numbers and add their products. This operation is called a multiply-accumulate instruction.

Unfortunately, the current computing architecture does not provide support for efficient multiply-accumulate instructions using multiple filter lengths and multiple data sizes with signed or unsigned coefficients. In addition, byte operations are not supported. As a result, traditional computer architectures must use decombining instructions to convert 16-bit data. These computer architectures generally include support for certain multiply-accumulate operations that calculate the product of 16-bit data in different registers, and then add adjacent products to give a 32-bit result. This scheme is acceptable for filter coefficients that require 16-bit precision data, but for 8-bit filter coefficients, in 8-bit data (common for images and videos), Instruction and data level parallelism is wasted.

Referring now to FIG. 6, FIG. 6 shows the first source register 452 and the second source register 454. In one embodiment, the first and second source registers are N-bit long SIMD registers, such as 128-bit Interl(R) SSE2 XMM registers. The multiply and accumulate instructions implemented on this register can give the following results of the two pixel vectors 452 and 454, which are stored in the target register 456. Correspondingly, this example shows an 8-bit byte to 16-bit word multiply-accumulate instruction, called PMADDUSBW operation 147 (Figure 1), where U and S in the instruction refer to unsigned and signed bytes. Help memorize. The byte in one of the source registers is signed, and the byte in the other is unsigned.

In an embodiment of the present invention, the register with unsigned data is the target and the 16-bit multiplication and accumulation result. The reason for this choice is that in most implementations, the data is unsigned and the coefficients are signed. Correspondingly, the data is preferably overwritten, because it is unlikely that the data will be needed in future calculations. As shown in FIG. 1, the PMADDUUBW operation 149 for unsigned bytes in the two registers and the PMADDSSBW operation 151 for signed bytes in the two source registers are additional byte multiply-accumulate instructions. The multiply-accumulate instruction is completed by the PMADDWD instruction 153, which is applied to a 16-bit signed word pair to obtain a 32-bit signed product.

As in the general case of filtering operations, the second vector generally contains filter coefficients. Correspondingly, in order to prepare the XMM register, the coefficient can be loaded into a part of the register and copied to the rest of the register using the shuffle instruction 145. For example, as shown in FIG. 7A, in response to the execution of the data load instruction, the coefficient data storage device 502, such as an XMM 128-bit register, is initially loaded with 3 coefficients. However, those skilled in the art will recognize that the filter coefficients can be organized in memory before data processing. In this way, prior to filtering, based on its organization in the memory, initially the coefficients can be loaded as shown in Figure 7B.

In this manner, the coefficient register 502 contains filter coefficients F3, F2, and F1, which can be encoded as signed or unsigned bytes. Once the coefficient register 502 is loaded, the existing command PSHUFD can be used to copy the filter coefficients to the rest of the coefficient register to obtain the following result as shown in FIG. 7B. As shown in Figure 7B, the coefficient register 504 now contains coefficients that are shuffled as needed to perform data processing operations in parallel. As is well known by those skilled in the art, it is very common to include a filter with 3 coefficients in an image processing algorithm. However, those skilled in the art will recognize that certain filtering operations such as JPEG 2000 utilize 9 and 7 16-bit coefficients. Correspondingly, the processing of these coefficients exceeds the capacity of the coefficient register, resulting in partial filtering results. Therefore, processing continues until the final result is obtained using each coefficient.

Referring now to FIG. 7C, FIG. 7C shows the arrangement of pixel data in the source register 506, which is initially contained in the source register 404 as shown in FIG. 5 and shuffled in the target register 406. Accordingly, in response to the execution of the data processing operation, using the result stored in the target register 510, the PMADDUSBW instruction can be used to calculate the sum of two multiplications. Unfortunately, in order to complete the calculation and produce the data processing result for the selected data processing operation, adjacent pairs of accumulated products in the target register 510 must be added.

Correspondingly, if the sum of the multiply and accumulate instructions is longer than 2 pixels (this is very common), different sums must be added. Unfortunately, the current computing architecture does not provide an efficient algorithm for adding adjacent sums, because adjacent sums are located in the same target register. Correspondingly, the present invention utilizes adjacent addition instructions, and the results are shown in Figures 8A-8D.

Referring now to FIG. 8A, FIG. 8A shows the addition of 2 adjacent 16-bit values (PAADD2WD operation 157) to give a 32-bit and subsequent target register 552. In this manner, FIG. 8A shows two adjacent 16-bit results of the multiply-accumulate instruction, and the two 16-bit results are added to give the 32-bit sum of the 4-byte product. Figure 8B shows an adjacent add instruction (PAADD4WD operation 157) which adds 4 adjacent 16-bit values to give a 32-bit sum. In this way, the 4 adjacent 16-bit results of the byte multiplication accumulate instruction are added to give the 32-bit sum of the 8-byte product. Figure 8C illustrates an adjacent addition instruction (PAADD8WD operation 157), which adds 8 adjacent 16-bit values to give a 32-bit sum. As such, this example illustrates 8 adjacent 16-bit results of a byte multiplication and accumulation operation, which are added to give a 32-bit sum of 16-byte products.

Accordingly, the selection of instructions to perform adjacent addition operations is based on the number (N) of turns in the sum. For example, using a 3-tap filter as shown in FIGS. 7A-7C, the first instruction (PAADD2WD operation 157) will obtain the following result as shown in FIG. 8D. However, for the association of two 16-bit pixel vectors (such as the first row of a macro block), the last instruction (PAADD8WD operation 157) is used, as shown in FIG. 8C. As SIMD registers increase in size, this kind of operation becomes more and more important for an efficient implementation. Without this kind of operation, many other instructions are needed.

In this way, the adjacent addition instruction set according to the present invention supports a large number of adjacent values that can be added and a large number of common data types. In one embodiment, the addition of adjacent 16-bit values includes a set of instructions (PAADDNWD operation 157), whose range starts by adding 2 adjacent values (N=2), and doubling the number of additions It is 4 (N=4) and then 8 (N=8), up to the total number in the register. The data size of the 16-bit adjacent addition is 32 bits. In another alternative embodiment, adjacent 16-bit values are added (PAADDWD operation 161) to obtain a 32-bit sum.

In this alternative embodiment, other instructions with a 16-bit data size are not included because adjacent addition instructions with 32-bit inputs are used to add the sum generated by instructions with 16-bit inputs. Both embodiments include a set of 32-bit adjacent addition instructions (PAADDNDWD operation 159), whose range starts by adding 2 adjacent values (N=2), and doubling the number of additions to 4 (N = 4), then 8 (N=8) and so on, up to the total number in the register. The data size of the sum of 32-bit adjacent additions is 32 bits. In some cases, the result does not fill the register. For example, in the instructions shown in Figures 8A, 8B, and 8C, 3 different adjacent additions produce 4, 2, and 1 32-bit results. In one embodiment, the result is stored in the lower, least significant portion of the target data storage device.

Correspondingly, when there are two 32-bit results, as shown in FIG. 8B, the results are stored in the lower 64 bits. In the case of a 32-bit result, as shown in Figure 8C, the result is stored in the lower 32 bits. As those skilled in the art recognize, some applications make use of the sum of adjacent bytes. Using the instruction of adding 2 adjacent signed bytes to give a 16-bit word (PAADDNB operation 155) and the instruction of adding 2 adjacent unsigned bytes to give a 16-bit word result, the present invention supports byte The adjacent addition. Applications that need to add more than 2 adjacent bytes use the appropriate 16-bit adjacent addition operation to add the 16-bit sum of the two bytes together.

Once the result of the data processing operation has been calculated, the next operation returns the result to the storage device. As illustrated in the above embodiment, the result can be encoded with 32-bit precision. Therefore, simple move operations that operate on double words, such as the above-mentioned MOVD operation 143, and logic right shift operations (PSRLDQ) that operate on the entire register, and double quadword logic right shift operations, can be used to write the result back Memory. In this way, writing all the results back to the memory will require 4 MOVDs and 3 PSRLDQs in the first case (Figure 8A), and 2 MOVDs and 1 PSRLDQ in the second case (Figure 8B), and In the last case, only 1 MOVD is needed, as shown in Figure 8C.

Unfortunately, although the adjacent addition operation as shown in FIG. 7C can be performed in parallel, the filtering calculation generally requires the next pixel in the image. Therefore, it is necessary to load one or more pixels in the source data storage device or register. In order to avoid loading 8 pixels in the register each time, two schemes have been proposed for this operation. In one embodiment, the present invention describes a register merge operation 163, as shown in Figure 9A. In this manner, in order to process the pixels A1-A8 in the target register 606, the pixels A7-A1 and the pixel A8 are concatenated to form the pixels A8-A1 in the target register 606. Correspondingly, the register merge operation uses the number of bytes to select the register, which is provided by the input argument.

Referring now to FIG. 9B, FIG. 9B shows an alternative embodiment for performing a register merge operation. Initially, 8 pixels are loaded into the first source register 608 (MM0). Then, the next 8 pixels are loaded into the second source register (MM1) 610. Then, a permute operation is performed on the second source register 610. Once executed, the register 610 is copied to the third source register (MM2) 612. Then, the first source register 608 is shifted to the right by 8 bits. In addition, the second source register 610 and the mask register 614 are combined according to a combinational logical AND (AND) instruction and stored in the first source register 608.

Then, a logical OR (OR) operation is performed between the second source register 610 and the first source register 608 to produce the following result in the target register 620 to form a register merge operation. The process continues as shown by shifting the first source register 608. Then, the second source register 610 is shifted to generate a register 612. Then, a logical AND operation is performed between the mask register 614 and the second source register 612, and the result is stored in the target register 622. Finally, a combined OR operation is performed between the second source register 612 and the first source register 608 to generate a subsequent register merge operation in the target register 624. A procedural method for implementing the teachings of the present invention will now be described.

Operation Referring now to FIG. 10, FIG. 10 shows a block diagram illustrating a method 700 for efficiently performing filtering and convolution of content data in, for example, the computer system 100 shown in FIGS. 1 and 2. As described herein, content data refers to image, audio, video, and voice data. In addition, as recognized by those skilled in the art, the data storage device referred to in the present invention includes various devices capable of storing digitized data, including, for example, data registers, such as 128-bit Intel(R) architecture SSE2 MMX registers.

Referring again to FIG. 10, the method begins at processing block 702, where it is determined whether to perform a data processing operation. As described herein, data processing operations include, but are not limited to, convolution and filtering operations performed on pixel data. Once executed, processing block 704 is executed. At processing block 704, a data load instruction is executed. In response to the execution of the data load instruction, at processing block 706, the input data stream data is loaded into the source data storage device 212A and the auxiliary data storage device 212B, for example, as shown in FIG. 2.

At processing block 708, it is determined whether a data shuffling instruction has been executed by the data processing operation. In response to the execution of the data shuffle instruction, at processing block 710, a part of the data selected from, for example, the source data storage device 212B is organized in the target data storage device, or organized according to the arrangement of the coefficients in the coefficient data storage device (see FIG. 5). ). The coefficients in the coefficient data storage device are organized according to the expected data processing operation calculations (as shown in FIGS. 7A and 7B). In one embodiment, before any filtering operation, the coefficients are organized in memory. Accordingly, the coefficients can be loaded into the coefficient data storage without shuffling the cards (see Figure 7B).

As mentioned above, data and coefficients need to be sorted to achieve parallel calculations, as required for data processing operations, as shown in Figures 7A-7C. However, since the coefficients are known before the data processing operation, the coefficients can be organized in the memory so that they can be loaded into the register as organized in the memory, without the need to shuffle the coefficients during the data processing operation. Finally, in processing block 720, the loaded data is processed according to the data processing operation to generate one or more data processing results. Once generated, the result of the data processing operation can be written back to the memory.

Referring now to FIG. 11, FIG. 11 shows a block diagram illustrating a method 722 for processing data according to a data processing operation. At processing block 724, it is determined whether the data processing operation has executed a multiply and accumulate instruction. In response to the execution of the multiply-accumulate instruction, in processing block 726, a plurality of accumulated product pairs of data are generated in the target storage device, and coefficients are generated in the coefficient data storage device, as shown in FIG. 7C. Then, in processing block 728, it is determined whether the data processing operation has executed the adjacent add instruction.

In response to the execution of adjacent additions, in processing block 730, in response to the execution of adjacent additions, the adjacent accumulation product pairs in the target data storage device 510 (FIG. 7C) are added to form one or more processing operation results (See Figure 8D). However, in some embodiments, if the number of coefficients exceeds the capacity of the coefficient register (see processing block 732), partial data processing results will be obtained. Therefore, continue to process and organize the coefficients (processing block 734) and data (processing block 736) until the final data processing operation result is obtained, as shown in optional processing blocks 732-736. Otherwise, at processing block 738, the one or more data processing operation results are stored. Finally, at processing block 790, it is determined whether the processing of the input data stream data is completed. In this manner, processing blocks 724-732 are repeated until the processing of the input data stream data is completed. Once processing is complete, control flow returns to processing block 720, where method 700 terminates.

Referring now to FIG. 12, FIG. 12 shows a block diagram illustrating another method 740 for processing other input data. At processing block 742, it is determined whether there is any unaccessed data in the source data storage device 212A. As described herein, unaccessed data refers to data in the source data storage device 212A that has not been shuffled in the data storage device to execute the multiply-accumulate instruction. When the data storage device contains unaccessed data, in processing block 744, a part of the data from the source data storage device is selected as the selected data. Once selected, processing block 786 is executed.

Otherwise, in processing block 746, select the first one or more unprocessed data from the source data storage device and select one or more data elements from the auxiliary data storage device. As described here, unprocessed data elements refer to data elements for which the results of data processing operations have not yet been calculated. Then, in processing block 780, a register merge instruction (see FIGS. 9A and 9B) is executed, which concatenates the unprocessed data elements of the source data storage device with the data elements selected from the auxiliary data storage device to form selected data. Then, at processing block 782, the data from the auxiliary data storage device is transferred to the source data storage device.

In this way, the source data storage device data is no longer needed because it has already been accessed. Accordingly, auxiliary storage data containing unaccessed data can be used to overwrite the data in the source data storage device. At processing block 784, the input data stream data from the memory device is loaded into the auxiliary data storage device, and the data requires other data processing, such as filtering or convolution. Finally, in processing block 786, the selected data is organized in the target data storage device, or organized according to the arrangement of the coefficients in the coefficient data storage device (see FIG. 5). Once executed, the control flow returns to processing block 790, as shown in Figure 11, to continue processing of the selected data.

Referring now to FIG. 13, FIG. 13 shows another method 748 for selecting unprocessed data elements. At processing block 750, it is determined whether the source data storage device contains unprocessed data. When every part of the data in the source data storage device has been processed, processing block 770 is executed. In processing block 770, a part of data is selected from the auxiliary data storage device as selected data, and then processed according to the data processing operation.

Otherwise, at processing block 752, one or more unprocessed data elements are selected from the source data storage device. Finally, in processing block 766, according to the count of unprocessed data elements, other data elements are selected from the auxiliary data storage device to form selected data. In this manner, the data selected for shuffling in the target data storage device before performing the data processing operation is limited to the count of data elements based on the number of filter coefficients. Accordingly, using this data element count, the number of unprocessed data elements is subtracted from the data element count to determine the number of elements that need to be selected from the auxiliary data storage device in order to perform the register merge operation.

Finally, referring to FIG. 14, FIG. 14 shows another method 754 for selecting unprocessed data elements of the processing block 752, as shown in FIG. At process block 756, a data element is selected from the source data storage device. Then, in processing block 758, it is determined whether the data processing operation result has been calculated for the data element. When this result has been calculated, the selected data element is discarded. Otherwise, in processing block 760, the selected data element is an unprocessed data element, and it is stored. Then, at processing block 762, the unprocessed data element count is incremented. Finally, in processing block 764, processing blocks 756-762 are repeated until each data element in the source data storage device has been processed.

In this way, using the teaching of the present invention, unnecessary data type changes can be avoided, and the number of SIMD operations per instruction can be maximized. In addition, the number of clock cycles required to sort data for arithmetic operations is greatly reduced. Correspondingly, Table 1 shows estimated speedups for several filtering applications using the teachings and instructions of the present invention.

Table 1

Alternate embodiments have described several aspects of an implementation of a computing architecture for providing efficient data filtering and convolution using SIMD registers. However, various implementations of the computing architecture provide a large number of features that include, complete, supplement, and/or replace the above-mentioned features. In different implementations, multiple features can be implemented as part of a computing architecture, or as part of specific software or hardware components. In addition, for illustrative purposes, the foregoing description uses specific terminology to provide a thorough understanding of the present invention. However, it is clear to those skilled in the art that these specific details are not required to implement the present invention.

In addition, although the embodiment described here relates to a system that uses SIMD registers for efficient filtering and convolution of content data, it is clear to those skilled in the art that the teachings of the present invention can also be applied to other system. In fact, systems for processing image, audio and video data are all within the teachings of the present invention without departing from the spirit and scope of the present invention. The above-mentioned embodiments are chosen and described in order to best illustrate the principle of the present invention and its practical application. These embodiments are selected to enable those skilled in the art to make the best use of the present invention and various embodiments with various modifications suitable for the specific use under consideration.

The embodiments of the present invention provide many advantages over known technologies. The present invention includes an ability to efficiently implement filtering/convolution operations for a variety of array lengths, data sizes, and coefficient signs. These operations are achieved by using some instructions that are part of a small group of single instruction multiple data (SIMD) instructions. Accordingly, the present invention avoids unnecessary data type conversion. As a result, by avoiding unnecessary data type conversion, the present invention maximizes the number of SIMD operations per instruction, while greatly reducing the number of clock cycles required for data sorting for arithmetic operations such as multiplication and accumulation operations.

FIG. 15 is a block diagram of the micro-architecture of the processor of an embodiment, which includes a plurality of logic circuits to perform the parallel right shift merge operation according to the present invention. The right shift merge operation can also be referred to as the register merge operation and the register merge instruction, as described above. For an embodiment of the right shift merge instruction (PSRMRG), the instruction obtains the same result as the register merge operation 167 of FIGS. 1, 9A and 9B. The in-order front end 1001 is a part of the processor 1000, which fetches multiple macro-instructions to be executed, and prepares them for later use in the processor pipeline. The front end of this embodiment includes several units. The instruction prefetcher 1026 fetches macro instructions from the memory and feeds them to the instruction decoder 1028, which then decodes them into micro instructions or micro operations (also called micro ops or uops) Primitives, the machine knows how to execute these primitives. The trace cache 1030 obtains the decoded uops, and assembles them into a program sequence or trace in the uop queue 1034 for execution. When the trace buffer 1030 encounters a complex macro instruction, the microcode ROM 1032 provides the required uop to complete the operation.

Many macro instructions are converted into a single micro op, while other macro instructions require several micro ops to complete the entire operation. In this embodiment, if more than 4 micro ops are needed to complete the macro instruction, the decoder 1028 accesses the microcode ROM 1032 to execute the macro instruction. In one embodiment, if multiple micro ops are needed to complete the operation, the instructions for the parallel right shift merge algorithm can be stored in the microcode ROM 1032. The trace buffer 1030 refers to the entry point programmable logic array (PLA) to determine a correct microinstruction pointer, which is used to read the microcode sequence for the shift merge algorithm in the microcode ROM 1032. After the microcode ROM 1032 completes the micro op serialization for the current macro instruction, the front end 1001 of the machine resumes fetching the micro op from the trace cache 1030.

Some SIMD and other multimedia-type instructions are considered complex instructions. Most floating-point related instructions are also complex instructions. In this way, when the instruction decoder 1028 encounters a complex instruction, it accesses the appropriate location of the microcode ROM 1032 to obtain the microcode sequence for the macro instruction. Each micro op required to execute the macro instruction is transferred to the out-of-order execution engine 1003 for execution at the appropriate integer and floating point execution units.

The out-of-order execution engine 1003 is where microinstructions are prepared for execution. The out-of-order execution logic has multiple buffers, which are used to smooth and reorder the flow of micro-instructions when the micro-instructions go down the pipeline and are scheduled for execution to optimize performance. The allocator logic allocates the machine buffers and resources required by each uop for execution. The register renaming logic renames the logical register to the entry in the register file. The allocator also allocates an entry for each uop in one of the two uop queues before the instruction scheduler. One of the two queues is used for memory operations and the other is used for non-memory operations. The instruction scheduler is: memory A scheduler, a fast scheduler 1002, a slow/universal floating-point scheduler 1004, and a simple floating-point scheduler 1006. The uop scheduler 1002, 1004, 1006 determines when the uop is ready to execute based on the degree of readiness of their related input register source operands and the availability of execution resources required by the uop to complete their operations. The fast scheduler 1002 of this embodiment can schedule once every half of the main clock cycle, while other schedulers can only schedule once per clock cycle of the main processor. The scheduler arbitrates the distribution port to schedule uop for execution.

The register files 1008, 1010 are located between the scheduler 1002, 1004, 1006 and the execution units 1012, 1014, 1016, 1018, 1020, 1024 in the execution module 1011. There are separate register files 1008 and 1010 for integer and floating-point operations. Each register file 1008, 1010 of this embodiment also includes a bypass network, which can bypass the result that has just been completed but has not yet been written into the register file, or forward it to a new related uop. The integer register file 1008 and the floating point register file 1010 can also send data to each other. For one embodiment, the integer register file 1008 is divided into two independent register files, one register file is used for the low-end 32 bits of data, and the other register file is used for the high-end 32 bits of data. The floating-point register file 1010 of one embodiment has 128-bit wide entries because floating-point instructions generally have operands ranging from 64 to 128-bit wide.

The execution module 1011 includes execution units 1012, 1014, 1016, 1018, 1020, 1024, in which instructions are actually executed. This part includes register files 1008, 1010, which store integer and floating point data operands required for microinstruction execution. The processor 1000 of this embodiment is composed of multiple execution units: address generation unit (AGU) 1012, AGU 1014, fast ALU 1016, fast ALU 1018, slow ALU 1020, floating point ALU 1022, floating point move unit 1024 . For this embodiment, the floating point execution module 1022, 1024 performs floating point, MMX, SIMD, and SSE operations. The floating-point ALU 1022 of this embodiment includes a 64-bit division by 64-bit floating-point divider to perform division, square root, and remainder microops. For the embodiments of the present invention, any action involving floating point values is related to floating point hardware. For example, the conversion between integer format and floating-point format involves floating-point register files. Similarly, floating-point division operations are performed at the floating-point divider. On the other hand, non-floating-point numbers and integer types are handled by integer hardware resources. Simple and frequently occurring ALU operations are executed by high-speed ALU execution units 1016 and 1018. The fast ALUs 1016 and 1018 of this embodiment can perform fast operations with an efficient delay of half a clock cycle. For one embodiment, most complex integer operations are performed by the slow ALU 1020 execution, because the slow ALU 1020 includes integer execution hardware for long-latency type operations, such as multiplication, shifting, flag logic, and branch processing. The memory load/store operation is performed by AGU 1012, 1014. For this embodiment, integer ALUs 1016, 1018, 1020 are described in the context of performing integer operations on 64-bit data operands. In alternative embodiments, ALUs 1016, 1018, and 1020 can be implemented to support multiple data bit widths, including 16, 32, 128, 256, and so on. Similarly, the floating point units 1022, 1024 can be implemented to support multiple operands with different bit widths. For one embodiment, the floating-point units 1022, 1024 can combine SIMD and multimedia instructions to operate on 128-bit wide combined data operands.

In this embodiment, the uop scheduler 1002, 1004, 1006 distributes related operations before the parent loading is completed. Since uop is scheduled and executed predictively in the processor 1000, the processor 1000 also includes logic for handling memory misses. If the data loading is missing in the data cache, there may be an in-flight related operation in the pipeline, which has provided the scheduler with temporarily incorrect data. The replay mechanism can track and re-execute instructions that use incorrect data. Only related operations need to be played back, and related operations can be completed. The scheduler and playback mechanism of one embodiment of the processor is also designed to capture instruction sequences for use in extended precision integer division operations.

The term "register" is used here to refer to the on-board processor storage unit, which is used as part of the microinstructions to identify operands. In other words, the registers referred to here are those that are visible outside the processor (from the programmer's perspective). However, the registers described herein can be implemented by circuits within the processor using any number of different techniques, such as dedicated physical registers, dynamically allocated physical registers using register renaming, a combination of dedicated and dynamically allocated physical registers, and so on. For the following discussion, it should be understood that the register is a data register designed to hold combined data, such as the 64-bit wide MMXTM register (mm register) in the microprocessor of Intel Corporation of Santa Clara, California. The microprocessor uses MMX technology. These processors have both integer and floating point forms, and can operate on combined data elements accompanied by SIMD and SSE instructions. Similarly, 128-bit wide XMM registers related to SSE2 technology can also be used to hold this combined data operand.

In the example of the following figures, multiple data operands are described. For simplicity, the data segments are labeled alphabetically from letter A upwards, where A is located at the lowest address and Z is located at the highest address. In this way, A can be at address 0, B at address 1, C at address 2, and so on. Although the data sequence in some examples appears in reverse alphabetical order, addressing still starts with A at 0, B at 1, and so on. Theoretically, as in the right shift merge of an embodiment, if the sequence is D, C, B, A, the right shift operation causes the lower address data segment to be shifted out to the right. In this way, shifting to the right simply shifts the data elements of the data block to the right across a fixed line. Moreover, in theory, the right shift merge operation can move the rightmost data segment from one operand to the left of the other data operand, as if the two operands are continuous.

Fig. 16A is a block diagram showing an embodiment of logic for performing parallel right shift merge operations on data operands according to the present invention. The right shift merge (and register shift) instruction (PSRMRG) used in this embodiment starts with 3 pieces of information: a first data operand 1102, a second data operand 1103, and a shift count 1106. In one embodiment, the shift PSRMRG instruction is decoded into a micro operation. In another embodiment, the instruction can be decoded into a different number of micro ops to perform a shift and merge operation on the data operand. For this example, the data operands 1102, 1104 are 64-bit wide data stored in the register/memory, and the shift count 1106 is an 8-bit wide immediate value. Depending on the specific implementation, the data operand and the shift count can have other widths, such as 128/256 bits and 16 bits, respectively. The first operand 1102 in this example consists of 8 data segments: P, O, N, M, L, K, J, and I. The second operand 1104 also consists of 8 data segments: H, G, F, E, D, C, B, and A. The data segments here have equal length, and each consists of a single byte (8 bits) of data. However, another embodiment of the present invention uses a longer 128-bit operand to operate, wherein each of the data segments is composed of a single byte (8 bits), and the 128-bit wide operand may have 16 A single-byte wide data segment. Similarly, if each data segment is double-word (32-bit) or quad-word (64-bit), the 128-bit operand can have 4 double-word wide or 2 quad-word wide data segments, respectively. Therefore, the embodiments of the present invention are not limited to data operands, data segments, or shift counts of a specific length, but may have an appropriate size for each implementation.

Operands 1102, 1104 may reside in registers or memory units or register files or mixed structures. The data operands 1102, 1104, and count 1106 are sent to the execution unit 1110 in the processor along with the right shift merge instruction. When the right shift merge instruction reaches the execution unit 1110, the instruction should have been decoded in advance in the processor pipeline. Therefore, the right shift merge instruction may have a micro-operation (uop) form or other decoded format. For this embodiment, two data operands 1102, 1104 are received at the concatenated logic and temporary registers. The concatenation logic merges/joins the data segments of the two operands and places the new data block in a temporary register. Here, the new data block includes 16 data segments: P, O, N, M, L, K, J, I, H, G, F, E, D, C, B, A. Since this embodiment works with 64-bit wide operands, the temporary register required to hold the combined data is 128 bits wide. For 128-bit wide data operands, 256-bit wide temporary registers are required.

The right shift logic 1114 in the execution unit 1110 obtains the contents of the temporary register, and executes a logical right shift of n data segments on the data block, as requested by the count 1106. In this embodiment, the count 1106 represents the number of bytes to be shifted right. Depending on the specific embodiment, the count 1106 can also be used to indicate the number of bits, nibbles, words, double words, quad words, etc. to be shifted, depending on the granularity of the data segment. For this embodiment, n is equal to 3, so the contents of the temporary register are shifted by 3 bytes. If each data segment is word or double word wide, the count indicates the number of words or double words to be shifted, respectively. For this embodiment, when the data in the temporary register is shifted to the right, 0 is shifted from the left side of the register to fill the vacant space. Therefore, if the shift count 1106 is greater than the number of data segments in the data operand (in this case 8), then one or more zeros may appear in the result number 1108. Moreover, if the shift count 1106 is equal to or exceeds the total number of data segments of the two operands, the result number will consist of all zeros because all data segments will be removed. The right shift logic 1114 outputs the appropriate number of data segments from the temporary register as the result number 1108. In another embodiment, an output multiplexer or latch may be included after the right shift logic to output the result number. For this embodiment, the result number is 64 bits wide and includes 8 bytes. Due to the right shift and merge operation of the two data operands 1102, 1104, the result number is composed of the following 8 data segments: K, J, I, H, G, F, E, and D.

Fig. 16B is a block diagram showing another embodiment of logic for performing a right shift merge operation. Similar to the previous example in FIG. 16A, the right shift merge operation of this embodiment starts with 3 items of information: a 64-bit wide first data operand 1102, a 64-bit wide second data operand 1104, and an 8-bit wide Shift right counts 1106. The shift count 1106 indicates the number of positions to be shifted in the data segment. For this embodiment, the count 1106 is expressed in bytes. In another embodiment, the count may represent the number of bits, nibbles, words, double words, or quad words to shift the data. The first operand 1102 in this example consists of 8 equal-length, byte-sized data segments (H, G, F, E, D, C, B, A), and the second operand 1104 consists of 8 Data segment (P, O, N, M, L, K, J, I) is composed. The count n is equal to 3. Another embodiment of the present invention can be operated with operands and data segments of other lengths, such as 128/256/512 bit wide operands, data segments with bit/byte/word/doubleword/quadword calculation size, and 8/16/32 bit wide shift count. Therefore, the embodiments of the present invention are not limited to data operands, data segments, or shift counts of a specific length, but may have an appropriate size for each implementation.

The data operands 1102, 1104, and count 1106 are sent to the execution unit 1120 in the processor along with the right shift merge instruction. For this embodiment, the first data operand 1102 and the second data operand 1104 are received at the left shift logic 1122 and the right shift logic 1124, respectively. The count 1106 is also sent to the shift logic 1122, 1124. The left shift logic 1122 shifts the data segment of the first operand 1102 to the left by "the number of data segments in the first operand-n" data segments. When the data segment is moved to the left, 0 is moved in from the right to fill the vacant space. In this case, there are 8 data segments, so the first operand 1102 is shifted to the left by 8 minus 3 or 5 positions. The first operand 1102 is shifted by this different value, and the correct data alignment is obtained to merge at the logical OR gate 1126. After shifting to the left, the first operand becomes: K, J, I, O, O, O, O, O. If the count 1106 is greater than the number of data segments in the operand, the left shift calculation can produce a negative number, indicating a negative left shift. A logical left shift with a negative count can be understood as a negative shift, which is essentially a logical right shift. A negative left shift will introduce 0 from the left side of the first operand 1102.

Similarly, the right shift logic 1124 shifts the data segment of the second operand to the right by n segments. When the data segment is moved to the right, 0 is moved from the left to fill the vacant position. The second data operand becomes: O, O, O, H, G, F, E, D. The shifted operands are output from the left/right shift logic 1122, 1124 and merged together at the logic OR gate 1126. The OR gate performs the logical OR of the data segment and provides the 64-bit wide result number 1108 of this embodiment. The OR operation of "K, J, I, O, O, O, O, O" and "O, O, O, H, G, F, E, D" produces a result number including 8 bytes 1108: K , J, I, H, G, F, E, D. This result is the same as the result of the first embodiment in FIG. 16A. Note that for a count n 1106 that is greater than the number of data elements in the operand, an appropriate number of zeros can begin to appear on the left of the result number. Moreover, if the count 1106 is greater than or equal to the total number of data elements in the two operands, the result number consists of all zeros.

FIG. 17A illustrates the operation of the parallel right shift merge instruction according to the first embodiment of the present invention. For these discussions, MM1 1204, MM2 1206, TEMP 1232, and DEST 1242 generally refer to operands or data blocks, but are not limited to these, but also include registers, register files, and memory cells. In one embodiment, MM1 1204 and MM2 1206 are 64-bit wide MMX registers (also referred to as "mm" in some cases). At state I 1200, the shift count imm[y] 1202, the first operand MM1[x] 1204, and the second operand MM2[x] 1206 are sent along with the parallel right shift merge instruction. The count 1202 is an immediate value of wide y bits. The first operand 1204 and the second operand 1206 are data blocks including x data segments, and if each data segment is one byte (8 bits), each operand has a total width of 8x bits. Each of the first operand 1204 and the second operand 1206 is composed of multiple smaller data segments. For this example, the first data operand MM1 1204 is composed of 8 data segments of equal length: P1211, O 1212, N 1213, M 1214, L 1215, K 1216, J 1217, I 1218. Similarly, the second data operand MM2 1206 is composed of 8 data segments of equal length: H 1221, G1222, F 1223, E 1224, D 1225, C 1226, B 1227, A 1228. Each of these data segments is'x×8' bits wide. Therefore, if x is 8, each operand is 8 bytes or 64 bits wide. For other embodiments, the data elements may be nibbles (4 bits), words (16 bits), double words (32 bits), quad words (64 bits), and so on. In another embodiment, x may be 16, 32, 64, etc. data elements wide. For this embodiment, the count y is equal to 8, and the immediate number can be expressed as one byte. For other embodiments, y can be a bit width of 4, 16, 32, etc. Also, the count 1202 is not limited to being an immediate value, and may also be stored in a register or a memory unit.

Operands MM1 1204 and MM2 1206 are merged together at state II 1230 to form a temporary data block TEMP[2x] 1232, which is 2x data elements (or bytes, in this case) wide. The combined data 1232 of this example consists of 16 data segments arranged as: P, O, N, M, L, K, J, I, H, G, F, E, D, C, B, and A. An 8-byte wide window 1234 surrounds the 8 data segments of the temporary data block 1232, starting from the rightmost edge. Therefore, the right edge of the window 1234 will be aligned with the right edge of the data block 1232, so that the window 1234 surrounds the data segments: H, G, F, E, D, C, B, and A. The shift count n 1202 represents the required amount to shift the combined data to the right. The count value can be implemented to specify the shift amount in units of bits, nibbles, bytes, words, double words, quad words, etc. or the number of specific data segments. Here, based on the count value 1202, the data block 1232 is shifted to the right by 1236 n data segments. For this example, n is equal to 3, and the data block 1232 is moved 3 positions to the right. Another way to look at this problem is to shift the window 1234 in the opposite direction. In other words, the window 1234 can theoretically be regarded as moving 3 positions from the right edge of the temporary data block 1232 to the left. For one embodiment, if the shift count n is greater than the total number of data segments that appear in the combined data block 2x, the result number will consist of all zeros. Similarly, if the shift count n is greater than or equal to the number of data segments x in the first operand 1204, the result number contains one or more zeros from the left. At the state III 1240, the data segment (K, J, I, H, G, F, E, D) enclosed by the window 1234 is output as the result number to the target DEST[x] 1242 with a width of x data elements.

FIG. 17B shows the operation of the right shift merge instruction according to the second embodiment. In the state I 1250, the right shift merge instruction has a count imm[y] with y bits, a first data operand MM1[X] with x data segments, and a second data operand MM2 with x data segments. [x]. As in the example of Figure 17A, y is equal to 8 and x is equal to 8, where each of MM1 and MM2 is 64 bits or 8 bytes wide. In this embodiment, the first operand 1204 and the second operand 1206 are composed of multiple data segments of the same size. In this case, each data segment is one byte wide, respectively "P 1211, O 1212, N 1213, M 1214, L 1215, K1216, J 1217, I 1218" and "H 1221, G 1222, F 1223, E 1224, D1225, C 1226, B 1227, A 1228".

At state II 1260, the first operand 1204 and the second operand 1206 are shifted using the shift count n 1202. The count in this embodiment indicates the number of data segments for which the merged data will be shifted to the right. For this embodiment, the shift occurs before the merge of the first operand 1204 and the second operand 1206. As a result, the first operand 1204 is shifted in a different manner. In this example, the first operand 1204 is shifted to the left by xn data segments. The calculation of xn takes into account the correct data alignment at the subsequent data merging. Therefore, for the count n whose value is 3, the first operand 1204 is shifted to the left by 5 data segments or 5 bytes. Move in 0 from the right to fill the vacant position. However, if the shift count n 1202 is greater than the number x of data segments in the first operand 1204, the left shift calculation xn may generate a negative number, which essentially represents a negative left shift. In one embodiment, a logical left shift with a negative count is interpreted as a negative left shift, which is essentially a logical right shift. A negative left shift will introduce 0 from the left side of the first operand 1204. Similarly, the second operand 1206 is shifted to the right by 3 shift counts, and 0 is shifted from the left to fill the vacant position. The shift results held for the first operand 1204 and the second operand 1206 are stored in registers TEMP1 1266 and TEMP2 1268 with x data segment widths, respectively. At state III 1270, will come from TEMP1 1266 and TEMP2 The shift results of 1268 are combined together 1272 to generate the desired shift combined data at the register DEST 1242. If the shift count n 1202 is greater than x, one or more zeros may be included from the left in the result number. Moreover, if the shift count 1202 is equal to 2x or greater, the result count in DEST 1242 will consist of all zeros.

In the above examples such as FIGS. 17A and 18B, one or both of MM1 and MM2 may be a 64-bit data register in a processor with MMX/SSE technology, or a 128-bit data register with SSE2 technology. Depending on the implementation, these registers can be 64/128/256 bits wide. Similarly, one or both of MM1 and MM2 may be register units instead of registers. In the processor architecture of one embodiment, MM1 and MM2 are the source operands of the right shift merge instruction (PSRMRG), as described above. For this PSRMRG instruction, the shift count IMM is also an immediate value. For one embodiment, the target location DEST of the result number is also an MMX or XMM data register. Also, DEST can be the same register as one of the source operands. For example, in one architecture, the PSRMRG instruction has a first source operand MM1 and a second source operand MM2. The predefined target location of the result number can be the register of the first source operand, in this case MM1.

Fig. 18A is a flowchart showing an embodiment of a method for parallel right shifting of merged data operands. Here, the length value L is generally used to indicate the width of the operand and the data block. Depending on the specific embodiment, L can be used to specify the width calculated according to the number of data segments, bits, bytes, words, etc. At block 1302, a first operand of length L is received for the execution of the shift and merge operation. At block 1304, the second operand of the length L of the shift and merge instruction is also received. At block 1306, a shift count is received, and the shift count represents the number or distance of data segments in units of bits/nibbles/bytes/words/doublewords/quadwords. At block 1308, the execution logic concatenates the first operand and the second operand. For one embodiment, a temporary register with a length of 2L maintains a concatenated data block. In another embodiment, the combined data is maintained in the memory cell. At block 1310, the concatenated data is shifted right according to the shift count. If the count is expressed as a data segment count, the data block is shifted to the right according to the number of data segments, and 0 is shifted from the left along the most significant bit end of the data block to fill the vacant position. If the count is expressed in bits or bytes, for example, the data block is similarly shifted to the right by the distance. At block 1312, a result number of length L is generated from the right side or the least significant end of the shifted data block. For one embodiment, the data segment of length L is multiplexed from the shifted data block to the target register or memory unit.

FIG. 18B shows a flowchart of another embodiment of a method for shifting merged data to the right. At block 1352, the first data operand of length L is received for the processing of the right shift merge operation. At block 1354, a second data operand of length L is received. At block 1356, a shift count indicating the required right shift distance is received. At block 1358, based on the calculation with the shift count, shift the first data operand to the left. The calculation of one embodiment includes subtracting the shift count from L. For example, if the operand length L and the shift count are calculated based on the data segment, the first operand is shifted to the left by "L-shift count" segments, and 0 is shifted from the least significant end of the operand. Similarly, if L is expressed in bits and the count is expressed in bytes, the first operand is shifted to the left by "L-shift count × 8" bits. At block 1360, the second data operand is shifted to the right according to the shift count, and 0 is shifted from the most significant end of the second operand to fill the vacant position. At block 1362, the shifted first operand and the shifted second operand are merged together to produce a result number of length L. For one embodiment, the merging produces a result containing the desired data segment from the first and second operands.

An increasingly popular computer application involves the manipulation of extremely large video and audio files. Even though these videos and audios are generally transmitted through a network with a very high bandwidth or a large-capacity storage medium, data compression is still required to handle the traffic. As a result, different compression algorithms are becoming an important part of the representation or coding schemes of many popular audio, image, and video formats. Video according to one of the Animation Expert Group (MPEG) standards is an application that uses compression. Split MPEG video into a hierarchical structure with multiple layers to facilitate error handling, random search and editing, and synchronization.

For the purpose of illustration, the layers that make up an MPEG video will be briefly described. At the top level is the video sequence layer, which includes a self-contained bitstream. The second layer down is a group of pictures, which is composed of one or more groups of intra-frames and/or non-intra frames. The third layer down is the picture layer itself, and the next layer is the slice layer. Each picture strip is a continuous sequence of raster-ordered macroblocks, which is most often line-based in typical video applications, but is not limited to this. Each stripe is composed of a plurality of macroblocks, the macroblock is a 16×16 array of luminance pixels or image data elements, and has two 8×8 arrays of associated chrominance pixels. The macro block can be further divided into different 8×8 blocks for further processing, such as transform coding. A macro block is the basic unit of motion compensation and motion estimation, and may have a motion vector associated with it. Depending on the embodiment, the macro block may have 16 rows×16 columns or multiple dimensions.

A temporal prediction technique used in MPEG video is based on motion estimation. Motion estimation is based on the assumption that consecutive video frames are basically similar, except for changes caused by object movement within the frame. If there is no motion between frames, the encoder can easily and efficiently predict the current frame as a copy of the previous or predicted frame. The previous frame can also be referred to as a reference frame. In another embodiment, the reference frame may be the next frame or even some other frame in the sequence. The motion estimation embodiment does not need to compare the current frame with the previous frame. Therefore, any other frame can be used in the comparison. Then, the information that must be transmitted to the encoder becomes the syntactic overhead required to reconstruct the image from the initial reference frame. However, if there is movement between images, the situation is more complicated. The difference between the best matching macroblock and the current macroblock is ideally multiple zero values. When encoding a macroblock, the difference between the best matching macroblock and the current macroblock is transformed and quantified. For one embodiment, the quantized value is passed to the variable length encoding component for compression. Since 0 can be compressed well, the best match with many 0 differences is expected. The motion vector can also be derived from the difference.

Fig. 19A illustrates a first example of motion estimation. The frame 1402 on the left is a sample of the previous video frame, including a villain and a road sign. The frame 1404 on the right is a sample of the current video frame, including a similar villain and road sign. In the current frame 1404, the shaking of the lens causes the road sign to move to the lower right from its initial position in the previous frame 1402. The villain with arms raised in the current frame is also shifted downward from its center position in the previous frame 1402 to the right. The motion estimation algorithm can be used to adequately represent the changes between the two video frames 1402, 1404.

For one embodiment, the motion estimation algorithm performs a comprehensive two-dimensional (2D) spatial search to obtain each luminance macroblock. Depending on the implementation, motion estimation may not be directly applied to chrominance in MPEG video, because color motion can be adequately represented by the same motion information as brightness. Many different ways can be used to implement motion estimation, and the specific scheme used to perform motion estimation depends to a certain extent on the complexity vs. quality of the specific application. A complete and exhaustive search of a wide 2D area generally yields the best matching result. However, this operation is accompanied by a huge computational cost, because motion estimation is often the most computationally intensive part of video coding. Attempting to reduce the cost by limiting the range of pixel search or the type of search may lose some video quality.

Fig. 19B illustrates an example of macroblock search. Each of the frames 1410, 1420 includes a plurality of macroblocks. The target macroblock 1430 of the current frame is the current macroblock to be matched with the previous macroblocks from the previous frames 1410, 1420. In the first frame 1410, the bad matching macroblock 1412 contains a part of road signs and is a bad match of the current macroblock. In the second frame 1420, the good matching macroblock 1420 contains a small part of the road signs and the head of the villain, which is similar to the current macroblock 1430 to be encoded. The two macroblocks 1422, 1430 have a certain degree of commonality, and there is only a slight error. Because a relatively good match is obtained, the encoder assigns the motion vector to the macroblock. These vectors indicate how far the macroblock needs to be moved horizontally and vertically in order to achieve a match.

Figure 20 illustrates an example application of motion estimation and the resulting prediction in generating the second frame. The previous frame 1510 comes before the current frame 1520 in time. For this example, the current frame 1520 is subtracted from the previous frame 1510 to obtain a less complex residual error image 1530, which can be encoded and transmitted. The previous frame 1510 of this example includes a road sign 1511 and a villain 1513. The current frame 1520 includes a road sign 1521 and two villains 1522, 1523, which are located on the board 1524. The more accurate the motion estimation and matching, the more likely the residual error is to be close to 0, and higher coding efficiency can be obtained. Macroblock prediction helps reduce the size of the search window.

Efficient coding can be achieved by taking advantage of the fact that motion vectors tend to be highly correlated between macroblocks. Therefore, the horizontal component can be compared with the previous effective horizontal motion vector, and the difference can be coded. Similarly, the vertical component difference can be calculated before encoding. For this example, subtracting the current frame 1520 from the previous frame 1510 produces a residual image 1530 that includes the second villain 1532 with the arm raised and the board 1534. This residual image 1530 is compressed and transmitted. Ideally, this residual image 1530 is simpler to encode and requires less memory than compressing and transmitting the entire current frame 1520. However, not every macroblock search will result in an acceptable match. If the encoder determines that there is no acceptable match, the specific macroblock is encoded.

21A-B illustrate exemplary current frame 1601 and previous frame 1650 processed during motion estimation. The previous frame 1650 precedes the current frame 1601 in the time sequence of the video frame series. Each frame is composed of a large number of pixels that extend across the frame in the horizontal and vertical directions. The current frame 1601 includes a plurality of macroblocks 1610, 1621-1627, arranged in horizontal and vertical directions. For this embodiment, the current frame 1601 is divided into equal-sized and non-overlapping macroblocks 1610, 1621-1627. Each of these square macroblocks is further divided into an equal number of rows and columns. For the same macro block 1610, a matrix with 8 rows and 8 columns can be obtained. Each square of the macro block 1610 corresponds to a single pixel. Therefore, this sample macroblock 1610 includes 64 pixels. In other embodiments, the macroblock has a dimension of 16 rows and 16 columns (16×16). For one embodiment, the data of each pixel includes 8 data bits or one word. In other embodiments, the data of each pixel can have other sizes, including nibbles, words, double words, quad words, and so on. Attempt to match these current macroblocks of the current frame with macroblocks in the previous frame 1650 for use in motion estimation.

For this embodiment, the previous frame 1650 includes a search window 1651, where a portion of the frame is surrounded by the search window 1651. The search window 1651 includes an area in which an attempt is made to match the current macroblock from the current frame 1601. Similar to the current frame, the search window is divided into multiple macroblocks of equal size. An exemplary macroblock 1660 with 8 rows and 8 columns is illustrated here, but the macroblock may include various other dimensions, including 16 rows and 16 columns. In the motion estimation algorithm of one embodiment, each single macroblock from the search window 1651 is sequentially compared with the current macroblock from the current frame to find an acceptable match. For one embodiment, the upper left corner of the first previous macroblock in the search window 1651 is aligned with the upper left corner of the search window 1651. In a motion estimation algorithm, the direction of macroblock processing starts from the left side of the search window and proceeds pixel by pixel to the right edge. Therefore, the leftmost edge of the second macroblock is one pixel away from the left edge of the search window, and so on. At the end of the first pixel row, the algorithm returns to the left edge of the search window and starts from the first pixel of the next row. This process is repeated until the macroblock of each pixel in the search window 1651 has been compared with the current macroblock.

Figures 22A-D illustrate the operation of motion estimation of a frame according to an embodiment of the present invention. The embodiments of the invention discussed herein relate to a full search motion estimation algorithm. Using the full search, an attempt is made to match the macroblocks at all pixel positions in the search window of the previous frame (reference frame) with the macroblocks from the current frame. For one embodiment, the fast full search motion estimation algorithm uses the SIMD right shift merge operation to quickly process the combined data in the frame. The SIMD right shift merge operation of an embodiment can also improve processor performance by reducing the number of data loads, especially unaligned memory loads, and other data manipulation instructions. Generally speaking, the following pseudo code can be used to describe the motion estimation process of an embodiment: for (each current block in the x and y directions) {for (search for all modulo 1 positions in the y axis of the window) {for (search All mod 4 positions in the x-axis of the window) {load pixel data from the memory to the register; perform block matching for 4 adjacent previous frames; track the minimum value and index position of the previous frame; }}} one of the blocks The matching operation requires: for (each row from row 1 to row m) {for (starting from each macro block from column 1 to column 4) {From the data held in the register to this previous [row ] Generate correct data; evaluate data [row] + = the sum of absolute difference (current [row], previous [row]);}}.

Therefore, for this embodiment, the previous macroblock at each pixel position in the search window is evaluated relative to the current macroblock. As described above, this embodiment evaluates 4 neighboring previous macroblocks per cycle. Use the memory alignment load instruction to load the pixel data from the memory to the register. By using the right shift merge operation, this pixel data can be manipulated to form various combinations of shifted data segments suitable for adjacent macroblocks. For example, the first, second, third, and fourth pixels on the first row of the first previous macroblock may start at memory addresses 0, 1, 2, and 3, respectively. For the first pixel on the first row of the second previous macroblock, the pixel starts at memory address 1. In this way, the right shift and merge operation of the register data can generate necessary pixel row data for the second previous macroblock by multiplexing the data loaded from the memory into the first previous macroblock, thereby saving time and resources. A similar shift and merge operation can generate line data for other adjacent previous macroblocks, such as the third and fourth previous macroblocks, and so on.

In this way, the block matching process of the motion estimation algorithm of an embodiment can be described with the following pseudo code: block matching of 4 adjacent previous macroblocks {for (each row from the 1st row to the mth row) {= Load pixel data for one row of the current macroblock; load two consecutive pixel data blocks from the memory into the register aligned for one row of the search window; through the right shift merge operation, the 4 from the loaded data Each of the two adjacent previous macroblocks produces a suitable pixel data row; for each of the four adjacent previous macroblocks, the calculation of the row from the previous macroblock and the corresponding row from the aligned macroblock The sum of absolute differences between the four; for each of the four adjacent previous macroblocks, four respective sums of absolute differences are accumulated;}}.

This process is described further below. Although these examples are described in terms of operating on 4 adjacent macroblocks of the search window, alternative embodiments of the present invention are not limited thereto. However, the embodiments of the present invention are not limited or limited to operations on adjacent macroblocks. The multiple reference macroblocks processed together do not need to be changed by the distance of a single pixel. For an embodiment, any reference macroblock can be processed together, as long as it has pixels located within a 16×16 window around a specific pixel position. Depending on hardware resources such as the number of available data registers and execution units, other embodiments may perform block matching and absolute difference sum calculations for more or less macroblocks. For example, another embodiment has at least 8 combined data registers to hold 4 different combinations of pixel data generated by right-shifting and combining two data blocks with a width of 8 data segments. This embodiment can only Use twice-aligned 8-data-segment-wide memory load to operate on 4 adjacent previous macroblocks. Four of the eight combined data registers are used to calculate overhead: the first eight data segments from the previous frame, the next eight data segments from the previous frame, the eight data segments from the current frame, and the eight data segments from the current frame are maintained. Shift 8 data segments of the merge operation to the right. The other 4 combined data registers are used to accumulate the total sum of absolute difference (SAD) of each of the 4 macroblocks. However, more combined data registers can be added for SAD calculation and accumulation, thereby increasing the number of reference macroblocks processed together. Therefore, if there are 4 combined data registers available, 4 other previous macroblocks can also be processed. In one embodiment, the number of available combinatorial registers that maintain the cumulative sum of absolute differences can limit the number of macroblocks that can be processed at one time.

Moreover, in some processor architectures, memory access may have a specific granularity and be aligned with a specific boundary. For example, a processor can access memory based on blocks of 16 or 32 bytes. In this case, accessing data that is not aligned at the 16- or 32-byte boundary may require unaligned memory access instructions, which are costly in terms of execution time and resources. Worse, a piece of required data may cross the boundary and cover multiple memory blocks. Cache line splits that require unaligned load instructions to access data located on two different cache lines can be costly. The situation is even worse for data rows that cross the memory page boundary. For example, by processing an 8-byte memory block and a macroblock spanning 8 pixels, each pixel having one byte of data, an aligned memory load instruction is sufficient for the macroblock row. But for the next adjacent macro block one pixel column apart, the data required by the pixel row will span the memory block of 7 data bytes starting from the first macro block, and also span the data of the next memory block. Byte memory boundary. The embodiment of the present invention uses a right shift merge operation to efficiently process such data. In one embodiment, two consecutive memory blocks are loaded at aligned memory boundaries and kept in registers for multiple use. The right shift merge operation can obtain these memory blocks and shift the data segments in them by the required distance to obtain the correct data rows. Therefore, for this example, the right shift merge instruction can take the two loaded memory blocks, move one data byte out of the second block, and move one data byte from the first block into the second block to generate The data of the first row of the second macro block does not have to perform unaligned loading. The embodiment of motion estimation can also break the correlation chain based on how the algorithm is implemented. For example, by modifying the order of calculations, the data/instruction correlation can be removed or shifted so that certain calculations and instructions can be executed out of order, as in the processor 1000 of FIG. 15. Due to the increased execution delay and available computing resources, even greater performance improvements can be achieved with the updated processor architecture. By using the embodiment of the right shift merge instruction, some correlations in the block matching sequence can be avoided. For example, multiple absolute difference sum operations and/or accumulation operations can be performed in parallel.

FIG. 22 illustrates the progress of the current macroblock across the current frame 1701. For this embodiment, each current macroblock 1710 is divided into 16 rows and 16 columns, and therefore includes 256 individual pixels. For this embodiment, the pixels in each macroblock 1710 are processed in a row 1711 at a time. When all 16 lines in the current block have been processed relative to the desired macro block in the search window, the next current macro block is processed. According to the step of calculating the size in macroblocks, the macroblocks of this embodiment are processed in the horizontal direction 1720 from the left to the right of the current frame 1701. That is, the aligned macroblocks in this embodiment do not overlap, and the current macroblock is arranged so that each macroblock is adjacent to the next macroblock. For example, the first macroblock may extend from the first pixel column to the 16th pixel column. The second macro block extends from column 17 to column 32, and so on. At the end of the macroblock line, the process returns 1722 to the left edge and drops one macroblock height, which is 16 lines in this example. Then macroblocks with the size of one macroblock down are processed 1724 horizontally from left to right, until the tentative matching for the entire frame 1701 is completed.

FIG. 22B illustrates the progress of the macroblock across the search window 1751 of the previous (reference) frame. Depending on the specific implementation, the search window 1751 may be concentrated in a certain area and therefore smaller than the entire previous frame. In another embodiment, the search window may completely overlap the previous frame. Similar to the current block, each previous macro block 1760, 1765, 1770, 1775 is divided into 16 rows and 16 columns, and there are a total of 256 pixels in each macro block. For this embodiment of the present invention, in finding a match, the four previous macroblocks 1760, 1765, 1770, and 1775 of the search window 1751 are processed in parallel with a single current block. Unlike the current macroblock of the current frame, the previous macroblocks 1760, 1765, 1770, 1775 in the search window 1751 can overlap, and as in this example, they do overlap. Here, each previous macroblock is shifted by one pixel column. Thus, the leftmost pixel on the first row of BLK1 is pixel 1761, for BLK 2 it is pixel 1766, for BLK 3 it is pixel 1771, and for BLK 4 it is pixel 1776. In the motion estimation algorithm, each row of the previous macroblocks 1760, 1765, 1770, 1775 is compared with the corresponding row of the current block. For example, the first row 1760 of BLK 1, the first row 1765 of BLK 2, the first row 1770 of BLK 3, and BLK The first row 1775 of 4 is processed with the first row of the current block.

Continue the line-by-line comparison of the 4 overlapping adjacent macroblocks until all 16 lines of the macroblock have been compared. The algorithm of this embodiment shifts the distance of 4 pixel columns to operate on the next four macroblocks. Thus, for this example, the leftmost pixel columns of the next four macroblocks will be pixel 1796, pixel 1797, pixel 1798, and pixel 1799, respectively. For this embodiment, the previous macroblock processing continues to the right 1780, across the search window 1751, wraps around 1782 to the next pixel row and restarts at the leftmost pixel of the search window 1751, until the search is completed window. Although the current macroblocks of the current frame of this embodiment do not overlap and the next single macroblock is one macroblock height or width away, the previous macroblocks of the previous or reference frame do overlap, and the next batch of macroblocks is increased by a single macroblock. Pixel rows or columns. Although the four reference macroblocks 1760, 1765, 1770, and 1775 in this example are adjacent and separated from each other by a single pixel column, the search window can be overlapped on the designated area around the selected pixel position. Any macroblock is processed together with the macroblock at that pixel. For example, the macroblock 1760 at pixel 1796 is currently being processed. Any macroblock in the 16×16 window surrounding the pixel 1796 can be processed together with the macroblock 1760. The 16×16 window in this example is derived from the dimension of the macroblock and the line width of one line. In this case, a row or data row has 16 data elements. Because the block matching function of this embodiment of the motion estimation algorithm can load two data rows with 16 data elements and perform a right shift merge operation to generate each of the shifted/combined versions of the two data rows. Such data rows, so other macroblocks that overlap on the 16×16 window for which the data for this macroblock will be loaded will be able to at least partially multiplex the loaded data. Therefore, any macro block that overlaps the macro block 1760, such as the macro blocks 1760, 1765, 1770, 1775, or the macro block starting at the lower right pixel position of the macro block 1760, can be processed together with the macro block 1760. The difference in the amount of overlap affects the amount of data that can be reused from the previous data load.

With an embodiment of motion estimation according to the present invention, the macroblock analysis includes comparing the previous (reference) macroblock with the current macroblock row by row to obtain the sum of absolute differences between the two macroblocks. The sum of the absolute differences may indicate the degree of difference of the macroblocks and the closeness of matching. For one embodiment, each previous macroblock may be represented by a value obtained by accumulating the sum of absolute differences for all 16 rows in the macroblock. For the current macroblock being analyzed, the flag of the closest matching macroblock is maintained. For example, tracking the minimum accumulated sum of absolute differences and the position index for the corresponding previous macroblock. When motion estimation is performed across the search window, the cumulative sum of each previous macroblock is compared with the minimum value. If the updated previous macroblock has a smaller accumulated difference than the tracked minimum value, and therefore represents a match that is closer than the existing closest match, then the updated accumulated difference and index information of the previous macroblock is called The new minimum difference and index. In one embodiment, when the available macroblocks of all pixels in the search window have been processed, the index macroblock with the smallest difference can be used to help obtain the residual image used to compress the current frame.

FIG. 22C illustrates the parallel processing of 4 reference macroblocks 1810, 1815, 1820, 1825 and the current macroblock 1840 for a given search window for an embodiment of the present invention. For this example, sort the pixel data in the search window as "A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P" 1860, Among them, "A" is located at the lowest address position (0) in the data set, and "P" is located at the highest address position (15). This pixel set 1860 includes two parts 1861, 1862, each of which has 8 (m) data segments. Using the right shift merge operation as described above allows the embodiment of the present invention to manipulate the operands of the two data parts 1861, 1862, and generate correctly aligned images for different previous macroblocks 1810, 1815, 1820, 1825. Line data 1830. Each macro block (previous macro block 1810, 1815, 1820, 1825 and current macro block 1840) has a size of m rows and m columns. For discussion purposes and to simplify the problem, m is equal to 8 in this example. Other embodiments may have macroblocks of different sizes, where m is equal to, for example, 4, 16, 32, 128, 256, and so on.

In this example, the motion estimation algorithm is applied to the four previous macroblocks 1810, 1815, 1820, 1825 and the first row of the current macroblock 1840. For one embodiment, two aligned memory load operations are used to load two macroblock widths (2 m) of pixel data including the two data portions 1861 and 1862 from the memory and hold them in a temporary register. The right shift and merge operation of the two data parts 1861 and 1862 can generate 9 possible combinations of the line data 1830 without requiring a large amount of memory access. Moreover, it is possible to avoid misaligned memory loads that are costly in terms of execution time and resources. In this example, the two data portions 1861, 1862 are aligned on byte boundaries. Memory loads that do not start from addresses on byte boundaries, such as data segments B, C, or D, generally require unaligned memory load operations. The row data 1830 of each of the blocks are arranged as follows, where the leftmost data segment is the lowest address. In block 11810, the first row 1811 includes "A, B, C, D, E, F, G, H". Since the data in the first row 1811 is the same as the first data portion 1861, there is no need to shift. But the first row 1816 of block 21815 includes "B, C, D, E, F, G, H, I". Because the previous block 11810 and the block 21815 are horizontally separated by 1 pixel, the block 21815 starts with the pixel data B, and the block 11810 starts with the pixel data A, and the second pixel data is B. Therefore, the right shift merge of the two data parts 1861 and 1862 with the shift count of 1 will generate the first row of data in block 2.

Similarly, block 31820 is located one more pixel to the right, and the first row 1821 of block 31820 starts with pixel data C, including "C, D, E, F, G, H, I, J". The shift count of the operands of the two data parts 1861 and 1862 is 2 and the right shift merge operation produces the first row of block 3 data. The first row 1826 of block 41825 is composed of "D, E, F, G, H, I, J, K". This data can be generated by the right shift merge operation where the count of the same data operand is 4. Using the right shift merge operation for the temporarily saved and previously loaded data portions 1861 and 1862 allows data to be multiplexed when generating line data for other adjacent macroblocks, and by reducing the number of memory loads, especially unaligned memory loads. Save time/resources. Note that the pixel data for the current block is the same as the pixel data for the sum of all absolute differences compared with the reference macroblock of the previous frame. A single aligned memory load can be used for the row data 1842 of the current block 1840 because the current block 1840 may be aligned with the memory boundary.

This example of an embodiment of motion estimation is continued below. Each row of the previous macroblock 1810, 1815, 1820, 1825 is compared with the corresponding row of the current block 1840 to obtain the value of the sum of absolute differences. Therefore, in operation 1850 of the sum of absolute difference (SAD), the first row 1811 of the block 11810 is compared with the first row 1841 of the current block 1840. Perform the same operation on the other 3 blocks currently being operated on. Although it seems that the four macroblocks 1810, 1815, 1820, 1825 are being operated concurrently or in parallel, other embodiments of the present invention are not limited thereto. Therefore, operations on the 4 macroblocks can occur serially in time, but as a sequence of 4 macroblocks. For example, in the order of block 11810, block 21815, block 31820, and block 41825, the first row of each reference block receives the SAD operation 1850 of that row of the current block 1840. Then, the second row of each reference block accepts the SAD operation 1850, and so on. After each SAD operation 1850, the run-time sum of the sum of absolute differences is accumulated in the temporary register. Therefore, in this exemplary embodiment, 4 registers accumulate the sum of absolute differences until all m rows of the macro block have been completed. As part of the search for the best macroblock match, the accumulated value of each block is compared with the existing minimum difference value. Although this example describes the processing of 4 adjacent overlapping previous macroblocks, other macroblocks that overlap with the first block BLK 1810 in the search window can also be loaded with BLK 1810 data if the data lines are related. deal with. Therefore, macroblocks in a 16×16 window surrounding the macroblock currently being processed can also be processed.

Figure 22D illustrates the operation 1940 of Sum of Absolute Difference (SAD) and the summation of these SAD values. Here, each row from row A to row P of the reference macroblock block 11900 and its corresponding row in the current macroblock 1920 all accept the SAD operation 1940. The SAD operation 1940 compares the data representing the pixels in each row, and calculates a value representing the absolute difference between two rows (one from the previous macroblock 1900 and one from the current macroblock 1920). The values of all rows A to P from these SAD operations 1900 are summed together as a block sum 1942. This block sum 1942 provides an accumulated value of the sum of absolute differences between the entire previous macro block 1900 and the current macro block 1920. Based on this block sum 1942, the motion estimation algorithm can determine the similarity and closeness of matching of the previous macroblock 1900 with respect to this current macroblock 1920.

Although this embodiment operates on 4 reference macroblocks at a time, other embodiments can operate on a different number of macroblocks, depending on the amount of pixel data loaded and the number of available registers. Moreover, various registers can be used in the motion estimation process. For example, extension registers such as mm registers with MMX technology and XMM registers with SSE2 technology can be used to hold combined data similar to pixel data. In one embodiment, a 64-bit wide MMX register can hold 8 bytes, or 8 individual pixels if each pixel has 8 bits of data. In another embodiment, a 128-bit wide XMM register can hold 16 bytes, or 16 individual pixels if each pixel has 8-bit data. Similarly, other sizes that can hold combined data, such as 32/128/256/512-bit wide registers, can also be used with the embodiments of the present invention. On the other hand, calculations that do not require combined data registers, such as regular integer operations, can use integer registers and integer hardware.

Figure 23A is a flowchart illustrating an embodiment of a method for prediction and motion estimation. At block 2002, the tracked minimum (min) value and the index position of the minimum value are initialized. For this embodiment, the tracked min value and index indicate which of the processed previous (reference) macroblocks from the search window is the closest match of the current macroblock. At block 2004, it is checked whether all the desired macroblocks in the current frame have been completed. If it is, this part of motion estimation is completed. If all the desired current macroblocks have not been processed, then at block 2006, an unprocessed current macroblock of the current frame is selected. At block 2008, block matching starts from the first pixel position in the search window of the previous (reference) frame. At block 2010, it is checked whether the processing of the search window has been completed. In the first round, none of the search windows were processed. However, in the subsequent round, if the entire search window has been processed, the flow returns to block 2004 to determine whether there are other current macroblocks.

If the analysis of the entire search window has not been completed, a check is made at block 2012 to determine whether all pixels along this x-axis line have been processed. If this line is completed, the line count is increased to the next line, and the flow returns to block 2010 to determine whether there are more macroblocks on this new line in the search window. However, if all existing macroblocks of the pixel on the row have not been processed, it is checked at block 2014 whether the macroblocks at the pixel column and row have been processed. If the macroblock has been processed, the column count is increased, and the flow returns to block 2012 to determine whether the macroblock of the pixel in this new column has been processed. But if the macroblock of the pixel in this column and row has not been processed, block matching is performed between this reference macroblock and the current macroblock.

The flow in this example is described in terms of increasing the row and column positions of pixels along the X and Y axes, adding one pixel at a time for the sake of simplicity. However, for one embodiment of the present invention, 4 previous macroblocks can be processed in each round. In this way, the column count along the Y axis can be increased by 4 columns per round. Other embodiments can also process 8, 16, 32, etc. macroblocks at a time, so the column count is correspondingly increased by 8, 16, 32, etc. columns to point to the correct pixel positions in the subsequent rounds of the algorithm. Although the block matching processing of this embodiment uses searches along the X and Y axes in an orderly manner, the block matching of another embodiment can use another algorithm, such as a diamond search using a different pattern. ), or log search.

FIG. 23B is a flowchart that further describes the block matching of FIG. 23A. At block 1222, the data of the reference macroblock and the current macroblock are loaded. For one embodiment, the reference macroblock data is loaded as two combined data blocks, including data of multiple consecutive pixels. In one embodiment, each combined data block includes 8 data elements. At block 2224, a right shift merge operation is performed on the data block as needed to obtain the correct data block. For the above-mentioned embodiment where the 4 previous macroblocks are processed together, the right shift merge operation can generate data blocks corresponding to the rows located in each macroblock. The data block of each adjacent macroblock that is one pixel away is also shifted by one pixel, where, for each pixel row in the search window, the macroblock appears to slide through the search one pixel at a time window. The operations at blocks 2226, 2228, 2230, and 2232 are applied to the 4 previous macroblocks being processed together. For one embodiment, all 4 macroblocks receive the same operation before the next operation occurs. For another embodiment, a single previous macroblock can complete all operations before processing the next previous macroblock with a data block that includes the correctly shifted data segment.

At block 2226, for each row of these macroblocks, the sum of the absolute differences between the corresponding rows of the previous macroblock and the current macroblock is calculated. At block 2228, the sum of the absolute differences of all lines in the previous macroblock is accumulated together. At block 2230, the accumulated difference value of the previous macroblock is compared with the current minimum value. At block 2232, if the difference of this previous macroblock is less than the current min value, the min value is updated with this new difference. The index is also updated to reflect the position of this previous macroblock to indicate that the previous macroblock is the closest match to date. However, at block 2232, if the new difference is greater than the preset min value, the previous block is not a closer match than the block that has been matched so far.

The embodiments of the motion estimation algorithm according to the present invention can also utilize existing hardware resources to improve processor and system performance. However, as technology continues to improve, if the embodiments of the present invention are combined with a larger number of hardware resources and faster and more efficient logic circuits, they may have a greater impact on the improvement of performance. Therefore, an efficient implementation of motion estimation may have different and greater impact on different generations of processors. Simply adding more resources to modern processor architectures does not guarantee better performance improvements. By also maintaining the efficiency of the application similar to the motion estimation and shift right merge instruction (PSRMRG) embodiment, a greater performance improvement can be obtained.

Although the above examples are generally described in the context of 64-bit wide hardware/registers/operands to simplify the discussion, other embodiments may also use 128-bit wide hardware/registers/operands to perform register merge operations, right Shift and merge operation and motion estimation calculation. Moreover, the embodiments of the present invention are not limited to specific hardware or technology types such as MMX/SSE/SSE2 technology, but can be used with other SIMD implementations and other graphics data manipulation technologies. Although the motion estimation and block matching embodiments described in FIGS. 20-23B are described in the context of a line (line or row) with a width of 8 pixels or 8 data elements and a macroblock with a size of 8 rows and 8 columns, , But other embodiments may also include other dimensions. For example, a line (line or row) can be 16 pixels wide or 16 data elements wide, and a macro block can be 16 rows and 16 columns.

In the foregoing description, the present invention has been described with reference to specific exemplary embodiments thereof. However, it is clear that various modifications and changes can be made thereto without departing from the broader spirit and scope of the present invention as set forth in the appended claims. Therefore, the specification and drawings should be understood as descriptive and not restrictive.