Marian Csontos wrote:
Hi Bill,
A very nice sudoku. Unfortunately I did not have enough free time over
weekend to solve it ;-)
I think the suggested algorithm will not work for following recipeset:
rs = [ set('a','b','c') , set('a','b') ,
set('c') ]
r1 = rs[0] # abc
r2 = rs[1] # ab
r3 = rs[2] # c
if (r1 - r2):
r1 -= r2 # c
# we now have 2 recipes - r1 and r3 with only one machine left in the
set - c. :-(
I have a hunch it is NP-complete problem, so I am not surprised it does
not work in all cases.
For small number of recipes and systems, backtracking will be the most
accurate, with still good performance.
Use heuristic for bigger number of systems.
Suggested algorithm:
1. sort recipes by number of systems in increasing order ( and keep it
sorted )
I've implemented this locally and it seems to solve all the problems.
I'm in the process of creating unit tests to verify that this is doing
everything we think it should be doing. I'll post again when I have
that done.
2. sort systems by number of recipes which can run on this machine (
and
keep it sorted )
Now we have a sort of 2 dimensional {0,1} array/matrix, with recipes
being rows and systems columns.
We are going to find a reordering of columns and rows the first NxN
elements will have all-1 on diagonal.
*Anyone with better/more fresh algebra*?
3. if there are no more recipes to solve OR if there are enough systems
(using Bill's check) - recipeset can run on this LC - return True
4. remove all all-zero columns
5. if there are no more machines - return False
6. if there is a recipe which can run on only one machine - use this
machine and remove row and column. go back to 3.
7. if there is a system which can run only one recipe - use this machine
(it will not affect other recipes) and remove row and column. go back to 3.
8. heuristic module, which returns a (recipe,system) tuple, comes here.
(Note: if LC was not found, which could run the test, use stronger
heuristic/deeper backtracking. )
- Bill's
- Marian's first attempt: choose the system with lowest number of
recipes it can run and assign recipe with lowest number of systems it
can use (rationale: after removing this recipe and system from game, the
densest part of the matrix should remain.)
I think I can change the order of systems I get back in the filtering to
be weighted by how many other recipes the systems match for.
9. Remove row and column and go back to 3.
*Any better algorithms*?
[ I would enjoy to spend more time on this nice problem, but at the
moment I have to move on :-( ]
Plus two more comments - see inline.
-- Marian
Bill Peck wrote:
> Just sending this to the list to get feedback. If you remember from
> previous emails a recipe = a single system. a RecipeSet contains
> mutliple recipes that need to be scheduled at the same time. Also, we
> only want multi-host jobs to be scheduled on the same lab controller.
> A couple problems present themselves right away.
>
> 1) If N-1 recipes are able to be scheduled on a single lab controller
> then we don't want any of those possible systems since we couldn't
> possibly fulfil the recipeset there.
> 2) If RecipeA can use HOSTA or HOSTB but RecipeB can only use HOSTA,
> then we need to remove HOSTA from RecipeA's possible choices.
> 3) If the number of possible Systems in each Recipe is larger than the
> number of Recipes in the RecipeSet Then there are enough choices to
> prevent a dead lock. In other words, we can leave the choices alone.
>
> All of the above has to be done for every lab controller the recipeSet
> matches for. :-)
>
> The following code seems to work. I have tested quite a few
> possibilities and everything works out. It does seem to remove more
> choices than needed in some situations but I can't see an easier way.
> The good news is this is still pretty damn fast. And we only need to
> do it once. (ok, if the inventory server data changes we need to do it
> again), but not every 20 seconds! ;-)
>
> I'm also attaching a small test script that I used to develop the
> ideas below..
>
>
> def processed_recipesets(*args):
> recipesets = RecipeSet.query()\
> .join(['recipes','status'])\
>
> .filter(Recipe.status==TestStatus.by_name(u'Processed'))
>
>
> for recipeset in recipesets:
> bad_l_controllers = set()
> # We only need to do this processing on multi-host recipes
> if len(recipeset.recipes) == 1:
> print "recipe ID %s moved from Processed to Queued" %
> recipeset.recipes[0].id
> recipeset.recipes[0].status = TestStatus.by_name(u'Queued')
> continue
>
> # Find all the lab controllers that this recipeset may run.
> rsl_controllers = set(LabController.query()\
> .join(['systems',
> 'queued_recipes',
> 'recipeset'])\
>
> .filter(RecipeSet.id==recipeset.id).all())
> # Any lab controllers that are not associated to all recipes in
> the
> # recipe set must have those systems on that lab controller
> removed
> # from any recipes. For multi-host all recipes must be
> schedulable
> # on one lab controller
> for recipe in recipeset.recipes:
> rl_controllers = set(LabController.query()\
> .join(['systems',
> 'queued_recipes'])\
>
> .filter(Recipe.id==recipe.id).all())
> bad_l_controllers =
> bad_l_controllers.union(rl_controllers.difference(rsl_controllers))
>
IMO, bad_l_controllers will be always empty: rl_controllers will find
only subset of controllers in rsl_controllers, thus
rl_controllers.difference(rsl_controllers) will be empty, thus the union
will be empty.
Not True.
rsl_controllers will be lab controllers that are in every recipe of this
recipe set (look at the joins).
Consider the following:
RecipeA has two possible hosts: HostA and HostB
RecipeB has two possible hosts: HostC and HostD
LabController1 has HostA, HostC, and HostD
LabController2 has HostB
rsl_controllers will only have LabController1.
For RecipeA rl_controllers will have LabController1 and LabController2
So bad_l_controllers will end up with LabController2
If it founds lc which is not already in rsl_c, there must be a recipe
in
recipeset, which could run on this controller.
But this recipe would be found by first filter as well and the lc would
be in rsl_c.
Am I missing any subtle detail?
Is not it intersection we are looking for here, to find controllers able
to run ALL recipes (rsl_c)?
rsl_controllers = set(recipeset.recipes[0])
for recipe in recipeset.recipes[1:]:
rl_controllers = set(LabController.query()\
.join(['systems',
'queued_recipes'])\
.filter(Recipe.id==recipe.id).all())
rsl_controllers.intersection_update(rl_controllers)
bad_l_controller could be found as original
rsl_controller.difference_update(rsl_c):
bad_l_controllers = set(LabController.query()\
.join(['systems',
'queued_recipes',
'recipeset'])\
.filter(RecipeSet.id==recipeset.id).all())
bad_l_controllers.difference_update(rsl_controllers)
> for l_controller in rsl_controllers:
> enough_systems = False
> for recipe in recipeset.recipes:
> systems = recipe.dyn_systems.filter(
>
> System.lab_controller==l_controller
> ).all()
> if len(systems) < len(recipeset.recipes):
> break
> else:
> # There are enough choices We don't need to worry about
> dead
> # locks
> enough_systems = True
> if not enough_systems:
> # Eliminate bad choices.
> for recipe in recipeset.recipes:
> for tmprecipe in recipeset.recipes:
> systemsa = set(recipe.dyn_systems.filter(
>
> System.lab_controller==l_controller
> ).all())
> systemsb = set(tmprecipe.dyn_systems.filter(
>
> System.lab_controller==l_controller
>
> ).all())
>
> if systemsa.difference(systemsb):
> for rem_system in
> systemsa.intersection(systemsb):
> print "Removing %s from recipe id %s" %
> (rem_system, recipe.id)
> recipe.systems.remove(rem_system)
> for recipe in recipeset.recipes:
> count = 0
> systems = recipe.dyn_systems.filter(
> System.lab_controller==l_controller
> ).all()
> for tmprecipe in recipeset.recipes:
> tmpsystems = tmprecipe.dyn_systems.filter(
>
> System.lab_controller==l_controller
> ).all()
> if recipe != tmprecipe and \
> systems == tmpsystems:
> count += 1
> if len(systems) <= count:
> # Remove all systems from this lc on this rs.
> bad_l_controllers =
> bad_l_controllers.union([l_controller])
>
break
> # Remove systems that are on bad lab controllers
> # This means one of the recipes can be fullfilled on a lab
> controller
> # but not the rest of the recipes in the recipeSet.
> # This could very well remove ALL systems from all recipes in this
> # recipeSet. If that happens then the recipeSet cannot be
> scheduled
> # and will be aborted by the abort process.
> for recipe in recipeset.recipes:
> for l_controller in bad_l_controllers:
> systems = (recipe.dyn_systems.filter(
>
> System.lab_controller==l_controller
> ).all()
> )
> for system in systems:
> print "Removing %s from recipe id %s" % (system,
> recipe.id)
> recipe.systems.remove(system)
> if recipe.systems:
> # Set status to Queued
> print "recipe ID %s moved from Processed to Queued" %
> recipe.id
> recipe.status = TestStatus.by_name(u'Queued')
> else:
> # Set status to Aborted
> print "recipe ID %s moved from Processed to Aborted" %
> recipe.id
> recipe.recipeset.abort('Recipe ID %s does not match any
> systems' % recipe.id)
>
> session.flush()
>
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Beaker-devel mailing list
> Beaker-devel(a)lists.fedorahosted.org
>
https://fedorahosted.org/mailman/listinfo/beaker-devel
>
_______________________________________________
Beaker-devel mailing list
Beaker-devel(a)lists.fedorahosted.org
https://fedorahosted.org/mailman/listinfo/beaker-devel