Team 403 : FAST

From OpenSSDWiki
Jump to: navigation, search

Please copy this page to make your own final report...


Project Information

  • Project title: "FAST - Hash and Linear search"
  • Team members: "Hyunjong Yoo, Kyeorae Lee"


  • Implement FAST with hash and linear search algorithms.
  • Compare processing speed between hash and linear search on FAST FTL.


When read or write operations happen, FTL should find correct pages.

Normally hash is faster than linear search. But, due to limited capacity of SRAM, we should use DRAM for hash algorithm.

As you know, processing speed of DRAM is slower than that of SRAM. So we think linear search is able to be faster than hash if we use DRAM in search algorithm.

  Design and Implementation

  Overall architecture

The architecture of FAST is analogous to that of BAST.

One important difference is that log blocks in FAST are divided into two areas

  : one log block is used for sequential writes and the other blocks for random writes.

FAST keeps a dedicated log block for sequential writes and maintains separate sector-level mapping tables for the above two types of log blocks.

A more complex mapping table is needed for the RW log blocks. This table records which sectors are written

and the offsets of the RW log blocks. In theory, a sector can be placed on any RW log block.

    Main data structures


 Handling writes

1.jpg Figure 1. Processing write operations in the FAST scheme.

- The log blocks in FAST are divided into two groups: the SW and the RW log blocks.

 Handling reads

Yields a small overhead in sector read operations, compared to BAST.

For every sector read operation in FAST, should check whether the most recent version of the sector exists in the log blocks.

Check is accomplished by scanning the sector-level mapping table in SRAM, not by scanning the log blocks.

Thus, for every read operation against sectors in log blocks, FAST yields the overhead for scanning the sectorlevel mapping table in SRAM.


  Testing Environment

  • SSD Jasmine OpenSSD Platform Total 8 banks.
  • 2048 + 28 blocks per Bank,128 Pages per Block,64 Sectors per Page.
  • OS : Windows 7 Ultimate K 64bit.
  • CPU : Inter(R) Core(TM)2 Quad CPU Q9400 @ 2.66GHz 2.67GHz 4GB RAM.

Failure to achieve 

  • Binery search : We shloud not sort the data of memory. That means biaery search is useless.
  • Hash optimizing : We tried to optimize hashing. But, it doesn't faster than original hashing. To make matters worse, it also dissipated the memory.

Evaluation methodology

  • Testcase : Refered to the testcase of project 1.
  • Reading and writing speed are measured by IOmeter.


  • Successfully achieved all of 7 tests.
  • When random writing, hash and linear search result in very similar performances.

3.png Figure 2. Testcase delay


We have learned linear search is as fast as hashing. But, linear search dissipated lots of memory. Finally, we concluded using the hash search when dealing with mass storage disk.


  • S.-W. Lee, D.-J. Park, T.-S. Chung, D.-H. Park, .-J. Song, "A Log-buffer based Flash Translation Layer using Fully-Associative Sector Translation," ACM Transactions on Embedded Computing Systems, Vol. 6, No. 3, 2007.

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