Patent EP0112982A2 successfully refreshed from Google Patents.
EP0112982A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method and apparatus for determining minimum/maximum of multiple data words
Assignee: International Business Machines Corp
•
Filing: 1983-10-05
•
Granted: —
•
Expires: 2003-10-05
Abstract
Abstract A method and apparatus for very rapidly determining a minimum or maximum data word from a list of such words in which the expected time for completing the determination of the minimum or maximum value decreases as the number of words in the list is increased. Each data word is stored in a dedicated processing element (100). Each processing element first outputs onto an open-collector bus (400) a "0" in a position corresponding to the highest order "1" bit in the stored data word. The data signal thus assembled on the bus thus has a "0" at positions corresponding to the highest order "1" bit of each of the processing elements. In response to this data signal, a single controller (300) transmits back to the processing elements a control signal having a "0" in and only in the lowest order "0" bit of the data signal received on the bus. In the processing elements, ones of the processing elements which have a "1" bit in a higher position than the single "0" bit of the control signal are eliminated, while in processing elements still active, "1" bits are eliminated from the stored data word in the same position as the "0" of the control signal. The most significant "1" bit of the modified control word in each processing element is again determined, and the process repeated until only a single processing element, or multiple processing elements in which the same dataword is stored, is left transmitting back to the controller. In that processing element is stored the minimum or maximum data word.
Inventors
- 👤 Se June Hong
- 👤 Ravindra Nair
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-01 21:14
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/38; G06F7/48; G06F7/544; G06F7/02; G06F7/026; G06F7/22; G06F9/00; G06F9/06; G06F9/30; G06F9/30003; G06F9/30007; G06F9/30021
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
212 words
1 . A method for determining a minimum/maximum among a plurality of data words, characterized by a) storing each of said data words in a corresponding processing element (100), b) outputting from each of said processing element a first multi-bit signal having a predetermined bit state only in a position corresponding to the position of the highest order non-zero bit of the data word stored in the processing element, c) assembling a second multi-bit signal having said predetermined bit state in positions corresponding to each of said positions in each of said processing elements, d) eliminating from said second multi-bit signal said predetermined bit state in all positions except far a lowest order position in said predetermined bit state to provide a third multi-bit signal, e) deactivating ones of said processing elements having a data word having a non-zero bit in a higher position than said lowest order position in said third multi-bit signal, f) in each processing element not deactivated, eliminating any non-zero bit from said data word in the same position as said lowest order position in said third multi- bit signal, and g) repeating said steps (b) to (f) until only a single processing element or plural processing elements in which are stored the same data word remain active.
Claim 2
Dependent Claim
212 words
1 . A method for determining a minimum/maximum among a plurality of data words, characterized by a) storing each of said data words in a corresponding processing element (100), b) outputting from each of said processing element a first multi-bit signal having a predetermined bit state only in a position corresponding to the position of the highest order non-zero bit of the data word stored in the processing element, c) assembling a second multi-bit signal having said predetermined bit state in positions corresponding to each of said positions in each of said processing elements, d) eliminating from said second multi-bit signal said predetermined bit state in all positions except far a lowest order position in said predetermined bit state to provide a third multi-bit signal, e) deactivating ones of said processing elements having a data word having a non-zero bit in a higher position than said lowest order position in said third multi-bit signal, f) in each processing element not deactivated, eliminating any non-zero bit from said data word in the same position as said lowest order position in said third multi- bit signal, and g) repeating said steps (b) to (f) until only a single processing element or plural processing elements in which are stored the same data word remain active.
Claim 3
Dependent Claim
71 words
2 . The method of claim 1, wherein said step (a) of storing each of said data words comprises storing each of said data words in an uncomplemented form, whereby said method is a method for determining a minimum, or wherein said step (a) of storing each of said data words comprises storing each of said data words in complemented form, whereby said method is a method for determining a maximum.
Claim 4
Dependent Claim
64 words
3 . The method of claim 1, wherein, in said step (b) of outputting from each of said processing element a first multi-bit signal, said predetermined bit state is a logical " 0 ", and wherein said step (c) of assembling said second multi-bit signal comprises determing a bit-by-bit low-truth OR function of each said first multi-bit signals from each of said processing elements.
Claim 5
Dependent Claim
33 words
The method of claim 3, wherein said step (c) of assembling said second multi-bit signal comprises applying each said first multi-bit signals from each of said processing elements to an open-collector bus (400).
Claim 6
Dependent Claim
39 words
5 . The method of claim 1, further comprising the step of: h) assembling a value having a "1" in positions corresponding to said lowest order position in said third Multi-bit signal for each repetition of said step (d).
Claim 7
Dependent Claim
61 words
6 . The method of claim 5, further comprising the steps of: i) in each of said processing elements, determining whether the result of said step (f) is an all-zeros signal, and j) if in said step (i) it is determined that said result of said step (f) is an all-zeros signal, producing an indication that a minimum/maximum has been determined.
Claim 8
Dependent Claim
55 words
The method of claim 1, wherein said step (e) of deactivaing ones of said processing elements comprises the steps of: in each said processing element, comparing'said first multi-bit signal with said third multi-bit signal, and inhibiting the processing element from outputting its first multi-bit signal unless said first and third multi-bit signals are the same.
Claim 9
Dependent Claim
90 words
The method of claim 1, wherein said predetermined bit state is a "1" state, said first multi-bit signal is outputted onto an open-collector bus (410) through first a signal complementing bus transiver (110) in each processing element (100), said second multi-bit signal is generated by transferring the signals on the open-collector bus through a second signal complementing bus transiver (310) in a controller (300) into a storing register (320), and wherein said third multi-bit signal is generated from the second multi-bit signal in a trailing decoder (330) in the controller.
Claim 10
Dependent Claim
184 words
9 . An apparatus for determining a minimum/maximum among a plurality of data words, characterized by a) a plurality of processing elements (100), each of said processing elements comprising: means (230) for storing a respective one of said data words, means (140) for producing a first multibit signal having a "1" bit in a position corresponding to the position of a highest "1" bit in the data word stored in the processing element, means (161-168, 250, 506) for eliminating from said data word a "1" bit in the same position as a "1" bit in a control signal, and means (130, 146, 150) for comparing said control signal with said multi-bit signal and deactivating the processing element unless said control signal and said multi-bit signal are the same, b) means for providing a second multi-bit signal as a bit-by-bit logical OR of said first multi-bit signals from ones of said processing elements which are not deactivated, and c) controller means (300) comprising means (330) for producing said control signal by eliminating . .all but a lowest order "1" bit from said second multi-bit signal.
Claim 11
Dependent Claim
184 words
9 . An apparatus for determining a minimum/maximum among a plurality of data words, characterized by a) a plurality of processing elements (100), each of said processing elements comprising: means (230) for storing a respective one of said data words, means (140) for producing a first multibit signal having a "1" bit in a position corresponding to the position of a highest "1" bit in the data word stored in the processing element, means (161-168, 250, 506) for eliminating from said data word a "1" bit in the same position as a "1" bit in a control signal, and means (130, 146, 150) for comparing said control signal with said multi-bit signal and deactivating the processing element unless said control signal and said multi-bit signal are the same, b) means for providing a second multi-bit signal as a bit-by-bit logical OR of said first multi-bit signals from ones of said processing elements which are not deactivated, and c) controller means (300) comprising means (330) for producing said control signal by eliminating . .all but a lowest order "1" bit from said second multi-bit signal.
Claim 12
Dependent Claim
64 words
1 0 . The apparatus of claim 9, wherein said means for providing said second multi-bit signal comprises: in each of said processing elements, means (110) for complementing said first multi-bit signal, an open-collector bus (400) receiving the outputs of said complementing means from each of said processing elements, and in said controller means, means (310) for complementing the signal on said open-collector bus.
Claim 13
Dependent Claim
25 words
The apparatus of claim 10, wherein said controller means further comprises means for transmitting said control signal to said processing elements through said open-collector bus.
Claim 14
Dependent Claim
39 words
The apparatus of claim 9, wherein said controller means further comprises means (370) for assembling and storing a value having "1" bits in positions corresponding to "1" bits of said control signal for each state of said control signal.
Claim 15
Dependent Claim
41 words
The apparatus of claim 9, wherein said controller means further comprises means (380, 500) for activating, in sequence, said means for producing said multi-bit signal, said means for eliminating, said means for comparing, and said means for producing said control signal.
Claim 16
Dependent Claim
22 words
The apparatus of claim 9, wherein said open-collector bus includes a plurality of data lines (410) 'and a completion signal line (600).
Claim 17
Independent Claim
274 words
The apparatus of claims 9, 10 and 14, wherein each of said processing elements comprises, a first bus transceiver (110) having a bus port coupled to said open-collector bus, a first register (120) for storing data from a data output port of said bus transceiver, a second register (230) for storing a respective one of said data words, an S-R latch register (250), first gating means (261-268) for loading a value stored in said second register into said S-R latch register through S inputs of said S-R latch register at the beginning of a minimum/maximum determination procedure, second gating means (191-198) for inputting to said S-R latch register through R inputs thereof an output value from said first register, leading one detector means (140) having an input port coupled to an output port of said S-R latch register and an output port coupled to a data input port of said first bus transceiver, comparator means (130) for producing an output signal in an active state when values present on first and second input ports thereof are unequals, said first input port of said comparing means being coupled to outputs of said first register and said second input port of said comparing means being coupled to output port of said leading one detector, a latch (150) for storing the output of said comparing means, third gating means (129) for controlling a trans- mit/receive state of said first but transceiver in according with an output of said latch, and open-collector logical OR means (260) having inputs coupled to said output port of said leading one detector and an output (270) coupled to said completion signal line.
Claim 18
Independent Claim
122 words
The apparatus of claims 9 and 15 wherein said controller means comprises, a second bus transceiver (310) having a bus port coupled to said open-collector bus (410), a fourth register (320) for storing a data value from a data output port of said second bus transceiver, trailing one detector means (330) having input port coupled to an output-port of said fourth register, and output port of said trailing one detector being coupled to a data input port of said second bus transceiver, and a control unit (380) for generating control signals (501-506) for sequentially activating said first (110) and second (310) bus transceivers, said first through fourth registers (120, 230, 250, 320), said first through third gating means, and said latch (150).
Claim 19
Dependent Claim
44 words
17 . The apparatus of claim 16, wherein said control unit (380) comprises: a continuously cycling counter (840) for generating said control signals, and means (830) for inhibiting said counter in response to an active state being present on said completion signal line (600).
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.