CS4395 INDEPENDENT STUDY PRESENTATION
Title: Identifying Efficient Parallelization Patterns for Irregular Graph Algorithms
Presenter: Avery Vanausdal
Advisor: Martin Burtscher
Date/Time: Friday, August 5th @ 3:00 p.m.
Location: https://txstate.zoom.us/my/martin.burtscher (no password required)
Abstract:
Parallelization is a powerful technique for improving the performance of applications, but there are many “irregular” algorithms that are inherently difficult to efficiently parallelize. Small changes in the implementation of irregular code can have a large effect on overall efficiency. To identify useful parallelization patterns, I implemented many variations of four irregular graph algorithms using the C++ concurrency support library. Comparing runtimes on the same hardware and inputs, I was able to identify which patterns typically perform the best and on which types of graphs. My results show that the optimal strategy for a given algorithm and input is generally at least 30 times faster than the worst strategy.
Deadline: Aug. 8, 2022, midnight