NDLI: An inter-reference gap model for temporal locality in program behavior

Content Provider	ACM Digital Library
Author	Phalke, Vidyadhar Gopinath, Bhaskarpillai
Abstract	The property of locality in program behavior has been studied and modelled extensively because of its application to memory design, code optimization, multiprogramming etc. We propose a k order Markov chain based scheme to model the sequence of time intervals between successive references to the same address in memory during program execution. Each unique address in a program is modelled separately. To validate our model, which we call the Inter-Reference Gap (IRG) model, we show substantial improvements in three different areas where it is applied. (1) We improve upon the miss ratio for the Least Recently Used (LRU) memory replacement algorithm by up to 37%. (2) We achieve up to 22% space-time product improvement over the Working Set (WS) algorithm for dynamic memory management. (3) A new trace compression technique is proposed which compresses up to 2.5% with zero error in WS simulations and up to 3.7% error in the LRU simulations. All these results are obtained experimentally, via trace driven simulations over a wide range of cache traces, page reference traces, object traces and database traces.
Starting Page	291
Ending Page	300
Page Count	10
File Format	PDF
ISSN	01635999
DOI	10.1145/223586.223620
Journal	ACM SIGMETRICS Performance Evaluation Review (PERV)
Volume Number	23
Issue Number	1
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-01-10
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Dynamic memory management Trace compaction Locality of reference Trace driven simulation Prediction Markov chains Memory replacement
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An inter-reference gap model for temporal locality in program behavior

Blocking: exploiting spatial locality for trace compaction

Effect of program localities on memory management strategies

Complete or fast reference trace collection for simulating multiprogrammed workloads:choose one

Adaptive page replacement based on memory reference behavior

Program Behavior and the Performance of Interleaved Memories

Accuracy of Memory Reference Traces of Parallel Computations in Trace-Driven Simulation (1990)

Improving the Cache Locality of Memory Allocation (1993)

An Example of Correct Global Trace Generation (1990)

An inter-reference gap model for temporal locality in program behavior

Similar Documents

An inter-reference gap model for temporal locality in program behavior

Blocking: exploiting spatial locality for trace compaction

Effect of program localities on memory management strategies

Complete or fast reference trace collection for simulating multiprogrammed workloads:choose one

Adaptive page replacement based on memory reference behavior

Program Behavior and the Performance of Interleaved Memories

Accuracy of Memory Reference Traces of Parallel Computations in Trace-Driven Simulation (1990)

Improving the Cache Locality of Memory Allocation (1993)

An Example of Correct Global Trace Generation (1990)

An inter-reference gap model for temporal locality in program behavior