CEGMA: Coordinated Elastic Graph Matching Acceleration for Graph Matching Networks
CEGMA: Coordinated Elastic Graph Matching Acceleration for Graph Matching Networks
复制标题
DOI：
10.1109/hpca56546.2023.10070956
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Yuezhen Dai;Youtao Zhang;Xulong Tang
中科院分区：
文献类型：
--
作者：
Yuezhen Dai;Youtao Zhang;Xulong Tang
最近提出的图匹配网络模型(GMN)有效地提高了图相似性分析任务的推理精度。GMN通常将图对作为输入，嵌入节点特征，并在图之间进行节点匹配以进行相似性分析。虽然GMN具有很高的推理精度，但GMN中的全对全节点匹配阶段引入了二次计算复杂性和过多的内存访问，导致了大量的计算和内存开销，这是现有方法无法处理的。在本文中，我们提出了协调弹性图匹配加速器(CEGMA)，这是一个软硬件协同设计的加速器，以应对GMN的挑战。具体地说，通过利用输入图中的重复子图，我们开发了一种弹性匹配过滤器来显著降低二次计算开销。通过挖掘节点特征访问带来的大量数据重用问题，提出了一种融合交叉图相似度计算和图内计算的交叉图协调器，以增强数据的局部性。实验结果表明，与现有的GPU实现和GNN加速器相比，CEGMA在GMN计算上的平均加速比分别达到了353倍和6.5倍。
The recently proposed Graph Matching Network models (GMNs) effectively improve the inference accuracy of graph similarity analysis tasks. GMNs often take graph pairs as input, embed nodes features, and match nodes between graphs for similarity analysis. While GMNs deliver high inference accuracy, the all-to-all node matching stage in GMNs introduces quadratic computing complexity with excessive memory accesses, resulting in significant computing and memory overhead that cannot be handled by existing approaches. In this paper, we propose the Coordinated Elastic Graph Matching Accelerator (CEGMA), a software and hardware co-design accelerator to address the challenges of GMNs. Specifically, by exploiting duplicate subgraphs in the input graphs, we develop an elastic matching filter to significantly reduce the quadratic computing overhead. By exploring the substantial data reuses oriented from accessing node features, we propose a cross-graph coordinator that fuses cross-graph similarity computing with intra-graph computing to enhance data locality. Experimental results show that, on average, CEGMA achieves 353× and 6.5× speedups in GMN computing compared to state-of-the-art GPU implementation and GNN accelerators, respectively.