An efficient implementation of dynamic programming

Hello,

I am dealing with the implementation of dynamic programming. The problem is that I have a high dimensional problem to solve, 4 inputs u and 4 states x.

For example, if I choose the following discretization grid, for each input 600 elements and for each state 50 elements. So, should I implement 8 for loops ,which the first one would be parfor loop or should I come combine some Iput/State as a matrix together, in order to reduce the number of loops? What would be the efficient way to solve this 8 dimensional problem?

I tried a 4 dimension problem (3 inputs and 1 state) and computation time was faster, if I choose two loops (1 parfor and 1 for), instead of 1 parfor loop. I guess the handling of a 3 dimensional matrix cost more computation time. Is it correct?

Thank you in advance.

Shane

Answer 1

[Natch Ruengsakulrach]

The question depends on many factors such as job delegation time, job computation time, and the number of workers available. The presence of a for-loop inside “parfor” means that each worker will be assigned to execute a for-loop (including all its iterations), while the absence of it means that each worker shares the workload (iterations of “parfor”). Each method has its own benefits.

The first method will reduce the number of job delegations, so it will improve the overall performance if your job delegation time is significant. The second method has more job delegations but may better utilize all your worker resources. The best way is to measure the computation time of each approach and decide the best one that suits your workflow. Refer to this link on how to measure the performance of your program:

http://www.mathworks.com/help/matlab/matlab_prog/measure-performance-of-your-program.html

[Shane Dominic]

Hello Natch,

thanks for your answer. But is it better to use high order matrixes (3D or 4D) or to separate the calculation it into more for-loops?

From my first experience, it seems to be that the separation technique is much faster. Is it true?

Will the computation time also decrease linear, if the number of cores is increased?