[OpenSPARC-T2-SAM] / rst / rstzip3 / rstzip_v3 / rz3_valuecache.h

/*
* ========== Copyright Header Begin ==========================================
* 
* OpenSPARC T2 Processor File: rz3_valuecache.h
* Copyright (c) 2006 Sun Microsystems, Inc.  All Rights Reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES.
* 
* The above named program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public
* License version 2 as published by the Free Software Foundation.
* 
* The above named program is distributed in the hope that it will be 
* useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
* General Public License for more details.
* 
* You should have received a copy of the GNU General Public
* License along with this work; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
* 
* ========== Copyright Header End ============================================
*/
/* rz3_valuecache.h
 * multi-level value cache
 */

#ifndef _rz3_valuecache_h_
#define _rz3_valuecache_h_


#include <stdlib.h>
#include <sys/types.h>
#include <string.h>
#include <strings.h>


// set the following to 0 unless debugging
#define rz3_valuecache_debug 0

struct rz3_valuecache_module {

  rz3_valuecache_module(int arg_size, int arg_lsbits) {

    size = arg_size;
    lsbits = arg_lsbits;

    tags = new uint64_t [size];

    refs = misses = 0;

    Clear();
  }

  ~rz3_valuecache_module() {
    delete [] tags;
  }

  void Clear() {
    bzero(tags, size*sizeof(uint64_t));
  }


  int size;
  int lsbits;
  uint64_t *tags;

  uint64_t refs;
  uint64_t misses;

  // these are statistics-related variables set and used by rz3_valuecache
  int cost; // cost per hit
  uint64_t level_hits;
  uint64_t levelcost; // total cost of hits at this level

}; // struct rz3_valuecache_tbl


// these are hand-crafted values based on several tpcc, specweb, spec cpu traces
// size must be LESS THAN 2^idxbits because we use index=size as a special marker

// values are defined both as scalar consts and static const arrays because the scalar
// consts are used to define other static structs while the arrays are indexed by
// program variables
static const int rz3_valuecache_size0 = 7;
static const int rz3_valuecache_size1 = 31;
static const int rz3_valuecache_size2 = 61;
static const int rz3_valuecache_size3 = 127;
static const int rz3_valuecache_size4 = 509;
static const int rz3_valuecache_size5 = 2039;
static const int rz3_valuecache_size6 = 8191;
static const int rz3_valuecache_size[] = {
  rz3_valuecache_size0,
  rz3_valuecache_size1,
  rz3_valuecache_size2,
  rz3_valuecache_size3,
  rz3_valuecache_size4,
  rz3_valuecache_size5,
  rz3_valuecache_size6,
};

static const int rz3_valuecache_idxbits0 = 3;
static const int rz3_valuecache_idxbits1 = 5;
static const int rz3_valuecache_idxbits2 = 6;
static const int rz3_valuecache_idxbits3 = 7;
static const int rz3_valuecache_idxbits4 = 9;
static const int rz3_valuecache_idxbits5 = 11;
static const int rz3_valuecache_idxbits6 = 13;
static const int rz3_valuecache_idxbits[] = {
  rz3_valuecache_idxbits0,
  rz3_valuecache_idxbits1,
  rz3_valuecache_idxbits2,
  rz3_valuecache_idxbits3,
  rz3_valuecache_idxbits4,
  rz3_valuecache_idxbits5,
  rz3_valuecache_idxbits6,
};

static const int rz3_valuecache_lsbits0 = 4;
static const int rz3_valuecache_lsbits1 = 6;
static const int rz3_valuecache_lsbits2 = 7;
static const int rz3_valuecache_lsbits3 = 8;
static const int rz3_valuecache_lsbits4 = 9;
static const int rz3_valuecache_lsbits5 = 10;
static const int rz3_valuecache_lsbits6 = 12;
static const int rz3_valuecache_lsbits[] = {
  rz3_valuecache_lsbits0,
  rz3_valuecache_lsbits1,
  rz3_valuecache_lsbits2,
  rz3_valuecache_lsbits3,
  rz3_valuecache_lsbits4,
  rz3_valuecache_lsbits5,
  rz3_valuecache_lsbits6,
};

struct rz3_valuecache {

  enum consts_e {
    nlevels = 7
  };

  rz3_valuecache(const char * arg_name) {

    name = (arg_name == NULL) ? strdup("Noname") : strdup(arg_name);

    modules = new rz3_valuecache_module * [nlevels];

    lsbmask = new uint64_t [nlevels];

    int i;
    for (i=0; i<nlevels; i++) {
      modules[i] = new rz3_valuecache_module(rz3_valuecache_size[i], rz3_valuecache_lsbits[i]);
      lsbmask[i] = (1ull << rz3_valuecache_lsbits[i]) - 1;
    }

    refs = 0;
    misses = 0;

    level_id_bits = nbits(nlevels); // 0..(nlevels-1) and raw value is an additional level
  }

  ~rz3_valuecache() {
    int i;
    for (i=0; i<nlevels; i++) {
      delete modules[i];
      modules[i] = NULL;
    }
    delete [] modules;

    delete [] lsbmask;

    free(name);
  }


  void Clear() {
    int i;
    for (i=0; i<nlevels; i++) {
      modules[i]->Clear();
    }
  }


  int Ref(uint64_t v, uint64_t & key) {
    refs++;
    int i;

    if (rz3_valuecache_debug) fprintf(stderr, "valuecache %s: ref %lld: v=%llx ", name, refs, v);
    for (i=0; i<nlevels; i++) {
      modules[i]->refs++;

      uint64_t tag = (v >> rz3_valuecache_lsbits[i]);
      if (tag == 0) {
	// write a special idx to indicate tag=0
	uint64_t idx = rz3_valuecache_size[i]; // size is guaranteed to be <idxbits> because size is < 2^(idxbits>
	key = (idx << rz3_valuecache_lsbits[i]) | (v & lsbmask[i]);
	if (rz3_valuecache_debug) fprintf(stderr, "HIT: level=%d tag=0 idx=%x key=%llx\n", i, idx, key);
	return i;
      }
      uint64_t idx = tag % rz3_valuecache_size[i];
      if (modules[i]->tags[idx] == tag) {
	key = (idx << rz3_valuecache_lsbits[i]) | (v & lsbmask[i]);
	if (rz3_valuecache_debug) fprintf(stderr, "HIT: level=%d tag=%llx idx=%x key=%llx\n", i, tag, idx, key);
	return i;
      } else {
	modules[i]->tags[idx] = tag;
	modules[i]->misses++;
      }
    }
    if (rz3_valuecache_debug) fprintf(stderr, "MISS: key=value\n");

    misses++;
    key = v;
    return nlevels; // indicates a miss

  } // Ref()

  bool Retrieve(int level, uint64_t key, uint64_t & v)
  {

    if (level == nlevels) {
      v = key;
      if (rz3_valuecache_debug) fprintf(stderr, "valuecache %s: Retrieve: refs=%lld level %d key %llx (value=key)\n", name, refs, level, key);
    } else {

      uint64_t lsbits = key & lsbmask[level];
      uint idx = key >> rz3_valuecache_lsbits[level];

      if (idx == rz3_valuecache_size[level]) {
	v = lsbits;
      } else {
	v = (((uint64_t)modules[level]->tags[idx]) << rz3_valuecache_lsbits[level]) | lsbits;
      }

      if (rz3_valuecache_debug) fprintf(stderr, "valuecache %s: Retrieve: refs %lld level %d key %llx (idx %x lsb %llx)\n", name, refs, level, key, idx, lsbits);
    }


    uint64_t key2;
    int level2;
    level2 = Ref(v, key2);

    if ((level2 != level) || (key2 != key)) {
      fprintf(stderr, "valuecache %s: Retrieve ERROR - retrieved value does not match result of Ref()\n", name);
      fprintf(stderr, "  refs %lld level %d key %llx retrieved value %llx retrieved level %d retrieved key %llx\n", refs, level, key, v, level2, key2);
      return false;
    }
 
    return true;
  }


#if 0
  int Ref_noupdate(uint64_t v, uint64_t & key) {
    refs++;
    int i;

    for (i=0; i<nlevels; i++) {
      modules[i]->refs++;
      uint64_t tag = (v >> rz3_valuecache_lsbits[i]);
      if (tag == 0) {
	// write a special idx to indicate tag=0
	uint64_t idx = rz3_valuecache_size[i]-1;
	key = (idx << rz3_valuecache_lsbits[i]) | (v & lsbmask[i]);
	return i;
      }
      uint64_t idx = tag % rz3_valuecache_size[i];
      if (modules[i]->tags[idx] == tag) {
	key = (idx << rz3_valuecache_lsbits[i]) | (v & lsbmask[i]);
	return i;
      } else {
	// modules[i]->tags[idx] = tag;
	modules[i]->misses++;
      }
    }
    misses++;
    key = v;
    return nlevels; // indicates a miss

  }
#endif
  char * name;

  struct rz3_valuecache_module ** modules;

  uint64_t * lsbmask;

  uint64_t refs;
  uint64_t misses;

  int level_id_bits;

  void Report(FILE *fp) {
    fprintf(fp, "\nValuecache %s report:\n", name);
    fprintf(fp, "Refs %lld Misses %lld (%0.4f%%/ref)\n", refs, misses, misses*100.0/refs);

    uint64_t rawcost = misses * (64 + level_id_bits);

    uint64_t cost = 0;
    int i;
    for (i=0; i<nlevels; i++) {
      modules[i]->cost = modules[i]->lsbits + nbits(modules[i]->size-1);
      modules[i]->levelcost = (modules[i]->refs-modules[i]->misses) * (modules[i]->cost + level_id_bits);
      cost += modules[i]->levelcost;
    }
    cost += rawcost;

    uint64_t incr_cost = 0;
    for (i=0; i<nlevels; i++) {
      fprintf(fp, "level %d: Refs %lld Misses %lld (%0.4f%%/local-ref, %0.4f%%/ref)\n", i, modules[i]->refs, modules[i]->misses,
	      modules[i]->misses*100.0/modules[i]->refs, modules[i]->misses*100.0/refs);
      uint64_t levelcost = modules[i]->levelcost;
      incr_cost += levelcost;
      fprintf(fp, "  cost = %lld hits * (%d idxlsb + %d lvl bits) = %lld [%lld] (%0.4f/ref) %0.4f%% of total\n",
	     (modules[i]->refs-modules[i]->misses), modules[i]->cost, level_id_bits, levelcost, incr_cost, levelcost*1.0/refs, levelcost*100.0/cost);
    }

    fprintf(fp, "cost of raw ea: %lld * (64 + %d id-bits) = %lld %0.4f%% of total\n", misses, level_id_bits, rawcost, rawcost*100.0/cost);

    fprintf(fp, "Total cost: %lld (%0.4f bits/ref)\n", cost, cost*1.0/refs);

  }


  static int nbits(uint64_t n) {
    int rv = 1;
    while(n>>rv) {
      rv++;
    }
    return rv;
  }

}; // struct valuecache


#endif // _rz3_valuecache_h_
Commit	Line	Data
920dae64 AT	1	/*
	2	* ========== Copyright Header Begin ==========================================
	3	*
	4	* OpenSPARC T2 Processor File: rz3_valuecache.h
	5	* Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
	6	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES.
	7	*
	8	* The above named program is free software; you can redistribute it and/or
	9	* modify it under the terms of the GNU General Public
	10	* License version 2 as published by the Free Software Foundation.
	11	*
	12	* The above named program is distributed in the hope that it will be
	13	* useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
	14	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	15	* General Public License for more details.
	16	*
	17	* You should have received a copy of the GNU General Public
	18	* License along with this work; if not, write to the Free Software
	19	* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
	20	*
	21	* ========== Copyright Header End ============================================
	22	*/
	23	/* rz3_valuecache.h
	24	* multi-level value cache
	25	*/
	26
	27	#ifndef _rz3_valuecache_h_
	28	#define _rz3_valuecache_h_
	29
	30
	31	#include <stdlib.h>
	32	#include <sys/types.h>
	33	#include <string.h>
	34	#include <strings.h>
	35
	36
	37	// set the following to 0 unless debugging
	38	#define rz3_valuecache_debug 0
	39
	40	struct rz3_valuecache_module {
	41
	42	rz3_valuecache_module(int arg_size, int arg_lsbits) {
	43
	44	size = arg_size;
	45	lsbits = arg_lsbits;
	46
	47	tags = new uint64_t [size];
	48
	49	refs = misses = 0;
	50
	51	Clear();
	52	}
	53
	54	~rz3_valuecache_module() {
	55	delete [] tags;
	56	}
	57
	58	void Clear() {
	59	bzero(tags, size*sizeof(uint64_t));
	60	}
	61
	62
	63	int size;
	64	int lsbits;
65	uint64_t *tags;
66
67	uint64_t refs;
68	uint64_t misses;
69
70	// these are statistics-related variables set and used by rz3_valuecache
71	int cost; // cost per hit
72	uint64_t level_hits;
73	uint64_t levelcost; // total cost of hits at this level
74
75	}; // struct rz3_valuecache_tbl
76
77
78	// these are hand-crafted values based on several tpcc, specweb, spec cpu traces
79	// size must be LESS THAN 2^idxbits because we use index=size as a special marker
80
81	// values are defined both as scalar consts and static const arrays because the scalar
82	// consts are used to define other static structs while the arrays are indexed by
83	// program variables
84	static const int rz3_valuecache_size0 = 7;
85	static const int rz3_valuecache_size1 = 31;
86	static const int rz3_valuecache_size2 = 61;
87	static const int rz3_valuecache_size3 = 127;
88	static const int rz3_valuecache_size4 = 509;
89	static const int rz3_valuecache_size5 = 2039;
90	static const int rz3_valuecache_size6 = 8191;
91	static const int rz3_valuecache_size[] = {
92	rz3_valuecache_size0,
93	rz3_valuecache_size1,
94	rz3_valuecache_size2,
95	rz3_valuecache_size3,
96	rz3_valuecache_size4,
97	rz3_valuecache_size5,
98	rz3_valuecache_size6,
99	};
100
101	static const int rz3_valuecache_idxbits0 = 3;
102	static const int rz3_valuecache_idxbits1 = 5;
103	static const int rz3_valuecache_idxbits2 = 6;
104	static const int rz3_valuecache_idxbits3 = 7;
105	static const int rz3_valuecache_idxbits4 = 9;
106	static const int rz3_valuecache_idxbits5 = 11;
107	static const int rz3_valuecache_idxbits6 = 13;
108	static const int rz3_valuecache_idxbits[] = {
109	rz3_valuecache_idxbits0,
110	rz3_valuecache_idxbits1,
111	rz3_valuecache_idxbits2,
112	rz3_valuecache_idxbits3,
113	rz3_valuecache_idxbits4,
114	rz3_valuecache_idxbits5,
115	rz3_valuecache_idxbits6,
116	};
117
118	static const int rz3_valuecache_lsbits0 = 4;
119	static const int rz3_valuecache_lsbits1 = 6;
120	static const int rz3_valuecache_lsbits2 = 7;
121	static const int rz3_valuecache_lsbits3 = 8;
122	static const int rz3_valuecache_lsbits4 = 9;
123	static const int rz3_valuecache_lsbits5 = 10;
124	static const int rz3_valuecache_lsbits6 = 12;
125	static const int rz3_valuecache_lsbits[] = {
126	rz3_valuecache_lsbits0,
127	rz3_valuecache_lsbits1,
128	rz3_valuecache_lsbits2,
129	rz3_valuecache_lsbits3,
130	rz3_valuecache_lsbits4,
131	rz3_valuecache_lsbits5,
132	rz3_valuecache_lsbits6,
133	};
134
135	struct rz3_valuecache {
136
137	enum consts_e {
138	nlevels = 7
139	};
140
141	rz3_valuecache(const char * arg_name) {
142
143	name = (arg_name == NULL) ? strdup("Noname") : strdup(arg_name);
144
145	modules = new rz3_valuecache_module * [nlevels];
146
147	lsbmask = new uint64_t [nlevels];
148
149	int i;
150	for (i=0; i<nlevels; i++) {
151	modules[i] = new rz3_valuecache_module(rz3_valuecache_size[i], rz3_valuecache_lsbits[i]);
152	lsbmask[i] = (1ull << rz3_valuecache_lsbits[i]) - 1;
153	}
154
155	refs = 0;
156	misses = 0;
157
158	level_id_bits = nbits(nlevels); // 0..(nlevels-1) and raw value is an additional level
159	}
160
161	~rz3_valuecache() {
162	int i;
163	for (i=0; i<nlevels; i++) {
164	delete modules[i];
165	modules[i] = NULL;
166	}
167	delete [] modules;
168
169	delete [] lsbmask;
170
171	free(name);
172	}
173
174
175	void Clear() {
176	int i;
177	for (i=0; i<nlevels; i++) {
178	modules[i]->Clear();
179	}
180	}
181
182
183	int Ref(uint64_t v, uint64_t & key) {
184	refs++;
185	int i;
186
187	if (rz3_valuecache_debug) fprintf(stderr, "valuecache %s: ref %lld: v=%llx ", name, refs, v);
188	for (i=0; i<nlevels; i++) {
189	modules[i]->refs++;
190
191	uint64_t tag = (v >> rz3_valuecache_lsbits[i]);
192	if (tag == 0) {
193	// write a special idx to indicate tag=0
194	uint64_t idx = rz3_valuecache_size[i]; // size is guaranteed to be <idxbits> because size is < 2^(idxbits>
195	key = (idx << rz3_valuecache_lsbits[i]) \| (v & lsbmask[i]);
196	if (rz3_valuecache_debug) fprintf(stderr, "HIT: level=%d tag=0 idx=%x key=%llx\n", i, idx, key);
197	return i;
198	}
199	uint64_t idx = tag % rz3_valuecache_size[i];
200	if (modules[i]->tags[idx] == tag) {
201	key = (idx << rz3_valuecache_lsbits[i]) \| (v & lsbmask[i]);
202	if (rz3_valuecache_debug) fprintf(stderr, "HIT: level=%d tag=%llx idx=%x key=%llx\n", i, tag, idx, key);
203	return i;
204	} else {
205	modules[i]->tags[idx] = tag;
206	modules[i]->misses++;
207	}
208	}
209	if (rz3_valuecache_debug) fprintf(stderr, "MISS: key=value\n");
210
211	misses++;
212	key = v;
213	return nlevels; // indicates a miss
214
215	} // Ref()
216
217	bool Retrieve(int level, uint64_t key, uint64_t & v)
218	{
219
220	if (level == nlevels) {
221	v = key;
222	if (rz3_valuecache_debug) fprintf(stderr, "valuecache %s: Retrieve: refs=%lld level %d key %llx (value=key)\n", name, refs, level, key);
223	} else {
224
225	uint64_t lsbits = key & lsbmask[level];
226	uint idx = key >> rz3_valuecache_lsbits[level];
227
228	if (idx == rz3_valuecache_size[level]) {
229	v = lsbits;
230	} else {
231	v = (((uint64_t)modules[level]->tags[idx]) << rz3_valuecache_lsbits[level]) \| lsbits;
232	}
233
234	if (rz3_valuecache_debug) fprintf(stderr, "valuecache %s: Retrieve: refs %lld level %d key %llx (idx %x lsb %llx)\n", name, refs, level, key, idx, lsbits);
235	}
236
237
238	uint64_t key2;
239	int level2;
240	level2 = Ref(v, key2);
241
242	if ((level2 != level) \|\| (key2 != key)) {
243	fprintf(stderr, "valuecache %s: Retrieve ERROR - retrieved value does not match result of Ref()\n", name);
244	fprintf(stderr, " refs %lld level %d key %llx retrieved value %llx retrieved level %d retrieved key %llx\n", refs, level, key, v, level2, key2);
245	return false;
246	}
247
248	return true;
249	}
250
251
252	#if 0
253	int Ref_noupdate(uint64_t v, uint64_t & key) {
254	refs++;
255	int i;
256
257	for (i=0; i<nlevels; i++) {
258	modules[i]->refs++;
259	uint64_t tag = (v >> rz3_valuecache_lsbits[i]);
260	if (tag == 0) {
261	// write a special idx to indicate tag=0
262	uint64_t idx = rz3_valuecache_size[i]-1;
263	key = (idx << rz3_valuecache_lsbits[i]) \| (v & lsbmask[i]);
264	return i;
265	}
266	uint64_t idx = tag % rz3_valuecache_size[i];
267	if (modules[i]->tags[idx] == tag) {
268	key = (idx << rz3_valuecache_lsbits[i]) \| (v & lsbmask[i]);
269	return i;
270	} else {
271	// modules[i]->tags[idx] = tag;
272	modules[i]->misses++;
273	}
274	}
275	misses++;
276	key = v;
277	return nlevels; // indicates a miss
278
279	}
280	#endif
281	char * name;
282
283	struct rz3_valuecache_module ** modules;
284
285	uint64_t * lsbmask;
286
287	uint64_t refs;
288	uint64_t misses;
289
290	int level_id_bits;
291
292	void Report(FILE *fp) {
293	fprintf(fp, "\nValuecache %s report:\n", name);
294	fprintf(fp, "Refs %lld Misses %lld (%0.4f%%/ref)\n", refs, misses, misses*100.0/refs);
295
296	uint64_t rawcost = misses * (64 + level_id_bits);
297
298	uint64_t cost = 0;
299	int i;
300	for (i=0; i<nlevels; i++) {
301	modules[i]->cost = modules[i]->lsbits + nbits(modules[i]->size-1);
302	modules[i]->levelcost = (modules[i]->refs-modules[i]->misses) * (modules[i]->cost + level_id_bits);
303	cost += modules[i]->levelcost;
304	}
305	cost += rawcost;
306
307	uint64_t incr_cost = 0;
308	for (i=0; i<nlevels; i++) {
309	fprintf(fp, "level %d: Refs %lld Misses %lld (%0.4f%%/local-ref, %0.4f%%/ref)\n", i, modules[i]->refs, modules[i]->misses,
310	modules[i]->misses100.0/modules[i]->refs, modules[i]->misses100.0/refs);
311	uint64_t levelcost = modules[i]->levelcost;
312	incr_cost += levelcost;
313	fprintf(fp, " cost = %lld hits * (%d idxlsb + %d lvl bits) = %lld [%lld] (%0.4f/ref) %0.4f%% of total\n",
314	(modules[i]->refs-modules[i]->misses), modules[i]->cost, level_id_bits, levelcost, incr_cost, levelcost1.0/refs, levelcost100.0/cost);
315	}
316
317	fprintf(fp, "cost of raw ea: %lld * (64 + %d id-bits) = %lld %0.4f%% of total\n", misses, level_id_bits, rawcost, rawcost*100.0/cost);
318
319	fprintf(fp, "Total cost: %lld (%0.4f bits/ref)\n", cost, cost*1.0/refs);
320
321	}
322
323
324	static int nbits(uint64_t n) {
325	int rv = 1;
326	while(n>>rv) {
327	rv++;
328	}
329	return rv;
330	}
331
332	}; // struct valuecache
333
334
335
336	#endif // _rz3_valuecache_h_