Call for Paper - May 2023 Edition
IJCA solicits original research papers for the May 2023 Edition. Last date of manuscript submission is April 20, 2023. Read More

Sharing and Hit based Prioritizing Replacement Algorithm for Multi-Threaded Applications

Print
PDF
International Journal of Computer Applications
© 2014 by IJCA Journal
Volume 90 - Number 12
Year of Publication: 2014
Authors:
Muthukumar S
Jawahar P. K
10.5120/15776-4557

Muthukumar S and Jawahar P.k. Article: Sharing and Hit based Prioritizing Replacement Algorithm for Multi-Threaded Applications. International Journal of Computer Applications 90(12):34-38, March 2014. Full text available. BibTeX

@article{key:article,
	author = {Muthukumar S and Jawahar P.k},
	title = {Article: Sharing and Hit based Prioritizing Replacement Algorithm for Multi-Threaded Applications},
	journal = {International Journal of Computer Applications},
	year = {2014},
	volume = {90},
	number = {12},
	pages = {34-38},
	month = {March},
	note = {Full text available}
}

Abstract

Cache replacement techniques like LRU, MRU etc. that are currently being deployed across multi-core architecture platforms, try to classify elements purely based on the number of hits they receive during their stay in the cache. In multi-threaded applications data can be shared by multiple threads (which might run on the same core or across different cores). Such data needs to be given more priority when compared to private data because miss on those data items may stall the functioning of multiple threads resulting in performance bottleneck. Since the traditional algorithms mentioned above do not possess this additional capability, they might lead to sub-optimal performance for most of the current multi-threaded applications. To address this limitation, our paper proposes a Sharing and Hit Based Prioritizing (SHP) replacement strategy that takes the sharing status of the data elements into consideration while making replacement decisions. Every cache element is associated with a 'Sharing Degree' which indicates the extent to which the element is shared based on the number of threads that try to access that element. There are four degrees of sharing namely – Not shared (or private), lightly shared, heavily shared and very heavily shared. Combining the sharing degree along with the number of hits received by the element, we embark on a priority based on which the replacement decisions are made. Evaluation results obtained using multi-threaded workloads derived from the PARSEC benchmark suite shows an average improvement of 4% to 5% in the overall hit rate when compared to LRU algorithm.

References

  • John L. Henessey, David A. Patterson. 2006. Computer Architecture: A Quantitative Approach, Fourth Edition, Elsevier Publications.
  • Aamer Jaleel, William Hasenplaugh, Moinuddin Qureshi, Julien Sebot, Simon Steely, Joel Emer, "Adaptive Insertion Policies for Managing Shared Caches", ACM Parallel Architectures and Compilation Techniques (PACT), Oct. 2008, p. 208-219.
  • Livio Soares, David Tam, Michael Stumm, "Reducing the Harmful Effects of Last-Level Cache Polluters with an OS-level, Software-Only Pollute Buffer", 41st Annual IEEE/ACM International Symposium on Microarchitecture, 2008, p. 258-269.
  • Mazen Kharbutli, Yan Solihin, "Counter Based Cache Replacement and Bypassing Algorithms", IEEE Transactions on Computers, Vol. 57, Issue. 4, April 2008, p. 433-447.
  • Carole-Jean Wu, Margaret Martonosi, "Adaptive Timekeeping Replacement: Fine-Grained Capacity Management for Shared CMP Caches", ACM Transactions on Architecture and Code Optimization, Vol. 8, No. 1, Article 3, April 2011.
  • Shekhar Srikantaiah, Mahmut Kandemir, Mary Jane Irwin, "Adaptive Set Pinning: Managing Shared Caches in Chip Multiprocessors", ACM Architectural Support for Programming Languages and Operating Systems (ASPLOS), Vol. 36, Issue. 1, March 2008, p. 135-144.
  • Konstantinos Nikas. Matthew Horsnell. Jim Garside. 2008. An Adaptive Bloom Filter Cache Partitioning Scheme for Multi-Core Architectures. In Proceedings of the IEEE International Conference on Embedded Computer Systems Architectures Modeling and Simulation, p. 25-32.
  • Mainak Chaudhuri, Jayesh Gaur, Nithiyanandan Bashyam, Srinivas Subramoney, Joseph Nuzman, "Introducing Hierarchy-Awareness in Replacement and Bypass Algorithms for Last-Level Caches", ACM Parallel Architectures and Compilation Techniques (PACT), Sep. 2012, p. 293-304.
  • Fazal Hameed. Bauer L. and Henkel J. 2012. Dynamic Cache Management in Multi-Core Architectures through Runtime Adaptation. In Proceedings of Design Automation & Test in Europe Conference & Exhibition (DATE), p. 485-490.
  • Miao Zhou, Yu Du, Bruce Chilers, Rami Melham, Daniel Mosse, "Writeback-Aware Partitioning and Replacement for Last-Level Caches in Phase Change Main Memory Systems", ACM Transactions on Architecture and Code Optimization, Vol. 8, No. 4, Article 53, Jan. 2012.
  • Haiming Liu, Michael Ferdman, Jaehyuk Huh, Doug Burger, "Cache Bursts: A New Approach for Eliminating Dead Blocks and Increasing Cache Efficiency", 41st Annual IEEE/ACM International Symposium on Microarchitecture, Vol. 1, Issue. 12, 2008, p. 222-233.
  • N. Binkert et al. "The gem5 simulator", SIGARCH Computer. Architecture New, Vol. 39, Issue. 2, May 2011, p. 1-7.
  • Christian Bienia, Sanjeev Kumar, Jaswinder Pal Singh, Kai Li, "The PARSEC Benchmark Suite: Characterization and Architectural Implications", Princeton University Technical Report, TR-811-08, Jan. 2008.
  • M. Gebhart et al. , "Running PARSEC 2. 1 on M5", University of Texas at Austin, Department of Computer Science, Technical Report, TR-09-32, Oct. 2009.