Memory management unit and method of walking page table

Patent metadata

Field	Value
Publication number	US-12450164-B2
Application number	US-202318502058-A
Country	US
Kind code	B2
Filing date	Nov 5, 2023
Priority date	Dec 15, 2022
Publication date	Oct 21, 2025
Grant date	Oct 21, 2025

Abstract

A memory management unit includes a TLB configured to cache PTEs including a mapping between a virtual and a physical frame number, and to convert a virtual address into a physical address using the cached PTEs. A page table walk request queue is configured to queue page requests corresponding to a virtual page number when a TLB miss is occurred, and one or more PTWs are configured to acquire a PTE from the main memory, and to convert the virtual page numbers into physical frame numbers using the PTE. A PTW is configured to select associated page table walk requests having the same base address of corresponding virtual page numbers, to consecutively provide cache line requests for acquiring PTEs corresponding to the associated page table walk requests, to acquire the PTEs corresponding to the associated PTE requests, and to provide the acquired PTEs to the TLB.

First claim

What is claimed is:

1. A memory management unit, comprising:
a translation lookaside buffer (TLB) configured to cache page table entries (PTEs) including a mapping relationship between a virtual page number and a physical frame number, and further configured to convert a virtual address received from a processor into a physical address of a main memory using the cached PTEs;
a page table walk request queue configured to queue page table walk requests corresponding to a virtual page number included in the virtual address when a TLB miss has occurred; and
one or more page table walkers (PTWs) configured to acquire, based on virtual page numbers of the page table walk requests, a PTE from the main memory, and to convert the virtual page numbers into physical frame numbers using the PTE,
wherein a PTW, selected from among the one or more PTWs, is configured to select, from among the page table walk requests queued in the page table walk request queue, associated page table walk requests having a same base address of corresponding virtual page numbers, to consecutively provide, to the main memory, cache line requests for acquiring PTEs corresponding to the associated page table walk requests, to acquire, from cache lines acquired from the main memory, the PTEs corresponding to the associated page table walk requests, and to provide the acquired PTEs to the TLB.

2. The memory management unit of claim 1 , wherein the selected PTW is configured to:
determine, based on a size of a virtual page allocated to one virtual page number and a size of a PTE, a number of PTEs that may be stored in one virtual page as 2 M (where M is a positive integer); and
determine, in the virtual page number that is N bits (where N is a positive integer), a high-order (N−M) bit-address as the base address.

3. The memory management unit of claim 1 , wherein the selected PTW is configured to:
determine, based on a size of a row buffer of the main memory and a size of a PTE, the number of PTEs that may be stored in the row buffer as 2 M (where M is a positive integer); and
determine a high-order (N−M) bit-address as the base address in the virtual page number that is N bits (where N is a positive integer).

4. The memory management unit of claim 3 , wherein the selected PTW is configured to specify cache lines for acquiring the PTEs using a high-order K-bit address, among low-order M-bit addresses, in the virtual page number, when the number of cache lines included in the row buffer is 2 K (where K is a positive integer).

5. The memory management unit of claim 1 , wherein the selected PTW is configured to:
determine, based on a smaller size, among a size of a virtual page allocated to one virtual page number and a size of a row buffer of the main memory, and a size of a PTE, a number of PTEs that may be stored in one virtual page or one row buffer as 2 M (where M is a positive integer); and
determine a high-order (N−M) bit-address as the base address in the virtual page number that is N bits (where N is a positive integer).

6. The memory management unit of claim 1 , wherein the selected PTW is configured to:
determine a page directory entry (PDE) indicating a page table in which a target PTE corresponding to a virtual page number is stored, among a plurality of page tables, by searching a page directory using high-order bits of the virtual page number, and determine the target PTE by searching the page table using low-order bits excluding the high-order bits of the virtual page number; and
determine the high-order bits of the virtual page number as the base address.

7. The memory management unit of claim 1 , wherein the selected PTW is configured to select one page table walk request among a plurality of page table walk requests queued in the page table walk request queue, and to select page table walk requests having a base address that is the same as a base address of the one page table walk request by searching the page table walk request queue as the associated page table walk requests.

8. The memory management unit of claim 7 , further comprising:
a bloom filter configured to determine whether there is an address that is the same as the base address of the one page table walk request, among base addresses of the plurality of page table walk requests queued in the page table walk request queue, when the base addresses of the plurality of page table walk requests queued in the page table walk request queue are inserted and the base address of the one page table walk request is input.

9. The memory management unit of claim 7 , wherein the selected PTW is configured to exclude a page table walk request for which processing is started by another PTW, among the plurality of page table walk requests, from search targets of the page table walk request queue.

10. The memory management unit of claim 1 , wherein the selected PTW is configured to acquire a PTE by performing a multi-level search on a multi-level page table, and to determine a base address at a certain search level as an address indicating a page directory or page table searched at the search level.

11. The memory management unit of claim 10 , further comprising:
a plurality of bloom filters depending on search levels of the multi-level search,
wherein base addresses of the plurality of page table walk requests queued in the page table walk request queue, determined depending on the search level, are inserted into the bloom filters, respectively.

12. The memory management unit of claim 1 , wherein the one or more PTWs include:
a search logic configured to select one of the page table walk requests queued in the page table walk request queue, and to select associated page table walk requests having a base address that is the same as a base address of the selected page table walk request;
an associated request storage unit configured to store the associated page table walk requests selected by the search logic;
a cache line determination logic configured to determine, from among a plurality of cache lines included in a row buffer of the main memory, cache lines from which PTEs corresponding to the associated page table walk requests stored in the associated request storage unit are to be acquired;
a cache line request logic configured to consecutively provide, to the main memory, requests for the determined cache lines; and
a page table walk request processing logic configured to acquire the corresponding PTEs from the cache lines acquired from the main memory.

13. The memory management unit of claim 12 , wherein the memory management unit is an input-output memory management unit (IOMMU) electrically connected to an external processor, and is configured to selectively inactivate the search logic in the one or more PTWs depending on a processor type of the external processor.

14. The memory management unit of claim 13 , wherein the memory management unit is configured to selectively inactivate the search logic in the one or more PTWs depending on a parallel processing capability of the external processor.

15. A memory management unit, comprising:
a page table walker (PTW) configured to acquire, based on a virtual page number of a page table walk request, a page table entry (PTE) from a main memory; and
a page table walk request queue configured to queue a plurality of page table walk requests,
wherein the PTW is configured to determine, based on virtual page numbers of the page table walk requests queued in the page table walk request queue, associated page table walk requests, among the page table walk requests, in which a corresponding PTE is stored in a same memory ce

Assignees

• Samsung Electronics Co Ltd

Inventors

• Lee Jiwon
• Ro Won Woo
• Jeong Ipoom
• Kal Hongju
• Ko Gun
• Lee Hyunwuk

Classifications

• G06F12/1009 Primary

  using page tables, e.g. page table structures · CPC title

• G06F2212/50

  Control mechanisms for virtual memory, cache or TLB · CPC title

• G06F12/0882

  Page mode · CPC title

• G06F12/1027 Primary

  using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB] · CPC title

• G06F2212/684

  TLB miss handling · CPC title