Any way to use DistributedProblem correctly?

[sjiherzig]

I see that in SearchExecutor a DistributedProblem is created:

...
if (this.getExecutorService() != null) {
    problem = new DistributedProblem((Problem) problem, this.getExecutorService());
} else if (this.getNumberOfThreads() > 1) {
    executorService = Executors.newFixedThreadPool(this.getNumberOfThreads());
    problem = new DistributedProblem((Problem) problem, executorService);
}
...

As expected, the original SearchProblem is passed correctly. However, when it comes to algorithm construction in the following runAlgorithm, the DistributedProblem is not passed all the way: DynamicAlgorithmProvider is responsible for providing one of the IRegisteredAlgorithms through, e.g., the EvolutionaryAlgorithmFactory. However, in EvolutionaryAlgorithmFactory, algorithms are created by passing createProblem() to their constructors. The specific implementation of interest for createProblem is in TransformationSearchOrchestration, which simply returns a new TransformationProblem(...):

@Override
public TransformationProblem createProblem() {
    return new TransformationProblem(getFitnessFunction(), getSolutionGenerator());
}

I've tried to modify the calls in the EvolutionaryAlgorithmFactory to simply create a DistributedProblem with an inner TransformationProblem, a la:

@Override
public NSGAII createAlgorithm() {
    final ExecutorService executorService = Executors
        .newFixedThreadPool(Runtime.getRuntime().availableProcessors());
    final Problem problem = new DistributedProblem(createProblem(), executorService);

    return new NSGAII(problem, createSortingPopulation(), createEpsilonBoxArchive(), selection,
        createVariation(variation), createInitialization());
}

A side note: this is dirty and was done, of course, just to test the use of a DistributedProblem.

Ultimately, this led to a DistributedProblem being passed correctly (even though the created Problem in the SearchExecutor is still existing, but never used). However, now evaluation fails, of course, since none of the TransformationSolutions are FutureSolutions.

Any ideas or hints? Have you had a look into parallelization before? I'd be ready to implement this, but would love to see whether there is a better solution, or if this is even possible (concurrency problems with EMF?).

Sebastian

[sjiherzig]

Investigating further, this may actually not be that easy...

I've experimented with creating a separate DistributedTransformationProblem class that inherits from TransformationProblem where in evaluate(final Solution solution) the fitness function evaluation is submitted as a Future. I was trying to get the evaluation to be triggered latest during TransformationSolution.execute by calling get on the future, but so far no real success (what I had would have likely lead to concurrency issues).

Anyway, any thoughts would be appreciated. This looks like a bigger project...

[martin-fleck-at]

Hi Sebastian,

I think what you are doing is quite interesting. I have not had a look at parallelization so far. From what I see in the MOEA framework, the two relevant classes are indeed DistributedProblem and FutureSolution.

In MOMoT, the SearchExecutor is responsible for running a given algorithm on a problem. It seems one problem stems from the fact that the algorithm is registered with the problem created using TransformationSearchOrchestration, but the SearchExecutor adapts the problem to a distributed problem when we run the search. However, the search executor retrieves the algorithm from the registry and thus there is a discrepancy [1]. So, I think a good solution to this may be to adapt IRegisteredAlgorithm.createAlgorithm to take the Problem as a parameter. Then, SearchExecutor.getAlgorithm should return a newly created algorithm for the provided distributed problem. I have not tried this yet, but I think it may work.

Of course, this only solves the issue of delegating the correct problem. We will need to take care that we create the correct FutureSolution elements and not simple TransformationSolutions for distributed problems. I think a good place for this would be the TransformationSearchOrchestration.createSolutionGenerator. Here we generate a TransformationSolutionGenerator by default, but we would probably need a future solution generator which simply takes the current default and wraps the created solutions into future solutions. In the code of future solutions, they already take care of concurrency a bit, but there may be additional challenges.

I think this may get part of the basis for parallelization going, but I have not tried it out. Unfortunately, I am currently lacking the time to actually implement it, but I will try to help you as much as I can.

Thank you very much and best wishes, Martin

[1] I am surprised that you do not see an error when you are trying to get an algorithm for a distributed problem from the DynamicAlgorithmProvider since it checks whether the problem set in the algorithm and the problem you are querying are the same based on their name. But maybe the DistributedProblem wrapper just has the same name.

[sjiherzig]

Thanks! While this would be the most elegant approach, it has a number of challenges / problems that may not be circumventable without significant rewriting / incorporation of large parts of MOEA: for example, FutureSolution only has a package-private constructor, enabling DistributedProblem to access the constructor, but no other element outside the package. This means that wrapping the TransformationSolution around FutureSolution will not work.

Another major problem with using FutureSolution is the way that the IFitness... evaluators work: e.g., in most cases, an aggregate fitness is computed, requiring, e.g., access to the objectives (via solution.getObjectives) when first evaluating the future (which may be triggered by a call to solution.getConstraints). In FutureSolution this would cause update to be called twice - normally not a problem, but since it is synchronized, the thread would go into deadlock. This is due to the dependence of MultiDimensionalFitnessFunction on both Solution.getObjectives() and Solution.getConstraints(), each of which would try to call the synchronized update.

I've found a way around this by essentially replicating the idea of FutureSolution and DistributedProblem, with slight modifications to the way the aggregate fitness is computed in MultiDimensionalFitnessFunction. It seems to work pretty well (at least it does with the projects I've tested thus far - it's incredibly fast now, distributing evaluations of solutions over all cores). I'll clean it up in the coming days and publish for your review. Still not 100% sure what the impact on EMF concurrency will be (esp. related to calling the OCL engine in parallel), but I'll keep this thread updated.

[martin-fleck-at]

That is great news! Regarding the package private constructor, I must have missed that. There are a few places in MOMoT where we used reflection to incorporate stuff from MOEA to access fields or override methods. So if that would help you in your solution, it is for sure no tabu.

Nevertheless, I trust you are doing a great job and I am looking forward to your code! Thanks!