期刊文献+
共找到7篇文章
< 1 >
每页显示 20 50 100
面向忆阻器存内计算架构的高能效编解码机制
1
作者 黄禹 郑龙 +4 位作者 刘海峰 邱启航 辛杰 廖小飞 金海 《中国科学:信息科学》 CSCD 北大核心 2024年第8期1827-1842,共16页
近年来,以忆阻器为代表的存内计算架构被广泛研究,用于加速各种应用,并有望突破冯·诺伊曼(von Neumann)架构面临的内存墙瓶颈.本文观察到忆阻器计算操作的能源消耗存在不对称性,即在低电阻状态下对忆阻器单元的操作能耗可能比在高... 近年来,以忆阻器为代表的存内计算架构被广泛研究,用于加速各种应用,并有望突破冯·诺伊曼(von Neumann)架构面临的内存墙瓶颈.本文观察到忆阻器计算操作的能源消耗存在不对称性,即在低电阻状态下对忆阻器单元的操作能耗可能比在高电阻状态下高出数个数量级.这为通过减少低电阻状态单元的数量来节省计算能源提供了机会.为此,本文提出了一套通用且高效的忆阻器编解码机制,可以无缝集成到现有加速器中,并且不会影响其计算结果.在编码部分,设计了一个基于减法的编码器,实现了低电阻状态到高电阻状态的编码转换,并将编码问题表述为图遍历问题以实现最优的编码结果在解码部分,配备了一个轻量级的硬件解码器,用于还原编码的计算结果,并且避免引入额外的计算时间开销。实验结果显示,本方案在机器学习和图计算等多个领域取得不俗效果,分别实现了高达31.3%和56.0%的能源节约. 展开更多
关键词 存内计算 忆阻器 加速器 高能效 机器学习 图计算
原文传递
一种高效的面向动态有向图的增量强连通分量算法 被引量:6
2
作者 廖小飞 陈意诚 +3 位作者 张宇 金海 刘海坤 赵进 《中国科学:信息科学》 CSCD 北大核心 2019年第8期988-1004,共17页
强连通分量(strongly connected component, SCC)算法可以将一个有向图缩略为有向无环图(directed acyclic graph, DAG),广泛应用于可达性查询等有向图分析应用.尽管现有工作已经提出多种面向静态有向图的强连通分量算法,但是它们需要... 强连通分量(strongly connected component, SCC)算法可以将一个有向图缩略为有向无环图(directed acyclic graph, DAG),广泛应用于可达性查询等有向图分析应用.尽管现有工作已经提出多种面向静态有向图的强连通分量算法,但是它们需要高额的运行时开销来反复对整个图进行全量计算,以响应现实世界中普遍存在的动态有向图结构的频繁变化.其实,在通常情况下,动态有向图每次改变量极小(少于5%).其允许我们以增量的方式对动态有向图进行强连通分量计算,以缩短响应时间.因此,为解决此问题,本文提出了一种高效的面向动态有向图的增量强连通分量算法Incremental Strongly Connected Components Algorithm,简称Inc-SCC,通过对不必要的计算进行裁剪以减少算法的数据访问量和计算量,并利用SCC的不相交性进行并行处理以提升SCC计算效率.其次,提出了一种启发式优化方法进一步加快算法收敛速度.实验结果显示,本方法可以用于实时响应有向图持续性动态变化,并且当整个有向图的边变化比例为5%时,本方法相对于现有算法的加速比可达2.8到12倍,当整个有向图的边变化比例为0.5%时,本方法相对于现有算法的加速比可达2.9到12倍. 展开更多
关键词 强连通分量 动态有向图 增量计算 收敛 有向无环图
原文传递
一种冗余感知的高能效图计算加速器
3
作者 姚鹏程 廖小飞 +6 位作者 金海 周宇航 徐鹏 张伟 曾圳 潘晨高 朱冰 《中国科学:信息科学》 CSCD 北大核心 2024年第6期1369-1385,共17页
图作为一种灵活表达对象之间关系的数据结构,广泛地应用于各类重要的现实场景.近年来,随着性能提升速度放缓,通用处理器逐渐无法满足图计算应用的需求,并成为限制图计算发展的主要瓶颈.因此,面向图计算的领域专用加速器成为近年来的研... 图作为一种灵活表达对象之间关系的数据结构,广泛地应用于各类重要的现实场景.近年来,随着性能提升速度放缓,通用处理器逐渐无法满足图计算应用的需求,并成为限制图计算发展的主要瓶颈.因此,面向图计算的领域专用加速器成为近年来的研究热点.通过定制化的硬件设计,图计算加速器可以在图计算应用中取得通用处理器数十倍的性能.然而,现有的图计算加速器在运行宽度优先算法时会频繁地重复访问幂律顶点的相关数据,进而导致了严重的冗余访存问题.在特定场景下,现有的图计算加速器的性能甚至低于通用CPU.为了解决该问题,本文提出一种冗余感知的高能效图计算加速器JiFeng.当幂律顶点完成迭代计算时,JiFeng通过跳过剩余的相邻边大幅减少其被重复访问的次数.JiFeng实现了一系列软硬件协同设计,在保证负载均衡的同时提升硬件的执行效率.为了验证JiFeng的有效性,本文采用FPGA原型系统对相关设计进行性能评估.JiFeng在典型的生成图和现实图上实现最高每秒遍历4612亿条边的性能和每秒每瓦特遍历125亿条边的能效比,并在2023年11月的图计算超算排行榜GreenGraph500的小数据集榜单上取得第2名的成绩. 展开更多
关键词 图计算 加速器 宽度优先搜索 冗余访存 FPGA
原文传递
面向动态有向图的单调图算法硬件加速机制 被引量:1
4
作者 杨赟 余辉 +8 位作者 赵进 张宇 廖小飞 姜新宇 金海 刘海坤 毛伏兵 张吉 王彪 《中国科学:信息科学》 CSCD 北大核心 2023年第8期1575-1592,共18页
随着现实世界中动态图计算需求的快速增长,现有的研究工作已经提出了多种方法来有效支持单调图算法在动态有向图中的处理.然而,由于动态有向图的图结构频繁发生变化,其相邻图顶点之间的状态更新存在复杂的依赖关系,这使得现有的软硬件... 随着现实世界中动态图计算需求的快速增长,现有的研究工作已经提出了多种方法来有效支持单调图算法在动态有向图中的处理.然而,由于动态有向图的图结构频繁发生变化,其相邻图顶点之间的状态更新存在复杂的依赖关系,这使得现有的软硬件方法在处理单调图算法时依然面临着数据访问成本高和收敛速度慢的问题.为此,本文提出了一种面向动态有向图的单调图算法加速器DSGraph,它能够充分利用图顶点之间的依赖关系来加快单调图算法在动态有向图处理中的收敛速度,并有效降低数据访问成本.具体来说,DSGraph通过实时提取动态有向图中图顶点的局部拓扑依赖顺序来执行异步迭代处理,从而显著减少冗余的图顶点状态更新.同时,DSGraph设计了一种异步迭代流水线架构,其按照依赖顺序对图顶点状态进行异步迭代处理,从而加速图顶点状态传播速度并减少数据访问开销.最后,DSGraph提出了一种无阻塞数据同步机制,通过并行执行本地图顶点的状态更新和外部图顶点的数据同步来减少系统同步开销.实验显示,与目前最先进的面向单调图算法的动态图处理系统KickStarter相比,DSGraph将动态有向图处理速度平均提升了11.2倍. 展开更多
关键词 动态有向图 单调图算法 增量计算 依赖感知 图加速器
原文传递
一种高效的面向高并发图分析任务的存储系统 被引量:3
5
作者 赵进 姜新宇 +7 位作者 张宇 廖小飞 金海 刘海坤 杨赟 张吉 王彪 余婷 《中国科学:信息科学》 CSCD 北大核心 2022年第1期111-128,共18页
随着现实世界中图计算需求的快速增长,同一平台上往往并发运行着大量迭代图分析任务.然而,现有的图计算系统主要是为了高效执行单个图分析任务而设计的.因此,当多个并发图分析任务同时在同一个底层图上并行执行时,现有图计算系统会面临... 随着现实世界中图计算需求的快速增长,同一平台上往往并发运行着大量迭代图分析任务.然而,现有的图计算系统主要是为了高效执行单个图分析任务而设计的.因此,当多个并发图分析任务同时在同一个底层图上并行执行时,现有图计算系统会面临巨大的数据访问开销.为了提高并发图分析任务的吞吐量,现有的核外并发图处理方案通过共享图数据减少并发任务的数据存储与访问开销.但是,由于现实世界中图的图顶点度数幂律分布特性以及图分析任务之间的差异性,现有方案在访问数据时依旧存在着大量的不必要的冗余I/O开销.这是因为即使静态图分区中绝大部分顶点处于非活跃状态或者只被少数图分析任务共享,现有方法也依旧会将整个分区加载入内存供并发图分析任务处理.为解决上述问题,本文提出了一个面向并发图分析任务的高效存储系统GraphDP.它能够插入到现有核外图计算系统中来透明有效地减少现有图计算系统执行并发图分析任务时的存储消耗与数据访问开销,从而提高并发图分析任务的吞吐量.具体来说,GraphDP使用一种新颖的动态I/O调度策略,能够使系统以最优的I/O访问方式完成图数据的加载,并有效地减少加载到内存和cache的数据.同时,GraphDP通过高效的缓存机制在内存中优先缓存被频繁访问的图数据,从而进一步减少数据访问开销.为证明GraphDP的有效性,我们将GraphDP插入到目前流行的核外图计算系统中,包括GridGraph,GraphChi和X-Stream.实验结果表明,GraphDP分别将GridGraph,GraphChi和X-Stream的吞吐量提高了1.57~2.19倍,1.86~2.37倍和1.62~2.21倍. 展开更多
关键词 迭代图处理 并发任务 存储系统 I/O开销 吞吐量
原文传递
图计算在ATPG中的应用探究
6
作者 毛伏兵 彭达 +7 位作者 张宇 廖小飞 姜新宇 杨赟 金海 赵进 刘海坤 王柳峥 《中国科学:信息科学》 CSCD 北大核心 2023年第2期211-233,共23页
ATPG(automatic test pattern generation)是VLSI(very large scale integration circuits)电路测试中非常重要的技术,它的好坏直接影响测试成本与开销.然而现有的并行ATPG方法普遍存在负载不均衡、并行策略单一、存储开销大和数据局部... ATPG(automatic test pattern generation)是VLSI(very large scale integration circuits)电路测试中非常重要的技术,它的好坏直接影响测试成本与开销.然而现有的并行ATPG方法普遍存在负载不均衡、并行策略单一、存储开销大和数据局部性差等问题.由于图计算的高并行度和高扩展性等优点,快速、高效、低存储开销和高可扩展性的图计算系统可能是有效支持ATPG的重要工具,这将对减少测试成本显得尤为重要.本文将对图计算在组合ATPG中的应用进行探究;介绍图计算模型将ATPG算法转化为图算法的方法;分析现有图计算系统应用于ATPG面临的挑战;提出面向ATPG的单机图计算系统,并从基于传统架构的优化、新兴硬件的加速和基于新兴存储器件的优化几个方面,对图计算系统支持ATPG所面临的挑战和未来研究方向进行了讨论. 展开更多
关键词 图计算 超大规模集成电路 自动测试向量生成 电子设计自动化 电路测试
原文传递
图数据中极大团枚举问题的求解:研究现状与挑战 被引量:2
7
作者 许绍显 廖小飞 +2 位作者 邵志远 华强胜 金海 《中国科学:信息科学》 CSCD 北大核心 2022年第5期784-803,共20页
随着大数据时代的到来,图数据挖掘成为了一个热门的研究方向.极大团枚举(maximal clique enumeration,MCE)作为图论中的一个基本问题,在很多领域都有着广泛的应用.然而,鉴于极大团枚举问题本身的复杂性以及现实图数据规模的飞速增长,在... 随着大数据时代的到来,图数据挖掘成为了一个热门的研究方向.极大团枚举(maximal clique enumeration,MCE)作为图论中的一个基本问题,在很多领域都有着广泛的应用.然而,鉴于极大团枚举问题本身的复杂性以及现实图数据规模的飞速增长,在现实图数据上进行极大团枚举是很耗时的.目前已经有大量的工作对该问题的求解算法进行改进,或采用各种计算优化方法减少算法的运行时间.本文就极大团枚举问题做了如下工作:对现有的极大团枚举问题的研究工作进行了分类归纳;对极大团枚举问题的研究现状进行了详细介绍;对该问题进一步发展所面临的挑战和发展方向进行了讨论和展望. 展开更多
关键词 极大团枚举 图论 图数据挖掘 图划分 并行计算
原文传递
上一页 1 下一页 到第
使用帮助 返回顶部