复杂非紧密嵌套循环变换在并行编译中的应用

在并行编译中,循环变换是开发程序并行度的主要方法,但存在复杂控制流的非紧密嵌套循环往往无法得到有效的并行化。文章结合分析Benchmark和实现自动并行化系统AFT中复杂非紧密嵌套循环变换的经验,给出复杂非紧密嵌套循环变换的特点及其在并行编译中的应用。     

基于多核阵列体系结构的嵌套循环并行优化

多核处理器已广泛应用于高性能计算领域,如何有效地将传统串行程序转换为并行代码并减少程序中嵌套循环所占用时间仍是该领域的挑战性问题。本文首先基于多面体模型对嵌套循环进行依赖特征分析并实现瓦片分割,据此自动生成粗粒度并行代码。针对多核阵列处理器的结构特点,采用遗传算法生成通信优化的瓦片任务序列,在此基础上建立了有效的任务调度模型。最后将上述方法应用于LU分解,结果表明该方法与传统调度算法相比,在增加数据局部性、实现负载平衡方面具有更好效果。     

一种面向众核处理器的嵌套循环多维并行识别方法*

现有并行识别方法用于众核处理器时存在一定不足,当选择的循环并行维迭代数较少时可能导致严重地负载不均衡。针对这一问题,提出了一种面向众核处理器的多维并行识别方法,在现有并行识别方法无法做到较好的负载均衡时,选择嵌套循环的多个维进行并行,将多个并行维的迭代空间合并后再做任务划分,减少负载不均衡对程序并行效率的影响。此方法已在课题组开发的自动并行化系统中进行了实现,实际应用过程中能够提升一些应用程序在众核处理器上并行执行的效率。     

基于LLVM Pass的复杂嵌套循环自动并行化框架

随着多核处理器的普及应用,针对嵌入式遗留系统中串行代码的自动并行化方法是研究热点.其中,针对具有非完美嵌套结构、非仿射依赖关系特征的复杂嵌套循环的自动并行化方法存在技术挑战.提出了一种基于LLVMPass的复杂嵌套循环的自动并行化框架(CNLPF).首先,提出了一种复杂嵌套循环的表示模型,即循环结构树,并将嵌套循环的正则区域自动转换为循环结构树表示;然后,对循环结构树进行数据依赖分析,构建循环内和循环间的依赖关系;最后,基于OpenMP共享内存的编程模型生成并行的循环程序.针对SPEC2006数据集中包含近500个复杂嵌套循环的6个程序案例,分别对其进行复杂嵌套循环占比统计和并行性能加速测试.结果表明,提出的自动并行化框架可以处理LLVMPolly无法优化的复杂嵌套循环,增强了LLVM的并行编译优化能力,且该方法结合Polly的组合优化,比单独采用Polly优化的加速效果提升了9%-43%.     

分支嵌套循环的自动并行化研究

GCC编译器是一种受广大研究者青睐的开源优化编译器,但它仅仅能够对完美嵌套循环进行依赖分析。为了更好地挖掘嵌套循环粗粒度的并行,深入研究了GCC5.1数据依赖分析过程,提出了一种能够处理分支嵌套循环的依赖测试方法。首先识别出分支嵌套循环,然后分析数组下标与分支嵌套循环外层索引变量的关系,最后计算出外层循环索引变量的距离向量,并通过检测距离向量判断循环是否存在依赖。实验结果表明,该方法能够正确、有效地分析出分支嵌套循环的依赖关系。     

并行程序设计的模型,语言及编译技术

并行程序设计的研究对并行机性能的发挥和推广应用都具有重要的作用。本文介绍了并行计算机的结构、并行程序设计模型和并行语言的一些基本概念，讨论了并行程序设计的方法，分析了大规模并行处理中编译技术的若干问题和研究方向。     

并行推理机编译技术的研究

自动模式识别,数据相关性分析、AND并行性的开发、副作用处理、并行性的粒度分析、并发语言的处理和WAM指令集的扩充是并行推理机编译中所面临的一些课题。本文对这些课题及我们所做的工作逐一作了论述,并展示了并行推理机编译技术研究的前景。     

MPI通信代码自动生成算法

对于高性能并行计算机而言，如何由给出的计算、数据划分信息及精确数组数据流分析信息自动生成并行化代码是实现串行程序并行化的一个重要问题。根据Saman P.Amarasinghe和Lam的定理，实现了一种并行化识别工具中MPI（Message Passing Interface）并行化代码自动生成技术的算法，并对该算法的性能进行分析。     

基于LSF集群技术的网格并行编译服务模型

针对目前单机编译环境中编译资源局限、编译作业执行时间过长等问题,通过对网格集群技术的研究,提出了一种基于集群技术的网格并行编译服务模型。该模型中首先对编译作业进行分解,并依据作业调度算法,把分解后的元编译作业分发至集群中的编译服务器进行并行编译。实际应用表明,该模型充分利用了编译服务网格资源,提高了编译效率,具有很高的实用价值。     

基于投影分层技术的嵌套循环空间局部性优化方法

从数据访问轨迹入手，探讨了利用数据变换来改善数据访问局部性的本质，提出了一种新的优化数据访问的投影分层技术以及基于它的数据变换框架．该框架主要利用投影技术来优化数据访问的空间局部性，并同时利用数据分层技术来解决因投影而带来的数据重叠问题．该数据变换框架不仅能处理仿射数组下标，而且还能处理许多非仿射的更复杂的数组下标，同时它还能简单直接地确定数据元素的最优存储布局以及优化数据访问的数据变换短阵，并能使访问间距尽量小．实验结果表明它是有效的．     

嵌套循环到多处理机的映射

给出了将具有变相关的嵌套循环映射到具有分布式存储的多处理机上的两种方法.通过相关向量的分解或由相关向量导入方向向量,可将具有变相关的嵌套循环分解成若干互相没有相关关系的独立部分.由于它们可以被独立地执行,从而可以被映射到各个处理机上并行处理.     

Generation of Efficient Nested Loops from Polyhedra

Automatic parallelization in the polyhedral model is based on affine transformations from an original computation domain (iteration space) to a target space-time domain, often with a different transformation for each variable. Code generation is an often ignored step in this process that has a significant impact on the quality of the final code. It involves making a trade-off between code size and control code simplification/optimization. Previous methods of doing code generation are based on loop splitting, however they have nonoptimal behavior when working on parameterized programs. We present a general parameterized method for code generation based on dual representation of polyhedra. Our algorithm uses a simple recursion on the dimensions of the domains, and enables fine control over the tradeoff between code size and control overhead.     

NestStep: Nested Parallelism and Virtual Shared Memory for the BSP Model

NestStep is a parallel programming language for the BSP (bulk–synchronous–parallel) model of parallel computation.Extending the classical BSP model, NestStep supports dynamically nested parallelism by nesting of supersteps and a hierarchical processor group concept. Furthermore, NestStep adds a virtual shared memory realization in software, where memory consistency is relaxed to superstep boundaries. Distribution of shared arrays is also supported.A prototype for a subset of NestStep has been implemented based on Java as sequential basis language. The prototype implementation is targeted to a set of Java Virtual Machines coupled by Java socket communication to a virtual parallel computer.     

中文医疗文本中的嵌套实体识别方法

实体识别是信息抽取的关键技术. 相较于普通文本, 中文医疗文本的实体识别任务往往面对大量的嵌套实体. 以往识别实体的方法往往忽视了医疗文本本身所特有的实体嵌套规则而直接采用序列标注方法, 为此, 提出一种融合实体嵌套规则的中文实体识别方法. 所提方法在训练过程中将实体的识别任务转化为实体的边界识别与边界首尾关系识别的联合训练任务, 在解码过程中结合从实际医疗文本中所总结出来的实体嵌套规则对解码结果进行过滤, 从而使得识别结果能够符合实际文本中内外层实体嵌套组合的组成规律. 在公开的医疗文本实体识别的实验上取得良好的效果. 数据集上的实验表明, 所提方法在嵌套类型实体识别性能上显著优于已有的方法, 在整体准确率方面比最先进的方法提高0.5%.     

基于交互式特征融合的嵌套命名实体识别

现有命名实体识别模型在字嵌入过程中多采用字符向量、字向量等不同单词表示向量的拼接或累加方式提取信息,未考虑不同单词表示特征之间的相互依赖关系,导致单词内部特征信息获取不足。提出一种基于交互式特征融合的嵌套命名实体识别模型,通过交互的方式构建不同特征之间的通信桥梁,以捕获多特征之间的依赖关系。采用交互机制得到包含不同单词表示信息的字嵌入向量,基于双向长短时记忆网络提取单词的表示特征,并对不同单词的表示特征进行交互,捕获特征之间的相互依赖关系。为进一步提取序列特征的上下文信息,采用基于特征交互的多头注意力机制捕获句子上下文的依赖关系。在此基础上,采用二元序列标记法过滤非实体区域,得到粗粒度候选区间,并对其进行细粒度划分以判断实体类别。实验结果表明,该模型的召回率和F1值为72.4%和71.2%,相比现有的嵌套命名实体识别模型,F1值平均提高了1.72%。     

基于Bayes决策的密码算法识别技术

在可执行代码中识别密码算法对于查找恶意代码、保护计算机系统安全有着重要的意义。该文在对汇编级密码算法特征分析的基础上,提出了汇编级密码算法特征度量元的概念,并采用七维特征向量对其进行形式化描述,建立基于Bayes决策的密码算法识别模型,测试结果表明该模型稳定、准确,能够高效地定位代码中的密码算法。     

实体提及的多层嵌套识别方法研究

实体识别在许多自然语言处理应用系统中发挥着极其重要的作用。目前大部分研究集中在命名实体识别,且不考虑实体之间的嵌套,本文在自动内容抽取评测(Automatic Content Extraction, ACE)背景下,对汉语文本中各种实体提及(命名性,名词性,代词性)的多层嵌套识别进行了研究。我们将嵌套实体识别分成两个子任务: 嵌套实体边界检测和实体多层信息标注。首先,本文提出了一种层次结构信息编码方法,将多层嵌套边界检测问题转化为传统的序列标注问题,利用条件随机场模型融合多种特征进行统计决策。其次,将多层信息标注问题看作分类问题,从实现的角度设计了含有两个分类引擎的并行SVM分类器,避免了对每层信息标注都设计一个分类器,比采用单一分类器在性能上有明显提高。在标准ACE语料上的实验表明,基于条件随机场的多层实体边界检测模型正确率达到71％,融合特征选择策略的两个并行分类引擎的正确率也分别达到了89.05%和82.17%。     

中文嵌套命名实体识别语料库的构建

嵌套命名实体含有丰富的实体和实体间语义关系,有助于提高信息抽取的效率。由于缺少统一的标准中文嵌套命名实体语料库,目前中文嵌套命名实体的研究工作难于比较。该文在已有命名实体语料的基础上采用半自动化方法构建了两个中文嵌套命名实体语料库。首先利用已有中文命名实体语料库中的标注信息自动地构造出尽可能多的嵌套命名实体,然后再进行手工调整以满足对中文嵌套实体的标注要求,从而构建高质量的中文嵌套命名实体识别语料库。语料内和跨语料嵌套实体识别的初步实验表明,中文嵌套命名实体识别仍是一个比较困难的问题,需要进一步研究。