Parallel dynamic programming and ship voyage management

The paper is concerned with the design and implementation of a parallel dynamic programming algorithm for use in ship voyage management The basic concepts are presented in terms of a simple model for weather routing. Other factors involved in voyage management, and their inclusion in a more comprehensive algorithm, are also discussed. The algorithms have been developed and implemented using a transputer-based distributed-memory parallel machine using the high-level communication harness CS Tools. Trial calculations over grids of up to 282 nodes have been carried out and the results are presented. Good speed-ups for the calculations have been attained, and the factors affecting the efficiency of the parallel computations are reviewed. These trial calculations indicate that a ship voyage management system based on parallel dynamic programming is likely to be beneficial.     

Parallel dynamic programming on clusters of workstations

The standard DP (dynamic programming) algorithms are limited by the substantial computational demands they put on contemporary serial computers. In this work, the theory behind the solution to serial monadic dynamic programming problems highlights the theory and application of parallel dynamic programming on a general-purpose architecture (cluster or network of workstations). A simple and well-known technique, message passing, is considered. Several parallel serial monadic DP algorithms are proposed, based on the parallelization in the state variables and the parallelization in the decision variables. Algorithms with no interpolation are also proposed. It is demonstrated how constraints introduce load unbalance which affect scalability and how this problem is inherent to DP.     

Parallel processing of optimal-control problems by dynamic programming

A method is presented for the parallel evaluation of optimal-control problems using an iterative method of dynamic programming. The procedure is based on the application of the interaction prediction principle by which the global optimal-control problem is reduced to the optimization of subproblems. Each of these problems is locally optimized using successive approximations of single-variable state-increment dynamic-programming problems. Examples of the parallel solution of multivariable, constrained, nonlinear problems for which the computation is carried out on a microcomputer are given.     

Parallel programming inPanda

Distributed systems are an alternative to shared-memory multiprocessors for the execution of parallel applications.Panda is a run-time system that provides architectural support for efficient parallel and distributed programming. It supplies fast user-level threads and a means for transparent and coordinated sharing of objects across a homogeneous network. The paper motivates the major architectural choices that guided our design. The problem of sharing data in a distributed environment is discussed, and the performance of the mechanisms provided by thePanda prototype implementation is assessed.     

Parallel programming in 2001

Factors driving the growth of parallel computing and those inhibiting its growth are identified. The impact of advances in communication, VLSI technology, and embedded systems on parallel architecture are discussed. The two categories of parallel programs-transformational and reactive-are examined. The use of templates and libraries is considered. Reasoning about parallel processes in the context of software design is discussed. Programming environments and operating systems support are addressed     

Parallel programming with Polaris

Parallel programming tools are limited, making effective parallel programming difficult and cumbersome. Compilers that translate conventional sequential programs into parallel form would liberate programmers from the complexities of explicit, machine oriented parallel programming. The paper discusses parallel programming with Polaris, an experimental translator of conventional Fortran programs that target machines such as the Cray T3D     

Relaxing dynamic programming

The idea of dynamic programming is general and very simple, but the "curse of dimensionality" is often prohibitive and restricts the fields of application. This paper introduces a method to reduce the complexity by relaxing the demand for optimality. The distance from optimality is kept within prespecified bounds and the size of the bounds determines the computational complexity. Several computational examples are considered. The first is optimal switching between linear systems, with application to design of a dc/dc voltage converter. The second is optimal control of a linear system with piecewise linear cost with application to stock order control. Finally, the method is applied to a partially observable Markov decision problem (POMDP).     

Coarse-to-fine dynamic programming

We introduce an extension of dynamic programming, we call "coarse-to-fine dynamic programming" (CFDP), ideally suited to DP problems with large state space. CFDP uses dynamic programming to solve a sequence of coarse approximations which are lower bounds to the original DP problem. These approximations are developed by merging states in the original graph into "superstates" in a coarser graph which uses an optimistic arc cost between superstates. The approximations are designed so that CFDP terminates when the optimal path through the original state graph has been found. CFDP leads to significant decreases in the amount of computation necessary to solve many DP problems and can, in some instances, make otherwise infeasible computations possible. CFDP generalizes to DP problems with continuous state space and we offer a convergence result for this extension. We demonstrate applications of this technique to optimization of functions and boundary estimation in mine recognition     

Parallel programming for multimedia applications

Computing capabilities are continuing to increase with the availability of multi core and many core processors. The wide availability of multi core processors has made parallel programming possible for end user applications running on desktops, workstations, and mobile devices. While parallel hardware has become common, software that exploits parallel capabilities is just beginning to take hold. Multimedia applications, with their data parallel nature and large computing requirements will benefit significantly from parallel programming. In this paper an overview of parallel programming is presented and languages and tools for parallel programming such as OpenMP and CUDA are introduced within the scope of multimedia applications.     

Parallel programming for computer vision

Two Unix environments developed for programming parallel computers to handle image-processing and vision applications are described. Visx is a portable environment for the development of vision applications that has been used for many years on serial computers in research. Visx was adapted to run on a multiprocessor with modest parallelism by using functional decomposition and standard operating-system capabilities to exploit the parallel hardware. Paragon is a high-level environment for multiprocessor systems that has facilities for both functional decomposition and data partitioning. It provides primitives that will work efficiently on several parallel-processing systems. Paragon's primitives can be used to build special image-processing operations, allowing one's own programming environment to be grown naturally     

Lock-free parallel dynamic programming

We show a method for parallelizing top down dynamic programs in a straightforward way by a careful choice of a lock-free shared hash table implementation and randomization of the order in which the dynamic program computes its subproblems. This generic approach is applied to dynamic programs for knapsack, shortest paths, and RNA structure alignment, as well as to a state-of-the-art solution for minimizing the maximum number of open stacks. Experimental results are provided on three different modern multicore architectures which show that this parallelization is effective and reasonably scalable. In particular, we obtain over 10 times speedup for 32 threads on the open stacks problem.     

Parallel programming: An axiomatic approach

This paper develops some ideas expounded in [1]. It distinguishes a number of ways of using parallelism, including disjoint processes, competition, cooperation, and communication. In each case an axiomatic proof rule is given.     

Parallel programming interface for distributed data

The Parallel Programming Interface for Distributed Data (PPIDD) library provides an interface, suitable for use in parallel scientific applications, that delivers communications and global data management. The library can be built either using the Global Arrays (GA) toolkit, or a standard MPI-2 library. This abstraction allows the programmer to write portable parallel codes that can utilise the best, or only, communications library that is available on a particular computing platform.Program summaryProgram title: PPIDDCatalogue identifier: AEEF_v1_0Program summary URL: http://cpc.cs.qub.ac.uk/summaries/AEEF_1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 17 698No. of bytes in distributed program, including test data, etc.: 166 173Distribution format: tar.gzProgramming language: Fortran, CComputer: Many parallel systemsOperating system: VariousHas the code been vectorised or parallelized?: Yes. 2–256 processors usedRAM: 50 MbytesClassification: 6.5External routines: Global Arrays or MPI-2Nature of problem: Many scientific applications require management and communication of data that is global, and the standard MPI-2 protocol provides only low-level methods for the required one-sided remote memory access.Solution method: The Parallel Programming Interface for Distributed Data (PPIDD) library provides an interface, suitable for use in parallel scientific applications, that delivers communications and global data management. The library can be built either using the Global Arrays (GA) toolkit, or a standard MPI-2 library. This abstraction allows the programmer to write portable parallel codes that can utilise the best, or only, communications library that is available on a particular computing platform.Running time: Problem dependent. The test provided with the distribution takes only a few seconds to run.     

Solving nonlinear dynamic models by iterative dynamic programming

The paper presents a discrete-time dynamic programming algorithm that is suitable to track nonlinearities in intertemporal optimization problems. In contrast to using linearization methods for solving intertemporal models, the proposed algorithm operates globally by iteratively computing the value function and the controls in feedback form on a grid. A conjecture of how the trajectories might behave is analytically obtained by letting the discount rate approach infinity. The dynamic found serves as a useful device for computing the trajectories for finite discount rates employing the algorithm. Commencing with a large step and grid size, and then pursuing time step and grid refinements allows for the replication of the nonlinear dynamics for various finite discount rates. As the time step and grid size shrink, the discretization errors vanish. The algorithm is applied to three economic examples. Two examples are of deterministic type; the third is stochastic. In the deterministic cases limit cycles are detected.The present paper draws on joint work with Malte Sieveking whom I want to thank for many discussions.     

Skeletal based programming for dynamic programming on MultiGPU systems

Current parallel systems composed of mixed multi/manycore systems and/with GPUs become more complex due to their heterogeneous nature. The programmability barrier inherent to parallel systems increases almost with each new architecture delivery. The development of libraries, languages, and tools that allow an easy and efficient use in this new scenario is mandatory. Among the proposals found to broach this problem, skeletal programming appeared as a natural alternative to easy the programmability of parallel systems in general, but also the GPU programming in particular. In this paper, we develop a programming skeleton for Dynamic Programming on MultiGPU systems. The skeleton, implemented in CUDA, allows the user to execute parallel codes for MultiGPU just by providing sequential C++ specifications of her problems. The performance and easy of use of this skeleton has been tested on several optimization problems. The experimental results obtained over a cluster of Nvidia Fermi prove the advantages of the approach.     

面向序列的AOI动态规划算法*

虽然面向属性归纳(AOI)方法用在广义特征的寻找非常有用,但它只能挖掘不具有序列性的关系数据的特征。为此,针对银联信用卡数据的特征提出一种以AOI技术为基础的动态规划算法,可以从序列数据中找到广义的特征,并挖据出连续K个有序的广义元组,用来描述用户自定义的K个连续数据区间的广义特征。     

One-at-a-time dynamic programming over polytope

The one-at-a-time dynamic programming method developed by [3] is generalized so that convergence is achieved in a wide range of situations. The method and convergence proof are described together with a numerical example having an 8-dimensional state space. The results obtained indicate the numerical feasibility of the proposed method.