近日，2023年国际设计自动化会议（Design Automation Conference，DAC 2023）录用结果揭晓，实验室赵进博士、黄禹博士、博士生齐豪（导师金海教授）、硕士生蒋子涵（导师毛伏兵博士）的4篇论文均被录用。
赵进的论文题目为“SaGraph: A Similarity-aware Hardware Accelerator for Temporal Graph Processing”。现实世界的图数据通常随着时间不断变化，同时大量图计算应用对挖掘这些图数据随着时间变化的特征越来越感兴趣。例如，分析事物之间距离的变化，研究社交网络直径的变化以及挖掘网页排名随时间的演变等。这些应用通常需要对这些图数据的多个图快照执行特定的图算法，通常将其称为时序图处理。现有面向时序图处理的系统和硬件解决方案对这些图快照之间交集的相关图数据仍存在着严重的不规则数据访问行为，导致高昂的片外数据传输开销。为此，赵进在论文中提出了相似性感知的时序图处理加速器SaGraph，以从本质上高效地解决此问题。SaGraph能够动态且有效地协调不同快照图处理之间的图遍历行为以及自适应地缓存图顶点状态数据，充分利用时序图处理的数据访问相似性特征，从而降低数据访问开销。实验结果表明，相比于现有最好的时序图处理系统和硬件加速器，SaGraph能够获得8.5倍和4.2倍以上的加速比。
黄禹的论文题目为“MeG2 : In-Memory Acceleration for Genome Graphs Analysis”。基因组图谱分析已成为一种有效的基因分析方法，可使 DNA 片段映射到参考基因组上。它采用基于图的表示形式取代传统的线性参考序列，以增加基因变异和多样性信息，显著提高了基因分析的质量。黄禹通过深入分析基因组图谱负载，观察到它的瓶颈主要集中于不规则的种子索引访问和密集的对齐操作，这两类操作分别对内存系统和计算资源造成了巨大压力。基于上述观察，该项工作提出了MeG2——一个轻量级且DRAM可兼容的存内计算（PIM）架构，以加速基因组图谱分析。MeG2特点在于同时集成了近内存处理和原位计算的能力。具体而言，MeG2利用近内存处理的低访问延迟和以索引为中心的数据加载机制，缓解了播种过程中不规则的内存访问开销；同时利用DRAM存储单元的原位计算能力和距离感知技术，提升了对齐过程中比对操作的并行效率。结果显示，相较于当前最先进的基于CPU、GPU和ASIC的基因组图谱分析解决方案，MeG2可取得30.2倍、15.1倍和8.3倍的性能提升，以及85.6倍、77.1倍和11.7倍的能效提升。
齐豪的论文题目为“PSMiner: A Pattern-Aware Accelerator for High-Performance Streaming Graph Pattern Mining” 。现实世界的图通常随着时间动态改变，该类型的图被称为流图。流图模式挖掘（Streaming Graph Pattern Mining）已被广泛应用于许多应用领域。然而，现有的流图模式挖掘增量解决方案采用模式不感知的模型，导致大量不必要的探索和同构测试开销，而现有的静态图模式挖掘解决方案在每次图更新后，需重新计算整个图。为此，齐豪在论文中提出了一种模式感知的增量执行方法。然而，在提出的方法中，集合计算（例如两个集合的交集）占总执行时间的 89% 以上。通过分析流图挖掘中集合操作的运行时特征，发现集合操作存在大量冗余集合计算，并且负载呈现出多样性特点。基于这两个观察，进一步设计了冗余检测算法和混合集计算机制。基于上述技术，论文提出了一个高性能流图模式挖掘加速器，称为 PSMiner。它可以高效的减少冗余集合计算和加速多种集合计算。实验结果表明，与现有的软件和硬件解决方案相比，PSMiner 分别实现了平均 770.9 倍和 60.4 倍的加速比。
蒋子涵的论文题目为“ACGraph: Accelerating Streaming Graph Processing via Dependence Hierarchy”。流图处理需要进行快速的连续查询。在之前的流图系统中，受图更新影响的顶点往往以不规则的顺序处理，这会导致大量冗余计算和严重的性能下降。为了解决上述问题，蒋子涵在论文中提出了ACGraph，一种用于流图上单调图算法处理的运行时方法。它一方面在运行期间维护依赖树，并针对边增加和边删除两种情况采用不同的算法策略，使图顶点按照它们在依赖树上的层次结构从上到下的顺序进行处理，减少了大量冗余计算；另一方面提出一种串并行相结合的计算模式，使算法在软件实现的情况下保证了高并行性，并且几乎没有引入任何额外开销。实验结果表明，与最先进的流图系统相比，ACGraph平均减少了50％的顶点更新次数，实现了约1.75-7.43倍的性能提升。特别地，在边增加场景下实现了最高22.8倍的加速。
DAC是设计自动化领域的顶级国际会议，是中国计算机学会（CCF）推荐的A类会议。本届会议共收到约1157篇投稿，共录用263篇论文，录用率约为23%。
（通讯员：赵进、黄禹、齐豪、蒋子涵）
