一种高效的凸连通子图枚举算法

在可配置处理器的定制指令设计过程中,需要提取热点代码数据流图的凸连通子图.为实现子图的快速枚举,对有向无环图内的凸子图特性进行了研究.根据凸子图特性和节点邻接关系,提出了一种AS(adjacent search) 算法用于枚举有向无环图内满足I/O端口约束的凸连通子图.实验数据显示,AS算法比现有算法具有更高的效率,加速比可达10～1000X.当现有算法因数据流图规模较大而失效时,应用AS算法仍能成功完成子图枚举.     

面向ASAP自定义指令生成算法研究

从处理器的指令集进行扩展的优势主要是降低系统设计时间和代价以及可减小代码大小、寄存器压力,从而降低取指频率和功耗。基于此,结合ASAP框架给出自定义指令生成的算法,通过数据流分析、指令簇标记、子图枚举、子图合并的方法,找出符合自定义扩展指令的多个约束要求的候选指令集合。实验结果表明,该算法能够高效地找出目标应用的所有非平凡自定义指令集合。     

二进制翻译中代码生成的子图覆盖算法

二进制翻译技术能够有效解决二进制兼容问题,促进新型体系结构的发展,也是虚拟机技术的重要组成部分,具有重要的研究和应用价值,但是其效率仍然有待提升,特别是目标代码生成的效率。设计了一种高效的目标代码生成算法——代码生成的子图覆盖算法(subgraph covering for code generation,SCCG),能够以尽可能少的代价生成精简的目标代码。该算法应用数据流图对二进制代码中的基本块进行建模,获取指令间的数据相关,并采用基于子图覆盖的贪心算法得到目标代码。在TransARM原型系统中进行了实现和测试,结果表明该算法获得了更优质的目标代码,并且成本得到了有效控制。     

一种改进数据流图的子字并行程序表示方法

论文致力于对图像处理算法的串行C程序进行子字并行分析,并重定向到带有多媒体扩展的通用处理器和多媒体专用嵌入式微处理器。图像处理算法的特点决定其是内在可并行的,这种并行粒度介于数据并行(DLP)和指令级并行(ILP)之间,称之为子字并行。但是,当前的编译技术很难充分挖掘和定位程序基本块内的子字并行,对此设计了一种基于流图程序表示的编译方法,能够从串行程序中显式地定位子字并行。扩展了编译器的功能,增加了特定的模式库,基于模式识别的控制流和数据流分析后,产生特定的子字并行流图(SWFG,Sub-WordFlowGraph),并将该图作为中间表示,提供给子字并行指令选择,进而实现有效的子字并行代码产生。     

一种支持SIMD指令的表驱动的代码选择技术*

代码选择在编译器的代码产生阶段是一个十分重要的任务,它的目标就是在与机器无关的中间表示代码和与处理器相关的机器指令之间寻找一种高效的映射方法。为了支持DSP处理器的SIMD指令,在传统的基于数据流树中间表示的代码选择算法的基础上,提出一种基于数据流图（DFG）的代码选择技术,它能在最大限度地挖掘和利用SIMD指令的基础上寻求对整个DFG的最优覆盖。     

基于多维度异质图结构的代码注释自动生成

代码注释能够增强源代码的可读性、辅助软件开发过程，因此代码注释自动生成任务成为研究热点。然而现有工作大多只利用了源代码的序列信息或抽象语法树信息，未能充分捕捉代码语言特有的多种特征。为进一步利用源代码的多维度特征，提升注释生成的效果，构建基于多维度异质图结构的代码注释自动生成模型。利用异质图结构和图神经网络，将源代码的抽象语法树、控制流图、数据流图等进行融合并构建为具有多种节点和连边的异质表示图，以此表现代码的语义特征、序列特征、语法特征、结构特征等多维度特征。在真实数据集上的实验结果表明，该模型相较于Hybrid-DRL、NeuralCodeSum、SeqGNN等模型具有更好的效果，在BLEU-4、METEOR、ROUGE-L指标上分别最高提升1.6%、3.2%、3.1%，可获得更流畅、可读性更好的代码注释。     

一种基于代价子图的子字并行指令选择算法

子字并行能够充分利用多媒体算法的数据精度小、内部循环处理形式规则的特点,是加速多媒体处理的有效方式。然而,如何充分挖掘多媒体应用中的子字并行仍然是一个难题。本文说明传统的并行技术可以有效地开发循环中的子字并行性,同时提出一种基于代价子图的子字并行指令自动识别的方法。与其他方法相比,该方法利用代价模型对子子字并行指令选择进行定量评估。本文在TTA体系结构框架下实现了这一方法。实验结果表明,该方法可以充分地提取循环中的子字并行性。     

指令扩展中相关子图的分析与处理

由于没有充分考虑候选子图间重叠、包含等相关关系,按照现有指令扩展方法选出的扩展指令可能无法带来预期的性能收益.详细讨论了子图相关关系和处理方法,并提出相应的指令扩展算法.在子图识别时,根据延迟约束合并相互包含的子图,根据重叠结点的位置合并重叠子图,缩小搜索空间;在子图压缩时,根据子图相关关系动态地调整候选子图的性能收益,减少相关子图引起的估算误差.此外,还根据剩余候选子图的性能收益对时间与精度进行折中.该算法已在传输触发结构ASIP的自动设计流程中实现,实际性能加速比与预期值的平均误差仅为0.17%,远低于原先的3.6%.     

基于子字并行的串行图像处理算法表示方法

多媒体应用程序的一个最突出的特点就是其内在的并行性,要求同时对多个数据单元进行相同的规则操作,这种并行性被称为子字并行。如何让编译器产生有效的并行代码,如何从普通的串行C程序中识别出子字并行指令,是一个前沿性的研究课题。提出了一种用于实现对串行源代码进行显式表示的方法,该方法对数字信号处理领域常用的同步数据流图方法进行改进,结合模式匹配技术,着眼于内层循环,通过扩展规范的模式库,对带模式识别的数据流、控制流进行分析,能够从串行应用程序中自动地提取其固有的子字并行,得到显式的并行化中间表示,基于这种数据流图表示,采用改进的树模式匹配实现子字并行指令选择和代码生成。实验测试表明了该方法的有效性。     

一种面向图神经网络安卓恶意代码检测的通用解释定位方法

面对不断涌现的安卓恶意应用,虽然大量研究工作采用图神经网络分析代码图实现了准确高效的恶意应用检测,但由于未提供应用内恶意代码的具体位置信息,难以对后续的人工复核工作提供有效帮助.可解释技术的出现为此问题提供了灵活的解决方法,在基于不同类型神经网络及代码特征表示实现的检测模型上展示出了较好的应用前景.本研究聚焦于基于图神经网络的安卓恶意代码检测模型上,使用可解释技术实现安卓恶意代码的准确定位:（1）提出了基于敏感API及多关系图特征的敏感子图提取方法.根据敏感API,控制流逻辑以及函数调用结构三类特征与恶意代码子图分布的关联性,细致刻画恶意代码特征,精简可解释技术关注的代码图规模;（2）提出了基于敏感子图输入的可解释技术定位方法.使用基于扰动原理的可解释技术,在不改变检测模型结构的情况下对代码图边缘进行恶意性评分,为各类基于图神经网络安卓恶意代码检测提供解释定位;（3）设计实验验证敏感子图提取对于与恶意代码特征的刻画效果以及基于敏感子图提取的解释定位效果.实验结果显示,本文的敏感子图提取方法相较于MsDroid固定子图半径的方法更为精确,能够为可解释技术提供高质量的输入;基于此方法改进后得到的可解释技术定位方法相较于GNNExplainer通用解释器及MsDroid定位方法,在保证定位适用性和效率的同时,恶意代码平均定位准确率分别提高了8.8%和2.7%.     

求解最大团问题的并行多层图划分方法

在当今大数据环境下,针对图中节点的海量性和分析的复杂性对最大团问题的研究在速度和精度上都提出了更高要求的问题,提出求解最大团问题的并行多层图划分方法（PMGP_SMC）。首先,提出一种新的多层图划分（MGP）方法,在保持原有图的团结构不被破坏的情况下对大规模图例划分产生子图,并对规模较大的子图进行多层图划分,进一步缩小子图规模,并且应用GraphX图计算框架实现MGP,形成并行MGP（PMGP）方法;然后,依据划分后的子图规模,减少了惩罚值局部搜索算法（PBLS）的迭代次数,提出基于速度优化的PBLS（SPBLS）来求解划分后的各个子图的最大团;最后,将PMGP和SPBLS相结合形成PMGP_SMC。采用Stanford大规模数据集运行测试,实验结果表明,PMGP相比并行单层图划分方法（PSGP）,求得的最大子图规模能缩小至原来的1/100,平均子图规模能缩小至原来的1/2;PMGP_SMC相比求解最大团问题的PSGP（PSGP_SMC）,总体时间缩短至原来的1/100,并且PMGP_SMC求解最大团的精度和基于极大团枚举求解最大团问题的并行多层图划分方法（PMGP_MCE）一致。PMGP_SMC能够快速精准地求解大规模图例的最大团。     

基于路径的频繁子图挖掘算法研究

图挖掘是数据挖掘的一个重要研究方向,而图挖掘主要集中在图数据集内频繁子图的挖掘。频繁子图挖掘技术的关键是建立有效机制减少冗余候选子图,以便高效计算和处理所需的频繁子图。提出了一种基于路径的频繁子图挖掘算法,该算法首先找出所有频繁边从而挖掘出频繁单路径,然后通过组合、双射和操作扩展出较多的频繁路径,再通过连接操作产生所有频繁子图候选集。通过定理证明了该算法的正确性和完整性,从理论上分析了该算法时间复杂度低于现有的算法,最后进行了2个图数据集实验,在候选集产生的数量和时间性能2方面验证了算法的优越性。     

Parallel custom instruction identification for extensible processors

With the ability of customization for an application domain, extensible processors have been used more and more in embedded systems in recent years. Extensible processors customize an application domain by executing parts of application code in hardware instead of software. Determining parts of application code as custom instruction generally requires subgraph enumeration and subgraph selection. Both subgraph enumeration problem and subgraph selection problem are computationally difficult problems. Most of previous works focus on sequential algorithms for these two problems. In this paper, we present a parallel implementation of a latest subgraph enumeration algorithm based on a computer cluster. A standard ant colony optimization algorithm (ACO), a modified version of ACO with local optimum search and a parallel ACO algorithm are also proposed to solve the subgraph selection problem in this work. Experimental results show that the parallel algorithms outperform the sequential algorithms in terms of runtime or (and) quality of results. In addition, we have formally proved the upper bound on the number of feasible solutions in subgraph selection problem with or without the overlapping constraint.     

基于FSG的最大频繁子图挖掘算法*

图挖掘已成为数据挖掘领域研究的热点,然而挖掘全部频繁子图很困难且得到的频繁子图过多,影响结果的理解和应用。可通过挖掘最大频繁子图来解决挖掘结果数量巨大的问题,最大频繁子图挖掘得到的结果数量很少且不丢失信息,节省了空间和以后的分析工作。基于算法FSG提出了最大频繁子图挖掘算法FSG-MaxGraph;结合节点的度、标记及邻接列表来计算规范编码,提出两个定理来减少子图同构判断的次数,并应用改进后的决策树来计算支持度。实验证明,新算法解决了挖掘结果太多理解困难的问题,且提高了挖掘效率。     

基于类别信息的特征子图选择策略

选择频繁的特征子图在基于频繁子图的图数据分类中起着非常重要的作用.提出了一种基于类别信息的特征子图选择策略,即从候选的频繁子图中选出独有频繁子图和显著频繁子图作为特征子图.实验结果显示,在对化合物数据分类时,该选择策略在分类性能上优于SVM方法特征选择策略和CEP方法的特征选择策略.     

一种新的频繁子图挖掘算法

传统Aprior频繁子图挖掘算法中存在大量冗余子图.针对该问题,提出一种新的频繁子图挖掘算法(GAI).介绍一种三层MADI索引结构,用于存储图集的信息,以减少图集的扫描次数,通过扩展ETree树构造频繁子图,并用表来存储候选子图,避免扩展过程中冗余图的产生以及对整个数据库的扫描,从而简化支持度的计算,提高图/子图同构...     

基于L-Metric重叠子图发现的B细胞表位预测模型

针对现有表位预测方法对抗原中存在的重叠表位预测能力不佳的问题,提出了将基于局部度量（L-Metric）的重叠子图发现算法用于表位预测的模型。首先,利用抗原上的表面原子构建原子图并升级为氨基酸残基图;然后,利用基于信息流的图划分算法将氨基酸残基图划分为互不重叠的种子子图,并使用基于L-Metric的重叠子图发现算法对种子子图进行扩展以得到重叠子图;最后,利用由图卷积网络（GCN）和全连接网络（FCN）构建的分类模型将扩展后的子图分类为抗原表位和非抗原表位。实验结果表明,所提出的模型在相同数据集上的F_{\mathrm{1}}值与现有表位预测模型DiscoTope 2、ElliPro、EpiPred和Glep相比分别提高了267.3%、57.0%、65.4%和3.5%。同时,消融实验结果表明,所提出的重叠子图发现算法能够有效改善预测能力,使用该算法的模型相较于未使用该算法的模型的F_{\mathrm{1}}值提高了19.2%。     

嵌入式系统芯片中SM2算法软硬件协同设计与实现

针对现有的椭圆曲线算法系统级设计中开发周期长,以及不同模块的性能开销指标不明确等问题,提出一种基于电子系统级(ESL)设计的软硬件(HW/SW)协同设计方法.该方法通过分析SM2(ShangMi2)算法原理与实现方式,研究了不同的软硬件划分方案,并采用统一建模语言SystemC对硬件模块进行周期精确级建模.通过模块级与系统级两层验证比较软硬件模块执行周期数,得出最佳性能划分方式.最后结合算法控制流程图(CFG)与数据流程图(DFG)将ESL模型转化为寄存器传输级(RTL)模型进行逻辑综合与比较,得出在180 nm CMOS工艺,50 MHz频率下,当算法性能最佳时,点乘模块执行时间为20 ms,门数83 000,功耗约2.23 mW.实验结果表明所提系统级架构分析对基于椭圆曲线类加密芯片在性能、面积与功耗的评估优势明显且适用性强,基于此算法的嵌入式系统芯片(SoC)可根据性能与资源限制选择合适的结构并加以应用.     

利用MapReduce平台实现高效并行的频繁子图挖掘

频繁子图挖掘是数据挖掘领域的一个重要问题,并且有着广泛的应用。在Hadoop平台上实现了一种基于MapReduce的高效频繁子图挖掘算法Cloud-GFSG（cloud-global frequent subgraph）。该算法基于Apriori思想,在扩展边生成新的子图时,使用已经挖掘出的k-1阶的频繁子图生成k阶的频繁子图。同时,检查是否存在待扩展生成的子图,设定生成的频繁子图表示规则,保证了频繁子图信息的唯一性。较同类算法相比,该算法在挖掘频繁子图时更具通用性,并且在扩展边时避免产生大量的复制图,从而使得算法的正确性得以保证,且运行效率显著提高。