Parallel Algorithms for Stochastic Dynamic Programming with Continuous State and Control Variables

We compare two partitioning methods for solving a multi-dimensional optimal control problem in parallel using continuous state, continuous control, stochastic dynamic programming (SCP). The algorithm uses tensor products to interpolate the multi-dimensional, continuous variable state space. Unlike previous parallel SDP applications, an iterative optimization routine is used to find the optimal continuous control for each node point in the state space. This routine causes load balance and dependence problems not encountered in previous parallel SDP applications. Even with these additional computational complexities, superb efficiencies are achieved on a shared memory MIMD architecture. The two methods of solution differ in the following way: Method 1 uses the outer state loop index to send subsets of the state space (called parcels) to each concurrent process. The number of parcels sent as parallel tasks is the number of discretizations of one of the state variables. Method 2 allows the user to determine the number of parcels to be sent as parallel tasks. Method 2 splits the state space into a greater number of parcels, so that the processors are more likely to finish at the same time at a synchronization barrier. Computational results indicate that Method 2 has better load balance, with efficiencies up to 93.5%.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.