Meshes of Trees (MoT) and Applications in Integer Arithmetic Panagiotis Voulgaris Petros Mol Course: Parallel Algorithms 1 Outline of the talk
The two-Dimensional Mesh of Trees Definitions Properties Variations Integer Arithmetic Applications
Multiplication Division Powering Root Finding 2 Definition
Construction: N N grid Mesh of Trees 3N 2 2 N Nodes 3 Properties
1)Diameter (maximum distance between any pair of processors): 4logN Proof Case 1: u belongs to a row tree and v to a column tree u u v Dist<=2logN +2logN v
4 Properties (cont.) Case 2:u,v belong only to row trees (or only to column trees) uu v Dist=logN r +2logN + logN + s<=4logN since r>=s u
5 Properties (cont) 2)Bisection Width(the minimum number of wires that have to be removed in order to disconnect the network into two halves with almost identical number of processors) :N (Proof omitted)
Thus meshes of trees enjoy both small diameter and large bisection width. This fact makes them a more efficient structure than arrays and simple trees 6 Recursive Decomposition N N Mesh of trees Four disjoint copies of
N N 2 2 Mesh of trees Importance: This property makes mesh of trees appropriate for recursive algorithms for parallel computation 7
Ideal Parallel Computer P+M P: Processor P+M M: Memory P+M P+M
P+M P+M P+M P+M Every processor is linked to every other processor. Advantage: Speed !! Drawback: Cost
8 Ideal Parallel Computer P M P M
M P P M
Process/Memory separation Every Processor has direct access to a memory register Again here the degree of each node becomes large as the number of processor increases Idea: Why not simulate the complete bipartite graph? 9 Ideal Parallel Computer
10 Ideal Parallel Computer 11 Ideal Parallel Computer 12 Benefits and Drawbacks
+Simulation of any step of K N , N in 2logN steps +Bounded degree graph with essentially the computational power as K N , N +We have actually constructed the NxN mesh of Trees 2 - The mesh of Trees has nearly 3Nnodes whereas the initial complete bipartite graph had only 2N Solution: Later 13
Transformation to mesh of Trees Back 14 Variations 1) 15 Variations (cont)
16 Variations (cont) 2) 17 Variations (cont.) 3)
18 Variations (cont.) 4) 19