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

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

迭代算法在Excel中的实现探究

迭代算法是指利用计算机反复执行同一个模式的运算,并结合变量因素,实现对最终值的明确。迭代算法是一种线性的函数计算模式,基于不同的运算方式,可以将其分为雅克比迭代、二分法迭代、牛顿迭代等,基于此方程在Excel中的应用,不需要软件便可直观展现计算最终数值。笔者基于迭代算法在Excel中的应用,阐述了迭代算法应用的要点和原理,并对不同迭代算法的应用进行了分析,具有重要借鉴价值。     

迭代硬阈值压缩感知重构算法——IIHT

研究了压缩感知信号重构算法的理论,针对迭代硬阈值(IHT)重构算法对测量矩阵的过分依赖、计算复杂度高、运算时间长的缺点,通过修订迭代硬阈值重构算法的代价函数和自适应地调整迭代步长的选取原则,设计了一种迭代硬阈值重构算法--IIHT。IIHT算法显著提高了信号精确重构的概率,降低了算法的计算复杂度,进一步减少了算法的运算时间,加快了算法的收敛速度。     

一种改进的静态程序切片算法

提出了一种改进的静态程序切片算法,并应用到软件逆向工程中。在处理目标程序的过程间调用时,通过建立参数影射关系表,将过程间调用转换为过程内调用,简化了建立程序依赖图的复杂度;在归纳分析目标程序变量类型的基础上,给出了代数运算法则,对程序中的线性运算代码进行等价变换,缩减了切片程序的规模。最后通过具体的切片实例,证明了改进算法的有效性。     

基于约束满足搜索算法的测试用例生成策略

针对约束系统中非线性谓词函数、指针、数组等复杂运算的求解问题,运用约束满足搜索算法,通过减少约束方程组中参数变量的个数,逐步缩小参数变量的取值范围,提出基于符号法求解约束的改进算法。对含有非线性谓词、数组的程序实例进行实验,结果表明改进算法能有效生成测试用例。     

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

本文以FORTRAN语言作为背景,通过例题首先抽象出向量化中的隐数据依赖关系的概念,继而分类剖析它对串行运算向量化的潜在影响;描述向量运算识别器对于隐数据依赖关系的识别算法。本算法已经基本实现。     

基于软比特域的LT码修正震荡迭代算法

LT码的BP译码算法复杂度较高,在译码时由于Tanner图短环的出现易产生震荡效应。为此,提出一种软比特域迭代译码算法。将双曲正切函数进行变换和量化处理,得到(-1,1)区间的软比特域,并将变量节点信息更新算法变换到软比特域中进行计算。为解决LT码中短环的存在导致某些变量节点的外信息出现震荡效应的问题,给出一种新的震荡判断准则,只有当变量节点在连续2次迭代时符号发生反转,且软比特域值均高于阈值时判定为出现震荡。仿真结果表明,简化软比特域震荡迭代译码算法约比传统BP算法降低75%的运算量,并在误码率性能上逼近BP算法。     

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

以FORTRAN语言作为背景,本文通过例题首先抽象出向量化中的隐数据依赖关系的概念,继而分类剖析它对串行运算向量化的潜在影响,描述向量运算识别器对于隐数据依赖关系的识别算法,本算法已经在银河机上基本实现。     

NURBS曲线拟合的最小二乘渐进迭代逼近优化算法

为了使NURBS曲线更精确地拟合散乱数据点,提出了一种基于最小二乘渐进迭代逼近(least square progressive and iterative approximation,LSPIA)的NURBS曲线拟合优化算法.首先,确定一条初始NURBS曲线,利用LSPIA算法优化控制顶点;然后,分别优化数据点参数,拟合曲线的节点和权因子,每优化好一个变量,重新优化控制顶点;最后,经多次优化迭代得到高精度的NURBS拟合曲线.在优化每类变量时,为了避免被其他变量影响,保持其他变量不变.基于LSPIA的NURBS曲线拟合优化算法充分利用了LSPIA算法的优点,在迭代过程中,可以重复使用前一迭代步骤得到的控制顶点等数据,从而节省了运算时间.算法实例表明,该算法能获得一定保形效果.     

一种改进的Turbo解码与解调混合迭代算法研究

Turbo码的优异性能使得它被广泛应用于新一代通信系统中。在3G与4G通信标准中,由于使用16QAM或更高阶的调制使得每个调制符号中的信息比特具有符号相关性,因此可以考虑在解码端与解调端之间进行相关迭代运算以提高解码的误码率性能。提出一个新的Turbo解码与解调混合迭代算法,通过蒙特卡罗仿真,可以看出最终误码率性能较传统Turbo解码算法有明显提高。     

The saturation algorithm for symbolic state-space exploration

We present various algorithms for generating the state space of an asynchronous system based on the use of multiway decision diagrams to encode sets and Kronecker operators on boolean matrices to encode the next-state function. The Kronecker encoding allows us to recognize and exploit the “locality of effect” that events might have on state variables. In turn, locality information suggests better iteration strategies aimed at minimizing peak memory consumption. In particular, we focus on the saturation strategy, which is completely different from traditional breadth-first symbolic approaches, and extend its applicability to models where the possible values of the state variables are not known a priori. The resulting algorithm merges “on-the-fly” explicit state-space generation of each submodel with symbolic state-space generation of the overall model. Each algorithm we present is implemented in our tool SmArT. This allows us to run fair and detailed comparisons between them on a suite of representative models. Saturation, in particular, is shown to be many orders of magnitude more efficient in terms of memory and time with respect to traditional methods.     

基于随机混沌序列的图像加密算法

混沌系统的参数敏感性、初值敏感性和以同一分布遍历各态的特性很好地对应了密码系统应具备的一些基本特性。本文提出了一种基于随机混沌序列的图像加密算法。在该算法的图像像素的空间置乱过程中,采用了离散的标准映射混沌系统。而在像素的扩散过程中,通过复合离散混沌系统隐藏了混沌序列产生时所经历的迭代次数。理论分析和仿真实验表明,本文提出的算法具有较高的安全性能,特别是在统计攻击、差分攻击和选择明文攻击能力方面具有很好的抗攻击性能。     

Look Left, Look Right, Look Left Again: An Application of Fractal Symbolic Analysis to Linear Algebra Code Restructuring

Fractal symbolic analysis is a symbolic analysis technique for verifying the legality of program transformations. It is strictly more powerful than dependence analysis; for example, it can be used to verify the legality of blocking LU factorization with pivoting, a task for which dependence analysis is inadequate. In this paper, we show how fractal symbolic analysis can be used to convert between left- and right-looking versions of three kernels of central importance in computational science: triangular solve, Cholesky factorization, and LU factorization with pivoting.     

Heuristic algorithms for scheduling iterative task computations ondistributed memory machines

Many partitioned scientific programs can be modeled as iterative executions of computational tasks and represented by iterative task graphs (ITGs). An ITG may or may not have dependence cycles. In this paper, we consider the symbolic scheduling of ITGs on distributed memory architectures with nonzero communication overhead and propose heuristic algorithms for scheduling both cyclic and acyclic ITGs without searching an entire iteration space. Our approach incorporates techniques of software pipelining, graph unfolding, directed acyclic graph (DAG) scheduling, and load balancing. We analyze the asymptotic optimality of the algorithms to show that the derived schedules are competitive to optimal solutions. We also study the sensitivity of scheduling performance on inaccurate weights. Finally, we present experimental results to demonstrate the effectiveness of the optimization techniques     

Dependence uniformization: a loop parallelization technique

Data dependence uniformization, a method for overcoming the difficulties in parallelizing a doubly nested loop with irregular dependence constraints is proposed. This approach is based on the concept of vector decomposition. A simple set of basic dependences is developed from which all dependence constraints can be composed. The set of basic dependences is added to every iteration to replace all original dependences so that the dependence constraints become uniform. An efficient synchronization method is presented to obey the uniform dependence constraints in every iteration     

Detecting value-based scalar dependence

Precise value-based data dependence analysis for scalars is useful for advanced compiler optimizations. The new method presented here for flow and output dependence uses Factored Use and Def chains (FUD chains), our interpretation and extension of Static Single Assignment. It is precise with respect to conditional control flow and dependence vectors. Our method detects dependences which are independent with respect to arbitrary loop nesting, as well as loop-carried dependences. A loop-carried dependence is further classified as being carried from the previous iteration, with distance 1, or from any previous iteration, with direction <. This precision cannot be achieved by traditional analysis, such as dominator information or reaching definitions. To compute anti- and input dependence, we use Factored Redef-Use chains, which are related to FUD chains. We are not aware of any prior work which explicitly deals with scalar data dependence utilizing a sparse graph representation. A preliminary version of this paper appeared in theSeventh Anual Workshop on Languages and Compilers for Parallel Computing, August 1994. Supported in part by NSF Grant CCR-9113885 and a grant from Intel Corporation and the Oregon Advanced Computing Institute.     

Performance Prediction in Symbolic Scheduling of Partitioned Programs with Weight Variation

In this paper we consider the symbolic scheduling of partitioned loop programs which are modeled as iterative task graphs (ITGs). Each task in such a graph is coarse grained and contains a large chunk of computations. The weights of computation and communication vary from one iteration to another depending on the index value of the loop. The goal of scheduling such graphs is to incorporate the symbolic variables in weight functions and loop bounds and provide an asymptotically optimal schedule and predict its performance accurately. We provide a lower bound for optimal scheduling when weights of iterative task graphs change monotonically in the course of iterations and there is a sufficient number of processors. We present a technique that devises a valid symbolic schedule without searching all task instances and examine the asymptotic performance of this schedule compared to an optimal solution. Finally, we present case studies and experimental results on nCUBE-2 to verify our solutions.     

Identification of the position of an equilibrium attitude of the International Space Station as a problem of stable matrix completion

For a discrete model of the angular motion of the International Space Station, using an onboard identification model, the problem of identification of the equilibrium attitude position is solved under the action of aerodynamic, gravitational, gyroscopic moments. It is shown that the convergence of the iteration process is determined by a choice of weight coefficients in the equations of the identification onboard model. In this paper, the possibility of finding numerical values of the weight coefficients by solving the problem of stable matrix completion is addressed. A symbolic method for solving the problem of stable matrix completion is proposed. Using this method, numerical values of the weight coefficients that provide fast convergence of the iteration search of an equilibrium attitude of the International Space Station are obtained.