Pipelining and parallelism for implementing a mixture model

Abstract

One factor in limiting the speed of conventional implementations of mixture models is that the algorithm involves many decisions where different operations are fetched and performed depending on the outcome of the decisions. These decisions cause flushing of the pipeline, and thus prevent the realization of a highly parallel pipeline in a processor. Without parallelism, the throughput of the pipeline in the processor, i.e., the ability to process many samples of the digital input at a time, is limited. To alleviate this issue, implementation of the mixture model is reformulated, among other things, by embedding decisions into the process flow as multiplicative factors. The resulting implementation alleviates the need to use if-else statements for the decisions and reduces the number of times the pipeline has to be flushed. The implementation enables a pipeline with a higher degree of parallelism and thereby increases throughput and speed of the implementation.

What is claimed is: 
     
         1 . A digital signal processor for enabling parallel processing of decisions involving a mixture model comprising a plurality of probability distributions, the digital signal processor comprising:
 hardware computation blocks comprising parallel multiplier-accumulator blocks (MACS);   memory comprising samples and instructions for processing the samples based on the mixture model, wherein the instructions, when executed by the hardware computation blocks, perform the following operations:
 computing a first decision variable based on a first distance of a pixel from a first probability distribution of the mixture model, and a first distance threshold, wherein the first decision variable equals to 1 or 0; 
 computing, a second decision variable based on a second distance of the pixel from a second probability distribution of the mixture model and a second distance threshold, wherein the second decision variable equals to 1 or 0; 
 updating, using the parallel MACS, a first parameter for the first probability distribution using the first decision variable; and 
 updating, using the parallel MACS, a second parameter for the second probability distribution using the second decision variable during a same clock cycle as the updating of the first parameter. 
   
     
     
         2 . The digital signal processor of  claim 1 , wherein:
 the MACS implement infinite impulse response filters; and   coefficients of the infinite impulse response filters to update the first parameter and the second parameter are computed using on the first decision variable, the second decision variable, and a predefined learning rate.   
     
     
         3 . The digital signal processor of  claim 1 , wherein:
 the hardware computation blocks further comprise a subtraction hardware computation block; and   computing of the first decision variable comprises providing the first distance and the first distance threshold as operands of the subtraction hardware computation block, extracting a sign bit of a result of the subtraction hardware computation block, and setting the sign bit as the first decision variable.   
     
     
         4 . The digital signal processor of  claim 1 , wherein:
 the first parameter is one of the following: a weight, a mean, and a variance of the first probability distribution; and   the second parameter is one of the following: a weight, a mean, and a variance of the second probability distribution.   
     
     
         5 . A method implemented on a digital signal processor having hardware computation blocks, for classifying pixels of an image frame based on a mixture model comprising a plurality of probability distributions, the method comprising:
 computing, using the hardware computation blocks, a first decision variable based on a first distance of a pixel from a first probability distribution of the mixture model, and a first distance threshold, wherein the first decision variable equals to 1 or 0;   computing, using the hardware computation blocks, a second decision variable based on a second distance of the pixel from a second probability distribution of the mixture model and a second distance threshold, wherein the second decision variable equals to 1 or 0;   updating, using the hardware computation blocks, a first parameter for the first probability distribution using the first decision variable; and   updating, using the hardware computation blocks, a second parameter for the second probability distribution using the second decision variable, during a same clock cycle as the updating of the first parameter.   
     
     
         6 . The method of  claim 5 , wherein updating the first parameter comprises:
 setting a first multiplicative factor as 1 subtracted by a predefined learning rate.   
     
     
         7 . The method of  claim 5 , wherein updating the first parameter comprises:
 setting a second multiplicative factor as the first decision variable.   
     
     
         8 . The method of  claim 5 , wherein updating the first parameter comprises:
 setting a first multiplicative factor as 1 subtracted by a predefined learning rate;   setting a second multiplicative factor as the first decision variable; and   setting an updated value for the first parameter by (1) multiplying the first multiplicative factor with a prior value of the first parameter, (2) multiplying the second multiplicative factor with the predefined learning rate, and (3) setting the updated value for the first parameter as a sum of (1) and (2).   
     
     
         9 . The method of  claim 5 , wherein updating the first parameter and updating the second parameter are performed without use of an if-else statement or branching. 
     
     
         10 . The method of  claim 5 , wherein updating the first parameter and updating the second parameter are performed using two infinite impulse response filters executing in parallel. 
     
     
         11 . The method of  claim 5 , wherein updating the first parameter comprises:
 setting a first multiplicative factor as 1 subtracted by a predefined learning rate;   setting a second multiplicative factor as the first decision variable; and   setting an updated value for the first parameter by using the first multiplicative factor and the second multiplicative factor as coefficients of an infinite impulse response filter.   
     
     
         12 . The method of  claim 5 , wherein:
 the first parameter is one of the following: a weight, a mean, and a variance of the first probability distribution; and   the second parameter is one of the following: a weight, a mean, and a variance of the second probability distribution.   
     
     
         13 . A digital signal processor for enabling parallel processing of decisions involving a mixture model comprising a plurality of probability distributions, the digital signal processor comprising:
 hardware computation blocks comprising parallel multiplier-accumulator blocks (MACS);   memory comprising pixels and instructions for processing the pixels based on the mixture model, wherein the instructions, when executed by the hardware computation blocks, perform the following operations:   computing a decision variable based on a distance of a pixel from a probability distribution of the mixture model, and a distance threshold, wherein the decision variable equals to 1 or 0;   updating, using the parallel MACS, a first parameter for the probability distribution using the decision variable; and   updating, using the parallel MACS, a second parameter for the probability distribution using the decision variable, during a same clock cycle as the updating of the first parameter.   
     
     
         14 . The digital signal processor of  claim 13 , wherein the first parameter and the second parameter are two of the following: a weight, a mean, and a variance of the probability distribution. 
     
     
         15 . The digital signal processor of  claim 13 , wherein:
 the parallel MACS implement infinite impulse response filters; and   coefficients of the infinite impulse response filters to update the first parameter and the second parameter are computed using the decision variable and a predefined learning rate.   
     
     
         16 . The digital signal processor of  claim 13 , wherein:
 the hardware computation blocks further comprise a subtraction hardware computation block; and   computing of the decision variable comprises providing the distance and the distance threshold as operands of the subtraction hardware computation block, extracting a sign bit of a result of the subtraction hardware computation block, and setting the sign bit as the decision variable.   
     
     
         17 . The digital signal processor of  claim 13 , wherein the operations further comprise:
 setting a first multiplicative factor as 1 subtracted by a predefined learning rate.   
     
     
         18 . The digital signal processor of  claim 13 , wherein the operations further comprise:
 setting a second multiplicative factor as the decision variable.   
     
     
         19 . The digital signal processor of  claim 13 , wherein:
 the operations further comprise:
 setting a first multiplicative factor as 1 subtracted by a predefined learning rate; and 
 setting a second multiplicative factor as the decision variable; and 
   updating the first parameter comprises (1) multiplying the first multiplicative factor with a prior value of the first parameter, (2) multiplying the second multiplicative factor with the predefined learning rate, and (3) setting the updated value for the first parameter as a sum of (1) and (2).   
     
     
         20 . The digital signal processor of  claim 13 , wherein the operations further comprise:
 updating, using the parallel MACS, a third parameter for the probability distribution using the decision variable, during a same clock cycle as the updating of the first parameter and the updating of the second parameter.