litmus-rt.git - The LITMUS^RT kernel.

diff options

author	Linus Torvalds <torvalds@linux-foundation.org>	2009-09-05 16:48:37 -0400
committer	Linus Torvalds <torvalds@linux-foundation.org>	2009-09-05 16:48:37 -0400
commit	93697a3cabd3605c434a9b915c0272ad800b3f97 (patch)
tree	dc26826f10979e02efbd2c6a87b326b770284b18 /lib/dma-debug.c
parent	63995344721be45b3fb3b76488b1b0a8c95def26 (diff)
parent	a3df6f7d3090e611bcc774cd2cba45ae016d37e1 (diff)

Merge branch 'perfcounters-fixes-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip

* 'perfcounters-fixes-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip: perf_counter/powerpc: Fix cache event codes for POWER7 perf_counter: Fix /0 bug in swcounters perf_counters: Increase paranoia level

Diffstat (limited to 'lib/dma-debug.c')

0 files changed, 0 insertions, 0 deletions

17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147

151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237

442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500

#!/usr/bin/env python from __future__ import division import copy import math import random import schedcat.mapping.binpack as bp def clear_partitioning(ts): for t in ts: t.partition = -1 return ts def partition_no_cache(ts, gs, subts, clustersz, nr_clusters, model, aggressiveness, overheads): """Partition using worst-fit utilization. Ignores caching effects.""" partitions = bp.worst_fit(ts, nr_clusters, capacity = clustersz, weight = lambda t: t.utilization(), misfit = bp.report_failure) for i,p in enumerate(partitions): for t in p: t.partition = i return ts def __filter_by_neigborhood_util(overheads, sets, sums, clustersz, candidates, num_levels_up = 1): # sanity check if not candidates or clustersz >= overheads.consumer.system.ncpus: return candidates cur_dist = overheads.consumer.system.distance(0, clustersz-1) neighborhoodsz = clustersz while neighborhoodsz < overheads.consumer.system.ncpus and overheads.consumer.system.distance(0,neighborhoodsz) != cur_dist + num_levels_up + 1: neighborhoodsz += clustersz # No useful information if there is just one neighborhood if neighborhoodsz == overheads.consumer.system.ncpus: return candidates assert overheads.consumer.system.distance(0,neighborhoodsz-1) == cur_dist + num_levels_up num_neighborhoods = int(overheads.consumer.system.ncpus / neighborhoodsz) num_clusters_in_neighborhood = int(neighborhoodsz / clustersz) neighborhood_sums = [0.0 for _ in xrange(0, num_neighborhoods)] for i,s in enumerate(sums): idx = int(i/num_clusters_in_neighborhood) neighborhood_sums[idx] += s min_util = min(neighborhood_sums) # pick out neighborhoods with the minimum utilization candidate_neighborhoods = [i for i,n in enumerate(neighborhood_sums) if n == min_util] # currently have no criteria to tie-break among neighborhoods, so just # filter against them all filtered = [] for n in candidate_neighborhoods: lo_cluster = n * num_clusters_in_neighborhood hi_cluster = (n + 1) * num_clusters_in_neighborhood - 1 filtered.extend(filter(lambda c: c >= lo_cluster and c <= hi_cluster, candidates)) if filtered: return filtered # Least-utilized neighborhood does not contain a candidate partition (e.g., # a least utilized partition). Recurse until we find a neighborhood that # contains a candidate partition. return __filter_by_neigborhood_util(overheads, sets, sums, clustersz, candidates, num_levels_up + 1) def __filter_by_neigborhood(overheads, sets, sums, clustersz, graph_partition_info, candidates, num_levels_up = 1): # sanity check if not candidates or clustersz >= overheads.consumer.system.ncpus: return None cur_dist = overheads.consumer.system.distance(0, clustersz-1) neighborhoodsz = clustersz while neighborhoodsz < overheads.consumer.system.ncpus and overheads.consumer.system.distance(0,neighborhoodsz) != cur_dist + num_levels_up + 1: neighborhoodsz += clustersz # No useful information if there is just one neighborhood if neighborhoodsz == overheads.consumer.system.ncpus: return None assert overheads.consumer.system.distance(0,neighborhoodsz-1) == cur_dist + num_levels_up num_neighborhoods = int(overheads.consumer.system.ncpus / neighborhoodsz) num_clusters_in_neighborhood = int(neighborhoodsz / clustersz) neighborhood_counts = [0 for _ in xrange(0, num_neighborhoods)] neighborhood_sums = [0.0 for _ in xrange(0, num_neighborhoods)] for i,s in enumerate(sums): idx = int(i/num_clusters_in_neighborhood) neighborhood_counts[idx] += graph_partition_info[i] neighborhood_sums[idx] += s max_counts = max(neighborhood_counts) assert max_counts != 0 # pick out only the maximum-affinity neighborhoods candidate_neighborhoods = [i for i,n in enumerate(neighborhood_counts) if n == max_counts] # sort by utilization, least to greatest candidate_neighborhoods.sort(key = lambda n: neighborhood_sums[n]) # return the first neighborhood (least util) that overlaps the candidates for n in candidate_neighborhoods: lo_cluster = n * num_clusters_in_neighborhood hi_cluster = (n + 1) * num_clusters_in_neighborhood - 1 filtered = filter(lambda c: c >= lo_cluster and c <= hi_cluster, candidates) if filtered: return filtered # recurse up the memory hierarchy return __filter_by_neigborhood(overheads, sets, sums, clustersz, graph_partition_info, candidates, num_levels_up + 1) def __filter_by_consumption(t, overheads, sets, sums, clustersz, candidates): # Can we minimize t's consumption cost? packed_edges = [e for e in t.node.inEdges if e.p.task.partition != -1] if packed_edges: # pick partition that minimizes t's consumption costs consumption_costs = [0.0 for _ in xrange(0, len(candidates))] for i,c in enumerate(candidates): consumption_costs[i] = overheads.consumer.consume_cost_spilled_estimate(t, c, clustersz) min_cost = min(consumption_costs) candidates = [candidates[i] for i,c in enumerate(consumption_costs) if c == min_cost] if len(candidates) > 1: candidates.sort(key = lambda i: sums[i]) return candidates def __filter_by_production(t, overheads, sets, sums, clustersz, candidates): packed_edges = [e for e in t.node.outEdges if e.s.task.partition != -1] if packed_edges: # pick partitions that maximizes slack to children tasks total_slacks = [0.0 for _ in xrange(0, len(candidates))] valid_candidates = [True for _ in xrange(0, len(candidates))] for i,c in enumerate(candidates): candidate_hi_cpu = (c+1)*clustersz - 1 for e in packed_edges: packed_lo_cpu = e.s.task.partition*clustersz level = overheads.consumer.system.schedcat_distance(candidate_hi_cpu, packed_lo_cpu) consume_cost = overheads.consumer.consume_cost(level, e.wss) # density of slack slack = 1.0 - (e.s.task.cost + consume_cost)/e.s.task.deadline if slack < 0.0: valid_candidates[i] = False # really big negative value total_slacks[i] = -1000000000.0 else: total_slacks[i] += slack if sum(valid_candidates) != 0: max_slack = max(total_slacks) candidates = [candidates[i] for i,s in enumerate(total_slacks) if valid_candidates[i] and s == max_slack] if len(candidates) != 1: # resort by utilization candidates.sort(key = lambda i: sums[i]) return candidates def __filter_by_system(t, overheads, sets, sums, graph_partition_info, clustersz, candidates): # sort, greatest affinity first affinity = [(i,j) for i,j in enumerate(graph_partition_info)] affinity.sort(key = lambda p: p[1], reverse = True) if affinity[0][1] != 0: # some of our graph has been partitioned, pick out affinity partitions affinity_partitions = [p[0] for p in affinity if p[1] != 0] temp = filter(lambda a: a in candidates, affinity_partitions) if temp: # the first has greatest affinity since 'affinity' was # sorted. limit choice to the first. temp = temp[0:1] else: # t cannot fit in any of the partitions with which it has affinity. # Look up the memory hierarchy to get as close as we can. # !!!! Might return None !!!! temp = __filter_by_neigborhood(overheads, sets, sums, clustersz, graph_partition_info, candidates) if not temp: temp = __filter_by_neigborhood_util(overheads, sets, sums, clustersz, candidates) candidates = temp else: # Failed to make a smart affinity-based solution. Fall back to a util # based solution candidates = __filter_by_neigborhood_util(overheads, sets, sums, clustersz, candidates) candidates.sort(key = lambda i: sums[i]) return candidates def __pick_partition(t, sets, sums, graph_sets, model, overheads, worst_fit, capacity_cap = 1.0, fudge = 0.0): """Find the partition that induces the least over-all consumption""" """overheads for task t.""" # find sets that have the most space available clustersz = int(model.ncpus/len(sets)) capacity = clustersz * capacity_cap if worst_fit: # only consider sets with the smallest utilization min_util = min(sums) + fudge candidates = [i for i, s in enumerate(sums) if s <= min_util and s + t.utilization() <= capacity] else: # consider all sets in which we can fit candidates = [i for i, s in enumerate(sums) if s + t.utilization() <= capacity] candidates.sort(key = lambda i: sums[i]) if not candidates: bp.report_failure(t) # only one choice available if len(candidates) == 1: return candidates[0] # !!! candidates is sorted by least to greatest utilization !!! # Can we minimize t's consumption cost? candidates = __filter_by_consumption(t, overheads, sets, sums, clustersz, candidates) if len(candidates) == 1: return candidates[0] # Can we minimize impact on t's packed children? candidates = __filter_by_production(t, overheads, sets, sums, clustersz, candidates) if len(candidates) == 1: return candidates[0] # Can we make a better choice by taking a system-wide view? # (Graph affinity and system architecture) candidates = __filter_by_system(t, overheads, sets, sums, graph_sets[t.graph], clustersz, candidates) return candidates[0] def add_to_partition(t, partition, sets, sums, graph_sets): t.partition = partition sets[partition] += [t] sums[partition] += t.utilization() graph_sets[t.graph][partition] += 1 def __partition_to_minimize_tardiness(ts, gs, clustersz, nr_clusters, model, overheads): """Partitions c*(ceil(U+/c) - 1)-highest-utilizing tasks across the """ """tasks across the partitions to minimize tardiness.""" FUDGE = 0.05 u_plus = math.ceil(ts.utilization()) nr_in_phase_one = int(nr_clusters * (math.ceil(u_plus/nr_clusters) - 1)) nr_to_pack = int(min(nr_in_phase_one,len(ts))) # sort tasks by utilization, then by graph, then by working set size, reversed # ts.sort(key = lambda t: (t.utilization(), t.wss/float(t.deadline), t.graph), reverse = True) wss_cost = overheads.cache_affinity_loss(ts.max_wss()) ts.sort(key = lambda t: ((t.cost + wss_cost + overheads.cache_affinity_loss(t.wss))/float(t.period), t.graph), reverse = True) # pack the c*(ceil(U+/c) - 1) tasks q = ts[0:nr_to_pack] sums = [0.0 for _ in xrange(0, nr_clusters)] sets = [list() for _ in xrange(0, nr_clusters)] graph_sets = {} for g in gs: graph_sets[g] = [0 for _ in xrange(0, nr_clusters)] for t in q: which_set = __pick_partition(t, sets, sums, graph_sets, model, overheads, worst_fit = True, capacity_cap = 1.0 - FUDGE/clustersz, fudge = FUDGE) add_to_partition(t, which_set, sets, sums, graph_sets) return ts[nr_to_pack:len(ts)], sets, sums, graph_sets def pick_partition(t, sets, sums, graph_sets, model, aggressiveness, overheads): # 5% per-task utilization FUDGE = 0.05 clustersz = int(model.ncpus/len(sets)) try: which_set = __pick_partition(t, sets, sums, graph_sets, model, overheads, worst_fit = False, capacity_cap = aggressiveness) except bp.DidNotFit: try: which_set = __pick_partition(t, sets, sums, graph_sets, model, overheads, worst_fit = True, capacity_cap = 1.0 - FUDGE/clustersz, fudge = FUDGE) except bp.DidNotFit: which_set = __pick_partition(t, sets, sums, graph_sets, model, overheads, worst_fit = True) return which_set def partition_cache_aware(ts, gs, subts, clustersz, nr_clusters, model, aggressiveness, overheads): q = copy.copy(ts) # q.sort(key = lambda t: (t.utilization(), t.wss, t.graph), reverse = True) # sums = [0.0 for _ in xrange(0, nr_clusters)] # sets = [list() for _ in xrange(0, nr_clusters)] # graph_sets = {} # for g in gs: # graph_sets[g] = [0 for _ in xrange(0, nr_clusters)] q, sets, sums, graph_sets = __partition_to_minimize_tardiness(q, gs, clustersz, nr_clusters, model, overheads) for t in q: which_set = pick_partition(t, sets, sums, graph_sets, model, aggressiveness, overheads) add_to_partition(t, which_set, sets, sums, graph_sets) return ts def partition_cache_aware_edges(ts, gs, subts, clustersz, nr_clusters, model, aggressiveness, overheads): q = copy.copy(ts) q, sets, sums, graph_sets = __partition_to_minimize_tardiness(q, gs, clustersz, nr_clusters, model, overheads) wss_cost = overheads.cache_affinity_loss(ts.max_wss()) ts.sort(key = lambda t: ((t.cost + wss_cost + overheads.cache_affinity_loss(t.wss))/float(t.period), t.graph), reverse = True) if q: edges = [] for g in gs: edges.extend(g.edges) wss_cost = overheads.cache_affinity_loss(ts.max_wss()) # sort edges by consumption bandwidth edges.sort(key = lambda x : ((x.s.task.cost + wss_cost + overheads.cache_affinity_loss(x.s.task.wss))/float(x.s.task.period), x.wss/float(x.s.task.period)), reverse = True) for e in edges: # # pack the predecessor # p = e.p.task # if p.partition == -1: # which_set = pick_partition(p, sets, sums, graph_sets, model, aggressiveness, overheads) # add_to_partition(p, which_set, sets, sums, graph_sets) # pack the successor s = e.s.task if s.partition == -1: which_set = pick_partition(s, sets, sums, graph_sets, model, aggressiveness, overheads) add_to_partition(s, which_set, sets, sums, graph_sets) # tasks of single-node graphs still need to be assigned orphans = [o for o in q if o.partition == -1] for o in orphans: which_set = pick_partition(o, sets, sums, graph_sets, model, aggressiveness, overheads) add_to_partition(o, which_set, sets, sums, graph_sets) return ts


context:
space:
mode: