CS4395 Independent Research 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.


Locationhttps://txstate.zoom.us/my/martin.burtscher (no password required)



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