{"id":{"repo_id":"ohiolink","oai_identifier":"oai:etd.ohiolink.edu:osu1365811711"},"canonical_url":"https://search.dev.ndltd.org/etd/ohiolink/oai:etd.ohiolink.edu:osu1365811711","repository":{"repo_id":"ohiolink","name":"OhioLINK","base_url":"https://etd.ohiolink.edu/acprod/odb_etd/ws/oai/oai"},"display":{"title":"Analysis of Garbage Collector Algorithms in Non-Volatile Memory Devices","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Mahadevan Muralidharan, Ananth"],"institution":"The Ohio State University","degree_name":"Master of Science","degree_level":"masters","degree_discipline":"Computer Science and Engineering","degree_department":null,"school":null,"contributors":["Ramnath, Rajiv"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-08-09","date_published":"2013-08-09","updated_at":"2026-07-24T03:37:31Z","subjects":["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"],"languages":["English"],"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."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://rave.ohiolink.edu/etdc/view?acc_num=osu1365811711","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Ramnath, Rajiv"]},{"key":"dc:creator","label":"Author","values":["Mahadevan Muralidharan, Ananth"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2013-08-09"]},{"key":"dc:publisher","label":"Institution","values":["The Ohio State University / OhioLINK"]},{"key":"dc:type","label":"Dc Type","values":["Electronic Thesis or Dissertation"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science and Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["The Ohio State University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["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"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://rave.ohiolink.edu/etdc/view?acc_num=osu1365811711"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf","p.72","1.84 MB"]},{"key":"dc:title","label":"Title","values":["Analysis of Garbage Collector Algorithms in Non-Volatile Memory Devices"]}]}],"canonical_facts":{"dc:contributor":["Ramnath, Rajiv"],"dc:creator":["Mahadevan Muralidharan, Ananth"],"dc:date":["2013-08-09"],"dc:description":["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."],"dc:format":["application/pdf","p.72","1.84 MB"],"dc:identifier":["http://rave.ohiolink.edu/etdc/view?acc_num=osu1365811711"],"dc:language":["English"],"dc:publisher":["The Ohio State University / OhioLINK"],"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."],"dc:subject":["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"],"dc:title":["Analysis of Garbage Collector Algorithms in Non-Volatile Memory Devices"],"dc:type":["Electronic Thesis or Dissertation"],"thesis:degree_discipline":["Computer Science and Engineering"],"thesis:degree_level":["masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["The Ohio State University"]},"updated_at":"2026-07-24T03:37:31Z"}