Method for finding local extrema of a set of values for a parallel processing element

• US 7,454,451 B2
• Filed: 10/20/2003
• Issued: 11/18/2008
• Est. Priority Date: 04/23/2003
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Beaumont, Mark
• Primary Examiner(s): Mai; Tan V
• Application Number:
  US10/689,335
• Publication Number:
  US 20040215678A1
• Time in Patent Office: 1,856 Days
• Field of Search: 708/207
• US Class Current: 708/207
• CPC Class Codes: G06F 7/544 for evaluating functions by calculation G06F7/4824 takes precedence
• CPC Class Codes: G06F 9/3001 Arithmetic instructions
• CPC Class Codes: G06F 9/30021 Compare instructions, e.g. Greater-Than, Equal-To, MINMAX

Abstract

A method for finding a local extrema for a single processing element having a set of values associated therewith includes separating the set of values into an odd set of values and an even set of values, determining a first extrema from the odd set of values, determining a second extrema from the even set of values, and determining the local extrema from the first extrema and the second extrema. The first extrema is found by comparing each odd-numbered value in the set to each other odd-numbered value in the set and the second extrema is found by comparing each even-numbered value in the set to each other even-numbered value in the set.

Claims

1. A method of optimizing the operation of a processing element comprising:

serially loading, on each clock cycle, values in odd positions within a set of values into a first register and values in even positions within said set into a second register;

determining a series of first extrema from said odd set when values in even positions are being loaded and saving a current value for said first extrema in a third register when a value in an odd position is being loaded;

determining a series of second extrema from said even set when values in odd positions are being loaded and saving a current value for said second extrema in a fourth register when a value in an even position is being loaded;

determining a local extrema from values in said third and fourth registers; and

storing said local extrema.

2. The method of claim 1 wherein said serial loading said set of values comprises:

loading a value from an odd position within said set into said first register;

loading a value from an even position within said set into said second register and transferring said value in said first register to said third register;

loading a value from a next odd position within said set into said first register and transferring said value in said second register to said fourth register; and

loading a value from a next even position within said set into said second register.

3. The method of claim 2 wherein said determining a first series of extrema from said odd set comprises comparing the value in said first register to the value in said third register.

4. The method of claim 3 wherein said determining further comprises:

selecting the greater value from said first register and said third register if a high first extrema is desired; and

selecting the lesser value from said first register and said third register if a low first extrema is desired.

5. The method of claim 2 wherein said determining a second series of extrema from said even set of values comprises comparing the value in said second register to the value in said fourth register.

6. The method of claim 5 wherein said determining further comprises:

selecting the greater value from said second register and said fourth register if a high second extrema is desired; and

selecting the lesser value from said second register and said fourth register if a low second extrema is desired.

7. The method of claim 2 further comprising:

storing a first in said series of second extrema in said fourth register;

loading another value from an even position within said set into said second register;

comparing the value in said second register to the value in said fourth register; and

repeating said storing, loading and comparing steps for remaining values within an even position within said set.

8. The method of claim 1 wherein said determining said local extrema further comprises:

selecting the greater value from said third and fourth registers if a local high extrema is desired; and

selecting the lesser value from said third and fourth registers if a local low extrema is desired.

9. The method of claim 2 further comprising:

storing a first in said series of first extrema in said third register;

loading another value from an odd position within said set into said first register;

comparing the value in said first register to the value in said third register; and

repeating said storing, loading and comparing steps for remaining values within an odd position within said set.

10. The method of claim 1 wherein said determining a series of first extrema from said odd set comprises comparing a least significant byte of a short value from said odd position within said set to a least significant byte of a short value from another odd position within said set and comparing a most significant byte of said short value from said odd position within said set to a most significant byte of said short value from said another odd position within said set.

11. The method of claim 1 wherein said determining a series of second extrema from said even set comprises comparing a least significant byte of a short value from said even position within said set to a least significant byte of a short value from another even position within said set and comparing a most significant byte of said short value from said even position within said set to a most significant byte of said short value from said another even position within said set.

12. A processing element, comprising:

an arithmetic logic unit;

condition logic responsive to said arithmetic logic unit;

a plurality of registers connected to a bus and responsive to said arithmetic logic unit;

a result pipeline responsive to said arithmetic logic unit;

an interface; and

register files connected between said interface and said result pipeline;

said processing element configured to;

serially load, on each clock cycle, values in odd positions within a set of values into a first register and values in even positions within said set into a second register;

said arithmetic logic unit determining a series of first extrema from said odd set when values in even positions are being loaded and saving a current value for said first extrema in a third register when a value in an odd position is being loaded;

said arithmetic logic unit determining a series of second extrema from said even set when values in odd positions are being loaded and saving a current value for said second extrema in a fourth register when a value in an even position is being loaded;

said arithmetic logic unit determining a local extrema from values in said third and fourth registers; and

output said local extrema through said result pipeline and said interface.

13. The processing element of claim 12 wherein said arithmetic logic unit is configured to determine a series of first extrema from said odd set by comparing the value in said first register to the value in said third register.

14. The processing element of claim 13 wherein said arithmetic logic unit is configured to:

select the greater value from said first register and said third register if a high first extrema is desired; and

select the lesser value from said first register and said third register if a low first extrema is desired.

15. The processing element of claim 12 wherein said arithmetic logic unit is configured to determining a second series of extrema from said even set of values by comparing the value in said second register to the value in said fourth register.

16. The processing element of claim 15 wherein said arithmetic logic unit is configured to:

select the greater value from said second register and said fourth register if a high second extrema is desired; and

select the lesser value from said second register and said fourth register if a low second extrema is desired.

17. The processing element of claim 12 wherein said arithmetic logic unit is configured to:

select the greater value from said third and fourth registers if a local high extrema is desired; and

select the lesser value from said third and fourth registers if a local low extrema is desired.

18. The processing element of claim 12 wherein the processing element is configured to:

serially load another value from an odd position within said set into said first register;

compare the value in said first register to the value in said third register; and

repeat said storing, loading and comparing steps for remaining values within odd positions within said set.

19. The processing element of claim 12 wherein said processing element is configured to:

serially load another value from an even position within said set into said second register;

comparing the value in said second register to the value in said fourth register; and

repeat said storing, loading and comparing steps for remaining values within even positions within said set.