1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
|
/*
* Copyright (c) 2002-2005 The Regents of The University of Michigan
* 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.
*
* Authors: Erik Hallnor
*/
/**
* @file
* Declaration of the Indirect Index Cache (IIC) tags store.
*/
#ifndef __IIC_HH__
#define __IIC_HH__
#include <list>
#include <vector>
#include "mem/cache/blk.hh"
#include "mem/cache/tags/iic_repl/repl.hh"
#include "mem/packet.hh"
#include "base/statistics.hh"
#include "mem/cache/tags/base.hh"
class BaseCache; // Forward declaration
/**
* IIC cache blk.
*/
class IICTag : public CacheBlk
{
public:
/**
* Copy the contents of the given IICTag into this one.
* @param rhs The tag to copy.
* @return const reference to this tag.
*/
const IICTag& operator=(const IICTag& rhs)
{
CacheBlk::operator=(rhs);
chain_ptr = rhs.chain_ptr;
re = rhs.re;
set = rhs.set;
trivialData = rhs.trivialData;
numData = rhs.numData;
data_ptr.clear();
for (int i = 0; i < rhs.numData; ++i) {
data_ptr.push_back(rhs.data_ptr[i]);
}
return *this;
}
/** Hash chain pointer into secondary store. */
unsigned long chain_ptr;
/** Data array pointers for each subblock. */
std::vector<unsigned long> data_ptr;
/** Replacement Entry pointer. */
void *re;
/**
* An array to store small compressed data. Conceputally the same size
* as the unsused data array pointers.
*/
uint8_t *trivialData;
/**
* The number of allocated subblocks.
*/
int numData;
};
/**
* A hash set for the IIC primary lookup table.
*/
class IICSet{
public:
/** The associativity of the primary table. */
int assoc;
/** The number of hash chains followed when finding the last block. */
int depth;
/** The current number of blocks on the chain. */
int size;
/** Tag pointer into the secondary tag storage. */
unsigned long chain_ptr;
/** The LRU list of the primary table. MRU is at 0 index. */
IICTag ** tags;
/**
* Find the addr in this set, return the chain pointer to the secondary if
* it isn't found.
* @param asid The address space ID.
* @param tag The address to find.
* @param chain_ptr The chain pointer to start the search of the secondary
* @return Pointer to the tag, NULL if not found.
*/
IICTag* findTag( Addr tag, unsigned long &chain_ptr)
{
depth = 1;
for (int i = 0; i < assoc; ++i) {
if (tags[i]->tag == tag && tags[i]->isValid()) {
return tags[i];
}
}
chain_ptr = this->chain_ptr;
return 0;
}
/**
* Find an usused tag in this set.
* @return Pointer to the unused tag, NULL if none are free.
*/
IICTag* findFree()
{
for (int i = 0; i < assoc; ++i) {
if (!tags[i]->isValid()) {
return tags[i];
}
}
return 0;
}
/**
* Move a tag to the head of the LRU list
* @param tag The tag to move.
*/
void moveToHead(IICTag *tag);
/**
* Move a tag to the tail (LRU) of the LRU list
* @param tag The tag to move.
*/
void moveToTail(IICTag *tag);
};
/**
* The IIC tag store. This is a hardware-realizable, fully-associative tag
* store that uses software replacement, e.g. Gen.
*/
class IIC : public BaseTags
{
public:
/** Typedef of the block type used in this class. */
typedef IICTag BlkType;
/** Typedef for list of pointers to the local block type. */
typedef std::list<IICTag*> BlkList;
protected:
/** The number of set in the primary table. */
const int hashSets;
/** The block size in bytes. */
const int blkSize;
/** The associativity of the primary table. */
const int assoc;
/** The base hit latency. */
const int hitLatency;
/** The subblock size, used for compression. */
const int subSize;
/** The number of subblocks */
const int numSub;
/** The number of bytes used by data pointers */
const int trivialSize;
/** The amount to shift address to get the tag. */
const int tagShift;
/** The mask to get block offset bits. */
const unsigned blkMask;
/** The amount to shift to get the subblock number. */
const int subShift;
/** The mask to get the correct subblock number. */
const unsigned subMask;
/** The latency of a hash lookup. */
const int hashDelay;
/** The number of data blocks. */
const int numBlocks;
/** The total number of tags in primary and secondary. */
const int numTags;
/** The number of tags in the secondary tag store. */
const int numSecondary;
/** The Null tag pointer. */
const int tagNull;
/** The last tag in the primary table. */
const int primaryBound;
/** All of the tags */
IICTag *tagStore;
/**
* Pointer to the head of the secondary freelist (maintained with chain
* pointers.
*/
unsigned long freelist;
/**
* The data block freelist.
*/
std::list<unsigned long> blkFreelist;
/** The primary table. */
IICSet *sets;
/** The replacement policy. */
Repl *repl;
/** An array of data reference counters. */
int *dataReferenceCount;
/** The data blocks. */
uint8_t *dataStore;
/** Storage for the fast access data of each cache block. */
uint8_t **dataBlks;
/**
* Count of the current number of free secondary tags.
* Used for debugging.
*/
int freeSecond;
// IIC Statistics
/**
* @addtogroup IICStatistics IIC Statistics
* @{
*/
/** Hash hit depth of cache hits. */
Stats::Distribution<> hitHashDepth;
/** Hash depth for cache misses. */
Stats::Distribution<> missHashDepth;
/** Count of accesses to each hash set. */
Stats::Distribution<> setAccess;
/** The total hash depth for every miss. */
Stats::Scalar<> missDepthTotal;
/** The total hash depth for all hits. */
Stats::Scalar<> hitDepthTotal;
/** The number of hash misses. */
Stats::Scalar<> hashMiss;
/** The number of hash hits. */
Stats::Scalar<> hashHit;
/** @} */
public:
/**
* Collection of parameters for the IIC.
*/
class Params {
public:
/** The size in bytes of the cache. */
int size;
/** The number of sets in the primary table. */
int numSets;
/** The block size in bytes. */
int blkSize;
/** The associativity of the primary table. */
int assoc;
/** The number of cycles for each hash lookup. */
int hashDelay;
/** The number of cycles to read the data. */
int hitLatency;
/** The replacement policy. */
Repl *rp;
/** The subblock size in bytes. */
int subblockSize;
};
/**
* Construct and initialize this tag store.
* @param params The IIC parameters.
* @todo
* Should make a way to have less tags in the primary than blks in the
* cache. Also should be able to specify number of secondary blks.
*/
IIC(Params ¶ms);
/**
* Destructor.
*/
virtual ~IIC();
/**
* Register the statistics.
* @param name The name to prepend to the statistic descriptions.
*/
void regStats(const std::string &name);
/**
* Regenerate the block address from the tag.
* @param tag The tag of the block.
* @param set Not needed for the iic.
* @return The block address.
*/
Addr regenerateBlkAddr(Addr tag, int set) {
return (((Addr)tag << tagShift));
}
/**
* Return the block size.
* @return The block size.
*/
int getBlockSize()
{
return blkSize;
}
/**
* Return the subblock size.
* @return The subblock size.
*/
int getSubBlockSize()
{
return subSize;
}
/**
* Return the hit latency.
* @return the hit latency.
*/
int getHitLatency() const
{
return hitLatency;
}
/**
* Generate the tag from the address.
* @param addr The address to a get a tag for.
* @return the tag.
*/
Addr extractTag(Addr addr) const
{
return (addr >> tagShift);
}
/**
* Return the set, always 0 for IIC.
* @return 0.
*/
int extractSet(Addr addr) const
{
return 0;
}
/**
* Get the block offset of an address.
* @param addr The address to get the offset of.
* @return the block offset of the address.
*/
int extractBlkOffset(Addr addr) const
{
return (addr & blkMask);
}
/**
* Align an address to the block size.
* @param addr the address to align.
* @return The block address.
*/
Addr blkAlign(Addr addr) const
{
return (addr & ~(Addr)blkMask);
}
/**
* Swap the position of two tags.
* @param index1 The first tag location.
* @param index2 The second tag location.
*/
void tagSwap(unsigned long index1, unsigned long index2);
/**
* Clear the reference bit of the tag and return its old value.
* @param index The pointer of the tag to manipulate.
* @return The previous state of the reference bit.
*/
bool clearRef(unsigned long index)
{
bool tmp = tagStore[index].isReferenced();
tagStore[index].status &= ~BlkReferenced;
return tmp;
}
/**
* Invalidate a block.
* @param blk The block to invalidate.
*/
void invalidateBlk(BlkType *blk);
/**
* Access block and update replacement data. May not succeed, in which case
* NULL pointer is returned. This has all the implications of a cache
* access and should only be used as such.
* Returns the access latency and inCache flags as a side effect.
* @param addr The address to find.
* @param asid The address space ID.
* @param lat The access latency.
* @return A pointer to the block found, if any.
*/
IICTag* accessBlock(Addr addr, int &lat);
/**
* Find the block, do not update the replacement data.
* @param addr The address to find.
* @param asid The address space ID.
* @return A pointer to the block found, if any.
*/
IICTag* findBlock(Addr addr) const;
/**
* Find a replacement block for the address provided.
* @param pkt The request to a find a replacement candidate for.
* @param writebacks List for any writebacks to be performed.
* @return The block to place the replacement in.
*/
IICTag* findReplacement(Addr addr, PacketList &writebacks);
/**
* Read the data from the internal storage of the given cache block.
* @param blk The block to read the data from.
* @param data The buffer to read the data into.
* @return The cache block's data.
*/
void readData(IICTag *blk, uint8_t *data);
/**
* Write the data into the internal storage of the given cache block.
* @param blk The block to write to.
* @param data The data to write.
* @param size The number of bytes to write.
* @param writebacks A list for any writebacks to be performed. May be
* needed when writing to a compressed block.
*/
void writeData(IICTag *blk, uint8_t *data, int size,
PacketList & writebacks);
/**
* Called at end of simulation to complete average block reference stats.
*/
virtual void cleanupRefs();
private:
/**
* Return the hash of the address.
* @param addr The address to hash.
* @return the hash of the address.
*/
unsigned hash(Addr addr) const;
/**
* Search for a block in the secondary tag store. Returns the number of
* hash lookups as a side effect.
* @param asid The address space ID.
* @param tag The tag to match.
* @param chain_ptr The first entry to search.
* @param depth The number of hash lookups made while searching.
* @return A pointer to the block if found.
*/
IICTag *secondaryChain(Addr tag, unsigned long chain_ptr,
int *depth) const;
/**
* Free the resources associated with the next replacement block.
* @param writebacks A list of any writebacks to perform.
*/
void freeReplacementBlock(PacketList & writebacks);
/**
* Return the pointer to a free data block.
* @param writebacks A list of any writebacks to perform.
* @return A pointer to a free data block.
*/
unsigned long getFreeDataBlock(PacketList & writebacks);
/**
* Get a free tag in the given hash set.
* @param set The hash set to search.
* @param writebacks A list of any writebacks to perform.
* @return a pointer to a free tag.
*/
IICTag* getFreeTag(int set, PacketList & writebacks);
/**
* Free the resources associated with the given tag.
* @param tag_ptr The tag to free.
*/
void freeTag(IICTag *tag_ptr);
/**
* Mark the given data block as being available.
* @param data_ptr The data block to free.
*/
void freeDataBlock(unsigned long data_ptr);
};
#endif // __IIC_HH__
|