基于IBM Cell多核平台的OpenMP数组私有化技术研究

数组私有化是并行化编译中的重要技术之一,IBM Cell是异构多核处理器,SPMD代表实现OpenMP数组私有化的重要手段,但是SPMD形式的OpenMP程序却不能直接通过IBM XLC(适用于IBM Cell多核平台的编译器)的编译.为了解决该问题,并充分利用IBM Cell本地存储器中的静态缓冲区以减少DMA通信,提出一种IBM Cell多核平台的OpenMP数组私有化技术.旨在充分利用本地存储器、减少DMA通信,集中处理可重用数据的私有化.主要包括:数组私有化分析、数组私有化转换、同步消除与非阻塞DMA操作,从而扩大数据的可重用作用域.转换后的Jacobi迭代代码进行实际测试表明,这种基于IBM Cell多核平台的数组私有化技术能够平均提高3%左右的执行性能,尤其对于小规模计算来说性能提高还会更多.     

一类不规则问题的自动并行性识别

传统的数据相关性分析主要针对线性数组下标表达式,并不适用于不规则计算中的循环并行性识别.利用间接数组特征分析和基于严格数组私有化定义的运行时动态测试技术来解决包含间接数组下标引用的循环并行性判断问题,给出性能估测,并与相关工作进行了比较.     

非必要内存重用的COMMON变量的识别和处理

在Fortran程序中，公用块的使用有时是为了重复利用某一内存区域，这给数据划分和分布带来了不必要的麻烦，该文提出了数据生命期的概念，借鉴数组私有化中的相关技术，通过计算子程序公用块中数组的暴露集等方法，对非必要内存重用的COMMON变量进行识别和处理。     

一种跳频信号动态检测方法

基于构造型神经网络运算复杂度低、构造直观方便、学习速度快、可解释性强的特点,提出一种跳频信号动态检测方法.首先从滑动窗口的数据流模型入手,采用适合增量学习的覆盖算法动态聚类,聚合相似度大的样本,分离相似度小的样本,降低了聚类复杂度,并减轻了噪声的影响,实现了覆盖簇的动态维护.然后在不同的覆盖簇中提取信号数据概要,构造数据结构数组,运用时频关联方法,排除数组中的定频信号、突发信号、随机噪声信号等,分离出了其中的跳频信号,实现了跳频信号的动态检测.实验结果表明该方法能快速、准确地动态检测跳频信号.     

数组生命期分析的区域延拓方法

数据划分是大规模并行处理中最重要的技术，我们可以用换名、数组扩张、循环交换、循环拆分等方法来增加程序的并行性，从而有可能取得数据的一致划分。数组的生命期信息则是应用这些方法的依据。利用数据流属性的区域延拓方法，我们设计出自动分析工具来得到比较准确的数组生命期信息，使数据可能取得最佳的划分。     

基于污点分析的数组越界缺陷的静态检测方法

随着移动计算、物联网、云计算、人工智能等领域的飞速发展,也涌现出了很多新的编程语言和编译器,但是C/C++语言依旧是最受欢迎的编程语言之一,而数组是C语言最重要的数据结构之一.当在程序中通过数组下标访问数组元素时,必须确保该下标在该数组的边界之内,否则就会导致数组越界.程序中的数组越界缺陷会使得程序在运行时导致系统崩溃,甚至使攻击者可以截取控制流以执行任意恶意代码.当前针对数组越界的静态检查方法无法达到高精度的分析,尤其是无法处理复杂约束和表达式,过多的误报额外增加了开发者的负担.因此,提出了一种基于污点分析的数组越界的静态检测方法.首先,提出流敏感、上下文敏感的按需指针分析方法,实现数组长度区间分析.然后,提出按需污点分析方法,实现数组下标和数组长度污染情况的计算.最后,定义数组越界缺陷判定规则,提出使用后向数据流分析方法,检测数组下标是否越界.在进行数组越界检测的过程中,为了处理程序中的复杂约束和表达式,在分析过程中将调用约束求解器来判断约束的可满足性.如果没有发现相应的语句,则报告数组越界缺陷警报.同时,实现了自动静态分析工具Carraybound,并通过实验展示了方法的有效性.     

数组越界的故障模型及其检测方法研究

数组越界是C程序中的常见故障，该类故障可能造成系统的崩溃。首先针对常见的数组越界故障进行了分析，提出了检测数组越界的判定准则，建立了故障模型。根据该故障模型，采用程序控制流图和路径条件，并结合静态分析思想，给出了可有效地检测出程序中存在的数组越界故障的方法。最后通过实例分析了该方法的应用过程。     

基于封装结构随机化的程序保护方法

随机化方法作为保护程序免受攻击的一项技术,已经得到广泛的应用.但现有的随机化方法存在两个问题:其一,粒度较粗,不能阻止发生在函数、结构体、类内部的攻击;其二,绝大多数攻击是通过外部输入篡改关键对象,而现有随机化方法对这种攻击特点关注不够.基于此,一种增强的随机化安全结构被提出:通过对封装结构(函数、结构体以及类)内部的结构重新排列而达到随机化的细粒度;同时,分析抽取出与外部输入相关的数组,并在这些数组之间插入哨兵,防止其产生溢出.这种随机化方法不仅将随机化技术应用到函数、结构体、类内部,而且抓住了攻击的特点,对关键的与输入相关的数组对象进行保护,使程序免受控制流和非控制流攻击,从而增强了现有的随机化技术.     

用C语言中的指针模拟动态数组

利用指针模拟数组,使其在任何时候都可建立、修改、释放和覆盖数组。     

一种面向分布主存多处理机的有效数据分布方法

本文针对分布主存多处理机中的数据分布问题，在程序已经过并行性分析的基础之上，提出了一种基于数据变换技术的有效数据分布方法。该方法能对多个嵌套循环中具有一般仿射数组下标的任意维数组进行有效的数据分布，并且该方法还考虑了偏移常量的对准问题，从而能使得数据通信量尽量小。实验结果表明了该方法的有效性。     

GCC4．1数据依赖分析器的分析与改进

本文深入分析了GCC4．1的数据依赖分析器，针对它在分析Fortran程序的线性化数组访问时的不足，给出了两点改进：一是初步实现了一个非仿射数组下标依赖分析算法；二是提出并实现了分裂递归链的仿射数组下标数据依赖分析方法。实验表明，这两点改进增强了GCC4．1的数据依赖分析能力，为进行循环变换如循环交换提供了更准确的数据依赖信息。     

面向PMVS算法的自动两级并行翻译方法

当使用高分辨率的图像作为图像处理算法的输入时会降低算法运行速度,将算法并行化可提升执行效率,但手动将串行程序转换为并行程序则较为繁琐,并且现有自动并行翻译工具性能不稳定,同时翻译后的程序是单一并行模式。面向基于面片的三维多视角立体视觉（PMVS）算法,提出一种从C到CUDA的自动两级并行翻译方法。使用ANTLR自动解析源C代码,通过分析数据依赖关系和循环数组私有化来识别可并行化的循环结构,将算法翻译成CPU多线程和GPU两级并行结构的代码。在算法执行过程中,将输入图像在CPU和GPU上分别进行处理,降低了算法总执行时间。实验结果表明,该方法的计算加速比随着输入图像分辨率的增加逐渐提高,最高约达到32,相比于PPCG和OpenACC自动并行翻译方法提升明显。     

基于频域ICA的波达方向估计方法

为降低阵元数目和提高相干多径入射信号的波达方向(DOA)估计精度。提出了一种基于频域独立分量分析与波束零点形成相结合的DOA估计方法。该方法综合利用阵列结构信息和目标信号的统计独立特性,与常规算法相比,降低了算法对阵元数目和精度的依赖,并能实现对相干多径入射信号的DOA估计。计算机仿真结果表明,该算法具有少阵元、收敛快、误差小的特点。     

一种改进的共形阵方向图综合方法

与传统阵列相比,共形阵安置更为灵活,应用更为广泛。然而,针对共形阵的方向图综合也更为复杂。传统的方向图综合方法对共形阵并不适用。通过在旁瓣区域施加虚拟干扰能够有效实现共形阵的方向图综合。如何通过迭代过程控制虚拟干扰功率的大小成为该方法的关键。现有的迭代方法一般存在收敛缓慢或计算复杂的问题。 本文基于线性约束最小方差准则,提出了一种改进的共形阵方向图综合方法。该方法适用于 任意阵型的方向图综合。仿真实验证明,该方法能加快收敛速度,并降低自适应波束形成器 对迭代系数的依赖性。     

The LRPD test: speculative run-time parallelization of loops withprivatization and reduction parallelization

Current parallelizing compilers cannot identify a significant fraction of parallelizable loops because they have complex or statically insufficiently defined access patterns. As parallelizable loops arise frequently in practice, we advocate a novel framework for their identification: speculatively execute the loop as a doall and apply a fully parallel data dependence test to determine if it had any cross-iteration dependences; if the test fails, then the loop is reexecuted serially. Since, from our experience, a significant amount of the available parallelism in Fortran programs can be exploited by loops transformed through privatization and reduction parallelization, our methods can speculatively apply these transformations and then check their validity at run-time. Another important contribution of this paper is a novel method for reduction recognition which goes beyond syntactic pattern matching: it detects at run-time if the values stored in an array participate in a reduction operation, even if they are transferred through private variables and/or are affected by statically unpredictable control flow. We present experimental results on loops from the PERFECT Benchmarks, which substantiate our claim that these techniques can yield significant speedups which are often superior to those obtainable by inspector/executor methods     

符号执行中的循环依赖分析方法

符号执行方法处理循环时存在路径爆炸的问题。为此,提出一种基于归纳变量的循环依赖分析方法。通过识别循环归纳变量及符号表达式,结合边界约束条件生成可达归纳变量分支的路径约束,并采用符号化映射方法分析嵌套循环归纳变量依赖问题,从而在不展开循环的情况下生成覆盖归纳变量分支的测试用例。对开源工具Libxml2进行实验,该方法能发现其中2个while循环所引发的数组访问越界错误。     

Interprocedural Array Region Analyses

Many program optimizations require exact knowledge of the sets of array elements that are referenced in or that flow between statements or procedures. Some examples are array privatization, generation of communications in distributed memory machines, or compile-time optimization of cache behavior in hierarchical memory machines. Exact array region analysis is introduced in this article. These regions exactly represent the effects of statements and procedures upon array variables. To represent the flow of these data, we also introduce two new types of array region analyses: in and out regions. The intraprocedural propagation is presented, as well as a general linear framework for interprocedural analyses, which handles array reshapes. The intra- and inter-procedural propagation of array regions is implemented in pips, the interprocedural parallelizer of fortran programs developed at École des mines de Paris.