vpr/SRC/power/power_components.c

/*********************************************************************
 *  The following code is part of the power modelling feature of VTR.
 *
 * For support:
 * http://code.google.com/p/vtr-verilog-to-routing/wiki/Power
 *
 * or email:
 * vtr.power.estimation@gmail.com
 *
 * If you are using power estimation for your researach please cite:
 *
 * Jeffrey Goeders and Steven Wilton.  VersaPower: Power Estimation
 * for Diverse FPGA Architectures.  In International Conference on
 * Field Programmable Technology, 2012.
 *
 ********************************************************************/

/**
 *  This file offers functions to estimate power of major components
 * within the FPGA (flip-flops, LUTs, interconnect structures, etc).
 */

/************************* INCLUDES *********************************/
#include <cstring>
using namespace std;

#include <assert.h>

#include "power_components.h"
#include "power_lowlevel.h"
#include "power_util.h"
#include "power_callibrate.h"
#include "globals.h"

/************************* STRUCTS **********************************/

/************************* GLOBALS **********************************/
t_power_components g_power_by_component;

/************************* FUNCTION DECLARATIONS ********************/
static void power_usage_mux_rec(t_power_usage * power_usage, float * out_prob,
		float * out_dens, float * v_out, t_mux_node * mux_node,
		t_mux_arch * mux_arch, int * selector_values,
		float * primary_input_prob, float * primary_input_dens,
		boolean v_out_restored, float period);

/************************* FUNCTION DEFINITIONS *********************/

/**
 * Module initializer function, called by power_init
 */
void power_components_init(void) {
	int i;

	g_power_by_component.components = (t_power_usage*) my_calloc(
			POWER_COMPONENT_MAX_NUM, sizeof(t_power_usage));
	for (i = 0; i < POWER_COMPONENT_MAX_NUM; i++) {
		power_zero_usage(&g_power_by_component.components[i]);
	}
}

/**
 * Module un-initializer function, called by power_uninit
 */
void power_components_uninit(void) {
	free(g_power_by_component.components);
}

/**
 * Adds power usage for a component to the global component tracker
 * - power_usage: Power usage to add
 * - component_idx: Type of component
 */
void power_component_add_usage(t_power_usage * power_usage,
		e_power_component_type component_idx) {
	power_add_usage(&g_power_by_component.components[component_idx],
			power_usage);
}

/**
 * Gets power usage for a component
 * - power_usage: (Return value) Power usage for the given component
 * - component_idx: Type of component
 */
void power_component_get_usage(t_power_usage * power_usage,
		e_power_component_type component_idx) {
	memcpy(power_usage, &g_power_by_component.components[component_idx],
			sizeof(t_power_usage));
}

/**
 * Returns total power for a given component
 * - component_idx: Type of component
 */
float power_component_get_usage_sum(e_power_component_type component_idx) {
	return power_sum_usage(&g_power_by_component.components[component_idx]);
}

/**
 * Calculates power of a D flip-flop
 * - power_usage: (Return value) power usage of the flip-flop
 * - D_prob: Signal probability of the input
 * - D_dens: Transition density of the input
 * - Q_prob: Signal probability of the output
 * - Q_dens: Transition density of the output
 * - clk_prob: Signal probability of the clock
 * - clk_dens: Transition density of the clock
 */
void power_usage_ff(t_power_usage * power_usage, float size, float D_prob,
		float D_dens, float Q_prob, float Q_dens, float clk_prob,
		float clk_dens, float period) {
	t_power_usage sub_power_usage;
	float mux_in_dens[2];
	float mux_in_prob[2];
	PowerSpicedComponent * callibration;
	float scale_factor;

	power_zero_usage(power_usage);

	/* DFF is build using a master loop and slave loop.
	 * Each loop begins with a MUX and contains 2 inverters
	 * in a feedback loop to the mux.
	 * Each mux is built using two transmission gates.
	 */

	/* Master */
	mux_in_dens[0] = D_dens;
	mux_in_dens[1] = (1 - clk_prob) * D_dens;
	mux_in_prob[0] = D_prob;
	mux_in_prob[1] = D_prob;
	power_usage_MUX2_transmission(&sub_power_usage, size, mux_in_dens,
			mux_in_prob, clk_dens, (1 - clk_prob) * D_dens, period);
	power_add_usage(power_usage, &sub_power_usage);

	power_usage_inverter(&sub_power_usage, (1 - clk_prob) * D_dens, D_prob,
			size, period);
	power_add_usage(power_usage, &sub_power_usage);

	power_usage_inverter(&sub_power_usage, (1 - clk_prob) * D_dens, 1 - D_prob,
			size, period);
	power_add_usage(power_usage, &sub_power_usage);

	/* Slave */
	mux_in_dens[0] = Q_dens;
	mux_in_dens[1] = (1 - clk_prob) * D_dens;
	mux_in_prob[0] = (1 - Q_prob);
	mux_in_prob[1] = (1 - D_prob);
	power_usage_MUX2_transmission(&sub_power_usage, size, mux_in_dens,
			mux_in_prob, clk_dens, Q_dens, period);
	power_add_usage(power_usage, &sub_power_usage);

	power_usage_inverter(&sub_power_usage, Q_dens, 1 - Q_prob, size, period);
	power_add_usage(power_usage, &sub_power_usage);

	power_usage_inverter(&sub_power_usage, Q_dens, Q_prob, size, period);
	power_add_usage(power_usage, &sub_power_usage);

	/* Callibration */
	callibration =
			g_power_commonly_used->component_callibration[POWER_CALLIB_COMPONENT_FF];
	if (callibration->is_done_callibration()) {
		scale_factor = callibration->scale_factor(1, size);
		power_scale_usage(power_usage, scale_factor);
	}

	return;
}

/**
 * Calculated power of a look-up table (LUT)
 * - power_usage: (Return value) The power usage of the LUT
 * - LUT_size: Number of LUT inputs
 * - SRAM_values: The 2^(LUT_size) truth table values.  String of '0' and '1' characters.
 * 		First characters is for all inputs = 0 and last characters is for all inputs = 1.
 * - input_prob: Array of input signal probabilities
 * - input_dens: Array of input transition densities
 *
 * NOTE: The following provides a diagram of a 3-LUT, the sram bit ordering, and
 *  the input array ordering.
 *
 *	X - NMOS gate controlled by complement of input
 *	Z - NMOS gate controlled by input
 *
 * S
 * R  I   I   I
 * A  N   N   N
 * M  2   1   0
 * |  |   |   |
 * v  v   |   |
 *        v   |
 * 0 _X_      |
 *      |_X_  v
 * 1 _Z_|   |
 *          |_X_
 * 2 _X_    |   |
 *      |_Z_|   |
 * 3 _Z_|       |
 *              |------ out
 * 4 _X_        |
 *      |_X_    |
 * 5 _Z_|   |   |
 *          |_Z_|
 * 6 _X_    |
 *      |_Z_|
 * 7 _Z_|
 *
 */
void power_usage_lut(t_power_usage * power_usage, int lut_size,
		float transistor_size, char * SRAM_values, float * input_prob,
		float * input_dens, float period) {
	float **internal_prob;
	float **internal_dens;
	float **internal_v;
	int i;
	int level_idx;
	PowerSpicedComponent * callibration;
	float scale_factor;

	int num_SRAM_bits;

	boolean level_restorer_this_level = FALSE;

	power_zero_usage(power_usage);

	num_SRAM_bits = 1 << lut_size;

	/* Initialize internal node data */
	internal_prob = (float**) my_calloc(lut_size + 1, sizeof(float*));
	internal_dens = (float**) my_calloc(lut_size + 1, sizeof(float*));
	internal_v = (float**) my_calloc(lut_size + 1, sizeof(float*));
	for (i = 0; i <= lut_size; i++) {
		internal_prob[i] = (float*) my_calloc(1 << (lut_size - i),
				sizeof(float));
		internal_dens[i] = (float*) my_calloc(1 << (lut_size - i),
				sizeof(float));
		internal_v[i] = (float*) my_calloc(1 << (lut_size - i), sizeof(float));
	}

	/* Initialize internal probabilities/densities from SRAM bits */
	for (i = 0; i < num_SRAM_bits; i++) {
		if (SRAM_values[i] == '0') {
			internal_prob[0][i] = 0.;
		} else {
			internal_prob[0][i] = 1.;
		}
		internal_dens[0][i] = 0.;
		internal_v[0][i] = g_power_tech->Vdd;
	}

	for (level_idx = 0; level_idx < lut_size; level_idx++) {
		t_power_usage driver_power_usage;
		int MUXs_this_level;
		int MUX_idx;
		int reverse_idx = lut_size - level_idx - 1;

		MUXs_this_level = 1 << (reverse_idx);

		/* Power of input drivers */
		power_usage_inverter(&driver_power_usage, input_dens[reverse_idx],
				input_prob[reverse_idx], 1.0, period);
		power_add_usage(power_usage, &driver_power_usage);

		power_usage_inverter(&driver_power_usage, input_dens[reverse_idx],
				input_prob[reverse_idx], 2.0, period);
		power_add_usage(power_usage, &driver_power_usage);

		power_usage_inverter(&driver_power_usage, input_dens[reverse_idx],
				1 - input_prob[reverse_idx], 2.0, period);
		power_add_usage(power_usage, &driver_power_usage);

		/* Add level restorer after every 2 stages (level_idx %2 == 1)
		 * But if there is an odd # of stages, just put one at the last
		 * stage (level_idx == LUT_size - 1) and not at the stage just before
		 * the last stage (level_idx != LUT_size - 2)
		 */
		if (((level_idx % 2 == 1) && (level_idx != lut_size - 2))
				|| (level_idx == lut_size - 1)) {
			level_restorer_this_level = TRUE;
		} else {
			level_restorer_this_level = FALSE;
		}

		/* Loop through the 2-muxs at each level */
		for (MUX_idx = 0; MUX_idx < MUXs_this_level; MUX_idx++) {
			t_power_usage sub_power;
			float out_prob;
			float out_dens;
			float sum_prob = 0;
			int sram_offset = MUX_idx * ipow(2, level_idx + 1);
			int sram_per_branch = ipow(2, level_idx);
			int branch_lvl_idx;
			int sram_idx;
			float v_out;

			/* Calculate output probability of multiplexer */
			out_prob = internal_prob[level_idx][MUX_idx * 2]
					* (1 - input_prob[reverse_idx])
					+ internal_prob[level_idx][MUX_idx * 2 + 1]
							* input_prob[reverse_idx];

			/* Calculate output density of multiplexer */
			out_dens = internal_dens[level_idx][MUX_idx * 2]
					* (1 - input_prob[reverse_idx])
					+ internal_dens[level_idx][MUX_idx * 2 + 1]
							* input_prob[reverse_idx];

#ifdef POWER_LUT_FAST
			out_dens += ((1 - internal_prob[level_idx][MUX_idx * 2]) * internal_prob[level_idx][MUX_idx * 2 + 1]
					+ internal_prob[level_idx][MUX_idx * 2] * (1 - internal_prob[level_idx][MUX_idx * 2 + 1]))
			* input_dens[reverse_idx];
#elif defined(POWER_LUT_SLOW)
			for (sram_idx = sram_offset;
					sram_idx < sram_offset + sram_per_branch; sram_idx++) {
				float branch_prob = 1.;
				if (SRAM_values[sram_idx]
						== SRAM_values[sram_idx + sram_per_branch]) {
					continue;
				}
				for (branch_lvl_idx = 0; branch_lvl_idx < level_idx;
						branch_lvl_idx++) {
					int branch_lvl_reverse_idx = lut_size - branch_lvl_idx - 1;
					int even_odd = sram_idx / ipow(2, branch_lvl_idx);
					if (even_odd % 2 == 0) {
						branch_prob *= (1 - input_prob[branch_lvl_reverse_idx]);
					} else {
						branch_prob *= input_prob[branch_lvl_reverse_idx];
					}
				}
				sum_prob += branch_prob;
			}
			out_dens += sum_prob * input_dens[reverse_idx];
#endif

			/* Calculate output voltage of multiplexer */
			if (level_restorer_this_level) {
				v_out = g_power_tech->Vdd;
			} else {
				v_out = (1 - input_prob[reverse_idx])
						* power_calc_mux_v_out(2, 1.0,
								internal_v[level_idx][MUX_idx * 2],
								internal_prob[level_idx][MUX_idx * 2 + 1])
						+ input_prob[reverse_idx]
								* power_calc_mux_v_out(2, 1.0,
										internal_v[level_idx][MUX_idx * 2 + 1],
										internal_prob[level_idx][MUX_idx * 2]);
			}

			/* Save internal node info */
			internal_dens[level_idx + 1][MUX_idx] = out_dens;
			internal_prob[level_idx + 1][MUX_idx] = out_prob;
			internal_v[level_idx + 1][MUX_idx] = v_out;

			/* Calculate power of the 2-mux */
			power_usage_mux_singlelevel_dynamic(&sub_power, 2,
					internal_dens[level_idx + 1][MUX_idx],
					internal_v[level_idx + 1][MUX_idx],
					&internal_prob[level_idx][MUX_idx * 2],
					&internal_dens[level_idx][MUX_idx * 2],
					&internal_v[level_idx][MUX_idx * 2],
					input_dens[reverse_idx], input_prob[reverse_idx],
					transistor_size, period);
			power_add_usage(power_usage, &sub_power);

			/* Add the level-restoring buffer if necessary */
			if (level_restorer_this_level) {
				/* Level restorer */
				power_usage_buffer(&sub_power, 1,
						internal_prob[level_idx + 1][MUX_idx],
						internal_dens[level_idx + 1][MUX_idx], TRUE, period);
				power_add_usage(power_usage, &sub_power);
			}
		}

	}

	/* Free allocated memory */
	for (i = 0; i <= lut_size; i++) {
		free(internal_prob[i]);
		free(internal_dens[i]);
		free(internal_v[i]);
	}
	free(internal_prob);
	free(internal_dens);
	free(internal_v);

	/* Callibration */
	callibration =
			g_power_commonly_used->component_callibration[POWER_CALLIB_COMPONENT_LUT];
	if (callibration->is_done_callibration()) {
		scale_factor = callibration->scale_factor(lut_size, transistor_size);
		power_scale_usage(power_usage, scale_factor);
	}

	return;
}

/**
 * This function calculates power of a local interconnect structure
 * - power_usage: (Return value) Power usage of the structure
 * - pb: The physical block to which this interconnect belongs
 * - interc_pins: The interconnect input/ouput pin information
 * - interc_length: The physical length spanned by the interconnect (meters)
 */
void power_usage_local_interc_mux(t_power_usage * power_usage, t_pb * pb,
		t_interconnect_pins * interc_pins) {
	int pin_idx;
	int out_port_idx;
	int in_port_idx;
	float * in_dens;
	float * in_prob;
	t_power_usage MUX_power;
	t_interconnect * interc = interc_pins->interconnect;
	t_interconnect_power * interc_power = interc->interconnect_power;

	power_zero_usage(power_usage);

	/* Ensure port/pins are structured as expected */
	switch (interc_pins->interconnect->type) {
	case DIRECT_INTERC:
		assert(interc_power->num_input_ports == 1);
		assert(interc_power->num_output_ports == 1);
		break;
	case MUX_INTERC:
		assert(interc_power->num_output_ports == 1);
		break;
	case COMPLETE_INTERC:
		break;
	}

	/* Power of transistors to build interconnect structure */
	switch (interc_pins->interconnect->type) {
	case DIRECT_INTERC:
		/* Direct connections require no transistors */
		break;
	case MUX_INTERC:
	case COMPLETE_INTERC:
		/* Many-to-1, or Many-to-Many
		 * Implemented as a multiplexer for each output
		 * */
		in_dens = (float*) my_calloc(
				interc->interconnect_power->num_input_ports, sizeof(float));
		in_prob = (float*) my_calloc(
				interc->interconnect_power->num_input_ports, sizeof(float));

		for (out_port_idx = 0;
				out_port_idx < interc->interconnect_power->num_output_ports;
				out_port_idx++) {
			for (pin_idx = 0;
					pin_idx < interc->interconnect_power->num_pins_per_port;
					pin_idx++) {

				int selected_input = OPEN;

				/* Clear input densities */
				for (in_port_idx = 0;
						in_port_idx
								< interc->interconnect_power->num_input_ports;
						in_port_idx++) {
					in_dens[in_port_idx] = 0.;
					in_prob[in_port_idx] = 0.;
				}

				/* Get probability/density of input signals */
				if (pb) {
					int output_pin_net =
							pb->rr_graph[interc_pins->output_pins[out_port_idx][pin_idx]->pin_count_in_cluster].net_num;

					if (output_pin_net == OPEN) {
						selected_input = 0;
					} else {
						for (in_port_idx = 0;
								in_port_idx
										< interc->interconnect_power->num_input_ports;
								in_port_idx++) {
							t_pb_graph_pin * input_pin =
									interc_pins->input_pins[in_port_idx][pin_idx];
							int input_pin_net =
									pb->rr_graph[input_pin->pin_count_in_cluster].net_num;

							/* Find input pin that connects through the mux to the output pin */
							if (output_pin_net == input_pin_net) {
								selected_input = in_port_idx;
							}

							/* Initialize input densities */
							if (input_pin_net != OPEN) {
								in_dens[in_port_idx] = pin_dens(pb, input_pin);
								in_prob[in_port_idx] = pin_prob(pb, input_pin);
							}
						}

						/* Check that the input pin was found with a matching net to the output pin */
						assert(selected_input != OPEN);
					}
				} else {
					selected_input = 0;
				}

				/* Calculate power of the multiplexer */
				power_usage_mux_multilevel(&MUX_power,
						power_get_mux_arch(
								interc_pins->interconnect->interconnect_power->num_input_ports,
								g_power_arch->mux_transistor_size), in_prob,
						in_dens, selected_input, TRUE, g_solution_inf.T_crit);

				power_add_usage(power_usage, &MUX_power);
			}
		}

		free(in_dens);
		free(in_prob);
		break;
	default:
		assert(0);
	}

	power_add_usage(&interc_pins->interconnect->interconnect_power->power_usage,
			power_usage);
}

/**
 *  This calculates the power of a multilevel multiplexer, with static inputs
 *  - power_usage: (Return value) The power usage of the multiplexer
 *  - mux_arch: The information on the multiplexer architecture
 *  - in_prob: Array of input signal probabilities
 *  - in_dens: Array of input transition densitites
 *  - selected_input: The index of the input that has been statically selected
 *  - output_level_restored: Whether the output is level restored to Vdd.
 */
void power_usage_mux_multilevel(t_power_usage * power_usage,
		t_mux_arch * mux_arch, float * in_prob, float * in_dens,
		int selected_input, boolean output_level_restored, float period) {
	float output_density;
	float output_prob;
	float V_out;
	boolean found;
	PowerSpicedComponent * callibration;
	float scale_factor;
	int * selector_values = (int*) my_calloc(mux_arch->levels, sizeof(int));

	assert(selected_input != OPEN);

	power_zero_usage(power_usage);

	/* Find selection index at each level */
	found = mux_find_selector_values(selector_values, mux_arch->mux_graph_head,
			selected_input);

	assert(found);

	/* Calculate power of the multiplexor stages, from final stage, to first stages */
	power_usage_mux_rec(power_usage, &output_density, &output_prob, &V_out,
			mux_arch->mux_graph_head, mux_arch, selector_values, in_prob,
			in_dens, output_level_restored, period);

	free(selector_values);

	callibration =
			g_power_commonly_used->component_callibration[POWER_CALLIB_COMPONENT_MUX];
	if (callibration->is_done_callibration()) {
		scale_factor = callibration->scale_factor(mux_arch->num_inputs,
				mux_arch->transistor_size);
		power_scale_usage(power_usage, scale_factor);
	}

}

/**
 * Internal function, used recursively by power_calc_mux
 */
static void power_usage_mux_rec(t_power_usage * power_usage, float * out_prob,
		float * out_dens, float * v_out, t_mux_node * mux_node,
		t_mux_arch * mux_arch, int * selector_values,
		float * primary_input_prob, float * primary_input_dens,
		boolean v_out_restored, float period) {
	int input_idx;
	float * in_prob;
	float * in_dens;
	float * v_in;
	t_power_usage sub_power_usage;

	/* Single input mux is really just a wire, and has no power.
	 * Ensure that it has no children before returning. */
	if (mux_node->num_inputs == 1) {
		assert(mux_node->level == 0);
		return;
	}

	v_in = (float*) my_calloc(mux_node->num_inputs, sizeof(float));
	if (mux_node->level == 0) {
		/* First level of mux - inputs are primar inputs */
		in_prob = &primary_input_prob[mux_node->starting_pin_idx];
		in_dens = &primary_input_dens[mux_node->starting_pin_idx];

		for (input_idx = 0; input_idx < mux_node->num_inputs; input_idx++) {
			v_in[input_idx] = g_power_tech->Vdd;
		}
	} else {
		/* Higher level of mux - inputs recursive from lower levels */
		in_prob = (float*) my_calloc(mux_node->num_inputs, sizeof(float));
		in_dens = (float*) my_calloc(mux_node->num_inputs, sizeof(float));

		for (input_idx = 0; input_idx < mux_node->num_inputs; input_idx++) {
			/* Call recursively for multiplexer driving the input */
			power_usage_mux_rec(power_usage, &in_prob[input_idx],
					&in_dens[input_idx], &v_in[input_idx],
					&mux_node->children[input_idx], mux_arch, selector_values,
					primary_input_prob, primary_input_dens, FALSE, period);
		}
	}

	power_usage_mux_singlelevel_static(&sub_power_usage, out_prob, out_dens,
			v_out, mux_node->num_inputs, selector_values[mux_node->level],
			in_prob, in_dens, v_in, mux_arch->transistor_size, v_out_restored,
			period);
	power_add_usage(power_usage, &sub_power_usage);

	if (mux_node->level != 0) {
		free(in_prob);
		free(in_dens);
	}
}

/**
 * This function calculates the power of a multistage buffer
 * - power_usage: (Return value) Power usage of buffer
 * - size: The size of the final buffer stage, relative to min-sized inverter
 * - in_prob: The signal probability of the input
 * - in_dens: The transition density of the input
 * - level_restored: Whether this buffer must level restore the input
 * - input_mux_size: If fed by a mux, the size of this mutliplexer
 */
void power_usage_buffer(t_power_usage * power_usage, float size, float in_prob,
		float in_dens, boolean level_restorer, float period) {
	t_power_usage sub_power_usage;
	int i, num_stages;
	float stage_effort;
	float stage_inv_size;
	float stage_in_prob;
	float input_dyn_power;
	float scale_factor;
	PowerSpicedComponent * callibration;

	power_zero_usage(power_usage);

	if (size == 0.) {
		return;
	}

	num_stages = power_calc_buffer_num_stages(size,
			g_power_arch->logical_effort_factor);
	stage_effort = calc_buffer_stage_effort(num_stages, size);

	stage_in_prob = in_prob;
	for (i = 0; i < num_stages; i++) {
		stage_inv_size = pow(stage_effort, i);

		if (i == 0) {
			if (level_restorer) {
				/* Sense Buffer */
				power_usage_level_restorer(&sub_power_usage, &input_dyn_power,
						in_dens, stage_in_prob, period);
			} else {
				power_usage_inverter(&sub_power_usage, in_dens, stage_in_prob,
						stage_inv_size, period);
			}
		} else {
			power_usage_inverter(&sub_power_usage, in_dens, stage_in_prob,
					stage_inv_size, period);
		}
		power_add_usage(power_usage, &sub_power_usage);

		stage_in_prob = 1 - stage_in_prob;
	}

	/* Callibration */
	if (level_restorer) {
		callibration =
				g_power_commonly_used->component_callibration[POWER_CALLIB_COMPONENT_BUFFER_WITH_LEVR];
	} else {
		callibration =
				g_power_commonly_used->component_callibration[POWER_CALLIB_COMPONENT_BUFFER];
	}

	if (callibration->is_done_callibration()) {
		scale_factor = callibration->scale_factor(1, size);
		power_scale_usage(power_usage, scale_factor);
	}

	/* Short-circuit: add a factor to dynamic power, but the factor is not in addition to the input power
	 * Need to subtract input before adding factor - this matters for small buffers
	 */
	/*power_usage->dynamic += (power_usage->dynamic - input_dyn_power)
	 * power_calc_buffer_sc(num_stages, stage_effort, level_restorer,
	 input_mux_size); */
}