Maintaining even and odd array pointers to extreme values by searching and comparing multiple elements concurrently where a pointer is adjusted after processing to account for a number of pipeline stages

Abstract

In one embodiment, a programmable processor searches an array of N data elements in response to N/M machine instructions, where the processor has a pipeline configured to process M data elements in parallel. In response to the machine instructions, a control unit directs the pipeline to retrieve M data elements from the array of elements in a single fetch cycle, concurrently compare the data elements to M current extreme values, and update the current extreme values, as well as M references to the current extreme values, based on the comparisons.

1 . An apparatus comprising: 
 a processor coupled to a memory device, wherein the processor includes a pipeline configured to process M data elements in parallel and a control unit configured to direct the pipeline to search an array of N data elements for an extreme value in response to N/M machine instructions, wherein in response to the machine instructions, the pipeline being configured to:    retrieve M data elements from the array of N data elements in a single fetch cycle;    concurrently compare the retrieved M data elements to corresponding M current extreme values, and update accumulators and pointers associated with the M current extreme values based on said comparing, the pointers including one or more pointer registers to store information indicative of addresses of extreme values in the array of N data elements; and    analyze results of the N/M machine instructions to identify at least a value of at least one extreme value in the array, wherein the at least one extreme value comprises an extreme value occurring more than once in the array, and wherein the position of the at least one extreme value in the array comprises a position of a predetermined one of a first occurrence and a last occurrence of the extreme value occurring more than once in the array.    
   
   
       2 . An apparatus as in  claim 1 , further comprising the memory device.  
   
   
       3 . An apparatus as in  claim 2 , wherein the memory device comprises static random access memory.  
   
   
       4 . An apparatus as in  claim 2 , wherein the memory device comprises FLASH memory.  
   
   
       5 . An apparatus as in  claim 1 , wherein the pipeline includes M registers configured to store the accumulators and pointers.  
   
   
       6 . An apparatus as in  claim 5 , wherein the registers include first and second pointer registers to store information indicative of addresses of first and second extreme values of the array.  
   
   
       7 . An apparatus as in  claim 5 , wherein the registers are general-purpose data registers.  
   
   
       8 . An apparatus comprising: 
 a processor coupled to a memory device, wherein the processor comprises: 
 a pipeline configured to process M data elements in parallel;  
 a control unit configured to direct the pipeline to search an array of N data elements by issuing N/M search instructions; and  
 M registers configured to store accumulators and pointers;  
 wherein in response to the search instructions, the pipeline being configured to:  
   store references to a location of a data element value for each of the M data elements;    determine an array value based on the stored references to the data element values;    update an accumulator to hold the array value; and    update a pointer to reference data quantity corresponding to the array value.    
   
   
       9 . An apparatus as in  claim 8 , further comprising the memory device.  
   
   
       10 . An apparatus as in  claim 9 , wherein the memory device comprises static random access memory.  
   
   
       11 . An apparatus as in  claim 9 , wherein the memory device comprises FLASH memory.  
   
   
       12 . An apparatus for searching an array of N data elements for an extreme value, the apparatus comprising: 
 means for issuing N/M machine instructions to a processor, wherein the processor is adapted to process M data elements in parallel;    means for concurrently comparing M data elements to corresponding M current extreme values,    means for retrieving another M elements in a single fetch cycle to be compared when executing a subsequent machine instruction;    means for updating accumulators and pointers associated with the M current extreme values based on said means for concurrently comparing, the pointers including one or more pointer registers to store information indicative of addresses of extreme values in the array of N data elements; and    means for analyzing results of the machine instructions to identify at least a value and a position of at least one extreme value in the array, wherein the at least one extreme value comprises an extreme value occurring more than once in the array, and wherein the position of the at least one extreme value in the array comprises a position of a predetermined one of a first occurrence and a last occurrence of the extreme value occurring more than once in the array.    
   
   
       13 . An apparatus as in  claim 12 , further comprising: 
 means for determining an address of a first extreme value based on a value in a pointer register and based on a correction factor to compensate for one or more errors.    
   
   
       14 . An apparatus as in  claim 12 , further comprising: 
 means for storing the M current extreme values in M accumulators; and    means for copying the M data elements to the accumulators based on said means for concurrently comparing.    
   
   
       15 . An apparatus as in  claim 12 , wherein said means for concurrently comparing the M data elements to M corresponding current extreme values comprises means for determining whether each of the data elements is less than the corresponding current extreme value.  
   
   
       16 . An apparatus as in  claim 12 , wherein said means for concurrently comparing the M data elements to M corresponding current extreme values comprises means for determining whether each of the data elements is greater than the corresponding current extreme value.  
   
   
       17 . An apparatus as in  claim 12 , further comprising: 
 means for setting up registers for said accumulators and pointers.    
   
   
       18 . An apparatus as in  claim 12 , wherein M=2 and N is greater than two.  
   
   
       19 . An apparatus as in  claim 17 , wherein said means for concurrently comparing the M data elements comprises means for processing a first data element with a first execution unit of a pipelined processor and means for processing a second data element with a second execution unit of the pipelined processor.  
   
   
       20 . An apparatus as in  claim 17 , wherein said means for concurrently comparing the M data elements comprises means for concurrently processing a first data element and a second data element within a single execution unit of a pipelined processor.