Content area
With the rise of social networks, search engines, recommender systems, and data science, efficiently processing large graphs has become crucial. The underlying irregular programs often exhibit input-dependent control flow and memory accesses, posing challenges in implementation, parallelization, and optimization. This dissertation explores the systematic design of benchmark suites for this important domain. I extracted key code patterns, styles, and hybridization techniques from existing graph codes, generalized them, and created thousands of meaningful parallel irregular codes based on them. The resulting suites contain two orders of magnitude more codes than preexisting suites and even more inputs. To handle these large numbers, I automated the generation and used this approach to create three benchmark suites: Indigo1 focuses on important code patterns, Indigo2 targets frequently used styles, and Indigo3 introduces hybrid parallelization strategies and deliberately planted software defects. Additionally, I developed the ECL Suite of validated HPC graph codes. The four suites facilitate performance evaluation, verification, and education, providing the community with a diverse range of irregular codes for extensive research. This dissertation not only offers insights into parallelization strategies but also enhances code verification methods, potentially saving debugging time and enhancing programmer efficiency. Moreover, it serves as an educational resource for students and developers, imparting knowledge on innovative parallelization techniques.