GraphIt - A High-Performance Graph DSL

on YouTube ↗23m

" summary

DSL that separates algorithm from schedule and a scheduling language that composes push/pull direction, partitioning for cache, parallelization, NUMA and data-layout choices into a single representation called the graph iteration space. Compiler generates C++ and an autotuner searches schedules for a given graph; tuned PageRank achieves >23× over a naive version on 2-socket 24-core hardware, GraphIt tops six frameworks on 24 of 32 experiments by up to 4.8× and trims code size by up to an order of magnitude.

AI-written summary · about

" chapters (24)

1. 0:00Intro
2. 0:52Performance is Important
3. 1:13PageRank Example in C++
4. 1:50Hand-Optimized C++
5. 3:14Outline
6. 3:29Power-Law Graphs
7. 4:03Bounded-Degree Graphs
8. 4:21Graph Algorithms
9. 4:38Data-Driven Algorithms
10. 4:56Graph Execution Hardware
11. 5:09Push Traversal
12. 5:56Partitioning
13. 6:17Optimization Tradeoff Space
14. 9:16Algorithm Language
15. 10:50Scheduling Language
16. 12:32Speedups of Schedules
17. 13:20Schedule Representation
18. 13:51Iteration Spaces
19. 14:17Graph Iteration Space
20. 16:08Schedule 4
21. 16:30Autotuner
22. 17:11State of the Art and Graphit
23. 18:31Consistent High-Performance
24. 19:20Summary