University:
Massachusetts Institute of Technology
Course:
6.896 | Theory of Parallel Hardware (SMA 5511)
Academic year:

2021
Views:

150

Pages:

5
Author:

kopiena3

General Layout Strategy Tree of meshes (not mesh of trees) TOM(n) N = n + lgn n 000 00 n² leaves Area: TOM TOM TOM TOM (ক) (2) -8(4) S(n)=25(1/2)+ A(n) = O(n²lgn) Fold and squash: n²lgn layers → O(n²lgn) area. Truncated TOM: TOM(n,k) - top k levels Area = O(n²k²) Decomposition trees T is a (w, w₂)..., w > decomposition tree for G=(V, E): 1. Vertices in V mapped to leaves of T. 2. Edges in E run through links of T. 3. #edges leaving subtree rooted at depth i is swi For K₁₂, G has a (w, w₂)..., w > decomposition tree if it has a decomp tree. A decomp tree is balanced if all subgraphs at the same depth have same # vertices to within 1. Layout strategy 1. Start with (w, √2) decomp tree 2. Balance the decomp tree. 3. Embed the balanced tree in trunc TOM 4. Use trunc TOM layout to yield O(w²lgn) area layout. Balancing decomp trees Warm-up: Necklace with black and white pearls. How many cuts to divide into 2 sets, each with half the pearls of each color? 00 2 cuts suffice. Continuity argument. Lemma: Consider any 2 strings composed of an even # of black pearls and an even # of white pearls. By making at most 2 cuts, the pearls can be partitioned into 2 sets, each containing 2 strings, such that each set has 1/2 the pearls of each color. PS. (Continuity arg) Lemma. Let T be cbt drawn with n leaves on a straight line, and consider any set S of k consecutive leaves of T. Then, there is a forest F of complete binary subtrees of T$ 1. S={ leaves of F} 2. at most 2 trees of F have any given height. 3. depth of largest tree in F is log k. Pf. F be forest of maximal cbt's whose leaves lie only in S. (1) & (3) follow. Use induction to prove (2). Thm. Let G be a graph on n vertices that has a (w, w₂)..., w > decomposition tree T, where G has a (w₁, w₂, ..., wn) balanced decomp tree T. Whene H W = 4 Σωκ. Kこし PE Color leaves of T: 1= node of G, 0= empty. left (') Recursively split B&W leaves evenly. Each stage has 52 strings of consec. leaves from T, each of which has 2dbt's of a given herght.

6.896 Lecture 20 Notes

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock