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.4Storage Technology Trends
6.2 Locality
6.3 The Memory Hierarchy
p. 639Aside: why index with the middle bits?
 6.4.6Anatomy of a Real Cache Hierarchy
 6.4.7Performance impact of Cache Parameters
p. 649Aside: 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.

Last updated October 6 2011

o This web-page and the list of participants to this course is maintained by Arnoud Visser (arnoud@science.uva.nl)
Faculty of Science
University of Amsterdam

visitors in arnoud@science.uva.nl