联合下标循环的并行执行方法

所谓联合下标循环是指循环体中,数组下标的引用由多个循环索引联合决定。这是一种常见的循环程序,且数据相关模式复杂,循环空间没有规律。能否开发这类程序的并行性,是一个重要的研究课题。文章针对联合下标循环程序,系统地提出了一套有效的并行执行方法。     

Statement-Level Communication-Free Partitioning Techniques for Parallelizing Compilers

This paper addresses the problem of communication-free partition of iteration spaces and data spaces along hyperplanes. To finding more possible communication-free hyperplane partitions, we treat statements within a loop body as separate schedulable units. Instead of using the information about data dependence distance or direction vectors, our technique explicitly formulates array references as transformations from statement-iteration spaces to data spaces. Based on these transformations, the necessary and sufficient conditions for communication-free partition along hyperplanes to be feasible have been proposed. This approach can be applied to all programs with an imperfectly nested loop or sequences of imperfectly nested loops, whose array references are affine functions of outer loop indices or loop invariant variables. The proposed approach is more practical than existing methods in finding the data and computation distribution patterns that can cause the processor to execute fully-parallel on multicomputers without any interprocessor communication.     

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

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

带数组和循环的路径测试数据自动生成技术研究

提出了一种新的带数组和循环的路径测试数据自动生成的方法.该方法只考虑数组中与路径中谓词函数有关的数组元素,将循环中的同一变量名在每一次执行时用不同的变量参数来替代,从而较好地解决了路径中数组循环有效处理的问题.为有效、简单地自动生成测试数据,建立了谓词函数关于输入变量的线性约束系统.当谓词函数为线性表达式时,不需要计算其线性算术表示,仅计算非线性函数谓词函数的线性算术表示,且不需计算路径中的谓词片和确定输入依赖集,以及构造谓词函数关于输入变量增量的线性约束系统.理论分析和实例验证该方法具有简单、直观、有效且计算量小等特点.     

Geometry and Convergence Analysis of Algorithms for Registration of 3D Shapes

The computation of a rigid body transformation which optimally aligns a set of measurement points with a surface and related registration problems are studied from the viewpoint of geometry and optimization. We provide a convergence analysis for widely used registration algorithms such as ICP, using either closest points (Besl and McKay, 1992) or tangent planes at closest points (Chen and Medioni, 1991) and for a recently developed approach based on quadratic approximants of the squared distance function (Pottmann et al., 2004). ICP based on closest points exhibits local linear convergence only. Its counterpart which minimizes squared distances to the tangent planes at closest points is a Gauss–Newton iteration; it achieves local quadratic convergence for a zero residual problem and—if enhanced by regularization and step size control—comes close to quadratic convergence in many realistic scenarios. Quadratically convergent algorithms are based on the approach in (Pottmann et al., 2004). The theoretical results are supported by a number of experiments; there, we also compare the algorithms with respect to global convergence behavior, stability and running time.     

Note on Max Lin-2 above Average

In the Max Lin-2 problem we are given a system S of m linear equations in n variables over F₂ in which equation j is assigned a positive integral weight wj for each j. We wish to find an assignment of values to the variables which maximizes the total weight of satisfied equations. This problem generalizes Max Cut. The expected weight of satisfied equations is W/2, where W=w₁+?+wm; W/2 is a tight lower bound on the optimal solution of Max Lin-2.Mahajan et al. (Parameterizing above or below guaranteed values, J. Comput. Syst. Sci. 75 (2009) 137-153) stated the following parameterized version of Max Lin-2: decide whether there is an assignment of values to the variables that satisfies equations of total weight at least W/2+k, where k is the parameter. They asked whether this parameterized problem is fixed-parameter tractable, i.e., can be solved in time f(k)(nm)^O(1), where f(k) is an arbitrary computable function in k only. Their question remains open, but using some probabilistic inequalities and, in one case, a Fourier analysis inequality, Gutin et al. (A probabilistic approach to problems parameterized above tight lower bound, in: Proc. IWPEC'09, in: Lect. Notes Comput. Sci., vol. 5917, 2009, pp. 234-245) proved that the problem is fixed-parameter tractable in three special cases.In this paper we significantly extend two of the three special cases using only tools from combinatorics. We show that one of our results can be used to obtain a combinatorial proof that another problem from Mahajan et al. (Parameterizing above or below guaranteed values, J. Comput. Syst. Sci. 75 (2009) 137-153), Max r-SAT above Average, is fixed-parameter tractable for each r?2. Note that Max r-SAT above Average has been already shown to be fixed-parameter tractable by Alon et al. (Solving MAX-r-SAT above a tight lower bound, in: Proc. SODA 2010, pp. 511-517), but the paper used the approach of Gutin et al. (A probabilistic approach to problems parameterized above tight lower bound, in: Proc. IWPEC'09, in: Lect. Notes Comput. Sci., vol. 5917, 2009, pp. 234-245).     

An acceptance system decision rule with data envelopment analysis

This paper further discusses the suggestion proposed by Troutt et al. [1] that data envelopment analysis (DEA) can be used to develop an acceptance boundary. It is shown that the linear programming model with an arbitrary objective function developed by Troutt et al. [1] can, in fact, be directly obtained from their assumptions. We develop a DEA-type linear programming model to determine not only whether a new case is accepted, but also the location of the new case with respect to the samples proviously classified. A numerical example is provided.     

Output feedback optimal guaranteed cost control of uncertain piecewise linear systems

This paper proposes the output feedback optimal guaranteed cost controller design method for uncertain piecewise linear systems based on the piecewise quadratic Lyapunov functions technique. By constructing piecewise quadratic Lyapunov functions for the closed‐loop augmented systems, the existence of the guaranteed cost controller for closed‐loop uncertain piecewise linear systems is cast as the feasibility of a set of bilinear matrix inequalities (BMIs). Some of the variables in BMIs are set to be searched by genetic algorithm (GA), then for a given chromosome corresponding to the variables in BMIs, the BMIs turn to be linear matrix inequalities (LMIs), and the corresponding non‐convex optimization problem, which minimizes the upper bound on cost function, reduces to a semidefinite programming (SDP) which is convex and can be solved numerically efficiently with the available software. Thus, the output feedback optimal guaranteed cost controller can be obtained by solving the non‐convex optimization problem using the mixed algorithm that combines GA and SDP. Numerical examples show the effectiveness of the proposed method. Copyright © 2008 John Wiley & Sons, Ltd.     

Faster pairing computation on genus 2 hyperelliptic curves

In this paper, new efficient pairings on genus 2 hyperelliptic curves of the form C:y²=x⁵+ax with embedding degree k satisfying 4|k are constructed, that is an improvement for the results of Fan et al. (2008) [10]. Then a variant of Miller?s algorithm is given to compute our pairings. In this algorithm, we just need to evaluate the Miller function at two divisors for each loop iteration. However, Fan et al. had to compute the Miller function at four divisors. Moreover, compared with Fan et al.?s algorithm, the exponentiation calculation is simplified. We finally analyze the computational complexity of our pairings, which shows that our algorithm can save 2036m operations in the base field or be 34.1% faster than Fan et al.?s algorithm. The experimental result shows that our pairing can achieve a better performance.     

H optimization problem with sign-indefinite quadratic form

This paper presents the solution to min-max control problem arising when the matrix C₁^TC₁ of the cost function in the standard H^∞ control problem (Doyle et al., 1989) is replaced by an arbitrary matrix Q 0. This difference is proved to be sufficient for results obtained in (Doyle et al., 1989) not to cover such the case. Their derivations essentially base on the cost function being H^∞ norm and can not be adjusted to deal with sign-indefinite quadratic form. With some sort of strict frequency condition assumed, state space technique is fruitful to obtain the necessary and sufficient conditions of the solvability of the problem. The solution is given by two Riccati equations and has some difference when compared to that of (Doyle et al., 1989).