Speedup estimates for some variants of the parallel implementations of the branch-and-bound method

The efficiency of parallel implementations of the branch-and-bound method in discrete optimization problems is considered. A theoretical analysis and comparison of two parallel implementations of this method is performed. A mathematical model of the computation process is constructed and used to obtain estimates of the maximum possible speedup. Examples of problems in which none of these two parallel implementations can speed up the computations are considered.     

A new type SVM-projected SVM

Support vector machine (SVM), developed by Vapnik et al., is a new and promising technique for classification and regression and has been proved to be competitive with the best available learning machines in many applications. However, the classification speed of SVM is substantially slower than that of other techniques with similar generalization ability. A new type SVM named projected SVM (PSVM), which is a combination of feature vector selection (FVS) method and linear SVM (LSVM), is proposed in present paper. In PSVM, the FVS method is first used to select a relevant subset (feature vectors, FVs) from the training data, and then both the training data and the test data are projected into the subspace constructed by FVs, and finally linear SVM(LSVM) is applied to classify the projected data. The time required by PSVM to calculate the class of new samples is proportional to the count of FVs. In most cases, the count of FVs is smaller than that of support vectors (SVs), and therefore PSVM is faster than SVM in running. Compared with other speeding-up techniques of SVM, PSVM is proved to possess not only speeding-up ability but also de-noising ability for high-noised data, and is found to be of potential use in mechanical fault pattern recognition.     

适用于Linux系统的高效可并行电磁PIC计算技术

为了能够使大型机和高性能集群得到更好的加速比和并行计算效率,在深入研究并行和FDTD-PIC算法的基础上,在CHIPIC软件平台上开发了Linux系统下的大型全三维可并行电磁PIC代码。分别以一个磁绝缘线振荡器、回旋管和相对论速调管为例进行测试和计算,得到了3.70,6.72和6.00的加速比,验证了在同等的进程数下,高性能集群能够得到比PC机群高得多的加速比和计算效率,能够更好地利用计算资源。     

Parallel implementation of the p‐version of the finite element method for elliptic equations on a shared‐memory architecture

An implementation of the p‐version of the finite element method for solving two‐dimensional linear elliptic problems on a shared‐memory parallel computer is analyzed. The idea is to partition the problem among the available processors and perform computations corresponding to different elements in parallel. The parallelization is based on a domain decomposition technique using the Lagrange multipliers. The numerical experiments carried out on the Sequent system indicate very high performance of the mixed finite element algorithm in terms of attained speedups. This revised version was published online in August 2006 with corrections to the Cover Date.     

MPI在蒙特卡罗程序GMT中的应用和发展

针对ADS颗粒靶概念的研究和设计,中国科学院近代物理研究所自主研发了蒙特卡罗模拟软件GMT。为了提高GMT程序的计算效率,研究了MPI在GMT中的应用和发展,实现了大规模随机数在进程中的随机分配,并采用快速读写文件的方式替代了MPI相关数据通信函数,极大地提高了计算效率。并研究了不同规模计算实例进程数、加速比、效率之间的关系,确定了最大加速进程数及并行效率最高时的进程数,为科研工作者在计算资源和计算效率之间选择最优计算方案提供了科学依据。MPI在GMT中的成功应用使计算资源得到了充分、高效的利用,极大地提高了计算效率,解决了蒙特卡罗方法中大规模事件模拟计算时间长、计算不稳定等问题,在散裂靶大规模扫描计算中发挥了重要的作用。For the research and design of the ADS granular-flow target concept, the Institute of Modern Physics, CAS has developed a Monte Carlo simulation software (GPU-accelerated Monte Carlo Transport program, GMT). In order to improve the computational efficiency of the GMT program, development and application of MPI in GMT were studied, to realize random distribution of the large-scale random number in the sub processes. Rapid reading and writing files were employed instead of the MPI data communication function, which greatly improves the computational efficiency. Different scale calculations were performed to study the relationship of process instance number, speedup to find the maximum acceleration process number and the number of processes when parallel efficiency is highest, which provides a scientific basis for researchers to optimize the computational program between computational resources and computation efficiency. The successful application of MPI in GMT, utilizes the computing resources fully and efficiently, improves the computational efficiency, solve the long time cost and unstable problem of Monte Carlo method in large-scale event simulations, plays an important role in the large-scale scanning calculation of the spallation target.     

A parallel method for finding the global minimum of univariate functions

We describe a new parallel method for solving global optimization problems. The formulation of the decision rules of this method is presented. We examine convergence conditions of the proposed algorithm and establish conditions which guarantee a considerable speedup with respect to the sequential version of the algorithm. We also present some numerical experiments executed on Alliant FX/80 for one class of multiextremal functions.The authors are greatly indebted to R. G. Strongin who stimulated the fulfillment of this research. They also would like to thank the anonymous referees for their useful suggestions.The research of the first author was partially supported by Grant 9494/NC/89 from the Italian Government under the Italian-Soviet Agreement about the Cultural and Scientific Exchange in 1990–1991. He thanks the Systems Department, University of Calabria, where he was a Visitor.     

结构模态分析的有限元并行模拟

以子结构模态综合分析为基础,提出一种求解大型结构特征值问题的并行解法．采用子结构模态综合算法,结构特征模态采用子空间迭代方式并行求解．这种子空间迭代法的子结构并行计算的实施是利用子结构的刚度阵和质量阵而不必完全组集系统刚度阵和质量阵求解综合系统的特征值问题．数值结果表明这种求解大型结构特征值问题的并行算法是可行有效的．     

基于消息传递接口的空中爆炸问题的并行计算

研究了用于处理三维多物质欧拉网格的模糊界面技术以及算法存在的数据相关性问题,提出了解决数据相关性的方法。采用基于消息传递接口(MPI)模式,设计出了相应的MMIC-3D并行程序,得到了无限空气介质中爆炸的三维数值模拟结果,计算结果与实际的实验现象及规律基本吻合。在共享存储的全对称多处理机(SMP)上进行了测试,得到了理想的加速比。     

A Parallel Algorithm for Multiple Objective Linear Programs

This paper presents an ADBASE-based parallel algorithm forsolving multiple objective linear programs (MOLPs). Job balance,speedup and scalability are of primary interest in evaluatingefficiency of the new algorithm. The scalability of a parallelalgorithm is a measure of its capacity to increase performance withrespect to the number of processors used. Implementation results onIntel iPSC/2 and Paragon multiprocessors show that the algorithmsignificantly speeds up the process of solving MOLPs, which isunderstood as generating all or some efficient extreme points andunbounded efficient edges. The algorithm is shown to be scalable andgives better results for large problems. Motivation andjustification for solving large MOLPs are also included.     

An improved partial enumeration algorithm for integer programming problems

In this paper, we present an improved Partial Enumeration Algorithm for Integer Programming Problems by developing a special algorithm, named PE_SPEEDUP (partial enumeration speedup), to use whatever explicit linear constraints are present to speedup the search for a solution. The method is easy to understand and implement, yet very effective in dealing with many integer programming problems, including knapsack problems, reliability optimization, and spare allocation problems. The algorithm is based on monotonicity properties of the problem functions, and uses function values only; it does not require continuity or differentiability of the problem functions. This allows its use on problems whose functions cannot be expressed in closed algebraic form. The reliability and efficiency of the proposed PE_SPEEDUP algorithm has been demonstrated on some integer optimization problems taken from the literature.