Daniel Carvalho has uploaded this change for review. (
https://gem5-review.googlesource.com/c/public/gem5/+/36581 )
Change subject: mem-cache: Use the compression factor to co-allocate
......................................................................
mem-cache: Use the compression factor to co-allocate
The compression factor of a block is measured according to the maximum
achievable compression ratio.
For example, if up to 4 blocks can co-allocate in a superblock, and
a cache line has 512 bits, the possible compression factors are 1
(uncompressed, <=512 bits), 2 (compressed, <=256 bits), 4 (compressed,
<=128 bits).
This is an approach similar to the one described in "Yet Another
Compressed Cache", by Sardashti et al.
Change-Id: I52ef36989f3eeef6fc8890132a57f995ef9c5258
Signed-off-by: Daniel R. Carvalho <[email protected]>
---
M src/mem/cache/tags/compressed_tags.hh
M src/mem/cache/tags/super_blk.cc
M src/mem/cache/tags/super_blk.hh
3 files changed, 99 insertions(+), 18 deletions(-)
diff --git a/src/mem/cache/tags/compressed_tags.hh
b/src/mem/cache/tags/compressed_tags.hh
index 306acd5..e391538 100644
--- a/src/mem/cache/tags/compressed_tags.hh
+++ b/src/mem/cache/tags/compressed_tags.hh
@@ -60,10 +60,6 @@
* tag, to virtually implement compression without increasing the
complexity
* of the simulator.
*
- * This is a simple implementation of cache compression, where superblocks
- * can only have at most numBlocksPerSector compressed blocks, each
compressed
- * to at least (100/numBlocksPerSector)% of its size.
- *
* numBlocksPerSector holds the maximum number of blocks a superblock with
* the best possible compression factor would hold. It is equivalent to CR
* from the previous definition.
diff --git a/src/mem/cache/tags/super_blk.cc
b/src/mem/cache/tags/super_blk.cc
index 8623765..9325a69 100644
--- a/src/mem/cache/tags/super_blk.cc
+++ b/src/mem/cache/tags/super_blk.cc
@@ -34,7 +34,10 @@
#include "mem/cache/tags/super_blk.hh"
-#include "base/logging.hh"
+#include <climits>
+#include <cmath>
+
+#include "base/bitfield.hh"
CompressionBlk::CompressionBlk()
: SectorSubBlk(), _size(0), _decompressionLatency(0),
_compressed(false)
@@ -95,6 +98,9 @@
_size = size;
SuperBlk* superblock = static_cast<SuperBlk*>(getSectorBlock());
+ const uint8_t compression_factor =
+ superblock->calculateCompressionFactor(size);
+ superblock->setCompressionFactor(compression_factor);
// Either this function is called after an insertion, or an update.
// If somebody else is present in the block, keep the superblock's
@@ -102,7 +108,7 @@
const uint8_t num_valid = superblock->getNumValid();
assert(num_valid >= 1);
if (num_valid == 1) {
- if (superblock->canCoAllocate(size)) {
+ if (compression_factor != 1) {
setCompressed();
} else {
setUncompressed();
@@ -138,16 +144,17 @@
int
CompressionBlk::checkExpansionContraction(const std::size_t size) const
{
- // @todo As of now only two states are supported: compressed to its
- // maximum compression, and uncompressed. Support for intermediate
- // states (e.g., if MaxCR=4, 2/4 and 3/4 of the blkSize) should be
added
+ // An expansion happens when a block passes from a compressible state
+ // to a less compressible state (e.g., blkSize/4 to (blkSize/2 or
blkSize),
+ // or blkSize/2 to blkSize). A contraction happens when a block passes
+ // from a less compressible state to a more compressible state (i.e.,
the
+ // opposite of expansion)
const SuperBlk* superblock =
static_cast<const SuperBlk*>(getSectorBlock());
- const bool prev_compressed = isCompressed();
- const bool new_compressed = superblock->canCoAllocate(size);
+ const uint8_t prev_cf = superblock->getCompressionFactor();
+ const uint8_t new_cf = superblock->calculateCompressionFactor(size);
// Expansion: 1. Contraction: -1. Same size: 0.
- return (prev_compressed == new_compressed) ? 0 :
- ((prev_compressed & !new_compressed) ? 1 : -1);
+ return (new_cf < prev_cf) ? 1 : ((new_cf > prev_cf) ? -1 : 0);
}
std::string
@@ -158,6 +165,18 @@
getDecompressionLatency());
}
+SuperBlk::SuperBlk()
+ : SectorBlk(), blkSize(0), compressionFactor(1)
+{
+}
+
+void
+SuperBlk::invalidate()
+{
+ SectorBlk::invalidate();
+ compressionFactor = 1;
+}
+
bool
SuperBlk::isCompressed(const CompressionBlk* ignored_blk) const
{
@@ -174,10 +193,11 @@
bool
SuperBlk::canCoAllocate(const std::size_t compressed_size) const
{
- // Simple co-allocation function: at most numBlocksPerSector blocks
that
- // compress at least to (100/numBlocksPerSector)% of their original
size
- // can share a superblock
- return (compressed_size <= (blkSize * 8) / blks.size());
+ // A YACC-like (Sardashti et al., 2016) co-allocation function: at most
+ // numBlocksPerSector blocks that compress at least to fit in the space
+ // allocated by its compression factor can share a superblock
+ return (getNumValid() < getCompressionFactor()) &&
+ (compressed_size <= (blkSize * CHAR_BIT) / getCompressionFactor());
}
void
@@ -186,3 +206,31 @@
assert(blkSize == 0);
blkSize = blk_size;
}
+
+uint8_t
+SuperBlk::calculateCompressionFactor(const std::size_t size) const
+{
+ // The number of blocks per sector determines the maximum comp factor.
+ // If the compressed size is worse than the uncompressed size, we
assume
+ // the size is the uncompressed size, and thus the compression factor
is 1
+ const std::size_t compression_factor = (size > (CHAR_BIT * blkSize)) ?
1 :
+ alignToPowerOfTwo(std::floor(double(CHAR_BIT * blkSize) / size));
+ return std::min(compression_factor, blks.size());
+}
+
+uint8_t
+SuperBlk::getCompressionFactor() const
+{
+ return compressionFactor;
+}
+
+void
+SuperBlk::setCompressionFactor(const uint8_t compression_factor)
+{
+ // Either the block is alone, in which case the compression factor
+ // must be set, or it co-allocates with someone with a worse or
+ // equal compression factor, in which case it should not be updated
+ if (getNumValid() <= 1) {
+ compressionFactor = compression_factor;
+ }
+}
diff --git a/src/mem/cache/tags/super_blk.hh
b/src/mem/cache/tags/super_blk.hh
index 6c7c727..c262f83 100644
--- a/src/mem/cache/tags/super_blk.hh
+++ b/src/mem/cache/tags/super_blk.hh
@@ -156,8 +156,15 @@
/** Block size, in bytes. */
std::size_t blkSize;
+ /**
+ * Superblock's compression factor. It is aligned to be a power of two,
+ * limited by the maximum compression ratio, and calculated as:
+ * compressionFactor = uncompressedSize/compressedSize
+ */
+ uint8_t compressionFactor;
+
public:
- SuperBlk() : SectorBlk(), blkSize(0) {}
+ SuperBlk();
SuperBlk(const SuperBlk&) = delete;
SuperBlk& operator=(const SuperBlk&) = delete;
~SuperBlk() {};
@@ -185,6 +192,36 @@
* @param blk_size The uncompressed block size.
*/
void setBlkSize(const std::size_t blk_size);
+
+ /**
+ * Calculate the compression factor (cf) given a compressed size and
the
+ * maximum compression ratio. Therefore cf is:
+ * 1 if comp_size > blk_size/2,
+ * 2 if comp_size > blk_size/4,
+ * 4 if comp_size > blk_size/8,
+ * 8 if comp_size > blk_size/16,
+ * and so on.
+ *
+ * @param size The compressed size.
+ * @return Compression factor corresponding to the size.
+ */
+ uint8_t calculateCompressionFactor(const std::size_t size) const;
+
+ /**
+ * Get the compression factor of this superblock.
+ *
+ * @return The compression factor.
+ */
+ uint8_t getCompressionFactor() const;
+
+ /**
+ * Set the compression factor of this superblock.
+ *
+ * @param compression_factor The new compression factor.
+ */
+ void setCompressionFactor(const uint8_t compression_factor);
+
+ void invalidate() override;
};
#endif //__MEM_CACHE_TAGS_SUPER_BLK_HH__
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/36581
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: develop
Gerrit-Change-Id: I52ef36989f3eeef6fc8890132a57f995ef9c5258
Gerrit-Change-Number: 36581
Gerrit-PatchSet: 1
Gerrit-Owner: Daniel Carvalho <[email protected]>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list -- [email protected]
To unsubscribe send an email to [email protected]
%(web_page_url)slistinfo%(cgiext)s/%(_internal_name)s
