OR-Tools  8.2
subsolver.cc
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
15
17
18#if !defined(__PORTABLE_PLATFORM__)
19#include "absl/synchronization/mutex.h"
20#include "absl/time/clock.h"
21#endif // __PORTABLE_PLATFORM__
22
23namespace operations_research {
24namespace sat {
25
26namespace {
27
28// Returns the next SubSolver index from which to call GenerateTask(). Note that
29// only SubSolvers for which TaskIsAvailable() is true are considered. Return -1
30// if no SubSolver can generate a new task.
31//
32// For now we use a really basic logic: call the least frequently called.
33int NextSubsolverToSchedule(
34 const std::vector<std::unique_ptr<SubSolver>>& subsolvers,
35 const std::vector<int64>& num_generated_tasks) {
36 int best = -1;
37 for (int i = 0; i < subsolvers.size(); ++i) {
38 if (subsolvers[i]->TaskIsAvailable()) {
39 if (best == -1 || num_generated_tasks[i] < num_generated_tasks[best]) {
40 best = i;
41 }
42 }
43 }
44 if (best != -1) VLOG(1) << "Scheduling " << subsolvers[best]->name();
45 return best;
46}
47
48void SynchronizeAll(const std::vector<std::unique_ptr<SubSolver>>& subsolvers) {
49 for (const auto& subsolver : subsolvers) subsolver->Synchronize();
50}
51
52} // namespace
53
54void SequentialLoop(const std::vector<std::unique_ptr<SubSolver>>& subsolvers) {
55 int64 task_id = 0;
56 std::vector<int64> num_generated_tasks(subsolvers.size(), 0);
57 while (true) {
58 SynchronizeAll(subsolvers);
59 const int best = NextSubsolverToSchedule(subsolvers, num_generated_tasks);
60 if (best == -1) break;
61 num_generated_tasks[best]++;
62 subsolvers[best]->GenerateTask(task_id++)();
63 }
64}
65
66#if defined(__PORTABLE_PLATFORM__)
67
68// On portable platform, we don't support multi-threading for now.
69
71 const std::vector<std::unique_ptr<SubSolver>>& subsolvers,
72 int num_threads) {
73 SequentialLoop(subsolvers);
74}
75
77 const std::vector<std::unique_ptr<SubSolver>>& subsolvers, int num_threads,
78 int batch_size) {
79 SequentialLoop(subsolvers);
80}
81
82#else // __PORTABLE_PLATFORM__
83
85 const std::vector<std::unique_ptr<SubSolver>>& subsolvers, int num_threads,
86 int batch_size) {
87 CHECK_GT(num_threads, 0);
88 CHECK_GT(batch_size, 0);
89 if (batch_size == 1) {
90 return SequentialLoop(subsolvers);
91 }
92
93 int64 task_id = 0;
94 std::vector<int64> num_generated_tasks(subsolvers.size(), 0);
95 while (true) {
96 SynchronizeAll(subsolvers);
97
98 // TODO(user): We could reuse the same ThreadPool as long as we wait for all
99 // the task in a batch to finish before scheduling new ones. Not sure how
100 // to easily do that, so for now we just recreate the pool for each batch.
101 ThreadPool pool("DeterministicLoop", num_threads);
102 pool.StartWorkers();
103
104 int num_in_batch = 0;
105 for (int t = 0; t < batch_size; ++t) {
106 const int best = NextSubsolverToSchedule(subsolvers, num_generated_tasks);
107 if (best == -1) break;
108 ++num_in_batch;
109 num_generated_tasks[best]++;
110 pool.Schedule(subsolvers[best]->GenerateTask(task_id++));
111 }
112 if (num_in_batch == 0) break;
113 }
114}
115
117 const std::vector<std::unique_ptr<SubSolver>>& subsolvers,
118 int num_threads) {
119 CHECK_GT(num_threads, 0);
120 if (num_threads == 1) {
121 return SequentialLoop(subsolvers);
122 }
123
124 // The mutex will protect these two fields. This is used to only keep
125 // num_threads task in-flight and detect when the search is done.
126 absl::Mutex mutex;
127 absl::CondVar thread_available_condition;
128 int num_scheduled_and_not_done = 0;
129
130 ThreadPool pool("NonDeterministicLoop", num_threads);
131 pool.StartWorkers();
132
133 // The lambda below are using little space, but there is no reason
134 // to create millions of them, so we use the blocking nature of
135 // pool.Schedule() when the queue capacity is set.
136 int64 task_id = 0;
137 std::vector<int64> num_generated_tasks(subsolvers.size(), 0);
138 while (true) {
139 bool all_done = false;
140 {
141 absl::MutexLock mutex_lock(&mutex);
142
143 // The stopping condition is that we do not have anything else to generate
144 // once all the task are done and synchronized.
145 if (num_scheduled_and_not_done == 0) all_done = true;
146
147 // Wait if num_scheduled_and_not_done == num_threads.
148 if (num_scheduled_and_not_done == num_threads) {
149 thread_available_condition.Wait(&mutex);
150 }
151 }
152
153 SynchronizeAll(subsolvers);
154 const int best = NextSubsolverToSchedule(subsolvers, num_generated_tasks);
155 if (best == -1) {
156 if (all_done) break;
157
158 // It is hard to know when new info will allows for more task to be
159 // scheduled, so for now we just sleep for a bit. Note that in practice We
160 // will never reach here except at the end of the search because we can
161 // always schedule LNS threads.
162 absl::SleepFor(absl::Milliseconds(1));
163 continue;
164 }
165
166 // Schedule next task.
167 num_generated_tasks[best]++;
168 {
169 absl::MutexLock mutex_lock(&mutex);
170 num_scheduled_and_not_done++;
171 }
172 std::function<void()> task = subsolvers[best]->GenerateTask(task_id++);
173 const std::string name = subsolvers[best]->name();
174 pool.Schedule([task, num_threads, name, &mutex, &num_scheduled_and_not_done,
175 &thread_available_condition]() {
176 task();
177
178 absl::MutexLock mutex_lock(&mutex);
179 VLOG(1) << name << " done.";
180 num_scheduled_and_not_done--;
181 if (num_scheduled_and_not_done == num_threads - 1) {
182 thread_available_condition.SignalAll();
183 }
184 });
185 }
186}
187
188#endif // __PORTABLE_PLATFORM__
189
190} // namespace sat
191} // namespace operations_research
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
#define VLOG(verboselevel)
Definition: base/logging.h:978
void Schedule(std::function< void()> closure)
Definition: threadpool.cc:77
const std::string name
int64_t int64
void DeterministicLoop(const std::vector< std::unique_ptr< SubSolver > > &subsolvers, int num_threads, int batch_size)
Definition: subsolver.cc:84
void SequentialLoop(const std::vector< std::unique_ptr< SubSolver > > &subsolvers)
Definition: subsolver.cc:54
void NonDeterministicLoop(const std::vector< std::unique_ptr< SubSolver > > &subsolvers, int num_threads)
Definition: subsolver.cc:116
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...