Overview

Computer system design is a game of trade-offs. No where is that more evident than in the memory hierarchy, an organization of several devices meant to provide excellent performance at a reasonable cost.

In this reading you’ll be introduced to the memory hierarchy, starting with the trends in device cost, speed, and size that drive the organization of this hierarchy. You’ll also explore two fundamental concepts of computer science: locality and caching.

Required Reading

Sections 6.1.4, 6.2 - 6.3 (pp. 602-614) from the course textbook.

Learning Objectives

BASIC Learning Objectives

Each student will be responsible for learning and demonstrating proficiency in the following objectives PRIOR to the class meeting. The reading quiz will test these objectives.

  1. Describe the trends in cost, speed, and size for SRAM, DRAM, and rotating disks.
  2. Describe the trends in relative speed between CPUs, DRAM, and rotating disks.
  3. Compare and contrast spatial and temporal locality.
  4. Given a table of addresses, identify instances of spatial and temporal locality.
  5. Provide an example of code with a stride-k reference pattern.
  6. Describe how inverting the order of nested loops can affect program performance.
  7. Describe the trends associated with moving from higher to lower levels in the memory hierarchy.
  8. Given a storage device (e.g. Main memory) and a memory hierarchy, determine the other device for which it acts as a cache.
  9. Describe the three types of cache misses.

ADVANCED Learning Objectives

The following objectives should be mastered by each student DURING and FOLLOWING the class session through active work and practice.

  1. Determine which types of locality a given C program is likely to exhibit.
  2. Identify the cause(s) of each type of cache miss and propose one or more ways to reduce that type of miss.

Pre-class Exercises

These exercises are geared towards mastering the BASIC learning objectives listed above. You are expected to submit them before class and it is highly recommended that you complete them before attempting the reading quiz.

  1. The table below contains a sequence of memory address accesses, where the first row is the first access, the second row is the next access, and so forth. Complete the table by filling in yes/no as to whether each access is an example of spatial or temporal locality. You can assume that all accesses are 4 bytes (i.e. reading or writing an int).

    Address Spatial? Temporal?
    0
    4
    8
    12
    100
    104
    108
    200
    4
    8
    200

  2. Complete the following C code such that the code has a stride-4 reference pattern.

    int get_max(int *arr, int size) {
    int max = 0;

    for (                                           ) {
        int tmp = arr[i];
        if (tmp > max) max = tmp;
    }

    return max;
}

  3. For each of these layers in the memory hierarchy, list the device for which it acts as a cache.