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

• US 6,948,056 B1
• Filed: 09/28/2000
• Issued: 09/20/2005
• Est. Priority Date: 09/28/2000
• Status: Active Grant

• Current Assignee: Analog Devices, Inc.
• Original Assignee: Analog Devices, Inc., Intel Corporation
• Inventors: Roth, Charles P., Fridman, Jose, Kolagotla, Ravi
• Primary Examiner(s): Chan, Eddie
• Assistant Examiner(s): DOLLINGER, TONIA LYNN MEONSKE
• Application Number:
  US09/675,066
• Time in Patent Office: 1,818 Days
• Field of Search: 712/300, 712/223, 712/21, 712/244, 708/207, 708/236, 708/524, 708/671, 711/220
• US Class Current: 712/300
• CPC Class Codes: G06F 7/22 Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
• CPC Class Codes: G06F 9/30021 Compare instructions, e.g. Greater-Than, Equal-To, MINMAX
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations

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.

Claims

1. A method comprising:

retrieving a pair of data elements from an array of elements in a single fetch operation, wherein the pair of data elements includes an even data element and an odd data element;

substantially comparing the even element of the pair with an even extreme value;

if the even element of the pair exceeds the even extreme value, storing the even element of the pair as the even extreme value and storing a parameter indicative of an address of the even element of the pair in a pointer register, wherein storing the parameter indicative of an address of the even element of the pair in a pointer register comprises maintaining a first pointer register to store an address for the extreme value of the even data elements;

concurrent with said comparing the even element of the pair with the even extreme value, comparing the odd element of the pair with an odd extreme value;

if the odd element of the pair exceeds the odd extreme value, storing the odd element of the pair as the odd extreme value, and further comprising maintaining a second pointer register to store an address for the extreme value of the odd data elements;

substantially fetching and comparing remaining pairs of data elements of the array until all of the data elements of the array have been processed; and

adjusting at least one of the pointer registers after processing all of the pairs of data elements to account for a number of stages in a pipeline.

2. The method of claim 1, further comprises setting the even extreme value as a function of the even element of the element pair and setting the odd extreme value as a function of the odd element of the element pair.

3. The method of claim 1, further comprises maintaining a first accumulator to store a minimum value for the even elements and a second accumulator to store a minimum value for the odd elements.

4. The method of claim 1, wherein the method is invoked by issuing N/M machine instructions to a programmable processor, wherein N equals a number of elements in the array, and M equals a number of data elements that the processor can concurrently compare.