Opened 9 years ago

Closed 9 years ago

#1333 closed feature request (done)

Implement ParallelEngine

Reported by: swagner Owned by: swagner
Priority: high Milestone: HeuristicLab 3.3.3
Component: ParallelEngine Version: 3.3.3
Keywords: Cc:

Description (last modified by swagner)

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

Change History (39)

comment:1 Changed 9 years ago by swagner

  • Milestone changed from HeuristicLab x.x.x to HeuristicLab 3.3.3

comment:2 Changed 9 years ago by swagner

  • Version changed from 3.3.2 to branch

comment:3 Changed 9 years ago by swagner

  • Component changed from ### Undefined ### to ParallelEngine
  • Status changed from new to accepted
  • Version changed from branch to 3.3.2

comment:4 Changed 9 years ago by swagner

  • Description modified (diff)
  • Summary changed from Port ThreadParallelEngine from HL 3.2 to HL 3.3 to Implement ParallelEngine
  • Version changed from 3.3.2 to branch

Created branch in r5175.

comment:5 Changed 9 years ago by swagner

Added first implementation of ParallelEngine in r5176.

comment:6 Changed 9 years ago by swagner

Removed property ExecutionContext in Operator in r5177.

comment:7 Changed 9 years ago by 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.

comment:8 Changed 9 years ago by swagner

Stored execution contexts locally for each thread in r5183.

comment:9 Changed 9 years ago by swagner

Worked on cancellation and refactored code in r5185.

comment:10 Changed 9 years ago by swagner

Worked on cancellation and refactored code in r5187.

comment:11 Changed 9 years ago by swagner

Adapted DebugEngine according to cancellation changes in r5188.

comment:12 Changed 9 years ago by swagner

Merged branch back into trunk in r5193.

comment:13 Changed 9 years ago by swagner

Deleted branch in r5194.

comment:14 Changed 9 years ago by swagner

  • Owner changed from swagner to epitzer
  • Status changed from accepted to reviewing
  • Version changed from branch to 3.3.2

epitzer, please review changes of DebugEngine in r5193.

comment:15 Changed 9 years ago by swagner

  • Owner changed from epitzer to swagner
  • Status changed from reviewing to assigned

comment:16 Changed 9 years ago by swagner

  • Status changed from assigned to accepted

comment:17 Changed 9 years ago by swagner

Adapted EAs to enable parallel solution evaluation in r5208.

comment:18 Changed 9 years ago by swagner

epitzer reviewed and agreed with changes of DebugEngine in r5193.

comment:19 Changed 9 years ago by swagner

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

comment:20 Changed 9 years ago by swagner

Updated samples in r5211.

comment:21 Changed 9 years ago by swagner

  • Owner changed from swagner to gkronber
  • Status changed from accepted to assigned

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.

comment:22 Changed 9 years ago by mkommend

  • Owner changed from gkronber to mkommend

comment:23 Changed 9 years ago by mkommend

  • Owner changed from mkommend to swagner

Made SimpleArithmeticExpressionInterpreter thread safe with r5223.

comment:24 Changed 9 years ago by swagner

  • Status changed from assigned to accepted

comment:25 Changed 9 years ago by swagner

  • Owner changed from swagner to mkommend
  • Status changed from accepted to assigned

Please update GP symbolic regression and symbolic classification samples.

comment:26 Changed 9 years ago by swagner

  • Status changed from assigned to reviewing

comment:27 follow-up: Changed 9 years ago by 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?

comment:28 Changed 9 years ago by abeham

  • Owner changed from mkommend to abeham
  • Status changed from reviewing to assigned

comment:29 Changed 9 years ago by 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
Last edited 9 years ago by abeham (previous) (diff)

comment:30 Changed 9 years ago by 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

comment:31 Changed 9 years ago by abeham

r5353

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

comment:32 Changed 9 years ago by 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.

comment:33 Changed 9 years ago by abeham

  • Owner changed from abeham to swagner
  • Status changed from assigned to reviewing

Please review r5352:5354.

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

Last edited 9 years ago by abeham (previous) (diff)

comment:34 Changed 9 years ago by swagner

  • Owner changed from swagner to mkommend

comment:35 Changed 9 years ago by mkommend

  • Owner changed from mkommend to swagner

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

comment:36 in reply to: ↑ 27 Changed 9 years ago by 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.

comment:37 Changed 9 years ago by swagner

Changes of r5352:5354 look good. Thanks.

comment:38 Changed 9 years ago by swagner

  • Status changed from reviewing to readytorelease

comment:39 Changed 9 years ago by mkommend

  • Resolution set to done
  • Status changed from readytorelease to closed
  • Version changed from 3.3.2 to 3.3.3
Note: See TracTickets for help on using tickets.