Search

Hot data identification in flash memory is of great interest because it significantly affects the garbage collection and wear-leveling performance. Presently, certain hot and cold data classification schemes based on Bloom filters (BFs) have been proposed. Although BFs are efficient in most cases, there is a significant trade-off between false positive rates, which are the result of hash value collisions and memory utilization. In this paper, we suggest a better data categorization mechanism that is based on a hashing technique called Fingerprinting by Random Polynomials with the aim of reducing false positive rates and achieving lower memory consumption compared to the BF-based schemes. We also introduce a new methodology for classifying write requests by linking the definition of hot and cold write requests to the flash memory software layer, the flash translation layer (FTL) characteristics. Our approach improves space utilization by representing each logical block number (lbn) by one counter in the hash table, and achieves an extremely low error rate by choosing the degree of the hash function based on the address space of the flash memory. In addition, we achieved lower false identification rates. We demonstrate the performance using mathematical analysis and trace-driven simulation. [ABSTRACT FROM AUTHOR]

We present a new approach to parallel copying garbage collection on symmetric multiprocessor (SMP) machines appropriate for Java and other object-oriented languages. Parallel, in this setting, means that the collector runs in several parallel threads. Our collector is based on a new idea called delayed allocation, which completely eliminates the fragmentation problem of previous parallel copying collectors while still keeping low synchronization, high efficiency, and simplicity of collection. In addition to this main idea, we also discuss several other ideas such as termination detection, balancing the distribution of work, and dealing with contention during work distribution. [ABSTRACT FROM AUTHOR]

Replication-based incremental garbage collection is one of the more appealing concurrent garbage collection algorithms known today. It allows continuous operation of the application (the mutator) with very short pauses for garbage collection. There is a growing need for such garbage collectors suitable for a multithreaded environments such as the Java Virtual Machine. Furthermore, it is desirable to construct collectors that also work on multiprocessor computers. We begin by pointing out an important, yet subtle point, which arises when implementing the replication-based garbage collector for a multithreaded environment. We first show that a simple and natural implementation of the algorithm may lead to an incorrect behavior of multithreaded applications. We then show that another simple and natural implementation eliminates the problem completely. Thus, the contribution of this part is in stressing this warning to future implementors. Next, we address the effects of the memory coherence model on this algorithm. We show that even when the algorithm is properly implemented with respect to our first observation, a problem might still arise when a multiprocessor system is used. Adopting a naive solution to this problem results in very frequent (and expensive) synchronization. We offer a slight modification to the algorithm which eliminates the problem and requires little synchronization. [ABSTRACT FROM AUTHOR]