An efficient implementation of dynamic programming

3 views (last 30 days)
Shane Dominic
Shane Dominic on 29 Aug 2016
Edited: Shane Dominic on 1 Sep 2016
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

Answers (1)

Natch Ruengsakulrach
Natch Ruengsakulrach on 31 Aug 2016
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:
  1 Comment
Shane Dominic
Shane Dominic on 1 Sep 2016
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?

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!