Patent ID: 8010770

Claim:
A caching device for NAND flash translation layer positioned between a memory read/write controller and a flash memory, comprising: an instruction register connecting the memory read/write controller from which the instruction for reading or writing the flash memory from the memory read/write controller is received and temporarily stored; a logical address register connecting the memory read/write controller from which the logical address for reading or writing the flash memory from the memory read/write controller is received and temporarily stored; a data register connecting the memory read/write controller so that the data for writing into or reading from the flash memory is temporarily stored; an address translation unit which is a memory device containing address mapping table for the logical and physical addresses of the flash memory; a microprocessor connecting the instruction register and the address translation unit responsible not only for the reading and writing the flash memory but also for the caching operation for logical and physical address translation; a caching control unit which is a programmable device containing the caching instruction and data for caching the logical and physical address mapping; a pair of auxiliary controllers where a first auxiliary controller interfaces the data and logical address registers with the microprocessor, and a second auxiliary controller interfaces the caching control unit with the microprocessor via which the caching instructions are fed into the microprocessor for execution; a flash memory address register interfacing the address translation unit and the second auxiliary controller with the flash memory for temporarily storing the obtained physical address in accessing the flash memory via the second auxiliary controller; and a caching instruction and data buffer area which is a memory device connecting the caching control unit for temporarily storing the caching instruction and data used by the caching control unit, wherein a caching mechanism established in the caching instruction and data buffer area comprises a search tree, an internal translation node, an external translation node, a translation unit, a link list, and a root, wherein the internal translation node is assigned a first set of attribute values, the external translation node is assigned a second set of attribute values, the first set of attribute values comprises a first parameter to point to the external translation node, and the second set of attribute values comprises a second parameter to point to a link list of the translation unit.