Using mask operand obtained from composite operand to perform logic operation in parallel with composite operand

• US 5,651,121 A
• Filed: 12/18/1992
• Issued: 07/22/1997
• Est. Priority Date: 12/18/1992
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Davies, Daniel
• Primary Examiner(s): Lall, Parshotam S.
• Assistant Examiner(s): VU, VIET DUY
• Application Number:
  US07/993,938
• Time in Patent Office: 1,677 Days
• Field of Search: 395/375, 395/775, 395/800, 395/162, 364/736, 364/760, 382/33
• US Class Current: 712/200
• CPC Class Codes: G06F 7/764 Masking
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations

Abstract

A mask operand can be obtained using a composite operand. A composite operand is an operand with plural multi-bit component data items. A logic operation can be performed on the mask operand and the composite operand to select a subset of components. The mask operand can have one value, such as ON, in bit positions aligned with the subset of components and another value, such as OFF, in all other bit positions. Other operations can then be performed on the selected components. A mask operand and its inverse can be used to merge two other operands, such as by selecting the maximum or minimum of each pair of aligned components in the operands. A mask operand can be obtained from flag bits at an end of each component in a composite operand, by selecting the flag bits and propagating them across the components. A mask operand can also be obtained from flag bits at the least significant bit position by an arithmetic operation. Mask obtaining instructions and mask using instructions can be included in a software product. The mask operands can be used to filter an image to select pixels above a threshold, equal to a constant, or within a range; to compare or combine two images; to perform multiplication, division, or threshold convolution; or, more generally, to perform any image processing operation involving data driven branching.

Claims

1. A method of operating a processor;

the method comprising;

obtaining a composite operand that includes three or more component data items, each including more than one bit;

obtaining a mask operand from the composite operand;

the mask operand including, for each bit in the composite operand, a respective bit aligned with the bit in the composite operand;

the component data items including a first data item subset that includes at least two of the component data items and a second data item subset that includes at least one of the component data items;

each bit in the mask operand aligned with a bit in the first data item subset having a first value;

each bit in the mask operand aligned with a bit in the second data item subset having a second value; and

performing a logic operation in parallel using the mask operand and the composite operand;

the logic operation obtaining, for each component data item in the first data item subset, a resulting data item that has a value that depends on the component data item;

the logic operation obtaining, for each component data item in the second data item subset, a resulting data item that has a uniform value in all bits;

the uniform value in all of the bits of the resulting data item of each component data item in the second data item subset being one of the first value and the second value.

2. A method of operating a processor;

the processor including a central processing unit for executing instructions;

execution of instructions causing the central processing unit to perform operations using operands;

the central processing unit having two or more processing positions, each for performing operations using one bit;

the processing positions being connected to form an array;

the array of processing positions performing operations on operands in parallel during execution of instructions by the central processing unit;

the method comprising acts of;

providing to the central processing unit a first composite operand that includes three or more first component data items;

each first component data item including more than one bit;

each first component data item being provided to a respective subarray of the array of processing positions in the central processing unit;

operating the central processing unit to execute a first sequence of instructions;

during execution of the first sequence of instructions by the central processing unit, the array of processing positions performing a first sequence of operations in parallel on the component data items of the composite operand;

the first sequence of operations obtaining, in the subarray of each first component data item, a respective first mask data item;

the first mask data item including, for each bit in the first component data item, a respective bit aligned with the bit in the first component data item;

the first component data items including a first data item subset that includes at least two of the first component data items and a second data item subset that includes at least one of the first component data items;

each bit in a first mask data item aligned with a bit in a first component data item in the first data item subset having a first value;

each bit in a first mask data item aligned with a bit in a first component data item in the second data item subset having a second value;

the first mask data items together forming a first mask operand that can be used to perform operations selectively on the first and second data item subsets; and

operating the central processing unit to execute a second sequence of instructions;

during execution of the second sequence of instructions by the central processing unit, the array of processing positions performing a second sequence of operations in parallel in such a way that operations are performed selectively on the first and second data item subsets;

the second sequence of operations including a first logic operation using the first composite operand and the first mask operand;

the first logic operation obtaining, in the subarray of each first component data item, a respective resulting data item;

the resulting data item of each first component data item in the first data item subset having the same value as the first component data item;

the resulting data item of each first component data item in the second data item subset having a uniform value in all bits;

the uniform value in all of the bits of the resulting data item of each first component data item in the second data item subset being one of the first value and the second value.

3. The method of claim 2 in which the central processing unit is a microprocessor.

4. The method of claim 2 in which the logic operation is an AND operation.

5. The method of claim 2 in which each first component data item relates to a respective pixel of an image.

6. The method of claim 5 in which each first component data item is a gray scale pixel value.

7. The method of claim 5 in which each first component data item is a color pixel value.

8. The method of claim 2 in which the first value is ON, the second value is OFF, the first logic operation is an AND operation, and the uniform value is the second value.

9. The method of claim 2 in which the second sequence of operations performed by the array of processing positions during execution of the second sequence of instructions by the central processing unit further includes an additional operation performed in parallel using the resulting data items of the first component data items;

the additional operation obtaining, in the subarray of each first component data item in the first data item subset, a respective modified resulting data item;

the additional operation obtaining, in the subarray of each first component data item in the second data item subset, a respective unmodified resulting data item;

the modified resulting data items and the unmodified resulting data items together forming a modified resulting operand.

10. The method of claim 9 in which the second sequence of operations performed by the array of processing positions during execution of the second sequence of instructions by the central processing unit includes a second logic operation performed in parallel using the first mask operand, the first composite operand, and the modified resulting operand to obtain a modified version of the first composite operand;

the modified version of the first composite operand including the modified resulting data items.

11. A method of operating a processor;

the processor including processing circuitry for performing operations in parallel using operands;

the processing circuitry having two or more processing positions, each for performing operations using one bit;

the method comprising acts of;

providing to the processing circuitry a first composite operand and a first mask operand;

the first composite operand including three or more first component data items;

each first component data item including more than one bit;

each first component data item being provided to a respective subarray of processing positions in the processing circuitry;

the first mask operand including, for each first component data item, a respective first mask data item that is provided to the first component data item'"'"'s subarray of processing positions;

the first mask data item including, for each bit in the first component data item, a respective bit aligned with the bit in the first component data item;

the first component data items including a first data item subset that includes at least two of the first component data items and a second data item subset that includes at least one of the first component data items;

each bit in a first mask data item aligned with a bit in a first component data item in the first data item subset having a first value;

each bit in a first mask data item aligned with a bit in a first component data item in the second data item subset having a second value;

operating the processing circuitry to perform a first logic operation in parallel using the first composite operand and the first mask operand;

the first logic operation obtaining, in the subarray of each first component data item, a respective resulting data item;

the resulting data item of each first component data item in the first data item subset having the same value as the first component data item;

the resulting data item of each first component data item in the second data item subset having a uniform value in all bits;

the uniform value in all of the bits of the resulting data item of each first component data item in the second data item subset being one of the first value and the second value;

providing to the processing circuitry a second composite operand and a second mask operand;

the second composite operand including three or more second component data items;

each second component data item including more than one bit;

each second component data item being provided to a respective subarray of processing positions in the processing circuitry;

the subarray of each second component data item being aligned with the subarray of a respective one of the first component data items;

the second mask operand including, for each second component data item, a respective second mask data item that is provided to the second component data item'"'"'s subarray of processing positions;

the second mask data item including, for each bit in the second component data item, a respective bit aligned with the bit in the second component data item;

the second component data items including a third data item subset that includes at least one of the second component data items and a fourth data item subset that includes at least two of the second component data items, with the subarray of each second component data item in the third data item subset being aligned with the subarray of a respective one of the first component data items in the first data item subset and each second component data item in the fourth data item subset being aligned with the subarray of each first component data item in the second data item subset so that each bit in each second mask data item is aligned with a respective bit in a respective first mask data item;

each bit in each second mask data item being an inverse of the respective bit in the respective first mask data item, the bit in the second mask data item having the first value if the respective bit in the respective first mask data item has the second value and having the second value if the respective bit in the respective first mask data item has the first value;

operating the processing circuitry to perform a second logic operation in parallel using the second composite operand and the second mask operand;

the second logic operation obtaining, in the subarray of each second component data item, a respective resulting data item;

the resulting data item of each second component data item in the fourth data item subset having the same value as the second component data item;

the resulting data item of each second component data item in the third data item subset having the uniform value in all bits; and

operating the processing circuitry to perform a third logic operation in parallel using the resulting data items of the first component data items and using the resulting data items of the second component data items;

the third logic operation obtaining a result that includes the resulting data item of each first component data item in the first data item subset and the resulting data item of each second component data item in the fourth data item subset.

12. The method of claim 11 in which the third logic operation is an OR operation.

13. The method of claim 11 in which the result includes, for each first component data item and the respective second component data item, a resulting component data item that is equal to a maximum of the first component data item and the respective second component data item.

14. The method of claim 11 in which the result includes, for each first component data item and the respective second component data item, a resulting component data item that is equal to a minimum of the first component data item and the respective second component data item.

15. A method of operating a processor;

the processor including processing circuitry for performing operations in parallel using operands;

the processing circuitry having two or more processing positions, each for performing operations using one bit;

the method comprising acts of;

providing to the processing circuitry a composite operand that includes two or more component data items;

each component data item including more than one bit;

each component data item being provided to a respective subarray of processing positions in the processing circuitry;

the subarray of each component data item including an end of the subarray;

the processing positions including, at the end of each subarray, a respective flag bit position; and

operating the processing circuitry to perform a mask obtaining operation in parallel using the composite operand;

the mask obtaining operation obtaining, in the subarray of each component data item, a respective mask data item;

the mask data item including, for each bit in the component data item, a respective bit aligned with the bit in the component data item;

the component data items including a first data item subset that includes at least one of the component data items and a second data item subset that includes at least one of the component data items;

each bit in a mask data item aligned with a bit in a component data item in the first data item subset having a first value;

each bit in a mask data item aligned with a bit in a component data item in the second data item subset having a second value;

the mask data items together forming a mask operand;

the mask obtaining operation comprising;

a flag bit operation that uses the composite operand to obtain a flag bit operand;

the flag bit operand including the first value in the flag bit position of each component data item in the first data item subset and the second value in the flag bit position of each component data item in the second data item subset;

the flag bit operand further including the second value in all other processing positions in the subarray of each component data item;

a series of suboperations, each suboperation obtaining a respective shifted version of the flag bit operand; and

a logic operation that uses the flag bit operand and the shifted versions of the flag bit operand to obtain the mask operand.

16. A method operating a processor;

the processor including processing circuitry for performing operations in parallel using operands;

the processing circuitry having two or more processing positions, each for performing operations using one bit;

the method comprising acts of;

providing to the processing circuitry a composite operand that includes two or more component data items;

each component data item including more than one bit;

each component data item being provided to a respective subarray of processing positions in the processing circuitry;

the subarray of each component data item including a least significant bit position at an end of the subarray; and

operating the processing circuitry to perform a mask obtaining operation in parallel using the composite operand;

the mask obtaining operation obtaining, in the subarray of each component data item, a respective mask data item;

the mask data item including, for each bit in the component data item, a respective bit aligned with the bit in the component data item;

the component data items including a first data item subset that includes at least one of the component data items and a second data item subset that includes at least one of the component data items;

each bit in a mask data item aligned with a bit in a component data item in the first data item subset having a first value;

each bit in a mask data item aligned with a bit in a component data item in the second data item subset having a second value;

the mask data items together forming a mask operand;

the mask obtaining operation comprising;

a flag bit operation that uses the composite operand to obtain a flag bit operand;

the flag bit operand including the first value in the least significant bit position of each component data item in the first data item subset and the second value in the least significant bit position of each component data item in the second data item subset;

the flag bit operand further including the second value in all other processing positions in the subarray of each component data item; and

an arithmetic operation in parallel that uses the flag bit operand to obtain the mask operand.

17. A processor comprising:

processing circuitry for performing operations in parallel using operands;

the processing circuitry having two or more processing positions, each for performing operations using one bit;

the processing circuitry comprising K-bit shifting circuitry for shifting an operand by K bits within the processing positions, where K is greater than one; and

control circuitry connected for providing control signals to the processing circuitry and the K-bit shifting circuitry;

the control signals causing the processing circuitry to perform a flag bit obtaining operation using a composite operand that includes two or more component data items, each including more than one bit;

the component data items including a first data item subset that includes at least one of the component data items and a second data item subset that includes at least one of the component data items;

the processing circuitry performing the flag bit obtaining operation using each component data item in a respective subarray of processing positions to obtain a respective resulting data item in the subarray;

the subarray of each component data item including a most significant bit position at a first end of the subarray and a least significant bit position at a second end of the subarray;

the processing positions including, adjacent the first end of each subarray, a respective flag bit position;

the processing circuitry performing the flag bit obtaining operation using each component data item to obtain a respective flag bit in the respective flag bit position;

the flag bit having the first value if the component data item is in the first data item subset and having a second value if the component data item is in the second data item subset;

the control signals causing the processing circuitry and the K-bit shifting circuitry to perform a flag shift/select operation using the resulting data items and flag bits of the component data items to obtain a flag bit operand;

the flag bit operand including the first value in the least significant bit position of each component data item in the first data item subset and the second value in the least significant bit position of each component data item in the second data item subset;

the flag bit operand further including the second value in the flag bit position and in all other processing positions in the subarray of each component data item;

the flag shift/select operation including an operation of the K-bit shifting circuitry to shift the flag bit of each component data item by K bits in shifting the flag bit from the flag bit position to the least significant bit position;

the control signals further causing the processing circuitry to perform an arithmetic operation in parallel that uses the flag bit operand to obtain, in the subarray of each component data item, a respective mask data item;

the mask data item including, for each bit in the component data item, a respective bit aligned with the bit in the component data item;

each bit in a mask data item aligned with a bit in a component data item in the first data item subset having a first value;

each bit in a mask data item aligned with a bit in a component data item in the second data item subset having a second value;

the mask data items together forming a mask operand.

18. An article of manufacture for use in a system that includes:

memory for storing data items, each including more than one bit;

a storage medium access device for accessing a medium that stores data; and

a processor connected for accessing the data items stored in the memory and for receiving data from the storage medium access device;

the processor including a central processing unit for executing instructions;

execution of instructions causing the central processing unit to perform operations using operands;

the central processing unit having two or more processing positions, each for performing operations using one bit;

the processing positions being connected to form an array;

the array of processing positions performing operations on operands in parallel during execution of instructions by the central processing unit;

the article comprising;

a data storage medium that can be accessed by the storage medium access device when the article is used in the system; and

instruction data stored by the data storage medium so that the storage medium access device can provide the instruction data to the central processing unit when the article is used in the system;

the instruction data indicating a sequence of instructions the central processing unit can execute;

during execution of the sequence of instructions by the central processing unit, the array of processing positions performing a sequence of operations in parallel;

the sequence of operations including;

a first subsequence of operations that uses a composite operand to obtain a mask operand;

the composite operand including two or more component data items from the data items stored in the memory, each component data item including more than one bit;

each component data item being in a respective subarray of the processing positions in the array of processing positions;

the array of processing positions, in performing the first subsequence of operations;

using the composite operand to obtain, in the subarray of each component data item, a respective mask data item;

the mask data item including, for each bit in the component data item, a respective bit aligned with the bit in the component data item;

the component data items including a first data item subset that includes at least one of the component data items and a second data item subset that includes at least one of the component data items;

each bit in a mask data item aligned with a bit in a component data item in the first data item subset having a first value;

each bit in a mask data item aligned with a bit in a component data item in the second data item subset having a second value;

the mask data items together forming the mask operand; and

a second subsequence of operations that operate selectively on the first and second data item subsets;

the second subsequence of operations including a logic operation that is performed in parallel using the composite operand and the mask operand;

the logic operation using the composite operand and the mask operand to obtain, in the subarray of each component data item in the first data item subset, a resulting data item having the same value as the component data item and, in all of the bits of the subarray of each component data item in the second data item subset, a uniform value;

the uniform value in all of the bits of each component data item in the second data item subset being one of the first value and the second value.

19. The article of claim 18 in which the central processing unit is a microprocessor;

the instruction data comprising code that the microprocessor can execute.

20. The article of claim 18 in which the data storage medium is a magnetic storage medium.

21. The article of claim 18 in which the data storage medium is an optical storage medium.

22. The article of claim 18 in which the data storage medium comprises semiconductor memory.

23. A method of operating a processor;

the method comprising;

obtaining first and second composite operands and first and second mask operands, all with equal numbers of bits;

each of the first and second composite operands including two or more component data items, each including more than one bit;

the component data items of the first composite operand including a first data item subset that includes at least one of the component data items of the first composite operand and a second data item subset that includes at least one of the component data items of the first composite operand;

the component data items of the second composite operand including a third data item subset that includes at least one of the component data items of the second composite operand and a fourth data item subset that includes at least one of the component data items of the second composite operand;

each component data item in the third data item subset being aligned with a component data item in the first data item subset;

each component data item in the fourth data item subset being aligned with a component data item in the second data item subset;

each bit in the first mask operand aligned with a bit in the first data item subset having a first value;

each bit in the first mask operand aligned with a bit in the second data item subset having a second value;

each bit in the second mask operand aligned with a bit in the third data item subset having the second value;

each bit in the second mask operand aligned with a bit in the fourth data item subset having the first value;

performing a first logic operation in parallel using the first mask operand and the first composite operand;

the first logic operation obtaining, for each component data item in the first data item subset, a resulting data item that has a value that depends on the component data item;

the first logic operation obtaining, for each component data item in the second data item subset, a resulting data item that has a uniform value in all bits;

the uniform value in all of the bits of the resulting data item of each component data item in the second data item subset being one of the first value and the second value;

the resulting data items from the first logic operation together forming a third composite operand;

performing a second logic operation in parallel using the second mask operand and the second composite operand;

the second logic operation obtaining, for each component data item in the fourth data item subset, a resulting data item that has a value that depends on the component data item;

the second logic operation obtaining, for each component data item in the third data item subset, a resulting data item that has a uniform value in all bits;

the uniform value in all of the bits of the resulting data item of each component data item in the second data item subset being one of the first value and the second value;

the resulting data items from the second logic operation together forming a fourth composite operand; and

performing a third logic operation in parallel using the third and fourth composite operands;

the third logic operation obtaining a merged composite operand that includes only the resulting data items from the third and fourth composite operands that have values that depend on component data items in the first and fourth data items subsets.

24. A method of operating a processor to perform multiplication, the processor including a central processing unit for executing instructions;

execution of instructions causing the central processing unit to perform operations using operands;

the central processing unit having two or more processing positions, each for performing operations using one bit;

the processing positions being connected to form an array;

the array of processing positions performing operations on operands in parallel during execution of instructions by the central processing unit;

the method comprising;

operating the processor to obtain a multiplier operand and a multiplicand operand;

the multiplier operand including two or more multiplier data items, each including more than one bit position;

the multiplier data items all having equal numbers of bit positions;

the multiplicand operand including, for each multiplier data item, a multiplicand data item;

the processor providing each multiplier data item and its multiplicand data item to a respective subarray of the array of processing positions in the central processing unit;

operating the central processing unit to execute instructions;

during execution of the instructions by the central processing unit, the array of processing positions;

for each bit position in the multiplier data items, using the multiplier operand to obtain a mask operand in parallel;

the mask operand for a bit position including, for each multiplier data item, a mask data item in the subarray of the multiplier data item;

the mask data item for each multiplier data item having a value in every bit position equal to a value in the bit position of the multiplier data item;

for each bit position in the multiplier data items, performing a logic operation in parallel using the bit position'"'"'s mask operand and the multiplicand operand;

the logic operation obtaining, for each multiplier data item, a resulting data item in the subarray of the multiplier data item;

the resulting data items from the logic operation together forming a result operand; and

combining the result operands for all of the bit positions to obtain a composite product operand;

the composite product operand including, for each multiplier data item, a product data item indicating a product of the multiplier data item and its multiplicand data item;

the product data item being in the subarray of the multiplier data item.

25. A method of operating a processor, the processor including a central processing unit for executing instructions;

execution of instructions causing the central processing unit to perform operations using operands;

the central processing unit having two or more processing positions, each for performing operations using one bit;

the processing positions being connected to form an array;

the array of processing positions performing operations on operands in parallel during execution of instructions by the central processing unit;

the method comprising;

operating the processor to obtain a composite operand that includes two or more component data items, each including one bit position;

operating the processor to spread the composite operand to obtain a mask operand that includes, for each component data item in the composite operand, a mask data item;

all of the mask data items including equal numbers of bit positions, the numbers being greater than one;

the processor providing each mask data item to a respective subarray of the array of processing positions in the central processing unit;

operating the central processing unit to execute instructions;

during execution of the instructions by the central processing unit, the array of processing positions;

performing operations in parallel to obtain a result operand that includes, for each component data item in the composite operand, a result data item;

all of the result data items including equal numbers of bit positions, the numbers being greater than one;

each result data item being obtained in a respective subarray of the array of processing positions in the central processing unit;

the array of processing positions, in performing operations in parallel;

performing a logic operation in parallel using the mask operand; and

operating the processor to subsample the result operand to obtain a subsampled result operand;

the subsampled result operand including one bit position for each component data item in the composite operand;

each component data item'"'"'s bit position having a value that depends on the component data item'"'"'s result data item.