More Web Proxy on the site http://driver.im/

research-article

Modeling of cache access behavior based on Zipf's law

Authors:

Hiroyuki Takizawa,

Hiroaki KobayashiAuthors Info & Claims

MEDEA '08: Proceedings of the 9th workshop on MEmory performance: DEaling with Applications, systems and architecture

Pages 9 - 15

https://doi.org/10.1145/1509084.1509086

Published: 26 October 2008 Publication History

Abstract

Recently, chip multiprocessors (CMPs) that can simultaneously execute multiple workloads using multiple cores have become a key to achieve high-performance processing. To improve CMP performance, various shared resource management mechanisms have been proposed. In particular, cache partitioning is significantly effective to avoid resource conflicts at a shared cache memory. As most cache partitioning methods need to predict the changes in cache access characteristics of each workload when the cache partition moves, it is important for cache partitioning to establish an accurate prediction model.

In this paper, we first analyze the cache access locality of various applications using stack distance profiling. We figure out that stack distance distributions incline to obey socalled Zipf's law. To achieve effective cache partitioning, then, we propose a model based on Zipf's law that predicts the changes in the stack distance distributions. Using the model, we also show the validity of a measure, which has been proposed in our previous work to quantify how much a workload demands the cache capacity.

References

[1]

A. Bardine, P. Foglia, G. Gabrielli, C. A. Prete, and P. Stenström. Improving power efficiency of d-nuca caches. ACM SIGARCH Computer Architecture News, 35(4):53--58, Sept. 2007.

Digital Library

[2]

N. Binkert, R. Dreslinski, L. Hsu, K. Lim, A. Saidi, and S. Reinhardt. The m5 simulator: Modeling networked systems. IEEE Micro, 26(4):52--60, July-Aug. 2006.

Digital Library

[3]

L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web caching and zipf-like distributions: evidence and implications. INFOCOM '99: Proceedings of the Eighteenth Annual Joint Conference, 1:126--134, Mar 1999.

[4]

D. Chandra, F. Guo, S. Kim, and Y. Solihin. Predicting inter-thread cache contention on a chip multi-processor architecture. In HPCA '05: Proceedings of the 11th International Symposium on High-Performance Computer Architecture, pages 340--351, 2005.

Digital Library

[5]

C. Cunha, A. Bestavros, and M. Crovella. Characteristics of World Wide Web Client-based Traces. Technical Report BUCS-TR-1995-010, Boston University, CS Dept, Boston, MA 02215, April 1995.

Digital Library

[6]

D. G. Feitelson. On the interpretation of top500 data. International Journal of High Performance Computing Applications, 13(2):146--153, 1999.

Digital Library

[7]

B. Gutenberg and C. F. Richter. Frequency and energy of earthquakes. Seismicity of the Earth and Associated Phenomena, pages 17--19, 1954.

[8]

R. Iyer, L. Zhao, F. Guo, R. Illikkal, S. Makineni, D. Newell, Y. Solihin, L. Hsu, and S. Reinhardt. Qos policies and architecture for cache/memory in cmp platforms. Proceedings of the 2007 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 35(1):25--36, 2007.

Digital Library

[9]

S. Kim, D. Chandra, and Y. Solihin. Fair cache sharing and partitioning in a chip multiprocessor architecture. In PACT '04: Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, pages 111--122, 2004.

Digital Library

[10]

H. Kobayashi, I. Kotera, and H. Takizawa. Locality analysis to control dynamically way-adaptable caches. ACM SIGARCH Computer Architecture News, 33(3):25--32, 2005.

Digital Library

[11]

I. Kotera, K. Abe, R. Egawa, H. Takizawa, and H. Kobayashi. Power-aware dynamic cache partitionning for cmps. Transactions on High-Performance Embedded Architectures and Compilers, 3(2):149--167, 2008.

[12]

I. Kotera, R. Egawa, H. Takizawa, and H. Kobayashi. A power-aware shared cache mechanism based on locality assessment of memory reference for cmps. In MEDEA '07: Proceedings of the 2007 workshop on MEmory performance, pages 113--120, 2007.

Digital Library

[13]

M. K. Qureshi and Y. N. Patt. Utility-based cache partitioning: A low-overhead, high-performance, runtime mechanism to partition shared caches. In MICRO 39: Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, pages 423--432, 2006.

Digital Library

[14]

M. Ripeanu. Note on zipf distribution in top500 supercomputers list. Technical report, IEEE Distributed Systems Online, October 2006.

[15]

G. E. Suh, L. Rudolph, and S. Devadas. Dynamic partitioning of shared cache memory. Journal of Supercomputing, 28(1):7--26, 2004.

Digital Library

[16]

The Standard Performance Evaluation Corporation. http://www.spec.org/.

[17]

TOP500 Supercomputer Sites. http://www.top500.org/.

[18]

G. K. Zipf. Human Behavior and the Principle of Least Effort. Addison-Wesley, 1949.

Cited By

Yuan ZLv XXie PGe HYou X(2022)CSEA: A Fine-Grained Framework of Climate-Season-Based Energy-Aware in Cloud Storage SystemsThe Computer Journal10.1093/comjnl/bxac184Online publication date: 30-Dec-2022
https://doi.org/10.1093/comjnl/bxac184
Yang YZhu J(2016)Write Skew and Zipf DistributionACM Transactions on Storage10.1145/290855712:4(1-19)Online publication date: 8-Jun-2016
https://dl.acm.org/doi/10.1145/2908557
Luo CWang ZChen XLuo TBoudriga NRekhis S(2014)LBA privacy preserving index and its theoretical analysis in cloud storage systemsProceedings of the 2nd international workshop on Security and forensics in communication systems10.1145/2598918.2598924(37-44)Online publication date: 3-Jun-2014
https://dl.acm.org/doi/10.1145/2598918.2598924
Show More Cited By

Index Terms

Modeling of cache access behavior based on Zipf's law

Recommendations

Data access history cache and associated data prefetching mechanisms
SC '07: Proceedings of the 2007 ACM/IEEE conference on Supercomputing

Data prefetching is an effective way to bridge the increasing performance gap between processor and memory. As computing power is increasing much faster than memory performance, we suggest that it is time to have a dedicated cache to store data access ...
CPU Cache Prefetching: Timing Evaluation of Hardware Implementations

Prefetching into CPU caches has long been known to be effective in reducing the cache miss ratio, but known implementations of prefetching have been unsuccessful in improving CPU performance. The reasons for this are that prefetches interfere with ...
Code-based cache partitioning for improving hardware cache performance
ICUIMC '12: Proceedings of the 6th International Conference on Ubiquitous Information Management and Communication

Recently, improving hardware cache performance is getting more important, because the performance gap between processor and memory has caused "memory wall" problem. Most cache designs are based on the LRU replacement policy which is effective for high-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

MEDEA '08: Proceedings of the 9th workshop on MEmory performance: DEaling with Applications, systems and architecture

October 2008

88 pages

ISBN:9781605582436

DOI:10.1145/1509084

Conference Chairs:
Pierfrancesco Foglia
Università di Pisa
,
Cosimo Antonio Prete
Università di Pisa
,
Sandro Bartolini
Università di Siena
,
Roberto Giorgi
Università di Siena

Copyright © 2008 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 October 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Ministry of Education, Culture, Sports, Science, and Technology

Conference

MEDEA '08

MEDEA '08: The 2008 workshop on MEmory performance: DEaling with Applications, systems and architectures

October 26, 2008

Toronto, Canada

Acceptance Rates

Overall Acceptance Rate 6 of 9 submissions, 67%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
384
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)2

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yuan ZLv XXie PGe HYou X(2022)CSEA: A Fine-Grained Framework of Climate-Season-Based Energy-Aware in Cloud Storage SystemsThe Computer Journal10.1093/comjnl/bxac184Online publication date: 30-Dec-2022
https://doi.org/10.1093/comjnl/bxac184
Yang YZhu J(2016)Write Skew and Zipf DistributionACM Transactions on Storage10.1145/290855712:4(1-19)Online publication date: 8-Jun-2016
https://dl.acm.org/doi/10.1145/2908557
Luo CWang ZChen XLuo TBoudriga NRekhis S(2014)LBA privacy preserving index and its theoretical analysis in cloud storage systemsProceedings of the 2nd international workshop on Security and forensics in communication systems10.1145/2598918.2598924(37-44)Online publication date: 3-Jun-2014
https://dl.acm.org/doi/10.1145/2598918.2598924
Quislant RGutierrez EPlata O(2014)Scalability Analysis of Signatures in Transactional Memory SystemsProceedings of the 2014 IEEE 26th International Symposium on Computer Architecture and High Performance Computing10.1109/SBAC-PAD.2014.40(128-135)Online publication date: 22-Oct-2014
https://dl.acm.org/doi/10.1109/SBAC-PAD.2014.40
Joseph JPionteck T(2014)A cycle-accurate Network-on-Chip simulator with support for abstract task graph modeling2014 International Symposium on System-on-Chip (SoC)10.1109/ISSOC.2014.6972440(1-6)Online publication date: Oct-2014
https://doi.org/10.1109/ISSOC.2014.6972440
Quislant RGutierrez EPlata OZapata E(2013)LS-SigIEEE Transactions on Computers10.1109/TC.2011.23062:2(322-335)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1109/TC.2011.230
Zhuravlev SSaez JBlagodurov SFedorova APrieto M(2012)Survey of scheduling techniques for addressing shared resources in multicore processorsACM Computing Surveys10.1145/2379776.237978045:1(1-28)Online publication date: 7-Dec-2012
https://dl.acm.org/doi/10.1145/2379776.2379780
Wang ZLuo TXu YCheng FZhang XWang X(2012)A fast indexing algorithm optimization with user behavior patternProceedings of the 2012 international conference on Pervasive Computing and the Networked World10.1007/978-3-642-37015-1_52(592-605)Online publication date: 28-Nov-2012
https://dl.acm.org/doi/10.1007/978-3-642-37015-1_52
Idziorek JTannian MJacobson DCachin CRistenpart T(2011)Detecting fraudulent use of cloud resourcesProceedings of the 3rd ACM workshop on Cloud computing security workshop10.1145/2046660.2046676(61-72)Online publication date: 21-Oct-2011
https://dl.acm.org/doi/10.1145/2046660.2046676

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