## 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.