Parallel Graph AlgorithmsLecture OutlineRouting in transportation networksInternet and the WWWScientific ComputingLarge-scale data analysisData Analysis and Graph Algorithms in Systems BiologyGraph –theoretic problems in social networksNetwork Analysis for Intelligence and SurvellianceResearch in Parallel Graph AlgorithmsCharacterizing Graph-theoretic computations (2/2)Slide 12HistoryThe PRAM modelThe Helman-JaJa modelPRAM Pros and ConsBuilding blocks of classical PRAM graph algorithmsPrefix SumsParallel PrefixList ranking IllustrationList Ranking key ideaConnected ComponentsShiloach-Vishkin algorithmAn example higher-level algorithmData structures: graph representationData structures in (parallel) graph algorithmsSlide 28Graph Algorithms on today’s systemsThe locality challenge “Large memory footprint, low spatial and temporal locality impede performance”The parallel scaling challenge “Classical parallel graph algorithms perform poorly on current parallel systems”Optimizing BFS on cache-based multicore platforms, for networks with “power-law” degree distributionsGraph traversal (BFS) problem definitionParallel BFS StrategiesA deeper dive into the “level synchronous” strategyPerformance ObservationsImproving locality: Vertex relabelingImproving locality: OptimizationsImproving locality: Cache blockingVertex relabeling heuristicArchitecture-specific OptimizationsExperimental SetupImpact of optimization strategiesCache locality improvementParallel performance (Orkut graph)Slide 46Parallel Single-source Shortest Paths (SSSP) algorithms∆ - stepping algorithm [MS03]∆ - stepping algorithm: illustrationSlide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61No. of phases (machine-independent performance count)Average shortest path weight for various graph families ~ 220 vertices, 222 edges, directed graph, edge weights normalized to [0,1]Last non-empty bucket (machine-independent performance count)Number of bucket insertions (machine-independent performance count)Slide 66Betweenness CentralityAlgorithms for Computing BetweennessOur New Parallel AlgorithmsParallel BC AlgorithmParallel BC Algorithm IllustrationSlide 72Slide 73Slide 74Slide 75Graph traversal step analysisGraph Traversal Step locality analysisSlide 78Slide 79Accumulation step locality analysisCentrality Analysis applied to Protein Interaction NetworksSlide 82Community IdentificationAgglomerative Clustering, ParallelizationGraph Analysis with cache-based multicore systemsDesigning fast parallel graph algorithmsReview of lectureFuture Research ChallengesThank you!CS267/EngC233 Spring 2010April 15, 2010Parallel Graph AlgorithmsKamesh Madduri [email protected] Berkeley National Laboratory•Applications•Review of key results•Case studies: Graph traversal-based problems, parallel algorithms–Breadth-First Search–Single-source Shortest paths–Betweenness Centrality–Community IdentificationLecture OutlineRoad networks, Point-to-point shortest paths: 15 seconds (naïve) 10 microsecondsRouting in transportation networksH. Bast et al., “Fast Routing in Road Networks with Transit Nodes”, Science 27, 2007.•The world-wide web can be represented as a directed graph–Web search and crawl: traversal–Link analysis, ranking: Page rank and HITS–Document classification and clustering•Internet topologies (router networks) are naturally modeled as graphsInternet and the WWW•Reorderings for sparse solvers–Fill reducing orderingsPartitioning, eigenvectors–Heavy diagonal to reduce pivoting (matching) •Data structures for efficient exploitation of sparsity•Derivative computations for optimization–Matroids, graph colorings, spanning trees•Preconditioning–Incomplete Factorizations–Partitioning for domain decomposition–Graph techniques in algebraic multigridIndependent sets, matchings, etc.–Support TheorySpanning trees & graph embedding techniquesScientific ComputingB. Hendrickson, “Graphs and HPC: Lessons for Future Architectures”, http://www.er.doe.gov/ascr/ascac/Meetings/Oct08/Hendrickson%20ASCAC.pdfImage source: Yifan Hu, “A gallery of large graphs”Image source: Tim Davis, UF Sparse Matrix Collection.•Graph abstractions are very useful to analyze complex data sets.•Sources of data: petascale simulations, experimental devices, the Internet, sensor networks•Challenges: data size, heterogeneity, uncertainty, data qualityLarge-scale data analysisAstrophysics: massive datasets, temporal variations Bioinformatics: data quality, heterogeneitySocial Informatics: new analytics challenges, data uncertainty Image sources: (1) http://physics.nmt.edu/images/astro/hst_starfield.jpg (2,3) www.visualComplexity.com•Study of the interactions between various components in a biological system•Graph-theoretic formulations are pervasive:–Predicting new interactions: modeling–Functional annotation of novel proteins: matching, clustering–Identifying metabolic pathways: paths, clustering–Identifying new protein complexes: clustering, centralityData Analysis and Graph Algorithms in Systems BiologyImage Source: Giot et al., “A Protein Interaction Map of Drosophila melanogaster”, Science 302, 1722-1736, 2003.Image Source: Nexus (Facebook application)Graph –theoretic problems in social networks–Community identification: clustering–Targeted advertising: centrality–Information spreading: modeling•[Krebs ’04] Post 9/11 Terrorist Network Analysis from public domain information•Plot masterminds correctly identified from interaction patterns: centrality•A global view of entities is often more insightful•Detect anomalous activities by exact/approximate subgraph isomorphism.Image Source: http://www.orgnet.com/hijackers.htmlNetwork Analysis for Intelligence and SurvellianceImage Source: T. Coffman, S. Greenblatt, S. Marcus, Graph-based technologies for intelligence analysis, CACM, 47 (3, March 2004): pp 45-47Research in Parallel Graph AlgorithmsApplication AreasMethods/ProblemsArchitecturesGraph AlgorithmsTraversalShortest PathsConnectivityMax Flow ………GPUsFPGAsx86 multicoreserversMassively multithreadedarchitecturesMulticoreClustersCloudsSocial NetworkAnalysisWWWComputational BiologyScientific Computing EngineeringFind central entitiesCommunity detectionNetwork dynamicsData sizeProblemComplexityGraph partitioningMatchingColoringGene regulationMetabolic pathwaysGenomicsMarketingSocial SearchVLSI
View Full Document
Unlocking...