System and method for searching mapping table of flash memory

• US 7,991,944 B2
• Filed: 02/06/2008
• Issued: 08/02/2011
• Est. Priority Date: 02/13/2007
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Lee, Jeong-Woo, Lee, Byoung-Kook
• Primary Examiner(s): Nguyen; Hiep T
• Application Number:
  US12/026,837
• Publication Number:
  US 20080195802A1
• Time in Patent Office: 1,273 Days
• Field of Search: None
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages

Abstract

A system and method for searching a mapping table of a flash memory is provided. The system includes at least one random access memory for storing the mapping table retrieved from the flash memory and at least one search engine for searching for data from the mapping table stored in the at least one random access memory using dedicated hardware. Thus, the search efficiency for the mapping table and system performance may be increased.

Claims

1. A flash memory system for interfacing a host device to a flash memory, comprising:

at least one random access memory for storing a mapping table mapping logical memory addresses of the flash memory to physical memory addresses of the flash memory, the mapping table retrieved from the flash memory; and

at least one dedicated hardware-based search engine, which is distinct from a memory controller, associated with each of the at least one random access memories for searching for desired physical memory addresses of the flash memory from the mapping table stored in the random access memory, wherein the dedicated hardware-based search engine comprises;

a start address register for storing a start address from which searching starts;

an ending address register for storing an ending address from which searching ends;

a search value register for storing a value of a logical address to be searched for;

a hit address register for storing a physical address corresponding to the logical address to be searched for; and

a control register for storing a control command for the dedicated hardware-based search engine.

2. The system according to claim 1, further comprising a controller for loading the mapping table into the at least one random access memory and controlling the at least one search engine.

3. The system according to claim 2, wherein there are two or more random access memories including:

a first random access memory having a relatively higher access and interface speed; and

a second random access memory having a relatively lower access and interface speed than the first random access memory.

4. The system according to claim 3, wherein the first random access memory is a static random access memory (SRAM), and the second random access memory is a dynamic random access memory (DRAM).

5. The system according to claim 3, wherein the controller loads first mapping table data having high importance, small size, or high search frequency into the first random access memory, and loads second mapping table data having low importance, great size, or low search frequency into the second random access memory.

6. The system according to claim 2, wherein each of the two or more search engines operate independently of each other.

7. The system according to claim 5, wherein the first mapping table data and the second mapping table data are transferred via a common data bus and are retrieved into the first random access memory and the second random access memory, respectively.

8. The system according to claim 5, wherein the first mapping table data is transferred via a first data bus and retrieved into the first random access memory, and the second mapping table data is transferred via a second data bus slower than the first data bus and retrieved into the second random access memory.

9. A method for searching a mapping table mapping logical memory addresses of a flash memory to physical memory addresses of the flash memory, the method comprising:

loading data of the mapping table of the flash memory into a first and second random access memory, the first and second random access memories differing in access and interface speed;

inputting an address range and a logical address of the flash memory to at least a first and second dedicated hardware-based search engine, distinct from a memory controller, associated with each of the first and second random access memory, the first and second search engines being independent from each other; and

searching for a physical address corresponding to the logical address from the mapping table data retrieved in the first and second random access memories using the first and second dedicated hardware-based search engines, and outputting a hit address corresponding to the physical address.

10. The method according to claim 9, wherein the mapping table data are divided according to importance, size and search frequency and separately retrieved into the first and second random access memories.

11. The method according to claim 10, wherein data of the mapping table data having high importance, small size, or high search frequency is retrieved into the first random access memory, and data of the mapping table data having low importance, great size, or low search frequency is retrieved into the second random access memory, wherein the first random access memory has a higher access speed and interface speed than the second random access memory.

12. The method according to claim 11, wherein the first random access memory is an SRAM, and the second random access memory is a DRAM.

13. The method according to claim 11, wherein:

the first search engine searches the mapping table data from the first random access memory; and

the second search engine searches the mapping table data rom the second random access memory, wherein the first search engine and the second search engine operate independently of each other.

14. A method for searching a mapping table of a flash memory, the mapping table mapping logical memory addresses of the flash memory to physical memory addresses of the flash memory, the method comprising searching the mapping table using at least one dedicated hardware-based search engine, distinct from a memory controller, the dedicated hardware-based search engine comprising:

a start address register for storing a start address from which searching starts;

an ending address register for storing an ending address from which searching ends;

a search value register for storing a value of a logical address to be searched for;

a hit address register for storing a physical address corresponding to the logical address to be searched for; and

a control register for storing a control command for the dedicated hardware-based search engine.

15. The method according to claim 14, comprising dividing data of the mapping table according to importance, search frequency, and size;

separately loading the divided data into at least two random access memories; and

searching for the mapping table data from the random access memories using at least two corresponding search engines of the at least one search engine.