CAREER: Scalable Combinatorial Scientific Computing

摘要：组合算法是科学计算的重要使能技术，尤其适用于大规模问题和高性能计算。该项目的总体目标是开发1)用于解决极端规模架构上基于图和超图的组合问题的数学和计算基础设施；2)用于分析复杂和多价交互网络的技术和工具。在本项目中，开发了有效的新型组合模型，如超图，k-部超图和有向超图模型，用于模拟大规模科学应用的复杂工作流程（计算，通信和数据依赖以及数据访问模式）以及化学和生物实体的复杂相互作用。针对图和超图的聚类和分区以及动态负载平衡问题，设计了基于多层次框架的可扩展算法。可扩展的图着色技术和基于图搜索的语义图分析技术是在可扩展的分布式内存图/超图运行时中间件之上开发的。这项工作的技术影响将是为上述具有计算挑战性的问题设计有效的模型和算法。因此，在许多科学领域，这项工作将允许使用并行计算，这在以前是不可能的。这个项目的教育和推广活动包括一个针对弱势群体的高中生的暑期项目，研究生课程的显著扩展，本科生参与研究项目，以及通过多学科项目对研究生进行教育。在项目中开发的新模型和算法的实现将作为开源分发，以最大限度地提高研究结果的影响和传播。

CAREER: Scalable Combinatorial Scientific ComputingPI: Umit V. CatalyurekAbstract:Combinatorial algorithms are an important enabling technology for scientific computing, especially for large-scale problems and high performance computing. The overarching goals of this project are development of 1) a mathematical and computational infrastructure for solving graph and hypergraph-based combinatorial problems on extreme-scale architectures and 2) techniques and tools for analysis of complex and multivalent interaction networks.In this project, effective novel combinatorial models, such as hypergraph, k-partite hypergraph and directed hypergraph models, are developed for modeling complex workflows (computation, communication and data dependencies, and data access patterns) of large-scale scientific applications and the complicated interactions of chemical and biological entities. New scalable algorithms, based on a multi-level framework, are designed for graph and hypergraph clustering and partitioning, and dynamic load balancing problems. Scalable graph coloring techniques and graph search-based analysis techniques for semantic graphs are developed on top of an extensible distributed memory graph/hypergraph runtime middleware.The technical impact of this work will be in designing efficient models and algorithms for the above mentioned computationally challenging problems. Hence, in many fields of science the work will allow the use of parallel computing where it was not possible before. The education and outreach activities of this project include a summer program for high school students from underrepresented groups, significant expansion of graduate courses, undergraduate student involvement in research projects, and graduate student education through multi-disciplinary projects. The implementations of the novel models and algorithms developed in the project will be distributed as open source to maximize the impact and dissemination of the research results.