You need to explore the effectiveness of branch direction prediction (taken vs not taken) using an actual program. Your task is to use the given branch prediction simulation infrastructure to evaluate the effectiveness of some simple branch prediction schemes. The simulation infrastructure can be downloaded from the class website ( cbp2-infrastructure-v2. tar).
To do this, you will implement a C++ branch prediction class (see README contained in the zip file) that reads in the trace and simulates a local history based branch predictor. A local history based predictor is a dynamic branch predictor that uses the local history of a branch to predict its future outcome. The predictor uses a history table (local history table) to record the taken/not-taken history of a branch. The local history table holds 10 bits of branch history for up to 4096 branches, indexed by the instruction address. The predictor uses the 10-bit local history to select from one of the 1024 2-bit prediction counters. Each two-bit includes one of four values: strongly taken (T), weakly taken (t), weakly not taken (n), and strongly not taken (N).
To make a prediction, the predictor selects a counter from the local prediction table using the 10 local history bits as index. The 10 local history bits are retrieved from a local history table using 12 bits of the instruction's address (its program counter value) as index. The direction prediction is made based on the value of the counter.
To finish the homework, open my_predictor.h and implement the three member functions of local_predictor class.
class local_predictor : public branch_predictor { public:
local_update u;
local_predictor (void) {
}
branch_update *predict (branch_info & b) { u.direction_prediction (true); u.target_prediction (0);
return &u;
}
void update (branch_update *u, bool taken, unsigned int target)
{
}
To compile the predictor, type make under /cbp2-infrastructure-v2/src. You will see two binary programs generated, predict and predict_extra_credit. Binary program predict does branch prediction using an instance of local_predictor class. Binary program predict_extra_credit does branch prediction using an instance of extra_predictor class (defined in my_predictor.h). To test your local predictor, type run traces under ./cbp2- infrastructure-v2/.
2.) Branch Predictor Competition
Assuming a total hardware budget of 4KB (32768 bits), implement a branch predictor to maximize predication performance (use my_predictor.h and extra_predictor class). You must justify why your predictor actually fits within the 4KB budget. For example, a table of 4096 2-bit counters would eat up the entire 8192-bit (1KB) budget. Assume "logic" (adders, etc.) is free. Note that using something like a float would actually cost you 32 bits per float (or 64 bits for a double), and so it's likely that you'll want to stick with narrow-width integer counters.