关于串行循环的并行执行

FORTRAN77的DO循环是一个串行执行的语句序列,它重复执行若干次。当它满足一定的基本条件后就有可能并行执行——向量化。当数组元素下标表达式“一维化”后为C_(ij)*1 K_(ij) Q_(ij)的形式,并且循环增值参数为非零的整型常数时,本文讨论可向量化的判别法则,改写时语句顺序的确定,引进临时数组的规则等,并给出初步的结果。     

相关距离在循环语句并行化重构中的应用

Ｌ为一个顺序执行的ＤＯ循环语句，其中包含赋值语句或ＩＦ－ＴＨＥＮ－ＥＬＳＥ条件语句。通过数据相关性分析，计算相关距离，可以析取Ｌ中内在的并行性，实现Ｌ向ＤＯＡＬＬ循环的完全变换或部分变换。本文具体讨论了通过相关距离，对包含具有较为复杂的数组索引下标的赋值语句的ＤＯ循环，以及包含静态条件语句的ＤＯ循环进行并行化处理的两种方法。     

实用数据依赖分析方法

数据依赖分析是检测程序循环级并行的基本步骤，基于数组下标对分类，本文提出了一个实用，有效的数据依赖分析方案。现有的依赖测试算法，都有循环正规化的假设，由于它存在某些弊端，我们抛弃这一假设，允许循环增量是任意整表达式，为此，本文对有关依赖的定义做了适当修改，并重新推导了某些重要结论，为处理循环增量为变量或表达式的情形，给出了弱形式下的ＧＣＤ和Ｂａｎｅｒｊｅｅ测试，该方案已在ＰＯＲＴ中实现。     

面向对象数据库中循环查询处理技术的研究

循环查询是一种比较特殊的查询。针对面向对象数据库及其循环查询的特点,以ＯＤＭＧ－９３国际标准为基础,提出了一种实用有效的循环查询处理策略,并对其中的循环成分识别算法和循环成分处理算法进行了分析讨论。实际应用表明,该策略能有效地处理ＯＯＤＢ中的循环查询。     

向量化中数据依赖关系的强化

本文以数组项为结点的循环向量化分析方法,对“如果一个语句的所有结点(数组的每次出现)都不在递归回路中,则这个语句就能写成向量形式”的论点提出了反面例证,并通过对数据依赖关系进行强化的方法对循环体的部分向量化问题做了重新论述。     

基于SIMD机器的优化数据传输的并行循环分割

本文提出一个基于分布式局存的ＳＩＭＤ机器的循环分割理论体系以优化运算中所需要的数据传输。该体系使用矩阵表示迭代空间、数据空间和数组存取式。我们引入数据传输概念，并建立一个简单有效的数据传输模型来评估数据在全局内存和局部内存之间的传输开销。最后，对于给定的循环嵌套，我们给出一个循环分割算法以获得优化循环块，使得循环嵌套中所需要的数据传输开销最小，并且大大减少了数据传输和计算的同步开销。实验结果证明了     

高级向量优化技巧的实践与经验

本文讨论了将油藏数值模拟中某大型FORTRAN程序(RSP)在向量机KJ89 20上做向量化时所使用的若干技巧.文中首次分析了一类对称型语句间的伪依赖性,提出了引入临时数组的实用方案,并讨论了向量化逻辑IF和转移语句等技巧.     

面向对象数据库系统的触发器机制

如何将触发器机制引入数据库系统是人们长期以来一直关心、考虑的问题。本文就面向对象数据库系统（ＯＯＤＢＳ）中的触发器机制进行了讨论，具体介绍了我们研制的ＯＯＤＢＳ中触发子的描述形式与操作，处理方式。     

面向部分向量化的循环分布及聚合优化

大量循环中都存在着少数无法向量化的语句以及许多可向量化语句,循环分布通常可以将这些语句分离到不同的循环中,进而实现循环的部分向量化。目前主流的优化编译器仅支持简单激进的循环分布方法,因而导致向量化后的循环开销过大,且不利于寄存器和cache的重用。针对上述问题,提出了面向部分向量化的循环分布及聚合方法。首先,分析了一般循环分布的两个关键问题:语句集的划分和循环执行顺序的确定;其次,提出了面向最大聚合的凝聚图结点排序方法来指导循环合并,在不影响并行性的前提下减小了循环开销;最后,通过实验对提出的方法进行了验证。实验结果表明,对于测试用例,提出的方法能够生成正确的向量化代码,并且能够显著提高向量化程序的执行效率。     

串行循环向量化的图论方法

本文讨论FORTRAN内层DO循环的向量化问题。对于满足给定条件的DO循环,根据文中导出的计算公式,可以精确地构造出与循环体相对应的时序依赖关系图。按照判别一个有向图是否存在有向回路的充要条件,采取逐个消去图中某些出度或入度为零的顶点的“消元法”,找出循环体中可以向量化的语句,并统一讨论了确定语句顺序和引进临时数组的算法。     

Scalarization Using Loop Alignment and Loop Skewing

Array syntax, which is supported in many technical programming languages, adds expressive power by allowing operations on and assignments to whole arrays and array sections. To compile an array assignment statement to a uniprocessor, the language processor must convert the statement into a loop that has the same meaning. This process is called scalarization.Scalarization presents a significant technical problem because an array assignment needs to be implemented as if all inputs are fetched before any outputs are stored. Since a loop intermixes loads and stores, the compiler typically allocates a temporary array to hold the intermediate result. Because these extra temporary arrays can cause performance problems in cache, many techniques have been developed to avoid their use or minimize their size.In this paper, we present a novel application of two compiler strategies—loop alignment and loop skewing—to address this problem. We show that these strategies can achieve the asymptotically minimal memory allocation for stencil computations. Our experiments with loop alignment and loop skewing demonstrate that it is extremely effective in improving memory hierarchy performance of Fortran 90 array code on standard uniprocessors. The result should be applicable to other array languages, such as MATLAB.     

闭合螺线阵列的最短路径算法

介绍了闭合螺线阵列的概念;利用动态规划法中的Floyd算法思想对求解闭合螺线阵列最短路径的问题进行了描述,并给出了具体算法;给出了利用二维数组算法求解闭合螺线阵列最短路径的过程.对于以上两种算法的优缺点进行了比较.这两种算法可以用于解决大多数路径问题.     

一种基于代表元的划分算法

划分是把程序中不同的计算和数据分配到并行处理系统的不同处理机来充分利用并行系统的计算资源、提高程序处理速度的一种优化技术.划分的效果对程序在并行系统上的执行效率将产生至关重要的影响,因此划分问题一直是并行领域研究的一个热点.但是应用程序的一些特性,如非紧密嵌套循环、一条语句对非只读数组的多次引用间存在重叠、不同语句对同一数组不同步长的引用,给有效解决划分问题设置了极大的障碍.已有的划分算法无法对具有这些特征的程序进行自动划分.虽然在对具有这些特征的程序进行手工优化过程中,存在一些直观上的划分策略,但这些策略无法应用到编译器中来指导编译器完成对程序的自动划分.文中根据这类程序的特点,提出了一种基于代表元的划分算法.该算法通过使用程序中对划分计算产生实际影响的数组引用作为代表元素构造各种划分的限制条件,完成程序的划分.同时通过寻找最大一致性数据划分方向有效减少了程序划分过程中的数据重组织通信.该算法已经在AFT2004中实现,并对应用程序获得了很好的效果.     

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

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

进化算法与基于同伦理论算法在多维触觉阵列传感器解耦应用中的对比

为获取大规模多维柔性触觉阵列传感器触觉信息,比较进化算法与基于同伦理论的算法在传感器解耦中的应用.仿真结果表明对一定规模的阵列传感器来说,进化算法解耦效果优于其它人工智能算法,但对大规模阵列传感器则无法满足实时性和准确性.通过引入时间参数,基于同伦理论的解耦算法将传统的传感器静态解耦转换成动态解耦过程.算法不仅适用于大规模阵列触觉传感器的信息解耦,而且解决高维、多参数传感器信息精确、实时解耦的难题.     

Achieving distributed control through model checking

We apply model checking of knowledge properties to the design of distributed controllers that enforce global constraints on concurrent systems. The problem of synthesizing a distributed controller is undecidable in the general case. We thus look at a variant of the synthesis problem that allows adding temporary synchronizations between processes. We calculate when processes can decide autonomously, based on their knowledge, whether to take or block an action so that the global constraint is not violated. The local knowledge of processes may not suffice to control the processes so as to achieve the global constraint without introducing new deadlocks. When individual processes cannot take a decision alone based on their knowledge, one may coordinate several processes to achieve joint knowledge in order to take joint decisions. A fixed coordination among sets of processes may severely degrade concurrency. Therefore, we propose the use of temporary coordinations. Since realizing such coordinations on a distributed platform induces communication overhead, we strive to minimize their number. We show how this framework is applied to the case of synthesizing a distributed controller for enforcing a priority order. Finally, we show that the general undecidability of distributed synthesis without adding synchronization holds even for the particular problem of enforcing a priority order.     

Loop Staggering,Loop Compacting:Restructuring Techniques for Thrashing Problem

Parallel loops account for the greatest amount of parallelism in numerical programs.Executing nested loops in parallel wit low run-time overhead is thus very important for achieving high performance in paralleo processing systems.However,in parallel processing systems with caches of local memories in memory hierarchies,“thrashing problemmay” may arise when data move back and forth frequently between the caches or local memories in different processors.The techniques associated with parallel compiler to solve the problem are not completely developed.In this paper,we present two restructuring techniques called loopg staggering,loop staggering and compacting,with which we can not only eliminate the cache or local memory thrashing phemomena significantly,but also exploit the potential parallelism existing in outer serial loop.Loop staggering benefits the dynamic loop scheduling strategies,whereas loop staggering and compacting is good for static loop scheduling strategies,Our method especially benefits parallel programs,in which a parallel loop is enclosed by a serial loop and array elements are repeatedly used in the different iterations of the parallel loop.     

逆Nyquist阵列设计中的小增益递推原理与实现

本文通过在逆Ｎｙｑｕｉｓｔ阵列设计中引入小增益递推原理，提出了一种改进的ＩＮＡ（ＲＩＮＡ）设计方法，该方法既保持了传统的ＩＮＡ（ＲＩＮＡ）设计方法的优点，又解决了当系统的传递函数矩阵的对角优势（鲁棒对角优势）遭到破坏时，系统的稳定性（鲁棒稳定性）问题。     

基于模拟的企业过程模型自动优化技术研究

企业过程模型参数自动优化是一个多参数多目标的系统优化问题.采用线性加权法将其转换成多参数单目标问题的求解,提出基于计算机模拟的企业过程模型参数的自动寻优方法.它将传统的共轭梯度法FR(fletcher reeves)和禁忌搜索算法TS(tabu search)结合起来,采用FR法进行局部寻优,由TS法实现从当前局部最优点向全域范围内的更优区域转移,循环往复达到求出全域范围最优点的目的.改进了FR法与TS法,克服了各自的缺陷,并提出禁忌区域表的概念,从而加速寻优过程.它适用于任意多维曲面的多极值问题最优求解