Implement ParallelEngine

[swagner]

Similar to the ThreadParallelEngine of HL 3.2, a ParallelEngine should be implemented in HL 3.3.

[swagner]

Created branch in r5175.

[swagner]

Added first implementation of ParallelEngine in r5176.

[swagner]

Removed property ExecutionContext in Operator in r5177.

[swagner]

Removing the ExecutionContext property in Operator is not necessary as I found a more elegant (or at least less severe) solution. Therefore revoked changes of r5177 in r5178.

[swagner]

Stored execution contexts locally for each thread in r5183.

[swagner]

Worked on cancellation and refactored code in r5185.

[swagner]

Worked on cancellation and refactored code in r5187.

[swagner]

Adapted DebugEngine according to cancellation changes in r5188.

[swagner]

Merged branch back into trunk in r5193.

[swagner]

Deleted branch in r5194.

[swagner]

epitzer, please review changes of DebugEngine in r5193.

[swagner]

Adapted EAs to enable parallel solution evaluation in r5208.

[swagner]

epitzer reviewed and agreed with changes of DebugEngine in r5193.

[swagner]

Adapted distance matrix calculation in TSPCoordinatesPathEvaluator in r5210 to avoid that multiple distance matrices are created, if the evaluator is executed in parallel.

[swagner]

Updated samples in r5211.

[swagner]

When using GP to solve a symbolic regression or symbolic classification problem with the ParallelEngine, an exception is thrown. It seems that there are still some synchronization issues in the corresponding evaluators.

[mkommend]

Made SimpleArithmeticExpressionInterpreter thread safe with r5223.

[swagner]

Please update GP symbolic regression and symbolic classification samples.

[abeham]

Comments regarding r5208

• OSGA: EvaluatedSolutions should probably not be incremented in each thread by one, but after the parallel region and by the size of SelectedParents. The IntCounter is implemented thread-safe, but it will probably cause a lot of waits. In the case of reevaluating the mutated individuals after the OS, I think it would be okay to do it inside, though of course it would be nicer to just increment by the number of subscopes.
• I'm hesitating to accept the change to IntCounter making it thread-safe. I would like to spark a discussion on providing additional thread-safe variants for basic operators. We could introduce a new plugin HeuristicLab.Operators.(ThreadSafe|Parallel). That way the operator designer doesn't need to make the trade-off, but instead the algorithm designer has to make the decision (which she has to make anyway). It's also more obvious if an operator is thread-safe or not. On the other hand the library is already quite complex and it doesn't get simpler if we add more operators.

Regarding r5210

• I'm fine with that, although I'm swinging in favor of removing the feature from the evaluators and putting it into the problem. What was the reason again that we didn't do this?

[abeham]

TODO for me:

• Remove counting of evaluated solutions from the parallel part
  • OSGA
  • SASEGASA
  • Island OSGA
  • Island GA
  • GA
  • ES
  • NSGA-II
• Add an operator that counts the sub-scopes and increments EvaluatedSolutions accordingly after the parallel part
• Allow parallel evaluation in
  • LocalSearch
  • SimulatedAnnealing (note: does not work)
  • TabuSearch

[abeham]

r5352

• Removed changes to IntCounter that would make it thread-safe, if a thread-safe operator is needed a separate one should be implemented
• Moved counting of evaluated solutions out of the parallel region

[abeham]

r5353

• Adapted local search to perform move evaluation in parallel (using the parallel engine)

[abeham]

r5354

• Adapated Tabu Search to run move evaluations and tabu check in parallel

Note that simulated annealing can't be parallelized easily. It will apply any move as soon as it satisfies the acceptance criterion.

[abeham]

r5356

• Adapted all algorithms to count evaluated solutions / moves and outside of the parallel region
• Used the same pattern in every algorithm: Initialize and collect the variable in the Algorithm and increment it in the main loops and main operators

Please review r5352:5354 and r5356.

The samples should be updated just before the ticket is ready to release.

[mkommend]

Reviewed all changes in the different engines, but I didn't have a look at the according changes in the algorithms.

[swagner]

Replying to abeham:

Regarding r5210

• I'm fine with that, although I'm swinging in favor of removing the feature from the evaluators and putting it into the problem. What was the reason again that we didn't do this?

Yes, that's a good point. I put the distance matrix calculation into the evaluators so that the importer has less work to do. However, this was not the best idea (cf. also ticket #1396). I wrote a comment for ticket #1396 that we should change this.

[swagner]

Changes of r5352:5354 look good. Thanks.