Tree-based languages (continued?)

4th March 2010 (Think I missed something)

These are lecture notes from my Computer Science course, not a general reference for "Tree-based languages (continued?)"

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?

1. starting at root of tree, find largest tile that fits
2. that tile covers root node and some other nodes, leaving subtrees
3. 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?

1. Assign to each subtree an optimum tiling and cost of that tiling
2. 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.

Comments

blog comments powered by Disqus