Parallel Algorithm for Unconstrained Optimization Based on Decomposition Techniques

We present a numerical implementation of the parallel gradient distribution (PGD) method for the solution of large-scale unconstrained optimization problems. The proposed parallel algorithm is characterized by a parallel phase which exploits the portions of the gradient of the objective function assigned to each processor; then, a coordination phase follows which, by a synchronous interaction scheme, optimizes over the partial results obtained by the parallel phase. The parallel and coordination phases are implemented using a quasi-Newton limited-memory BFGS approach. The computational experiments, carried out on a network of UNIX workstations by using the parallel software tool PVM, show that parallelization efficiency was problem dependent and ranged between 0.15 and 8.75. For the 150 problems solved by PGD on more than one processor, 85 cases had parallelization efficiency below 1, while 65 cases had a parallelization efficiency above 1.     

Modelling Techniques for Simulation of Submarine Engagements

The process of designing complex, costly military systems benefits substantially from analyses of performance as predicted by some form of model of the system and its operating environment. In this paper, techniques are described that have been implemented in a suite of computer programs to represent the tactical situations that can develop between two opposing submarines. The kernel of the program suite is the Submarine Interactive Attack Model (SIAM). This is sufficiently versatile that a wide range of scenarios can be simulated, and meaningful statistics for expected submarine performance obtained. Emphasis is placed on the modelling of both the dynamic tactical situations that can evolve in underwater warfare and the tactical decision-making that influences the outcome of submarine operations. Although the techniques have been applied to a specific domain it is believed that they are applicable to a wide range of complex problems.     

Parallel integer relation detection: Techniques and applications

Let be a vector of real numbers. An integer relation algorithm is a computational scheme to find the integers , if they exist, such that . In the past few years, integer relation algorithms have been utilized to discover new results in mathematics and physics. Existing programs for this purpose require very large amounts of computer time, due in part to the requirement for multiprecision arithmetic, yet are poorly suited for parallel processing.

This paper presents a new integer relation algorithm designed for parallel computer systems, but as a bonus it also gives superior results on single processor systems. Single- and multi-level implementations of this algorithm are described, together with performance results on a parallel computer system. Several applications of these programs are discussed, including some new results in mathematical number theory, quantum field theory and chaos theory.

     

考虑加工速率相互干扰的平行机调度最优策略研究

随着智能互联网的应用深入、个性化消费时代的来临,制造服务企业开始注重利用网络平台为客户提供个性化的定制服务,在此过程中派生出了产品设计师可与多名客户在线同步交互的一种新型服务模式。本文根据设计师服务效率受并行服务客户数量影响的特征,将问题刻画为机器处理速度相互影响的一类平行机调度模型,以最小化总完工时间为优化目标,研究设计最优调度方案。首先,对于只有两名设计师且各自同时处理最多两个任务的情形,提出了改进的SPT调度规则,运用归纳法证明了该规则可以生成最优加工方案。其次,对改进的SPT规则进行任务分配方式的适当松驰以便更加易于操作,并证明松驰后的新分配方案保持了解的最优性。最后,将相关结论推广至多名设计师的一般情形。上述研究为个性化在线定制服务模式下的有效调度策略制定提供了良好的理论支撑。     

A Simulation of Techniques for Forecasting Shipments Using Firm Orders-to-Date

Many companies use firm orders-to-date to make forecasts of units to be shipped at a future time t that is j periods away, j = 1, 2,..., h. A number of methods for making these forecasts were developed and evaluated using simulation. The time series for bookings was decomposed into a shipment time series and a time series for factors representing the fraction of shipments booked j periods ahead. Separate techniques were used for the shipments series (namely, naive, exponential smoothing and Bayesian procedures) and for the factors (naive and exponential smoothing procedures). The accuracy of these approaches, as well as an ARIMA model that ignored orders-to-date, was evaluated by using several simulated patterns of bookings. No approach was dominant, but one of the simplest approaches (naive/smoothing) did comparatively well.     

A Simulation Analysis of Advanced Concepts for Semi-automated Mail Processing

Over the last decade, much attention has been given to the development of automated mail processing systems for postal operations. Optical character readers and bar-code sorters have begun to augment the mechanized equipment in use since the mid-1960s. Current automation programmes are aimed at minimizing the growth in labour costs which, at $30.5 billion in the United States, accounted for 83% of the U.S. Postal Service's operating budget in 1988. In this paper, a SLAM II simulation model is developed to assist postal managers in evaluating and implementing new technologies at general mail facilities (GMFs). The Northern Virginia Area GMF, located just outside Washington, D.C., serves as the baseline. Results are presented for a proposed design embodying a variety of new concepts and equipment, including carrier route sequencing. Annual savings of over $6 billion are estimated to accompany nation-wide implementation of this design. Alternative scenarios involving changes in mail volume and address quality are also investigated. The analysis demonstrates the system's sensitivity to relatively modest increases in traffic, and points up the need for integrative long-range planning.     

High Performance Computing Techniques for the FEM Simulation in Structural Mechanics

For the solution of large scale simulations in structural mechanics iterative solving methods are mandatory. The efficiency of such methods can crucially depend on different factors: choice of material parameters, quality of the underlying computational mesh and number of processors in a parallel computing system. We distinguish between three aspects of ‘efficiency’: processor efficiency (degree to which the solving algorithm is able to exploit the processor's computational power), parallel efficiency (ratio between computation and communication times) and numerical efficiency (convergence behaviour). With the new FEM software package Feast we pursue the aim to develop a solver mechanism which at the same time gains high efficiencies in all three aspects, while trying to minimise the mentioned dependencies. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Parallel Markov chain Monte Carlo Simulation by Pre-Fetching

In recent years, parallel processing has become widely available to researchers. It can be applied in an obvious way in the context of Monte Carlo simulation, but techniques for “parallelizing” Markov chain Monte Carlo (MCMC) algorithms are not so obvious, apart from the natural approach of generating multiple chains in parallel. Although generation of parallel chains is generally the easiest approach, in cases where burn-in is a serious problem, it is often desirable to use parallelization to speed up generation of a single chain. This article briefly discusses some existing methods for parallelization of MCMC algorithms, and proposes a new “pre-fetching” algorithm to parallelize generation of a single chain.     

具有学习效应和加工时间可控的平行机排序问题

本文研究了一类不相关平行机的排序问题,在该问题中工件的加工时间既具有学习效应,又资源可控,也就是说在该问题模型中,工件的实际加工时间为其正常的加工时间、加工过程中工件所处位置以及加工时间可控这些变量的函数。该研究的目的是为使得总机器负载和总的控制费用的加权和最小以及总的完工时间和总的控制费用的加权和最小。文章通过对问题的相关性质的分析和证明找到了一个解决问题的最优化算法,并且也证明了在处理机的数量给定的条件下,该问题的时间复杂性为O(n^m+2),最后也给出了相应的数值例子来阐述该问题。     

Massively Parallel Particle Simulations on Graphics Processing Units with CUDA

Particle methods are a powerful tool to model dynamic systems. Thereby, the system is discretized by a large number of particles, which are interacting via local, predefined particle-particle interaction laws. The resulting computational effort includes neighborhood search, computation of interaction forces and state update via time integration. Particle methods are used in a lot of different fields of applications like computer science, physics and engineering sciences. As the analyzed systems' number of particles constantly grow, performance enhancement has become an important part of present algorithm development. Besides the well-established approach of algorithm parallelization on multi-core CPUs or CPU clusters, modern graphics processing units (GPUs) present a different and trend-setting possibility for massive parallelization even on desktop computers. Among the top four supercomputers of the world, three are already using NVIDIA GPUs. In late 2006, NVIDIA introduced the first GPUs optimized for general purpose calculations. This was followed by the introduction of a new computing architecture differing from the standard graphics user-interface like OpenGL. This architecture is called Compute Unified Device Architecture (CUDA). It enables the user to program the GPU using standard C commands with few additional runtime functions. The differences in architecture between CPU and GPU result in a completely different algorithm implementation. So, a performance evaluation of different types of particle systems implemented on a GPU using CUDA and on a standard CPU is presented. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Studies Regarding the Alternate Simulation Techniques for Machine Toolsand Industrial Robots

In the paper are presented results regarding the design, simulation and testing of some robotized structures with parallel kinematics in order to identify appropriate simulation techniques and to reveal the properties of particular studied characteristics. The paper is structured in three parts: introduction regarding the tasks of the simulations techniques and the developed applications, comparison of the results obtained in simulations, considering the working space modelling accuracy and the speed of workspace identification and the last part conclusions. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

目标拦截模拟系统中的造型方法

对目标拦截模拟系统中的造型技术作了研究.包括飞行器造型、地形造型、火焰喷射模拟等.提出了蒙皮技术造型中存在的三个问题及相应改进措施.给出了一个基于蒙皮技术的地形生成新算法.利用嵌套圆台扰动的思想较好地实现了导弹飞行时的火焰喷射模拟.     

Dynamical Particle Simulation with Parallel Cache-Aware Domain Decomposition Strategies

The simulation of large particle systems with the Discrete Element Method can be very time consuming. This is due to the necessity for collision detection between the disordered particles. Various methods, originating from different areas such as computer science, are well established and have been used in various applications. For parallel computations the simulation domain needs to be divided into subdomains to be distributed among the different nodes or machines within a supercomputer or a computer-cluster. The strategy for this domain decomposition has a significant influence on the performance of the calculation. In this paper we discuss some aspects of the development of a hierarchical domain decomposition algorithm that provides flexible adaption of the decomposition pattern to the changing structure of the particle system during the simulation. Thus an even load distribution among the different machines can be maintained. Moreover, the same method is also used to deal with the computational bottleneck caused by the presence of unstructured data. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Parallel Simulation of a Compressible Jet Including Nozzle Modelling

Circular jet flows play an important role for many technical applications. Realistic simulations of such flows require modelling of the nozzle geometry to represent the turbulent state of the boundary layer at the nozzle exit. An available high-order finite-difference code for solving the compressible Navier-Stokes equations on a cylindrical grid was adapted to account for the nozzle geometry within the simulation domain. The code was parallelized using the message-passing interface MPI to be able to complete the simulations within acceptable turn-around times. Validation of the implementation was performed by checking the convergence behaviour of the spatial discretization schemes. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Balancing Workloads and Minimizing Set-up Costs in the Parallel Processing Shop

This paper presents an optimal scheduling algorithm for minimizing set-up costs in the parallel processing shop while meeting workload balancing restrictions.There are M independent batch type jobs which have sequence dependent set-up costs and N parallel processing machines. Each of the M jobs must be processed on exactly one of the N available machines. It is desirable to minimize total changeover costs with the restriction that each machine workload assignment T _n be within P units of the average machine assignment. The paper describes a static problem in which all jobs are available at time zero. The sequence dependent change over costs are identical for each machine. An extension of the algorithm handles nonidentical processor problems.A combinatorial programming approach to the problem is used. For the special case of identical processors, the problem can be treated as a multi-salesman travelling salesman problem. A general branch and bound algorithm and numerical results are given.     

加工时间可控和简单线性增长的平行机排序

本文研究加工时间可控并随开工时间简单线性增长的平行机排序问题.证明了该问题为NP-难问题,该问题存在满足以下性质的最优排序:每个工件的加工时间要么完全压缩,要么完全不压缩;每台机器的工件排序由一个工件参数和控制变量的函数的递增序给出.通过将问题等价转换为0-1非线性整数规划问题,给出了平行机排序问题的贪婪算法.     

多服务台并联排队系统的随机模拟

针对多服务台并联排队系统,提出了计算机随机模拟的方法.分别研究了基本和非基本排队系统中,诸如排队人数、排队时间、平稳分布、忙期及其忙期服务人数等各项排队指标的模拟求解方法.通过模拟例子和实际数据分析,显示了本文所提模拟方法的有效性、灵活性和实用性.