清华主页 - 清华新闻 - 学术科研 - 正文

姚班本科生提出图挖掘算法硬件加速芯片架构

清华新闻网12月22日电 近日,清华大学交叉信息研究院高鸣宇研究组利用多种细粒度并行优化,提出新型图挖掘硬件加速芯片架构。

图挖掘(Graph Mining)算法在大规模(数百万节点及数千万边)图中匹配与指定图案同构的子图。其在社会科学、生物信息学等领域有着广泛的应用。目前最先进的普适图挖掘算法将每个图节点的邻接节点表示为集合,将每个起始图节点的匹配任务建模为一个搜索树,在每一级中依次考虑图案中各个节点,通过集合相交和相减进行匹配。由于其巨大的计算复杂度,近年来图挖掘算法开始利用专用软件系统和硬件加速芯片以优化性能和效率。

 

FINGERS采用的三种细粒度并行方式

为了进一步提升图挖掘算法的性能和效率,研究者提出了名为FINGERS的硬件加速芯片架构。在利用不同搜索树之间的粗粒度并行执行的同时,该架构提出并实现了三种不同的细粒度并行方式。片段层面并行:将两个输入集合分别拆分成片段并配对执行集合相交和相减,利于并行处理和平衡工作量;集合层面并行:在提前计算未来结果的同时复用输入数据;分支层面并行:提供更多可灵活选择的子任务,最大化利用计算资源,并掩盖访存时间。在硬件设计上,论文采用资源分配、负载均衡、轻量计算单元间通信等创新设计,高效实现上述并行方式,在同等面积下相比当前最佳架构达到平均2.8倍、最高8.9倍的性能提升。

 

FINGERS整体硬件架构

该研究成果被计算机体系结构领域国际顶级会议编程语言和操作系统的体系结构支持会议(ASPLOS 2022接收。2019级姚班本科生陈启航为论文第一作者,通讯作者为高鸣宇助理教授,其它作者包括交叉信息院2020级博士生田博宇。

此外,高鸣宇研究组与美国斯坦福大学师生关于云计算数据中心FPGA硬件上的可信执行环境方面的合作成果亦被ASPLOS 2022接收。ASPLOS是国际计算机协会(ACM主办的横跨硬件、体系结构、编译器、编程语言、操作系统、网络、应用等多学科的国际会议,尤其关注这些学科间的交叉性研究课题。

供稿:交叉信息研究院

编辑:李华山

审核:吕婷

2021年12月22日 08:57:24

相关新闻

读取内容中,请等待...

最新动态

清华大学新闻中心版权所有,清华大学新闻网编辑部维护,电子信箱: news@tsinghua.edu.cn
Copyright 2001-2020 news.tsinghua.edu.cn. All rights reserved.