CN104268094B - Optimized flash memory address mapping method - Google Patents
Optimized flash memory address mapping method Download PDFInfo
- Publication number
- CN104268094B CN104268094B CN201410488749.5A CN201410488749A CN104268094B CN 104268094 B CN104268094 B CN 104268094B CN 201410488749 A CN201410488749 A CN 201410488749A CN 104268094 B CN104268094 B CN 104268094B
- Authority
- CN
- China
- Prior art keywords
- page
- address
- data
- block
- flash memory
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 230000015654 memory Effects 0.000 title claims abstract description 93
- 238000013507 mapping Methods 0.000 title claims abstract description 79
- 238000000034 method Methods 0.000 title claims abstract description 76
- 238000006243 chemical reaction Methods 0.000 claims abstract description 130
- 239000010813 municipal solid waste Substances 0.000 claims description 64
- 230000009466 transformation Effects 0.000 claims description 30
- 238000005457 optimization Methods 0.000 claims description 20
- 238000006073 displacement reaction Methods 0.000 claims description 9
- 238000009826 distribution Methods 0.000 claims description 9
- 238000003860 storage Methods 0.000 claims description 9
- 238000000205 computational method Methods 0.000 claims description 3
- 238000006467 substitution reaction Methods 0.000 claims description 3
- 235000013399 edible fruits Nutrition 0.000 claims description 2
- 238000003306 harvesting Methods 0.000 claims 1
- 238000013519 translation Methods 0.000 description 10
- 238000002474 experimental method Methods 0.000 description 8
- 230000008569 process Effects 0.000 description 7
- 230000002776 aggregation Effects 0.000 description 5
- 238000004220 aggregation Methods 0.000 description 5
- 230000007246 mechanism Effects 0.000 description 5
- 238000013500 data storage Methods 0.000 description 4
- 230000006870 function Effects 0.000 description 4
- 238000004088 simulation Methods 0.000 description 4
- 230000009897 systematic effect Effects 0.000 description 4
- 230000006399 behavior Effects 0.000 description 3
- 238000000151 deposition Methods 0.000 description 3
- 238000011161 development Methods 0.000 description 3
- 230000018109 developmental process Effects 0.000 description 3
- 238000005516 engineering process Methods 0.000 description 3
- 238000007726 management method Methods 0.000 description 3
- 238000011084 recovery Methods 0.000 description 3
- 230000008901 benefit Effects 0.000 description 2
- 230000008859 change Effects 0.000 description 2
- 238000011156 evaluation Methods 0.000 description 2
- 239000004744 fabric Substances 0.000 description 2
- 230000004927 fusion Effects 0.000 description 2
- 238000012423 maintenance Methods 0.000 description 2
- 230000005055 memory storage Effects 0.000 description 2
- 238000012545 processing Methods 0.000 description 2
- 230000002123 temporal effect Effects 0.000 description 2
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000007812 deficiency Effects 0.000 description 1
- 239000008187 granular material Substances 0.000 description 1
- 230000035800 maturation Effects 0.000 description 1
- 210000003205 muscle Anatomy 0.000 description 1
- 230000009467 reduction Effects 0.000 description 1
- 238000011160 research Methods 0.000 description 1
- 230000004044 response Effects 0.000 description 1
- 230000035939 shock Effects 0.000 description 1
- 239000007787 solid Substances 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
- G06F12/023—Free address space management
- G06F12/0238—Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
- G06F12/0246—Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory in block erasable memory, e.g. flash memory
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
- G06F2212/72—Details relating to flash memory management
- G06F2212/7201—Logical to physical mapping or translation of blocks or pages
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Memory System (AREA)
- Techniques For Improving Reliability Of Storages (AREA)
- Memory System Of A Hierarchy Structure (AREA)
Abstract
The invention discloses an optimized flash memory address mapping method, in a demand-based page level address mapping DFTL method, a global conversion page mapping table GTD is maintained in a memory, and meanwhile, an address mapping cache CMT is used in the memory to cache frequently accessed address mapping items in a conversion page, wherein cached data units are the whole address conversion page. The invention unifies the granularity of the address mapping information in the flash memory and the cache, fully utilizes the time locality and the space locality of the data, for example, frequently accesses the local data in a short time, only needs to access the page-level address mapping cache without accessing the flash memory, and simultaneously, when a certain conversion page needs to be replaced out of the cache, all the updated address mapping information can be updated into the flash memory together, thereby improving the utilization rate of the mapping information.
Description
Technical field
The present invention relates to flash memory technology field, and in particular to a kind of flash memory address mapping method of optimization.
Background technology
Development and maturation with flash memory technology, flash memories are widely used to all kinds of storage systems, such as USB flash disk, intelligence
Energy mobile phone, panel computer, digital memory card, solid state hard disc etc..Compared with traditional magnetic disk memorizer, flash memory has readwrite performance
The advantages such as high, non-volatile, low-power consumption, high density and good shock resistance.Therefore, flash memory has become mobile embedded type equipment
Storage medium.However, flash memory there is also some limitations, such as " strange land renewal " and the erasable number of times of limited block.In order to solve these
Deficiency simultaneously makes flash memory work as traditional block device, and a kind of referred to as flash translation layer (FTL) (flash is occurred in that in flash-memory storage system
Translation layer, abbreviation FTL) embedded software, for process exterior I/O request and management flash memory.Wherein, ground
Location mapping as a significant components is responsible for that the logical address for coming from file system is converted to the physical address in flash memory.
Therefore, how to efficiently perform address of cache and manage map information, become a key issue.
NAND is a kind of storage scheme more more preferable than hard disk drive, and this is showed in the low capacity application less than 4GB
It is still obvious to obtain.As people persistently pursue, power consumption is lower, weight lighter and performance more preferably product.Flash chip is mainly by thing
Reason block composition, each physical block is divided into a number of Physical Page：Block is the elementary cell of erasable operation, and page is read-write operation
Elementary cell.One page contains data field and backup domain, and backup domain is also called OOB (out of band).OOB is typically used
In storage error correcting code (ECC) and some self-defined informations.
Although nand flash memory has many advantages, some limitations are there is also：
First it is " strange land renewal ", cannot updates again after data page is written into data, until affiliated whole block quilt
Erasing.Therefore, different Physical Page will be written into the different update data of same logical address, wherein, deposit latest data
Page be referred to as active page, and before legacy data page is referred to as invalid page.Therefore, address mapping method conversion logic ground is needed in flash memory
The physical address that location is located to latest data；Simultaneously as data page is constantly consumed, garbage reclamation mechanism is needed to go copy effective
Page simultaneously wipes invalid data block, to regain sky data block.
Next to that the restriction of limited erasable number of times, for single stage unit (SLC) nand flash memory, the erasable number of times of each block is big
It is approximately 100 000 times, and to multi-level unit (MLC) nand flash memory, erasable number of times only about 10 000 times.Wipe as fruit block is actual
Write number of times and be then likely to become bad block more than limiting, it is impossible to used again.Consequently, it is desirable to uniform loss mechanism is balancing different masses
Temperature, and choose suitable data block and carry out garbage reclamation.
In order to make up drawbacks described above, flash translation layer (FTL) (FTL) management flash memory used in nand flash memory.Flash translation layer (FTL) is located at
It is fully transparent to user between file system and flash drive layer, and the operate interface for providing block device for topmost paper system.
Address of cache as the significant components of flash translation layer (FTL) is responsible for that sudden strain of a muscle will be converted to from the logical address of file system
Physical address in depositing.Address mapping method is broadly divided into 3 classes：Page level mapping, the mapping of block level and mixed-use developments.
In page level address of cache, map information granularity is consistent with date read-write cell, is all data page, therefore data please
Asking can write in any data page of flash memory.Meanwhile, page level address of cache can postpone the time of garbage reclamation triggering, also
It is to say, until the close saturation of flash memory storage just triggers garbage reclamation, therefore, it is possible to obtain more excellent systematic function.But page level ground
Location mapping method needs to safeguard huge page level address mapping table, is difficult in resource-constrained embedded system.Block level
The mapping granule of address of cache is data block, and the logical address of each request of data is divided into block number and block bias internal amount, and each is patrolled
Collect block and be allocated one or more physical blocks, yet with the restriction of " strange land renewal ", the data page of data storage cannot be straight
Renewal is connect, therefore, there is update inconsistency in block level address of cache, may trigger substantial amounts of garbage reclamation, and systematic function is relatively low.Mixed
In closing mapping method, physical block is divided into data block (primary block) and log blocks (log block), makes in data block
The data write first with the mapping of block level address of cache, and log blocks are updated the data using page level address of cache storage.Although mixed
Close mapping and weighed systematic function and memory cost, but need to be closed data block and log blocks in garbage reclamation mechanism
And, it is possible to create substantial amounts of performance cost, therefore, mixed-use developments method is also without solving well asking for performance and memory cost
Topic.
Need-based page level address of cache (DFTL) is proposed in recent years, is on the one hand carried using page level address mapping method
For efficient address translation performance, on the other hand, the generation of page level address mapping table is solved by address of cache caching mechanism
A large amount of memory cost problems.
Physical block in DFTL is logically divided into two classes：Data block (data block) and address conversion block
(translation block).Data block is used for data storage, and conversion block is used to preserve page level address mapping table.Data block and
The physical space of the shared flash memory of conversion block.Page in each address conversion block is referred to as address conversion page (translation
Page), each page contains a number of logical page number (LPN) to the page level address of cache item of physical page number.It is newest to navigate to
Conversion page, maintains a global transformation page map table (global translation directory, abbreviation in internal memory
GTD).Meanwhile, address of cache caching (cached mapping table, abbreviation CMT) used in internal memory, to be buffered in conversion
The address of cache item frequently accessed in page.. address of cache caching enters line replacement using lru algorithm to address of cache item.Due to interior
GTD and CMT is only safeguarded in depositing, memory cost is significantly reduced.Meanwhile, using the temporal locality of request of data, maintain efficiently
Address of cache performance.
In need-based page level mapping method, the operation to address conversion page will produce extra performance cost, open
Pin is mainly derived from two aspects：
First, address of cache item is extracted from the address conversion page of flash memory and will produces the read operation of conversion page in caching,
When caching is completely needed into line replacement, the more new mappings item of displacement needs first to read corresponding conversion page, and writes in the updated
Backflash is deposited.Therefore, during cache miss, best situation produces 1 read operation, and worst case can produce 2 read operations and 1
Write operation.As shown in Figure 1, it is assumed that the logical address of request of data is 28, due to cache miss, GTD is accessed first and is obtained most
The address of new address conversion page, then reads the page (TP1) from internal memory, navigate to corresponding address of cache item (28,56), most
After put it into address of cache caching in.When CMT displace address of cache item (112, when 84), due to the mapping item in the buffer
It is updated, needs to obtain the address conversion page (TP32) in flash memory according to GTD first, reads and update after the page corresponding address
Mapping item, in finally writing back to new conversion page.Can see, address of cache caching can bring many address conversion page read-write behaviour
Make, during these operations are interspersed in processing data request, affect systematic function.
On the other hand, performance cost derives from garbage collection procedure.When data block is by garbage reclamation, all active pages pair
The conversion page answered is required for updating, as shown in Fig. 2 having 4 active pages (PPN from 10 to 13) in block is reclaimed, each page right
Should be in different conversion pages (respectively TP97, TP100, TP101, TP103), after copy active page, all corresponding addresses
Conversion page is also required to be read, updates, writes back to (respectively TP128, TP129, TP130, TP131 after writing back) in flash memory.Value
It is noted that the actual address mapping information for updating only has 4, but cause the renewal operation of 4 conversion pages of correspondence.Therefore,
When there is many valid data pages in reclaiming block, garbage reclamation will produce substantial amounts of conversion web update expense.
The content of the invention
The technical problem to be solved in the present invention is：Generally speaking, need-based page level address mapping method has two
Subject matter, first, the map information utilization rate of address of cache caching is relatively low, and after whole conversion page is read, a caching is wherein
One address of cache item.For continuous read-write, certain address conversion page may be repeated quickly and easily as many times as required request and produce a large amount of expenses.Its
Secondary, in processing write requests, the data of Different Logic address are continuously written in same data block, will be produced in garbage reclamation
Substantial amounts of conversion web update.For the problems referred to above, a kind of address mapping method of optimization is devised herein.
The present invention from need-based page level address mapping method, open by the extra performance caused with solving address of cache
Pin problem.This Section Overhead be mainly derived from address of cache caching and flash memory in address conversion page.By analyzing the two
Source, devises a kind of complete optimization method based on the caching mechanism of conversion page, flash data write and garbage reclamation.
The technical solution adopted in the present invention is：
A kind of flash memory address mapping method of optimization, in need-based page level address of cache (DFTL) method, internal memory
In maintain a global transformation page map table (global translation directory, abbreviation GTD), meanwhile, including
Address of cache caching (cached mapping table, abbreviation CMT) used in depositing, changes what is frequently accessed in page to be buffered in
Address of cache item, the data cell of caching is whole address conversion page, the address mapping information unified in flash memory and caching
Granularity, each address conversion page contains the map information of 1MB address spaces, local data is frequently accessed such as in the short time, only
Page level address of cache caching need to be accessed without accessing flash memory；Meanwhile, when certain conversion page needs to be displaced caching, institute
The address mapping information for having renewal can be updated in the lump in flash memory, improve the utilization rate of map information.
The GTD is also a page level address mapping table, the address conversion page being responsible in positioning flash memory, is turned address is read
After skipping, actual address mapping information, and the flash memory address mapping method of the optimization can be obtained using the overall situation in internal memory
Conversion page map table and page level address of cache caching have the access process of both same map Information Granularity, fusion, extend
Global transformation page map table GTD, increased caching index (cache index, abbreviation CI), during directly positioning is cached from GTD
Conversion page, make conversion page map table be directly linked to page level mapped cache；When there is logical address request, first according to request
Logical address navigate to the item of global transformation page map table, because the initial logical address of each is fixed, therefore, will
Logical address can have access to the item in conversion page map table, the Xiang Wei divided by the address of cache item number that each conversion page is preserved
Conversion page physical address in a flash memory and caching index are protected；If caching index is 1, show the conversion page not yet
Caching, needs to access flash memory acquisition address mapping information；Otherwise, according to caching index can direct access cache address of cache page
To obtain the physical address of request.
The new address of cache access mode proposed by this method, simplifies the access process of address of cache, will cache
In continuous or Hash lookup mode be changed into directly access, saved the cache access time.
The flash memory address mapping method of the optimization uses LRU (LRU) slow as page level address of cache
The Replacement Strategy deposited, wherein, the update times for changing page are also one of foundation of selection displacement, if certain conversion page is in caching
In be never updated, it will go out caching by preferential substitution, because such replacement operator will not produce extra conversion page and read
Write expense.Using initial address (start logical address, the letter of the corresponding address conversion page of displacement item in caching
Claim SLA) and global transformation page map table (GTD), to position flash memory in actual storage conversion page address, execution replacement operator.
In the example in figure 3, when there is individual write request W, when 49, the 13rd conversion page in PAMC needs replaced.Can see, put
When changing, all 4 amended map informations being capable of write-once address conversion page.
In order to further reduce because address mapping information updates the conversion page expense brought, methods described is employed to be based on and turned
The data method for congregating for skipping：Using the corresponding conversion page of its logical address as guidance, logical address is corresponding to same for data write
The data of one conversion page will be written into identical data block, therefore, during garbage reclamation, the corresponding conversion number of pages of data block is most
For constant 1, the expense that resulting extra address mapping information updates is reduced to minimum.
In order to realize data method for congregating, the flash memory address mapping method of the optimization continues to extend the mapping of global transformation page
Table, each item in table saves the physical address (available page number, abbreviation APN) of data available page, its
In, physical address represents this and not yet distributes data block for 1, meanwhile, using empty block pond (free block pool, abbreviation
FBP) all of empty data block in flash memory is recorded, when there is request of data, the empty data block of distribution according to need maps to global transformation page
Table, in garbage reclamation, it is erasable after empty block be recovered to sky block pond, data aggregation technique optimizes the data point in data block
Cloth, i.e. the logical address of data is limited in the address space range of corresponding conversion page maintenance, due to address in each data block
Close data are easier to be updated together, active page number of copies when the method can indirectly reduce garbage reclamation.
In the flash memory starting stage, there is free data block to belong to sky block pond, each data available in global transformation page map table
Page address is all unallocated state (1), when there is write data requests, according to computational methods mentioned above global transformation is positioned
The item of page map table, if the APN in item is 1, directly writes data into corresponding data page, and it is institute subsequently to update APN
Next data available page in distribution data block, if data block is full, by the address 1 is set to；Otherwise, if the conversion page
Not yet distribute data block, check in empty block pond and whether there is available empty data block, the 1st is distributed according to need and recorded if existing
The physical address of data page otherwise calls garbage reclamation to obtain new empty data block as APN.
Because physical block is divided into data block and address conversion block according to data storage type, accordingly there are two kinds of rubbish
Rubbish is reclaimed:Data block garbage reclamation and conversion block garbage reclamation. in the garbage reclamation of data block, in order to ensure each data block
Only correspondence one changes page after garbage reclamation, and the flash memory address mapping method of the optimization will be based on conversion page data aggregation side
Method is multiplexed in garbage reclamation, and in address of cache, the promoter of request of data is file system, and in garbage reclamation is rubbish
Rubbish withdrawer, both have similar address of cache process, therefore method can be multiplexed, in the garbage collection procedure of data block
In, when Garbage Collector needs to copy an active page, the mapping of global transformation page is accessed first to obtain current available number
According to the physical address (APN) of page, if data available page is that (non-1), directly writes data available by active page for presence
Page；Otherwise, if the data block of current distribution has run out, using swap block (swap block) as newly assigned data
Block stores active page；When garbage reclamation is completed, the empty data block after erasing is used as new swap block.
In order to the erasable number of times of equilibrium criterion block extends the durability of flash memory, the erasable of each data block is have recorded in flash memory
Number of times, can safeguard the temperature information of data area in global transformation page map table, record each address conversion page correspondence continuous
The access frequency of logical space, few " cold " block of erasable number of times is selected to the frequent item for accessing when write pointer request distributes, and
Then distribute erasable number of times more " heat " block to what is infrequently accessed；Equally, in garbage reclamation, select erasable number of times less and
The more data block of invalid page carries out erasable as recovery block；In flash memory free time, data can be carried out to hot and cold data block
Exchange with erasable number of times between balance weight.
Beneficial effect of the present invention：The granularity of the address mapping information that the present invention has unified in flash memory and caching, makes full use of
The temporal locality and spatial locality of data, frequently accesses local data such as in the short time, only need to access page level address of cache
Cache without accessing flash memory, meanwhile, when certain conversion page needs to be displaced caching, the address of cache letter of all renewals
Breath can be updated in the lump in flash memory, improve the utilization rate of map information.
Description of the drawings
Fig. 1 is that address of cache caches the expense for producing；
The conversion page behaviour that Fig. 2 is produced when being garbage reclamation（Effective page copy when data block is reclaimed）；
The conversion page behaviour that Fig. 3 is produced when being garbage reclamation（The renewal of address conversion page when data block is reclaimed）
Fig. 4 is slow for page level address of cache；
Fig. 5 is based on the data aggregation of conversion page；
Fig. 6 is the data block garbage reclamation based on conversion page；
Fig. 7 is the garbage reclamation of conversion block；
Fig. 8 is the simulation frame used in experiment.
Specific embodiment
Below according to Figure of description, in conjunction with specific embodiments, the present invention is further described：
A kind of flash memory address mapping method of optimization, in need-based page level address of cache (DFTL) method, internal memory
In maintain a global transformation page map table GTD, meanwhile, used in internal memory address of cache caching CMT, to be buffered in conversion
The address of cache item frequently accessed in page, the data cell of caching is whole address conversion page, in having unified flash memory and caching
The granularity of address mapping information, each address conversion page contains the map information of 1MB address spaces, such as in the short time frequently
Local data is accessed, page level address of cache caching need to be only accessed without accessing flash memory；Meanwhile, when certain conversion page need by
When displacing caching, the address mapping information of all renewals can be updated in the lump in flash memory, improve the utilization of map information
Rate.
The GTD is also a page level address mapping table, the address conversion page being responsible in positioning flash memory, is turned address is read
After skipping, actual address mapping information, and the flash memory address mapping method of the optimization can be obtained using the overall situation in internal memory
Conversion page map table and page level address of cache caching have the access process of both same map Information Granularity, fusion, extend
Global transformation page map table GTD, increased caching index (cache index, abbreviation CI), during directly positioning is cached from GTD
Conversion page, make conversion page map table be directly linked to page level mapped cache；When there is logical address request, first according to request
Logical address navigate to the item of global transformation page map table, because the initial logical address of each is fixed, therefore, will
Logical address can have access to the item in conversion page map table, the Xiang Wei divided by the address of cache item number that each conversion page is preserved
Conversion page physical address in a flash memory and caching index are protected；If caching index is 1, show the conversion page not yet
Caching, needs to access flash memory acquisition address mapping information；Otherwise, according to caching index can direct access cache address of cache page
To obtain the physical address of request.
The new address of cache access mode proposed by this method, simplifies the access process of address of cache, will cache
In continuous or Hash lookup mode be changed into directly access, saved the cache access time.
As shown in figure 4, caching example for page level address of cache, it is assumed that each conversion page can store 6 address of cache items,
It is 36 that the logical address of data is read in request, first, its map information item is positioned in global transformation page map table, by calculating
36/6=6 navigates to the 6th in mapping table, and it changes page address into 94, and caching index is 11.Because caching index is not 1,
Can directly access the 11st of PAMC obtain actual address mapping (36,134), so as to obtain counterlogic address 36 physically
Location is 134.
The flash memory address mapping method of the optimization uses LRU (LRU) slow as page level address of cache
The Replacement Strategy deposited, wherein, the update times for changing page are also one of foundation of selection displacement, if certain conversion page is in caching
In be never updated, it will go out caching by preferential substitution, because such replacement operator will not produce extra conversion page and read
Write expense.Using initial address (start logical address, the letter of the corresponding address conversion page of displacement item in caching
Claim SLA) and global transformation page map table (GTD), to position flash memory in actual storage conversion page address, execution replacement operator.
In the example in fig. 4, when have individual write request for (W, when 49), the 13rd in PAMC conversion page need it is replaced,
Can see, during displacement, all 4 amended map informations being capable of write-once address conversion page.
In order to further reduce because address mapping information updates the conversion page expense brought, methods described is employed to be based on and turned
The data method for congregating for skipping：Using the corresponding conversion page of its logical address as guidance, logical address is corresponding to same for data write
The data of one conversion page will be written into identical data block, therefore, during garbage reclamation, the corresponding conversion number of pages of data block is most
For constant 1, the expense that resulting extra address mapping information updates is reduced to minimum.
In order to realize data method for congregating, the flash memory address mapping method of the optimization continues to extend the mapping of global transformation page
Table, each item in table saves the physical address (available page number, abbreviation APN) of data available page, its
In, physical address represents this and not yet distributes data block for 1, meanwhile, using empty block pond (free block pool, abbreviation
FBP) all of empty data block in flash memory is recorded, when there is request of data, the empty data block of distribution according to need maps to global transformation page
Table, in garbage reclamation, it is erasable after empty block be recovered to sky block pond, data aggregation technique optimizes the data point in data block
Cloth, i.e. the logical address of data is limited in the address space range of corresponding conversion page maintenance, due to address in each data block
Close data are easier to be updated together, active page number of copies when the method can indirectly reduce garbage reclamation.
In the flash memory starting stage, there is free data block to belong to sky block pond, each data available in global transformation page map table
Page address is all unallocated state (1), when there is write data requests, according to computational methods mentioned above global transformation is positioned
The item of page map table, if the APN in item is 1, directly writes data into corresponding data page, and it is institute subsequently to update APN
Next data available page in distribution data block, if data block is full, by the address 1 is set to；Otherwise, if the conversion page
Not yet distribute data block, check in empty block pond and whether there is available empty data block, the 1st is distributed according to need and recorded if existing
The physical address of data page otherwise calls garbage reclamation to obtain new empty data block as APN.
As shown in figure 5, assembling example for data, it is assumed that include 4 Physical Page in each block, each conversion page can preserve 6
Individual address of cache item.For the write request of logical address 36, it is 36/6=6 that the item in its global transformation page map table is calculated first,
Then the address (APN) for obtaining data available page is 22.Therefore, data D can directly write to the data page 22 of data block 5
In.After write, data available page address is updated to into 23.For the write request that another logical address is 49, the 8th is calculated
The APN of item is 1, illustrates that the conversion page not yet distributes data block, therefore obtains an empty data block from empty block pond, then by number
Write in the 1st data page (data page 32) of empty block according to E, finally, APN is updated to next data page address 33.Can see
Arrive, for data block 5, according to data method for congregating, corresponding address mapping information all belongs to change page TP48.Here,
TP48 in the buffer, therefore directly can in the buffer update address mapping information.A new empty block also corresponding conversion page
TP65.So, each data block at most only corresponds to 1 address conversion page, so as to by the renewal cost reduction of conversion page to minimum.
Because physical block is divided into data block and address conversion block according to data storage type, accordingly there are two kinds of rubbish
Rubbish is reclaimed:Data block garbage reclamation and conversion block garbage reclamation. in the garbage reclamation of data block, in order to ensure each data block
Only correspondence one changes page after garbage reclamation, and the flash memory address mapping method of the optimization will be based on conversion page data aggregation side
Method is multiplexed in garbage reclamation, and in address of cache, the promoter of request of data is file system, and in garbage reclamation is rubbish
Rubbish withdrawer, both have similar address of cache process, therefore method can be multiplexed, in the garbage collection procedure of data block
In, when Garbage Collector needs to copy an active page, the mapping of global transformation page is accessed first to obtain current available number
According to the physical address (APN) of page, if data available page is that (non-1), directly writes data available by active page for presence
Page；Otherwise, if the data block of current distribution has run out, using swap block (swap block) as newly assigned data
Block stores active page；When garbage reclamation is completed, the empty data block after erasing is used as new swap block.
Be illustrated in figure 6 the example of data block garbage reclamation, have in the recovered data block chosen 4 valid data pages (Q,
B, D, E), when active page Q is copied, method navigates to first corresponding GTD items, and it is 68 to obtain APN, therefore, Q can be direct
In copying the data page 68 of data block 23 to；After copy, APN is updated to 69 from 68.In the same manner, for data B can also be copied to
In data page 69.Now, data block 23 has write full, so APN is set to 1.When next number arrives according to copy request D,
Distribution swap block gives GTD items, therefore, D and E is write in swap block, and APN is also updated to next available data in swap block
Page address.Finally, data block 23 will become new swap block after wiping, and be garbage reclamation service next time.To address conversion block
Garbage reclamation, in flash memory safeguard a currently available address conversion page, equivalent to unified write pointer, therefore, change page
To be written sequentially in the conversion block of current address.Triggering rubbish is returned when in flash memory without assignable address conversion block
Receive, when garbage reclamation, reclaiming the effective conversion page in block will copy the available address conversion page of write pointer sensing to.Meanwhile,
If address conversion page is located at caching, directly from the current conversion block of caching write, the read operation to effectively conversion page is reduced
With the conversion web update operation that future, caching was produced.Finally, the displacement of page level address of cache caching is by the conversion page of close temperature
Identical conversion block is write back, the number of active page during garbage reclamation in conversion block is reduced indirectly, so as to reduce conversion page
Renewal expense.
Be illustrated in figure 7 the garbage reclamation of address conversion block, choose the address conversion block of recovery comprising TP0, TP2, TP4 this
3 address conversion pages, this 3 address conversion pages are copied into (TPPN in the conversion block of current address:146~148).Copy procedure
In, if there is caching, then directly from caching write current address conversion block, corresponding GTD also updates simultaneously after copy, with true
Guarantor can navigate to newest address conversion page.
In order to the erasable number of times of equilibrium criterion block extends the durability of flash memory, the erasable of each data block is have recorded in flash memory
Number of times, can safeguard the temperature information of data area in global transformation page map table, record each address conversion page correspondence continuous
The access frequency of logical space, few " cold " block of erasable number of times is selected to the frequent item for accessing when write pointer request distributes, and
Then distribute erasable number of times more " heat " block to what is infrequently accessed；Equally, in garbage reclamation, select erasable number of times less and
The more data block of invalid page carries out erasable as recovery block；In flash memory free time, data can be carried out to hot and cold data block
Exchange with erasable number of times between balance weight.
In force, using the effectiveness of a series of benchmark dataset Simulation Evaluation context of methods. herein by proposition
Method (abbreviation OAT) and a kind of representational need-based page level mapping method (DFTL) have carried out experiment and have compared.In experiment
Using 4 performance metric:Cache hit rate, conversion page operations number, system response time and block erasing times.
Experiment simulation platform framework is illustrated in figure 8, wherein, DiskMon is disc drive data tracker, collects and accesses
The I/O request of data of disk；DiskSim is a ripe disk emulation framework for being widely used in industrial quarters；FlashSim makees
For an extension element of DiskSim, for emulating management method and the basic operation of flash chip.In emulation experiment, this
Experiment realizes the address mapping method of DFTL and this paper in FlashSim, is configured with the nand flash memory storage system of a 32GB
System.Impact of the experiment using actual I/O request of data research different address mapping method to performance.In experiment, using a series of
Benchmark dataset Simulation Evaluation context of methods, it was demonstrated that text method can substantially reduce conversion page operations and improve systematicness
Energy.
Claims (3)
1. a kind of flash memory address mapping method of optimization, in need-based page level address of cache DFTL method, ties up in internal memory
A global transformation page map table GTD has been protected, meanwhile, address of cache caching CMT, is changed in page with being buffered in used in internal memory
The address of cache item for frequently accessing, it is characterised in that：The data cell of caching is whole address conversion page；
The flash memory address mapping method of the optimization is using LRU LRU as putting that page level address of cache is cached
Strategy is changed, wherein, the update times for changing page are also one of foundation of selection displacement, if certain conversion page is in the buffer not never
It is updated, it will go out caching by preferential substitution, using initial address SLA of the corresponding address conversion page of displacement item in caching
With global transformation page map table GTD, to position flash memory in actual storage conversion page address, perform replacement operator；
Methods described employs the data method for congregating based on conversion page：Data write is made with the corresponding conversion page of its logical address
To instruct, logical address will be written into identical data block corresponding to the data of same conversion page；
In order to realize data method for congregating, the flash memory address mapping method of the optimization continues to extend global transformation page map table,
Each item in table saves the physical address APN of data available page, wherein, physical address represents this and not yet distributes for 1
Data block, meanwhile, using all of empty data block in empty block pond FBP record flash memories, when there is request of data, the empty number of distribution according to need
Give global transformation page map table according to block, in garbage reclamation, it is erasable after empty block be recovered to sky block pond；
In the flash memory starting stage, there is free data block to belong to sky block pond, each data available page ground in global transformation page map table
Location is all unallocated state, when there is write data requests, according to computational methods mentioned above global transformation page map table is positioned
Item, if the APN in item is 1, directly write data into corresponding data page, subsequently update APN to be distributed data
Next data available page in block, if data block is full, by the address 1 is set to；Otherwise, if the conversion page not yet distributes
Data block, checks in empty block pond and whether there is available empty data block, and the 1st data page is distributed according to need and recorded if existing
Physical address otherwise calls garbage reclamation to obtain new empty data block as APN.
2. the flash memory address mapping method of a kind of optimization according to claim 1, it is characterised in that：The flash memory of the optimization
Address mapping method will be multiplexed in garbage reclamation, in the garbage collection procedure of data block based on conversion page data method for congregating
In, when Garbage Collector needs to copy an active page, the mapping of global transformation page is accessed first to obtain current available number
According to the physical address APN of page, if data available page is exist, directly active page is write into data available page；Otherwise, such as
The data block of the current distribution of fruit has run out, then store active page using swap block as newly assigned data block；When rubbish is returned
When harvesting into, the empty data block after erasing is used as new swap block.
3. the flash memory address mapping method of a kind of optimization according to claim 2, it is characterised in that：Select erasable number of times compared with
Less and the more data block of invalid page as reclaim block carry out it is erasable；In flash memory free time, line number is entered to hot and cold data block
According to exchange with erasable number of times between balance weight.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201410488749.5A CN104268094B (en) | 2014-09-23 | 2014-09-23 | Optimized flash memory address mapping method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201410488749.5A CN104268094B (en) | 2014-09-23 | 2014-09-23 | Optimized flash memory address mapping method |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN104268094A CN104268094A (en) | 2015-01-07 |
| CN104268094B true CN104268094B (en) | 2017-05-03 |
Family
ID=52159617
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201410488749.5A Active CN104268094B (en) | 2014-09-23 | 2014-09-23 | Optimized flash memory address mapping method |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN104268094B (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109308273A (en) * | 2017-07-26 | 2019-02-05 | 北京兆易创新科技股份有限公司 | Flash controller, the adjusting method of flash controller function and equipment |
Families Citing this family (35)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104636285B (en) * | 2015-02-03 | 2016-03-23 | 北京麓柏科技有限公司 | A kind of flash-memory storage system and read-write thereof, delet method |
| CN106326146B (en) * | 2015-06-29 | 2019-05-14 | 上海华虹集成电路有限责任公司 | Check the method whether cache hits |
| CN105005510B (en) * | 2015-07-02 | 2018-07-17 | 西安交通大学 | Error correction protection architecture and method applied to solid state disk resistance-variable storing device caching |
| CN105975215B (en) * | 2016-05-25 | 2019-03-08 | 深圳大学 | A kind of stacked tile type magnetic substance storage translation layer mapping table management method based on Ondemand algorithm |
| CN106096025A (en) * | 2016-06-24 | 2016-11-09 | 北京保程保险公估有限公司 | Motor vehicles maintenance program assessment system and method |
| CN106210037A (en) * | 2016-07-08 | 2016-12-07 | 重庆市农业科学院 | Interactive Management System of Crop Production andIts based on WEB and method thereof |
| CN106445832A (en) * | 2016-09-06 | 2017-02-22 | 深圳市先天海量信息技术有限公司 | Address mapping method and apparatus for flash storage system |
| CN106815152B (en) * | 2016-12-27 | 2019-05-31 | 华中科技大学 | A method of optimization page grade flash translation layer (FTL) |
| CN115129618A (en) * | 2017-04-17 | 2022-09-30 | 伊姆西Ip控股有限责任公司 | Method and apparatus for optimizing data caching |
| CN107256196A (en) * | 2017-06-13 | 2017-10-17 | 北京中航通用科技有限公司 | The caching system and method for support zero-copy based on flash array |
| CN107368436B (en) * | 2017-06-29 | 2020-08-18 | 西安交通大学 | Flash memory cold and hot data separated storage method combined with address mapping table |
| US10437734B2 (en) * | 2017-08-31 | 2019-10-08 | Micron Technology, Inc. | Memory constrained translation table management |
| TWI659304B (en) * | 2017-10-20 | 2019-05-11 | 慧榮科技股份有限公司 | Method for accessing flash memory module and associated flash memory controller and electronic device |
| US10884947B2 (en) * | 2017-11-17 | 2021-01-05 | SK Hynix Inc. | Methods and memory systems for address mapping |
| CN109840219B (en) * | 2017-11-29 | 2024-04-05 | 北京忆恒创源科技股份有限公司 | Address translation system and method for mass solid state storage device |
| CN108153682B (en) * | 2017-12-12 | 2020-10-27 | 西安交通大学 | Method for mapping addresses of flash translation layer by utilizing internal parallelism of flash memory |
| CN109960667B (en) * | 2017-12-14 | 2023-09-15 | 北京忆恒创源科技股份有限公司 | Address translation method and device for large-capacity solid-state storage device |
| CN108089993A (en) * | 2017-12-29 | 2018-05-29 | 苏州大学 | Multiple field memory location nand flash memory, critical data storage method and rubbish recovering method |
| CN108197040A (en) * | 2018-01-12 | 2018-06-22 | 江苏华存电子科技有限公司 | A kind of provider location reflects the high-effect method of logical image position |
| CN108228479B (en) * | 2018-01-29 | 2021-04-30 | 深圳市泰比特科技有限公司 | Embedded FLASH data storage method and system |
| CN108304145A (en) * | 2018-01-30 | 2018-07-20 | 国科美国研究实验室 | The rubbish recovering method of data container device |
| CN108491335B (en) * | 2018-03-30 | 2020-12-29 | 深圳忆联信息系统有限公司 | Method, device, equipment and medium for processing mapping table item |
| CN109144894B (en) * | 2018-08-01 | 2023-04-07 | 浙江大学 | Memory access mode protection method based on data redundancy |
| KR20200031924A (en) * | 2018-09-17 | 2020-03-25 | 삼성전자주식회사 | Memory controller, method of operating the memory controller and storage device comprising memory controller |
| KR102694952B1 (en) * | 2018-09-20 | 2024-08-14 | 에스케이하이닉스 주식회사 | Memory system and operating method thereof |
| CN109739780A (en) * | 2018-11-20 | 2019-05-10 | 北京航空航天大学 | Dynamic secondary based on the mapping of page grade caches flash translation layer (FTL) address mapping method |
| CN110262982A (en) * | 2019-05-05 | 2019-09-20 | 杭州电子科技大学 | A kind of method of solid state hard disk address of cache |
| CN111273860B (en) * | 2020-01-15 | 2022-07-08 | 华东师范大学 | Distributed memory management method based on network and page granularity management |
| CN112764685B (en) * | 2021-01-26 | 2022-07-15 | 华中科技大学 | Method and device for eliminating repeated data writing of pre-written log in solid-state disk |
| CN113076267B (en) * | 2021-04-29 | 2023-05-26 | 华侨大学 | Address conversion method and data storage device based on hot spot aggregation |
| CN113419678B (en) * | 2021-06-18 | 2024-09-06 | 上海盈方微电子有限公司 | Storage management method for embedded system |
| CN114676072A (en) * | 2022-05-25 | 2022-06-28 | 阿里巴巴（中国）有限公司 | Data processing method and device |
| CN115952110B (en) * | 2023-03-09 | 2023-06-06 | 浪潮电子信息产业股份有限公司 | Data caching method, device, equipment and computer readable storage medium |
| CN117724992B (en) * | 2024-02-09 | 2024-05-28 | 深圳鲲云信息科技有限公司 | Method for accessing memory, data storage architecture and computing device |
| CN118170327B (en) * | 2024-05-14 | 2024-09-13 | 苏州元脑智能科技有限公司 | Solid state disk address mapping method, device and product |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102981963A (en) * | 2012-10-30 | 2013-03-20 | 华中科技大学 | Implementation method for flash translation layer of solid-state disc |
| CN103077119A (en) * | 2012-12-31 | 2013-05-01 | 记忆科技(深圳)有限公司 | Data processing system and method |
| CN103425600A (en) * | 2013-08-23 | 2013-12-04 | 中国人民解放军国防科学技术大学 | Address mapping method for flash translation layer of solid state drive |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8219776B2 (en) * | 2009-09-23 | 2012-07-10 | Lsi Corporation | Logical-to-physical address translation for solid state disks |
-
2014
- 2014-09-23 CN CN201410488749.5A patent/CN104268094B/en active Active
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102981963A (en) * | 2012-10-30 | 2013-03-20 | 华中科技大学 | Implementation method for flash translation layer of solid-state disc |
| CN103077119A (en) * | 2012-12-31 | 2013-05-01 | 记忆科技(深圳)有限公司 | Data processing system and method |
| CN103425600A (en) * | 2013-08-23 | 2013-12-04 | 中国人民解放军国防科学技术大学 | Address mapping method for flash translation layer of solid state drive |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109308273A (en) * | 2017-07-26 | 2019-02-05 | 北京兆易创新科技股份有限公司 | Flash controller, the adjusting method of flash controller function and equipment |
| CN109308273B (en) * | 2017-07-26 | 2020-11-20 | 北京兆易创新科技股份有限公司 | Flash memory controller, and method and device for adjusting functions of flash memory controller |
Also Published As
| Publication number | Publication date |
|---|---|
| CN104268094A (en) | 2015-01-07 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN104268094B (en) | Optimized flash memory address mapping method | |
| CN102981963B (en) | A kind of implementation method of flash translation layer (FTL) of solid-state disk | |
| Chung et al. | A survey of flash translation layer | |
| CN101673245B (en) | Comprise signal conditioning package and the storage management method of memory management unit | |
| US10387329B2 (en) | Profiling cache replacement | |
| EP2455865A1 (en) | Memory management device | |
| CN104102591A (en) | Computer subsystem and method for implementing flash translation layer in computer subsystem | |
| CN106815152B (en) | A method of optimization page grade flash translation layer (FTL) | |
| CN103019958A (en) | Method for managing data in solid state memory through data attribute | |
| US10740251B2 (en) | Hybrid drive translation layer | |
| CN110413537B (en) | Flash translation layer facing hybrid solid state disk and conversion method | |
| CN103425600A (en) | Address mapping method for flash translation layer of solid state drive | |
| CN110888600B (en) | Buffer area management method for NAND flash memory | |
| CN111580754B (en) | Write-friendly flash memory solid-state disk cache management method | |
| CN108845957A (en) | It is a kind of to replace and the adaptive buffer management method of write-back | |
| Kang et al. | CLOCK-DNV: A write buffer algorithm for flash storage devices of consumer electronics | |
| Park et al. | A workload-aware adaptive hybrid flash translation layer with an efficient caching strategy | |
| CN113253926A (en) | Memory internal index construction method for improving query and memory performance of novel memory | |
| CN105335220A (en) | Transaction recovery method and apparatus for storage device | |
| CN102521161B (en) | Data caching method, device and server | |
| Park et al. | A dynamic switching flash translation layer based on page-level mapping | |
| CN104156324A (en) | Program run method for embedded system | |
| CN104156178A (en) | Data access method for embedded terminal | |
| Pratibha et al. | Efficient flash translation layer for flash memory | |
| Lin et al. | Flash-aware linux swap system for portable consumer electronics |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |