From c8f3ff5e183273c2ba7a69dc53f01e5f9c14c9cb Mon Sep 17 00:00:00 2001 From: "Daniel R. Carvalho" Date: Wed, 5 Jun 2019 11:27:46 +0200 Subject: [PATCH] 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 Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/36581 Reviewed-by: Nikos Nikoleris Maintainer: Nikos Nikoleris Tested-by: kokoro --- src/mem/cache/tags/compressed_tags.hh | 4 -- src/mem/cache/tags/super_blk.cc | 78 ++++++++++++++++++++++----- src/mem/cache/tags/super_blk.hh | 39 +++++++++++++- 3 files changed, 102 insertions(+), 19 deletions(-) diff --git a/src/mem/cache/tags/compressed_tags.hh b/src/mem/cache/tags/compressed_tags.hh index 306acd5b7..e391538de 100644 --- a/src/mem/cache/tags/compressed_tags.hh +++ b/src/mem/cache/tags/compressed_tags.hh @@ -60,10 +60,6 @@ struct CompressedTagsParams; * 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 09bb2073f..d81cbc313 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 +#include + +#include "base/bitfield.hh" CompressionBlk::CompressionBlk() : SectorSubBlk(), _size(0), _decompressionLatency(0), _compressed(false) @@ -95,6 +98,9 @@ CompressionBlk::setSizeBits(const std::size_t size) _size = size; SuperBlk* superblock = static_cast(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 @@ CompressionBlk::setSizeBits(const std::size_t size) 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 @@ CompressionBlk::invalidate() CompressionBlk::OverwriteType 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(getSectorBlock()); - const bool prev_compressed = isCompressed(); - const bool new_compressed = superblock->canCoAllocate(size); - return (prev_compressed == new_compressed) ? UNCHANGED : - ((prev_compressed & !new_compressed) ? DATA_EXPANSION : - DATA_CONTRACTION); + const uint8_t prev_cf = superblock->getCompressionFactor(); + const uint8_t new_cf = superblock->calculateCompressionFactor(size); + return (new_cf < prev_cf) ? DATA_EXPANSION : + ((new_cf > prev_cf) ? DATA_CONTRACTION : UNCHANGED); } std::string @@ -158,6 +165,18 @@ CompressionBlk::print() const 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 @@ SuperBlk::isCompressed(const CompressionBlk* ignored_blk) const 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,33 @@ SuperBlk::setBlkSize(const std::size_t blk_size) 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 blk_size_bits = CHAR_BIT * blkSize; + const std::size_t compression_factor = (size > blk_size_bits) ? 1 : + ((size == 0) ? blk_size_bits : + alignToPowerOfTwo(std::floor(double(blk_size_bits) / 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 354b3f540..d98c14e19 100644 --- a/src/mem/cache/tags/super_blk.hh +++ b/src/mem/cache/tags/super_blk.hh @@ -170,8 +170,15 @@ class SuperBlk : public SectorBlk /** 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() {}; @@ -199,6 +206,36 @@ class SuperBlk : public SectorBlk * @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__ -- 2.30.2