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

Literature

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

Recommanded reading:

6.1.4	Storage Technology Trends
6.2	Locality
6.3	The Memory Hierarchy
p. 639	Aside: why index with the middle bits?
6.4.6	Anatomy of a Real Cache Hierarchy
6.4.7	Performance impact of Cache Parameters
p. 649	Aside: Cache lines, sets, and blocks, what is the difference?
6.5	Writing Cache-friendly Code
6.6	Putting it Together: the impact of caches on program performance

Schedule

The class is scheduled in three hours:

1. Lecture (Recording part1part2): 'Computer system - the impact of caches on program performance'
   Practice Problem 6.9: 'Order three functions to the spatial locality enjoyed by each.'
   Practice Problem 6.22: 'Estimate the time, in CPU cycles, to read a 8-byte word, from the L1-d cache for a i7 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. Exercise: 'Optimize the procedure 'line'
   Description, code, Makefile.