Bill Peck wrote:
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).
I thought this would return
rsl_controllers = set(LabController.query()\
.join(['systems',
'queued_recipes',
'recipeset'])\
_any_ LC which could run _any_ of the tests. May be I am wrong, but I
still think so - though I am not familiar with sqlalchemy (yet), I
understand SQL a bit. if this were supposed to return only LC`s which
could run ALL the tests, sqlalchemy would have to create very
interesting join, which would be dependent on recipes in recipeset.
I wanted to understand the code first, so did not try it yet.
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
>
>
_______________________________________________
Beaker-devel mailing list
Beaker-devel(a)lists.fedorahosted.org
https://fedorahosted.org/mailman/listinfo/beaker-devel