Parallel Programming with Linked Data Structures
Speaker: Yan Solihin – Orlando, FL, United StatesTopic(s): Architecture, Embedded Systems and Electronics, Robotics
Abstract
Linked data structures (LDS) such as linked lists, trees, graphs, and hash tables, are used heavily in programs. They utilize pointers and rely on pointer chasing to traverse the data structures. Traditional loop-level parallelization is ineffective for LDS due to loop-carried dependence in the traversal loops. Consequently, a different parallelization strategy is needed. Parallelization can be pursued at a higher level, among the LDS primitives, such as traversal, node insertion, and node deletion. Pursuing parallelization at the LDS primitive level, however, requires a different way to reason about the correctness of operations, and requires fine-grain locking along with all its intricacies. LDS parallelization is a rarely covered topics in SC, and the aim of this tutorial is to cover techniques that can be used to achieve an effective parallelization strategy for LDS.About this Lecture
Number of Slides: 100Duration: 120 minutes
Languages Available: English
Last Updated:
Request this Lecture
To request this particular lecture, please complete this online form.
Request a Tour
To request a tour with this speaker, please complete this online form.
All requests will be sent to ACM headquarters for review.