CS4395 Independent Research Presentation

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.

 

Locationhttps://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