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

• US 6,393,545 B1
• Filed: 06/05/2001
• Issued: 05/21/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): Zimmer, Mark
• Assistant Examiner(s): Monestime, Mackly
• Application Number:
  US09/873,429
• Time in Patent Office: 350 Days
• Field of Search: 712/34, 712/35, 712/200, 712/23, 712/32, 712/33, 711/147, 711/148, 711/153, 711/163
• 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 co-processor adapted for using virtual memory with host processing equipment, a memory being coupled to said host processing equipment to implement said virtual memory, said co-processor including:

a virtual-physical memory mapper adapted to interrogate a virtual memory table and map one or more virtual memory addresses requested by said co-processor into corresponding physical addresses in said memory coupled to said host processing equipment, wherein said virtual memory table is a page table stored in a plurality of physical pages of said memory and comprises a plurality of entries each containing one said virtual memory address and one said corresponding physical address, said virtual-physical memory mapper comprising;

a storing unit, adapted to store a physical address of each one of said plurality of physical pages constituting said page table;

a hasher, adapted to hash said requested virtual memory address using a hash function to produce a page table index, wherein said page table index comprises a first predefined number of bits indicating one of said stored physical addresses of said plurality of physical pages constituting said page table, and a second predefined number of remaining bits indicating an entry within a physical page;

a selector unit, adapted to select one of said stored physical addresses of said plurality of physical pages constituting said page table in response to said first predefined number of bits of said produced page table index;

an address generator, adapted to generate a physical address of an entry within a physical page using said selected physical address and said second predefined number of remaining bits of said produced page table index; and

an address retriever, adapted to retrieve said physical address contained in said entry table corresponding to said requested virtual memory address using said generated physical address.

2. The co-processor according to claim 1, wherein said virtual memory table is stored in two or more non-contiguously addressable regions of said memory.

3. The co-processor according to claim 1, wherein said virtual-physical memory mapper further includes:

a multiple-entry translation lookaside buffer for caching virtual-to-physical address mappings.

4. The co-processor according to claim 3, wherein said virtual-physical memory mapper further includes:

a buffer entry check unit, adapted to compare, replace, singly invalidate and multiply invalidate one or more entries of said translation lookaside buffer.

5. The co-processor according to claim 3, wherein said translation lookaside buffer is adapted to replace entries therein on a least-recently-used replacement basis.

6. The co-processor according to claim 3, wherein said hasher hashes said virtual memory address upon occurrence of a miss in said translation lookaside buffer.

7. A method of operating a co-processor to use virtual memory with host processing equipment, wherein said virtual memory is implemented in a memory coupled to said host processing equipment, said method including the steps of:

interrogating a virtual memory table; and

mapping one or more virtual memory addresses requested by said co-processor into corresponding physical addresses in said memory coupled to said host processing equipment, wherein

said virtual memory table is a page table stored in a plurality of physical pages of said memory and comprises a plurality of entries each containing a virtual memory address and a corresponding physical address,

a physical address of each one of said plurality of physical pages constituting said page table are stored in a storing unit, and

said mapping step comprises the sub-steps of;

hashing said requested virtual memory address using a hash function to produce a page table index, wherein said page table index comprises a first predefined number of bits indicating one of said stored physical addresses of said plurality of physical pages constituting said page table, and a second predefined number of remaining bits indicating an entry within a physical page;

selecting one of said physical addresses of said plurality of physical pages constituting said page table in response to said first predefined number of bits of said produced page table index;

generating a physical address of an entry within a physical page using said selected physical address and said second predefined number of remaining bits of said produced page table index; and

retrieving said physical address contained in said entry corresponding to said requested virtual memory address using said generated physical address.

8. The method according to claim 7, wherein said virtual memory table is stored in two or more non-contiguously addressable regions of said memory.

9. The method according to claim 7, further including the step of:

caching virtual-to-physical address mappings in a multiple-entry translation lookaside buffer.

10. The method according to claim 9, further including the steps of:

comparing, replacing, singly invalidating and multiply invalidating one or more entries of said translation lookaside buffer.

11. The method according to claim 9, wherein entries of said translation lookaside buffer are replaced on a least-recently-used replacement basis.

12. The method according to claim 9, wherein said hashing step is initiated upon occurrence of a miss in said translation lookaside buffer.

13. 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;

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 coupled to said host processing equipment, wherein

said virtual memory table is a page table stored in a plurality of physical pages of said host memory and comprises a plurality of entries each containing one said virtual memory address and one said corresponding physical address, and

said virtual-physical memory mapping unit comprises;

a storing unit, adapted to store a physical address of each one of said plurality of physical pages constituting said page table;

a hasher, adapted to hash said requested virtual memory address using a hash function to produce a page table index, wherein said page table index comprises a first predefined number of bits indicating one of said stored physical addresses of said plurality of physical pages constituting said page table, and a second predefined number of remaining bits indicating an entry within a physical page;

a selector unit, adapted to select one of said stored physical addresses of said plurality of physical pages constituting said page table in response to said first predefined number of bits of said produced page table index;

an address generator, adapted to generate a physical address of a entry within a physical page using said selected physical address and said second predefined number of remaining bits of said produced page table index; and

an address retriever, adapted to retrieve said physical address contained in said entry corresponding to said requested virtual memory address using said generated physical address.

14. The system according to claim 13, wherein said virtual memory table is stored in two or more non-contiguously addressable regions of said host memory.

15. The system according to claim 13, wherein 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 page address and a corresponding physical page address.

16. The system according to claim 15, wherein said virtual-physical memory mapping unit further includes:

a buffer entry checker, adapted to compare, replace, singly invalidate and multiply invalidate one or more entries of said translation lookaside buffer.

17. The system according to claim 15, wherein said translation lookaside buffer is adapted to replace entries therein on a least-recently-used replacement basis.

18. The system according to claim 15, wherein said hasher hashes said virtual memory address upon an occurrence of a miss in said translation lookaside buffer.

19. The system according to claim 15, wherein said virtual memory comprises a plurality of virtual-memory pages contained in said host memory.