/*
 * fpbnp.java
 *
 * Copyright (c) 2004 Rutgers, The State University of New Jersey
 *
 * Daniel A. Jiménez
 *
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use, copy,
 * modify, merge, publish, distribute, sublicense, and/or sell copies
 * of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT.  IN NO EVENT SHALL RUTGERS, THE STATE UNIVERSITY
 * OF NEW JERSEY BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 *
 */

// fast path-based neural branch predictor

public class fpbnp extends branch_predictor {

	int 	n,		// number of weights vectors
		h, 		// history length
		b, 		// number of bits per weight
		theta, 		// training threshold
		max_weight, 	// maximum weight value
		min_weight;	// minimum weight value
	int 	W[][];		// array of weights vectors
	boolean SG[], 		// speculative global history
		G[];		// nonspeculative global history
	int 	SR[],		// speculative "shift vector"
		R[];		// non-speculative shift vector
	int	v[],		// array of recently used indices in W
		spec_v[];	// speculative version of v

	final boolean 
		taken = true;	// taken is represented by Boolean true
	final boolean
		 not_taken = false; // not taken is represented by Boolean false

	// update class for this predictor

	class fpbnp_update extends branch_update {
		int y;		// result of dot product computation
		int i;		// index of weights vector used for bias weight
		int v[];	// contents of spec_v array when predicted
		boolean H[];	// speculative global history when predicted

		fpbnp_update () {
			v = new int[h+1];
			H = new boolean[h+1];
		}
	};

	// constructor.  the parameters are number of weights vectors,
	// history length, and number of bits per weight.

	fpbnp (int _n, int _h, int _b) { 
		int i, j;
		n = _n;
		h = _h;
		b = _b;

		// allocate and initialize G, SG, W, SR, and R
		G = new boolean[h+1];
		SG = new boolean[h+1];
		W = new int[n][h+1];
		SR = new int[h+1];
		R = new int[h+1];
		for (i=0; i<n; i++) for (j=0; j<=h; j++) W[i][j] = 0;
		for (j=0; j<=h; j++) {
			SR[j] = 0;
			R[j] = 0;
			G[j] = false;
			SG[j] = false;
		}

		// allocate v and spec_v

		v = new int[h+1];
		spec_v = new int[h+1];
		for (i=0; i<=h; i++) v[i] = 0;

		// set learning threshold as a function of history length

		theta = (int) (2.14 * (h+1) + 20.58);

		// figure out max and min weights values

		max_weight = (1<<(b-1))-1;
		min_weight = -(max_weight+1);
	}


	// shift an integer into an array; for shift vectors and v, spec_v

	void shift_int (int v[], int x) {
		System.arraycopy (v, 0, v, 1, h);
		v[0] = x;
	}

	// shift a Boolean into an array; for histories

	void shift_bool (boolean v[], boolean x) {
		System.arraycopy (v, 1, v, 2, h-1);
		v[1] = x;
	}

	// saturating increment or decrement

	int satincdec (int w, boolean inc) {
		if (inc) {
			if (w < max_weight) w++;
		} else {
			if (w > min_weight) w--;
		}
		return w;
	}


	// predict the branch at address pc

	branch_update predict (int pc) {

		// allocate a new object in which to return results
		// and keep state for the update

		fpbnp_update u = new fpbnp_update();
		int	i,	// index in array of weights vectors
			j,	// loop counter
			k,	// index in shift vector
			y;	// speculative dot product computation result
		boolean prediction; // taken or not taken

		// hash the pc to produce an index into W

 		i = pc % n;

		// shift this index into the array of previous addresses
		// so we know where to update later

		shift_int (spec_v, i);

		// copy spec_v and SG into the state we need for updating
		// (there's a cleaner way using less state to do this but
		// it's trickier)

		for (j=0; j<=h; j++) {
			u.v[j] = spec_v[j];
			u.H[j] = SG[j];
		}

		// add bias to current speculative running total

		y = W[i][0] + SR[h];

		// figure out the prediction

		prediction = y >= 0;

		// done with prediction.
		// now do speculative computation for next prediction

		for (j=1; j<=h; j++) {
			k = h - j;

			// there are no loop-carried dependences; this loop
			// can proceed in parallel

			if (prediction == taken)
				SR[k+1] = SR[k] + W[i][j];
			else
				SR[k+1] = SR[k] - W[i][j];
		}

		// start the running total for the branch h branches into
		// the future

		SR[0] = 0;

		// update speculative history

		shift_bool (SG, prediction);

		// fill in fields of the update object

		u.y = y;
		u.i = i;
		u.set_prediction (prediction);

		// ready to return result to main simulator

		return u;
	}

	// update a branch using the state returned in bu by the 'predict'
	// method and the true outcome

	void update (branch_update bu, boolean outcome) {
		fpbnp_update u = (fpbnp_update) bu;
		int	i,	// index into W
			j,	// loop counter
			k,	// index into R (and W)
			y;	// non-speculative dot product result

		i = u.i;
		y = u.y;

		// do non-speculative computation for next prediction;
		// these results are only useful for recovering from a 
		// misprediction

		for (j=1; j<=h; j++) {
			k = h - j;

			// can be done in parallel 

			if (outcome == taken)
				R[k+1] = R[k] + W[i][j];
			else
				R[k+1] = R[k] - W[i][j];
		}
		R[0] = 0;

		// update non-speculative history and v

		shift_bool (G, outcome);
		shift_int (v, u.i);

		// recover from misprediction, if any

		if (outcome != u.get_prediction()) for (j=0; j<=h; j++) {

			// copy non-speculative R, G, and G into speculative
			// SR, SG, and spec_v

			SR[j] = R[j];
			SG[j] = G[j];
			spec_v[j] = v[j];
		}

		// perceptron learning rule

		if (outcome != u.get_prediction() || Math.abs(u.y) < theta) {
			W[i][0] = satincdec(W[i][0], outcome);
			for (j=1; j<=h; j++) {
				k = u.v[j];
				W[k][j] = satincdec(W[k][j], outcome == u.H[j]);
			}
		}
	}
};