Hypercubic Networks

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

Recently Viewed Presentations

  • Biblestudyresourcecenter. com biblestudyresourcecenter.com Mishpatim Mishpatin Judgments The 18th

    Biblestudyresourcecenter. com biblestudyresourcecenter.com Mishpatim Mishpatin Judgments The 18th

    The rabbis consistently associate donkeys with Messiah son of David who comes "humble, and mounted on a donkey, even on a colt, the foal of a donkey" (Zechariah 9:9). At the same time, the mention of an ox invokes Messiah...
  • Metals and Nonmetals - CHISD

    Metals and Nonmetals - CHISD

    Where are the metals and nonmetals on the PT? What are the properties of metals and nonmetals? What are metalloids? * * * There is a zig-zag or staircase line that divides the table. Metals are on the left of...
  • FY 2020 PF Application Package General Information from

    FY 2020 PF Application Package General Information from

    Use updated cost and price detail spreadsheet(s) - Applications and Forms. Include the spreadsheet in the application. If you assist with the process, you cannot compete in the process. ... FY 2020 PF Application Package - PowerPoint Presentation Last modified...
  • Polemoniacea - Minnesota State University Moorhead

    Polemoniacea - Minnesota State University Moorhead

    The attractive, pinnately compound leaves and the loose flower clusters of this perennial arise on separate stalks. The stalks are slender and somewhat weak, rising 10-15 in. A smooth, weak-stemmed plant with light blue to purple, bell-shaped flowers in loose...
  • Chapter 17 Unemployment, Inflation, and Growth GDP and

    Chapter 17 Unemployment, Inflation, and Growth GDP and

    Figure 17.4A ©2002 South-Western College Publishing Real Wage Growth and Aggregate Supply: The New-Keynesian Model ©2002 South-Western College Publishing Figure 17.4B Real Wage Growth and Aggregate Supply: The New-Keynesian Model ©2002 South-Western College Publishing Figure 17.5 Dynamic ...
  • Levers

    Levers

    Levers-Second Class. In a second class lever the fulcrum is at the end, with the load in the middle. Think of a wheelbarrow. Levers-Third Class. In a third class lever the fulcrum is again at the end, but the effort...
  • Ontology Summit 2007 Survey Response Analysis

    Ontology Summit 2007 Survey Response Analysis

    OWL Ontology. A collection of formal classes and relationships using the OWL language that are theory of what exists for some domain. [Matthew West] Reference Model. A abstract model capturing the major concepts of a systems and the relationships amongst...
  • Enhancing the Teaching Profession

    Enhancing the Teaching Profession

    # off 1 to 7: Read and fill out "Think, puzzle and explore" chart 5 minutes. Get together with your like #'s: Talk about your findings 10 minutes…, Prioritize the top 2 things you want to share…, Then have each...