Hewlett-packard Company

Other

Hewlett-packard Corporation

Ruby B Lee

Allen Jay Baum

Joel D Lamb

Michael J Mahon

William R Bryg

Dale Calvin Morris

Stephen G Burger

Charles R Dowdell

Vasudev Bhaskaran

Jerome C Huck

Jeffrey D Kurtze

Barry J Flahive

Bernard L Stumpf

Daryl K Odnert

John Paul Beck

Russell Kao

Vivek S Pendharkar

Stephen L Bass

Steven S Muchnick

An apparatus for operating on the contents of an input register to generate the contents of an output register which contains a permutation, with or without repetitions, or a combination of the contents of the input register. The apparatus partitions the input register into a plurality of sub-words, each sub-word being characterized by a location in the input register and a length greater than one bit. In response to an instruction specifying a rearrangement of the input register, the present invention directs at least one of the sub-words in the input register to a location in the output register that differs from the location occupied by the sub-word in the input register. The ordering of the sub-words in the output register differ from the order obtainable by a single shift instruction. In the preferred embodiment of the present invention, the invention is implemented by modifying a conventional shifter comprising a plurality of layers of multiplexers. The modification comprises independently setting the control signals for at least one of the multiplexers in at least one of the layers.

Processor for performing subword permutations and combinations

A computer apparatus which detects a store or load operation into or from a shared memory page by a program that does not provide for synchronization when executed by a CPU that completes instructions out of program order. After the store or load is detected, the CPU explicitly orders operations into the shared memory page. Store operations are ordered such that no new store into the shared memory page is performed until all prior store operations into the shared memory page are complete. Also, load operations are ordered such that load operations from the shared memory page are performed in program order. This ordering is achieved by maintaining a process bit and a memory attribute bit associated with a shared memory page. When both bits are true, all load or store operations referencing the shared memory page are ordered.

Computer that selectively forces ordered execution of store and load

An apparatus that can also be used for generating the average of two integers. The apparatus can be divided into a plurality of sub-adders that operate on sub-words of the input integers in parallel. Hence, the adder can be used for adding or subtracting one set of two integers wherein each integer is of some predetermined length or a plurality of sets of two integers provided the sum of the lengths of the integers is less than or equal to this predetermined length. The apparatus can also generate the sum, or difference, of each of the sub-words divided by two. The parallel operations can be carried out in response to a single instruction. The results of the division by two are rounded in a manner that eliminates biasing of the results.

Parallel adding and averaging circuit and method

Circuitry combines a first operand A.sub.0, a second operand A.sub.1, and a third operand X in a blend function to produce a result Z. The result Z has a value equal to X*A.sub.0 +(1-X)* A.sub.1. The circuitry includes a plurality of logic gates organized in rows. When performing the blend operation each logic gates selects either a bit of the first operand A.sub.0 or a bit of the second operand A.sub.1. The selection for each logic gate depends upon bits of the third operand X. More specifically, each of the plurality of rows of logic gates selects the first operand A.sub.0 as output when an associated bit of the third operand X is at logic 1, and selects the second operand A.sub.1 as output when the associated bit of the third operand X is at logic 0. In addition to output generated by the plurality of rows of logic gates, a correction term is generated. For the blend operation, the correction term generated is the second operand A.sub.1. Partial product circuitry sums outputs of each row of logic gates and the correction term, to produce the result Z, so that the result Z has a value equal to X*A.sub.0 +(1-X)*A.sub.1.

Expediting blending and interpolation via multiplication

A multiplier is modified to perform a population count. A first value is input to the multiplier in place of a first multiplicand. The first value is an operand upon which the population count is to be performed. A second value is input into the multiplier in place of a second multiplicand. Each bit of the second value is at logic one. In partial product rows, certain partial products are forced to logic zero. This is done so that only a single column of partial products is used to calculate the population count. The partial products are then summed to produce a result. The present invention also may be adapted for use with Booth-encoded multipliers.

Performing a population count using multiplication

A multiplier is modified to perform a tree addition. A first value is input to the multiplier in place of a first multiplicand. The first value is a concatenation of addends upon which the tree addition is performed. A second value is input into the multiplier in place of a second multiplicand. Each bit of the second value is at logic zero except for a first subset of bits. The first subset of bits are bits of the second value, starting with the low order bit, which are at intervals equal to a bit length of each addend. Each of the first subset of bits is set to logic one. In partial product rows in the multiplier which correspond to the first subset of bits, certain partial products are forced to logic zero. This is done in such a way that all the addends for the tree addition are aligned in columns of the multiplier. The partial products are then summed to produce a result.

Performing tree additions via multiplication

A computer system facilitates efficient mixing of multiple sub-word items. Mixing circuitry is connected to a plurality of registers and a result register. The mixing circuitry mixes multiple sub-word items packed into the plurality of registers. The multiple sub-word items, when mixed, are placed in the result register. In the preferred embodiment, the mixing circuitry is implemented using a plurality of multiplexors. Control circuitry, connected to the control inputs of the multiplexors, generates control signals which control the mixing of multiple sub-word items by the multiplexors.

Efficient selection and mixing of multiple sub-word items packed into

A system allows parallel data processing within a single processor. In order to allow for parallel processing of data, an arithmetic logic unit or other operation executing entity within the processing system such as a shifter is partitioned. Within each partition operations are performed on a portion of one or more operands. When the operation is to be performed on full word length operands, there is no parallel processing. Thus data is allowed to freely propagate across boundaries between the partitions. When performing the operation in parallel using a plurality of operands of less than one full word in length, data is prevented from being propagated across at least one boundary between the partitions. The principles of the present invention may also be utilized to implement a multiplier which performs parallel multiplication of partial word multiplicands.

Performance of an operation on whole word operands and on operations in

A N-bit by N-bit multiplication apparatus having the ability to select a part of the multiplication result for storage into a result register N-bits wide. A first embodiment of the invention allows a sequence of n-bits from the N-bit by N-bit multiply result to be stored into an N-bit wide register. N+1 to 1 multiplexors are utilized to select which of the multiply result bits are stored into the result register in response to a computer instruction. The second preferred embodiment utilizes multiplexors having fewer than N+1 inputs to select discrete subsets of the multiply result bits for storage into the N-bit wide result register. In this manner, less complex multiplexors are required which take less chip area to implement. The third preferred embodiment utilizes multiple sets of multiplexors to select multiple subresults generated by a parallel multiplication operation. The multiple subresults are stored in a single result register. By allowing subresults to be selected and stored as part of the multiply operation, a multiply apparatus according to the present invention is more time and instruction efficient than prior art devices.

Computer multiply instruction with a subresult selection option

A computer instruction and apparatus for performing a N-bit by N-bit multiplication and having the ability to select a part of the multiplication result for storage into a result register N-bits wide. A first embodiment of the invention allows a sequence of n-bits from the N-bit by N-bit multiply result to be stored into an N-bit wide register. N+1 to 1 multiplexors are utilized to select which of the multiply result bits are stored into the result register in response to a multiply and select computer instruction. The second preferred embodiment utilizes multiplexors having fewer than N+1 inputs to select discrete subsets of the multiply result bits for storage into the N-bit wide result register. In this manner, less complex multiplexors are required which take less chip area to implement. The third preferred embodiment utilizes multiple sets of multiplexors to select multiple subresults generated by a parallel multiplication operation. The multiple subresults are stored in a single result register. By allowing subresults to be selected and stored as part of the multiply operation, a multiply apparatus according to the present invention is more time and instruction efficient than prior art devices.

Integer multiply instructions incorporating a subresult selection option

An inverse discrete cosine transform ('IDCT') implementation specifically for the decompression of JPEG, MPEG and Px64 encoded image and video data uses a preprocessing step embedded in a Huffman decoding process to classify data blocks prior to computing the IDCT. The use of data block classification, along with the use of pruned IDCTs appropriate for the specific block class, reduces the total number of multiply and addition operations necessary to decompress an encoded data block, and thereby allows faster data decompression. Synthesis of coefficients suitable for multiplication allows efficient implementation of the novel decompression technique in typical microprocessor architectures, including RISC processor architectures.

Method and apparatus for fast digital signal decoding

A computer system provides handling of positive and negative overflow. A first arithmetic operation is performed on a first n-bit unsigned binary operand and a second n-bit signed binary operand to produce an n-bit unsigned binary result. Overflow detection logic circuitry within the arithmetic logic unit detects positive overflow or negative overflow resulting from the arithmetic operation. When there is a positive overflow, saturation logic replaces the output of the two's complement adder with a value of 2.sup.n-1. When there is a negative overflow, the saturation logic replaces the output of the two's complement adder with a value of 0. In an alternate embodiment, a first arithmetic operation is performed on a first n-bit signed binary operand and a second n-bit signed binary operand to produce an n-bit positive signed binary result. For example the arithmetic operation is an addition or subtraction performed by a two's complement adder. In the alternate embodiment, overflow detection logic circuitry within the arithmetic logic unit detects positive overflow or negative overflow resulting from the arithmetic operation. When there is a positive overflow, saturation logic replaces the output of the two's complement adder with a value of 2.sup.n-1 -1. When there is a negative overflow, the saturation logic replaces the output of the two's complement adder with a value of 0.

Efficient hardware handling of positive and negative overflow resulting

A circuit for shifting the bits of an X word to obtain a Y word which is rounded to the nearest odd integer if any bit having the value 1 was shifted off of the word during the shifting operation. The circuit avoids biasing in the integer rounding operation. The shifting operations are accomplished with the aid of multiplexing circuits. The rounding operation is accomplished with the aid of multiplexing circuits that connect the least significant bit of Y to (X.sub.0 OR X.sub.1 OR . . . X.sub.m), where m is the number of places by which X is shifted.

Shift and rounding circuit and method

An apparatus for combining the contents of an X register, shifted by m places, with the contents of a Y register to generate a result Z. The functional unit can also be configured to perform parallel operations on sub-operands in the X and Y registers. The division of the apparatus into sub-operands is controlled by a mask which specifies the boundary of the sub-operands. The shifting operation is accomplished by multiplexers that connect the p.sup.th bit of the X register to the adder stage that operates on bit Y.sub.p-m of the Y register. Circuitry is provided at the boundary of the sub-operands to prevent the bit signals corresponding to the X register from being routed across a sub-operand boundary. Similarly, circuitry is provided for preventing the carry output of an adder stage that operates on one sub-operand from being propagated to an adder stage that operates on another sub-operand.

Parallel shift and add circuit and method

A method for operating a digital computer in response to the occurrence of an exception is disclosed. The method provides for the examination both of the contents of a predetermined computer location and of the instruction code for the instruction causing the exception. The computer then utilizes the result of those examinations to determine the dismissibility of the exception. The computer transfers control to the next instruction after the instruction which caused the exception if that instruction is dismissible.

Growing community of inventors

Los Altos Hills, CA, United States of America

Ruby B Lee