CN114817648B 一种高能效协同图计算方法及装置 （华中科技大学）

US2020311067A1,202本发明涉及一种高能效协同图计算装置及和直接依赖管理单元(5)：被配置为将核心依赖路径上首尾顶点间的依赖关系转换为直接依赖地对多条路径进行处理，加速图顶点状态的传2在动态图处理过程中，基于图结构的变化获取已失效的依赖在所述图计算加速器初始化的情况下，以四段流水线形式完成的边以及与边对应的一对顶点的状态输出到FIFO边缓冲区以供处理器内核进行访问处根据所述栈顶顶点的未访问边获取未访问邻居顶点的ID，并将其中一个邻居顶点压从顶点状态数组获取相关顶点的状态，将边以及与边对应的一对顶点的状态输出到队列作为新的活跃顶点；若无法从栈顶顶点的邻居中获取到图分区Gm中的未访问顶点，则栈顶顶点出栈。3,在第一次完成对核心依赖路径l的处理时，将其首尾顶点的编号j、i以及第一状态值sj将所述常数参数μ和的值保存至直接依赖索引数组，并将索引标识flag设置为A。所述直接依赖管理单元（5）按照定制化的插入策略和/或替换策略将8.根据权利要求4所述的高能效协同图计算装置，其特征在于，当预取到路径首顶点根据目标依赖索引的存储地址从直接依赖索引数组中获取顶点对应的直接依赖索引遍历图结构更新信息，获取被删除边<s,d>；从被删除边的目的顶点出发在核心子图中执行深度优先搜索遍历，并且设置最大遍将遍历访问到的核心顶点加入顶点集合Hd，在遍历结束后将顶点集合Hd传递至所述顶点加入核心顶点集合Hm。10.一种由权利要求1~9任一项所述的高能效协同图计算装置实现的高能效协同图计45两位指示index其余位与数值value的含义，S2、图计算加速器的预处理电路将转换后的请人保留在背景技术中增加相关现有技术之权利。6以及与边对应的一对顶点的状态输出到FIFO边缓冲区以供处理器[0014]优选地，所述依赖路径预取单元以四段流水线形式完成边的预取的方式至少包7元将表项<ID,start_offset,end_offset,weight>插入内存哈希表，其中权值weight设置元对表项的起始偏移量start_offset、结束偏移量end_offset以及权值weight进行更新，[0032]所述直接依赖管理单元按照定制化的插入策略和/或替换策略将内存哈希表中被频繁访问的表项与产生冲突的表项缓存至所述片[0033]当预取到路径首顶点时，所述直接依赖管理单元通过顶点ID检索对应的依赖索[0035]根据目标依赖索引的存储地址从直接依赖索引数组中获取顶点对应的直接依赖[0037]从被删除边的目的顶点d出发在核心子图中执行深度优先搜索遍历，并且设置最[0038]将遍历访问到的核心顶点加入顶点集合Hd，在遍历结束后将顶点[0041]本发明还提供一种由本发明的高能效协同图计算装置实现的高能效协同图计算[0042]接收活跃顶点信息，并且从循环队列中活跃顶点开始沿依赖路径预取图分区的8提供一种存储有本发明的图计算运行编码的存[0054]本发明中的缓存单元是指能够进行高效数据交换的存储器。缓存单元例如是RAM[0056]图计算加速器通过至少一个第二缓存单元6和至少一个第三缓存单元8建立通信赖路径预取单元3和直接依赖管理单元5建立数据传[0058]例如，依赖路径预取单元3包括具有依赖路径预取功能的子处理器、专用集成芯[0060]图计算加速器可以为集成有依赖路径预取功能、直接依赖管理功能和/或片上缓理器内核1和第二缓存单元6建立数据传输连接。图计算加速器分别与处理器内核1和第二9[0064]直接依赖管理单元5被配置为：将核心依赖路径上首尾顶点间的依赖关系转换为加速器的配置接口，将图数据信息传递到加速器可访问的内存映射寄存器来初始化加速[0076]在每一轮图处理中，加速器的依赖路径预取单元3从本地循环队列中的活跃顶点[0077]在第一次处理核心依赖路径l时，保存路径首尾顶点的第一组顶点的第一状态值i依赖公式的参数。根据直接依赖公式计算出首顶点更新对尾顶点的影响并更新尾顶点状核都会在内存中有一个对应的本地循环队列。Τ。vcurr[0107]图计算阶段：通过加速器的依赖路径预取单元3从活跃顶点开始沿依赖路径预取边进行处理，同时通过直接依赖管理单元5将核心依赖路径首尾顶点间的依赖关系转换为址等)而不是图数据本身传递到加速器。图数据信息的传递路线为：内存—第三缓存单元[0116](d)对应处理器内核的本地循环队列的大小和首地址，该循环队列用于存储图分[0120]依赖路径预取单元3使用一个固定深度的栈记录预取信息，栈中的每个条目都包[0133]当顶点之间的依赖关系为线性关系时，两个顶点的直接依赖关系可以表示为公j[0134]直接依赖管理单元5使用直接依赖索引数组保存路径首尾顶点间的直接依赖索[0153]直接依赖索引的索引标识flag初始化为N。在图处理过程中第一次完成对核心依顶点插入处理器内核的本地循环队列。缓存单元4用于存储内存哈希表(in_memoryhashtable)的表项。内存哈希表是直接依赖速度，直接依赖管理单元5使用内存哈希表(in_memoryhashtable)来快速获取目标依赖索引的存储地址，同时使用片上缓存单元4来缓存哈希表中被频繁访问的表项与产生冲突的表项。[0163]内存哈希表中的每一项可表示为<ID,start_offset,end_offset,weight>，其中start_offset与end_offset分别表示顶点ID所对应的依赖索引在直接依赖索引数组中的[0164]在直接依赖管理单元5进行依赖关系转换的同时，根据生成的直接依赖索引对内[0165]根据生成的直接依赖索引对内存哈希表进行插入或者更新的情况至少包括下面单元5对表项的起始偏移量start_offset、结束偏移量end_offset以及权值weight进行更[0168]当直接依赖管理单元5进行依赖索引检索时，首先通过顶点ID从哈希表中获取对[0169]直接依赖管理单元5将内存哈希表中被频繁访问的表项与产生冲突的表项缓存至存单元中权值(weight)最小的哈希表项将被[0173]当直接依赖管理单元5根据顶点ID获取哈希表项时，首先从片上缓存单元中进行[0175]依赖索引的可重用性划分：首先根据依赖源顶点的度数访问到的核心顶点加入顶点集合Hd。若目的顶点d属于核心顶点，则也将其加入该顶点集与目的顶点