Analysis of Garbage Collector Algorithms in Non-Volatile Memory Devices

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.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Computer Science and Engineering

Grantor dc:publisher

The Ohio State University

Year dc:date

2013

Author dc:creator

• Mahadevan Muralidharan, Ananth

Contributors dc:contributor

• Ramnath, Rajiv

• Computer Science
• Computer Engineering
• 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

Statement dc:rights

• unrestricted
• This thesis or dissertation is protected by copyright: all rights reserved. It may not be copied or redistributed beyond the terms of applicable copyright laws.

Language dc:language

English

Repository record dc:identifier

http://rave.ohiolink.edu/etdc/view?acc_num=osu1365811711

OAI identifier oai:identifier

oai:etd.ohiolink.edu:osu1365811711