Abstract
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.