SI2-SSE: Software Infrastructure For Partitioning Sparse Graphs on Existing and Emerging Computer Architectures

找到大型、稀疏和非结构化图的良好划分的算法是为需要处理和分析此类图的问题开发有效且计算效率高的方法的重要技术。因此，它们在高性能计算、科学计算、超大规模集成电路设计、数据挖掘、模式识别、计算机图形学、网络分析、数据库和地理信息系统、运筹学、优化和调度等许多不同领域得到了广泛的应用。该项目将开发并提供一个软件基础设施，为大型、稀疏和非结构化图提供广泛的图分区工具。该基础设施将使用现代面向对象的软件工程原则来构建，这将促进它们的模块化、用户可扩展性、可维护性和社区开发；并结合新的图分区算法，可以扩展到包含数十亿节点的图，并促进在不同计算体系结构上对不同类型的图进行分区。该软件基础设施将能够在包含数万个处理节点和数十亿个网格元素的并行系统上有效执行科学数值模拟，开发用于在不同芯片架构上合成超大型VLSI电路的分而治之方法，对超大型图形和网络进行聚类和分析。并解决了涉及不同目标和约束的大范围分区问题实例。这将对许多科学和工程学科、商业公司、非营利组织和个人产生积极的影响，这些人受益于依赖图划分的各种应用程序领域所支持和促进的计算结果。最后，该项目将研究与教育计划结合起来，重点是本科和研究生教育，并通过课程、软件工程项目、暑期学院和研究机会进行指导；社区发展和扩展计划旨在通过提供广泛的文档、在线教程以及在相关会议和研讨会上组织会议来促进所产生的软件基础结构的广泛采用。

Algorithms that find good partitionings of large, sparse, and unstructured graphs represent an important technique for developing effective and computationally efficient approaches for problems that need to process and analyze such graphs. As a result, they have found extensive applications in many diverse areas such as high-performance computing, scientific computing, VLSI design, data mining, pattern recognition, computer graphics, network analysis, database and geographical information systems, operations research, optimization, and scheduling. This project will develop and make available a software infrastructure that provides a broad range of graph partitioning tools for large, sparse, and unstructured graphs. This infrastructure will be built using modern object-oriented software engineering principles that will facilitate their modularity, user-extensibility, maintainability, and community development; and incorporate novel graph partitioning algorithms that can scale to graphs containing billions of nodes and facilitate the partitioning of different types of graphs on different computing architectures. This software infrastructure will enable the efficient execution of scientific numerical simulations on parallel systems containing tens of thousands of processing nodes and billions of mesh elements, the development of divide-and-conquer approaches for synthesizing very large VLSI circuits on different chip architectures, the clustering and analysis of very large graphs and networks, and the solution of a wide-range of partitioning problem instances involving different objectives and constraints.This will positively impact numerous science & engineering disciplines, commercial companies, non-profit organizations, and individuals that benefit from the results of the computations that are enabled and facilitated by the various application domains that rely on graph partitioning. Finally, the project integrates the research with an educational plan focused on undergraduate and graduate education and mentoring through courses, software engineering projects, summer institutes, and research opportunities; and a community development and an outreach plan designed to promote broad adoption of the resulting software infrastructure by providing extensive documentation, online tutorials, and organizing meetings at relevant conferences and workshops.