Optimizing Dynamic-Graph Data Structures on Multicores with the Locality-First Strategy

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=7mF-ZptnO9k


Duration: 47:43
312 views
8

Helen Xu
https://simons.berkeley.edu/talks/helen-xu-2023-09-18
Dynamic Graphs and Algorithm Design

Developing fast codes to solve large problems (on the order of gigabytes and up to terabytes) efficiently on multicores requires taking advantage of underlying multicore hardware features. Specifically, software systems must be optimized simultaneously to take advantage of the multiple cores via parallelism and the memory subsystem via locality. Optimizing for either of these features is notoriously difficult, however, and combining them only adds to the complexity.
This talk will present a case study of optimizing dynamic-graph data structures for locality. Real-world dynamic graphs present challenges to locality and parallelism due to their naturally-occurring sparse and skewed structure.



Other Videos By Simons Institute for the Theory of Computing


2023-09-20Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates
2023-09-20Online List Labeling: Breaking the log^2 n Barrier
2023-09-20Practical Dynamic Graph Algorithms: Data Structures and Connections Between Models
2023-09-20Decremental Shortest Paths against an Adaptive Adversary
2023-09-19Dynamic Matching: Rounding & Sparsification (And New Tools)
2023-09-19Parallel Batch-Dynamic Graph Representations
2023-09-19Dynamic Algorithms for 𝑘-center on Graphs
2023-09-19A Blackbox Reduction for Adaptive Adversaries using Differential Privacy
2023-09-19Recent Progress on Sublinear Time Algorithms for Maximum Matching: Upper Bounds
2023-09-18Parallelism in Dynamic Graph Algorithms
2023-09-18Optimizing Dynamic-Graph Data Structures on Multicores with the Locality-First Strategy
2023-09-18Recent Advances in Diversity Maximization in the Offline and Composable Coreset Models
2023-09-18Approximating Edit Distance in the Fully Dynamic Model
2023-09-18Lightning Talks
2023-09-12Dynamic Graph Algorithms: What We Know and What We Don’t | Richard M. Karp Distinguished Lecture
2023-09-08Probabilistic and Logical Circuits for Tractable Causal Reasoning
2023-09-08Probabilistic Reasoning and Learning for Trustworthy AI
2023-09-08Sampling and Approximately Counting CNF Formula Solutions in the Local Lemma Regime
2023-09-08Massively Parallel Join Algorithms
2023-09-08Relational Programming
2023-09-08Title: Research Interests and Latest Works


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Dynamic Graphs and Algorithm Design
Helen Xu