Determining an extremum value and its index in an array using a dual-accumulation processor
First Claim
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.
6 Assignments
0 Petitions
Accused Products
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.
-
Citations
16 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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. - View Dependent Claims (10, 11, 12, 13, 14)
-
-
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. - View Dependent Claims (16)
-
Specification