Faster and more efficient different precision sum of absolute differences for dynamically configurable block searches for motion estimation

This invention is a digital signal processor form plural sums of absolute values (SAD) in a single operation. An operational unit performing a sum of absolute value operation comprising two sets of a plurality of rows, each row producing a SAD output. Plural absolute value difference units receive corresponding packed candidate pixel data and packed reference pixel data. A row summer sums the output of the absolute value difference units in the row. The candidate pixels are offset relative to the reference pixels by one pixel for each succeeding row in a set of rows. The two sets of rows operate on opposite halves of the candidate pixels packed within an instruction specified operand. The SAD operations can be performed on differing data widths employing carry chain control in the absolute difference unit and the row summers.

TECHNICAL FIELD OF THE INVENTION

The technical field of this invention is digital data processing and more specifically sum of absolute difference calculations.

BACKGROUND OF THE INVENTION

This invention relates to the calculation of sum of absolute differences (SAD) between two pixel blocks. This computation is often used as a similarity measure. A lower the sum of absolute differences corresponds to a more similar pair of pixel blocks. This computation is widely used in determining a best motion vector in video compression. The two pixel blocks compared are corresponding locations in time adjacent frames. One block slides within an allowed range of motion and the sum of the absolute differences between the two pixel blocks determines their similarity. A motion vector is determined from the horizontal and vertical displacement between pixel blocks yielding the smallest sum of absolute differences (greatest similarity). This search for a best motion vector is thus very computationally intensive. The prior art implemented Sum of Absolute Difference (SAD) for specific macro block search, such as 16×16 or 8×8, using a single horizontal pixel line search for Full Search Block Matching (FSBM).

SUMMARY OF THE INVENTION

This invention is a digital signal processor which forms plural sums of absolute values (SAD) in a single operation. An operational unit performing a sum of absolute value operation comprises two sets of a plurality of rows. Each row produces a SAD output. Each row includes a plurality of absolute value difference units having a first input receiving corresponding packed candidate pixel data and a second input receiving corresponding packed reference pixel data. A row summer sums the output of the absolute value difference units in the row forming a sum output. The candidate pixels are offset relative to the reference pixels by one pixel for each succeeding row in a set of rows. The two sets of rows operate on opposite halves of the candidate pixels packed within an instruction specified operand.

Each absolute value difference unit of each row further receives a mask input. The SAD output is 0 if the corresponding mask input has a first digital state.

The SAD operations can be performed on differing data widths employing carry chain control in the absolute difference unit and the row summers.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

FIG. 1illustrates a single core scalar processor according to one embodiment of this invention. Single core processor100includes a scalar central processing unit (CPU)110coupled to separate level one instruction cache (L1I)111and level one data cache (L1D)112. Central processing unit core110could be constructed as known in the art and would typically include a register file, an integer arithmetic logic unit, an integer multiplier and program flow control units. Single core processor100includes a level two combined instruction/data cache (L2)113that holds both instructions and data. In the preferred embodiment scalar central processing unit (CPU)110, level one instruction cache (L1I)111, level one data cache (L1D)112and level two combined instruction/data cache (L2)113are formed on a single integrated circuit.

In a preferred embodiment this single integrated circuit also includes auxiliary circuits such as power control circuit121, emulation/trace circuits122, design for test (DST) programmable built-in self test (PBIST) circuit123and clocking circuit124. External to CPU110and possibly integrated on single integrated circuit100is memory controller131.

CPU110operates under program control to perform data processing operations upon defined data. The program controlling CPU110consists of a plurality of instructions that must be fetched before decoding and execution. Single core processor100includes a number of cache memories.FIG. 1illustrates a pair of first level caches. Level one instruction cache (L1I)111stores instructions used by CPU110. CPU110first attempts to access any instruction from level one instruction cache121. Level one data cache (L1D)112stores data used by CPU110. CPU110first attempts to access any required data from level one data cache112. The two level one caches (L1I111and L1D112) are backed by a level two unified cache (L2)113. In the event of a cache miss to level one instruction cache111or to level one data cache112, the requested instruction or data is sought from level two unified cache113. If the requested instruction or data is stored in level two unified cache113, then it is supplied to the requesting level one cache for supply to central processing unit core110. As is known in the art, the requested instruction or data may be simultaneously supplied to both the requesting cache and CPU110to speed use.

Level two unified cache113is further coupled to higher level memory systems via memory controller131. Memory controller131handles cache misses in level two unified cache113by accessing external memory (not shown inFIG. 1). Memory controller131handles all memory centric functions such as cacheabilty determination, error detection and correction, address translation and the like. Single core processor100may be a part of a multiprocessor system. In that case memory controller131handles data transfer between processors and maintains cache coherence among processors.

FIG. 2illustrates a dual core processor according to another embodiment of this invention. Dual core processor200includes first CPU210coupled to separate level one instruction cache (L1I)211and level one data cache (L1D)212and second CPU220coupled to separate level one instruction cache (L1I)221and level one data cache (L1D)212. Central processing units210and220are preferably constructed similar to CPU110illustrated inFIG. 1. Dual core processor200includes a single shared level two combined instruction/data cache (L2)231supporting all four level one caches (L1I211, L1D212, L1I221and L1D222). In the preferred embodiment CPU210, level one instruction cache (L1I)211, level one data cache (L1D)212, CPU220, level one instruction cache (L1I)221, level one data cache (L1D)222and level two combined instruction/data cache (L2)231are formed on a single integrated circuit. This single integrated circuit preferably also includes auxiliary circuits such as power control circuit241, emulation/trace circuits242, design for test (DST) programmable built-in self test (PBIST) circuit243and clocking circuit244. This single integrated circuit may also include memory controller251.

FIGS. 3 and 4illustrate single core and dual core processors similar to that shown respectively inFIGS. 1 and 2.FIGS. 3 and 4differ fromFIGS. 1 and 2in showing vector central processing units. As further described below Single core vector processor300includes a vector CPU310. Dual core vector processor400includes two vector CPUs410and420. Vector CPUs310,410and420include wider data path operational units and wider data registers than the corresponding scalar CPUs110,210and220.

Vector CPUs310,410and420further differ from the corresponding scalar CPUs110,210and220in the inclusion of streaming engine313(FIG. 3) and streaming engines413and423(FIG. 5). Streaming engines313,413and423are similar. Streaming engine313transfers data from level two unified cache313(L2) to a vector CPU310. Streaming engine413transfers data from level two unified cache431to vector CPU410. Streaming engine423transfers data from level two unified cache431to vector CPU420. In accordance with the preferred embodiment each streaming engine313,413and423manages up to two data streams.

Each streaming engine313,413and423transfer data in certain restricted circumstances. A stream consists of a sequence of elements of a particular type. Programs that operate on streams read the data sequentially, operating on each element in turn. Every stream has the following basic properties. The stream data have a well-defined beginning and ending in time. The stream data have fixed element size and type throughout the stream. The stream data have fixed sequence of elements. Thus programs cannot seek randomly within the stream. The stream data is read-only while active. Programs cannot write to a stream while simultaneously reading from it. Once a stream is opened the streaming engine: calculates the address; fetches the defined data type from level two unified cache; performs data type manipulation such as zero extension, sign extension, data element sorting/swapping such as matrix transposition; and delivers the data directly to the programmed execution unit within the CPU. Streaming engines are thus useful for real-time digital filtering operations on well-behaved data. Streaming engines free these memory fetch tasks from the corresponding CPU enabling other processing functions.

The streaming engines provide the following benefits. They permit multi-dimensional memory accesses. They increase the available bandwidth to the functional units. They minimize the number of cache miss stalls since the stream buffer can bypass L1D cache. They reduce the number of scalar operations required in the loop to maintain. They manage the address pointers. They handle address generation automatically freeing up the address generation instruction slots and the .D unit for other computations.

FIG. 5illustrates construction of one embodiment of the CPU of this invention. Except where noted this description covers both scalar CPUs and vector CPUs. The CPU of this invention includes plural execution units multiply unit511(.M), correlation unit512(.C), arithmetic unit513(.L), arithmetic unit514(.S), load/store unit515(.D), branch unit516(.B) and predication unit517(.P). The operation and relationships of these execution units are detailed below.

Multiply unit511primarily performs multiplications. Multiply unit511accepts up to two double vector operands and produces up to one double vector result. Multiply unit511is instruction configurable to perform the following operations: various integer multiply operations, with precision ranging from 8-bits to 64-bits; various regular and complex dot product operations; and various floating point multiply operations; bit-wise logical operations; moves; as well as adds and subtracts. As illustrated inFIG. 5multiply unit511includes hardware for four simultaneous 16 bit by 16 bit multiplications. Multiply unit511may access global scalar register file521, global vector register file522and shared .M and C. local register523file in a manner described below. Forwarding multiplexer530mediates the data transfer between global scalar register file521, global vector register file522, the corresponding streaming engine and multiply unit511.

Correlation unit512(.C) accepts up to two double vector operands and produces up to one double vector result. Correlation unit512supports these major operations. In support of WCDMA “Rake” and “Search” instructions correlation unit512performs up to 512 2-bit PN*8-bit I/Q complex multiplies per clock cycle. Correlation unit512performs 8-bit and 16-bit Sum-of-Absolute-Difference (SAD) calculations performing up to 512 SADs per clock cycle. Correlation unit512performs horizontal add and horizontal min/max instructions. Correlation unit512performs vector permutes instructions. Correlation unit512includes contains 8 256-bit wide control registers. These control registers are used to control the operations of certain correlation unit instructions. Correlation unit512may access global scalar register file521, global vector register file522and shared .M and C. local register file523in a manner described below. Forwarding multiplexer530mediates the data transfer between global scalar register file521, global vector register file522, the corresponding streaming engine and correlation unit512.

CPU500includes two arithmetic units: arithmetic unit513(.L) and arithmetic unit514(.S). Each arithmetic unit513and arithmetic unit514accepts up to two vector operands and produces one vector result. The compute units support these major operations. Arithmetic unit513and arithmetic unit514perform various single-instruction-multiple-data (SIMD) fixed point arithmetic operations with precision ranging from 8-bit to 64-bits. Arithmetic unit513and arithmetic unit514perform various vector compare and minimum/maximum instructions which write results directly to predicate register file526(further described below). These comparisons include A=B, A>B, A≧B, A<B and A≦B. If the comparison is correct, a 1 bit is stored in the corresponding bit position within the predicate register. If the comparison fails, a 0 is stored in the corresponding bit position within the predicate register. Vector compare instructions assume byte (8 bit) data and thus generate 32 single bit results. Arithmetic unit513and arithmetic unit514perform various vector operations using a designated predicate register as explained below. Arithmetic unit513and arithmetic unit514perform various SIMD floating point arithmetic operations with precision ranging from half-precision (16-bits), single precision (32-bits) to double precision (64-bits). Arithmetic unit513and arithmetic unit514perform specialized instructions to speed up various algorithms and functions. Arithmetic unit513and arithmetic unit514may access global scalar register file521, global vector register file522, shared .L and .S local register file524and predicate register file526. Forwarding multiplexer530mediates the data transfer between global scalar register file521, global vector register file522, the corresponding streaming engine and arithmetic units513and514.

Load/store unit515(.D) is primarily used for address calculations. Load/store unit515is expanded to accept scalar operands up to 64-bits and produces scalar result up to 64-bits. Load/store unit515includes additional hardware to perform data manipulations such as swapping, pack and unpack on the load and store data to reduce workloads on the other units. Load/store unit515can send out one load or store request each clock cycle along with the 44-bit physical address to level one data cache (L1D). Load or store data width can be 32-bits, 64-bits, 256-bits or 512-bits. Load/store unit515supports these major operations: 64-bit SIMD arithmetic operations; 64-bit bit-wise logical operations; and scalar and vector load and store data manipulations. Load/store unit515preferably includes a micro-TLB (table look-aside buffer) block to perform address translation from a 48-bit virtual address to a 44-bit physical address. Load/store unit515may access global scalar register file521, global vector register file522and .D local register file525in a manner described below. Forwarding multiplexer530mediates the data transfer between global scalar register file521, global vector register file522, the corresponding streaming engine and load/store unit515.

Branch unit516(.B) calculates branch addresses, performs branch predictions, and alters control flows dependent on the outcome of the prediction.

Predication unit517(.P) is a small control unit which performs basic operations on vector predication registers. Predication unit517has direct access to the vector predication registers526. Predication unit517performs different bit operations on the predication registers such as AND, ANDN, OR, XOR, NOR, BITR, NEG, SET, BITCNT (bit count), RMBD (right most bit detect), BIT Decimate and Expand, etc.

FIG. 6illustrates global scalar register file521. There are 16 independent 64-bit wide scalar registers. Each register of global scalar register file521can be read as 32-bits scalar data (designated registers A0to A15601) or 64-bits of scalar data (designated registers EA0to EA15611). However, writes are always 64-bit, zero-extended to fill up to 64-bits if needed. All scalar instructions of all functional units can read or write to global scalar register file521. The instruction type determines the data size. Global scalar register file521supports data types ranging in size from 8-bits through 64-bits. A vector instruction can also write to the 64-bit global scalar registers521with the upper 192 bit data of the vector discarded. A vector instruction can also read 64-bit data from the global scalar register file511. In this case the operand is zero-extended in the upper 192-bit to form an input vector.

FIG. 7illustrates global vector register file522. There are 16 independent 256-bit wide vector registers. Each register of global vector register file522can be read as 32-bits scalar data (designated registers X0to X15701), 64-bits of scalar data (designated registers EX0to EX15711), 256-bit vector data (designated registers VX0to VX15721) or 512-bit double vector data (designated DVX0to DVX7, not illustrated). In the current embodiment only multiply unit511and correlation unit512may execute double vector instructions. All vector instructions of all functional units can read or write to global vector register file522. Any scalar instruction of any functional unit can also access the low 32 or 64 bits of a global vector register file522register for read or write. The instruction type determines the data size.

FIG. 8illustrates local vector register file523. There are 16 independent 256-bit wide vector registers. Each register of local vector register file523can be read as 32-bits scalar data (designated registers M0to M15701), 64-bits of scalar data (designated registers EM0to EM15711), 256-bit vector data (designated registers VM0to VM15721) or 512-bit double vector data (designated DVM0to DVM7, not illustrated). In the current embodiment only multiply unit511and correlation unit512may execute double vector instructions. All vector instructions of all functional units can write to local vector register file523. Only instructions of multiply unit511and correlation unit512may read from local vector register file523. The instruction type determines the data size.

Multiply unit511may operate upon double vectors (512-bit data). Multiply unit511may read double vector data from and write double vector data to global vector register file521and local vector register file523. Register designations DVXx and DVMx are mapped to global vector register file521and local vector register file523as follows.

Local vector register file524is similar to local vector register file523. There are 16 independent 256-bit wide vector registers. Each register of local vector register file524can be read as 32-bits scalar data (designated registers L0to L15701), 64-bits of scalar data (designated registers EL0to EL15711) or 256-bit vector data (designated registers VL0to VL15721). All vector instructions of all functional units can write to local vector register file524. Only instructions of arithmetic unit513and arithmetic unit514may read from local vector register file524.

FIG. 9illustrates local register file525. There are 16 independent 64-bit wide registers. Each register of local register file525can be read as 32-bits scalar data (designated registers D0to D15701) or 64-bits of scalar data (designated registers ED0to ED15711). All scalar and vector instructions of all functional units can write to local register file525. Only instructions of load/store unit515may read from local register file525. Any vector instructions can also write 64-bit data to local register file525with the upper 192 bit data of the result vector discarded. Any vector instructions can also read 64-bit data from the 64-bit local register file525registers. The return data is zero-extended in the upper 192-bit to form an input vector. The registers of local register file525can only be used as addresses in load/store instructions, not as store data or as sources for 64-bit arithmetic and logical instructions of load/store unit515.

FIG. 10illustrates the predicate register file517. There are sixteen registers 32-bit registers in predicate register file517. Predicate register file517contains the results from vector comparison operations executed by either arithmetic and is used by vector selection instructions and vector predicated store instructions. A small subset of special instructions can also read directly from predicate registers, performs operations and write back to a predicate register directly. There are also instructions which can transfer values between the global register files (521and522) and predicate register file517. Transfers between predicate register file517and local register files (523,524and525) are not supported. Each bit of a predication register (designated P0to P15) controls a byte of a vector data. Since a vector is 256-bits, the width of a predicate register equals 256/8=32 bits. The predicate register file can be written to by vector comparison operations to store the results of the vector compares.

A CPU such as CPU110,210,220,310,410or420operates on an instruction pipeline. This instruction pipeline can dispatch up to nine parallel 32-bits slots to provide instructions to the seven execution units (multiply unit511, correlation unit512, arithmetic unit513, arithmetic unit514, load/store unit515, branch unit516and predication unit517) every cycle. Instructions are fetched instruction packets of fixed length further described below. All instructions require the same number of pipeline phases for fetch and decode, but require a varying number of execute phases.

FIG. 11illustrates the following pipeline phases: program fetch phase1110, dispatch and decode phase1120and execution phase1130. Program fetch phase1110includes three stages for all instructions. Dispatch and decode phase1120include three stages for all instructions. Execution phase1130includes one to four stages dependent on the instruction.

Fetch phase1110includes program address generation stage1111(PG), program access stage1112(PA) and program receive stage1113(PR). During program address generation stage1111(PG), the program address is generated in the CPU and the read request is sent to the memory controller for the level one instruction cache L1I. During the program access stage1112(PA) the level one instruction cache L1I processes the request, accesses the data in its memory and sends a fetch packet to the CPU boundary. During the program receive stage1113(PR) the CPU registers the fetch packet.

Instructions are always fetched sixteen words at a time.FIG. 12illustrates this fetch packet.FIG. 12illustrates 16 instructions1201to1216of a single fetch packet. Fetch packets are aligned on 512-bit (16-word) boundaries. The execution of the individual instructions is partially controlled by a p bit in each instruction. This p bit is preferably bit0of the instruction. The p bit determines whether the instruction executes in parallel with another instruction. The p bits are scanned from lower to higher address. If the p bit of an instruction is 1, then the next following instruction is executed in parallel with (in the same cycle as) that instruction I. If the p bit of an instruction is 0, then the next following instruction is executed in the cycle after the instruction. All instructions executing in parallel constitute an execute packet. An execute packet can contain up to nine instructions. Each instruction in an execute packet must use a different functional unit. An execute packet can contain up to nine 32-bit wide slots. A slot can either be a self-contained instruction or expand the constant field specified by the immediate preceding instruction. A slot can be used as conditional codes to apply to the instructions within the same fetch packet. A fetch packet can contain up to 2 constant extension slots and one condition code extension slot.

There are up to 11 distinct instruction slots, but scheduling restrictions limit to 9 the maximum number of parallel slots. The maximum nine slots are shared as follows: multiply unit511; correlation unit512; arithmetic unit513; arithmetic unit514; load/store unit515; branch unit516shared with predicate unit517; a first constant extension; a second constant extension; and a unit less instruction shared with a condition code extension. The last instruction in an execute packet has a p bit equal to 0.

The CPU and level one instruction cache L1I pipelines are de-coupled from each other. Fetch packet returns from level one instruction cache L1I can take different number of clock cycles, depending on external circumstances such as whether there is a hit in level one instruction cache L1I. Therefore program access stage1112(PA) can take several clock cycles instead of 1 clock cycle as in the other stages.

Dispatch and decode phase1120include instruction dispatch to appropriate execution unit stage1121(DS), instruction pre-decode stage1122(DC1); and instruction decode, operand reads stage1223(DC2). During instruction dispatch to appropriate execution unit stage1121(DS) the fetch packets are split into execute packets and assigned to the appropriate functional units. During the instruction pre-decode stage1122(DC1) the source registers, destination registers, and associated paths are decoded for the execution of the instructions in the functional units. During the instruction decode, operand reads stage1123(DC2) more detail unit decodes are done, as well as reading operands from the register files.

Execution phases1130includes execution stages1131to1135(E1to E5). Different types of instructions require different numbers of these stages to complete their execution. These stages of the pipeline play an important role in understanding the device state at CPU cycle boundaries.

During execute1stage1131(E1) the conditions for the instructions are evaluated and operands are operated on. As illustrated inFIG. 11, execute1stage1131may receive operands from a stream buffer1141and one of the register files shown schematically as1142. For load and store instructions, address generation is performed and address modifications are written to a register file. For branch instructions, branch fetch packet in PG phase is affected. As illustrated inFIG. 11, load and store instructions access memory here shown schematically as memory1151. For single-cycle instructions, results are written to a destination register file. This assumes that any conditions for the instructions are evaluated as true. If a condition is evaluated as false, the instruction does not write any results or have any pipeline operation after execute1stage1131.

During execute2stage1132(E2) load instructions send the address to memory. Store instructions send the address and data to memory. Single-cycle instructions that saturate results set the SAT bit in the control status register (CSR) if saturation occurs. For 2-cycle instructions, results are written to a destination register file.

During execute3stage1133(E3) data memory accesses are performed. Any multiply instructions that saturate results set the SAT bit in the control status register (CSR) if saturation occurs. For 3-cycle instructions, results are written to a destination register file.

During execute4stage1134(E4) load instructions bring data to the CPU boundary. For 4-cycle instructions, results are written to a destination register file.

During execute5stage1135(E5) load instructions write data into a register. This is illustrated schematically inFIG. 11with input from memory1151to execute5stage1135.

FIG. 13illustrates an example of the instruction coding of instructions used by this invention. Each instruction consists of 32 bits and controls the operation of one of the individually controllable functional units (multiply unit511, correlation unit512, arithmetic unit513, arithmetic unit514, load/store unit515). The bit fields are defined as follows. The creg field and the z bit are optional fields used in conditional instructions. These bits are used for conditional instructions to identify the predicate register and the condition. The z bit (bit28) indicates whether the predication is based upon zero or not zero in the predicate register. If z=1, the test is for equality with zero. If z=0, the test is for nonzero. The case of creg=0 and z=0 is treated as always true to allow unconditional instruction execution. The creg field and the z field are encoded in the instruction as shown in Table 2.

TABLE 2Conditional Registercregz31302928Unconditional0000Reserved0001A0001zA1010zA2011zA3100zA4101zA5110zReserved11xx
Note that “z” in the z bit column refers to the zero/not zero comparison selection noted above and “x” is a don't care state. This coding can only specify a subset of the 16 global scalar registers as predicate registers. This selection was made to preserve bits in the instruction coding. Note that unconditional instructions do not have these optional bits. For unconditional instructions these bits (28to31) are preferably used as additional opcode bits. However, if needed, an execute packet can contain a unique 32-bit condition code extension slot which contains the 4-bit CREGZ fields for the instructions which are in the same execute packet. Table 3 shows the coding of such a condition code extension slot.

TABLE 3BitsFunctional Unit3:0.L7:4.S11:5.D15:12.M19:16.C23:20.B28:24Reserved31:29Reserved
Thus the condition code extension slot specifies bits decoded in the same way the creg/z bits assigned to a particular functional unit in the same execute packet.

Special vector predicate instructions use the designated predicate register to control vector operations. In the current embodiment all these vector predicate instructions operate on byte (8 bit) data. Each bit of the predicate register controls whether a SIMD operation is performed upon the corresponding byte of data. The operations of predicate unit517permit a variety of compound vector SIMD operations based upon more than one vector comparison. For example a range determination can be made using two comparisons. A candidate vector is compared with a first vector reference having the minimum of the range packed within a first data register. A second comparison of the candidate vector is made with a second reference vector having the maximum of the range packed within a second data register. Logical combinations of the two resulting predicate registers would permit a vector conditional operation to determine whether each data part of the candidate vector is within range or out of range.

The dst field specifies a register in a corresponding register file as the destination of the instruction results.

The src2 field specifies a register in a corresponding register file as the second source operand.

The src1/cst field has several meanings depending on the instruction opcode field (bits2to12and additionally bits28to31for unconditional instructions). The first meaning specifies a register of a corresponding register file as the first operand. The second meaning is an immediate constant. Depending on the instruction type, this is treated as an unsigned integer and zero extended to a specified data length or is treated as a signed integer and sign extended to the specified data length.

The opcode field (bits2to12for all instructions and additionally bits28to31for unconditional instructions) specifies the type of instruction and designates appropriate instruction options. This includes designation of the functional unit and operation performed. A detailed explanation of the opcode is beyond the scope of this invention except for the instruction options detailed below.

The p bit (bit0) marks the execute packets. The p-bit determines whether the instruction executes in parallel with the following instruction. The p-bits are scanned from lower to higher address. If p=1 for the current instruction, then the next instruction executes in parallel with the current instruction. If p=0 for the current instruction, then the next instruction executes in the cycle after the current instruction. All instructions executing in parallel constitute an execute packet. An execute packet can contain up to eight instructions. Each instruction in an execute packet must use a different functional unit.

Correlation unit512and arithmetic units513and514often operate in a single instruction multiple data (SIMD) mode. In this SIMD mode the same instruction is applied to packed data from the two operands. Each operand holds plural data elements disposed in predetermined slots. SIMD operation is enabled by carry control at the data boundaries. Such carry control enables operations on varying data widths.

FIG. 14illustrates the carry control. AND gate1401receives the carry output of bit N within the operand wide arithmetic logic unit (256 bits for arithmetic units513and514, 512 bits for correlation unit512). AND gate1401also receives a carry control signal which will be further explained below. The output of AND gate1401is supplied to the carry input of bit N+1 of the operand wide arithmetic logic unit. AND gates such as AND gate1401are disposed between every pair of bits at a possible data boundary. For example, for 8-bit data such an AND gate will be between bits7and8, bits15and16, bits23and24, etc. Each such AND gate receives a corresponding carry control signal. If the data size is of the minimum, then each carry control signal is 0, effectively blocking carry transmission between the adjacent bits. The corresponding carry control signal is 1 if the selected data size requires both arithmetic logic unit sections. Table 4 below shows example carry control signals for the case of a 256 bit wide operand such as used in arithmetic units513and514which may be divided into sections of 8 bits, 16 bits, 32 bits, 64 bits or 128 bits. No control of the carry output of the most significant bit is needed, thus only 31 carry control signals are required.

This invention relates to the calculation of sum of absolute differences (SAD) between two pixel blocks. This computation is often used as a similarity measure. A lower the sum of absolute differences corresponds to a more similar pair of pixel blocks. This computation is widely used in determining a best motion vector in video compression. The two pixel blocks compared are corresponding locations in time adjacent frames. One block slides within an allowed range of motion and the sum of the absolute differences between the two pixel blocks determines their similarity. A motion vector is determined from the horizontal and vertical displacement between pixel blocks yielding the smallest sum of absolute differences (greatest similarity). This search for a best motion vector is thus very computationally intensive.

The prior art implemented Sum of Absolute Difference (SAD) for specific macro block search, such as 16×16 or 8×8, using a single horizontal pixel line search for Full Search Block Matching (FSBM). This invention implements faster and more power efficient SAD operations for different search block sizes, such as 1×32×32, 2×16×16, 2×8×8, 2×5×5, 2 4×4. These block sizes can be dynamically configured using mask bits in a control register and using double horizontal pixel lines search.

This invention includes correlation unit C512instructions for implementing a SAD computation. These instructions calculate the sum of absolute difference between two inputs. This absolute difference is accumulated between two pixels across 16 or 8 pixels based on input precision for each output. This is repeated with window offset by the pixel size for other outputs. A mask bit configures to different block size by zeroing out the absolute difference contribution of pixels outside the block. Thus these absolute differences do not contribute to the sum.

A first instruction of this class is called DVSADM8O16B16H (dual horizontal line search) which implements a sliding window correlation using sum of absolute difference of the unsigned 8 bit candidate and reference pixels at an offset of 8 bits or 1 pixel. This instruction uses a double horizontal line search (c(0) to c(15) and c(16) to c(31)). This instruction takes two sets of unsigned 8 bit candidate pixels (c(0) to c(15) and c(16) to c(c31)) as the src2 input and two sets of unsigned 8 bit reference pixels (r(0) to r(30) and r(32) to r(62)) as src1 input. This instruction also receives 2 sets of 1 bit mask (mask(0) to mask(15) and mask(16) to mask(31)) from an implicitly specified control register. This instruction accumulates sum of absolute differences between candidate and reference pixels across two sets of 16 pixels and produce 2 outputs of half word precision. This instruction repeats this calculation for 2 sets of candidate pixel in src2 against 2×16 sets of 16 pixels in src1 and produces 2 16 half-words (16 bit) outputs. The mask input can zero out SAD contribution to accumulation and configure a different block search. A src2 operand width of 256 bits (32 pixels by 8 bits per pixel) is selected by a single vector operand and a src1 operand width of 512 bits is selected by a vector register pair. The output width of 512 bits (32 SADs of 16 bits each) is stored in a register pair corresponding to dst (FIG. 13). The register number of the dst field of the instruction is limited to an even register number. The 256 lower bits of the 512 bit operand are stored in the designated register number and the 256 bits upper bits are stored in the register with the next higher register number.

This instruction is illustrated inFIGS. 15A and 15B.FIG. 15Aillustrates 16 rows1500,1510. . .1530. Each row includes 16 absolute value of difference units such as1501,1511. . .1531. The absolute value of difference units receive a first input of a corresponding candidate pixel c(i) and a second input of a corresponding reference pixel r(i). A multiplier such as multipliers1502,1512. . .1532receives the absolute value and corresponding mask bit m(i). The product is supplied to the summer1503,1513. . .1533of the corresponding row.FIG. 15Billustrates a second half including 16 rows1540,1550. . .1590. Each row includes 16 absolute value of difference units such as1541,1551. . .1591. The absolute value of difference units receive a first input of a corresponding candidate pixel c(i) and a second input of a corresponding reference pixel r(i). A multiplier such as multipliers1542,1552. . .1592receives the absolute value and corresponding mask bit m(i). The product is supplied to the summer1543,1553. . .1593of the corresponding row. As shown inFIG. 15Afor the first half the in row1500the candidate and the reference pixels have the same index. Thus row1500receives candidates pixels c(0) to c(15) and reference pixels r(0) to r(15). For each following row the reference pixels are offset by one pixel. Thus row1530receives candidate pixels c(0) to c(15) as other rows but receives reference pixels r(15) to r(30). As shown inFIG. 15Bfor the second half in row1540receives candidate pixels c(16) to c(31) and the reference pixels r(32) to r(47). For each following row the reference pixels are offset by one pixel. Thus row1590receives candidate pixels c(16) to c(31) as other rows but receives reference pixels r(62) to r(47). The whole apparatus ofFIGS. 15A and 15Bperforms dual lines search using 2 sets of candidate pixels and 2 sets of reference pixels and generates 2 sets of 16 16 bit sum of absolute differences s(0) to s(15) and s(16) to s(31).

A second instruction of this type called DVSADM16O8H8W (dual horizontal line search) which implements a sliding window correlation using sum of absolute difference of the unsigned 16 bit candidate pixels and reference pixels at an offset of 16 bits or 1 pixel. This instruction uses double horizontal line search (c(0) to c(7) and c(8) to c(15)). This instruction takes two sets of unsigned 16-bit candidate pixels (c(0) to c(7) and c(8) to c(c15)) as src2 input. This instruction takes two sets of unsigned 16-bit reference pixels (r(0) to r(14) and r(15) to r(30)) as src1 input. This instruction takes 2 sets of 1 bit mask (mask(0) to mask(7) and mask(8) to mask(15)) from an implicitly defined control register. This instruction accumulates sum of absolute differences between src2 and src1 pixels across two sets of 8 pixels and produce 2 outputs of word (32 bit) precision. This instructions repeats this calculation for 2 sets of candidate pixels in src2 against 2×8 sets of 8 pixels in src1 and produces 2 by 8 word (32 bit) outputs. The mask input can zero out SAD contribution to accumulation and configure a different block search. A src2 operand width of 256 bits (16 pixels by 16 bits per pixel) is selected by a single vector operand and the src1 operand width of 512 bits is selected by a vector register pair. The output width of 512 bits (16 SADs of 32 bits each) is stored in a register pair corresponding to dst (FIG. 13). The register number of the dst field of the instruction is limited to an even register number. The 256 lower bits of the 512 bit operand are stored in the designated register number and the 256 bits upper bits are stored in the register with the next higher register number.

This instruction is illustrated inFIGS. 16A and 16B.FIG. 16Aillustrates 8 rows1600,1610. . .1630. Each row includes 8 absolute value of difference units such as1601,1611. . .1631. The absolute value of difference units receive a first input of a corresponding candidate pixel c(i) and a second input of a corresponding reference pixel r(i). A multiplier such as multipliers1602,1612. . .1632receives the absolute value and corresponding mask bit m(i). The product is supplied to the summer1603,1613. . .1633of the corresponding row.FIG. 16Billustrates a second half including 8 rows1640,1650. . .1690. Each row includes 8 absolute value of difference units such as1641,1651. . .1691. The absolute value of difference units receive a first input of a corresponding candidate pixel c(i) and a second input of a corresponding reference pixel r(i). A multiplier such as multipliers1542,1552. . .1592receives the absolute value and corresponding mask bit m(i). The product is supplied to the summer1553,1553. . .1593of the corresponding row. As shown inFIG. 15Afor the first half the in row1500the candidate and the reference pixels have the same index. Thus row1500receives candidates pixels c(0) to c(7) and reference pixels r(0) to r(7). For each following row the reference pixels are offset by one pixel. Thus row1530receives candidate pixels c(0) to c(7) as other rows but receives reference pixels r(7) to r(14). As shown inFIG. 15Bfor the second half the in row1540receives candidate pixels c(8) to c(15) and the reference pixels r(8) to r(16). For each following row the reference pixels are offset by one pixel. Thus row1590receives candidate pixels c(8) to c(15) as other rows but receives reference pixels r(15) to r(22). The whole apparatus ofFIGS. 16A and 16Bperforms dual line search using 2 sets of candidate pixels and 2 sets of reference pixels and generates 2 sets of 8 32 bit sum of absolute differences s(0) to s(7) and s(8) to s(15).

FIG. 17schematically illustrates the comparisons of the DVSADM16O8H8W instruction illustrated inFIGS. 16A and 16B. Row1600forms the SAD of the candidate pixels c(0) to c(7) with respective reference pixels r(0) to r(7). Row1610forms the SAD of the candidate pixels c(0) to c(7) with respective reference pixels r(1) to r(8). The candidate pixels shift relative to the reference pixels and row1630forms the SAD of the candidate pixels c(0) to c(7) with respective reference pixels r(7) to r(14). The second 8 rows are completely distinct from the first 8 rows. Row1640forms the SAD of the candidate pixels c(8) to c(15) with respective reference pixels r(9) to r(15). Row1650forms the SAD of the candidate pixels c(8) to c(15) with respective reference pixels r(9) to r(16). The candidate pixels shift relative to the reference pixels and row1690forms the SAD of the candidate pixels c(8) to c(15) with respective reference pixels r(15) to r(22). With appropriate packing of pixel data this one instruction can form SAD calculations for two rows of a candidate block. A similar schematic view of the DVSADM8O16B16H instruction illustrated inFIGS. 15A and 15Bis possible. This view is similar toFIG. 17but is omitted because the number of pixels and rows would make illustration too busy.

A third instruction DVSADM8O16B32H is same as DVSADM8O16B16H except that it searches one horizontal line candidate pixels across 32 sets of 16 reference pixels.

A fourth instruction DVSADM16O8H16W is same as DVSADM16O8H8W except that it searches one horizontal line candidate pixels across 16 sets of 8 reference pixels.

FIG. 18illustrates a manner to implement the absolute value of difference units and corresponding multipliers illustrated inFIGS. 15A, 15B, 16A and 16B. The difference is formed by inversion and addition. Inverse unit1801forms the arithmetic inverse of the candidate pixel input c. This arithmetic inversion may be performed by a two's complement of the input number. The two's complement is based upon the relation −X=˜X+1. A two's complement can thus be generated by inverting the number and adding 1. The addition of 1 can be achieved by asserting a carry input to the lowest bit of adder1802. Adder1802adds the inverse of the candidate input and the reference input. Adder1802may generate an active carry output depending on the data inputs. If adder1802does not generate an active carry output, then the reference pixel value is greater than the candidate pixel value and the difference is positive. Thus the absolute value of the difference is the same as the difference. If adder1802generates an active carry output, then the candidate pixel value is greater than the reference pixel value and the difference is negative. Thus the absolute value of the difference is the arithmetic inverse of the difference. Inverse unit1803forms the arithmetic inverse the output of adder1802if adder1802generates an active carry output. Otherwise inverse unit1803leaves its input unchanged. Multipliers1503,1513,1533,1543,1553,1593,1603,1613,1633,1643,1653and1693are implemented via and AND gate1804because the mask input is a single bit. If the mask input is 1, then the absolute value is unchanged. If the mask value is 0, then the absolute value is set of all 0s. The output of AND gate1804is supplied to an input of the summer of the corresponding row.

This illustrates how the same hardware can be used to perform the two instructions DVSADM8O16B16H (FIGS. 15A and 15B) and DVSADM16O8H8W (FIGS. 16A and 16B). The adders1802can be constructed with carry control as shown inFIG. 14. In a first mode adders1802operate on 8 bit data by breaking the carry chain at 8 bit boundaries (DVSADM8O16B16H). In a second mode adders1802operate on 16 bit data by breaking the carry chain at 16 bit boundaries (DVSADM16O8H8W). The nature of the packed data means the data path between bits of the operand and input bits of the adders1802is the same for both modes. A similar carry chain control operates on the row adders1503,1513,1533,1543,1553,1593,1603,1613,1633,1643,1653,1693. Similarly the relationship between the row adder output bits and the destination bits is unchanged due to the nature of the packed data.

This invention can perform 512 8 bit or 256 16 bit absolute differences per cycle as compared to 8 8 bit or 4 16 bit absolute differences per cycle in prior art. This results in an improvement of sixty four times. Proposed art dynamically performs different block searches using mask bits in control registers. This invention may also perform two horizontal pixel line searches in a single instruction in addition the a single horizontal line search.