Method and system for parallel statistical inference on highly parallel platforms

1. A method of statistical inference, the method comprising:

(a) providing a computing platform comprising a Central Processing Unit (CPU) and a Graphical Processing Unit (GPU);

(b) generating a one or more level arc-based recognition network for a problem, comprising:

a plurality of epsilon arcs;

a plurality of non-epsilon arcs;

a plurality of states that may be interconnected by one or more epsilon or non-epsilon arcs; and

(c) selectively flattening the levels of the recognition network so as to improve inference speed;

(d) wherein the recognition network is executed on the CPU and the GPU;

(e) wherein the selectively flattening step comprises replacing one or more epsilon arcs with non-epsilon arcs, wherein semantics of the recognition network are preserved;

(f) generating an incoming array for a target state in the recognition network, said incoming array comprising:

a set of incoming states pointing to the target state; and

a corresponding weight that each incoming state will traverse to the target state;

(g) selectively pruning the incoming array to remove states with a corresponding probability below a threshold, thereby resulting in a reduced incoming state array; and

(h) mapping the reduced incoming state array to a port array.

2. The method of claim 1 , wherein the selectively flattening step results in a flatter recognition network selected from a group of flatter networks consisting of: a two-level network and a one-level network.

3. The method of claim 1 , further comprising:

selectively duplicating parts of the recognition network so as to reduce the size of the port array to a size represented by a Least Significant Bits (LSBs) portion of a merged word associated with each of the reduced incoming state array elements.

4. The method of claim 3 , further comprising:

assigning a weight to a Most Significant Bits (MSBs) portion of the merged word associated with each of the reduced incoming array state elements;

wherein the weight represents the corresponding probability that the reduced incoming array state element will traverse to the target state.

5. The method of claim 4 , further comprising:

traversing the recognition network in one- or two-levels of parallel traversal;

wherein the traversal from the reduced incoming state array to the target state is conflict-free.

6. The method of claim 5 , wherein the conflict-free traversal uses an extremum of the merged word weight associated with the reduced incoming array state elements.

7. The method of claim 6 , wherein the extremum is selected from a group of extrema consisting of: a maximum and a minimum.

8. The method of claim 6 , wherein the conflict-free traversal extremum is performed on the GPU.

9. The method of claim 8 , wherein the traversal extremum step is performed using one- or two-levels of atomic extremum functions on the GPU.

10. The method of claim 1 , wherein the generating the incoming array corresponding weight is performed on the GPU.

11. The method of claim 1 , wherein the problem is selected from a group of problems consisting of:

Large Vocabulary Continuous Speech Recognition (LVCSR);

Optical Character Recognition (OCR); and

automatic language translation.

12. The method of claim 1 , wherein the method is implemented in the form of a CPU and GPU executable stored on a computer readable medium which when executed carries out the steps of the method.

13. The method of claim 1 , wherein the CPU and GPU communicate either directly, or by means of a shared memory, or by both directly and by means of a shared memory.

14. The method of claim 1 , wherein the CPU and GPU have either a same or different hardware architecture.

15. A statistical inference system, comprising:

a programmable CPU controlling a GPU; and

programming executable on the CPU that causes the GPU to carry out operations comprising:

selectively flattening levels of a recognition network to improve inference speed; and

selectively duplicating parts of the recognition network to minimize a critical section in atomic accesses to as few as one atomic instruction.

16. A statistical inference method, comprising:

selectively flattening levels of a recognition network to improve inference speed; and

selectively duplicating parts of the recognition network to minimize a number of atomic operations;

providing a programmable CPU controlling a programmable GPU;

wherein programming executable on the CPU causes the programmable GPU to carry out operations comprising:

the selectively flattening step; or

the selectively duplicating step; or

the selectively flattening step and the selectively duplicating step.

17. The statistical inference method of claim 16 , further comprising:

executing the recognition network by using a merged word to minimize atomic operations in the GPU.