CAREER: Machine and Structure Oblivious Graph Analytics

University Of North Carolina At Charlotte, Charlotte NC

Investigators

Abstract

Graphs are fundamental mathematical tools used to represent entities and their interactions, such as intersections and roads that connect them, proteins and the genes that regulate them, or people and the social relation that binds them. In the last two decades, graphs have been applied to virtually all parts of human activity such as health, literature, national defense, and urban planning. The Internet and the information age in general increased significantly the amount of data that can be leveraged, and this has increased the size of the graphs being studied as well as the complexity of the analyses performed on them. Data analysts can not easily look into this kind of data as the current software and simple machines can not easily process the analysis and utilizing more powerful systems is often out of their skill set. Technically, the problem is that there is a wide variety of graphs to analyze (meshes of 3D objects, social networks, road networks to name a few) that have different properties in term of size, diameter, and connectivity. Even for a single problem, these differences cause differences in the algorithm that will solve the problem best; but the issue is magnified by the variety of analysis to perform. To make the matter worse, powerful workstations, accelerators, and clusters are different computing systems that are hard to leverage and could be relevant factors depending on which graph and which analysis is performed. This project answers the question posed by application scientists `How to best solve MY computational graph problem?'. The purpose of the project is to gain a clear understanding of the performance of graph algorithms on different hardware architectures, to understand which modes of operation are preferable to use, to design new algorithms for the cases where no good solutions exists, and to design better algorithms for common use cases. The project is based around a model-develop-experiment cycle to construct better algorithms geared at particular use cases. In particular it develops new algorithmic techniques to perform graph analysis by shortening critical paths, by leveraging vectorization, and by replicating data to improve load balance. Accurate modeling of the analyses is used to give insight on how to design better algorithms and to enable picking the best way to perform an analysis. Software is designed to confirm the soundness of the performed work and to provide application experts with an efficient tool that does not require high performance computing expertise. The project provides software, algorithms, and models which increase productivity of data analysts by reducing the development burden on the analyst and by efficiently using computing systems to analyze graphs in a timely fashion. The project also contributes to the education of undergraduate students by designing educational modules to train them in understanding and solving computing performance issues, and to the broadening of participation in STEM by preparing related activities and presenting them in diverse high schools and science fairs.