To evaluate the performance advantage REFPAT offers, you need to
understand how the system handles a range of data that a program references.
Consider the two-dimensional array in
Figure 1 that
is shown in row-major order and in order of increasing addresses.
This array has 1024 columns and 1024 rows and each element is eight
bytes in size. Each number in
Figure 1 represents
one element. The size of the array is 1048576 elements for a total
of 8388608 bytes. For simplicity, assume the array is aligned on a
page boundary. Assume, also, that the array is not already in central
storage. The program references each element in the array in a forward
direction (that is, in order of increasing addresses) starting with
the first element in the array.
Figure 1. Example of
using REFPAT with a Large Array
First, consider how the system brings data into central storage
without using the information REFPAT provides. At the first reference
of the array, the system takes a page fault and brings into central
storage the page (of 4096 bytes) that contains the first element.
After the program finishes processing the 512th element (4096 divided
by 8) in the array, the system takes another page fault and brings
in a second page. To provide the data for this program, the system
takes two page faults for each row. The following linear representation
shows the elements in the array and the page faults the system takes
as the program processes through the array.
By bringing in one page at a time, the system takes 2048 page faults
(8388608 divided by 4096), each page fault adding to the elapsed time
of the program.
Suppose, through REFPAT, the system knew in advance that a program
would be using the array in a consistently forward direction. The
system could then assume that the program's use of the pages of the
array would be sequential. To decrease the number of page faults,
each time the program requested data that was not in central storage,
the system could bring in more than one page at a time. Suppose the
system brought the next 20 consecutive pages (81920 bytes) of the
array into central storage on each page fault. In this case, the system
takes not 2048 page faults, but 103 (8388608 divided by 81920=102.4).
Page faults occur in the array as follows:
The system brings in successive pages only to the end of the array.
Consider another way of referencing this same array. The program
references the first twenty elements in each row, then skips over
the last 1004 elements, and so forth through the array. REFPAT allows
you to tell the system to bring in only the pages that contain the
data in the first 20 columns of the array, and not the pages that
contain only data in columns 21 through 1024. In this case, the reference
pattern includes a repeating gap of 8032 bytes (1004×8) every
8192 bytes (1024×8). The pattern looks like this:
The grouping of consecutive bytes that the program references is
called a
reference unit. The grouping of consecutive
bytes that the program skips over is called a
gap. Reference units and gaps alternate
throughout the data area. The reference pattern is as follows:
- The reference unit is 20 elements in size — 160 consecutive
bytes that the program references.
- The gap is 1004 elements in size — 8032 consecutive bytes
that the program skips over.
Figure 1 illustrates this reference pattern and shows
the pages that the system does not bring into central storage.