Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


AnalysisOfGCAlgorithmsForNVM.pdf (1.84 MB)

ETD Abstract Container

Abstract Header

Analysis of Garbage Collector Algorithms in Non-Volatile Memory Devices

Mahadevan Muralidharan, Ananth
http://orcid.org/0000-0001-8541-0436
http://rave.ohiolink.edu/etdc/view?acc_num=osu1365811711

Abstract Details

2013, Master of Science, Ohio State University, Computer Science and Engineering.
Non-volatile memory devices or flash, even with many advantages, still have a few problems such as the inability to update data in place. This necessitates the need for a garbage collector (GC) that can collect active data and create space by erasing flash blocks. However this is a very costly operation that increases the write latency thereby lowering the efficiency of the flash device. The frequency at which the GC is invoked by the underlying file system depends on the data’s traffic pattern as well as the fullness of the device. It is therefore important to study different GC algorithms for different traffic patterns and at varying fullness levels in order to find the most efficient one for a particular situation. In this report we study the efficiency of byte address non-volatile memory devices (such as NOR), under varying traffic patterns. We study the algorithms using simulations coded in Matlab. A simulator for the flash file system as well as the GC algorithms and various applications traffic was developed and used for the study. We compare and contrast the efficiency and the time taken for the GCs at utilization levels ranging from 2% to 98%. We also model some of the algorithms analytically and find that our analytical results match our simulations. The performance results for five different GC algorithms for flash devices for three traffic/access patterns are presented in this report. The access patterns include long-tailed, uniform and bimodal distributions. The algorithms studied are a round-robin style first in first out (FIFE), a greedy least active clean (LAC), 3-Generation (3-Gen) GC, N-Generation (N-Gen) GC (a generalized generation algorithm) and Eta-N-Generation (Eta-N-Gen) GC (a variation on N-Gen). The results indicate that round-robin style GC algorithm (FIFE) and greedy algorithm (LAC) perform better in most of the scenarios than generational algorithms. This is counter-intuitive to the existing norms. LAC slightly underperforms the FIFE under heavy flash utilization. For long-tailed traffic – the canonical use case for generational algorithms – FIFE and LAC still perform better than generational algorithms. The reason is that, it is non-trivial to configure a generational algorithm to get the optimum performance for a particular traffic pattern. To optimize performance, the radio of the size of subsequent generations should be the same as ratio between cold data and the rest of the data. Since in most application cases we do not know this a priori, static optimal configuration of generational algorithms is impossible. However an adaptive algorithm which changes allocations between generations on the fly could achieve better efficiency. Further we find that for better efficiency, at low levels of utilization it is important to isolate “cold’ data well, but at higher utilization identifying and handling hot data (i.e., never move the hot data) is important. Results from our study suggest that FIFE might work well for most of the application scenarios.
Rajiv Ramnath (Advisor)
Jayashree Ramanathan (Committee Member)
72 p.
Computer Engineering; Computer Science
Garbage collection; Non-volatile memory device; Solid state device; statistical analysis; Uniform distribution; Pareto distribution; Bimodal distribution; Generational garbage collection; Greedy garbage collection; efficient garbage collection;

Recommended Citations

Citations

  • Mahadevan Muralidharan, A. (2013). Analysis of Garbage Collector Algorithms in Non-Volatile Memory Devices [Master's thesis, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1365811711

    APA Style (7th edition)

  • Mahadevan Muralidharan, Ananth. Analysis of Garbage Collector Algorithms in Non-Volatile Memory Devices. 2013. Ohio State University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1365811711.

    MLA Style (8th edition)

  • Mahadevan Muralidharan, Ananth. "Analysis of Garbage Collector Algorithms in Non-Volatile Memory Devices." Master's thesis, Ohio State University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=osu1365811711

    Chicago Manual of Style (17th edition)

osu1365811711
1,610
© 2013, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.