Course Computer Systems for AI-programmers

"Computersystemen voor AI-programmeurs"

Week 9, March 2010

Description

Although fast calculations are essential for efficient code, the calculation can only proceed when there is data available. We demonstrate the effect of caches on the performance of an algorithm, and present a technique to to assist the compiler in creating efficient code.

In this class the following concepts are introduced:

• locality; tempory and spatial
• the impact of caches on program performance

• static and dynamic linking
• symbol resolution and address relocation
• ELF object files and their .text and .data sections

Literature

The class is based on chapter 6 and 7 of the book Computer Systems: A programmer's perspective by R.E. Bryant and D.R. O'Hallaron.

Recommanded reading:

6.1.3	Storage Technology Trends
6.2	Locality
6.3	The Memory Hierarchy (not 6.3.1 and 6.3.2)
6.6	Putting it Together: the impact of caches on program performance
p. 496	Aside: why index with the middle bits?
6.4.6	Instruction Caches and Unified Caches
6.4.7	Performance impact of Cache Parameters
p. 506	Aside: Cache lines, sets, and blocks, what is the difference?
6.6.2	Rearranging Loops to Increase Spatial Locality
6.7	Putting it Together: Exploiting locality in your progr ams
H7.1-7.10, 7.13-14

Schedule

The class is scheduled in three hours:

1. Lecture (Recording): 'Computer system - the impact of caches on program performance'
   Practice Problem 6.5: 'Order three functions to the spatial locality enjoyed by each.'
   Practice Problem 6.19: 'Estimate the time, in CPU cycles, to read a 4-byte word, from the different caches, for a Pentium Dual CPU processor.
   
2. Lecture (Recording): 'Computer system - Cache Characteristics'
   Problem 6.28: What percentage of writes will miss in the cache for the blank screen function?
3. Lecture (Recording): 'Computer system - Linking'
   Problem 7.7: Modify bar5.c to print the correct values.
   
4. Exercise: 'Optimize the procedure 'rotate'
   Description, code.