Title: Designing Benchmark Suites of Irregular Programs
Student: Yiqian Liu (y_l120@txstate.edu)
Advisor: Martin Burtscher
Date and Time: Fri Dec 9 2022 2:00 PM CST
Location: https://txstate.zoom.us/my/martin.burtscher
Abstract:
With the rise of social networks, search engines, recommender systems, and data science, efficiently processing large-scale graphs has become an important workload. The underlying irregular programs tend to exhibit input-dependent and dynamically changing control flow and memory accesses, making them challenging to implement, parallelize, and optimize. In this dissertation, I study how to systematically design benchmark suites for this important domain. Conventional suites with dozens of programs and inputs are too small to sufficiently capture the wide variety of runtime behavior and input dependence of irregular programs. As a remedy, I propose a new benchmark suite design method. First, I extract the key code patterns, implementation styles, and hybridization techniques from existing graph codes, then I generalize them, and finally I methodically build variations thereof to create thousands of meaningful parallel irregular codes. The resulting benchmark suites contain two orders of magnitude more codes than preexisting suites and even more inputs. Additionally, the new suites include codes with planted bugs to enable verification tool evaluation. Designing and maintaining such large sets of codes and inputs by hand is infeasible. Hence, I created a way to automate the suite generation. Moreover, I added filters that allow users to only study a desired subset of the suite. So far, I have successfully employed this methodology to create two benchmark suites, both of which contain more than 1000 codes. The first suite focuses on important code patterns found in irregular programs. The second suite targets frequently-used implementation styles and hybridization techniques. The third suite will be based on validated HPC graph codes. These benchmark suites can be used for performance evaluation, verification, and even education purposes. They provide the community, for the first time, with the needed large variety of irregular codes to extensively research this important domain.
Deadline: Jan. 6, 2023, midnight