pwrkap 7.30-5 / usr / lib / pwrkap / transitions.py

#!/usr/bin/python

"""Remember power domain snapshots and calculate expected transition costs."""
# (C) Copyright IBM Corp. 2008-2009
# Licensed under the GPLv2.
import math
import pwrkap_data

NEW_TRANSITION_WEIGHT = 0.2
class transition_store:
	"""Compute and store power-managed device transitions."""

	def __init__(self, snapshot_store, inter_domains, num_util_buckets):
		"""Create a transition store with a snapshot store."""
		self.snapshot_store = snapshot_store
		self.trans_table = {}
		self.num_util_buckets = num_util_buckets
		self.inter_domains = inter_domains

		for i in range(0, len(inter_domains)):
			util_buckets = []
			for j in range(0, num_util_buckets):
				p_states = {}
				for (p_state, potential) in inter_domains[i][0].get_power_states():
					p_state_dests = {}
					for (p_state_dest, potential_dest) in inter_domains[i][0].get_power_states():
						if p_state >= p_state_dest:
							continue
						p_state_dests[p_state_dest] = (None, potential_dest - potential)
					if len(p_state_dests) != 0:
						p_states[p_state] = p_state_dests
				util_buckets.append(p_states) #[(j + 1.00) / num_util_buckets] = p_states
			self.trans_table["idom" + str(i)] = util_buckets
		self.stat_cache = []

	def consider_snapshot(self, snap):
		"""Add a snapshot and try to determine some transitions."""
		global NEW_TRANSITION_WEIGHT

		self.snapshot_store.append(snap)
		a = self.genericize_snapshot(snap)
		a_hist = self.calc_snapshot_stats(a)

		for (old_hist, old_power) in self.stat_cache:
			# Find an interchangable-domain with just two changes
			key = self.find_idom_with_two_changes(a_hist, old_hist)
			if key == None:
				continue
			delta_power = old_power - a["power"]

			# Store this result in our transition table
			idom = key[0]
			bucket = key[1][1]
			p0 = key[1][0]
			p1 = key[2][0]
			if p0 > p1:
				pt = p0
				p0 = p1
				p1 = pt
				delta_power = -delta_power
			(power, perf) = self.trans_table[idom][bucket][p0][p1]
			if power == None:
				power = delta_power
			self.trans_table[idom][bucket][p0][p1] = \
				(NEW_TRANSITION_WEIGHT * delta_power + \
				 (1 - NEW_TRANSITION_WEIGHT) * power, \
				perf)

		if len(self.stat_cache) > self.snapshot_store.max_size:
			self.stat_cache.pop()
		self.stat_cache.append( (a_hist, a["power"]) )

	def find_idom_with_two_changes(self, a_hist, b_hist):
		"""See if we can find only one idom where one power state \
loses a core and one power state gains a core."""
		res = None

		# Same idoms?
		assert a_hist.keys() == b_hist.keys()

		for idom in a_hist.keys():
			a_idom_hist = a_hist[idom]
			b_idom_hist = b_hist[idom]
			a_set = set(a_idom_hist.keys())
			b_set = set(b_idom_hist.keys())
			ab_set = a_set.union(b_set)

			# No transitions?  Ignore this idom.
			if a_idom_hist == b_idom_hist:
				continue

			# A and B differ.  If we've already found a solution,
			# it's now invalid as A and B have two different idoms.
			if res != None:
				return None

			# Now scan A and B for changes
			a_state = None
			b_state = None
			for key in ab_set:
				if not b_idom_hist.has_key(key):
					b_val = 0
				else:
					b_val = b_idom_hist[key]
				if not a_idom_hist.has_key(key):
					a_val = 0
				else:
					a_val = a_idom_hist[key]

				diff = b_val - a_val # b_idom_hist[key] - a_idom_hist[key]

				# More than 1 device entered/exited this state;
				# this sample cannot be used.
				if diff > 1 or diff < -1:
					return None

				# No change; ignore
				if diff == 0:
					continue

				# This is a -1/+1 transition.
				if diff == 1:
					if b_state != None:
						return None
					b_state = key
				elif diff == -1:
					if a_state != None:
						return None
					a_state = key

				# Ignore transitions that don't involve speed changes
				if a_state != None and b_state != None and a_state[0] == b_state[0]:
					return None

			assert (a_state == None and b_state == None) or (a_state != None and b_state != None)
			if a_state != None and b_state != None:
				res = (idom, a_state, b_state)
		return res

	def calc_snapshot_stats(self, pseudo_snap):
		"""Construct a histogram of the number of idoms in a given \
(pwr_state, util_bucket)."""
		histogram = {}
		domains = pseudo_snap["domains"]
		for (domain, state) in domains:
			if histogram.has_key(domain) == False:
				histogram[domain] = {}
			hist_key = (state["state"], state["util_bucket"])
			if histogram[domain].has_key(hist_key) == False:
				histogram[domain][hist_key] = 1
			else:
				histogram[domain][hist_key] = histogram[domain][hist_key] + 1

		return histogram		

	def find_idomain_for_dev(self, dev_name):
		"""Find an identical-domain for a device."""
		for i in range(0, len(self.inter_domains)):
			domain = self.inter_domains[i]
			for domain_dev in domain:
				if domain_dev.inventory()[0] == dev_name:
					return "idom" + str(i)
		return dev_name

	def find_util_bucket(self, util):
		"""Change utilization to utilization bucket number."""
		return min(self.num_util_buckets - 1, int(util * self.num_util_buckets))

	def genericize_snapshot(self, snap):
		"""Construct a pseudo-snapshot from a real snapshot with device \
name changed to identical-domain ID, domain hierarchy flattened, devices \
within a domain collapsed into one, and utilization changed to utilization \
bucket number."""

		# Copy non-domain properties to new snapshot
		new_snap = {}
		for key in snap.keys():
			if key != "domains":
				new_snap[key] = snap[key]
	
		# Now copy domains but with a few changes.
		# XXX: We'll be in trouble if a domain isn't a strict subset
		#      of an idomain!
		new_domains = []
		for domain in snap["domains"]:
			new_state = {}
			dev0 = domain.keys()[0]
			new_name = self.find_idomain_for_dev(dev0)
			#new_state["old_name"] = dev0
			dev0_state = domain[dev0]
			for key in dev0_state.keys():
				if key != "utilization":
					new_state[key] = dev0_state[key]

			sum = 0.0
			for device in domain.keys():
				assert new_name == self.find_idomain_for_dev(device)
				device_state = domain[device]			
				sum = sum + pwrkap_data.average_utilization(device_state["util_details"])
			new_state["util_bucket"] = self.find_util_bucket(sum / len(domain.keys()))

			new_domains.append((new_name, new_state))
		new_snap["domains"] = new_domains
		return new_snap

	def propose_transitions(self, domain):
		"""Propose power state transitions that can be executed for a domain."""
		def try_to_find_transition(idom_table, bucket, a, b):
			"""Try to find a transition for the current utilization.  If none
found, try adjoining buckets."""
			(x, y) = idom_table[bucket][a][b]
			if not x == None:
				return (x, y)

			print ("Guessing!", bucket, a, b)
			for delta in range(1, max(len(idom_table) - bucket, bucket)):
				if bucket + delta < len(idom_table):
					(x, y) = idom_table[bucket + delta][a][b]
					if not x == None:
						return (x, y)
				if bucket - delta >= 0:
					(x, y) = idom_table[bucket - delta][a][b]
					if not x == None:
						return (x, y)

			return None
		curr_state = domain.get_current_power_state()
		curr_util = pwrkap_data.average_utilization(domain.get_utilization_details())
		possible_states = domain.get_power_states()
		device = domain.get_device()
		idom = self.find_idomain_for_dev(device.inventory()[0])
		bucket = self.find_util_bucket(curr_util)
		props = []

		for (new_state, junk) in possible_states:
			if curr_state == new_state:
				continue
			if curr_state > new_state:
				a = new_state
				b = curr_state
			else:
				a = curr_state
				b = new_state
			# XXX: What if there's no entry for this bucket?
			#(power, perf) = self.trans_table[idom][bucket][a][b]
			x = try_to_find_transition(self.trans_table[idom], bucket, a, b)
			if x == None:
				print ("What do we do with this?", self.trans_table, idom, bucket, a, b)
				continue
			(power, perf) = x
			if curr_state > new_state:
				power = -power
				perf = -perf
			prop = proposed_transition(domain, new_state, power, perf, curr_state, curr_util)
			props.append(prop)

		return props

class snapshot_store:
	"""Store power domain snapshots."""

	def __init__(self, max_size):
		"""Create a snapshot store device."""
		self.max_size = max_size
		self.records = []

	def append(self, snapshot):
		"""Append a snapshot record, deleting old ones if needed."""
		if len(self.records) >= self.max_size:
			self.records.pop()
		self.records.append(snapshot)

class proposed_transition:
	"""A proposal to change the power controls of a device."""
	
	def __init__(self, device, new_state, power_impact, performance_impact, curr_state, curr_util):
		"""Create a proposal."""
		self.device = device
		self.new_state = new_state
		self.performance_impact = performance_impact
		self.power_impact = power_impact
		# XXX: This class does not currently use utilization!
		self.curr_state = curr_state
		self.curr_util = curr_util

	def __repr__(self):
		"""Return string representation of object."""
		return str({"device": self.device.get_device().inventory()[0], "new_state": self.new_state, \
			"perf": self.performance_impact, "power": self.power_impact, \
			"state": self.curr_state, "util": self.curr_util})

def compare_proposals(self, other):
	"""Compare one proposal to another."""
	# This routine can be used to sort a list of proposals by "goodness".
	# Assumptions: (1) no proposal has zero power impact. (2) if the cap
	#              is increasing, all proposals increase performance.
	#              (3) if the cap is decreasing, all proposals cut power.
	# We therefore employ two factors to determine proposal ranking.
	# The first is dP / abs(dW) because we always want the most positive
	# change in performance for _any_ change in power budget.  In the
	# event of a tie, the proposal with the most negative dW wins.
	dPdW_a = self.performance_impact / abs(self.power_impact)
	dPdW_b = other.performance_impact / abs(other.power_impact)

	if dPdW_a > dPdW_b:
		return -1
	elif dPdW_a < dPdW_b:
		return 1

	if self.power_impact < other.power_impact:
		return -1
	elif self.power_impact > other.power_impact:
		return 1

	return 0