Re: [Ksummit-discuss] [TECH TOPIC] Addressing complex dependencies and semantics (v2)

["Luis R. Rodriguez" <mcgrof@kernel.org>]

On Thu, Jul 28, 2016 at 07:04:49PM +0300, Laurent Pinchart wrote:
> On Thursday 28 Jul 2016 09:25:58 Mauro Carvalho Chehab wrote:
> > 
> > For the device-centric media devices, the pipelines should be created by
> > the Kernel, and not via userspace. On such cases, a SAT solver could help
> > to setup the hardware pipelines.
> 
> That's the part I don't get. How is SAT related to that ?

Provided you have figured out how to generalize how describe items and
dependencies, you should be able to use a SAT solver to find optimal dependency
maps.  For instance SAT solvers have been used in challenges to help address
Linux distribution package dependency issues, helping improve the not only if a
request is satisfiable but also help with the most optimal solution.

A SAT solver therefore in theory could be used to help optimal dependency maps
as well for other things, which are kernel-related. For instance we'll baby
step testing this with kconfig [0], if that proves useful we'll have to find
timing / limitations, but it should at least give us a lower order resolution
time, and depending on your requirements it may suffice for some needs.
Furthermore, say you were not time constrained (linker or compiler) and could
order things in code prior to execution, you could sort things out pre-runtime
for a few situations.

This naturally then varies depending on the problem at hand. I've jotted down a
few ideas on the wiki but its really all just scrapbook notes at this point [1]
with an eye towards the long term here, and projecting work on kconfig gets
done.

[0] https://kernelnewbies.org/KernelProjects/kconfig-sat
[1] https://kernelnewbies.org/KernelProjects/linux-sat

  Luis