Method, apparatus and system for managing virtual memory with virtual-physical mapping

• US 6,336,180 B1
• Filed: 02/18/1998
• Issued: 01/01/2002
• Est. Priority Date: 04/30/1997
• Status: Expired due to Term

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Amies, Christopher, Webb, Michael John, Long, Timothy Merrick
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): Monestime, Mackly
• Application Number:
  US09/025,755
• Time in Patent Office: 1,413 Days
• Field of Search: 712/34, 711/206, 711/207, 711/209
• US Class Current: 712/34
• CPC Class Codes: G06F 9/3879 for non-native instruction execution, e.g. executing a command; for Java instruction set
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/3897 with adaptable data path
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining
• CPC Class Codes: G06T 15/00 3D [Three Dimensional] image rendering

Abstract

The present invention relates to a method, apparatus and system for managing virtual memory, in which a co-processor (224) is adapted to use virtual memory with a host processor (202). A host memory (203) is coupled to the host processor (202) to implement the virtual memory. The co-processor (224) includes a virtual-physical memory mapping device (915) for interrogating a virtual memory table and for mapping one or more virtual memory addresses (880) requested by the co-processor (224) into corresponding physical addresses (873) in the host memory (203). The virtual memory table is stored in two or more non-contiguously addressable regions of the host memory (203), and is preferably a page table. The memory mapping device (915) further includes a multiple-entry translation lookaside buffer (889) for caching virtual-to-physical address mappings (872), where entries in the buffer (889) are replaced on a least recently used replacement basis. The memory mapping device (915) also includes devices (901) for comparing, replacing, singly invalidating and multiply invalidating one or more entries of the translation lookaside buffer (889). It also includes a hashing device (892) for, upon an occurrence of a miss in the translation lookaside buffer (889), hashing a virtual memory address (880) using a hash function to produce an index into the virtual memory table.

Claims

1. A memory management apparatus for a co-processor coupled to a host processor with virtual memory, said co-processor adapted for using said virtual memory, said virtual memory comprising a plurality of virtual memory pages contained in a host memory coupled to said host processor, said host memory comprising a plurality of physical pages, said memory management apparatus including:

a buffering unit adapted to cache a predetermined number of virtual-to-physical memory address mappings, each memory-address mapping including a virtual-memory address and a corresponding physical address;

a comparison unit, adapted to compare a virtual-memory address requested by said co-processor with said memory-address mappings currently cached by said buffering unit;

an address provider adapted to, if said comparing unit determines said virtual memory address requested by said co-processor matches a virtual-memory address of one of said memory-address mappings in said buffering unit, provide a physical address to said co-processor from said matching memory-address mapping; and

an updating unit adapted to, if said comparing unit determines said virtual-memory address requested by said co-processor does not match the virtual memory address of any memory-address mapping currently cached in said buffering unit, update said buffering unit with a memory-address mapping retrieved from a page table, said retrieved memory-address mapping containing a physical address corresponding to said virtual memory address requested by said co-processor, said page table stored in a predetermined number of said physical pages.

2. The apparatus according to claim 1, wherein said predetermined number of said physical pages include at least two pages stored in two or more non-contiguously addressable regions of said host memory.

3. The apparatus according to claim 1, wherein:

said virtual memory address of said memory-address mapping comprises a virtual page number;

said physical address of said memory-address mapping comprises a physical page number in said host memory; and

said virtual memory address further comprises an offset within a respective virtual memory page, said offset being a predetermined number of lower order bits dependent on the size of said respective virtual memory page and also being the offset within a corresponding physical page.

4. The apparatus according to claim 3, wherein said pages are of a predetermined size, and said virtual memory page numbers and said physical memory page numbers are dimensioned to consist of a predetermined number of bits dependent upon said predetermined page size and a total size of said addressable memory.

5. The apparatus according to claim 4, wherein said virtual and physical page numbers include a fixed size portion of address bits dependent upon a minimum possible page size, and a variable size portion of the remaining address bits corresponding to a currently specified page size.

6. The apparatus according to claim 1, wherein said page table includes a predetermined number of memory-address mappings, each memory-address mapping including a virtual-memory page address and a physical page address in said host memory, said predetermined number of memory-address mappings corresponding to the number of said physical pages in said host memory.

7. The apparatus according to claim 1, wherein said updating unit further includes:

a hasher, adapted to hash a virtual-memory address of a virtual-memory page of a first number of bits into a page table index of a second number of bits, said second number being less than said first number of bits.

8. The apparatus according to claim 7, wherein said updating unit further includes:

a storing unit, adapted to store physical addresses of each of said predetermined number of physical pages constituting said page table.

9. The apparatus according to claim 8, wherein said page table index comprises a first predefined number of bits for selecting one of said stored physical addresses of said predetermined number of physical pages constituting said page table, and a second predefined number of remaining bits for selecting said retrieved memory-address mapping within said physical page corresponding said selected physical address.

10. The apparatus according to claim 9, further including a least-recently-used buffer for tracking use of said memory-address mappings in said buffering unit, and wherein said updating unit further includes:

a comparing unit, adapted to compare the virtual-memory page address of said retrieved memory-address mapping with a virtual-memory page address of said requested virtual-memory address;

a storing arrangement, adapted to, if said comparing unit determines a match, store said retrieved memory-address mapping in said buffering unit dependent upon said least-recently-used buffer and for updating said least-recently-used buffer; and

an incremental address unit, adapted to, if said comparing unit does not determine a match, incrementally address the next memory-addressing mapping in said page table and for continuing operation with said comparing unit the virtual-memory page addresses.

11. The apparatus according to claim 1, wherein said page table contains at least one invalid entry.

12. A method of managing virtual memory for a co-processor coupled to a host processor with said virtual memory, said co-processor adapted for using said virtual memory, said virtual memory comprising a plurality of virtual-memory pages contained in a host memory coupled to said host processor, said host memory comprising a plurality of physical pages, said method including the steps of:

caching a predetermined number of virtual-to-physical memory address mappings in a buffering unit, each memory-address mapping including a virtual-memory address and a corresponding physical address;

comparing a virtual-memory address requested by said co-processor with said memory-address mappings currently cached by said buffering unit;

if said comparison determines said virtual memory address requested by said co-processor matches a virtual-memory address of one of said memory-address mappings in said buffering unit, providing a physical address to said co-processor from said matching memory-address mapping; and

if said comparison determines said virtual-memory address requested by said co-processor does not match the virtual memory address of any memory-address mapping currently cached in said buffering unit, updating said buffering unit with a memory-address mapping retrieved from a page table, said retrieved memory-address mapping containing a physical address corresponding to said virtual memory address requested by said co-processor, said page table stored in a predetermined number of said physical pages.

13. The method according to claim 12 wherein said predetermined number of said physical pages include at least two pages stored in two or more non-contiguously addressable regions of said host memory.

14. The method according to claim 12, wherein:

said virtual memory address of said memory-address mapping comprises a virtual page number;

said physical address of said memory-address mapping comprises a physical page number in said host memory; and

said virtual memory address further comprises an offset within a respective virtual memory page, said offset being a predetermined number of lower order bits dependent on the size of said respective virtual memory page and also being the offset within a corresponding physical page.

15. The method according to claim 14, wherein said pages are of a predetermined size, and said virtual memory page numbers and said physical memory page numbers are dimensioned to consist of a predetermined number of bits dependent upon said predetermined page size and a total size of said addressable memory.

16. The method according to claim 15, wherein said virtual and physical page numbers include a fixed size portion of address bits dependent upon a minimum possible page size, and a variable size portion of the remaining address bits corresponding to a currently specified page size.

17. The method according to claim 12, wherein said page table includes a predetermined number of memory-address mappings, each memory-address mapping including a virtual-memory page address and a physical page address in said host memory, said predetermined number of memory-address mappings corresponding to the number of said physical pages in said host memory.

18. The method according to claim 12, wherein said updating step further includes the step of:

hashing a virtual-memory address of a virtual-memory page of a first number of bits into a page table index of a second number of bits, said second number being less than said first number of bits.

19. The method according to claim 18, wherein said updating step further includes the step of:

storing physical addresses of each of said predetermined number of physical pages constituting said page table.

20. The method according to claim 19, wherein said page table index comprises a first predefined number of bits for selecting one of said stored physical addresses of said predetermined number of physical pages constituting said page table, and a second predefined number of the remaining bits for selecting said retrieved memory-address mapping within said physical page corresponding to said selected physical address.

21. The method according to claim 20, further including the step of tracking said memory-address mappings in said buffering unit using a least-recently-used buffer, and wherein said updating step further includes the step of:

comparing the virtual-memory page address of said retrieved memory-address mapping with a virtual-memory page address of said requested virtual-memory address;

if said virtual-memory page address comparison determines a match, storing said retrieved memory-address mapping in said buffering unit dependent upon said least-recently-used buffer and for updating said least-recently-used buffer; and

if said virtual-memory page address comparison does not determine a match, incrementally addressing the next memory-addressing mapping in said page table and continuing operation with said step of comparing the virtual-memory page addresses.

22. The method according to claim 12, wherein said page table contains at least one invalid entry.

23. A system for managing virtual memory, said system including:

host processing equipment;

a host memory coupled to said host processing equipment to implement said virtual memory, wherein said virtual memory comprises a plurality of virtual-memory pages contained in said host memory and said host memory comprises a plurality of physical pages;

a co-processor adapted for using virtual memory;

a virtual-physical memory mapping unit, coupled to said co-processor, for interrogating a virtual memory table and for mapping one or more virtual memory addresses requested by said co-processor into corresponding physical addresses in said host memory, wherein said virtual memory table is a page table and said virtual-physical memory mapping unit further includes;

a multiple-entry translation lookaside buffer for caching virtual-to-physical memory address translations, each memory address translation including a virtual-memory address and a corresponding physical address;

a comparison unit, adapted to compare a virtual-memory address requested by said co-processor with said memory address translations stored in said translation lookaside buffer;

an address provider, adapted to, if said virtual memory address requested by said co-processor matches a virtual-memory address of one of said memory address translations in said translation lookaside buffer, provide a physical address to said co-processor from said matching memory address translation; and

an updating unit, adapted to, if said virtual-memory address requested by said co-processor does not match the virtual memory address of any memory address translation currently stored in said translation lookaside buffer, update a least-recently-used entry of said translation lookaside buffer with a memory address translation retrieved from said page table, said retrieved memory address translation containing a physical address corresponding to said virtual memory address requested by said co-processor, said page table stored in a predetermined number of said physical pages.

24. The system according to claim 23, wherein said predetermined number of said physical pages include at least two pages stored in two or more non-contiguously addressable regions of said host memory.

25. The system according to claim 23, wherein:

said virtual memory address of said memory address translation comprises a virtual page number;

said physical address of said memory address translation comprises a physical page number in said host memory; and

said virtual memory address further comprises an offset within a respective virtual memory page, said offset being a predetermined number of lower order bits dependent on the size of said respective virtual memory page and also being the offset within a corresponding physical page.

26. The system according to claim 25, wherein said pages are of a predetermined size, and said virtual memory page numbers and said physical memory page numbers are dimensioned to consist of a predetermined number of bits dependent upon said predetermined page size and a total size of said addressable memory.

27. The system according to claim 26, wherein said virtual and physical page numbers include a fixed size portion of address bits dependent upon a minimum possible page size, and a variable size portion of the remaining address bits corresponding to a currently specified page size.

28. The system according to claim 23, wherein said page table includes a predetermined number of memory address translations, each memory address translation including a virtual-memory page address and a physical page address in said host memory, said predetermined number of memory address translations corresponding to the number of said physical pages in said host memory.

29. The system according to claim 23, wherein said updating unit further includes:

a hasher, adapted to hash a virtual-memory address of a virtual-memory page of a first number of bits into a page table index of a second number of bits, said second number being less than said first number of bits.

30. The system according to claim 29, wherein said updating unit further includes:

a storing unit, adapted to store physical addresses of each of said predetermined number of physical pages constituting said page table.

31. The system according to claim 30, wherein said page table index comprises a first predefined number of bits for selecting one of said stored physical addresses of said predetermined number of physical pages constituting said page table, and a second predefined number of remaining bits for selecting said retrieved memory address translation within said physical page corresponding to said selected physical address.

32. The system according to claim 31, further including a least-recently-used buffer for tracking use of said memory address translations in said translation lookaside buffer, and wherein said updating unit further includes:

a comparison unit, adapted to compare the virtual-memory page address of said retrieved memory address translation with a virtual-memory page address of said requested virtual-memory address;

an address storing unit, adapted to, if said virtual-memory page addresses match, store said retrieved memory address translation in said translation lookaside buffer dependent upon said least-recently-used buffer and for updating said least-recently-used buffer; and

an incremental addressing unit, adapted to, if said virtual-memory page addresses do not match, incrementally address the next memory-addressing mapping in said page table and for continuing operation with said comparison unit for comparing the virtual-memory page addresses.

33. The system according to claim 23, wherein said page table contains at least one invalid entry.