ECE521 Project One

Cache Design

1. C++ Cade

// proj98_2.cxx
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct branch_st {
    unsigned int history;
    unsigned int tag;
    unsigned int target;
} Branch;

#define EMPTY 0xffffffff

Branch *branch;
unsigned int *predictor;
int m,n,h;
int branch_size, predictor_size;
int taken_limit;

//Data of Statistics

int accesses = 0;
int interferences = 0;
int mis_branch = 0;
int mis_target = 0;
float asc,cpi;
FILE *ifp;

int branch_access(unsigned int, char, unsigned int);

main(int argc, char *argv[])
{
    int i, j;
    char taken;
    unsigned int branch_addr, target_addr;

// Decode command line arguments

    if (argc != 5) {
        cout<< "usage:" << argv[0] << " trace_file_name m h n\n" ;
        exit(-1);
    }

    m = atoi(argv[2]);
    h = atoi(argv[3]);
    n = atoi(argv[4]);

ifp=fopen(argv[1],"r");

    if ((m>32)||(m<1)||(n<1)||(h<1)||(n>6) ) {
        cout<<"invalid parameters of m h n\n";
        cout<<"The range of m h n should be:\n";
        cout<<"1 < m < 33\t 1 < n < 7\t 1 < h\n";
        exit(-3);
    }

// Make arrays

    branch_size = 1<<m;
    predictor_size = 1<<h;
    taken_limit = 1 << (n-1);

branch = new Branch[branch_size];
predictor = new (unsigned int)[predictor_size];

    for (i = 0; i < branch_size; i++) {
        branch[i].history = 0;
        branch[i].tag = EMPTY;
        branch[i].target = EMPTY;
    }

    for (i = 0; i < predictor_size; i++) {
        predictor[i] = taken_limit - 1;
    }

//Begin reading the file and predicting branch directions

    while ((fscanf(ifp,"%x %c %x",&branch_addr, &taken, &target_addr))==3) {
      fflush(ifp);
      accesses++;
       //       cout<<accesses<<'\t'<<target_addr<<endl;
       branch_access(branch_addr,taken,target_addr);
    }
    fclose(ifp);

// Print out the final Statistic results

    cout<<endl;
    cout.flags(ios::dec);
    cout << "m n h\t";
    cout << "accesses    interf. mis_branch mis_target     asc       cpi\n";
    cout << m<<" "<<n<<" "<<h<<'\t';
    cout.width(8);
    cout << accesses<<" ";
    cout.width(8);
    cout << interferences<<" ";
    cout.width(8);
    cout << mis_branch<<" ";
    cout.width(8);
    cout << mis_target<<"       ";

asc = 2.0 * (mis_branch + mis_target)/(5.0 * accesses);
cpi = asc +1;

    cout.width(8);
    cout << asc<<'\t';
    cout.width(8);
    cout << cpi << '\n';
}

int branch_access(unsigned int addr1, char taken, unsigned int addr2)
{
int branch_index,predictor_index;
int branch_tag;
char pred;

// Get index and tag of the branch
branch_index = (addr1>>2) & ((1<<m)-1);
branch_tag = addr1>>(m+2);

/* cout.flags(ios::hex);
cout << "index= " << branch_index << '\t' << "tag= " << branch_tag;
cout << "\ttarget= "<<addr2 <<"\ttaken="<<taken<<endl;*/

// Check interference
if (branch[branch_index].tag != branch_tag) {
     if (branch[branch_index].tag != EMPTY)
         interferences++;
      branch[branch_index].tag = branch_tag;
     }

// Check mispredictions of branch target addresses
if ((branch[branch_index].target != addr2) && (taken == 't')) {
     mis_target++;
     branch[branch_index].target = addr2;
     }

// Predict the branch dirction
predictor_index = branch[branch_index].history & ((1<<h)-1);
if (predictor[predictor_index] < taken_limit)
pred = 'n';
else
pred = 't';

// Check mispredictions of branch direction
if (taken != pred)
mis_branch++;

// Modify predictor
if ((taken == 't') && (predictor[predictor_index] != ((1<<n)-1)))
predictor[predictor_index]++;

if ((taken == 'n') && (predictor[predictor_index] != 0))
predictor[predictor_index]--;

// Modify branch history
if (taken == 't')
branch[branch_index].history = ( branch[branch_index].history << 1 ) | 0x1;
if (taken == 'n')
branch[branch_index].history = branch[branch_index].history << 1 ;

/*    cout.flags(ios::dec);
    cout << "accesses\tinterference\tmis_branch\tmis_target\n";
    cout.width(8);
    cout << accesses<<'\t';
    cout.width(8);
    cout << interferences<<'\t';
    cout.width(8);
    cout << mis_branch<<'\t';
    cout.width(8);
    cout << mis_target<<'\n';
                               */

return 1;

}

2. Outputs

m n h accesses interf. mis_branch mis_target asc cpi
10 2 5 97864 1824 2629 4948 0.0309695 1.03097

m n h accesses interf. mis_branch mis_target asc cpi
11 2 5 97864 1047 2532 4758 0.0297965 1.0298

m n h accesses interf. mis_branch mis_target asc cpi
12 2 5 97864 696 2523 4722 0.0296125 1.02961

m n h accesses interf. mis_branch mis_target asc cpi
13 2 5 97864 519 2518 4657 0.0293264 1.02933

m n h accesses interf. mis_branch mis_target asc cpi
14 2 5 97864 405 2492 4657 0.0292201 1.02922

m n h accesses interf. mis_branch mis_target asc cpi
15 2 5 97864 268 2545 4596 0.0291874 1.02919

m n h accesses interf. mis_branch mis_target asc cpi
16 2 5 97864 267 2547 4596 0.0291956 1.0292

m n h accesses interf. mis_branch mis_target asc cpi
17 2 5 97864 5 2395 4533 0.0283168 1.02832

m n h accesses interf. mis_branch mis_target asc cpi
18 2 5 97864 0 2389 4533 0.0282923 1.02829

m n h accesses interf. mis_branch mis_target asc cpi
19 2 5 97864 0 2389 4533 0.0282923 1.02829

m n h accesses interf. mis_branch mis_target asc cpi
9 2 5 97864 3844 2927 5146 0.0329968 1.033

m n h accesses interf. mis_branch mis_target asc cpi
8 2 5 97864 8509 3599 6534 0.0414167 1.04142

m n h accesses interf. mis_branch mis_target asc cpi
7 2 5 97864 17684 5124 8848 0.0571078 1.05711

m n h accesses interf. mis_branch mis_target asc cpi
6 2 5 97864 29541 8343 11230 0.0800008 1.08

m n h accesses interf. mis_branch mis_target asc cpi
5 2 5 97864 50186 15171 14781 0.122423 1.12242

m n h accesses interf. mis_branch mis_target asc cpi
4 2 5 97864 71327 22569 23997 0.190329 1.19033

m n h accesses interf. mis_branch mis_target asc cpi
3 2 5 97864 81304 26423 31556 0.236978 1.23698

m n h accesses interf. mis_branch mis_target asc cpi
2 2 5 97864 82459 27998 33462 0.251206 1.25121

m n h accesses interf. mis_branch mis_target asc cpi
1 2 5 97864 84739 23038 34781 0.236324 1.23632

m n h accesses interf. mis_branch mis_target asc cpi
1 2 5 100001 95134 23488 25130 0.19447 1.19447

m n h accesses interf. mis_branch mis_target asc cpi
2 2 5 100001 90068 22573 20314 0.171546 1.17155

m n h accesses interf. mis_branch mis_target asc cpi
3 2 5 100001 46227 19110 12793 0.127611 1.12761

m n h accesses interf. mis_branch mis_target asc cpi
4 2 5 100001 28805 14713 9291 0.096015 1.09602

m n h accesses interf. mis_branch mis_target asc cpi
5 2 5 100001 13357 12619 4938 0.0702273 1.07023

m n h accesses interf. mis_branch mis_target asc cpi
6 2 5 100001 4171 10168 2075 0.0489715 1.04897

m n h accesses interf. mis_branch mis_target asc cpi
7 2 5 100001 1482 8497 248 0.0349796 1.03498

m n h accesses interf. mis_branch mis_target asc cpi
8 2 5 100001 91 7906 95 0.0320037 1.032

m n h accesses interf. mis_branch mis_target asc cpi
9 2 5 100001 0 7844 63 0.0316277 1.03163

m n h accesses interf. mis_branch mis_target asc cpi
10 2 5 100001 0 7844 63 0.0316277 1.03163

m n h accesses interf. mis_branch mis_target asc cpi
11 2 5 100001 0 7844 63 0.0316277 1.03163

m n h accesses interf. mis_branch mis_target asc cpi
12 2 5 100001 0 7844 63 0.0316277 1.03163

m n h accesses interf. mis_branch mis_target asc cpi
13 2 5 100001 0 7844 63 0.0316277 1.03163

m n h accesses interf. mis_branch mis_target asc cpi
14 2 5 100001 0 7844 63 0.0316277 1.03163

m n h accesses interf. mis_branch mis_target asc cpi
15 2 5 100001 0 7844 63 0.0316277 1.03163

m n h accesses interf. mis_branch mis_target asc cpi
16 2 5 100001 0 7844 63 0.0316277 1.03163

m n h accesses interf. mis_branch mis_target asc cpi
17 2 5 100001 0 7844 63 0.0316277 1.03163

m n h accesses interf. mis_branch mis_target asc cpi
18 2 5 100001 0 7844 63 0.0316277 1.03163

m n h accesses interf. mis_branch mis_target asc cpi
19 2 5 100001 0 7844 63 0.0316277 1.03163

m n h accesses interf. mis_branch mis_target asc cpi
20 2 5 100001 0 7844 63 0.0316277 1.03163

m n h accesses interf. mis_branch mis_target asc cpi
20 2 5 100001 0 11 6 6.79993e-05 1.00007

m n h accesses interf. mis_branch mis_target asc cpi
19 2 5 100001 0 11 6 6.79993e-05 1.00007

m n h accesses interf. mis_branch mis_target asc cpi
18 2 5 100001 0 11 6 6.79993e-05 1.00007

m n h accesses interf. mis_branch mis_target asc cpi
17 2 5 100001 0 11 6 6.79993e-05 1.00007

m n h accesses interf. mis_branch mis_target asc cpi
16 2 5 100001 0 11 6 6.79993e-05 1.00007

m n h accesses interf. mis_branch mis_target asc cpi
15 2 5 100001 0 11 6 6.79993e-05 1.00007

m n h accesses interf. mis_branch mis_target asc cpi
14 2 5 100001 0 11 6 6.79993e-05 1.00007

m n h accesses interf. mis_branch mis_target asc cpi
13 2 5 100001 0 11 6 6.79993e-05 1.00007

m n h accesses interf. mis_branch mis_target asc cpi
12 2 5 100001 0 11 6 6.79993e-05 1.00007

m n h accesses interf. mis_branch mis_target asc cpi
11 2 5 100001 0 11 6 6.79993e-05 1.00007

m n h accesses interf. mis_branch mis_target asc cpi
10 2 5 100001 0 11 6 6.79993e-05 1.00007

m n h accesses interf. mis_branch mis_target asc cpi
9 2 5 100001 0 11 6 6.79993e-05 1.00007

m n h accesses interf. mis_branch mis_target asc cpi
8 2 5 100001 0 11 6 6.79993e-05 1.00007

m n h accesses interf. mis_branch mis_target asc cpi
7 2 5 100001 0 11 6 6.79993e-05 1.00007

m n h accesses interf. mis_branch mis_target asc cpi
6 2 5 100001 0 11 6 6.79993e-05 1.00007

m n h accesses interf. mis_branch mis_target asc cpi
5 2 5 100001 20000 14 6 7.99992e-05 1.00008

m n h accesses interf. mis_branch mis_target asc cpi
4 2 5 100001 20000 14 6 7.99992e-05 1.00008

m n h accesses interf. mis_branch mis_target asc cpi
3 2 5 100001 59998 12 6 7.19993e-05 1.00007

m n h accesses interf. mis_branch mis_target asc cpi
2 2 5 100001 89998 12 40002 0.160054 1.16005

m n h accesses interf. mis_branch mis_target asc cpi
1 2 5 100001 99999 10 60000 0.240038 1.24004

m n h accesses interf. mis_branch mis_target asc cpi
1 2 5 100001 10139 3478 5191 0.0346757 1.03468

m n h accesses interf. mis_branch mis_target asc cpi
2 2 5 100001 8901 4144 3235 0.0295157 1.02952

m n h accesses interf. mis_branch mis_target asc cpi
3 2 5 100001 7162 3443 2507 0.0237998 1.0238

m n h accesses interf. mis_branch mis_target asc cpi
4 2 5 100001 5328 3019 1676 0.0187798 1.01878

m n h accesses interf. mis_branch mis_target asc cpi
5 2 5 100001 3049 2617 1483 0.0163998 1.0164

m n h accesses interf. mis_branch mis_target asc cpi
6 2 5 100001 2202 2025 1260 0.0131399 1.01314

m n h accesses interf. mis_branch mis_target asc cpi
7 2 5 100001 918 1647 687 0.00933591 1.00934

m n h accesses interf. mis_branch mis_target asc cpi
8 2 5 100001 524 1384 518 0.00760792 1.00761

m n h accesses interf. mis_branch mis_target asc cpi
9 2 5 100001 250 1299 397 0.00678393 1.00678

m n h accesses interf. mis_branch mis_target asc cpi
10 2 5 100001 0 1237 343 0.00631994 1.00632

m n h accesses interf. mis_branch mis_target asc cpi
11 2 5 100001 0 1237 343 0.00631994 1.00632

m n h accesses interf. mis_branch mis_target asc cpi
12 2 5 100001 0 1237 343 0.00631994 1.00632

m n h accesses interf. mis_branch mis_target asc cpi
13 2 5 100001 0 1237 343 0.00631994 1.00632

m n h accesses interf. mis_branch mis_target asc cpi
14 2 5 100001 0 1237 343 0.00631994 1.00632

m n h accesses interf. mis_branch mis_target asc cpi
15 2 5 100001 0 1237 343 0.00631994 1.00632

m n h accesses interf. mis_branch mis_target asc cpi
16 2 5 100001 0 1237 343 0.00631994 1.00632

m n h accesses interf. mis_branch mis_target asc cpi
17 2 5 100001 0 1237 343 0.00631994 1.00632

m n h accesses interf. mis_branch mis_target asc cpi
18 2 5 100001 0 1237 343 0.00631994 1.00632

m n h accesses interf. mis_branch mis_target asc cpi
19 2 5 100001 0 1237 343 0.00631994 1.00632
usage:proj2 m h n

m n h accesses interf. mis_branch mis_target asc cpi
20 2 5 100001 0 1237 343 0.00631994 1.00632

m n h accesses interf. mis_branch mis_target asc cpi
20 2 5 100001 0 6760 7007 0.0550674 1.05507

m n h accesses interf. mis_branch mis_target asc cpi
19 2 5 100001 0 6760 7007 0.0550674 1.05507

m n h accesses interf. mis_branch mis_target asc cpi
18 2 5 100001 0 6760 7007 0.0550674 1.05507

m n h accesses interf. mis_branch mis_target asc cpi
17 2 5 100001 0 6760 7007 0.0550674 1.05507

m n h accesses interf. mis_branch mis_target asc cpi
16 2 5 100001 0 6760 7007 0.0550674 1.05507

m n h accesses interf. mis_branch mis_target asc cpi
17 2 5 100001 0 6760 7007 0.0550674 1.05507

m n h accesses interf. mis_branch mis_target asc cpi
15 2 5 100001 0 6760 7007 0.0550674 1.05507

m n h accesses interf. mis_branch mis_target asc cpi
14 2 5 100001 0 6760 7007 0.0550674 1.05507

m n h accesses interf. mis_branch mis_target asc cpi
13 2 5 100001 0 6760 7007 0.0550674 1.05507

m n h accesses interf. mis_branch mis_target asc cpi
12 2 5 100001 927 6908 7081 0.0559554 1.05596

m n h accesses interf. mis_branch mis_target asc cpi
11 2 5 100001 1113 6948 7130 0.0563114 1.05631

m n h accesses interf. mis_branch mis_target asc cpi
10 2 5 100001 1883 7294 7376 0.0586794 1.05868

m n h accesses interf. mis_branch mis_target asc cpi
9 2 5 100001 5834 8789 8940 0.0709153 1.07092

m n h accesses interf. mis_branch mis_target asc cpi
8 2 5 100001 9429 10803 9760 0.0822512 1.08225

m n h accesses interf. mis_branch mis_target asc cpi
7 2 5 100001 18760 14021 11517 0.102151 1.10215

m n h accesses interf. mis_branch mis_target asc cpi
6 2 5 100001 40680 18392 17325 0.142867 1.14287

m n h accesses interf. mis_branch mis_target asc cpi
5 2 5 100001 54693 22620 24827 0.189786 1.18979

m n h accesses interf. mis_branch mis_target asc cpi
4 2 5 100001 72532 27631 31888 0.238074 1.23807

m n h accesses interf. mis_branch mis_target asc cpi
3 2 5 100001 82066 33912 38147 0.288233 1.28823

m n h accesses interf. mis_branch mis_target asc cpi
2 2 5 100001 90593 32656 44940 0.310381 1.31038

m n h accesses interf. mis_branch mis_target asc cpi
1 2 5 100001 95302 34280 45904 0.320733 1.32073

m n h accesses interf. mis_branch mis_target asc cpi
1 2 5 100001 95169 36444 33354 0.279189 1.27919

m n h accesses interf. mis_branch mis_target asc cpi
2 2 5 100001 92268 37046 32994 0.280157 1.28016

m n h accesses interf. mis_branch mis_target asc cpi
3 2 5 100001 85200 39152 31901 0.284209 1.28421

m n h accesses interf. mis_branch mis_target asc cpi
4 2 5 100001 78677 37067 28230 0.261185 1.26119

m n h accesses interf. mis_branch mis_target asc cpi
5 2 5 100001 72976 37093 26016 0.252433 1.25243

m n h accesses interf. mis_branch mis_target asc cpi
6 2 5 100001 64263 33547 21760 0.221226 1.22123

m n h accesses interf. mis_branch mis_target asc cpi
7 2 5 100001 48778 21444 14149 0.142371 1.14237

m n h accesses interf. mis_branch mis_target asc cpi
8 2 5 100001 31296 15163 8932 0.096379 1.09638

m n h accesses interf. mis_branch mis_target asc cpi
9 2 5 100001 15206 8893 6629 0.0620874 1.06209

m n h accesses interf. mis_branch mis_target asc cpi
10 2 5 100001 7027 6271 5769 0.0481595 1.04816

m n h accesses interf. mis_branch mis_target asc cpi
11 2 5 100001 4937 5852 5252 0.0444156 1.04442

m n h accesses interf. mis_branch mis_target asc cpi
12 2 5 100001 2215 5200 5191 0.0415636 1.04156

m n h accesses interf. mis_branch mis_target asc cpi
13 2 5 100001 1608 5083 5175 0.0410316 1.04103

m n h accesses interf. mis_branch mis_target asc cpi
14 2 5 100001 1544 5075 5168 0.0409716 1.04097

m n h accesses interf. mis_branch mis_target asc cpi
15 2 5 100001 13 5070 4420 0.0379596 1.03796

m n h accesses interf. mis_branch mis_target asc cpi
16 2 5 100001 0 5074 4419 0.0379716 1.03797

m n h accesses interf. mis_branch mis_target asc cpi
17 2 5 100001 0 5074 4419 0.0379716 1.03797

m n h accesses interf. mis_branch mis_target asc cpi
18 2 5 100001 0 5074 4419 0.0379716 1.03797

m n h accesses interf. mis_branch mis_target asc cpi
19 2 5 100001 0 5074 4419 0.0379716 1.03797

m n h accesses interf. mis_branch mis_target asc cpi
20 2 5 100001 0 5074 4419 0.0379716 1.03797

m n h accesses interf. mis_branch mis_target asc cpi
20 2 5 100001 0 1567 7430 0.0359876 1.03599

m n h accesses interf. mis_branch mis_target asc cpi
19 2 5 100001 0 1567 7430 0.0359876 1.03599

m n h accesses interf. mis_branch mis_target asc cpi
18 2 5 100001 0 1567 7430 0.0359876 1.03599

m n h accesses interf. mis_branch mis_target asc cpi
17 2 5 100001 0 1567 7430 0.0359876 1.03599

m n h accesses interf. mis_branch mis_target asc cpi
16 2 5 100001 9 1565 7430 0.0359796 1.03598

m n h accesses interf. mis_branch mis_target asc cpi
15 2 5 100001 1079 1921 7433 0.0374156 1.03742

m n h accesses interf. mis_branch mis_target asc cpi
14 2 5 100001 3237 2143 7445 0.0383516 1.03835

m n h accesses interf. mis_branch mis_target asc cpi
13 2 5 100001 4047 2416 7773 0.0407556 1.04076

m n h accesses interf. mis_branch mis_target asc cpi
12 2 5 100001 5338 2786 7913 0.0427956 1.0428

m n h accesses interf. mis_branch mis_target asc cpi
11 2 5 100001 8551 3858 8225 0.0483315 1.04833

m n h accesses interf. mis_branch mis_target asc cpi
10 2 5 100001 14756 5385 9414 0.0591954 1.0592

m n h accesses interf. mis_branch mis_target asc cpi
9 2 5 100001 23043 8567 10765 0.0773272 1.07733

m n h accesses interf. mis_branch mis_target asc cpi
8 2 5 100001 34565 11936 12366 0.097207 1.09721

m n h accesses interf. mis_branch mis_target asc cpi
7 2 5 100001 50442 16334 16051 0.129539 1.12954

m n h accesses interf. mis_branch mis_target asc cpi
6 2 5 100001 70879 21869 21795 0.174654 1.17465

m n h accesses interf. mis_branch mis_target asc cpi
5 2 5 100001 82050 29936 25218 0.220614 1.22061

m n h accesses interf. mis_branch mis_target asc cpi
4 2 5 100001 88664 33623 27653 0.245102 1.2451

m n h accesses interf. mis_branch mis_target asc cpi
3 2 5 100001 95003 34975 29202 0.256705 1.25671

m n h accesses interf. mis_branch mis_target asc cpi
2 2 5 100001 97504 34104 31423 0.262105 1.26211

m n h accesses interf. mis_branch mis_target asc cpi
1 2 5 100001 98052 34176 31466 0.262565 1.26257
Data for program 1: Cache design

w 400341a0
r dfcfa8
w 7b034dd4
r df7c48
r 7b034dd4
r 423aebbc
r 423aebb8
r 423aebbc
r 40002634
w 40139dd0
r 423aeb9c
w 40139dd4
w 40138938
r 423aeba0
w 4013893c
r 7b034dcc
r df8a70
w 7b034c50
w 7b034c68
r df9f10