Skip to content

Instantly share code, notes, and snippets.

@renxida

renxida/notes.md

Last active Aug 30, 2019
Embed
What would you like to do?
automatic generation of peephole superoptimizers

Overview

(Paper:Bansal S, Aiken A, Automatic generation of peephole superoptimizers)

Superoptimization

This is the GRAIL. Infinity. The platonic ideal of optimization. Eu-optimization. One true optimization.

What we usually call optimization is nothing but improvement. Superoptimization is the real deal.

It's finding the one true optimal canonical fastest sequence of instructions to accomplish a task.

How could you tell if two instruction sequences are the same?

Q: How could you tell if two code sequences produce the same result? I see the phrase "Boolean tests"?

A: the entire state of the machine is represented as bits. Everything. Stack, memory, registers, stack counters, program counter, everything.

Overview

Paper: 1996 Lipasti S, Wilkinson C, Shen J, Value locality and Load Value Prediction)

Caching Concepts

  • Associativity

    N-way associative: each memory piece can only have N places to go in cache fully associative: each memory piece can be anywhere in the cache Tradeoff: more assocative = more search time looking for data, but also less likely to miss.

  • Victim Cache

    Extra, slightly slower cache to store most recently evicted item.

Memory Pages

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.