Browse Prior Art Database

Maintaining Multiple Free Lists to Enhance L2 Cache Performance

IP.com Disclosure Number: IPCOM000114718D
Original Publication Date: 1995-Jan-01
Included in the Prior Art Database: 2005-Mar-29
Document File: 2 page(s) / 49K

Publishing Venue

IBM

Related People

Alexander, WP: AUTHOR [+2]

Abstract

Most systems which support a multi-level cache hierarchy perform the first-level (L1) cache access in parallel with the virtual-to-real address translation. Subsequent levels of cache and memory are indexed with bits from the physical address. Due to the effective random assignment of page frames by operating systems, adjacent virtual pages are scattered throughout real memory. Since the placement of data in real memory determines the placement of data in a physically-mapped L2 cache, this scattering of pages results in L2 cache conflicts which would not occur in a virtually-indexed L2 cache. These additional conflicts degrade performance. In addition, the assignment of pages and the resulting conflicts vary from run to run causing fluctuations in program execution times.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 75% of the total text.

Maintaining Multiple Free Lists to Enhance L2 Cache Performance

      Most systems which support a multi-level cache hierarchy
perform the first-level (L1) cache access in parallel with the
virtual-to-real address translation.  Subsequent levels of cache and
memory are indexed with bits from the physical address.  Due to the
effective random assignment of page frames by operating systems,
adjacent virtual pages are scattered throughout real memory.  Since
the placement of data in real memory determines the placement of data
in a physically-mapped L2 cache, this scattering of pages results in
L2 cache conflicts which would not occur in a virtually-indexed L2
cache.  These additional conflicts degrade performance.  In addition,
the assignment of pages and the resulting conflicts vary from run to
run causing fluctuations in program execution times.  These problems
appear in all computer systems which include a physically-mapped L2
cache.

      Most contemporary operating systems maintain a single list,
called the free list, of page frames that are available to assign to
a process that incurs a page fault.  This proposal would replace the
single free list with n lists, labeled 0 through n-1, where n is a
power of 2.  The low-order log2(n) bits of the real page frame number
determine which list the frame is kept on.  When a process incurs a
page fault, the low-order bits of the virtual page number determine
from which free list the operating system attempts to...