Parallel Processing and Minimum Spanning TreesOverviewWhat is Parallel Processing?Slide 4Parallel Processing in NatureSlide 6Slide 7Parallel Processing vs. MultitaskingSlide 9Amdahl’s LawSlide 11Slide 12Slide 13Challenges in Parallel ProcessingSlide 15Slide 16Slide 17Slide 18Slide 19Undirected graph and 3 of its spanning treesSpanning treesFinding a spanning treeMinimizing costsMinimum-cost spanning treesSlide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Applications of Spanning TreesKruskal’s algorithmSpanning TreeSlide 40Kruskal’s AlgorithmSlide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Compare Prim and KruskalSlide 52Slide 53Prim’s algorithmSlide 55Slide 56Slide 57Slide 58Slide 59Slide 60Parallel Processing and Minimum Spanning TreesProf. Sin-Min LeeDept. of Computer Science,San Jose State UniversityOverview•What is Parallel Processing•Parallel Processing in Nature•Parallel Processing vs. Multitasking•Amdahl’s Law•Challenges in Parallel ProcessingWhat is Parallel Processing?•How to make machines solve problems better and faster?•Physical barriers limit the extent to which single processor performance can be improved—Clock Speed & Heat Dissipation•The next most obvious solution is to distribute the computing load among several processorsWhat is Parallel Processing?•Parallel Processing encompasses a wide variety of different things:•Intel Core Duo, Quad, Cell multiprocessors, networked and distributed computer systems, SETI@Home, Folding@Home, neural nets are all examplesParallel Processing in Nature•The world’s most powerful parallel processor comes standard•For everything else there’s American Express…Parallel Processing in Nature•For humans parallel processing comes easy•Human VisionColor, Motion,Depth, ShapeParallel Processing in Nature•Machines that are more like us, and hence more useful, will need to be able to process information more like us—in parallel.•Parallel Processing is key element in pattern recognition which distinguishes human & machine intelligence•This is not an easy hurdleParallel Processing vs. Multitasking•Today, computers are great at multi-tasking, but…•Multi-tasking only creates the illusion of parallel processing•The processor must switch between activities—it is only the speed with which it does so that creates the illusion of simultaneous execution•The illusion is most easily shattered when running virus scan while attempting to do anything elseParallel Processing vs. Multitasking•Think about it this way:•Multi-tasking•Parallel ProcessingAmdahl’s Law•Consider a single processor•Or two…•We tend to think that 2x as much work will be done in the same time•Or that the same amount of work will be done in half the timeAmdahl’s Law•Do n processors imply that a computational job should complete in 1/n time?•Sadly, no…Amdahl’s Law•1967 Gene Amdahl recognizes the interrelationship of all components•Overall speedup of a system depends on the speedup of a particular component & how much that component is used•S = 1/([1- f] + f / k)•S = overall system speed•f = fraction of the work performed by the faster component•k = speedup of new componentAmdahl’s Law•Additionally, no matter how well (or much) you parallelize an application there will always be a small portion of work that must be done serially.•Other processors must simply sit and wait in this interval•Every algorithm has a sequential part that limits potential speedupChallenges in Parallel Processing•Not always obvious where to “split” workload or even possible.•If you don’t use it, you lose it…programs not specifically written for parallel architecture run no more efficiently on parallel systemsChallenges in Parallel Processing•Connecting your CPUs•Dynamic vs Static—connections can change from one communication to next•Blocking vs Nonblocking—can simultaneous connections be present?•Connections can be complete, linear, star, grid, tree, hypercube, etc.•Bus-based routing•Crossbar switching—impractical for all but the most expensive super-computers•2X2 switch—can route inputs to different destinationsChallenges in Parallel Processing•Dealing with memory•Various options:•Global Shared Memory•Distributed Shared Memory•Global shared memory with separate cache for processors•Potential Hazards:•Individual CPU caches or memories can become out of synch with each other. “Cache Coherence”•Solutions:•UMA/NUMA machines•Snoopy cache controllers•Write-through protocolsIn the design of electronic circuitry, it is often necessary to make the pins of several components electrically equivalent by wiring them together. To interconnect a set of n pins, we can use an arrangement of n – 1 wires, each connecting two pins. Of all such arrangements, the one that uses the least amount of wire is usually the most desirable. We can model this wiring problem with a connected, undirected graph G = (V,E), where V is the set of pins, E is the set of possible interconnections between pairs of pins, and for each edge (u, v) ∈ E, we have a weight w(u,v) specifying the cost (amount of wire needed) to connect u and v.We then wish to find an acyclic subset T E that connects all of the vertices and whose total weightis minimized. Since T is acyclic and connects all of the vertices, it must form a tree, which we call a spanning tree since it “spans” the graph G. We call the problem of determining the tree T the minimum-spanning-tree problem.Undirected graph and 3 of its spanning treesUndirected GraphSpanning TreesSpanning trees•Suppose you have a connected undirected graph–Connected: every node is reachable from every other node–Undirected: edges do not have an associated direction•...then a spanning tree of the graph is a connected subgraph in which there are no cyclesA connected,undirected graphFour of the spanning trees of the graphFinding a spanning tree•To find a spanning tree of a graph, pick a node and call it part of the spanning tree do a search from the initial node: each time you find a node that is not in the spanning tree, add to the spanning tree both the new node a nd the edge you followed to get to itAn undirected graph Result of a BFSstarting from topResult of a DFSstarting from topMinimizing costs•Suppose you want to supply a set of houses (say, in a new
View Full Document