Patent EP0041808A1 successfully refreshed from Google Patents.
US5754885A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for selecting entries from an array
Assignee: International Business Machines Corp
•
Filing: 1996-04-04
•
Granted: 1998-05-19
•
Expires: 2016-04-04
Abstract
Abstract Control circuitry is used to select M entries from an N-entry storage array by viewing the array from both ends. Beginning at both ends of the array, particular bit values or entry content is looked for by the control logic. Once found at both ends, these entries are then used to produce control signals to be sent to a pair of muxes to remove these entries. Then a subset of the original array consisting of the remaining entries of the array is then iterated upon by a similar set of control circuitry for finding and removing the next M entries from the storage array.
Inventors
- 👤 Hoichi Cheong
- 👤 Tom Tien-Cheng Chiu
- 👤 Hung Qui Le
- 👤 Donald George Mikan, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 18:25
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/74
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
150 words
An apparatus for selecting M entries from an N-entry array, wherein M and N are positive integers, said apparatus comprising: circuitry for monitoring one or more bits of each entry of said N-entry array; circuitry, coupled to said monitoring circuitry, for selecting M entries from said N-entry array having a predetermined pattern of said one or more bits; and circuitry, coupled to said selecting circuitry, for outputting said M entries selected from said N-entry array having said predetermined pattern of said one or more bits, wherein said selecting circuitry further comprises: circuitry for selecting a first one of said M entries having said predetermined pattern of said one or more bits occurring from a first end of said N-entry array; and circuitry for selecting a first one of said M entries having said predetermined pattern of said one or more bits occurring from a second end of said N-entry array.
Claim 2
Independent Claim
150 words
An apparatus for selecting M entries from an N-entry array, wherein M and N are positive integers, said apparatus comprising: circuitry for monitoring one or more bits of each entry of said N-entry array; circuitry, coupled to said monitoring circuitry, for selecting M entries from said N-entry array having a predetermined pattern of said one or more bits; and circuitry, coupled to said selecting circuitry, for outputting said M entries selected from said N-entry array having said predetermined pattern of said one or more bits, wherein said selecting circuitry further comprises: circuitry for selecting a first one of said M entries having said predetermined pattern of said one or more bits occurring from a first end of said N-entry array; and circuitry for selecting a first one of said M entries having said predetermined pattern of said one or more bits occurring from a second end of said N-entry array.
Claim 3
Dependent Claim
36 words
The apparatus as recited in claim 1, wherein M≧2, and wherein said selecting circuitry selects said M entries having said predetermined pattern of said one or more bits beginning at one end of said N-entry array.
Claim 4
Dependent Claim
25 words
The apparatus as recited in claim 1, wherein said first and second ends of said N-entry array are at opposite ends of said N-entry array.
Claim 5
Dependent Claim
173 words
The apparatus as recited in claim 3, wherein said outputting circuitry further comprises first and second multiplexors each coupled to said each entry of said N-entry array, and wherein said circuitry for selecting said first one of said M entries having said predetermined pattern of said one or more bits occurring from said first end of said N-entry array produces a first control signal causing said first multiplexor to output said first one of said M entries having said predetermined pattern of said one or more bits occurring from said first end of said N-entry array from said N-entry array, and wherein said circuitry for selecting said first one of said M entries having said predetermined pattern of said one or more bits occurring from said second end of said N-entry array produces a second control signal causing said second multiplexor to output said first one of said M entries having said predetermined pattern of said one or more bits occurring from said second end of said N-entry array from said N-entry array.
Claim 6
Dependent Claim
59 words
The apparatus as recited in claim 4, wherein said circuitry for selecting M entries from said N-entry array having said predetermined pattern of said one or more bits further comprises: circuitry for selecting a second one of said M entries having said predetermined pattern of said one or more bits occurring from said first end of said N-entry array.
Claim 7
Dependent Claim
59 words
The apparatus as recited in claim 5, wherein said circuitry for selecting M entries from said N-entry array having said predetermined pattern of said one or more bits further comprises: circuitry for selecting a second one of said M entries having said predetermined pattern of said one or more bits occurring from said second end of said N-entry array.
Claim 8
Dependent Claim
65 words
The apparatus as recited in claim 6, wherein said second one of said M entries having said predetermined pattern of said one or more bits occurring from said first end of said N-entry array and said second one of said M entries having said predetermined pattern of said one or more bits occurring from said second end of said N-entry array are a same entry.
Claim 9
Dependent Claim
173 words
The apparatus as recited in claim 7, wherein said outputting circuitry further comprises third and fourth multiplexors each coupled to said each entry of said N-entry array, and wherein said circuitry for selecting said second one of said M entries having said predetermined pattern of said one or more bits occurring from said first end of said N-entry array produces a third control signal causing said third multiplexor to output said second one of said M entries having said predetermined pattern of said one or more bits occurring from said first end of said N-entry array from said N-entry array, and wherein said circuitry for selecting said second one of said M entries having said predetermined pattern of said one or more bits occurring from said second end of said N-entry array produces a fourth control signal causing said fourth multiplexor to output said second one of said M entries having said predetermined pattern of said one or more bits occurring from said second end of said N-entry array from said N-entry array.
Claim 10
Dependent Claim
65 words
The apparatus as recited in claim 1, wherein said first one of said M entries having said predetermined pattern of said one or more bits occurring from said first end of said N-entry array and said first one of said M entries having said predetermined pattern of said one or more bits occurring from said second end of said N-entry array are a same entry.
Claim 11
Independent Claim
189 words
An apparatus comprising: a storage array having N entries of K bits each; a valid vector wherein each entry of said valid vector is associated with one of said N entries of said storage array; M multiplexors each coupled to said storage array, wherein each of said M multiplexors has N inputs coupled to corresponding ones of said N entries of said storage array, and wherein said each of said M multiplexors has a K-bit output; and control circuitry coupled to said valid vector and to said each of said M multiplexors, wherein said control circuitry further comprises: circuitry for receiving said valid vector; circuitry for finding first entries of said valid vector from both ends of said valid vector having a preselected value; and circuitry for producing first and second control signals to be sent to first and second ones of said M multiplexors causing said first and second ones of said M multiplexors to select from said storage array and output from said K-bit outputs entries of said N entries of said storage array corresponding to said first entries of said valid vector having said preselected value.
Claim 12
Independent Claim
189 words
An apparatus comprising: a storage array having N entries of K bits each; a valid vector wherein each entry of said valid vector is associated with one of said N entries of said storage array; M multiplexors each coupled to said storage array, wherein each of said M multiplexors has N inputs coupled to corresponding ones of said N entries of said storage array, and wherein said each of said M multiplexors has a K-bit output; and control circuitry coupled to said valid vector and to said each of said M multiplexors, wherein said control circuitry further comprises: circuitry for receiving said valid vector; circuitry for finding first entries of said valid vector from both ends of said valid vector having a preselected value; and circuitry for producing first and second control signals to be sent to first and second ones of said M multiplexors causing said first and second ones of said M multiplexors to select from said storage array and output from said K-bit outputs entries of said N entries of said storage array corresponding to said first entries of said valid vector having said preselected value.
Claim 13
Dependent Claim
145 words
The apparatus as recited in claim 10, wherein said control circuitry further comprises: circuitry for producing a new valid vector from said valid vector by deleting said first entries of said valid vector having said preselected value and those entries of said valid vector occurring between said first entries and said both ends of said valid vector; circuitry for finding first entries of said new valid vector from both ends of said new valid vector having said preselected value; and circuitry for producing third and fourth control signals to be sent to third and fourth ones of said M multiplexors causing said third and fourth ones of said M multiplexors to select from said storage array and output from said K-bit outputs entries of said N entries of said storage array corresponding to said first entries of said new valid vector having said preselected value.
Claim 14
Dependent Claim
34 words
The apparatus as recited in claim 11, wherein said first entries of said new valid vector are a same entry of said new valid vector, and wherein said fourth control signal is therefore suppressed.
Claim 15
Dependent Claim
82 words
The apparatus as recited in claim 10, wherein said first control signal is an N-entry vector wherein said producing circuitry further comprises: a first AND gate receiving a first entry of said valid vector and an asserted bit and outputting a first entry of said first control signal; and a second AND gate receiving a second entry of said valid vector and an inverse of said first entry of said valid vector and outputting a second entry of said first control signal.
Claim 16
Dependent Claim
56 words
The apparatus as recited in claim 13, wherein said producing circuitry further comprises: a NOR gate receiving said first and second entries of said valid vector; and a third AND gate receiving a third entry of said valid vector and an output of said NOR gate and outputting a second entry of said first control signal.
Claim 17
Independent Claim
187 words
A method for selecting M entries from an N-entry array, wherein M and N are positive integers, said method comprising the steps of: a) monitoring one or more bits of each entry of said N-entry array; b) selecting a first one of said M entries having a predetermined pattern of said one or more bits occurring from a first end of said N-entry array; c) selecting a first one of said M entries having said predetermined pattern of said one or more bits occurring from a second end of said N-entry array; d) in response to step b), producing a first control signal causing a first multiplexor to output said first one of said M entries having said predetermined pattern of said one or more bits occurring from said first end of said N-entry array from said N-entry array; and e) in response to step c), producing a second control signal causing a second multiplexor to output said first one of said M entries having said predetermined pattern of said one or more bits occurring from said second end of said N-entry array from said N-entry array.
Claim 18
Independent Claim
187 words
A method for selecting M entries from an N-entry array, wherein M and N are positive integers, said method comprising the steps of: a) monitoring one or more bits of each entry of said N-entry array; b) selecting a first one of said M entries having a predetermined pattern of said one or more bits occurring from a first end of said N-entry array; c) selecting a first one of said M entries having said predetermined pattern of said one or more bits occurring from a second end of said N-entry array; d) in response to step b), producing a first control signal causing a first multiplexor to output said first one of said M entries having said predetermined pattern of said one or more bits occurring from said first end of said N-entry array from said N-entry array; and e) in response to step c), producing a second control signal causing a second multiplexor to output said first one of said M entries having said predetermined pattern of said one or more bits occurring from said second end of said N-entry array from said N-entry array.
Claim 19
Dependent Claim
69 words
The method as recited in claim 15, further comprising the steps of: f) selecting a second one of said M entries having said predetermined pattern of said one or more bits occurring from said first end of said N-entry array; and g) selecting a second one of said M entries having said predetermined pattern of said one or more bits occurring from said second end of said N-entry array.
Claim 20
Dependent Claim
107 words
The method as recited in claim 15, further comprising the steps of: h) in response to step f), producing a third control signal causing a third multiplexor to output said second one of said M entries having said predetermined pattern of said one or more bits occurring from said first end of said N-entry array from said N-entry array; and i) in response to step g), producing a fourth control signal causing a fourth multiplexor to output said second one of said M entries having said predetermined pattern of said one or more bits occurring from said second end of said N-entry array from said N-entry array.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-18 | 2001-11-17 | 2002-05-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-18 | 2005-11-17 | 2006-05-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-18 | 2009-11-17 | 2010-05-19 | $7700.00 | Window Closed / Lapsed |