Team 5

From OpenSSDWiki
Jump to: navigation, search

Contents

Project Information

  • Project title: KAST
  • Team members: Kwon cho rok(kjjang88@naver.com), Cho hyeon gyu(cho42me@gmail.com)

Goals

Make the basic KAST scheme and evaluate speed by compareing with other FTL

Motivation

We make a Log block FTL for project #1. Wish to compare a performance with Log block FTL and KAST.

Design and Implementation

Overall architecture

• To minimize the associativities of log blocks, the write requests on the different LBNs are distributed among different log blocks.

• Each log block is enforced to be associated to only the K number of data blocks at maximum. So, we can guarantee that k(L) ≤ K. By adjusting the value of K, the worstcase log block merge time is controlled.

• There are multiple SLBs unlike the FAST scheme which has only one SLB. However, there is the maximum number of SLBs. The SLB can be changed into a random log block (RLB) if there is no subsequent sequential write request.

CaseofLBM.jpg

Main data structures

Data Block Area

● This area is for data block address. Data block has to know hash value. This value is log lpn which is linked with data block.


Free Block Area

● This area is for free block address. Free block is just one. It is used when merge fuction is occured.


Log Block Area

● This area is for log block address. Log block has to know data block lpn which is linked with itself. If k_cnt is larger, this data is lager too. So, we can't store this data in SRAM. Therefore it is stored in DRAM.


Empty Block Area

● This area is remain area. When error message of run time bad block is checked, we can allocate new block in this area.

Handling writes

Basic Write

● Initially all log blocks are empty. When ftl_write is called at this time, log block need to be allocated with a zero offset through assign_write_page().

● When some log blocks are occupied and others are free, we allocate free log block in order to write new data block which is not linked with log block.

● If all log blocks are linked with at least one data block, new data block should be allocated any log block which is linked with the lowest data block by log_select().

● If all log blocks are allocated K_cnt data blocks and receive new data block write, all log blocks need to merge and return one log block for new data block write.


Padding

● Padding occurs when a log block is SLB state. When the log block is SLB state and write page number is not sequential, padding will be process. If data satisfy the pad_cnt and is valid, data tranfer into the log_block. In this case, log_block is not need to be modify state SLB to RLB.

Handling reads

● When ftl_read is called, get_vpn() looks for where is data stored.

● A data must be written to log block first, so ftl_read cause the problem when read the data in data block which does not have a data. So lbn needs to know the address where the real data is located. This information is written to spare area of data block. (We use hash in shashtbl.c.)

Check run time bad block when block erase

● Nand erase is occured when merge is executed. One of run time bad block is occured when block erase is executed. So, we check run time bad block at this time. We erase only log block and free block. (data block is not erase because of using page swap between free block and data block) Therefore we just check block state whether is log block or free block. If log block is erased, we allocate new log block in emtpy block area. And if free block is erased, we allocate new free block in emtpy block area.

Other information

What was most difficult to implement?

● The most difficult part to imblement is address such as mapping lba, calculate lpn, find vpn, set vpn and swap vpn and so on.


What is changed compared to the original paper?

● Our purpose is making same KAST in paper. So there is nothing to different.


Describe other miscellaneous information..

● We write log block first. And when merge is occured, we transfer log block to data block. So, state of data blocks is invalid until merge.

● When merge is occured, we need to bring all data block which is linked with log block. (maxium data block is K_cnt) So, log block have to memrize all linked data blocks.

Evaluation

Workloads

● KAST compares with other FTL(BAST) by bench mark.

● Use Web32G_NTFS.diskmon by trace.c

● Merge count of KAST compares with merge count of BAST.

Evaluation methodology

● Test KAST which has other K_cnt(1, 2, 4, 8, 16, 32) using Web32G_NTFS

● Test KAST which has other p_cnt(1, 2, 4, 8, 16, 32) using Web32G_NTFS

● Test KAST compare with other FTL(BAST) using Web32G_NTFS

● Test environment

CPU : Intel(R) Pentium(R) Dual CPU E2180 @ 2.00GHz

RAM : 2.98GB

OS  : Ubuntu 10.04LTS

(Use PC in room #400202 semiconductor building in SKKU)

Results

TEST 1.

Web32g elapsed time.bmp

● X-axis is k_cnt, Y-axis is time(s).

● Test KAST using Web32G_NTFS. SSD is 8GB. Data block is 256. Log block is 7(3% of data block). Padding count is 8.


TEST 2.

Padding count.bmp

● X-axis is k_cnt(1, 4, 16), Y-axis is time(s).

● Test KAST using Web32G_NTFS. SSD is 8GB. Data block is 256. Log block is 7(3% of data block). Padding count is 8.


TEST 3.

Block erase count.bmp

● X-axis is BAST, KAST(k_cnt is 4 and 16), Y-axis is block erase count.

● Test KAST using Web32G_NTFS. SSD is 8GB. Data block is 256. Log block is 7(3% of data block). Padding count is 8.

● Test BAST using Web32G_NTFS. SSD is 8GB. Data block is 256. Log block is 7(3% of data block).


TEST 4.

Log block utility.bmp

● X-axis BAST, KAST(k_cnt is 4 and 16), Y-axis is log block utility(%).

● Test KAST using Web32G_NTFS. SSD is 8GB. Data block is 256. Log block is 7(3% of data block). Padding count is 8.

● Test BAST using Web32G_NTFS. SSD is 8GB. Data block is 256. Log block is 7(3% of data block).


TEST 5.

Page copy count.bmp

● X-axis BAST, KAST(k_cnt is 4 and 16), Y-axis is page copy count.

● Test KAST using Web32G_NTFS. SSD is 8GB. Data block is 256. Log block is 7(3% of data block). Padding count is 8.

● Test BAST using Web32G_NTFS. SSD is 8GB. Data block is 256. Log block is 7(3% of data block).

Conclusion

● Higher k_cnt, we can get high speed when test KAST using Web32G_NTFS. However, saturation after K_cnt 16. High k_cnt means that we can use many pages in log block before merge. It brings higher log block utility.


● Higer k_cnt, hihger log block utility. we guess that log block utility is 100% when the value(k_cnt * number of log block) approaches almost 40% of number of data block.


● We can get lower block erase counts and page copy counts of KAST than those of BAST.


● We can't get property result about padding count test. In our test, work load is not appropriately test about the change of padding counts.

References

• “KAST: K-Associative Sector Translation for NAND Flash Memory in Real-Time Systems,” DATE’09





Whos here now:   Members 0   Guests 1   Bots & Crawlers 0
 
Personal tools