Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-01-04
2004-06-08
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06748405
ABSTRACT:
FIELD OF INVENTION
The present invention relates to techniques to search a number having a determined value in a set of numbers and more particularly to a method and circuits for searching the number having the minimum/maximum value in this set of numbers. The described solution allows a very fast search, improving thereby the response time and also providing a constant time response whatever the quantity of numbers among said set in which the minimum/maximum search is conducted.
BACKGROUND OF THE INVENTION
In today's computing processes, the search of the minimum or maximum value among a set of numbers is extensively performed in various technical fields such as in optimization, artificial neural networks, signal processing, etc. The resulting value is used in subsequent computation tasks or to undertake any appropriate action, e.g. to select a circuit associated thereto. Because, it is highly desirable that the search must be performed as fast as possible, this objective can only be met by using high performance and expensive dedicated circuits. To date, several solutions exist to solve this acute problem, that are implemented in hardware, typically in a silicon chip, with more or less difficulty.
For instance, the most known method to determine the number having the minimum value among a set of numbers consists in comparing a number with another number of the set, selecting the number having the lowest value and then proceeding the same way with the selected number until all the numbers of the set have been processed, to identify the number(s) having the minimum value. obviously, this solution which requires a lot of processing steps that are sequentially performed is not optimized and presents major drawbacks. As known for those skilled in the art, the response time is prohibitive. This solution, and more generally all solutions that are derived therefrom, have response time that are not acceptable for most applications to date mainly because they are based on sequential processing algorithms. Moreover, the response time is degraded because it is function of the precision (the number q of bits used to code said numbers) and also depends upon the quantity of numbers in which the minimum/maximum value is searched.
Another approach consists in a simultaneous evaluation (i.e. in a parallel way) of all the bits of a same weight for the totality of the numbers in which the minimum/maximum value is searched. Such a parallel approach has been recently described in the technical literature in connection with an advanced family of neural silicon chips that are manufactured and commercialized by IBM France under the ZISC036 label (ZISC is a registered Trade Mark of IBM Corp). For more details, one may refer to U.S. Pat. No. 5,740,326 entitled “Circuit for Searching/Sorting Data in Neural Networks” assigned to the same assignee.
The principle of this approach will be briefly explained by reference to
FIG. 1
, assuming that p numbers (referred to hereinbelow as Number
1
to Number p) coded on q bits are processed. Now turning to
FIG. 1
, circuit
10
which is comprised of p blocks
11
referenced
11
-
1
to
11
-p (one per Number to be searched) processes a one bit slice, in this case the second bit (bit
2
or Bit
2
) of said Numbers. Note that all the q slices are of identical construction. In essence, a block
11
is quite similar to the circuit shown in
FIG. 28B
of the above cited U.S. patent. For instance, block
11
-
1
comprises a two-way OR gate
12
-
1
, a two-way AND gate
13
-
1
and a two-way OR gate
14
-
1
. The two latter gates form sub-block
15
-
1
that has the key role of selecting/deselecting the Number associated thereto, Number
1
in this case. Using the same terminology as in the above cited U.S. patent, signals Exout
1-2
and Bit
1-2
are applied to OR gate
12
-
1
. Signals Exout
1-2
and Bit
1-2
represent the state of Number
1
(i.e. selected or deselected) and the value of bit
2
for that Number
1
respectively. The same construction applies to all blocks
11
-
1
to
11
-p. The outputs of OR gates
12
-
1
to
12
-p are applied to a p-way AND gate
16
(AND gate
16
needs as many inputs as there are Numbers to be simultaneously processed) to produce a signal which is inverted in inverter
17
. AND gate
16
and inverter
17
form block
18
. The resulting signal is applied to a first input of all AND gates
13
-
1
to
13
-p whose other input receives the corresponding Bit signal i.e. Bit
1-2
to Bit
1-2
. The outputs of AND gates
13
-
1
to
13
-p and the corresponding Exout signals, i.e. Exout
1-2
to Exout
p-2
are applied to OR gates
14
-
1
to
14
-p respectively. The signals that are output by OR gates
14
-
1
to
14
-p are labeled Exout
1-3
to Exout
p-3
to still remain consistent with that terminology. Block
18
which is common for all the p blocks
11
-
1
to
11
-p allows to determine the minimum value for bit
2
of the p numbers, i.e. for one bit only. For example, in order to do this comparison to select the minimum value, each slice of one bit of all Numbers
1
to p is processed in sequence, one slice per step (e.g. per clock cycle) from the most significant bit (MSB) to the less significant bit (LSB). The response time of this method is then function of the quantity q of slices, i.e. the number of bits used to code Number
1
to Number p. Thus, this solution is parallel for what concerns the p Numbers and sequential for what concerns the q bits of coding. So that, whatever the value of p, the computational time depends only of the number of bits/slices q. As shown in
FIG. 1
, the Exout signal, representing the exclusion bit, is used to select/deselect the corresponding Number during the evaluation process. A Number is selected as long as the Exout signal is equal to a logic “0” and it is deselected as soon as it is equal to a logic “1”. As a matter of fact, if a Number, e.g. Number
1
has been deselected during the evaluation of bit i (i varies from 1 to q), Exout
1-(i+1)
is equal to “1”, all the next signals: Exout
1-(i+2)
, . . . , Exout
1-q
will be set to “1”. As a result, Number
1
will not be taken into account anymore whatever its value and the values of signals Bit
1-(i+1)
, . . . , Bit
1-q
are inhibited. Because, still in this example limited to the search of the minimum value, the first slice corresponding to bit
1
(i.e. the MSB) must not be deselected when the evaluation process starts, signals Exout
1-1
to Exout
p-1
are forced to the logic “0”.
In summary, this solution requires as many steps as the quantity q of bits used to code Numbers
1
to p limiting thereby the search process speed and is clearly silicon room consuming.
SUMMARY OF THE PRESENT INVENTION
It is therefore a primary object of the present invention to provide a method and circuits for performing the search of the minimum/maximum value among a set of numbers wherein the response time is significantly improved because several bit slices can be simultaneously processed in parallel in a same step.
It is another object of the present invention to provide a method and circuits for performing the search of the minimum/maximum value among a set of numbers wherein the response time is constant whatever the quantity of numbers among which the search is performed.
It is still another object of the present invention to provide a method and circuits for performing the search of the minimum/maximum value among a set of numbers which save a significant area when implemented in a silicon chip and simplify its connectivity.
The accomplishment of these and other related objects is achieved by the method and circuits according to the present invention.
The method for performing the search of the minimum/maximum value among a set of p numbers referred to as Numbers coded in a binary format on q bits comprises the steps of:
a) splitting each Number in K sub-values coded on n bits (q<=K×n) and defining a parameter k(k=1 to K) which assigns a rank to each sub-value of a Number, all the sub-values of a same rank formi
de Tremiolles Ghislain Imbert
Louis Didier
Tannhof Pascal
Anderson Jay H.
Ngo Chuong Dinh
LandOfFree
Method and circuits for performing the quick search of the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and circuits for performing the quick search of the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and circuits for performing the quick search of the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3364396