An example of how the system manages data in an array

To evaluate the performance advantage reference pattern services offers, you need to understand how the system handles a range of data. The best way to describe this is through an example of a simple two-dimensional array. As array A(i,j) of 3 rows and 4 columns illustrates, the system stores arrays in FORTRAN programs in column-major order and stores arrays in COBOL, Pascal, PL/1, and C programs in row-major order.

  A(1,1)       A(1,2)      A(1,3)     A(1,4)
  A(2,1)       A(2,2)      A(2,3)     A(2,4)
  A(3,1)       A(3,2)      A(3,3)     A(3,4)

The system stores the elements of the arrays in the following order:

   Sequence of             FORTRAN           COBOL, Pascal, PL/1, C
Element in Storage       Array Element            Array Element

      1                     A(1,1)                   A(1,1)
      2                     A(2,1)                   A(1,2)
      3                     A(3,1)                   A(1,3)
      4                     A(1,2)                   A(1,4)
      5                     A(2,2)                   A(2,1)
      6                     A(3,2)                   A(2,2)
      7                     A(1,3)                   A(2,3)
      8                     A(2,3)                   A(2,4)
      9                     A(3,3)                   A(3,1)
      10                    A(1,4)                   A(3,2)
      11                    A(2,4)                   A(3,3)
      12                    A(3,4)                   A(3,4)

Examples in Introduction to reference pattern services and Using reference pattern services depict data as a horizontal string. The elements in the arrays, therefore, would look like the following:

                      Location of elements
_________________________________________________________
1    2    3    4    5    6    7    8    9    10   11   12

Consider a two-dimensional array, ARRAY1, that has 1024 columns and 1024 rows and each element is eight bytes in size. The size of the array, therefore, is 1048576 elements or 8388608 bytes. For simplicity, assume the array is aligned on a page boundary. Also, assume the data is not in central storage. The program references each element in the array in a forward direction, starting with the first element.

First, consider how the system brings data into central storage without information from reference pattern services. At the first reference of ARRAY1, 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 (4096 divided by 8) element in the array, the system takes another page fault and brings in a second page. The system takes a page fault every 512 elements, throughout the array.

The following linear representation shows the elements in the array and the page faults the system takes as a program processes 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 CSRIRP, 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 ARRAY1. The program references the first twenty elements, then skips over the next 1004 elements, and so forth through the array. CSRIRP allows you to tell the system to bring in only the pages that contain the data the program references. 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 array at regular intervals. 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 shows this reference pattern and the pages that the system does not bring into central storage.