METHOD AND SYSTEM FOR PARALLEL HISTOGRAM CALCULATION IN A SIMD AND VLIW PROCESSOR

• US 20090276606A1
• Filed: 03/12/2009
• Published: 11/05/2009
• Est. Priority Date: 06/03/2002
• Status: Active Grant

• Current Assignee: Tibet Mimar
• Original Assignee: Tibet Mimar
• Inventors: MIMAR, TIBET
• Granted Patent: US 8,069,334 B2
• Time in Patent Office: Days
• US Class Current: 712/4
• CPC Class Codes: G06F 15/8092 Array of vector units
• CPC Class Codes: G06F 9/3001 Arithmetic instructions
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: G06F 9/3004 to perform operations on memory

Abstract

The present invention provides histogram calculation for images and video applications using a SIMD and VLIW processor with vector Look-Up Table (LUT) operations. This provides a speed up of histogram calculation by a factor of N times over a scalar processor where the SIMD processor could perform N LUT operations per instruction. Histogram operation is partitioned into a vector LUT operation, followed by vector increment, vector LUT update, and at the end by reduction of vector histogram components. The present invention could be used for intensity, RGBA, YUV, and other type of multi-component images.

Claims

1-18. -18. (canceled)

19. A system for performing histogram calculations in a Single-Instruction-Multiple-Stream (SIMD) processor for audio, video, 3-D graphics, and digital signal processing functions comprising:

a. a program flow control unit coupled to the processor;

b. a vector register file coupled to the program control flow unit which includes a set of vector registers, where each vector register comprises N vector elements;

c. a data memory which is partitioned into N modules, wherein each of the N modules is independently addressed and a portion of data ports of the data memory are coupled to the vector register file;

d. a plurality of Look-Up Tables (LUTs), wherein each LUT corresponds to a respective module of the N modules, each LUT for storing count values;

e. a vector execution unit within the processor comprising N computing elements, each computing element corresponding to a respective LUT module, wherein for each computing element, the unit;

(i) performs a vector element data read operation to provide an entry index for a LUT and perform an LUT read operation;

(ii) increments each read LUT count value; and

, (iii) stores back the respective incremented count value; and

, wherein the output and inputs of vector execution unit are coupled to read and write ports of the vector register file; and

f. a port of the vector register file selectively coupled to an address input of the data memory;

wherein the processor performs a histogram operation.

20. The system of claim 19, wherein the SIMD processor performs operations on vectors in a single clock cycle using program instructions comprising:

a. setting a LUT base address register to point to a beginning point of a LUT to be stored in the data memory;

b. initializing a LUT module area in the data memory to zero;

c. reading a vector of N data values from a vector register and reading a corresponding location for each of the N LUT modules using the data values as the index address;

d. incrementing each read count value in the LUT by one, using vector arithmetic operations;

e. storing the incremented count value into its respective entry using a vector LUT update instruction, thereby updating the LUT; and

f. adding the count values in the LUT modules together to provide the histogram table.

21. The system of claim 19 wherein histogram operation comprises:

a. initializing all LUT contents to zero by multiple vector write operations by scanning all LUT addresses;

b. loading input data into a vector register, and reading the input data to perform a vector Look-Up-Table read operation;

c. incrementing the count value read from the LUT by one as a means of updating LUT count values;

d. performing a vector LUT write operation by writing back updated LUT count values to the vector LUT pointed to by the vector register containing input data values; and

e. adding same type of LUT data for each histogram bins to reduce vector components by using vector arithmetic instructions.

22. The system of claim 21, wherein a RISC processor is used for input/output processing for scalar and vector values and for program flow control, and SIMD processing is used for data processing, whereby one RISC and one SIMD instruction are executed every clock cycle.

23. The system of claim 22, wherein the value of N is an integer ranging from 8 to 256.