Arithmetic logic unit

Abstract

An arithmetic logic unit (ALU) including a first routing grid connected to multiple data lanes to drive first data to the data lanes. A second routing grid is connected to the data lanes to drive second data to the data lanes. Each of the data lanes include multiple, e.g. N, functional units with first inputs from the first routing grid and second inputs from the second routing grid. The functional units compute pairwise a function of the respective first data on the respective first inputs and the respective second data on the respective second inputs. Each of the data lanes include a reduction unit with inputs adapted to receive K′ bits per word from the functional units. The reduction unit is configured to perform a reduction operation configured to output an output result having a reduced number J′ bits per word, wherein J′ is less than N multiplied by K′.

We claim: 
     
         1 . An arithmetic logic unit (ALU) comprising:
 a first routing grid connected to N data lanes, wherein the first routing grid is adapted to drive first data to the N data lanes, wherein N is an integer that is greater than one;   a second routing grid connected to the N data lanes, wherein the second routing grid is adapted to drive second data to the N data lanes; and   wherein the ALU is configured to perform a filtering operation that is one of: two-dimensional filtering, median filtering, or sum of absolute difference filtering.   
     
     
         2 . The ALU of  claim 1 , wherein the ALU is configured to perform at least one median filter calculation iteration that includes the following operations:
 receiving N*2 pixels and generating, as the first data, N slices that differ from each other by one pixel; wherein different slices of the N slices are fed, by the first routing grid, to different data lanes of the N data lanes;   feeding, by the second routing grid, as the second data, different thresholds to different data lanes of the N data lanes; and   comparing, by each data lane, between pixels of a slice that is provided to the data lane and the threshold fed to the data lane to provide a count, wherein the count is indicative of a median of the slice.   
     
     
         3 . The ALU of  claim 2 , wherein the ALU is configured to perform multiple median filter calculation iterations and update at least some of the different thresholds from one iteration to another. 
     
     
         4 . The ALU of  claim 3 , wherein the median filtering iterations represent a filtering operation applied by a median filter, and wherein the ALU is configured to initialize the different thresholds to a value that is responsive to a size of the median filter. 
     
     
         5 . The ALU of  claim 2 , wherein each median filter calculation iteration results in a calculation of one bit of a median of a slice. 
     
     
         6 . The ALU of  claim 1 , wherein each data lane comprises a cyclic accumulator buffer that is coupled to a reduction unit of the data lane, wherein the ALU is configured to perform the two dimensional filtering operation by applying a two dimensional filter that comprises R rows of S coefficients each, and wherein R and S are integers that exceed one. 
     
     
         7 . The ALU of  claim 6 , wherein for each value q that ranges between 0 and (R*S)−1, the ALU is configured to perform an iteration comprising the following operations:
 receiving from a pre-processing unit of the ALU, N*2 pixels, starting from a (X+q)'th pixel and generating, as the first data, N slices that differ from each other by one pixel; and 
 feeding, by the second routing grid, as the second data, and to each of the N data lanes a coefficient vector that starts from the s'th coefficient of the two dimensional filter; wherein each data lane is configured to perform a multiplication between a slice provided to the data lane and the coefficient vector; 
 wherein each reduction unit is configured to calculate a sum by adding N products calculated by N functional units of a data lane that comprises the reduction unit; wherein during a first iteration of the iterations the cyclic accumulator buffer is reset; and wherein during subsequent iterations of the iterations the cyclic accumulator buffer is not reset. 
 
     
     
         8 . The ALU of  claim 1 , wherein the ALU is configured to perform the sum of absolute difference filtering. 
     
     
         9 . A filtering method comprising:
 performing, by an arithmetic logic unit (ALU), a filtering operation that is one of: medial filtering, two-dimensional filtering, or sum of absolute difference filtering, wherein performing the filtering comprises:
 driving first data to N data lanes, by a first routing grid of the ALU, the first routing grid is connected to the N data lanes, N being an integer that exceeds one; 
 driving second data to the N data lanes, by a second routing grid of the ALU, the second routing grid is connected to the N data lanes; and 
 performing, in each data lane of the N data lanes, by a plurality of N functional units of the N data lane, N instances of the filtering thereby outputting N results; and 
   performing an operation on the N results thereby outputting an output result.   
     
     
         10 . The filtering method of  claim 9 , wherein each data lane comprises a cyclic accumulator buffer that is coupled to the reduction unit of the data lane, wherein when the two dimensional filtering comprises applying a two dimensional filter that includes R rows of S coefficients each, and wherein R and S are integers that exceed one. 
     
     
         11 . The filtering method according to  claim 10 , wherein, for each value q that ranges between 0 and (R*S)−1, performing iterations comprising:
 receiving by a pre-processing unit of the ALU, N*2 pixels, starting from a (X+q)'th pixel and generating, as the first data, N slices that differ from each other by one pixel; wherein different slices of the N slices are fed, by the first routing grid, to different data lanes of the N data lanes; and 
 feeding, by the second routing grid, as the second data, and to each of the N data lanes a coefficient vector that starts from the s'th coefficient of the two dimensional filter; 
 performing, by each data lane, a multiplication between a slice provided to the data lane and the coefficient vector; 
 calculating, by each reduction unit, a sum by adding N products calculated by the N functional units of the data lane that comprises the reduction unit; 
 resetting the cyclic accumulator buffer during a first iteration of the iterations; and 
 not resetting the cyclic accumulator buffer during subsequent iterations of the iterations. 
 
     
     
         12 . The filtering method of  claim 9 , wherein the median filtering comprises performing at least one median filter calculation iteration comprising:
 receiving N*2 pixels and generating, as the first data, N slices that differ from each other by one pixel; wherein different slices of the N slices are fed, by the first routing grid, to different data lanes of the N data lanes;   feeding, by the second routing grid, as the second data, different thresholds to different data lanes of the N data lanes; and   comparing, by each data lane, between pixels of a slice that is provided to the data lane and the threshold fed to the data lane to provide a count; wherein the count is indicative of a median of the slice.   
     
     
         13 . The filtering method of  claim 12 , comprising performing multiple median filter calculation iterations and updating at least some of the different thresholds from one iteration to another. 
     
     
         14 . The filtering method of  claim 12 , wherein the median filtering iterations represent a filtering operation applied by a median filter, and wherein the method comprises initializing the different thresholds to a value that is responsive to a size of the median filter. 
     
     
         15 . The filtering method of  claim 11 , wherein each median filter calculation iteration results in a calculation of one bit of a median of a slice. 
     
     
         16 . The filtering method of  claim 9 , wherein the filtering comprises the sum of absolute difference filtering.