Parallelization Scheme for an Approximate Solution to Time Constraint Problems

摘要

Solving time constraint problems in wide area distributed computing environment is a challenge. We address this challenge by providing programmers a method to express their problems based on a parallelization scheme. The scheme consists of a decomposition tree defining possible decompositions of a problem into sub-problems and the decomposition dependency graph showing the relative order of execution of sub-problems. We have developed algorithms to address the following issues of the parallelization scheme: the execution of the scheme, the dependency of sub-problems, the min-max problem related to the time constraints of decomposed components. A genetic algorithm has been developed for the max-min problem. Experiment results show the good scalability of the algorithms up to thousands of nodes in each decomposition.