Method for finding local extrema of a set of values for a parallel processing element
AssigneeMicron Technology, Inc.
InventorMark Beaumont
Life of this patent
Estimating the term…
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.
Claims19
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.
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.
Dependencies are inferred from the claim text.