# Hypercubic Networks 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