A lock-free cache invalidation protocol for the atom system
Authors: 
Hugo Rito, João CachopoAuthors Info & Claims
Pages 111 - 116
Abstract
The Automatic Transaction-Oriented Memoization (ATOM) system is a thread-safe memoization tool specifically designed for multi-threaded object-oriented programs.
Currently, searching the ATOM's memo cache for a hit is still an expensive operation with linear time complexity.
We present a new lock-free cache invalidation protocol for the ATOM that allows multiple threads to concurrently search and invalidate cache entries, resorting to helping from threads to decrease the time spent with cache operations.
Results with the STMBench7 benchmark show that for a read-only workload the new algorithm increases the throughput of the benchmark up to 14-fold and that it scales well up to 48 cores, the maximum number of physical cores available on the machine used for the tests.
References
[1]
J. Cachopo and A. Rito-Silva. Versioned boxes as the basis for memory transactions. Science of Computer Programming, 63 (2): 172--185, 2006.
[2]
R. Guerraoui, M. Kapalka, and J. Vitek. STMBench7: A Benchmark for Software Transactional Memory. ACM SIGOPS Operating Systems Review, 41 (3): 315--324, 2007.
[3]
J. Manson, W. Pugh, and S. Adve. The Java memory model. In Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 378--391. ACM, 2005. ISBN 158113830X.
[4]
D. Michie. Memo functions and machine learning. Nature, 218 (1): 19--22, 1968.
[5]
H. Rito. ATOM: Automatic Transaction-Oriented Memoization, October 2009. Master's thesis, Technical University of Lisbon.
[6]
H. Rito and J. Cachopo. Memoization of methods using software transactional memory to track internal state dependencies. In Proceedings of the 8th International Conference on the Principles and Practice of Programming in Java, pages 89--98. ACM, 2010.
Index Terms
- A lock-free cache invalidation protocol for the atom system
Recommendations
Modeling LRU cache with invalidation
Least Recently Used (LRU) is a very popular caching replacement policy. It is very easy to implement and offers good performance, especially when data requests are temporally correlated, as in the case of web traffic.When the data content can change ...
A cache coherence scheme with fast selective invalidation
Special Issue: Proceedings of the 15th annual international symposium on Computer ArchitectureSoftware-assisted cache coherence enforcement schemes for large multiprocessor systems with shared global memory and interconnection network have gained increasing attention. Proposed software-assisted approaches rely on either indiscriminate ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2011 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 23 October 2011
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
SPLASH '11
Sponsor:
SPLASH '11: Conference on Systems, Programming, and Applications: Software for Humanity
October 23 - 24, 2011
Oregon, Portland, USA
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 63Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 24 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in