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

SI2-SSE：用于在现有和新兴计算机架构上分区稀疏图的软件基础设施

• 批准号: 1048018
• 负责人: George Karypis
• 金额: $ 49.98万
• 依托单位: University of Minnesota-Twin Cities
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-15 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1048018&HistoricalAwards=false
• 关键词: SI2; SSE; Software; Infrastructure; Partitioning

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.

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