【博士论文】利用图结构加速稀疏计算

稀疏计算（如图问题和稀疏矩阵算法中的计算）对于解决生物学、编译器设计和机器学习等领域的复杂问题至关重要。然而，在现代异构计算环境中，高效处理大规模、不规则的稀疏数据结构提出了重大挑战，必须在可扩展性和效率之间仔细权衡。现有的并行算法和计算模型通常未能充分利用稀疏数据中的固有结构，导致效率低下和可扩展性有限。这对于NP难问题尤其成问题，因为最坏情况下的解决方案速度较慢，而对于稀疏矩阵内核来说，它们是稀疏神经网络和科学计算中的瓶颈。 本论文介绍了利用稀疏数据结构特性的新算法、框架和模型。我们的贡献包括： 1. 固定参数可解算法：用于子图同构和k-团列举，利用平面性和缺乏密集子图的特性减少计算深度或工作量，从而提高并行环境中的可扩展性和效率。 1. 参数化模板图框架：高效处理执行图中的重复结构，优化并行程序分析中的数据移动。 1. 空间计算机模型与竞争模型：针对空间数据流架构的挑战，通过考虑空间局部性和竞争成本来优化稀疏通信模式。 1. 局部性优化的图布局：最小化通信成本，使现代加速器和分布式系统上的稀疏矩阵操作具有可扩展性。 1. 模型引导的实验评估：在最先进的数据流架构上对基本通信集体操作进行评估，强调了我们建模的影响。

这些贡献共同推动了稀疏计算的最新技术发展，为高性能计算的未来进步奠定了基础，可能对数据分析、科学计算和机器学习产生深远影响。