dwavesystems / dwave-hybrid Goto Github PK
View Code? Open in Web Editor NEWHybrid Asynchronous Decomposition Sampler prototype framework.
Home Page: https://docs.ocean.dwavesys.com/projects/hybrid/en/stable/
License: Apache License 2.0
Hybrid Asynchronous Decomposition Sampler prototype framework.
Home Page: https://docs.ocean.dwavesys.com/projects/hybrid/en/stable/
License: Apache License 2.0
Since Runnable.run()
is (via dispatch()
) offloading next()
to an executor, it's possible to run a single instance's next
multiple times in parallel.
This is not a problem if next()
does not mutate the self
, but it could potentially lead to a state lost, or even a deadlock if it does.
Should be categorically ban such a behaviour, or leave the responsibility to the block/workflow developer?
Identity
should never block (even when inside Race
), versus InterruptableIdentity
which is meant to block in Race
to prevent trivially winning and stopping remaining (useful) branches.
Right now, samplers ignore runopts provided to run()
.
Currently, one way of reducing the number of samples (in sampleset) is with the SliceSamples
block (which acts only on one dimension, typically energy).
We would like to have a block that reduces the number of samples, but by eliminating "similar ones", and keeping relatively distinct ones in.
Implement an isoenergetic cluster move (ICM) block, perhaps according to this paper.
Make Runnable.timers
and Runnable.counters
a defaultdict
(or alike).
s1 = hybrid.SimulatedAnnealingProblemSampler(num_reads=1000, sweeps=10000)
s2 = hybrid.SimulatedAnnealingProblemSampler(num_reads=1000, sweeps=10000)
p = hybrid.Parallel(s1, s2)
bqm = dimod.BinaryQuadraticModel({'a': 1}, {}, 0, 'BINARY')
state = hybrid.State.from_problem(bqm)
def time_runnable(runnable, init):
runnable.run(init).result()
return sum(runnable.timers['dispatch.next'])
t_s1 = time_runnable(s1, state)
t_s2 = time_runnable(s2, state)
t_p = time_runnable(p, state)
# (on my laptop)
# t_s1 ~ t_s2 ~ 0.2s
# t_p ~ t_s1 + t_s2 ~ 0.4s
# expected: t_p = max(t_s1, t_s2) ~ 0.2s
Timers are stored in a list, one per call, and counters are scalars updated on each call.
Provide a general underlying object ~ PerfCounter
/StatCounter
/VariableStats
/Trace
/similar that could be used to implement both behaviours + do on-update stats (count/min/max/mean/median).
Block developers could then use such PerfCounter
to trace/log/aggregate values of interest, per iteration (e.g. (sub)problem size, max chain length, best sample energy - maybe even per branch, etc.)
For example:
State.from_problem(bqm, beta=2.3)
t1 = hybrid.TabuProblemSampler(timeout=1000)
t2 = hybrid.TabuProblemSampler(timeout=2000)
w = hybrid.Race(t1, t2)
bqm = dimod.BinaryQuadraticModel({'a': 1}, {}, 0, 'BINARY')
state = hybrid.State.from_problem(bqm)
w.run(state).result()
# sum(w.timers['dispatch.next']) ~ 3 sec!
# -> it should be ~ 2 sec
Surfaced after #155 in "qbsolv-like-alt" example:
Unwind(...) | Parallel(Map(...), Map(...))
To properly fix this, we'll have to make traits more expressive, as well as traits validation more precise.
Right now EID deconstructs problems based solely on variables' energy impacts.
EID (or a new decomposer) should be able to traverse the problem graph, and select a connected subproblem.
We should support at least BFS and PFS traversal modes in EID (or in a new decomposer).
Ideally, traversing would be decoupled from variable weighting. (Weights could seed the traversal.)
Also, min/max chain length (or graph diameter) seem like useful parameters to control the crawl.
Runnable.__init__
to accept more options than it knows how to handle, defer all those to runtime, assuming run
will use them.
In other words, support definition of run time options during construction time.
Once this repo is public with a RTD site, add links to RTD/sampler, RTD/composers, and RTD/decomposers examples for command-line help users (because examples were moved out of class docstrings to RST file)
We need subsamples
for the initial_state
of the anneal.
Implement as infinite loop over Tabu/SA/etc.
For example:
Loop(<body>, convergence=3, timeout=30)
would iterate until output doesn't change over three consecutive iterations, or until 30 seconds of wall clock elapsed.
Alternatively, we could also inspect cumulative runtime of ?
Needed for #101.
For more involved workflows from #138, it might make sense to create them (and/or) as templates that would accept some workflow bits (runnables or parameters), and would construct a workflow according to a template.
Motivating pseudo-code example (see examples/qbsolv-like-alt.py
):
ParallelizedSubsampler = WorkflowTemplate<subsampler, initial_state=None> hybrid.Map(
subsampler
) | hybrid.Reduce(
hybrid.Lambda(merge_substates),
initial_state=initial_state
) | hybrid.SplatComposer()
Later we could use it:
qpu = ParallelizedSubsampler(hybrid.QPUSubproblemAutoEmbeddingSampler())
random = ParallelizedSubsampler(hybrid.RandomSubproblemSampler(), initial_state=some)
Unwind
block can propagate it requires unwinding behaviour from its children via runopts.
Simplify construction if we don't really care about the initial sample (or are happy with min/max/rnd):
state = State.from_problem(bqm, sample=<sample_like | factory_function | None>)
Trait could be:
'x'
: x
in state('x', Type)
: x
in state and isinstance(x, Type)
predicate :: state -> Bool
: predicate(state)
trueLoop
/LoopUntilNoImprovement
, LoopN
, LoopWhileNoImprovement
should:
I am getting the following error when trying to use DWave hybrid:
module 'hybrid' has no attribute 'InterruptableIdentity'
I have installed dwave hybrid from source.
Any idea why am I getting this?
Thank you,
See: https://circleci.com/gh/dwavesystems/dwave-hybrid/2404
When a set of user-supplied constraints are translated into a graph, that graph might have gaps in a sequence of integer node names.
Later, random.choice(range(len(graph))
assumes nodes are sequentially numbered and fails when RNG hits that hole. Here, node zero was not present in the graph because constraints look like [set(), {...}, ...]
.
Make Tabu{Problem,Subproblem}Sampler
accept infinite timeout and make it stoppable.
Similarly for simulated annealing.
The current set of samples from the input state should be used to initialize starting solutions for the underlying SA and Tabu solvers.
Child's context id would be nested under parent's context id, similarly to logging namespaces.
Logging/tracing/profiling subsystem could then use fully qualified context ids to uniquely address events.
To facilitate workflow reuse, "structure sweep", and structure/parameter perturbation, make some standard workflows available under (perhaps) hybrid.reference
or hybrid.workflow
.
We can start with the existing examples (and then keep adding simpler workflows as they are discovered):
Simulate until SAPI supports conditional submit.
bqm = dimod.BinaryQuadraticModel({'x': 0.0, 'y': 0.0, 'z': 8.0, 'a': 2.0, 'b': 0.0, 'c': 6.0},
{('y', 'x'): 2.0, ('z', 'x'): -4.0, ('z', 'y'): -4.0,
('b', 'a'): 2.0, ('c', 'a'): -4.0, ('c', 'b'): -4.0, ('a', 'z'): -4.0},
-1.0, 'BINARY')
sampler = samplers.TabuProblemSampler(bqm, tenure=2, timeout=5)
state = State.from_sample({'x': 0, 'y': 0, 'z': 1, 'a': 1, 'b': 1, 'c': 0}, bqm)
new_state = sampler.next(state)
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-7-e5fcdae3a847> in <module>()
----> 1 new_state = sampler.next(state)
test\dwave-hybrid\hybrid\samplers.py in next(self, state)
197 sampleset = self.sampler.sample(
198 state.problem, init_solution=state.samples, tenure=self.tenure,
--> 199 timeout=self.timeout, num_reads=self.num_reads)
200 return state.updated(samples=sampleset)
201
c:\python27\lib\site-packages\tabu\sampler.pyc in sample(self, bqm, init_solution, tenure, scale_factor, timeout, num_reads)
114
115 if not isinstance(num_reads, int):
--> 116 raise TypeError("'num_reads' should be a positive integer")
117 if num_reads < 1:
118 raise ValueError("'num_reads' should be a positive integer")
TypeError: 'num_reads' should be a positive integer
Stop flag/event/semaphore have to be reset in stoppable elements, otherwise next run will bail-out immediately.
Reading along the examples provided in "Using the Framework", it is not apparent where merge_substates
is defined.
Do we need to include def merge_substates()
in the document from the following file?
https://github.com/dwavesystems/dwave-hybrid/blob/2614c00c07a6bc867292f66e19b73f9e453c8d37/examples/qbsolv-like-alt.py
Use a shallow copy, wrapped in proxy that will do deepcopy of an individual attribute only on demand (when modified, not when accessed).
Currently, QPUSubproblemAutoEmbeddingSampler
will auto-embed with EmbeddingComposite
any structured sampler it receives for qpu_sampler
, thus turning it into an unstructured sampler - which is needed if we want to handle any subproblem out-of-the-box.
The problem is if user is aware of the embedding problems, and wants to pass in a structured sampler which can handle all subproblems we'll throw at it. For example, is it uses FixedEmbeddingComposite
with a clique embedding.
... to simplify the development of Runnables which use a semaphore (threading.Event
) to receive and handle the stop command.
There's a pattern that can be abstracted (see Loop
and Identity
).
Now that it's trivial to include Identity
runnable as an explicit identity branch, endomorphic
feature can be confusing for little benefit.
Consider dropping it altogether, deprecating it, or at least defaulting to off.
Prepending of Runnable
to Branches
fails
>>> Identity() & Branches(Runnable())
...
TypeError: not all branches have the same input dimensionality
but appending works:
>>> Branches(Runnable()) & Identity()
Branches(Runnable(), Identity())
Implement Population Annealing (PA) as an example workflow, and a reference importable workflow.
The runnable branch with QPUSubproblemAutoEmbeddingSampler may raise error with message: ValueError: Problem graph incompatible with solver. Here's the sample code:
# just a random bqm
bqm = dimod.BinaryQuadraticModel({'x': 0.0, 'y': 0.0, 'z': 8.0, 'a': 2.0, 'b': 0.0, 'c': 6.0},
{('y', 'x'): 2.0, ('z', 'x'): -4.0, ('z', 'y'): -4.0,
('b', 'a'): 2.0, ('c', 'a'): -4.0, ('c', 'b'): -4.0, ('a', 'z'): -4.0},
-1.0, 'BINARY')
qpusampler = DWaveSampler()
runnable = EnergyImpactDecomposer(max_size=1) | QPUSubproblemAutoEmbeddingSampler(num_reads=1000, qpu_sampler = qpusampler) | SplatComposer()
main = SimpleIterator(runnable, max_iter=10, convergence=3)
init_state = State.from_sample(min_sample(bqm), bqm)
solution = main.run(init_state).result()
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
<ipython-input-4-34da8c1091f1> in <module>()
10
11 init_state = State.from_sample(min_sample(bqm), bqm)
---> 12 solution = main.run(init_state).result()
~/anaconda3/lib/python3.6/concurrent/futures/_base.py in result(self, timeout)
430 raise CancelledError()
431 elif self._state == FINISHED:
--> 432 return self.__get_result()
433 else:
434 raise TimeoutError()
~/anaconda3/lib/python3.6/concurrent/futures/_base.py in __get_result(self)
382 def __get_result(self):
383 if self._exception:
--> 384 raise self._exception
385 else:
386 return self._result
~/anaconda3/lib/python3.6/concurrent/futures/thread.py in run(self)
54
55 try:
---> 56 result = self.fn(*self.args, **self.kwargs)
57 except BaseException as exc:
58 self.future.set_exception(exc)
~/anaconda3/lib/python3.6/site-packages/hybrid/core.py in dispatch(self, future)
341
342 with self.count('dispatch.next'):
--> 343 new_state = self.next(state)
344
345 self.validate_output_state_traits(new_state)
~/anaconda3/lib/python3.6/site-packages/hybrid/flow.py in next(self, state)
447
448 for iterno in range(self.max_iter):
--> 449 state = self.runnable.run(state).result()
450 state_quality = self.key(state)
451
~/anaconda3/lib/python3.6/concurrent/futures/_base.py in result(self, timeout)
423 raise CancelledError()
424 elif self._state == FINISHED:
--> 425 return self.__get_result()
426
427 self._condition.wait(timeout)
~/anaconda3/lib/python3.6/concurrent/futures/_base.py in __get_result(self)
382 def __get_result(self):
383 if self._exception:
--> 384 raise self._exception
385 else:
386 return self._result
~/anaconda3/lib/python3.6/concurrent/futures/thread.py in run(self)
54
55 try:
---> 56 result = self.fn(*self.args, **self.kwargs)
57 except BaseException as exc:
58 self.future.set_exception(exc)
~/anaconda3/lib/python3.6/site-packages/hybrid/core.py in dispatch(self, future)
341
342 with self.count('dispatch.next'):
--> 343 new_state = self.next(state)
344
345 self.validate_output_state_traits(new_state)
~/anaconda3/lib/python3.6/site-packages/hybrid/flow.py in next(self, state)
134 for component in self.components:
135 state = component.run(state, defer=False)
--> 136 return state.result()
137
138 def error(self, exc):
~/anaconda3/lib/python3.6/concurrent/futures/_base.py in result(self, timeout)
423 raise CancelledError()
424 elif self._state == FINISHED:
--> 425 return self.__get_result()
426
427 self._condition.wait(timeout)
~/anaconda3/lib/python3.6/concurrent/futures/_base.py in __get_result(self)
382 def __get_result(self):
383 if self._exception:
--> 384 raise self._exception
385 else:
386 return self._result
~/anaconda3/lib/python3.6/site-packages/hybrid/core.py in submit(self, fn, *args, **kwargs)
41 # customizable underlying executor (e.g. thread/process/celery/network)
42 try:
---> 43 return Present(result=fn(*args, **kwargs))
44 except Exception as exc:
45 return Present(exception=exc)
~/anaconda3/lib/python3.6/site-packages/hybrid/core.py in dispatch(self, future)
331 except Exception as exc:
332 with self.count('dispatch.resolve.error'):
--> 333 return self.error(exc)
334
335 if not getattr(self, '_initialized', False):
~/anaconda3/lib/python3.6/site-packages/hybrid/core.py in error(self, exc)
312 must be explicitly silenced.
313 """
--> 314 raise exc
315
316 def dispatch(self, future):
~/anaconda3/lib/python3.6/site-packages/hybrid/core.py in dispatch(self, future)
328 with self.count('dispatch.resolve'):
329 try:
--> 330 state = future.result()
331 except Exception as exc:
332 with self.count('dispatch.resolve.error'):
~/anaconda3/lib/python3.6/concurrent/futures/_base.py in result(self, timeout)
423 raise CancelledError()
424 elif self._state == FINISHED:
--> 425 return self.__get_result()
426
427 self._condition.wait(timeout)
~/anaconda3/lib/python3.6/concurrent/futures/_base.py in __get_result(self)
382 def __get_result(self):
383 if self._exception:
--> 384 raise self._exception
385 else:
386 return self._result
~/anaconda3/lib/python3.6/site-packages/hybrid/core.py in submit(self, fn, *args, **kwargs)
41 # customizable underlying executor (e.g. thread/process/celery/network)
42 try:
---> 43 return Present(result=fn(*args, **kwargs))
44 except Exception as exc:
45 return Present(exception=exc)
~/anaconda3/lib/python3.6/site-packages/hybrid/core.py in dispatch(self, future)
341
342 with self.count('dispatch.next'):
--> 343 new_state = self.next(state)
344
345 self.validate_output_state_traits(new_state)
~/anaconda3/lib/python3.6/site-packages/hybrid/samplers.py in next(self, state)
100
101 def next(self, state):
--> 102 response = self.sampler.sample(state.subproblem, num_reads=self.num_reads)
103 return state.updated(subsamples=response)
104
~/anaconda3/lib/python3.6/site-packages/dimod/core/sampler.py in sample(self, bqm, **parameters)
191 elif bqm.vartype is Vartype.BINARY:
192 h, J, offset = bqm.to_ising()
--> 193 response = self.sample_ising(h, J, **parameters)
194 response.change_vartype(Vartype.BINARY, energy_offset=offset)
195 return response
~/anaconda3/lib/python3.6/site-packages/dwave/system/samplers/dwave_sampler.py in sample_ising(self, h, J, **kwargs)
283 num_variables = len(active_variables)
284
--> 285 future = self.solver.sample_ising(h, J, **kwargs)
286
287 return dimod.Response.from_future(future, _result_to_response_hook(active_variables, dimod.SPIN))
~/anaconda3/lib/python3.6/site-packages/dwave/cloud/solver.py in sample_ising(self, linear, quadratic, **params)
196 # Our linear and quadratic objective terms are already separated in an
197 # ising model so we can just directly call `_sample`.
--> 198 return self._sample('ising', linear, quadratic, params)
199
200 def sample_qubo(self, qubo, **params):
~/anaconda3/lib/python3.6/site-packages/dwave/cloud/solver.py in _sample(self, type_, linear, quadratic, params)
251 # Check the problem
252 if not self.check_problem(linear, quadratic):
--> 253 raise ValueError("Problem graph incompatible with solver.")
254
255 # Mix the new parameters with the default parameters
ValueError: Problem graph incompatible with solver.
Something like:
Loop(key=operator.attrgetter('subsamples.first.energy'),
terminate=partial(operator.gt, 1000))
or
Loop(key='subsamples.first.energy', terminate=lambda v: v < 1000)
would terminate looping as soon as value of key function would drop below 1000.
Current implementation sets as a convergence criterion that the resulting energy is unchanged through convergence
number of iterations. In practice that will be infrequently triggered because of fluctuations in the energy landscape. It would be helpful to define a more flexible criterion such as a percentage of energy decrease in a window of iterations. So setting, for example, convergence_x=10, convergence_y=5
would terminate if the energy has decreased >= 5% from its value 10 iterations ago. ("x", "y" could be more intuitive names.) Thank you!
For latest dimod, tests are failing with e.g.:
======================================================================
ERROR: test_default (tests.test_composers.TestSplatComposer)
First subsample is combined with the first sample.
----------------------------------------------------------------------
Traceback (most recent call last):
File "/home/radomir/work/dwave-hybrid/tests/test_composers.py", line 65, in test_default
nextstate = SplatComposer().next(state)
File "/home/radomir/work/dwave-hybrid/hybrid/composers.py", line 44, in next
sample = next(state.samples.change_vartype(state.subsamples.vartype).samples())
TypeError: 'SamplesArray' object is not an iterator
The reason is a change in behaviour of SampleSet::samples()
(from iterator to iterable).
For example:
sa = hybrid.SimulatedAnnealingProblemSampler(sweeps=100)
...
sa.bind(sweeps=1000)
sa.partial(sweeps=1000) # alternatively
would be a syntactic sugar for:
sa.next = functools.partial(sa.next, sweeps=1000)
Sometimes is useful to propagate things like chain_length
.
Alternative is to partially apply those arguments on the passed-in sampler's sample()
.
Imagine you wanting to reset initial states for a sampler:
random_tabu = hybrid.Const(samples=None) | hybrid.TabuProblemSampler()
The requirement right now is for runnables to be pickleable in order for them to be run using hybrid.concurrency.process_executor
. The limitation comes from limitations of ProcessPoolExecutor
, which in turn comes from multiprocessing
.
QPUSubproblemAutoEmbeddingSampler
might fail on the embedding step even if embedding exists (due to heuristic nature of the algorithm used). We might provide some safety net for users by re-trying to embed some small number of times (e.g. retries=3
as a kwarg to the sampler init).
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.