/*****************************************************************************
* McPAT/CACTI
* SOFTWARE LICENSE AGREEMENT
* Copyright 2012 Hewlett-Packard Development Company, L.P.
* Copyright (c) 2010-2013 Advanced Micro Devices, Inc.
* All Rights Reserved
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met: redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer;
* redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution;
* neither the name of the copyright holders nor the names of its
* contributors may be used to endorse or promote products derived from
* this software without specific prior written permission.
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
***************************************************************************/
#include <cassert>
#include "Ucache.h"
#include "nuca.h"
unsigned int MIN_BANKSIZE = 65536;
#define FIXED_OVERHEAD 55e-12 /* clock skew and jitter in s. Ref: Hrishikesh et al ISCA 01 */
#define LATCH_DELAY 28e-12 /* latch delay in s (later should use FO4 TODO) */
#define CONTR_2_BANK_LAT 0
int cont_stats[2 /*l2 or l3*/][5/* cores */][ROUTER_TYPES][7 /*banks*/][8 /* cycle time */];
Nuca::Nuca(
TechnologyParameter::DeviceType *dt = &(g_tp.peri_global)
): deviceType(dt) {
init_cont();
}
void
Nuca::init_cont() {
FILE *cont;
char line[5000];
char jk[5000];
cont = fopen("contention.dat", "r");
if (!cont) {
cout << "contention.dat file is missing!\n";
exit(0);
}
for (int i = 0; i < 2; i++) {
for (int j = 2; j < 5; j++) {
for (int k = 0; k < ROUTER_TYPES; k++) {
for (int l = 0; l < 7; l++) {
int *temp = cont_stats[i/*l2 or l3*/][j/*core*/][k/*64 or 128 or 256 link bw*/][l /* no banks*/];
assert(fscanf(cont, "%[^\n]\n", line) != EOF);
sscanf(line, "%[^:]: %d %d %d %d %d %d %d %d", jk,
&temp[0], &temp[1], &temp[2], &temp[3],
&temp[4], &temp[5], &temp[6], &temp[7]);
}
}
}
}
fclose(cont);
}
void
Nuca::print_cont_stats() {
for (int i = 0; i < 2; i++) {
for (int j = 2; j < 5; j++) {
for (int k = 0; k < ROUTER_TYPES; k++) {
for (int l = 0; l < 7; l++) {
for (int m = 0; l < 7; l++) {
cout << cont_stats[i][j][k][l][m] << " ";
}
cout << endl;
}
}
}
}
cout << endl;
}
Nuca::~Nuca() {
for (int i = wt_min; i <= wt_max; i++) {
delete wire_vertical[i];
delete wire_horizontal[i];
}
}
/* converts latency (in s) to cycles depending upon the FREQUENCY (in GHz) */
int
Nuca::calc_cycles(double lat, double oper_freq) {
//TODO: convert latch delay to FO4 */
double cycle_time = (1.0 / (oper_freq * 1e9)); /*s*/
cycle_time -= LATCH_DELAY;
cycle_time -= FIXED_OVERHEAD;
return (int)ceil(lat / cycle_time);
}
nuca_org_t::~nuca_org_t() {
// if(h_wire) delete h_wire;
// if(v_wire) delete v_wire;
// if(router) delete router;
}
/*
* Version - 6.0
*
* Perform exhaustive search across different bank organizatons,
* router configurations, grid organizations, and wire models and
* find an optimal NUCA organization
* For different bank count values
* 1. Optimal bank organization is calculated
* 2. For each bank organization, find different NUCA organizations
* using various router configurations, grid organizations,
* and wire models.
* 3. NUCA model with the least cost is picked for
* this particular bank count
* Finally include contention statistics and find the optimal
* NUCA configuration
*/
void
Nuca::sim_nuca() {
/* temp variables */
int it, ro, wr;
int num_cyc;
unsigned int i, j, k;
unsigned int r, c;
int l2_c;
int bank_count = 0;
uca_org_t ures;
nuca_org_t *opt_n;
mem_array tag, data;
list<nuca_org_t *> nuca_list;
Router *router_s[ROUTER_TYPES];
router_s[0] = new Router(64.0, 8, 4, &(g_tp.peri_global));
router_s[0]->print_router();
router_s[1] = new Router(128.0, 8, 4, &(g_tp.peri_global));
router_s[1]->print_router();
router_s[2] = new Router(256.0, 8, 4, &(g_tp.peri_global));
router_s[2]->print_router();
int core_in; // to store no. of cores
/* to search diff grid organizations */
double curr_hop, totno_hops, totno_hhops, totno_vhops, tot_lat,
curr_acclat;
double avg_lat, avg_hop, avg_hhop, avg_vhop, avg_dyn_power,
avg_leakage_power;
double opt_acclat = INF, opt_avg_lat = INF, opt_tot_lat = INF;
int opt_rows = 0;
int opt_columns = 0;
double opt_totno_hops = 0;
double opt_avg_hop = 0;
double opt_dyn_power = 0, opt_leakage_power = 0;
min_values_t minval;
int bank_start = 0;
int flit_width = 0;
/* vertical and horizontal hop latency values */
int ver_hop_lat, hor_hop_lat; /* in cycles */
/* no. of different bank sizes to consider */
int iterations;
g_ip->nuca_cache_sz = g_ip->cache_sz;
nuca_list.push_back(new nuca_org_t());
if (g_ip->cache_level == 0) l2_c = 1;
else l2_c = 0;
if (g_ip->cores <= 4) core_in = 2;
else if (g_ip->cores <= 8) core_in = 3;
else if (g_ip->cores <= 16) core_in = 4;
else {
cout << "Number of cores should be <= 16!\n";
exit(0);
}
// set the lower bound to an appropriate value. this depends on cache associativity
if (g_ip->assoc > 2) {
i = 2;
while (i != g_ip->assoc) {
MIN_BANKSIZE *= 2;
i *= 2;
}
}
iterations = (int)logtwo((int)g_ip->cache_sz / MIN_BANKSIZE);
if (g_ip->force_wiretype) {
if (g_ip->wt == Low_swing) {
wt_min = Low_swing;
wt_max = Low_swing;
} else {
wt_min = Global;
wt_max = Low_swing - 1;
}
} else {
wt_min = Global;
wt_max = Low_swing;
}
if (g_ip->nuca_bank_count != 0) { // simulate just one bank
if (g_ip->nuca_bank_count != 2 && g_ip->nuca_bank_count != 4 &&
g_ip->nuca_bank_count != 8 && g_ip->nuca_bank_count != 16 &&
g_ip->nuca_bank_count != 32 && g_ip->nuca_bank_count != 64) {
fprintf(stderr, "Incorrect bank count value! Please fix the ",
"value in cache.cfg\n");
}
bank_start = (int)logtwo((double)g_ip->nuca_bank_count);
iterations = bank_start + 1;
g_ip->cache_sz = g_ip->cache_sz / g_ip->nuca_bank_count;
}
cout << "Simulating various NUCA configurations\n";
for (it = bank_start; it < iterations; it++) {
/* different bank count values */
ures.tag_array2 = &tag;
ures.data_array2 = &data;
/*
* find the optimal bank organization
*/
solve(&ures);
// output_UCA(&ures);
bank_count = g_ip->nuca_cache_sz / g_ip->cache_sz;
cout << "====" << g_ip->cache_sz << "\n";
for (wr = wt_min; wr <= wt_max; wr++) {
for (ro = 0; ro < ROUTER_TYPES; ro++) {
flit_width = (int) router_s[ro]->flit_size; //initialize router
nuca_list.back()->nuca_pda.cycle_time = router_s[ro]->cycle_time;
/* calculate router and wire parameters */
double vlength = ures.cache_ht; /* length of the wire (u)*/
double hlength = ures.cache_len; // u
/* find delay, area, and power for wires */
wire_vertical[wr] = new Wire((enum Wire_type) wr, vlength);
wire_horizontal[wr] = new Wire((enum Wire_type) wr, hlength);
hor_hop_lat =
calc_cycles(wire_horizontal[wr]->delay,
1 /(nuca_list.back()->nuca_pda.cycle_time *
.001));
ver_hop_lat =
calc_cycles(wire_vertical[wr]->delay,
1 / (nuca_list.back()->nuca_pda.cycle_time *
.001));
/*
* assume a grid like topology and explore for optimal network
* configuration using different row and column count values.
*/
for (c = 1; c <= (unsigned int)bank_count; c++) {
while (bank_count % c != 0) c++;
r = bank_count / c;
/*
* to find the avg access latency of a NUCA cache, uncontended
* access time to each bank from the
* cache controller is calculated.
* avg latency =
* sum of the access latencies to individual banks)/bank
* count value.
*/
totno_hops = totno_hhops = totno_vhops = tot_lat = 0;
k = 1;
for (i = 0; i < r; i++) {
for (j = 0; j < c; j++) {
/*
* vertical hops including the
* first hop from the cache controller
*/
curr_hop = i + 1;
curr_hop += j; /* horizontal hops */
totno_hhops += j;
totno_vhops += (i + 1);
curr_acclat = (i * ver_hop_lat + CONTR_2_BANK_LAT +
j * hor_hop_lat);
tot_lat += curr_acclat;
totno_hops += curr_hop;
}
}
avg_lat = tot_lat / bank_count;
avg_hop = totno_hops / bank_count;
avg_hhop = totno_hhops / bank_count;
avg_vhop = totno_vhops / bank_count;
/* net access latency */
curr_acclat = 2 * avg_lat + 2 * (router_s[ro]->delay *
avg_hop) +
calc_cycles(ures.access_time,
1 /
(nuca_list.back()->nuca_pda.cycle_time *
.001));
/* avg access lat of nuca */
avg_dyn_power =
avg_hop *
(router_s[ro]->power.readOp.dynamic) + avg_hhop *
(wire_horizontal[wr]->power.readOp.dynamic) *
(g_ip->block_sz * 8 + 64) + avg_vhop *
(wire_vertical[wr]->power.readOp.dynamic) *
(g_ip->block_sz * 8 + 64) + ures.power.readOp.dynamic;
avg_leakage_power =
bank_count * router_s[ro]->power.readOp.leakage +
avg_hhop * (wire_horizontal[wr]->power.readOp.leakage *
wire_horizontal[wr]->delay) * flit_width +
avg_vhop * (wire_vertical[wr]->power.readOp.leakage *
wire_horizontal[wr]->delay);
if (curr_acclat < opt_acclat) {
opt_acclat = curr_acclat;
opt_tot_lat = tot_lat;
opt_avg_lat = avg_lat;
opt_totno_hops = totno_hops;
opt_avg_hop = avg_hop;
opt_rows = r;
opt_columns = c;
opt_dyn_power = avg_dyn_power;
opt_leakage_power = avg_leakage_power;
}
totno_hops = 0;
tot_lat = 0;
totno_hhops = 0;
totno_vhops = 0;
}
nuca_list.back()->wire_pda.power.readOp.dynamic =
opt_avg_hop * flit_width *
(wire_horizontal[wr]->power.readOp.dynamic +
wire_vertical[wr]->power.readOp.dynamic);
nuca_list.back()->avg_hops = opt_avg_hop;
/* network delay/power */
nuca_list.back()->h_wire = wire_horizontal[wr];
nuca_list.back()->v_wire = wire_vertical[wr];
nuca_list.back()->router = router_s[ro];
/* bank delay/power */
nuca_list.back()->bank_pda.delay = ures.access_time;
nuca_list.back()->bank_pda.power = ures.power;
nuca_list.back()->bank_pda.area.h = ures.cache_ht;
nuca_list.back()->bank_pda.area.w = ures.cache_len;
nuca_list.back()->bank_pda.cycle_time = ures.cycle_time;
num_cyc = calc_cycles(nuca_list.back()->bank_pda.delay /*s*/,
1 /
(nuca_list.back()->nuca_pda.cycle_time *
.001/*GHz*/));
if (num_cyc % 2 != 0) num_cyc++;
if (num_cyc > 16) num_cyc = 16; // we have data only up to 16 cycles
if (it < 7) {
nuca_list.back()->nuca_pda.delay = opt_acclat +
cont_stats[l2_c][core_in][ro][it][num_cyc/2-1];
nuca_list.back()->contention =
cont_stats[l2_c][core_in][ro][it][num_cyc/2-1];
} else {
nuca_list.back()->nuca_pda.delay = opt_acclat +
cont_stats[l2_c][core_in][ro][7][num_cyc/2-1];
nuca_list.back()->contention =
cont_stats[l2_c][core_in][ro][7][num_cyc/2-1];
}
nuca_list.back()->nuca_pda.power.readOp.dynamic = opt_dyn_power;
nuca_list.back()->nuca_pda.power.readOp.leakage = opt_leakage_power;
/* array organization */
nuca_list.back()->bank_count = bank_count;
nuca_list.back()->rows = opt_rows;
nuca_list.back()->columns = opt_columns;
calculate_nuca_area (nuca_list.back());
minval.update_min_values(nuca_list.back());
nuca_list.push_back(new nuca_org_t());
opt_acclat = BIGNUM;
}
}
g_ip->cache_sz /= 2;
}
delete(nuca_list.back());
nuca_list.pop_back();
opt_n = find_optimal_nuca(&nuca_list, &minval);
print_nuca(opt_n);
g_ip->cache_sz = g_ip->nuca_cache_sz / opt_n->bank_count;
list<nuca_org_t *>::iterator niter;
for (niter = nuca_list.begin(); niter != nuca_list.end(); ++niter) {
delete *niter;
}
nuca_list.clear();
for (int i = 0; i < ROUTER_TYPES; i++) {
delete router_s[i];
}
g_ip->display_ip();
// g_ip->force_cache_config = true;
// g_ip->ndwl = 8;
// g_ip->ndbl = 16;
// g_ip->nspd = 4;
// g_ip->ndcm = 1;
// g_ip->ndsam1 = 8;
// g_ip->ndsam2 = 32;
}
void
Nuca::print_nuca (nuca_org_t *fr) {
printf("\n---------- CACTI version 6.5, Non-uniform Cache Access "
"----------\n\n");
printf("Optimal number of banks - %d\n", fr->bank_count);
printf("Grid organization rows x columns - %d x %d\n",
fr->rows, fr->columns);
printf("Network frequency - %g GHz\n",
(1 / fr->nuca_pda.cycle_time)*1e3);
printf("Cache dimension (mm x mm) - %g x %g\n",
fr->nuca_pda.area.h,
fr->nuca_pda.area.w);
fr->router->print_router();
printf("\n\nWire stats:\n");
if (fr->h_wire->wt == Global) {
printf("\tWire type - Full swing global wires with least "
"possible delay\n");
} else if (fr->h_wire->wt == Global_5) {
printf("\tWire type - Full swing global wires with "
"5%% delay penalty\n");
} else if (fr->h_wire->wt == Global_10) {
printf("\tWire type - Full swing global wires with "
"10%% delay penalty\n");
} else if (fr->h_wire->wt == Global_20) {
printf("\tWire type - Full swing global wires with "
"20%% delay penalty\n");
} else if (fr->h_wire->wt == Global_30) {
printf("\tWire type - Full swing global wires with "
"30%% delay penalty\n");
} else if (fr->h_wire->wt == Low_swing) {
printf("\tWire type - Low swing wires\n");
}
printf("\tHorizontal link delay - %g (ns)\n",
fr->h_wire->delay*1e9);
printf("\tVertical link delay - %g (ns)\n",
fr->v_wire->delay*1e9);
printf("\tDelay/length - %g (ns/mm)\n",
fr->h_wire->delay*1e9 / fr->bank_pda.area.w);
printf("\tHorizontal link energy -dynamic/access %g (nJ)\n"
"\t -leakage %g (nW)\n\n",
fr->h_wire->power.readOp.dynamic*1e9,
fr->h_wire->power.readOp.leakage*1e9);
printf("\tVertical link energy -dynamic/access %g (nJ)\n"
"\t -leakage %g (nW)\n\n",
fr->v_wire->power.readOp.dynamic*1e9,
fr->v_wire->power.readOp.leakage*1e9);
printf("\n\n");
fr->v_wire->print_wire();
printf("\n\nBank stats:\n");
}
nuca_org_t *
Nuca::find_optimal_nuca (list<nuca_org_t *> *n, min_values_t *minval) {
double cost = 0;
double min_cost = BIGNUM;
nuca_org_t *res = NULL;
float d, a, dp, lp, c;
int v;
dp = g_ip->dynamic_power_wt_nuca;
lp = g_ip->leakage_power_wt_nuca;
a = g_ip->area_wt_nuca;
d = g_ip->delay_wt_nuca;
c = g_ip->cycle_time_wt_nuca;
list<nuca_org_t *>::iterator niter;
for (niter = n->begin(); niter != n->end(); niter++) {
fprintf(stderr, "\n-----------------------------"
"---------------\n");
printf("NUCA___stats %d \tbankcount: lat = %g \tdynP = %g \twt = %d\t "
"bank_dpower = %g \tleak = %g \tcycle = %g\n",
(*niter)->bank_count,
(*niter)->nuca_pda.delay,
(*niter)->nuca_pda.power.readOp.dynamic,
(*niter)->h_wire->wt,
(*niter)->bank_pda.power.readOp.dynamic,
(*niter)->nuca_pda.power.readOp.leakage,
(*niter)->nuca_pda.cycle_time);
if (g_ip->ed == 1) {
cost = ((*niter)->nuca_pda.delay / minval->min_delay) *
((*niter)->nuca_pda.power.readOp.dynamic / minval->min_dyn);
if (min_cost > cost) {
min_cost = cost;
res = ((*niter));
}
} else if (g_ip->ed == 2) {
cost = ((*niter)->nuca_pda.delay / minval->min_delay) *
((*niter)->nuca_pda.delay / minval->min_delay) *
((*niter)->nuca_pda.power.readOp.dynamic / minval->min_dyn);
if (min_cost > cost) {
min_cost = cost;
res = ((*niter));
}
} else {
/*
* check whether the current organization
* meets the input deviation constraints
*/
v = check_nuca_org((*niter), minval);
if (minval->min_leakage == 0) minval->min_leakage = 0.1; //FIXME remove this after leakage modeling
if (v) {
cost = (d * ((*niter)->nuca_pda.delay / minval->min_delay) +
c * ((*niter)->nuca_pda.cycle_time / minval->min_cyc) +
dp * ((*niter)->nuca_pda.power.readOp.dynamic /
minval->min_dyn) +
lp * ((*niter)->nuca_pda.power.readOp.leakage /
minval->min_leakage) +
a * ((*niter)->nuca_pda.area.get_area() /
minval->min_area));
fprintf(stderr, "cost = %g\n", cost);
if (min_cost > cost) {
min_cost = cost;
res = ((*niter));
}
} else {
niter = n->erase(niter);
if (niter != n->begin())
niter --;
}
}
}
return res;
}
int
Nuca::check_nuca_org (nuca_org_t *n, min_values_t *minval) {
if (((n->nuca_pda.delay - minval->min_delay)*100 / minval->min_delay) >
g_ip->delay_dev_nuca) {
return 0;
}
if (((n->nuca_pda.power.readOp.dynamic - minval->min_dyn) /
minval->min_dyn)*100 >
g_ip->dynamic_power_dev_nuca) {
return 0;
}
if (((n->nuca_pda.power.readOp.leakage - minval->min_leakage) /
minval->min_leakage)*100 >
g_ip->leakage_power_dev_nuca) {
return 0;
}
if (((n->nuca_pda.cycle_time - minval->min_cyc) / minval->min_cyc)*100 >
g_ip->cycle_time_dev_nuca) {
return 0;
}
if (((n->nuca_pda.area.get_area() - minval->min_area) / minval->min_area) *
100 >
g_ip->area_dev_nuca) {
return 0;
}
return 1;
}
void
Nuca::calculate_nuca_area (nuca_org_t *nuca) {
nuca->nuca_pda.area.h =
nuca->rows * ((nuca->h_wire->wire_width +
nuca->h_wire->wire_spacing)
* nuca->router->flit_size +
nuca->bank_pda.area.h);
nuca->nuca_pda.area.w =
nuca->columns * ((nuca->v_wire->wire_width +
nuca->v_wire->wire_spacing)
* nuca->router->flit_size +
nuca->bank_pda.area.w);
}