Memory Hierachy

• registers: 1 cycle (256 bytes or so)
• cache: 4 cycles (100MB or so)
• memory: 100-500 cycles (128GB)
• disk: millions of cycles (1-10TB)

Trends

• power usage limits: with a fixed power budget, we can’t really get more transistors in the same space (i.e. stuff can’t be faster)
• cache miss cost is quite high, so using multiple lines of cache

register allocation

see Register Allocation

performance engineering

example

Consider:

for (int j=1; j<10; j++)
    for (int i=1; i<10000; i++)
        a[i] *= b[i]

you can see that, by the time you get to b[100000], you probably have lost b[1] from your cache.

Garbage Collection!

Garbage Collection

Very simple idea: when an object is created, unused space is automatically allocated. We leverage the observation that a program can use only the objects that it could find:

for instance

let x:A <- new A in { x <- y }

1. allocate space as needed for new objects
2. when spaces runs out… a) compute what objects might be used again (trace from “root”) b) free the space not found in

Mark and Sweep

when memory runs out…

computing

computing is to find out something by using mathematical processes …which doesn’t necessarily require computers

computing is the evolution of an environment via repeated applications of simple, local rules

computational lens

“is it likely / could this computation (i.e. folding proteins) be done within the timeframe given?”

these computations emerge sometimes naturally; such as markets computing equilibrium simply by buying and selling directly.

zero-knowledge

zero-knowledge proofs are proofs which is able to show results in computation without being given the knowledge that’s needed as inputs to the proof. this is usually true due to limited resources in computation

Algorithmic Fairness

Randomness and Pesudorandomness

When randomness can be reduced or eliminated, we call it “derandomization”.

pseudorandomness is an object which appears to be uniform distributed but actually it is not.

when randomness is necessary

1. distributed computing: symmetry, etc.
2. cryptography: secrets, semantic security, etc.

dining philosophers problems—how to break symmetry which causes deadlock?

Byzantine agreement—attack if all leaders want to attack with Byzantine decisions (if the clocks of attack decisions each round is not synchronized, the only way this could work is through randomized algorithms)

Deterministic Finite Automata, Nondeterministic Finite Automata and regular expressions

Streaming Algorithms