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电路的分而治之方法，对超大型图形和网络进行聚类和分析，以及解决涉及不同目标和约束的各种划分问题实例。这将对许多科学工程学科，商业公司，非营利组织&，以及从依赖于图分区的各种应用程序域启用和促进的计算结果中受益的个人。最后，该项目将研究与教育计划相结合，重点是通过课程，软件工程项目，暑期学院和研究机会进行本科生和研究生教育和指导;以及社区发展和推广计划，旨在通过提供广泛的文档，在线教程和组织相关会议和研讨会来促进广泛采用所产生的软件基础设施。