|
Thursday 9/10
|
Course Introduction
|
Julian Shun
|
Algorithm Engineering - An Attempt at a Definition
A Theoretician’s Guide to the Experimental Analysis of Algorithms
Slides
|
Algorithm Engineering: Bridging the Gap Between Algorithm Theory and Practice
A Guide to Experimental Algorithmics
Algorithm engineering: an attempt at a definition using sorting as an example
Algorithm Engineering for Parallel Computation
Distributed Algorithm Engineering
Experimental algorithmics
Programming Pearls
|
|
Tuesday 9/15
|
Parallel Algorithms
|
Julian Shun
|
Parallel Algorithms
Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques (Chapters 4 and 6)
Slides
|
CLRS Chapter 26 (Parallel Algorithms)
Prefix Sums and Their Applications
Algorithm Design: Parallel and Sequential
Introduction to Parallel Algorithms
Scheduling Multithreaded Computations by Work Stealing
Thread Scheduling for Multiprogrammed Multiprocessors
Problem Based Benchmark Suite
|
|
Thursday 9/17
|
Parallel Graph Traversal
Quiz
|
|
Direction-Optimizing Breadth-First Search
Chapter 7 of Shared-Memory Parallelism Can Be Simple, Fast, and Scalable
Slides Slides
|
Parallel Cluster-BFS and Applications to Shortest Paths
A Work-Efficient Parallel Breadth-First Search Algorithm (or How to Cope with the Nondeterminism of Reducers)
Internally Deterministic Parallel Algorithms Can Be Fast
SlimSell: A Vectorizable Graph Representation for Breadth-First Search
The More the Merrier: Efficient Multi-Source Graph Traversal
An Evaluation of Parallel Eccentricity Estimation Algorithms on Undirected Real-World Graphs
Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
Shared Memory Graph Frameworks
|
|
Tuesday 9/22
|
Low-Diameter Decomposition and Connectivity
|
|
Parallel Graph Decompositions Using Random Shifts
A Simple and Practical Linear-Work Parallel Algorithm for Connectivity
Slides Slides
|
Improved Parallel Algorithms for Spanners and Hopsets
|
|
Thursday 9/24
|
External-Memory Algorithms
Quiz
|
|
The input/output complexity of sorting and related problems
A Functional Approach to External Graph Algorithms
Slides Slides
|
Algorithms and Data Structures for External Memory
I/O-Complexity of Graph Algorithms
External-Memory Graph Algorithms
Beyond Synchronous: New Techniques for External-Memory Graph Connectivity and Minimum Spanning Forest
Fundamental parallel algorithms for private-cache chip multiprocessors
Parallel External Memory Graph Algorithms
Efficient Parallel and External Matching
External-Memory Computational Geometry
External Memory Geometric Data Structures
A Bulk-Parallel Priority Queue in External Memory with STXXL
|
|
Tuesday 9/29
|
Cache-Oblivious Algorithms
|
|
Cache-Oblivious Algorithms
Engineering a cache-oblivious sorting algorithm
Slides Slides
|
Cache-Oblivious Algorithms and Data Structures
Cache Oblivious Distribution Sweeping
Cache-oblivious databases: Limitations and opportunities
An Optimal Cache-Oblivious Priority Queue and Its Application to Graph Algorithms
Cache-Oblivious B-Trees
Cache-oblivious streaming B-trees
An experimental comparison of cache-oblivious and cache-conscious programs
|
|
Thursday 10/1
|
Sorting Algorithms
|
|
Low Depth Cache-Oblivious Algorithms (except Section 5)
The Case for a Learned Sorting Algorithm
Slides Slides
|
Super Scalar Sample Sort
Parallel Merge Sort
Optimal and sublogarithmic time randomized parallel sorting algorithms
A comparison of sorting algorithms for the connection machine CM-2
Efficient implementation of sorting on multi-core SIMD CPU architecture
Highly scalable parallel sorting
Designing efficient sorting algorithms for manycore GPUs
TritonSort: A Balanced Large-Scale Sorting System
Sort Benchmark
|
|
Tuesday 10/6
|
Graph Processing Frameworks
Quiz
|
|
GraphChi: Large-Scale Graph Computation on Just a PC
Scaling Parallel Algorithms to Massive Datasets using Multi-SSD Machines
|
Scalability! But at what COST?
External Memory Graph Frameworks
Shared Memory Graph Frameworks
Distributed Memory Graph Frameworks
|
|
Thursday 10/8
|
Pre-proposal Meeting
|
|
|
|
|
Tuesday 10/13
|
No class
|
|
|
|
|
Thursday 10/15
|
Locality in Graph Processing
|
|
Making Caches Work for Graph Analytics
Rebo: Locality-Aware Graph Processing via Reordering and Blocking
|
Reducing Pagerank Communication via Propagation Blocking
GraphIt: A High-Performance DSL for Graph Analytics
CoroGraph: Bridging Cache Efficiency and Work Efficiency for Graph Algorithm Execution
Cache-Efficient Fork-Processing Patterns on Large Graphs
Locality Optimizations
Shared Memory Graph Frameworks
|
|
Friday 10/16
|
Project Proposal due today
|
|
|
|
|
Tuesday 10/20
|
Compression
Quiz
|
|
An Experimental Analysis of a Compact Graph Representation
Decoding billions of integers per second through vectorization
|
Compact Representations of Separable Graphs
CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression
Chapter 8 of Shared-Memory Parallelism Can Be Simple, Fast, and Scalable
Graph Compression
Graph Partitioning and Reordering
|
|
Thursday 10/22
|
Peeling and Subgraph Finding Algorithms
|
|
Julienne: A Framework for Parallel Graph Algorithms using Work-efficient Bucketing
Parallel Clique Counting and Peeling Algorithms
|
Parallel k-Core Decomposition: Theory and Practice
|
|
Tuesday 10/27
|
Parallel Shortest Paths
Quiz
|
|
Delta-stepping: a parallelizable shortest path algorithm
Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths
|
Optimizing Ordered Graph Algorithms with GraphIt
Julienne: A Framework for Parallel Graph Algorithms using Work-efficient Bucketing
Parallel Shortest Paths Using Radius Stepping
An Experimental Study of a Parallel Shortest Path Algorithm for Solving Large-Scale Graph Instances
DSMR: A Parallel Algorithm for Single-Source Shortest Path Problem
Work-Efficient Parallel GPU Methods for Single-Source Shortest Paths
A Randomized Parallel Algorithm for Single-Source Shortest Path
Randomized Speedup of the Bellman-Ford Algorithm
The SprayList: A Scalable Relaxed Priority Queue
|
|
Thursday 10/29
|
Dynamic Graph Algorithms
|
|
Work-Efficient Parallel Union-Find
Parallel Batch-Dynamic Algorithms for k-Core Decomposition and Related Graph Problems
|
Dynamic Graph Algorithms
Streaming Graph Frameworks
Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
|
|
Tuesday 11/3
|
Streaming Graph Processing
Quiz
|
|
Low-Latency Graph Streaming Using Compressed Purely-Functional Trees
PaC-trees: supporting parallel and compressed purely-functional collections
|
Streaming Graph Frameworks
|
|
Thursday 11/5
|
Integer Sorting
|
|
Optimal and sublogarithmic time randomized parallel sorting algorithms (Sections 1-3)
Parallel Integer Sort: Theory and Practice
|
Theoretically-Efficient and Practical Parallel In-Place Radix Sorting
A comprehensive study of main-memory partitioning and its application to large-scale comparison- and radix-sort
Practical Massively Parallel Sorting
Engineering a Multi-core Radix Sort
PARADIS: An Efficient Parallel Algorithm for In-place Radix Sort
A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs
Sorting Data on Ultra-Large Scale with RADULS
Even Faster Sorting of (Not Only) Integers
|
|
Tuesday 11/10
|
Parallel In-Place Algorithms
|
|
Theoretically-Efficient and Practical Parallel In-Place Radix Sorting
Parallel In-Place Algorithms: Theory and Practice
|
Engineering In-place (Shared-memory) Sorting Algorithms
|
|
Thursday 11/12
|
Aggregation and Join
Quiz
|
|
Efficient Sorting, Duplicate Removal, Grouping, and Aggregation
A Top-Down Parallel Semisort
|
Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited
Main-Memory Hash Joins on Modern Processor Architectures
Sort vs. Hash Join Revisited for Near-Memory Execution
Many-query join: efficient shared execution of relational joins on modern hardware
An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory
High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems
|
|
Friday 11/13
|
Mid-term report due today
|
|
|
|
|
Tuesday 11/17
|
Clustering
|
|
Theoretically-Efficient and Practical Parallel DBSCAN
Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering
|
Parallel Index-Based Structural Graph Clustering and Its Approximation
|
|
Thursday 11/19
|
Hierarchical Clustering
Quiz
|
|
Optimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering
Fully-Dynamic Parallel Algorithms for Single-Linkage Clustering
|
ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain
|
|
Tuesday 11/24
|
Low-Dimensional Nearest Neighbors
|
|
Parallel Nearest Neighbors in Low Dimensions with Batch Updates
Parallel kd-tree with Batch Updates
|
Computational Geometry: Algorithms and Applications
|
|
Thursday 11/26
|
No class
|
|
|
|
|
Tuesday 12/1
|
High-Dimensional Nearest Neighbors
Quiz
|
|
DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node
ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms
|
Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations
|
|
Thursday 12/3
|
Project Presentations
|
|
|
|
|
Friday 12/4
|
Final report due today
|
|
|
|
|
Tuesday 12/8
|
Final Project Meeting
|
|
|
|
|
Thursday 12/10
|
Final Project Meeting
|
|
|
|