图计算体系结构和系统软件关键技术综述

图计算作为分析事物之间关联关系的重要工具,近年来已成为各国政府及公司争夺的关键技术.学术界和工业界在图计算体系结构和系统软件关键技术方面取得了一定进展.然而,现实场景图计算大多具有动态变化、应用需求复杂多样等特征.这给图计算在基础理论、体系架构和系统软件关键技术方面提出了新的需求,同时也带来了新的挑战.为应对这些挑战,科研人员提出了一系列图计算系统或图计算加速器,通过高性能计算、并行计算等技术来优化图计算过程.综述国内外图计算体系结构和系统软件关键技术的研究发展现状,对国内外研究的最新进展进行归纳、比较和分析,并结合国家发展战略和重大应用需求,选取与我国国计民生密切相关的领域,从典型应用分析总结图计算相关技术的行业进展.最后,就未来的技术挑战和研究方向进行展望.

基于迭代协作学习框架的信誉医学参与方选择

联邦学习和群智学习等协作学习技术,能够在保护数据隐私的条件下充分利用分布在各地的分布式数据深度挖掘数据中所蕴含的知识,拥有非常广阔的应用前景,尤其是在强调隐私惯例和道德约束的医疗健康领域.任何协作工作都需要选择可靠的参与方,协作学习中全局模型的性能在很大程度上取决于参与方的选择.然而,现有研究在选择参与方时都没有对不同机构医疗数据中存在的异质性加以直接关注.导致包含稳定性在内的全局模型的性能难以得到保障.提出了从信誉的角度尝试探索求解该问题.以迭代协作学习的方式尽可能挑选出具有良好信誉的参与方进行协作学习,以获得稳定可靠的高性能全局模型.首先,提出了一个描述医疗机构数据质量的AI信誉值指标AMP(AI medical promise),以帮助其在医疗领域中形成良好的AI生态.其次,建立了一个基于后向选择的迭代协作学习(colback-learning)框架.在单次协作学习任务中,利用后向选择方法以多项式时间复杂度迭代计算出性能良好且稳定的全局模型,完成AMP计算和积累.在AMP信誉值计算中,制定了一个综合考虑全局性能指标的评分函数,以针对医疗领域更有效地指导全局模型的训练.最后,使用真实医疗数据模拟多样化的协作学习场景.实验表明,colback-learning能够选择可靠参与方训练得到性能良好的全局模型,模型的性能稳定性比现有最好的参与方选择方法提高了1.3~6倍.全局模型的可解释性与集中式学习保持了较高的一致性.

ElasticDAG:弹性图式区块链

图式区块链采用有向无环图(directed acyclic graph,DAG)的并行拓扑结构,相较于基于串行拓扑结构的传统链式区块链,能够显著提升系统性能,已受到业界广泛关注.然而,现有图式区块链的共识协议与存储模型高度耦合,缺乏灵活性,难以适应多元化应用需求.同时,大部分图式区块链在共识协议层面上缺乏灵活性,局限于概率性共识协议,难以兼顾确认延迟和安全性,尤其对于延迟敏感型应用很不友好.为此,提出弹性图式区块链系统ElasticDAG,其核心思想是将存储模型和共识协议进行解耦,让两者并行、独立地运行,从而灵活适配多元化应用.针对提升系统吞吐量和活性的需求,为存储模型设计自适应区块确认策略和基于划分的确认区块排序算法;针对降低交易确认延迟的需求,设计低延迟DAG区块链混合共识协议.实验结果表明,ElasticDAG原型系统在广域网下的吞吐量高达11 Mb/s,并具有10秒级确认性能.与OHIE相比,Elastic DAG在实现同等吞吐量的情况下,可将确认延迟降低17倍;与Haootia相比,Elastic DAG在实现同等共识延迟的情况下,可将安全性从91.04%提升到99.999914%.

一种可动态配置的分布式内存池缓存一致性机制

在分布式内存系统中,缓存是减少远端内存访问开销的一种有效手段.然而,单一的缓存一致性保证机制往往不能高效适配不同类型负载的访存特性.为此,面向分布式异构内存池系统,设计了基于目录和基于广播相结合的混合缓存一致性保证机制.利用四象限矩阵分析方法,对每个数据对象进行访存模式的判定分析,并为其配置最高效的缓存一致性保证策略,并且可以根据对象访存特征的变化在2种策略之间动态切换.实验结果表明,相比使用单一的缓存一致性保证机制,采用可动态配置的混合缓存一致性保证机制可提升分布式异构内存池系统的读和写,性能平均达32.31%和31.20%.此外,混合的缓存一致性保证机制在客户端数量不断增加时仍然表现出良好的可扩展性.

基于学习索引的图式区块链高效可验证查询机制

区块链技术近年来受到了广泛关注,并应用于各个领域,数据查询是其在应用过程的一个重要技术,如物流链中的数据溯源等.随着区块链系统中交易数据量的持续增长,支持高并发事务处理的图式区块链成为区块链技术的研究热点.图式区块链的高并发区块使得数据查询难以像传统链式结构依次遍历,可以根据图式结构采用广度优先或深度优先遍历策略,但这种查询方式存在效率低、验证难等问题.针对图式区块链数据查询的效率和可验证性问题,提出了一种基于学习索引的高效可验证的图式区块链查询机制Lever.该机制通过引入学习索引技术对图式区块链中时序数据分布特征进行学习以实现对索引过程的优化,旨在提高图式区块链查询的效率和可验证性.学习索引是通过学习数据分布来减少索引存储空间和查询时间的新型索引技术,将学习索引应用于图式区块链的纪元高度与时间戳的映射关系中,通过函数运算的方式定位查询数据,提高查询速度和效率.同时,为了加快纪元内多个区块数据的过滤速度,在每个区块头部添加布隆过滤器,并为每个纪元生成一个聚合布隆过滤器,从而提高纪元内的数据遍历速度.此外,为保证查询结果的正确性和完整性,该机制结合布隆过滤器和排序默克尔树生成可验证对象,通过部分默克尔树分支实现对布隆过滤器假阳性的不存在证明,有效减小验证对象的规模,从而提高图式区块链查询过程的数据传输效率.实验结果表明,Lever能有效提高基于DAG的图式区块链查询效率和可验证性,与Conflux的基本查询机制相比,该机制的查询性能最高提升了10倍,可验证对象大小开销可以降低90%.

面向高性能图计算的高效高层次综合方法

图计算已成为大数据处理领域的主流应用,采用特定硬件加速可以显著提高图计算的性能和能效.众所周知,硬件代码的编写和验证十分耗时,尽管通用高层次综合(high level synthesis,HLS)系统允许用户使用高级语言(如C语言)特性自动生成硬件结构,但是对于图计算这种不规则算法,其仍缺乏有效的并行性和访存技术支撑,存在综合效果不理想、效率不高等突出问题.提出一种面向图计算的高效HLS方法,结合图算法嵌套循环、随机访存、数据冲突以及幂律分布等特性,采用数据流架构实现高效的并行流水线,保证处理单元的负载均衡.通过提供的编程原语,提出的方法可将通用图算法转化为模块化的数据流中间表示形式,进而映射到参数化的硬件模板.在Xilinx Virtex UltraScale+XCVU9P的实现验证了方法的正确性,不同类型的图算法在多个数据集上的实验结果表明,相比国际上通用的Spatial HLS系统,提出的方法可达到7.9~30.6倍的性能提升.