Tiling algorithms
Sorry, when did this become about tiles?
In RISC you have small tiles, in CISC you have large tiles.
Oh, this makes sense; tree tiles are bits of trees that can be matched up together to form complex operations. Several tiles can fit a higher level instruction/whatever. They usually have different levels of cost, and tiles can also be combined together where possible. Therefore you have different algorithms that combine smallest cost, and biggest tiles.
- Optimum tiling: a tiling with lowest possible costs.
- Optimal tiling: no two adjacent tiles combinable into a single tile of lower cost.
Maximal Munch Algorithm
- Top-down tiling
- Yields an optimal tiling
How does it work?
- starting at root of tree, find largest tile that fits
- that tile covers root node and some other nodes, leaving subtrees
- repeat algorithm for each subtree
He had an ‘animation’ for this.
Dynamic Programming Tiling
- Bottom-up tiling – Start at leaves, calculate best tiling at each leaf and gradually rise up each leaf calculating the optimum for that subtree until you reach the top.
- Global optimum tiling
How does it work?
- Assign to each subtree an optimum tiling and cost of that tiling
- Compute this info for a subtree by considering each tile that matches at the root. Cost of using tile is cost of tile plus costs of optimum tiling of remaining subtrees: choose the tile where cost of this is minimal.
He had an ‘animation’ for this too.