Patent US6026467A successfully refreshed from Google Patents.
US6026467A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Content-addressable memory implemented with a memory management unit
Assignee: Avaya Inc
•
Filing: 1997-10-01
•
Granted: 2000-02-15
•
Expires: 2017-10-01
Abstract
Abstract A content-addressable memory (CAM) is implemented by using otherwise-unused memory management unit (MMU 102) and cache memories (104, 105) of a program-controlled microprocessor (100). A program stored in an instruction cache (104) and executed by the microprocessor causes the microprocessor to respond to receipt of a word of data (200), which is illustratively the VPI/VCI of an ATM network connection, by applying the most-significant bits (MSBs 202) of the received word as a comparand to tags (203) of entries (206) of a fully-associative translation buffer (103) of the MMU to obtain an index (204) indicative of which translation buffer entry's corresponding tag matches the comparand. The program further causes the microprocessor to respond to obtaining of the index by concatenating the index with the least-significant bits (LSBs 201) of the received word to form a memory address of a data cache (105) which stores a plurality of records (210) and apply the address to the data cache to retrieve the addressed record, which is illustratively the path of the connection through the ATM network. Entries may be added to and deleted from the translation buffer during processing as needed.
Inventors
- 👤 Norman W. Petty
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 09:48
CPC Classifications
H; H04; H04L; H04L49/00; H04L49/30; H04L49/3081; H04L49/309; G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/10; G06F12/1027; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90339; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
200 words
A content-addressable memory (CAM) comprising: a first memory; a microprocessor connected to the first memory and having an internal memory management unit for translating virtual memory addresses into physical memory addresses that includes a translation buffer in the form of an associative second memory having a plurality of entries, each entry for indicating a corresponding portion of the physical memory and having a corresponding tag for indicating a corresponding portion of the virtual memory; and the microprocessor further having a program execution unit programmed, in an absence of use of the internal memory management unit for the translating of the virtual memory addresses into the physical memory addresses, to be responsive to receipt of a word of data that excludes a virtual memory address and comprises most-significant bits and least-significant bits by applying the most-significant bits as a comparand to the tags which indicate words of data that both correspond to the tags and exclude virtual memory addresses, to obtain an index indicative of which translation buffer entry's corresponding tag matches the comparand, and responsive to obtaining of the index by combining the index with the least-significant bits of the received word to form an address of the first memory.
Claim 2
Dependent Claim
200 words
A content-addressable memory (CAM) comprising: a first memory; a microprocessor connected to the first memory and having an internal memory management unit for translating virtual memory addresses into physical memory addresses that includes a translation buffer in the form of an associative second memory having a plurality of entries, each entry for indicating a corresponding portion of the physical memory and having a corresponding tag for indicating a corresponding portion of the virtual memory; and the microprocessor further having a program execution unit programmed, in an absence of use of the internal memory management unit for the translating of the virtual memory addresses into the physical memory addresses, to be responsive to receipt of a word of data that excludes a virtual memory address and comprises most-significant bits and least-significant bits by applying the most-significant bits as a comparand to the tags which indicate words of data that both correspond to the tags and exclude virtual memory addresses, to obtain an index indicative of which translation buffer entry's corresponding tag matches the comparand, and responsive to obtaining of the index by combining the index with the least-significant bits of the received word to form an address of the first memory.
Claim 3
Dependent Claim
39 words
The CAM of claim 1 wherein: the first memory comprises a plurality of addressable records; and the program execution unit forms the address for application to the first memory to retrieve a record that is addressed by the address.
Claim 4
Dependent Claim
48 words
The CAM of claim 1 wherein: the first memory is an internal memory of the microprocessor and stores a plurality of records; and the program execution unit applies the address to the internal memory to retrieve from the internal memory a record that is addressed by the address.
Claim 5
Dependent Claim
16 words
The CAM of claim 3 wherein: the internal memory is a data cache of the microprocessor.
Claim 6
Dependent Claim
40 words
The CAM of claim 1 wherein: the program execution unit comprises a processing unit for executing a program; and an internal memory of the microprocessor connected to the processing unit and storing the program for execution by the processing unit.
Claim 7
Dependent Claim
16 words
The CAM of claim 5 wherein: the internal memory is an instruction cache of the microprocessor.
Claim 8
Dependent Claim
33 words
The CAM of claim 2 wherein: the received word is an identifier of an asynchronous transfer mode (ATM) network connection; and the record defines a route of the connection through the ATM network.
Claim 9
Dependent Claim
320 words
The CAM of claim 1 wherein: the program execution unit is further programmed to respond to receipt of a second word of data comprising most-significant second bits and least-significant second bits by applying the most-significant second bits as a second comparand to the tags of the translation buffer entries to obtain a second index identifying which if any translation buffer entry's corresponding tag matches the second comparand, to respond to obtaining of a second index identifying an individual translation buffer entry as having a corresponding tag that matches the second comparand by checking a use field corresponding to the least-significant second bits of a use entry corresponding to the second index of a map of use of the first memory to determine if the record that corresponds to the checked use field is in use, to respond to a determination that the record that corresponds to the checked use field is in use by giving an indication thereof, to respond to a determination that the record that corresponds to the checked use field is not in use by causing the checked use field to indicate that the corresponding record is in use, to respond to obtaining of a second index identifying no translation buffer entry as having a corresponding tag that matches the second comparand by determining whether all translation buffer entries are in use, to respond to a determination that all translation buffer entries are in use by giving an indication thereof, to respond to a determination that all translation buffer entries are not in use by selecting an unused individual translation buffer entry, causing the use field corresponding to the least-significant second bits of a use entry corresponding to the individual translation buffer entry of the map of use of the first memory to indicate that the corresponding record is in use, and setting the tag of the individual translation buffer entry to match the most-significant second bits.
Claim 10
Dependent Claim
283 words
The CAM of claim 8 wherein: the program execution unit is further programmed to respond to receipt of a third word of data comprising most-significant third bits and least-significant third bits by applying the most-significant third bits as a third comparand to the tags of the translation buffer entries to obtain a third index identifying which if any translation buffer entry's corresponding tag matches the third comparand, to respond to obtaining of a third index identifying no translation buffer entry as having a corresponding tag that matches the third comparand by giving an indication thereof, to respond to obtaining of a third index identifying a second individual translation buffer entry as having a corresponding tag that matches the third comparand by checking a use field corresponding to the least-significant third bits of a second use entry corresponding to the third index of the map of use of the first memory to determine if the record that corresponds to the checked second use field is in use, to respond to a determination that the record that corresponds to the checked second use field is not in use by giving an indication thereof, to respond to a determination that the record that corresponds to the checked second use field is in use by causing the checked second use field to indicate that the corresponding record is not in use and determining whether all use fields of the second use entry indicate that the corresponding records are not in use, and to respond to a determination that all use fields of the second use entry indicate that the corresponding records are not in use by marking the second translation buffer entry as not being in use.
Claim 11
Independent Claim
222 words
A method of operating as a content-addressable memory (CAM) a first memory comprising a plurality of addressable records and a microprocessor connected to the first memory and having an internal memory management unit for translating virtual memory addresses into physical memory addresses that includes a translation buffer in the form of an associative second memory having a plurality of entries, each entry for indicating a corresponding portion of the physical memory and having a corresponding tag for indicating a corresponding portion of the virtual memory, comprising the steps of: responsive, in an absence of use of the internal memory management unit for the translating of the virtual memory addresses into the physical memory addresses, to receipt of a word of data that excludes a virtual memory address and comprises most-significant bits and least-significant bits, the microprocessor applying the most-significant bits as a comparand to the tags which indicate words of data that both correspond to the tags and exclude virtual memory addresses, to obtain an index indicative of which translation buffer entry's corresponding tag matches the comparand; responsive to obtaining of the index, the microprocessor combining the index with the least-significant bits of the received word to form an address of the first memory; and applying the address to the first memory to retrieve a record that is addressed by the address.
Claim 12
Independent Claim
222 words
A method of operating as a content-addressable memory (CAM) a first memory comprising a plurality of addressable records and a microprocessor connected to the first memory and having an internal memory management unit for translating virtual memory addresses into physical memory addresses that includes a translation buffer in the form of an associative second memory having a plurality of entries, each entry for indicating a corresponding portion of the physical memory and having a corresponding tag for indicating a corresponding portion of the virtual memory, comprising the steps of: responsive, in an absence of use of the internal memory management unit for the translating of the virtual memory addresses into the physical memory addresses, to receipt of a word of data that excludes a virtual memory address and comprises most-significant bits and least-significant bits, the microprocessor applying the most-significant bits as a comparand to the tags which indicate words of data that both correspond to the tags and exclude virtual memory addresses, to obtain an index indicative of which translation buffer entry's corresponding tag matches the comparand; responsive to obtaining of the index, the microprocessor combining the index with the least-significant bits of the received word to form an address of the first memory; and applying the address to the first memory to retrieve a record that is addressed by the address.
Claim 13
Dependent Claim
54 words
The method of claim 10 wherein: the first memory is an internal memory of the microprocessor and stores a plurality of records; and the step of applying comprises the step of the microprocessor applying the address to the internal memory to retrieve from the internal memory a record that is addressed by the address.
Claim 14
Dependent Claim
16 words
The method of claim 11 wherein: the internal memory is a data cache of the microprocessor.
Claim 15
Dependent Claim
24 words
The method of claim 10 wherein: the microprocessor performs the method steps by executing a program stored in an internal memory of the microprocessor.
Claim 16
Dependent Claim
16 words
The method of claim 13 wherein: the internal memory is an instruction cache of the microprocessor.
Claim 17
Dependent Claim
34 words
The method of claim 10 wherein: the received word is an identifier of an asynchronous transfer mode (ATM) network connection; and the addressed record defines a route of the connection through the ATM network.
Claim 18
Dependent Claim
309 words
The method of claim 10 further comprising the steps of: in response to receipt of a second word of data comprising most-significant second bits and least-significant second bits, applying the most-significant second bits as a second comparand to the tags of the translation buffer entries to obtain a second index identifying which if any translation buffer entry's corresponding tag matches the second comparand; in response to obtaining a second index identifying an individual translation buffer entry as having a corresponding tag that matches the second comparand, checking a use field corresponding to the least-significant second bits of a use entry corresponding to the second index of a map of use of the first memory to determine if the record that corresponds to the checked use field is in use; in response to a determination that the record that corresponds to the checked use field is in use, giving an indication thereof; in response to a determination that the record that corresponds to the checked use field is not in use, causing the checked use field to indicate that the corresponding record is in use; in response to obtaining a second index identifying no translation buffer entry as having a corresponding tag that matches the second comparand, determining whether all translation buffer entries are in use; in response to a determination that all translation buffer entries are in use, giving an indication thereof; and in response to a determination that all translation buffer entries are not in use, selecting an unused individual translation buffer entry, causing the use field corresponding to the least-significant second bits of a use entry corresponding to the individual translation buffer entry of the map of use of the first memory to indicate that the corresponding record is in use, and setting the tag of the individual translation buffer entry to match the most-significant second bits.
Claim 19
Dependent Claim
272 words
The method of claim 16 further comprising the steps of: in response to receipt of a third word of data comprising most-significant third bits and least-significant third bits, applying the most-significant third bits as a third comparand to the tags of the translation buffer entries to obtain a third index identifying which if any translation buffer entry's corresponding tag matches the third comparand; in response to obtaining a third index identifying no translation buffer entry as having a corresponding tag that matches the third comparand, giving an indication thereof; in response to obtaining a third index identifying a second individual translation buffer entry as having a corresponding tag that matches the third comparand, checking a use field corresponding to the least-significant third bits of a second use entry corresponding to the third index of the map of use of the first memory to determine if the record that corresponds to the checked second use field is in use; in response to a determination that the record that corresponds to the checked second use field is not in use, giving an indication thereof; in response to a determination that the record that corresponds to the checked second use field is in use, causing the checked second use field to indicate that the corresponding record is not in use, and determining whether all use fields of the second use entry indicate that the corresponding records are not in use; and in response to a determination that all use fields of the second use entry indicate that the corresponding records are not in use, marking the second translation buffer entry as not being in use.
Claim 20
Dependent Claim
440 words
A content-addressable memory (CAM) comprising: a first memory; a microprocessor connected to the first memory and having an internal memory management unit that includes a translation buffer in the form of an associative second memory having a plurality of entries and each entry having a corresponding tag; and the microprocessor further having a program execution unit programmed to be responsive to receipt of a word of data comprising most-significant bits and least-significant bits by applying the most-significant bits as a comparand to the tags to obtain an index indicative of which translation buffer entry's corresponding tag matches the comparand, and responsive to obtaining of the index by combining the index with the least-significant bits of the received word to form an address of the first memory, the program execution unit being further programmed to respond to receipt of a second word of data comprising most-significant second bits and least-significant second bits by applying the most-significant second bits as a second comparand to the tags of the translation buffer entries to obtain a second index identifying which if any translation buffer entry's corresponding tag matches the second comparand, to respond to obtaining of a second index identifying an individual translation buffer entry as having a corresponding tag that matches the second comparand by checking a use field corresponding to the least-significant second bits of a use entry corresponding to the second index of a map of use of the first memory to determine if the record that corresponds to the checked use field is in use, to respond to a determination that the record that corresponds to the checked use field is in use by giving an indication thereof, to respond to a determination that the record that corresponds to the checked use field is not in use by causing the checked use field to indicate that the corresponding record is in use, to respond to obtaining of a second index identifying no translation buffer entry as having a corresponding tag that matches the second comparand by determining whether all translation buffer entries are in use, to respond to a determination that all translation buffer entries are in use by giving an indication thereof, to respond to a determination that all translation buffer entries are not in use by selecting an unused individual translation buffer entry, causing the use field corresponding to the least-significant second bits of a use entry corresponding to the individual translation buffer entry of the map of use of the first memory to indicate that the corresponding record is in use, and setting the tag of the individual translation buffer entry to match the most-significant second bits.
Claim 21
Dependent Claim
440 words
A content-addressable memory (CAM) comprising: a first memory; a microprocessor connected to the first memory and having an internal memory management unit that includes a translation buffer in the form of an associative second memory having a plurality of entries and each entry having a corresponding tag; and the microprocessor further having a program execution unit programmed to be responsive to receipt of a word of data comprising most-significant bits and least-significant bits by applying the most-significant bits as a comparand to the tags to obtain an index indicative of which translation buffer entry's corresponding tag matches the comparand, and responsive to obtaining of the index by combining the index with the least-significant bits of the received word to form an address of the first memory, the program execution unit being further programmed to respond to receipt of a second word of data comprising most-significant second bits and least-significant second bits by applying the most-significant second bits as a second comparand to the tags of the translation buffer entries to obtain a second index identifying which if any translation buffer entry's corresponding tag matches the second comparand, to respond to obtaining of a second index identifying an individual translation buffer entry as having a corresponding tag that matches the second comparand by checking a use field corresponding to the least-significant second bits of a use entry corresponding to the second index of a map of use of the first memory to determine if the record that corresponds to the checked use field is in use, to respond to a determination that the record that corresponds to the checked use field is in use by giving an indication thereof, to respond to a determination that the record that corresponds to the checked use field is not in use by causing the checked use field to indicate that the corresponding record is in use, to respond to obtaining of a second index identifying no translation buffer entry as having a corresponding tag that matches the second comparand by determining whether all translation buffer entries are in use, to respond to a determination that all translation buffer entries are in use by giving an indication thereof, to respond to a determination that all translation buffer entries are not in use by selecting an unused individual translation buffer entry, causing the use field corresponding to the least-significant second bits of a use entry corresponding to the individual translation buffer entry of the map of use of the first memory to indicate that the corresponding record is in use, and setting the tag of the individual translation buffer entry to match the most-significant second bits.
Claim 22
Dependent Claim
283 words
The CAM of claim 18 wherein: the program execution unit is further programmed to respond to receipt of a third word of data comprising most-significant third bits and least-significant third bits by applying the most-significant third bits as a third comparand to the tags of the translation buffer entries to obtain a third index identifying which if any translation buffer entry's corresponding tag matches the third comparand, to respond to obtaining of a third index identifying no translation buffer entry as having a corresponding tag that matches the third comparand by giving an indication thereof, to respond to obtaining of a third index identifying a second individual translation buffer entry as having a corresponding tag that matches the third comparand by checking a use field corresponding to the least-significant third bits of a second use entry corresponding to the third index of the map of use of the first memory to determine if the record that corresponds to the checked second use field is in use, to respond to a determination that the record that corresponds to the checked second use field is not in use by giving an indication thereof, to respond to a determination that the record that corresponds to the checked second use field is in use by causing the checked second use field to indicate that the corresponding record is not in use and determining whether all use fields of the second use entry indicate that the corresponding records are not in use, and to respond to a determination that all use fields of the second use entry indicate that the corresponding records are not in use by marking the second translation buffer entry as not being in use.
Claim 23
Independent Claim
446 words
A method of operating a first memory comprising a plurality of addressable records and a microprocessor connected to the first memory and having an internal memory management unit that includes a translation buffer in the form of an associative second memory having a plurality of entries and each entry having a corresponding tag as a content-addressable memory (CAM), comprising the steps of: responsive to receipt of a word of data comprising most-significant bits and least-significant bits, the microprocessor applying the most-significant bits as a comparand to the tags to obtain an index indicative of which translation buffer entry's corresponding tag matches the comparand; responsive to obtaining of the index, the microprocessor combining the index with the least-significant bits of the received word to form an address of the first memory; applying the address to the first memory to retrieve a record that is addressed by the address; in response to receipt of a second word of data comprising most-significant second bits and least-significant second bits, applying the most-significant second bits as a second comparand to the tags of the translation buffer entries to obtain a second index identifying which if any translation buffer entry's corresponding tag matches the second comparand; in response to obtaining a second index identifying an individual translation buffer entry as having a corresponding tag that matches the second comparand, checking a use field corresponding to the least-significant second bits of a use entry corresponding to the second index of a map of use of the first memory to determine if the record that corresponds to the checked use field is in use; in response to a determination that the record that corresponds to the checked use field is in use, giving an indication thereof; in response to a determination that the record that corresponds to the checked use field is not in use, causing the checked use field to indicate that the corresponding record is in use; in response to obtaining a second index identifying no translation buffer entry as having a corresponding tag that matches the second comparand, determining whether all translation buffer entries are in use; in response to a determination that all translation buffer entries are in use, giving an indication thereof; and in response to a determination that all translation buffer entries are not in use, selecting an unused individual translation buffer entry, causing the use field corresponding to the least-significant second bits of a use entry corresponding to the individual translation buffer entry of the map of use of the first memory to indicate that the corresponding record is in use, and setting the tag of the individual translation buffer entry to match the most-significant second bits.
Claim 24
Independent Claim
446 words
A method of operating a first memory comprising a plurality of addressable records and a microprocessor connected to the first memory and having an internal memory management unit that includes a translation buffer in the form of an associative second memory having a plurality of entries and each entry having a corresponding tag as a content-addressable memory (CAM), comprising the steps of: responsive to receipt of a word of data comprising most-significant bits and least-significant bits, the microprocessor applying the most-significant bits as a comparand to the tags to obtain an index indicative of which translation buffer entry's corresponding tag matches the comparand; responsive to obtaining of the index, the microprocessor combining the index with the least-significant bits of the received word to form an address of the first memory; applying the address to the first memory to retrieve a record that is addressed by the address; in response to receipt of a second word of data comprising most-significant second bits and least-significant second bits, applying the most-significant second bits as a second comparand to the tags of the translation buffer entries to obtain a second index identifying which if any translation buffer entry's corresponding tag matches the second comparand; in response to obtaining a second index identifying an individual translation buffer entry as having a corresponding tag that matches the second comparand, checking a use field corresponding to the least-significant second bits of a use entry corresponding to the second index of a map of use of the first memory to determine if the record that corresponds to the checked use field is in use; in response to a determination that the record that corresponds to the checked use field is in use, giving an indication thereof; in response to a determination that the record that corresponds to the checked use field is not in use, causing the checked use field to indicate that the corresponding record is in use; in response to obtaining a second index identifying no translation buffer entry as having a corresponding tag that matches the second comparand, determining whether all translation buffer entries are in use; in response to a determination that all translation buffer entries are in use, giving an indication thereof; and in response to a determination that all translation buffer entries are not in use, selecting an unused individual translation buffer entry, causing the use field corresponding to the least-significant second bits of a use entry corresponding to the individual translation buffer entry of the map of use of the first memory to indicate that the corresponding record is in use, and setting the tag of the individual translation buffer entry to match the most-significant second bits.
Claim 25
Dependent Claim
272 words
The method of claim 20 further comprising the steps of: in response to receipt of a third word of data comprising most-significant third bits and least-significant third bits, applying the most-significant third bits as a third comparand to the tags of the translation buffer entries to obtain a third index identifying which if any translation buffer entry's corresponding tag matches the third comparand; in response to obtaining a third index identifying no translation buffer entry as having a corresponding tag that matches the third comparand, giving an indication thereof; in response to obtaining a third index identifying a second individual translation buffer entry as having a corresponding tag that matches the third comparand, checking a use field corresponding to the least-significant third bits of a second use entry corresponding to the third index of the map of use of the first memory to determine if the record that corresponds to the checked second use field is in use; in response to a determination that the record that corresponds to the checked second use field is not in use, giving an indication thereof; in response to a determination that the record that corresponds to the checked second use field is in use, causing the checked second use field to indicate that the corresponding record is not in use, and determining whether all use fields of the second use entry indicate that the corresponding records are not in use; and in response to a determination that all use fields of the second use entry indicate that the corresponding records are not in use, marking the second translation buffer entry as not being in use.
References Cited (Backward Citations)
US5414704A
Cited
US5712998A
Cited
US5805490A
Cited
US5835962A
Cited
US5893930A
Cited
US5749087A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-02-14 | 2003-08-16 | 2004-02-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-02-14 | 2007-08-16 | 2008-02-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-02-14 | 2011-08-16 | 2012-02-15 | $7700.00 | Window Closed / Lapsed |