Pro-active page replacement for scientific applications: A characterization

Research output: Contribution to conferencePaperpeer-review

2 Scopus citations


Paging policies implemented by today's operating systems cause scientific applications to exhibit poor performance, when the application's working set does not fit in main memory. This has been typically attributed to the suboptimal performance of LRU-like virtual-memory replacement algorithms. On one end of the spectrum, researchers in the past have proposed fully automated compiler-based techniques that provide crucial information on future access patterns (reuse-distances, release hints etc) of an application that can be exploited by the operating system to make intelligent prefetching and replacement decisions. Static techniques like the aforementioned can be quite accurate, but require that the source code be available and analyzable. At the other end of the spectrum, researchers have also proposed pure system-level algorithmic innovations to improve the performance of LRU-like algorithms, some of which are only interesting from the theoretical sense and may not really be implementable. Instead, in this paper we explore the possibility of tracking application's runtime behavior in the operating system, and find that there are several useful characteristics in the virtual memory behavior that can be anticipated and used to pro-actively manage physical memory usage. Specifically, we show that LRU-like replacement algorithms hold onto pages long after they outlive their usefulness and propose a new replacement algorithm that exploits the predictability of the application's page-fault patterns to reduce the number of page-faults. Our results demonstrate that such techniques can reduce page-faults by as much as 78% over both LRU and EELRU that is considered to be one of the state-of-the-art algorithms towards addressing the performance shortcomings of LRU. Further, we also present an implementable replacement algorithm within the operating system, that performs considerably better than the Linux kernel's replacement algorithm.

Original languageEnglish (US)
Number of pages10
StatePublished - 2005
EventISPASS 2005 - IEEE International Symposium on Performance Analysis of Systems and Software - Austin, TX, United States
Duration: Mar 20 2005Mar 22 2005


OtherISPASS 2005 - IEEE International Symposium on Performance Analysis of Systems and Software
Country/TerritoryUnited States
CityAustin, TX

All Science Journal Classification (ASJC) codes

  • General Engineering


Dive into the research topics of 'Pro-active page replacement for scientific applications: A characterization'. Together they form a unique fingerprint.

Cite this