1 # -*- coding: utf-8 -*-
10 from nepi.util.settools import setclusters
11 from nepi.util.settools import classify
13 class ResourceAllocationError(Exception):
16 def multicardinal(multiset):
17 return sum(quant for c,quant in multiset.iteritems())
19 def avail(cls, partition):
20 contains = classify.classContains
21 return reduce(operator.or_,
22 classify.classComponents(cls, partition),
25 def _log(logstream, message, *args, **kwargs):
28 logstream.write(message % args)
30 logstream.write(message % kwargs)
32 logstream.write(message)
35 def alloc(requests, logstream = None, nonseparable = False, saveinteresting = None, backtracklim = 100000000, verbose = True, sample = random.sample):
37 Takes an iterable over requests, which are iterables of candidate node ids,
38 and returns a specific node id for each request (if successful).
40 If it cannot, it will raise an ResourceAllocationError.
43 # First, materialize the request iterable
44 requests = map(set,requests)
46 # Classify all candidates
47 universe = reduce(operator.or_, requests, set())
48 partition = setclusters.disjoint_partition(*requests)
51 c_reqlist = classify.classify(requests, partition)
54 for c,r in c_reqlist.iteritems()
58 c_uni = map(len, partition)
60 # Perform invariant sanity checks
61 if multicardinal(c_req) > sum(c_uni):
62 raise ResourceAllocationError, "Insufficient resources to grant request"
64 for c,nreq in c_req.iteritems():
65 if nreq > len(avail(c, partition)):
66 raise ResourceAllocationError, "Insufficient resources to grant request, empty categories %s" % (
67 filter(lambda i : classify.classContains(c,i), xrange(len(c))),
70 # Test for separability
72 components = clusters = []
75 classify.classMembers(c, partition)
78 clusters = setclusters.disjoint_sets(*components)
82 _log(logstream, "\nDetected %d clusters", len(clusters))
84 # Requests are separable
85 # Solve each part separately, then rejoin them
87 # Build a class for each cluster
89 compmap = dict([(pid,idx) for idx,pid in enumerate(map(id,components))])
90 for cluster in clusters:
91 cluster_class = classify.getClass(
92 reduce(operator.or_, cluster, set()),
94 clustermaps.append(cluster_class)
96 # Build a plan: assign a cluster to each request
98 for cluster_class in clustermaps:
100 for c, c_requests in c_reqlist.iteritems():
101 if classify.isSubclass(cluster_class, c):
102 plan_reqs.extend(c_requests)
103 plan.append(plan_reqs)
107 for i,plan_req in enumerate(plan):
109 _log(logstream, "Solving cluster %d/%d", i+1, len(plan))
110 partial_results.append(alloc(plan_req,
113 saveinteresting = saveinteresting,
114 backtracklim = backtracklim,
119 _log(logstream, "Joining partial results")
120 reqmap = dict([(pid,idx) for idx,pid in enumerate(map(id,requests))])
121 joint = [None] * len(requests)
122 for partial_result, partial_requests in zip(partial_results, plan):
123 for assignment, partial_request in zip(partial_result, partial_requests):
124 joint[reqmap[id(partial_request)]] = assignment
128 # Non-separable request, solve
129 #_log(logstream, "Non-separable request")
132 partial = collections.defaultdict(list)
135 (c, len(avail(c, partition)))
140 # build a cardinality map
142 (c, [classify.classCardinality(c,partition), -nreq])
143 for c,nreq in req.iteritems()
146 classContains = classify.classContains
147 isSubclass = classify.isSubclass
152 0, # skipped branches
155 def recursive_alloc():
156 # Successful termination condition: all requests satisfied
160 # Try in cardinality order
162 order = heapq.nsmallest(2, req, key=Gavail.__getitem__)
164 order = sorted(req, key=Gavail.__getitem__)
166 # Do backtracking on those whose cardinality leaves a choice
167 # Force a pick when it does not
168 if order and (Gavail[order[0]] <= 1
169 or classify.classCardinality(order[0]) <= 1):
174 #carditem = cardinality[c]
175 for i,bit in enumerate(c):
176 if bit == "1" and Pavail[i]:
177 stats[0] += 1 # ops+1
179 subreq = min(Pavail[i], nreq)
181 # branch sanity check
183 for c2,navail in Gavail.iteritems():
184 if c2 != c and classContains(c2, i) and (navail - subreq) < req.get(c2,0):
185 # Fail branch, don't even try
189 stats[2] += 1 # skipped branches + 1
193 partial[c].append((i,subreq))
195 #carditem[1] -= subreq
198 if classContains(c2, i):
206 # Try to solve recursively
207 success = recursive_alloc()
215 #carditem[1] += subreq
218 if classContains(c2, i):
226 stats[1] += 1 # backtracks + 1
228 if (logstream or (saveinteresting is not None)) and (stats[1] & 0xffff) == 0:
229 _log(logstream, "%r\n%r\n... stats: ops=%d, backtracks=%d, skipped=%d", Gavail, req,
232 if stats[1] == 0x1400000:
233 # Interesting case, log it out
234 _log(logstream, "... interesting case: %r", requests)
236 if saveinteresting is not None:
237 saveinteresting.append(requests)
238 if stats[1] > backtracklim:
242 # We tried and tried... and failed
245 # First try quickly (assign most selective first exclusively)
247 success = recursive_alloc()
249 # If it fails, retry exhaustively (try all assignment orders)
251 success = recursive_alloc()
253 if verbose or (not success or stats[1] or stats[2]):
254 _log(logstream, "%s with stats: ops=%d, backtracks=%d, skipped=%d",
255 ("Succeeded" if success else "Failed"),
259 raise ResourceAllocationError, "Insufficient resources to grant request"
261 # Perform actual assignment
262 Pavail = map(set, partition)
264 for c, partial_assignments in partial.iteritems():
266 for i, nreq in partial_assignments:
269 raise AssertionError, "Cannot allocate resources for supposedly valid solution!"
270 assigned = set(sample(part, nreq))
275 # Format solution for the caller (return a node id for each request)
277 for c,reqs in c_reqlist.iteritems():
284 req_solution.append(solution[c].pop())
289 if __name__ == '__main__':
296 [[9, 11, 12, 14, 16, 17, 18, 20, 21],
299 [4, 5, 6, 7, 8, 11, 12, 13, 18, 22],
300 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22],
301 [6, 10, 11, 13, 14, 15, 16, 18, 20],
302 [3, 7, 8, 9, 10, 12, 14, 17, 22],
303 [0, 1, 3, 4, 5, 6, 7, 8, 10, 13, 14, 17, 19, 21, 22],
306 [[2, 10, 0, 3, 4, 8],
307 [4, 1, 6, 10, 2, 0, 5, 9, 8, 7],
308 [8, 3, 0, 2, 1, 4, 10, 7, 5],
312 [2, 7, 8, 3, 1, 0, 9, 10, 5, 4, 6],
313 [2, 4, 8, 10, 1, 3, 9],
316 [[2, 10, 0, 3, 4, 8],
317 [4, 1, 6, 10, 2, 0, 5, 9, 8, 7],
318 [8, 3, 0, 2, 1, 4, 10, 7, 5],
321 [2, 7, 8, 3, 1, 0, 9, 10, 5, 4, 6],
322 [2, 4, 8, 10, 1, 3, 9],
327 for n,(solvable,req) in enumerate(toughcases):
328 print "Trying #R = %4d, #S = %4d (tough case %d)" % (len(req), len(reduce(operator.or_, map(set,req), set())), n)
330 solution = alloc(req, sys.stdout, verbose=False)
332 print " OK - allocation successful"
334 raise AssertionError, "Case %r had no solution, but got %r" % (req, solution)
335 except ResourceAllocationError:
337 print " OK - allocation not possible"
339 raise AssertionError, "Case %r had a solution, but got none" % (req,)
343 suc_mostlypossible = mostlypossible = 0
344 suc_mostlyimpossible = mostlyimpossible = 0
348 # Fuzzer - mostly impossible cases
349 for i in xrange(10000):
350 nreq = random.randint(1,20)
351 nsrv = random.randint(max(1,nreq-5),50)
354 random.sample(srv, random.randint(1,nsrv))
355 for j in xrange(nreq)
357 print "Trying %5d: #R = %4d, #S = %4d... " % (i, nreq, nsrv),
359 mostlyimpossible += 1
361 solution = alloc(req, sys.stdout, saveinteresting = interesting, verbose=False)
362 suc_mostlyimpossible += 1
363 print " OK - allocation successful \r",
364 except ResourceAllocationError:
365 print " OK - allocation not possible \r",
366 except KeyboardInterrupt:
367 print "ABORTING CASE %r" % (req,)
371 # Fuzzer - mostly possible cases
372 for i in xrange(10000):
373 nreq = random.randint(1,10)
374 nsrv = random.randint(nreq,100)
377 random.sample(srv, random.randint(min(nreq,nsrv),nsrv))
378 for j in xrange(nreq)
380 print "Trying %5d: #R = %4d, #S = %4d... " % (i, nreq, nsrv),
384 solution = alloc(req, sys.stdout, saveinteresting = interesting, verbose=False)
385 suc_mostlypossible += 1
386 print " OK - allocation successful \r",
387 except ResourceAllocationError:
388 print " OK - allocation not possible \r",
389 except KeyboardInterrupt:
390 print "ABORTING CASE %r" % (req,)
394 # Fuzzer - biiig cases
396 nreq = random.randint(1,500)
397 nsrv = random.randint(1,8000)
400 random.sample(srv, random.randint(min(nreq,nsrv),nsrv))
401 for j in xrange(nreq)
403 print "Trying %4d: #R = %4d, #S = %4d... " % (i, nreq, nsrv),
407 solution = alloc(req, sys.stdout, saveinteresting = interesting, verbose=False)
409 print " OK - allocation successful \r",
410 except ResourceAllocationError:
411 print " OK - allocation not possible \r",
412 except KeyboardInterrupt:
413 print "ABORTING CASE %r" % (req,)
417 print "ABORTING TEST"
419 print "\nSuccess rates:"
420 print " Mostly possible: %d/%d (%.2f%%)" % (suc_mostlypossible, mostlypossible, 100.0 * suc_mostlypossible / max(1,mostlypossible))
421 print " Mostly impossible: %d/%d (%.2f%%)" % (suc_mostlyimpossible, mostlyimpossible, 100.0 * suc_mostlyimpossible / max(1,mostlyimpossible))
422 print " Huge: %d/%d (%.2f%%)" % (suc_huge, huge, 100.0 * suc_huge / max(1,huge))
425 print "%d interesting requests:" % (len(interesting),)
426 for n,req in enumerate(interesting):
427 print "Interesting request %d/%d: %r", (n,len(interesting),req,)