research-article

Cache line reservation: exploring a scheme for cache-friendly object allocation

Authors:

Vijay Sundaresan,

Nikola Grčevski,

Željko ŽilicAuthors Info & Claims

CASCON '09: Proceedings of the 2009 Conference of the Center for Advanced Studies on Collaborative Research

Pages 247 - 260

https://doi.org/10.1145/1723028.1723056

Published: 02 November 2009 Publication History

Abstract

We present a novel idea for object allocation, cache line reservation (CLR), whose goal is to reduce data cache misses. Certain objects are allocated from "reserved" cache lines, so that they don't evict other objects that will be needed later. We discuss what kinds of allocations could benefit from CLR, as well as sources of overhead. Basic prototypes were implemented in the IBM® J9 Java™ virtual machine (JVM) and its Testarossa just-in-time (JIT) compiler. We present preliminary results, which show that CLR can offer a benefit in specialized microbenchmarks, but not yet in SPECjbb2005 and SPECjvm2008. Furthermore, we discuss the limitations of the current implementation and suggest areas for improvement. CLR is not limited to Java applications, and we hope to see it developed for other compilers.

References

[1]

J. L. Hennessy and D. A. Patterson, Computer Architecture, Fourth Edition: A Quantitative Approach, Morgan Kaufmann, 2006.

Digital Library

[2]

J. Kim and Y. Hsu, "Memory system behavior of Java programs: methodology and analysis", Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, Santa Clara, California, United States: ACM, 2000, pp. 264--274.

Digital Library

[3]

H. Inoue, D. Stefanovic, and S. Forrest, "On the prediction of Java object lifetimes", Computers, IEEE Transactions on, vol. 55, 2006, pp. 880--892.

Digital Library

[4]

O. Temam, C. Fricker, and W. Jalby, "Cache interference phenomena", Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, Nashville, Tennessee, United States: ACM, 1994, pp. 261--271.

Digital Library

[5]

T. Sheu, Y. Shieh, and W. Lin, "The selection of optimal cache lines for microprocessor-based controllers", Proceedings of the 23rd annual workshop and symposium on Microprogramming and microarchitecture, Orlando, Florida, United States: IEEE Computer Society Press, 1990, pp. 183--192.

Digital Library

[6]

P. Viana, A. Gordon-Ross, E. Keogh, E. Barros, and F. Vahid, "Configurable cache subsetting for fast cache tuning", Proceedings of the 43rd annual conference on Design automation, San Francisco, CA, USA: ACM, 2006, pp. 695--700.

Digital Library

[7]

A. Janapsatya, A. Ignjatovič, and S. Parameswaran, "Finding optimal L1 cache configuration for embedded systems", Proceedings of the 2006 conference on Asia South Pacific design automation, Yokohama, Japan: IEEE Press, 2006, pp. 796--801.

Digital Library

[8]

J. M. Velasco, D. Atienza, and K. Olcoz, "Exploration of memory hierarchy configurations for efficient garbage collection on highperformance embedded systems", Proceedings of the 19th ACM Great Lakes symposium on VLSI, Boston Area, MA, USA: ACM, 2009, pp. 3--8.

Digital Library

[9]

A. Seznec, "A case for two-way skewed-as-sociative caches", Proceedings of the 20th annual international symposium on Computer architecture, San Diego, California, United States: ACM, 1993, pp. 169--178.

Digital Library

[10]

R. Subramanian, Y. Smaragdakis, and G. H. Loh, "Adaptive Caches: Effective Shaping of Cache Behavior to Workloads", Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, IEEE Computer Society, 2006, pp. 385--396.

Digital Library

[11]

M. Kandemir, J. Ramanujam, J. Irwin, N. Vijaykrishnan, I. Kadayif, and A. Parikh, "Dynamic management of scratch-pad memory space", Proceedings of the 38th conference on Design automation, Las Vegas, Nevada, United States: ACM, 2001, pp. 690--695.

Digital Library

[12]

C. Lebsack and J. Chang, "Using scratchpad to exploit object locality in Java", Computer Design: VLSI in Computers and Processors, 2005. ICCD 2005. Proceedings. 2005 IEEE International Conference on, 2005, pp. 381--386.

Digital Library

[13]

K. F. Chong, C. Y. Ho, and A. S. Fong, "Pretenuring in Java by Object Lifetime and Reference Density Using Scratch-Pad Memory", Parallel, Distributed and Network-Based Processing, 2007. PDP '07. 15th EUROMICRO International Conference on, 2007, pp. 205--212.

Digital Library

[14]

A. H. Hashemi, D. R. Kaeli, and B. Calder, "Efficient procedure mapping using cache line coloring", Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, Las Vegas, Nevada, United States: ACM, 1997, pp. 171--182.

Digital Library

[15]

J. Kalamatianos, A. Khalafi, D. Kaeli, and W. Meleis, "Analysis of temporal-based program behavior for improved instruction cache performance", Computers, IEEE Transactions on, vol. 48, 1999, pp. 168--175.

Digital Library

[16]

D. Genius, "Handling Cross Interferences by Cyclic Cache Line Coloring", Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, IEEE Computer Society, 1998, p. 112.

Digital Library

[17]

D. Callahan, K. Kennedy, and A. Porterfield, "Software prefetching", Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, Santa Clara, California, United States: ACM, 1991, pp. 40--52.

Digital Library

[18]

S. Coleman and K. S. McKinley, "Tile size selection using cache organization and data layout", Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, La Jolla, California, United States: ACM, 1995, pp. 279--290.

Digital Library

[19]

G. Rivera and C. Tseng, "Data transformations for eliminating conflict misses", Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, Montreal, Quebec, Canada: ACM, 1998, pp. 38--49.

Digital Library

[20]

C. Lattner and V. Adve, "Automatic pool allocation: improving performance by controlling data structure layout in the heap", Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, Chicago, IL, USA: ACM, 2005, pp. 129--142.

Digital Library

[21]

M. Hirzel, J. Henkel, A. Diwan, and M. Hind, "Understanding the connectivity of heap objects", Proceedings of the 3rd international symposium on Memory management, Berlin, Germany: ACM, 2002, pp. 36--49.

Digital Library

[22]

T. M. Chilimbi and J. R. Larus, "Using generational garbage collection to implement cache-conscious data placement", Proceedings of the 1st international symposium on Memory management, Vancouver, British Columbia, Canada: ACM, 1998, pp. 37--48.

Digital Library

[23]

T. M. Chilimbi, M. D. Hill, and J. R. Larus, "Cache-conscious structure layout", Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, Atlanta, Georgia, United States: ACM, 1999, pp. 1--12.

Digital Library

[24]

T. Domani, G. Goldshtein, E. K. Kolodner, E. Lewis, E. Petrank, and D. Sheinwald, "Thread-local heaps for Java", Proceedings of the 3rd international symposium on Memory management, Berlin, Germany: ACM, 2002, pp. 76--87.

Digital Library

[25]

"SPEC - Standard Performance Evaluation Corporation", Internet: http://www.spec.org/, {May 2009}

Cited By

Shingarov BLaval JEtien A(2015)Live Introspection of Target-Agnostic JIT in SimulationProceedings of the International Workshop on Smalltalk Technologies10.1145/2811237.2811295(1-9)Online publication date: 15-Jul-2015
https://dl.acm.org/doi/10.1145/2811237.2811295
Sciampacone RSundaresan VMaier DGray-Donald T(2010)Exploitation of multicore systems in a java virtual machineIBM Journal of Research and Development10.1147/JRD.2010.205791154:5(445-455)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1147/JRD.2010.2057911

Index Terms

Cache line reservation: exploring a scheme for cache-friendly object allocation
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Runtime environments
    2. General programming languages
      1. Language types
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Allocation / deallocation strategies

Recommendations

Location cache: a low-power L2 cache system
ISLPED '04: Proceedings of the 2004 international symposium on Low power electronics and design

While set-associative caches incur fewer misses than direct-mapped caches, they typically have slower hit times and higher power consumption, when multiple tag and data banks are probed in parallel. This paper presents the location cache structure which ...
Criticality aware tiered cache hierarchy: a fundamental relook at multi-level cache hierarchies
ISCA '18: Proceedings of the 45th Annual International Symposium on Computer Architecture

On-die caches are a popular method to help hide the main memory latency. However, it is difficult to build large caches without substantially increasing their access latency, which in turn hurts performance. To overcome this difficulty, on-die caches ...
Improving First Level Cache Efficiency for GPUs Using Dynamic Line Protection
ICPP '18: Proceedings of the 47th International Conference on Parallel Processing

A modern Graphics Processing Unit (GPU) utilizes L1 Data (L1D) caches to reduce memory bandwidth requirements and latencies. However, the L1D cache can easily be overwhelmed by many memory requests from GPU function units, which can bottleneck GPU ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

CASCON '09: Proceedings of the 2009 Conference of the Center for Advanced Studies on Collaborative Research

November 2009

392 pages

Conference Chairs:
Joanna Ng
Head of the Centre for Advanced Studies
,
Christian Couturier
National Research Council Canada
,
Editors:
Patrick Martin
Queen's University
,
Anatol W. Kark,
Darlene Stewart
National Research Council Canada
,
Program Chairs:
Anatol W. Kark
National Research Council Canada
,
Patrick Martin
Queen's University

Sponsors

IBM Toronto Software Lab
IBM Centers for Advanced Studies (CAS)

Publisher

IBM Corp.

United States

Publication History

Published: 02 November 2009

Qualifiers

Research-article

Acceptance Rates

Overall Acceptance Rate 24 of 90 submissions, 27%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
124
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shingarov BLaval JEtien A(2015)Live Introspection of Target-Agnostic JIT in SimulationProceedings of the International Workshop on Smalltalk Technologies10.1145/2811237.2811295(1-9)Online publication date: 15-Jul-2015
https://dl.acm.org/doi/10.1145/2811237.2811295
Sciampacone RSundaresan VMaier DGray-Donald T(2010)Exploitation of multicore systems in a java virtual machineIBM Journal of Research and Development10.1147/JRD.2010.205791154:5(445-455)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1147/JRD.2010.2057911

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents