CAREER: Machine and Structure Oblivious Graph Analytics

图形是基本的数学工具，用于表示实体及其相互作用，例如连接它们的十字路口和道路，蛋白质和调节它们的基因，或者人们和将他们联系在一起的社会关系。在过去的二十年里，图表几乎被应用于人类活动的各个方面，如健康、文学、国防和城市规划。总的来说，互联网和信息时代显著地增加了可以利用的数据量，这增加了所研究的图的大小以及对它们执行的分析的复杂性。数据分析师无法轻松查看这类数据，因为当前的软件和简单的机器无法轻松处理分析，而且利用更强大的系统通常超出了他们的技能范围。从技术上讲，问题在于有各种各样的图形需要分析（3D对象的网格、社交网络、道路网络等等），这些图形在大小、直径和连接性方面具有不同的属性。即使对于单个问题，这些差异也会导致最佳解决问题的算法的差异；但是，要执行的各种分析放大了这个问题。更糟糕的是，强大的工作站、加速器和集群是难以利用的不同计算系统，并且可能成为执行哪个图和哪个分析的相关因素。这个项目回答了应用科学家提出的问题“如何最好地解决我的计算图问题？”该项目的目的是为了清楚地了解图形算法在不同硬件架构上的性能，了解哪种操作模式更适合使用，为没有好的解决方案的情况设计新的算法，并为常见的用例设计更好的算法。该项目基于模型-开发-实验周期，以构建针对特定用例的更好算法。特别是，它开发了新的算法技术，通过缩短关键路径，利用向量化和通过复制数据来改善负载平衡来执行图形分析。分析的精确建模用于洞察如何设计更好的算法，并能够选择执行分析的最佳方法。软件的设计是为了确认所执行工作的可靠性，并为应用专家提供一个不需要高性能计算专业知识的有效工具。该项目提供了软件、算法和模型，通过减少数据分析人员的开发负担和有效地使用计算系统及时分析图形来提高数据分析人员的生产力。该计划亦透过设计教育模块，训练大学生理解和解决计算性能问题，为教育他们作出贡献。此外，该计划亦透过筹备相关活动，并在不同高中和科学展览中展示，扩大STEM的参与范围。

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.