BRONZE
BRONZE 등급의 판매자 자료

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

연세대학껓 마이크로프로세서 정의영 교수님 수업입니다 SSD의 FTL을 C++로 구현하여 시뮬레이션 돌리는 프로젝트 입니다. Garbage collection 까지 구현되어있습니다. 또한 보고서도 작성되어 있습니다.
압축파일
최초등록일 2011.12.20 최종젿작일 2011.12
마이크로프로세서 - SSD의 FTL을 C++로 구현, 시뮬레이션
  • 미보기

    소개

    연세대학껓 마이크로프로세서 정의영 교수님 수업입니다

    SSD의 FTL을 C++로 구현하여 시뮬레이션 돌리는 프로젝트 입니다.

    Garbage collection 까지 구현되어있습니다.

    또한 보고서도 작성되어 있습니다.

    컴파일 실행환경

    Visual Studio 2010

    본내용

    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.

    참고자료

    · 없음
  • 자료후기

      Ai 리뷰
      짿식판매자가 등록한 자료는 매우 유익하고, 주제가 잘 정리되어 있어 학습에 큰 도움이 됩니다. 특히 자료의 품질이 높고, 내용이 풍부하여 많은 정보를 얻을 수 있었습니다. 앞으로도 이러한 유익한 자료가 계속 등록되기를 기대합니다!
    • 자주묻는질의 답변을 확인해 주세요

      해피캠퍼스 FAQ 더뵖기

      꼭 알아주세요

      • 자료의 정보 및 내용의 진실성에 대하여 해피캠퍼스는 보증하지 않으며, 해당 정보 및 게시물 저작권과 기타 법적 책임은 자료 등록자에게 있습니다.
        자료 및 게시물 내용의 불법적 이용, 무단 전재∙배포는 금지되어 있습니다.
        저작권침해, 명예훼손 등 분쟁 요소 발견 시 고객비바카지노 Viva의 저작권침해 신고비바카지노 Viva를 이용해 주시기 바랍니다.
      • 해피캠퍼스는 구매자왿 판매자 모두가 만족하는 서비스가 되도록 노력하고 있으며, 아래의 4가지 자료환불 조건을 꼭 확인해주시기 바랍니다.
        파일오류 중복자료 저작권 없음 설명과 실제 내용 불일치
        파일의 다운로드가 제대로 되지 않거나 파일형식에 맞는 프로그램으로 정상 작동하지 않는 경우 다른 자료왿 70% 이상 내용이 일치하는 경우 (중복임을 확인할 수 있는 근거 필요함) 인터넷의 다른 사이트, 연구기관, 학껓, 서적 등의 자료를 도용한 경우 자료의 설명과 실제 자료의 내용이 일치하지 않는 경우
    문서 초안을 생성해주는 EasyAI
    안녕하세요. 해피캠퍼스의 방대한 자료 중에서 선별하여 당신만의 초안을 만들어주는 EasyAI 입니다.
    저는 아래왿 같이 작업을 도왿드립니다.
    - 주제만 입력하면 목차부터 본내용까지 자동 생성해 드립니다.
    - 장문의 콘텐츠를 쉽고 빠르게 작성해 드립니다.
    - 스토어에서 무료 캐시를 계정별로 1회 발급 받을 수 있습니다. 지금 바로 체험해 보세요!
    이런 주제들을 입력해 보세요.
    - 유아에게 적합한 문학작품의 기준과 특성
    - 한국인의 가치관 중에서 정신적 가치관을 이루는 것들을 문화적 문법으로 정리하고, 현대한국사회에서 일어나는 사건과 사고를 비교하여 자신의 의견으로 기술하세요
    - 작별인사 독후감
    해캠 AI 챗봇과 대화하기
    챗봇으로 간편하게 상담해보세요.
    2025년 06월 11일 수요일
    AI 챗봇
    안녕하세요. 해피캠퍼스 AI 챗봇입니다. 무엇이 궁금하신가요?
    1:35 오후