Remembering all the things I forgot

[big_bad_al]

Yesterday evening, John, Jacob (though not Jingleheimer-Schmidt) and I had a bull shoot for an hour and a half. We started out with John proposing a memory caching system which was intended to make garbage collection and blocking irrelevant. From there, the conversation natuarally progressed to online algorithms, cache-oblivious algorithms,

Comments

[big_bad_al]

The Gödel processor spends half its time running your code and half its time looking for proofs that faster-running code has the same output as the code you gave it. If it finds a faster-running program, it stops running your code and switches to the faster algorithm. Given enough time, it will always find the provably fastest-running way to calculate whatever you're trying to do.

[big_bad_al]

Pipelining can occur when you have an instruction that takes more than one CPU cycle to complete. If your hardware is set up correctly, you can start a second (or third, etc) instruction in that circuitry before the first is finished. This is used in multiplies, divides, loads, and other long instructions. Instruction-level parallelism is when you have several different instructions that don't depend on each other (such as an add, a multiply, and a load). You can execute them all in parallel because their order does not matter.

Speculative execution is a way of speeding up branching: instead of worrying about branch prediction, start executing the code for both branches, and then once you figure out which one you should have done, throw out the work you did on the wrong one and keep going on the right branch.