Page 182 -

152 CHAPTER 4 / CACHE MEMORY

Table 4.8 Relative Dynamic Frequency of High-Level Language Operations

Study [HUCK83] [KNUT71] [PATT82a] [TANE78]
Language Pascal FORTRAN Pascal C SAL
Workload Scientific Student System System System

Assign 74 67 45 38 42
Loop 4 3 5 3 4
Call 1 3 15 12 12
IF 20 11 29 43 36
GOTO 2 9 — 3 —
Other — 7 6 1 6

rather narrow window of procedure-invocation depth. Thus, over a short period
of time references to instructions tend to be localized to a few procedures.
3. Most iterative constructs consist of a relatively small number of instructions re-
peated many times. For the duration of the iteration, computation is therefore
confined to a small contiguous portion of a program.
4. In many programs, much of the computation involves processing data struc-
tures, such as arrays or sequences of records. In many cases, successive refer-
ences to these data structures will be to closely located data items.
This line of reasoning has been confirmed in many studies. With reference to
point 1, a variety of studies have analyzed the behavior of high-level language pro-
grams. Table 4.8 includes key results, measuring the appearance of various statement
types during execution, from the following studies.The earliest study of programming
language behavior, performed by Knuth [KNUT71], examined a collection of FOR-
TRAN programs used as student exercises. Tanenbaum [TANE78] published mea-
surements collected from over 300 procedures used in operating-system programs
and written in a language that supports structured programming (SAL). Patterson
and Sequein [PATT82a] analyzed a set of measurements taken from compilers and
programs for typesetting, computer-aided design (CAD), sorting, and file comparison.
The programming languages C and Pascal were studied. Huck [HUCK83] analyzed
four programs intended to represent a mix of general-purpose scientific computing,
including fast Fourier transform and the integration of systems of differential equa-
tions.There is good agreement in the results of this mixture of languages and applica-
tions that branching and call instructions represent only a fraction of statements
executed during the lifetime of a program.Thus, these studies confirm assertion 1.
With respect to assertion 2, studies reported in [PATT85a] provide confirma-
tion. This is illustrated in Figure 4.21, which shows call-return behavior. Each call is
represented by the line moving down and to the right, and each return by the line
moving up and to the right. In the figure, a window with depth equal to 5 is defined.
Only a sequence of calls and returns with a net movement of 6 in either direction
causes the window to move. As can be seen, the executing program can remain
within a stationary window for long periods of time.A study by the same analysts of
C and Pascal programs showed that a window of depth 8 will need to shift only on
less than 1% of the calls or returns [TAMI83].