BAR:a branch-alternation-resorting algorithm for locality exploration in graph processing

Unstructured and irregular graph data causes strong randomness and poor locality of data accesses in graph processing.This paper optimizes the depth-branch-resorting algorithm(DBR),and proposes a branch-alternation-resorting algorithm(BAR).In order to make the algorithm run in parallel and improve the efficiency of algorithm operation,the BAR algorithm is mapped onto the reconfigurable array processor(APR-16)to achieve vertex reordering,effectively improving the locality of graph data.This paper validates the BAR algorithm on the GraphBIG framework,by utilizing the reordered dataset with BAR on breadth-first search(BFS),single source shortest paht(SSSP)and betweenness centrality(BC)algorithms for traversal.The results show that compared with DBR and Corder algorithms,BAR can reduce execution time by up to 33.00%,and 51.00%seperatively.In terms of data movement,the BAR algorithm has a maximum reduction of 39.00%compared with the DBR algorithm and 29.66%compared with Corder algorithm.In terms of computational complexity,the BAR algorithm has a maximum reduction of 32.56%compared with DBR algorithm and53.05%compared with Corder algorithm.

Towards High-Performance Graph Processing: From a Hardware/Software Co-Design Perspective

Graph processing has been widely used in many scenarios,from scientific computing to artificial intelligence.Graph processing exhibits irregular computational parallelism and random memory accesses,unlike traditional workloads.Therefore,running graph processing workloads on conventional architectures(e.g.,CPUs and GPUs)often shows a significantly low compute-memory ratio with few performance benefits,which can be,in many cases,even slower than a specialized single-thread graph algorithm.While domain-specific hardware designs are essential for graph processing,it is still challenging to transform the hardware capability to performance boost without coupled software codesigns.This article presents a graph processing ecosystem from hardware to software.We start by introducing a series of hardware accelerators as the foundation of this ecosystem.Subsequently,the codesigned parallel graph systems and their distributed techniques are presented to support graph applications.Finally,we introduce our efforts on novel graph applications and hardware architectures.Extensive results show that various graph applications can be efficiently accelerated in this graph processing ecosystem.

Big Data Analytics Using Graph Signal Processing

The networks are fundamental to our modern world and they appear throughout science and society.Access to a massive amount of data presents a unique opportunity to the researcher’s community.As networks grow in size the complexity increases and our ability to analyze them using the current state of the art is at severe risk of failing to keep pace.Therefore,this paper initiates a discussion on graph signal processing for large-scale data analysis.We first provide a comprehensive overview of core ideas in Graph signal processing(GSP)and their connection to conventional digital signal processing(DSP).We then summarize recent developments in developing basic GSP tools,including methods for graph filtering or graph learning,graph signal,graph Fourier transform(GFT),spectrum,graph frequency,etc.Graph filtering is a basic task that allows for isolating the contribution of individual frequencies and therefore enables the removal of noise.We then consider a graph filter as a model that helps to extend the application of GSP methods to large datasets.To show the suitability and the effeteness,we first created a noisy graph signal and then applied it to the filter.After several rounds of simulation results.We see that the filtered signal appears to be smoother and is closer to the original noise-free distance-based signal.By using this example application,we thoroughly demonstrated that graph filtration is efficient for big data analytics.

An effective framework for asynchronous incremental graph processing

Although many graph processing systems have been proposed, graphs in the real-world are often dynamic. It is important to keep the results of graph computation up-todate. Incremental computation is demonstrated to be an efficient solution to update calculated results. Recently, many incremental graph processing systems have been proposed to handle dynamic graphs in an asynchronous way and are able to achieve better performance than those processed in a synchronous way. However, these solutions still suffer from sub-optimal convergence speed due to their slow propagation of important vertex state (important to convergence speed) and poor locality. In order to solve these problems, we propose a novel graph processing framework. It introduces a dynamic partition method to gather the important vertices for high locality, and then uses a priority-based scheduling algorithm to assign them with a higher priority for an effective processing order. By such means, it is able to reduce the number of updates and increase the locality, thereby reducing the convergence time. Experimental results show that our method reduces the number of updates by 30%, and reduces the total execution time by 35%, compared with state-of-the-art systems.

Efficient FPGA-based graph processing with hybrid pull-push computational model

Hybrid pull-push computational model can provide compelling results over either of single one for processing real-world graphs.Programmability and pipeline parallelism of FPGAs make it potential to process different stages of graph iterations.Nevertheless,considering the limited on-chip resources and streamline pipeline computation,the efficiency of hybrid model on FPGAs often suffers due to well-known random access feature of graph processing.In this paper,we present a hybrid graph processing system on FPGAs,which can achieve the best of both worlds.Our approach on FPGAs is unique and novel as follow.First,we propose to use edge block(consisting of edges with the same destination vertex set),which allows to sequentially access edges at block granularity for locality while still preserving the precision.Due to the independence of blocks in the sense that all edges in an inactive block are associated with inactive vertices,this also enables to skip invalid blocks for reducing redundant computation.Second,we consider a large number of vertices and their associated edge-blocks to maintain a predictable execution history.We also present to switch models in advance with few stalls using their state statistics.Our evaluation on a wide variety of graph algorithms for many real-world graphs shows that our approach achieves up to 3.69x speedup over state-of-the-art FPGA-based graph processing systems.

FDGLib: A Communication Library for Efficient Large-Scale Graph Processing in FPGA-Accelerated Data Centers

With the rapid growth of real-world graphs,the size of which can easily exceed the on-chip(board)storage capacity of an accelerator,processing large-scale graphs on a single Field Programmable Gate Array(FPGA)becomes difficult.The multi-FPGA acceleration is of great necessity and importance.Many cloud providers(e.g.,Amazon,Microsoft,and Baidu)now expose FPGAs to users in their data centers,providing opportunities to accelerate large-scale graph processing.In this paper,we present a communication library,called FDGLib,which can easily scale out any existing single FPGA-based graph accelerator to a distributed version in a data center,with minimal hardware engineering efforts.FDGLib provides six APIs that can be easily used and integrated into any FPGA-based graph accelerator with only a few lines of code modifications.Considering the torus-based FPGA interconnection in data centers,FDGLib also improves communication efficiency using simple yet effective torus-friendly graph partition and placement schemes.We interface FDGLib into AccuGraph,a state-of-the-art graph accelerator.Our results on a 32-node Microsoft Catapult-like data center show that the distributed AccuGraph can be 2.32x and 4.77x faster than a state-of-the-art distributed FPGA-based graph accelerator ForeGraph and a distributed CPU-based graph system Gemini,with better scalability.

Identifying influential nodes based on graph signal processing in complex networks

Identifying influential nodes in complex networks is of both theoretical and practical importance. Existing methods identify influential nodes based on their positions in the network and assume that the nodes are homogeneous. However, node heterogeneity （i.e., different attributes such as interest, energy, age, and so on ） ubiquitously exists and needs to be taken into consideration. In this paper, we conduct an investigation into node attributes and propose a graph signal pro- cessing based centrality （GSPC） method to identify influential nodes considering both the node attributes and the network topology. We first evaluate our GSPC method using two real-world datasets. The results show that our GSPC method effectively identifies influential nodes, which correspond well with the underlying ground truth. This is compatible to the previous eigenvector centrality and principal component centrality methods under circumstances where the nodes are homogeneous. In addition, spreading analysis shows that the GSPC method has a positive effect on the spreading dynamics.

A method for improving graph queries processing using positional inverted index (P.I.I) idea in search engines and parallelization techniques

The idea of positional inverted index is exploited for indexing of graph database. The main idea is the use of hashing tables in order to prune a considerable portion of graph database that cannot contain the answer set. These tables are implemented using column-based techniques and are used to store graphs of database, frequent sub-graphs and the neighborhood of nodes. In order to exact checking of remaining graphs, the vertex invariant is used for isomorphism test which can be parallel implemented. The results of evaluation indicate that proposed method outperforms existing methods.

Continuous-Time Independent Edge-Markovian Random Graph Process

In this paper, the continuous-time independent edge-Markovian random graph process model is constructed. The authors also define the interval isolated nodes of the random graph process, study the distribution sequence of the number of isolated nodes and the probability of having no isolated nodes when the initial distribution of the random graph process is stationary distribution, derive the lower limit of the probability in which two arbitrary nodes are connected and the random graph is also connected, and prove that the random graph is almost everywhere connected when the number of nodes is sufficiently large.

THE STATIONARY DISTRIBUTION OF A CONTINUOUS－TIME RANDOM GRAPH PROCESS WITH INTERACTING EDGES

In previous papers, the stationary distributions of a class of discrete and continuoustime random graph processes with state space consisting of the simple and directed graphs on Nvenices were studied. In this paper, the random graph graph process is extended one impotent stepfurther by allowing interaction of edges. Similarly, We obtha the expressions of the stationarydistributions and prove that the process is ergodic under different editions.

A Distributed Newton Method for Processing Signals Defined on the Large-Scale Networks

In the graph signal processing(GSP)framework,distributed algorithms are highly desirable in processing signals defined on large-scale networks.However,in most existing distributed algorithms,all nodes homogeneously perform the local computation,which calls for heavy computational and communication costs.Moreover,in many real-world networks,such as those with straggling nodes,the homogeneous manner may result in serious delay or even failure.To this end,we propose active network decomposition algorithms to select non-straggling nodes(normal nodes)that perform the main computation and communication across the network.To accommodate the decomposition in different kinds of networks,two different approaches are developed,one is centralized decomposition that leverages the adjacency of the network and the other is distributed decomposition that employs the indicator message transmission between neighboring nodes,which constitutes the main contribution of this paper.By incorporating the active decomposition scheme,a distributed Newton method is employed to solve the least squares problem in GSP,where the Hessian inverse is approximately evaluated by patching a series of inverses of local Hessian matrices each of which is governed by one normal node.The proposed algorithm inherits the fast convergence of the second-order algorithms while maintains low computational and communication cost.Numerical examples demonstrate the effectiveness of the proposed algorithm.

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

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

动态数据流驱动的再制造拆解工艺知识图谱构建方法

高效稳定的再制造拆解是实施规模化再制造的重要前提。然而,废旧零部件的内部结构、损伤特征等存在较大差异,需要对拆解工艺进行频繁调整,从而造成再制造拆解效率低、质量稳定性差,严重制约了再制造规模化效益。为此,提出一种从动态数据流中提取个性化拆解工艺知识的知识图谱构建方法,利用知识的高效更新与重用提升再制造拆解效率与质量。首先,分析再制造拆解工艺数据的动态时序性特点,以拆解工位为数据分析节点,建立动态数据流模型。其次,基于工位数据对拆解工艺知识进行分类,构建包含拆解过程知识、资源知识和特征知识的本体模型,并利用命名实体识别模型(ALBERT-BiLSTM-CRF)和自然语言处理方法自动抽取拆解工艺知识。进而,提出一种动态数据流驱动的图谱更新机制,实现知识图谱对拆解工艺调整的快速响应。最后,以某型号废旧动力电池包拆解为例,验证所提方法的有效性。

知识图谱技术实现流程及相关应用

目前,人类已经迈入信息时代的大门,大数据技术得到广泛化应用,信息数据成为一项宝贵的资源,通过知识图谱可以对海量数据进行整合、利用,挖掘高价值信息,以便为决策制定等多方面提供重要支持。基于此,该文围绕知识图谱的技术实现及相关应用展开深入、全面的探析。

基于溯源图和注意力机制的APT攻击检测模型构建

针对现有攻击检测方法难以应对持续时间长、攻击手段复杂隐蔽的高级持续威胁的问题,构建了基于注意力机制和溯源图的APT攻击检测模型。首先,基于系统的审计日志构建能够描述系统行为的溯源图;其次,设计优化算法,确保在不牺牲关键语义的前提下缩减溯源图规模;再次,利用深度神经网络(DNN)将原始攻击序列转换为语义增强的特征向量序列;最后,设计并实现了APT攻击检测模型DAGCN,该模型将注意力机制应用于溯源图序列,利用该机制对输入序列的不同位置分配不同的权重并进行权值计算,能够提取较长时间内的持续攻击的序列特征信息,从而有效地识别恶意节点,还原攻击过程。该模型在识别精确率等多个指标上均优于现有模型,在公开的APT攻击数据集上的实验结果表明,该模型在APT攻击检测中的精确率达到93.18%,优于现有主流检测模型。

基于因子图优化的激光惯性SLAM方法研究

融合激光雷达和惯性测量单元的SLAM方法是拒止环境下自动驾驶定位建图的重要技术手段。该技术包含前端和后端2个数据处理模块,在后端数据处理方面,现有方法存在长时间运行时累积误差较高、回环检测计算负载较大以及复杂拒止环境下鲁棒性不理想等问题。针对上述需求,提出一种适配前端激光惯性里程计的新型后端数据处理方法。该方法采用因子图优化算法架构,建立激光连续关键帧间的惯性单元预积分模型,将该模型作为因子图架构中表征惯性单元数据的算法因子,降低数据处理的计算负载。构建基于Scan-Context描述符的高效回环检测方法,将点云数据三维空间结构特征转化为二维特征图,在保证回环检测精度的前提下进一步提高计算效率。结合前端里程计信息,构建包含里程计因子、惯性单元预积分因子和回环检测因子误差项的目标函数,通过非线性优化算法求解最优位姿状态,形成完整的SLAM算法结构。对所述方法及FAST-LIO2、LIO-SAM和SC-LeGO-LOAM等现有主流激光惯性SLAM方法基于开源数据集进行对比验证,并开展实车试验。结果表明:相较于现有方法,所述DSC-Algo方法在公开数据集测试中的计算性能和全局定位精度实现了显著提升,在现实拒止环境实车测试中的定位精度和算法鲁棒性也具有明显优势。

基于面积加权GWT-GFT的水声目标识别

由于海洋环境的复杂性,水声目标的识别具有很大的挑战性。为解决这类复杂环境下特征提取的问题,提出了一种基于面积加权的图小波变换-图傅里叶变换(GWT-GFT)的分析方法。在完成数据预处理后,为了能够凸显顶点之间的关系,提出了一种新的基于顶点三角形面积的加权方法来构建图信号;构建好的图信号通过GWT分解为多尺度图分量;然后,利用GFT将这些分量从图域变换到特征值谱域进行分析;在此基础上,提取各分量特征值谱的特征;最后,利用基于高斯核函数的支持向量机(SVM)对获取的特征向量进行分类。基于水声信号ShipsEar数据库,采用5折交叉验证方法进行验证。与现有的其它方法相比,所提的模型以36个特征在376656个样本上取得了97.22%的准确率,证明了该分析方法的有效性和鲁棒性。

基于霍克斯过程和图神经网络的会话推荐

针对传统会话推荐系统(Session-Based Recommendation System, SBRS)往往忽略了项目点击量之间的交互,以及遗漏了会话内项目之间的相对顺序的问题,本文提出了一种基于霍克斯过程和图神经网络(Hawkes Process and Graph Neural Network, HPGNN)的会话推荐方法。该方法提出了包含图神经位置感知层和图神经霍克斯层的双流结构,分别学习用户的长期和短期偏好。图神经位置感知层通过门控图神经网络(Gated Graph Neural Network, GGNN)来捕捉各个节点之间的交互关系,得到会话中每个项目的隐向量表示,并引入逐次递减的残差网络,有效地将之前的编码信息与当前网络融合,然后通过位置感知注意力网络来捕捉项目节点在会话中的位置信息,用于学习用户的长期偏好表示。图神经霍克斯层通过将霍克斯过程和GGNN相结合来捕捉连续时间的项目点击量之间的关系,用于更准确的表示用户的短期偏好。最后将两者进行线性组合,来更好地描述用户意图。实验结果表明,提出的HPGNN在Diginetica和Yoochoose1/64两个基准会话推荐数据集上的推荐性能均优于其他会话推荐模型。

基于知识图谱的SMT产线工艺推荐与优化

面向复杂电路板组件产品,依赖人工经验设计表面贴装技术(SMT)工艺的传统方法存在准确度与适配度低、设计效率低、实物试错成本高等问题,提出了一种基于知识图谱的SMT产线工艺推荐与优化算法。建立知识图谱系统描述SMT产线工艺参数之间的关系,利用随机森林算法计算各个参数重要度,更新参数权重推荐合适参数,并与完全平均加权法对比,验证了其准确性与稳定性。

多光源照射下目标图像实时生成方法

由于地理位置、太阳、大气环境等因素限制,无法获取空间目标在各种姿态、光照条件、特别是激光、太阳和背景光共同作用下的实际成像。提出一种多光源照射下目标图像实时生成方法。该方法基于计算机图形学中纹理映射思想,采用现代图形显卡编程技术和帧缓存对象特性,在GPU(Graphics Processing Unit)端采用着色器语言实现多光源作用下目标亮度值高效计算和真实感增强;采用开源三维图形引擎OSG(Open SceneGraph)支持多种格式三维模型文件,提高与国产麒麟操作系统及常用战场态势显示软件的兼容性。仿真实验验证了该方法的有效性和优越性。