An efficient implementation of dynamic programming
4 views (last 30 days)
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.
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: