Uploaded image for project: 'OptaPlanner'
  1. OptaPlanner
  2. PLANNER-76

Multi-threaded incremental Solver (without partitioning): construction heuristics, local search, ...

    XMLWordPrintable

Details

    • Story
    • Resolution: Done
    • Critical
    • 7.9.0.Final
    • None
    • optaplanner-core
    • None
    • 2018 Week 13-14, 2018 Week 15-16, 2018 Week 17-18, 2018 Week 19-22, 2018 Week 23-24, 2018 Week 25-26, 2018 Week 27-29

    Description

      We need to take advantage of multiple CPU's and computer nodes, but we cannot afford to break "incremental score calculation" while we do.
      The gain of incremental score calculation is often numberOfEntities/2, so in practice, this gain is much higher than any gain parallelism could bring us.
      We need to have both: have our cake and eat it too.

      It's a matter of parallelizing the moveScope's.

      Do not confuse with Drools multi-threading, which is at a lower level and coming with the new PHREAK algorithm (in 6.x). Due to thread syncs, I suspect that OptaPlanner moveScope parallelization will be more efficient than Drools score calculation parallelization, but it will be nice to have both options

      Old Description:
      Use Future's to spread all possible moves in each step over a number of threads.
      This number of threads is equal to the number of cpu's by default, as no IO is done during solving.

      Problems:

      • each thread will needs it own WorkingMemory and during a step, each working memory will need to be updated
      • a bunch of classes will need to be thread safe, or at least visibility save, such as bestsolutionrecaller.
      • Barriers will be needed to collect the result of each step
      • decks might be a great way to spread out the load

      Attachments

        Issue Links

          blocks

          Task - Represents a small unit of work that is not end-user facing. PLANNER-137 Planning entity's hashCode() (used by tabu accepter) vs solutionHashCode() (used by solution equality)

          • Critical - To be worked on immediately following BLOCKER issues.
          • Open
          incorporates

          Feature Request - Feature requests from customers and/or users PLANNER-1025 Multithreaded solving: queue design for inter-thread communication

          • Major - To be worked after higher priority work items are addressed. When the severity is high and the effort to change it is low to moderate, this term is chosen. Issues in this category likely have an existing workaround but implementation or execution may be non-trivial.
          • Resolved
          is blocked by

          Task - Represents a small unit of work that is not end-user facing. PLANNER-1020 Add method Move.rebase(Scoredirector) to allow rebasing moves to other threads

          • Major - To be worked after higher priority work items are addressed. When the severity is high and the effort to change it is low to moderate, this term is chosen. Issues in this category likely have an existing workaround but implementation or execution may be non-trivial.
          • Resolved
          is incorporated by

          Story - Created by Jira Software - do not edit or delete. Issue type for a user story. PLANNER-304 Make OptaPlanner even faster (less slow) and even more scalable

          • Major - To be worked after higher priority work items are addressed. When the severity is high and the effort to change it is low to moderate, this term is chosen. Issues in this category likely have an existing workaround but implementation or execution may be non-trivial.
          • Resolved
          is related to

          Feature Request - Feature requests from customers and/or users PLANNER-491 Partitioned Search

          • Blocker - To be worked above all other priorities. This term is chosen when the severity of the issue is very high, has no workaround, or the effort for the change is comparatively low. Issues that may be very publicly visible and could generate significant media attention may also drive a higher priority.
          • Resolved

          Feature Request - Feature requests from customers and/or users PLANNER-61 Multi-threaded Benchmarker in Planner

          • Major - To be worked after higher priority work items are addressed. When the severity is high and the effort to change it is low to moderate, this term is chosen. Issues in this category likely have an existing workaround but implementation or execution may be non-trivial.
          • Resolved

          Feature Request - Feature requests from customers and/or users PLANNER-83 Planner: new Branch and bound solver, which is a better form of a brute force solver

          • Major - To be worked after higher priority work items are addressed. When the severity is high and the effort to change it is low to moderate, this term is chosen. Issues in this category likely have an existing workaround but implementation or execution may be non-trivial.
          • Resolved

          Enhancement - An enhancement to or refactoring of existing functionality that is not configurable by an end user (typically a change made by an internal team that affects users) PLANNER-54 Selectors should support cacheType SOLVER with DroolsScoreDirector and IncrementalScoreDirector too: reuse multi-threading id technology to migrate the selector cache to the new solution clone

          • Optional - The request should be considered desirable but is not an immediate necessity.
          • Open

          Activity

            People

              gdesmet@redhat.com Geoffrey De Smet (Inactive)
              gdesmet@redhat.com Geoffrey De Smet (Inactive)
              Votes:
              12 Vote for this issue
              Watchers:
              7 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: