I am working with an iterative application in a distributed setup. The application has n processes (P1, P2,...Pn) and m iterations. Each process may or may not perform any computation in a given iteration. Initially, each process (and its associated data) is assigned to a separate Virtual Machines (i.e. the first iteration starts with n VMs).

Each process requires different CPU time in each iteration. I am looking at this problem as an instance of bin packing problem. For a given iteration, I fix the bin capacity as the maximum CPU time required by a process in that iteration and migrate the processes to the minimum number of VMs. The migration of process has a cost associated with it.

My goal is to execute the application with minimum cost and minimum increase in makespan of the application.

(The minimum makespan can be achieved by assigning each process to a separate VM but that will increase the cost. Each VM has a single CPU core so when we assign multiple processes to same VM, they execute sequentially. Memory is not a constraint.)

In each iteration, I use bin-packing algorithm to find a minimum number of bins and use the Hungarian algorithm to map bins to VMs.

But sometimes, the cost of migration exceeds the maximum CPU time required in the given iteration, In which case migration becomes an overhead.

Is the problem described above, a variation of bin packing problem? Any suggestions on how to approach this optimization problem.


Your Answer

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

Browse other questions tagged or ask your own question.