向量并行度指导的循环SIMD向量化方法

SIMD扩展部件是集成到通用处理器中的加速部件,旨在发掘多媒体和科学计算等领域程序的数据级并行.当前两种基本的向量发掘方法分别是发掘迭代间并行的Loop-based方法和发掘迭代内并行的SLP方法.Loop-aware方法是对SLP方法的改进,其思想是首先通过循环展开将迭代间并行转换为迭代内并行,使循环体内的同构语句条数足够多,再利用SLP方法进行向量发掘.但当循环展开不合法或者并行度低于向量化因子时,Loop-aware方法无法实现程序向量并行性的发掘.因此提出了向量并行度指导的循环向量化方法,依据迭代间并行度、迭代内并行度和向量化因子,构建循环向量化方法选择方案,同时提出不充分向量化方法发掘并行度低于向量化因子的循环向量并行性,最后依据向量并行度对生成的向量循环进行展开.经过标准测试集测试,向量并行度指导的循环SIMD向量化方法比Loop-aware方法识别率提升107.5%,性能提升12.1%.     

新型超字级并行改进算法

对于超字级并行（SLP）算法不能有效地处理大型程序中并行代码率较小,且可向量化的代码中可能存在对向量化不利的代码的问题,提出了一种新型的SLP改进算法NSLPO。首先,将程序中不能向量化的非同构语句进行同构化处理,定位SLP丢失的向量化机会;然后,通过冗余节点添加构建最大通用子图,通过冗余删除等优化过程得到同构化之后的补充SLP图,提高程序中代码的并行性;最后,运用节流法将对向量化有害的代码摒除在向量化之外,仅对它们进行标量处理,通过只向量化处理那些向量化有收益的代码以尽可能地提升程序效率。在一组广泛使用的内核测试集中进行实验,结果显示,与SLP算法相比,NSLPO算法性能更优,其执行时间比SLP平均减少9.1%。     

类型转换语句的SLP发掘方法

多媒体技术的迅速发展使得越来越多的处理器集成了SIMD扩展,当前的编译器大多数都已实现了自动向量化功能。为了发掘迭代内并行,一些编译器在自动向量化模块中引入了SLP向量化方法。多媒体数据的密集存储和规则运算使得在处理多媒体数据时需要进行频繁的数据类型转换,而目前的SLP向量化方法对数据类型转换的处理能力还不完善。为了在存在大量数据类型转换语句的程序中发掘更多的SLP向量化机会,提出了一种类型转换语句的SLP发掘方法,它能够在SLP向量化框架下利用数据重组实现具有相同向量化因子和不同向量化因子的数据类型之间的转换。实验结果表明,该方法能够有效地对类型转换语句进行SLP向量化发掘,提高了程序的向量化执行效率。     

一种改进的控制流SIMD向量化方法

SIMD扩展部件是近年来集成到通用处理器中的加速部件,旨在发掘多媒体和科学计算等程序的数据级并行.控制依赖给发掘程序中的数据级并行带来了阻碍,当前不论基于loop-based还是SLP的控制流向量化方法都需要if转换,而没有考虑循环内蕴含的向量并行度,导致生成的向量代码效率较低.此外不精确的代价模型指导控制流向量化,同样导致生成的向量代码效率较低.为此提出了改进的控制流SIMD向量化方法,首先提出了含有控制依赖的循环分布算法,分离循环的可向量化部分和不可向量化部分,同时考虑分布时数据的局部性;其次提出了一种直接向量化控制流的方法,该方法考虑了基本块间的向量重用;最后利用精确的代价模型指导超字选择指令和超字条件分支指令的生成.实验结果表明,与现有的控制流向量化方法相比,本文提出的改进方法生成的向量代码性能提高24%.     

一种基于剪切的SLP向量化方法*

作为多媒体和科学计算等领域重要的程序加速器件之一,SIMD扩展部件现已广泛集成于各类处理器中。自动向量化方法是目前生成SIMD向量化程序的重要手段,超字并行SLP (Superword Level Parallelism)方法现已广泛应用于编译器中,并成为实现基本块级代码向量化的主要手段。SLP在进行收益评估时仅考虑代码段整体向量化的收益,并没有考虑到向量化收益为负的片段会降低最终整体的向量化收益,从而导致SLP方法无法达到最好的向量化效果。基于此,本文提出了一种基于剪切的SLP向量化方法(Throttling SLP,TSLP),通过寻找最优的向量化子图,去除了向量化收益为负的代码段,从而可以获得更好的向量化效果。通过标准测试程序的实验结果表明,与原来的SLP方法相比,TSLP方法平均能够获得9%的性能提升。     

基于Relief和BFO的并行支持向量机算法

针对大数据环境下并行支持向量机(SVM)算法存在冗余数据敏感、参数选取困难、并行化效率低等问题,提出了一种基于Relief和BFO算法的并行SVM算法RBFO-PSVM。首先,基于互信息和Relief算法设计了一种特征权值计算策略MI-Relief,剔除数据集中的冗余特征,有效地降低了冗余数据对并行SVM分类的干扰;接着,提出了基于MapReduce的MR-HBFO算法,并行选取SVM的最优参数,提高SVM的参数寻优能力;最后,提出核聚类策略KCS,减小参与并行化训练的数据集规模,并提出改进CSVM反馈机制的交叉融合级联式并行支持向量机CFCPSVM,结合MapReduce编程框架并行训练SVM,提高了并行SVM的并行化效率。实验表明,RBFO-PSVM算法对大型数据集的分类效果更佳,更适用于大数据环境。     

基于蚁群算法的移动机器人多目标路径规划

迫于工作空间的限制以及对绿色生产理念的追求,在智能制造等领域人们通常需要机器人并行地执行多个任务,因此研究机器人的多目标路径规划更加符合实际需求.针对栅格模型中四、八邻域搜索方向较少的问题,提出了改进的十六邻域搜索方法;同时通过删除冗余转折点对路径进行了平滑处理,改善了路径存在的锯齿效果;结合蚁群优化算法与Dijkstra路径搜索算法,提出了一种多目标路径规划方法.在几种障碍环境中进行了测试,结果表明,上述算法能较好地适应各种不同的地图,即使是复杂度较高的地图,所提算法也能有效地找到一条较优的路径.     

一种向量预选取的分段支持向量机回归算法

针对数据波动剧烈时,一组特定的支持向量机回归参数无法满足随数据分布而改变的要求,导致回归曲线达不到所要求的精度的问题,同时针对如何有效删除在回归过程中某些非必要的数据以加快求解速度的问题,本文提出一种向量预选取的分段支持向量机回归算法．该算法首先根据数据空间分布特点删除一些非必要数据,然后根据不同区域样本的复杂程度对区间进行分段,针对各个区域设置相应的参数．仿真实验证明：p-p-SVR算法在保持回归精度的同时,较传统方法具有更好的泛化性能．     

一种单指令多数据向量化归约方法

单指令多数据(SIMD)扩展部件旨在发掘多媒体程序和科学计算程序的数据级并行,归约操作引起的真依赖给发掘程序中的数据级并行带来了阻碍。但体系结构和指令集的差异,使得面向向量机的归约向量化方法并不适用于SIMD扩展部件。针对上述问题,提出一种面向SIMD扩展部件的归约向量代码生成方法,以及归约的识别方法,利用向量移位指令实现向量代码生成。基于SPEC2006标准测试集的测试结果表明,与未利用归约向量化技术前相比,利用该归约向量化方法后的向量化加速比提高34%,从而验证了该方法的有效性。     

基于跨基本块变换和循环分布的SLP优化技术

现有的SLP优化算法无法处理内层循环中存在的依赖环和归约,并且在基本块边界产生大量的冗余拆包和赋值语句,从而导致向量化效率不高.针对该问题,提出了一种基于跨基本块变换和循环分布的SLP优化算法.该算法以控制流图为基础,根据基本块间各数组变量的Define-Use关系以及跨越基本块之间的数据依赖关系进行跨基本块的向量化变换,有序地采用跨基本块变换和循环分布,尽可能发掘最内层循环基本块内语句的并行性,使SLP自动向量化编译器生成具有更多SIMD指令的向量化代码.实验结果表明,该算法能够隐藏更多跨基本块冗余操作的开销,同时利用跨基本决的数据依较生成更优的SIMD指令,有效地提高了向量化程序的加速比.     

Solving nonconvex nonlinear programs with reverse convex constraints by sequential linear programming

The sequential linear programming (SLP) method for solving nonlinear problems was introduced in the 1960s. Many papers that attempted to use SLP reported poor performance and convergence issues. We found that nonlinear programs with reverse convex constraints, which are the most difficult nonlinear programs with many local optima, are solved (heuristically) very well by SLP. We proved that for this type of problems, the solutions to the sequence of the linear programming problems converge to a local optimum. Since the final solution depends on the starting solution, we propose to apply SLP in a multistart approach starting from randomly generated solutions. This multistart SLP is very easy to implement. We recommend that the research community reconsiders the application of SLP for this type of problems.     

Topology optimization of dielectric substrates for filters and antennas using SIMP

Summary In this paper a novel design procedure based on the integration of full wave Finite Element Analysis (FEA) and a topology design method employing Sequential Linear Programming (SLP) is introduced. The employed design method is the Solid Isotropic Material with Penalization (SIMP) technique formulated as a general non-linear optimization problem. SLP is used to solve the optimization problem with the sensitivity analysis based on the adjoint variable method for complex variables. A key aspect of the proposed design method is the integration of optimization tools with a fast simulator based on the finite element-boundary integral (FE-BI) method. The capability of the design method is demonstrated by two design examples. First, we developed a metamaterial substrate with arbitrary material composition and subject to a pre-specified antenna bandwidth enhancement. The design is verified and its performance is evaluated via measurements and simulation. As a second example, the material distribution for a Thermo-Photovoltaic (TPV) filter subject to pre-specified bandwidth and compactness criteria is designed. Results show that the proposed design method is capable of designing full three-dimensional volumetric material textures and printed conductor topologies for filters and patch antennas with enhanced performance.     

Move limits definition in structural optimization with sequential linear programming. Part I: Optimization algorithm

A variety of numerical methods have been proposed in literature in purpose to deal with the complexity and non-linearity of structural optimization problems. In practical design, sequential linear programming (SLP) is very popular because of its inherent simplicity and because linear solvers (e.g. Simplex) are easily available. However, SLP performance is sensitive to the definition of proper move limits for the design variables which task itself often involves considerable heuristics. This research presents a new SLP algorithm (LESLP--linearization error sequential linear programming) that implements an advanced technique for defining the move limits. The LESLP algorithm is formulated so to overcome the traditional limitations of the SLP method. The new algorithm is successfully tested in weight minimization problems of truss structures with up to hundreds of design variables and thousands of constraints: sizing and configuration problems are considered. Optimization problems of non-truss structures are also presented.The key-ideas of LESLP and the discussion on numerical efficiency of the new algorithm are presented in a two-part paper. The first part concerns the basics of the LESLP formulation and provides potential users with a guide to programming LESLP on computers. In a companion paper, the numerical efficiency, advantages and drawbacks of LESLP are discussed and compared to those of other SLP algorithms recently published or implemented in commercial software packages.     

Adaptive stress limit approach for SLP method of structural optimization

A convergence aid based on adaptive stress limits and for use with the sequential linear programming (SLP) method of structural optimization is presented. The structural optimization problem is formulated using linearized behavioral constraints and is solved by the SLP method with a sequence of stress limits. The stress limits, for each linear programming stage, are modified using information derived from the previous iterations. This approach, by suitably modifying the feasible region, prevents the oscillation of solution due to linearization for nonvertex optimum and also permits disjoint global optimum to be attained. The effectiveness of the approach is demonstrated by applying it to truss structures with vertex, nonvertex, and disjoint global optima.     

Optimal PID Controller Autotuning Design for MIMO Nonlinear Systems Based on the Adaptive SLP Algorithm

In this paper, an adaptive swarm learning process (SLP) algorithm for designing the optimal proportional integral and derivative (PID) parameter for a multiple-input multiple-output (MIMO) control system is proposed. The SLP algorithm is proposed to improve the performance and convergence of PID parameter autotuning by applying the swarm algorithm and the learning process. The adaptive SLP algorithm improves the stability, performance and robustness of the traditional SLP algorithm to apply it to a MIMO control system. It can update the online weights of the SLP algorithm caused by the errors in the settling time, rise time and overshoot of the system based on a stable learning rate. The gradient descent is applied to update the weights. The stable learning rate is verified based on the Lyapunov stability theorem. Additionally, simulations are performed to verify the superiority of the algorithm in terms of performance and robustness. Results that compare the adaptive SLP algorithm with the traditional SLP, a neural network (NN), the genetic algorithm (GA), the particle swarm and optimization (PSO) algorithm and the kidney-inspired algorithm (KIA) based on a two-wheel inverted pendulum system are presented. With respect to performance and robustness, the adaptive SLP algorithm provides a better response than the traditional SLP, NN, GA, PSO and KIA.

     

Two types of El Niño and extratropical sea-level pressure variations

This study applies the nonlinear canonical correlation analysis (NLCCA) to explore the nonlinear relationship between the sea-level pressure (SLP) anomalies over the extratropical North Pacific and sea surface temperature (SST) anomalies in the tropical Pacific during 1985–2009. Our results suggest that the asymmetry between the warm eastern Pacific (EP) El Niño–Aleutian Low mode and the cool EP La Niña–anti-phase of the Aleutian Low mode is exhibited in the first NLCCA mode. Nonlinearity of the first NLCCA SST field is enhanced after 1998, and vice versa for the SLP field. The second NLCCA SST mode reveals weak nonlinearity representing the nonlinear central tropical Pacific (CP) El Niño–CP La Niña modes, while the second SLP field depicts the North Pacific Oscillation and anti-phase with the Aleutian Low phases. The nonlinearity of the second SST and SLP NLCCA modes is found to decrease gradually with time. During 1985–1997, the SST field exhibits linearity, while the SLP field shows weak nonlinearity. During 1997–2009, the SST and SLP fields both display weak linearity. Nonlinearity between the extratropical SLP and SST fields is further weakened from the first period. The Aleutian Low pattern could be excited by both EP and CP El Niños. Moreover, the CP El Niños have more connections with the North Pacific Oscillation state rather than the EP El Niños. Conclusively, this study reveals the asymmetric modes between the SLP and SST by the nonlinear method, and contributes to the understanding of the extratropical SLP variability response to two types El Niño events.     

Move limits definition in structural optimization with sequential linear programming. Part II: Numerical examples

A variety of numerical methods have been proposed in literature in purpose to deal with the complexity and non-linearity of structural optimization problems. In practical design, sequential linear programming (SLP) is very popular because of its inherent simplicity and because linear solvers (e.g. Simplex) are easily available. However, SLP performance is sensitive to the definition of proper move limits for the design variables which task itself often involves considerable heuristics. This research presents a new SLP algorithm (LESLP) that implements an advanced technique for defining the move limits. The linearization error sequential linear programming (LESLP) algorithm is formulated so to overcome the traditional limitations of the SLP method. In a companion paper [Comput. Struct. 81 (2003) 197] the basics of the LESLP formulation along with a guide to programming are provided.The new algorithm is successfully tested in weight minimisation problems of truss structures with up to hundreds of design variables and thousands of constraints: sizing and configuration problems are considered. Optimization problems of non-truss structures are also presented. The numerical efficiency, advantages and drawbacks of LESLP are discussed and compared to those of other SLP algorithms recently published or implemented in commercial software packages.