Associative memory

A computer system including a central processing unit (CPU) and an addressable main memory storing data pages, at least one data page storing a page table, said CPU comprising:

• A) a processor coupled to said main memory;
• B) an associative memory storing a plurality of entries in multiple levels of association, each entry in said associative memory being stored in accordance with a low order virtual address component issued by said processor, each entry in said associative memory including fields respectively holding:
• 1) a high order virtual address component;
• 2) a real page address;
• and
• 3) a multi-digit validity count;
• C) a multi-digit counter storing a current validity count;
• D) a comparator for each level of association in said associative memory, each comparator coupled to receive:
• 1) a high order virtual address component of a requested data page in said main memory from said processor when access to the requested page is desired during the ongoing activity of the CPU;
• said processor also sending a low order virtual address component of the requested data page to said associative memory to specify an entry therein at each level of association;
• 2) the high order virtual address component read from the specified associative memory entry at the comparator's level of association;
• 3) the multi-digit validity count read from the specified associative memory entry at the comparator's level of association;
• and
• 4) the multi-digit current validity count in the counter;
• E) a switch for each level of association in said associative memory, each said switch coupled to receive the real page address read from the specified associative memory entry at the switch's level of association and, when enabled, issue the real page address;
• and
• F) each said comparator issuing a signal to enable said switch at the same level of association when:
• 1) there is a match between the high order virtual address components received, respectively, from said processor and said associative memory;
• and
• 2) there is a match between the multi-digit validity counts received, respectively, from said counter and said associative memory.

A computer system including a central processing unit (CPU) and an addressable main memory storing data pages, at least one data page storing a page table, said CPU comprising:

• A) a processor coupled to said main memory;
• B) an associative memory storing a plurality of entries, each entry in said associative memory being stored in accordance with a low order virtual address component issued by said processor, each entry in said associative memory including fields respectively holding:
• 1) a high order virtual address component;
• 2) a real page address;
• and
• 3) a multi-digit validity count;
• C) a multi-digit counter storing a current validity count;
• D) a comparator coupled to receive:
• 1) a high order virtual address component of a requested data page in said main memory from said processor when access to the requested page is desired during the ongoing activity of the CPU;
• said processor also sending a low order virtual address component of the requested data page to said associative memory to specify an entry therein;
• 2) the virtual high order address component read from the specified associative memory entry;
• 3) the multi-digit validity count read from the specified associative memory entry;
• and
• 4) the multi-digit current validity count in the counter;
• E) a switch coupled to receive the real page address read from the specified associative memory entry and, when enabled, issue the real page address;
• F) concatenation means for appending an offset value from said processor to said issued real page address to obtain a main memory block address;
• G) said comparator issuing a hit signal to enable said switch when:
• 1) there is a match between the high order virtual address components received, respectively, from said processor and said associative memory;
• and
• 2) there is a match between the multi-digit validity counts received, respectively, from said counter and said associative memory;
• H) said comparator issuing a miss signal to said processor when at least one of the comparisons between:
• 1) the high order virtual address components received, respectively, from said processor and said associative memory;
• and
• 2) the multi-digit validity counts received, respectively, from said counter and said associative memory;
• results in a no-match condition;
• I) said processor responding to a miss signal received from said comparator by invoking an access to said page table stored in said main memory to obtain the real address of the requested data page identified by the high order virtual address component sent to said comparator by said processor and the low order virtual address component sent to said associative memory by said processor, thereby obtaining access to said requested data page;
• J) means for, in the event of a miss and resulting access to said page table, updating the entry specified by the virtual low order address of the requested data page by placing:
• 1) the high order virtual address component for the requested data page into the high order virtual address component field;
• 2) the real page address for the requested data page into the real page address field;
• and
• 3) the current count in said multi-digit counter into the multi-digit validity count field;
• and
• K) means for selectively incrementing said counter to simultaneously invalidate all entries in said associative memory.

A computer system including a central processing unit (CPU) and an addressable main memory storing data pages, at least one data page storing a page table, said CPU comprising:

• A) a processor coupled to said main memory;
• B) an associative memory storing a plurality of entries in multiple levels of association, each entry in said associative memory being stored in accordance with a low order virtual address component issued by said processor, each entry in said associative memory including fields respectively holding:
• 1) a high order virtual address component;
• 2) a real page address;
• and
• 3) a multi-digit validity count;
• C) a multi-digit counter storing a current validity count;
• D) a comparator for each level of association in said associative memory, each said comparator coupled to receive:
• 1) a high order virtual address component of a requested data page in said main memory from said processor when access to the requested page is desired during the ongoing activity of the CPU;
• said processor also sending a low order virtual address component of the requested data page to said associative memory to specify an entry therein at each level of association;
• 2) the virtual high order address component read from the specified associative memory entry at the comparator's level of association;
• 3) the multi-digit validity count read from the specified associative memory entry at the comparator's level of association;
• and
• 4) the multi-digit current validity count in the counter;
• E) a switch for each level of association in said associative memory, each said switch coupled to receive the real page address read from the specified associative memory entry at the switch's level of association and, when enabled, issue the real page address;
• F) each said comparator issuing a hit signal to enable said switch at the same level of association when:
• 1) there is a match between the high order virtual address components received, respectively, from said processor and said associative memory;
• and
• 2) there is a match between the multi-digit validity counts received, respectively, from said counter and said associative memory.
• G) concatenation means for appending an offset value from said processor to said issued real page address to obtain a main memory block address;
• H) each said comparator issuing a miss signal to said processor when at least one of the comparisons between:
• 1) the high order virtual address components received, respectively, from said processor and said associative memory;
• and
• 2) the multi-digit validity counts received, respectively, from said counter and said associative memory;
• results in a no-match condition;
• I) said processor responding to miss signals issued by all said comparators by invoking an access to said page table stored in said main memory to obtain the real page address of the requested data page identified by the high order virtual address component sent to said comparators by said processor and the low order virtual address component sent to said associative memory by said processor, thereby obtaining access to said requested data page;
• J) means for, in the event of a miss signal issued by all said comparators and resulting access to said page table, updating the entry specified by the virtual low order address of the requested data page by placing:
• 1) the high order virtual address component for the requested data page, as obtained from the page table, into the high order virtual address component field of the least-recently-used entry at the level of association defined by the virtual low order address of the requested data page;
• 2) the real page address for the requested data page, as obtained from the page table, into the real page address field of said least-recently-used entry defined by the virtual low order address of the requested data page;
• and
• 3) the current count in said multi-digit counter into the multi-digit validity count field of said least-recently-used entry defined by the virtual low order address of the requested data page;
• and
• K) means for selectively incrementing said counter to simultaneously invalidate all entries in said associative memory.