Determining an extremum value and its index in an array using a dual-accumulation processor

• US 5,991,785 A
• Filed: 11/13/1997
• Issued: 11/23/1999
• Est. Priority Date: 11/13/1997
• Status: Expired due to Term

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Simanapalli, Sivanand, Alidina, Mazhar M.
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US08/969,252
• Time in Patent Office: 740 Days
• Field of Search: 364/715.06, 364/736.02, 708/207, 708/524
• US Class Current: 708/207
• CPC Class Codes: G06F 7/544 for evaluating functions by calculation G06F7/4824 takes precedence

Abstract

A data processor determines an overall extremum value of an input set of array data, with the input set of array data partitionable into a first set of array data and a second set of array data. The data processor includes a pair of compare-select circuits implemented in an adder as well as in an arithmetic-logic unit (ALU), respectively, which operate in parallel for respectively processing the first set and the second set, and for respectively determining first and second extremum values of the first set and the second set, respectively. A first compare-select circuit of the pair of compare-select circuits determines the overall extremum value of the input set of array data from the first and second extremum values. The first compare-select circuit also determines the location of the overall extremum value in the input set of array data. The computational complexity in determining extrema is reduced by implementing compare-select features in an adder in addition to an ALU to operate in parallel to reduce the number of processing cycles.

Claims

1. In a data processor, apparatus for determining an overall extremum value of a set of array data, the apparatus comprising:

first and second compare-select circuits operating in parallel, the first compare-select circuit for processing a first data set to determine a first extremum value and the second compare-select circuit for processing a second data set to determine a second extremum value, the first and second data sets together constituting the set of array data;

the first or second compare-select circuits determining the overall extremum value between the first and second extremum values and storing the location of the overall extremum value in the set of array data; and

a first register derived from a counter storing the location of the extremum value for the first data set and a second register derived from the counter storing the location of the extremum value for the second data set, one of the first or second registers, depending on whether the extremum value is in the first or second data set, being manipulated by one or more operations using constant values in order to determine the overall extremum index.

2. The apparatus of claim 1, wherein the pair of compare-select circuits determines first and second minimum values of the first and second sets, respectively, as the first and second extremum values, respectively.

3. The apparatus of claim 1, wherein the pair of compare-select circuits determines first and second maximum values of the first and second sets, respectively, as the first and second extremum values, respectively.

4. The apparatus of claim 1, wherein one of the compare-select circuits is incorporated in an adder and the other compare-select circuit is incorporated in an arithmetic-logic unit.

5. The apparatus of claim 1, wherein each of the pair of compare-select circuits is responsive to a mode signal to determine whether the extremum values are maxima or minima.

6. The apparatus of claim 1, further comprising:

storage means responsive to the compare-select circuits to store the location of an extremum value in the array data.

7. The apparatus of claim 6, wherein the compare-select circuits further comprise:

flag generating means, responsive to the compare-select circuits determining the first and second extremum values in one clock cycle, to generate a flag which latches the storage of the location of the extremum value.

8. The apparatus of claim 1, wherein if the first data set contains the overall extremum value, the first register is manipulated by left shift one and subtract one and if the second data set contains the overall extremum value, the second register is manipulated by left shift by one.

9. A plural multiply-accumulate (plural-MAC) processor for determining an overall extremum value of an input set of array data, comprising:

an adder having a first compare-select circuit; and

an arithmetic-logic unit (ALU) having a second compare-select circuit;

the first compare-select circuit processing a first set of data to determine a first extremum value and the second compare-select circuit processing a second set of data to determine a second extremum value, the first and second compare-select circuits processing concurrently, and the first and second sets of data together constituting the set of array data;

the first or second compare-select circuits determining the overall extremum value of the input set of array data as the extremum value between the first and second extremum values; and

a first register derived from a counter storing the location of the extremum value for the first data set and a second register derived from the counter storing the location of the extremum value for the second data set, one of the first or second registers, depending on whether the extremum value is in the first or second data set, being manipulated by one or more operations using constant values in order to determine the overall extremum index.

10. The plural-MAC processor of claim 9, wherein the extremum values determined by the compare-select circuits are minimum values.

11. The plural-MAC processor of claim 9, wherein the extremum values determined by the compare-select circuits are maximum values.

12. The plural-MAC processor of claim 9, wherein each of the pair of compare-select circuits is responsive to a mode signal to determine whether the extremum values are maxima or minima.

13. The plural-MAC processor of claim 9, further comprising:

storage means responsive to the compare-select circuits to store a location of an extremum value in the array data.

14. The plural-MAC processor of claim 13, wherein the compare-select circuits further comprise:

flag generating means, responsive to the compare-select circuits determining the first and second extremum values in one clock cycle, to generate a flag which latches the storage of the location of the extremum value.

15. A method for determining an overall extremum value of an input set of array data in a data processor operating in consecutive processing cycles, the method comprising the steps of:

a. initializing first and second extremum values and selecting datum to form a pair of data to be processed from the array;

b. performing concurrent compare-select operations between one of the pair of data and the first extremum value and between the other of the pair of data and the second extremum value to produce new first and second extremum values equal to the resulting extremes; and

c. in the same processing cycle as step b, selecting an unprocessed pair of data from the array and returning to step b, unless no unprocessed data remain;

c1. in the same processing cycle each time step b is performed, storing the location of a newly selected extremum value of the array data;

d. determining the overall extremum value of the input set of array data as the extremum between the first and second extremum values; and

e. determining the overall extremum index by manipulating a register derived from a counter corresponding to the location of the overall extremum value depending on whether the overall extremum value is in the first or second set, said manipulating step being left shift by one and subtract one if the overall extremum value is in the first set and left shift by one if the overall extremum value is in the second set.

16. The method of claim 15, wherein the step c1 further comprises:

in the same processing cycle each time step b is performed, upon selecting a new value for the first or second extremum values, generating a flag which causes storage in a predefined memory area of the location of the corresponding extremum value in the array data.