마이크로프로세서 - SSD의 FTL을 C++로 구현, 시뮬레이션

1. [20 points] Explain your own FTL. The explanation may include the structure,
algorithm and so on. You may use some example when you explain about the
algorithm.


General structure of FTL
Logical Address
⟷
Physical Address
BLOCK
PAGE
SECTOR
BLOCK
PAGE
SECTOR
1
1
1
1
1
1
2
2
3
3
4
4
2
5
2
5
6
6
7
7
8
8
~
~
128
509
128
509
510
510
511
511
512
512
~
~
256
1
1
264
(256+
Reserved Block)
1
1
2
2
3
3
4
4
2
5
2
5
6
6
7
7
8
8
~
~
128
509
128
509
510
510
511
511
512
512

Basic is that one block has 128 pages of 4 sectors in each page. We only know the Logical address and it does not means the Physical address. So, we input the Physical structure in the “struct.h” and put the Logical Page into Physical page sequentially.

typedef struct {
blk_table_t Blk_Table[NUM_OF_LOGICAL_BLOCK];
phy_blk_table_t Phy_Blk_Table[NUM_OF_TOTAL_BLOCK];
uint count_Freeblock;
}FTL_t;


typedef struct{
uint LPA;// Logical Page Address
uint LBA;// Logical Page Address
uchar state; // 0: Free, 1: Valid, 2: Invalid
}phy_page_t;
typedef struct{
phy_page_t phy_page[PAGE_PER_BLOCK];
uint erase_count;
uint top_page;
uint invalid_page;
uchar is_free;
}phy_blk_table_t;

So far, this is the declare of Physical Address.
And the problem is, to map between Logical Address and Physical Address. As we construct with ‘Page Mapped’ way, real data will stack in Physical Address. In this time, set linkage continually.

void TableRefresh(uint LPA, uint PBA, uint PPA)
{
uint LB_Offset = get_LB_Offset_From_LPA(LPA);
uint LP_Offset = get_LP_Offset_From_LPA(LPA);
ftl->Blk_Table[LB_Offset].page[LP_Offset].PBA = PBA;
ftl->Blk_Table[LB_Offset].page[LP_Offset].PPA = PPA;
ftl->Blk_Table[LB_Offset].page[LP_Offset].state = PAGE_VALID;
ftl->Phy_Blk_Table[PBA].phy_page[PPA].LBA = LB_Offset;
ftl->Phy_Blk_Table[PBA].phy_page[PPA].LPA = LP_Offset;
ftl->Phy_Blk_Table[PBA].phy_page[PPA].state = PAGE_VALID;
}

Linkage process always operate when you write down the data and update exist data.

In the two cases(op read and write) , garbage collection and Reserved block,

(1) FTL Write operation

uint get_LP_Offset_From_LPA(uint LPA)
{
return ( LPA % PAGE_PER_BLOCK );
}
uint get_LB_Offset_From_LPA(uint LPA)
{
return ( LPA / PAGE_PER_BLOCK);
}

uint get_LPA_From_LSA(uint LSA)
{
return (LSA >> SECTOR_PER_PAGE_BIT) % MAX_LPA;
}
uint get_LPA_Offset_From_LSA(uint LSA)
{
return LSA % SECTOR_PER_PAGE;
}

To write data in SSD, we need to calculate LSA to find what block and page is. Using this, FTL Write operation will go on.
FTL Write has two similar condition. Write first and update in SSD, called update and write.
Update has “REGISTER” because of ‘page mapped’ algorism. In one page, sectors are exist but can’t access directly. So, need temporary data storage(REGISTER) to reserve original data.

Data
r
H
d
e
B
t
O

Wanna Insert only ‘r’ at the last Sector in page (124)
SSD(p124)
k
j
g
P


REG
k
j
g
P
⟶
REG
k
j
g
r
⟶
SSD(Reserved)
k
j
g
r

⟶
SSD(124)
Invalid

Here are the codes
char REG[5];
REG[4]='\0'
for (i=0;i<LPA_length;i++)
REG[LPA_offset+i]=data[i];

It is same in FTL Read operation.
Write has no reason to consider SECTOR because first input data takes whole storage so don’t need register in Write operation. But basically, it must have. We don't consider general input so there are no REGISTER in Write.
To write down page per page, we need to calculate how many times we write. So, calculating repeatTime is important.

uint calculate_Loop(uint LSA, uint length)
{
return (((LSA+length-1)/SECTOR_PER_PAGE)-(LSA/SECTOR_PER_PAGE)+1);
}

Above return value means how many pages we need to write down.
And then, how we get a free page that we write?

void get_a_free_page(uint *PBA, uint *PPA)
{
uint i;
uint count;

if (ftl->count_Freeblock<=1)
GarbageCollection();

for(i=0 ; i < NUM_OF_TOTAL_BLOCK ; i++)
if(ftl->Phy_Blk_Table[i].top_page < PAGE_PER_BLOCK)
{
*PBA = i;
*PPA = ftl->Phy_Blk_Table[i].top_page;
count = ftl->Phy_Blk_Table[i].erase_count;
break
}

for( ;i<NUM_OF_TOTAL_BLOCK ;i++)
if (ftl->Phy_Blk_Table[i].erase_count < count)
if(ftl->Phy_Blk_Table[i].top_page < PAGE_PER_BLOCK)
{
*PBA = i;
*PPA = ftl->Phy_Blk_Table[i].top_page;
count = ftl->Phy_Blk_Table[i].erase_count;
}

ftl->count_Freeblock-=(ftl->Phy_Blk_Table[*PBA].is_free == BLOCK_FREE);
}

Check whole Physical Pages until empty page is selected. After that, repeat same thing with some conditions. In this, for wear leveling, select another page that has erase_count less. Result will be selected less erase_count one. After all done, reduce count_Freeblock.
We set GarbageCollection in get_a_free_page to hold large data input. If there are no free block in SSD, do garbage collection and get free page. It has no risk for data length collision.

Next, in Nand_Command, we must set the state of page and block. In program mode, set VALID message in page and block because data is pushed already. and increase top page. In erase mode, set initial values for free block state.




case NAND_PROGRAM:
count_nand_program++;
ftl->Phy_Blk_Table[block].phy_page[page].state=PAGE_VALID;
ftl->Phy_Blk_Table[block].is_free=BLOCK_VALID;
ftl->Phy_Blk_Table[block].top_page++;
FindFilePosition(block, page);
WritePage(data);
break


case NAND_ERASE:
count_nand_erase++;
ftl->count_Freeblock++;
ftl->Phy_Blk_Table[block].is_free = BLOCK_FREE;
ftl->Phy_Blk_Table[block].erase_count++;
ftl->Phy_Blk_Table[block].top_page=0;
ftl->Phy_Blk_Table[block].invalid_page=0;
for(i=0;i<PAGE_PER_BLOCK;i++)
ftl->Phy_Blk_Table[block].phy_page[i].state = PAGE_FREE;
break


(2) FTL Read operation
FTL Read is more short than FTL Write. Basic concept is getting data through LSA in REGISTER and do some modification to find sectors that is really want.
Modification scheme is below.

for(j=LPA_offset;j<(LPA_offset+LPA_length);j++)
data[k++] = ptr[j];
ftl.c

if(operation == 1){
fprintf(result_out, "%s\n",data);
}
Main.c

Modificated data is in data array and it is printed to result.txt in main.

(3) Garbage Collection

As we learned in class, conditions in this operation are important.

if (ftl->count_Freeblock<=1)
GarbageCollection();
In get_a_free_block function


Garbage collection is called by get_a_free_block function so, it always do every time we need to write data. It protect memory overflow( Any length of data can be input ).
Basic operation is below.

void GarbageCollection()
{
uint i;
uint victim_block;
while(1)
{
victim_block = get_Victim_Block();
if (victim_block == NUM_OF_TOTAL_BLOCK+1) break
for(i=0 ; i<PAGE_PER_BLOCK ; i++)
if(ftl->Phy_Blk_Table[victim_block].phy_page[i].state == PAGE_VALID)
move_page(victim_block, i);
else
continue
erase_Block(victim_block);
}
}





How we decide victim block?
Victim block selection is also important. Erase operation cost much so reducing total victim select operation is better. It drive that select block that has much more invaild page is better. Select appropriate victim block and page is in next page.

uint get_Victim_Block(uint goal)
{
int i;
uint count_invalid_page=0, temp;

for(i=0 ; i<NUM_OF_TOTAL_BLOCK ; i++) // 가장 invalidpage수가 최대인 블럭을 고름
if ((ftl->Phy_Blk_Table[i].is_free == BLOCK_VALID) && (ftl->Phy_Blk_Table[i].invalid_page > count_invalid_page))
{
count_invalid_page = ftl->Phy_Blk_Table[i].invalid_page;
temp = i;
}
if ((count_invalid_page < PAGE_PER_BLOCK ) && (ftl->count_Freeblock>0))
temp=NUM_OF_TOTAL_BLOCK+1; //<==특정하게 약속된값 리턴하려고
//Freeblock이 하나이상잇을때 invalidpage가 128개인 것들만 다없앨때까지 garbage수행
return temp;
}

Search what block has the maximum number of invalid page and if there are free block exist, function return appointed value. It pass the garbage collection.
This selected block will be done by garbage collection.

And now, we move valid pages in victim block to somewhere. This work is done by move_page function.

void move_page(uint victim_block, uint victim_page)
{
uint PBA,PPA,LBoffset,LPoffset;

char temp[4]={'0'};

get_a_free_page_garbage(&PBA, &PPA, victim_block);

NAND_Command(NAND_READ, victim_block, victim_page, temp);
NAND_Command(NAND_PROGRAM, PBA, PPA, temp);

LBoffset = ftl->Phy_Blk_Table[victim_block].phy_page[victim_page].LBA;
LPoffset = ftl->Phy_Blk_Table[victim_block].phy_page[victim_page].LPA;
TableRefresh(LPoffset+LBoffset*PAGE_PER_BLOCK,PBA,PPA);
ftl->Phy_Blk_Table[victim_block].phy_page[victim_page].state = PAGE_INVALID;
ftl->Phy_Blk_Table[victim_block].invalid_page++;
}


By get_a_free_page_garbage function, we have destination to move. and then using NAND_Command, save original data in temporary and copy to destination. Other work is also needed. Adjust address to destination and change state invalid at original, valid at destination. TableRefresh( Mapping function ) will help you.

But, how can we get destination??

Set victim block and it is the one we want then, vaild pages in victim block are moved to free page. This free page is selected in block that is free or partially valid. When data move, selecting destination is important. That is in below.

void get_a_free_page_garbage(uint *PBA, uint *PPA, uint block)
{
uint i;
for(i=0;i<NUM_OF_TOTAL_BLOCK;i++) // 일단 Valid한 블럭 중에 옮길곳 찾음
if ((i != block) && (ftl->Phy_Blk_Table[i].is_free == BLOCK_VALID) && (ftl->Phy_Blk_Table[i].top_page < PAGE_PER_BLOCK))
{
*PBA = i;
*PPA = ftl->Phy_Blk_Table[i].top_page;
i=0;
break
}
if (i != 0)
{
for(i=0;i<NUM_OF_TOTAL_BLOCK;i++) // Vailid한 블럭 중 옮길곳이 없을경우 Free한 블럭중에서 찾음
if ((i != block) && (ftl->Phy_Blk_Table[i].top_page < PAGE_PER_BLOCK))
{
*PBA = i;
*PPA = ftl->Phy_Blk_Table[i].top_page;
ftl->count_Freeblock--;
break
}
}
}

At first, decide in used block to find free page. If not found, keep searching in free block and find out what is the free page&block. This process will reduce total amount of erase time. Because more used pages in block can erase more pages at one time.

(4) Number of RESERVED BLOCK

Garbage collection is up to number of Reserved block. So, setting the number of reserved block is what we have to do.

This is the table and graph when the different number of Reserved Block is set.
Using this table, we can find optimized number.
[Performance(1/T) per Cost(N)]
Look above graph, maximum performance is when choose N=8.