1

I have some function names which are assigned to some nodes. I have to decide which functions to move to other nodes to increase speed.

Why do I have to move the functions to other nodes? If communicating functions are on same nodes they take less time as compared to if communicating functions are on different nodes. A function might be communicating with several functions (all could be on different nodes). The question is which node do I move it to, to maximize the global performance.

I need to find a globally optimal solution using dynamic programming.

I have the following information

  1. The integer value of the amount of data transferred between functions

  2. The amount of time it takes to transfer data between nodes. Initially all functions have been assigned to some nodes.

Can somebody help me in mapping this problem to the assembly line scheduling algorithm (Dynamic programming) or creating some other dynamic programming solution to this problem?

The hard metric is the execution time of the entire program.The independent running time of a function is calculated by any timer API (We already have it). Its (function's) actual running time would be equal to its independent running time + the running time of all the functions which are producing data consumed by this function + the communication time between this function and other functions on same node + the communication time between this function and functions on other nodes. The program's running time would then be the sum of the running time of all the functions in the program.

I have to minimize the execution time of the program which is the sum of the execution time of all the functions.Each functions execution time is the sum of its own time(precalculated) and the sum of all functions which will will execute before it and its sum with its time spent communicating with other functions(same or different nodes).

  • 1
    The optimal solution is to put all functions onto the same node – so I guess there is a further constraint you haven't mentioned. Another question: Is the latency between nodes always the same, or does it differ as well? Also: what hard metric are you optimizing for? How do you measure global performance? I guess you want to minimize latency × transferred‑data. – amon Nov 21 '13 at 14:26
  • Are all functions identical in terms of cost? Are all nodes identical in terms of performance (how many functions they can run)? – Wilbert Nov 21 '13 at 14:58
  • This could possibly be modeled by assigning each node a budget (per time unit, e.g. CPU cycles), and each function a total cost, so that a node can spread its budget across multiple functions. This would allow a solution where it is faster to run two functions on the same node instead of having them communicate across the network. Would such a model fit the problem? – amon Nov 21 '13 at 15:03
  • 1
    @user109405 I think you mix together too many things: You have n nodes with a performance of x cycles/step, m functions with an estimated cost of y cycles, each taking i arguments with a transport cost of j per dist that connect to node in.... you might want to break it down into smaller problems first. – Wilbert Nov 21 '13 at 15:31
  • @user109405 I am just asking questions in order to build a model – but your problem is still very ill-defined. So let's try this differently: Please provide a function that calculates the running time of a certain functions×nodes configuration. We can then develop a heuristic to find the best configuration. Each optimization problem first needs a hard metric to optimize by, and “parallelism” is no such metric. – amon Nov 21 '13 at 15:34
7

So you have a scenario in which you have many variables which provide an easy-to-test result and you must absolutely know the optimal configuration?

Congratulations! You have yourself an NP-Complete problem. If you absolutely positively must know the optimal configuration, then you must perform a brute-force algorithm to try every single combination. Really, we're not talking about a problem that much different than the bin packing problem.

However, that said, maybe you're flexible on finding that optimal solution. Perhaps it doesn't have to be the best solution, but within 99% of the best solution.

Simulated annealing

Simulated annealing is an excellent approach in general, if you do not mind the fact that you will likely not get the optimal solution. The biggest advantage to this approach is its speed, since you are essentially making better solutions out of existing good solutions.

Upsides: Fast

Downsides: Best solution is not likely

Genetic algorithm

Genetic algorithms are designed to specifically handle these types of problems, which is to say, many variables, but easy to test. You'd have to define configuration solutions, be able to merge two configuration solutions, and be able to create a score based on that configuration (fitness). From there, you generate a population of random configuration solutions and you run it until you get a solution which is satisfactory.

Upsides: Far faster than brute force

Downsides: Not very efficient if there are only a few nodes

Brute force

I would not automatically exclude the brute force algorithm just because it is the slowest. If you have few nodes, you may find that you can get the optimal solution with minimum fuss. In any case, it is the solution that would take the least amount of time to implement and it is worth trying if not to see if this is a feasible solution.

Upsides: Easily implemented, guarantees optimal solution

Downsides: Slow with large amounts of nodes

Conclusion

It's difficult to say what is best suited for your needs, however, one thing is for sure: if getting the optimal solution is your priority, then it makes no difference which algorithm you apply for what concerns precision, since you must search the entire solution space to guarantee that you have the optimal solution. For what concerns speed, brute force is going to be the fastest of the three, since the other algorithms are only ideal for finding a good solution efficiently.

Hope that helps!

  • 1
    Nitpicks: your first paragraph might be read as saying that all easy test to solutions with many variables where you need an optimal solution are NP-complete. Also, NP-complete problems don't require brute force to get the optimal solution. There is a dynamic programming solution to the travelling salesperson problem. It's just that its still an exponetial time algorithm. – Winston Ewert Nov 21 '13 at 16:56
  • @Nell Its ok if I dont get the absolute best solution but its close to the best solution. – user109405 Nov 21 '13 at 16:58
  • 1
    @WinstonEwert I simply meant that there is no quick way to calculate the solution if it is, in fact, NP-complete. It wasn't my intention to mislead anyone. – Neil Nov 21 '13 at 17:12
  • 1
    I know, that's why its a nit pick. – Winston Ewert Nov 21 '13 at 17:16
  • 1
    @user109405 An equation for calculating the optimal solution? Could you write an equation to calculate the optimal solution to the traveling salesman problem? These types of problems require algorithms, not equations. – Neil Nov 22 '13 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy