mem-cache: Stub compression framework

Create a stub of a compression framework where we can have
multiple data blocks per tag entry. Only consecutive blocks
can share a tag as of now.

For each tag entry there can be multiple data blocks. We have
the same number of tags a conventional cache would have, but
we instantiate the maximum number of data blocks (according to
the compression ratio) per tag, to virtually implement
compression without increasing the complexity of the simulator.

Change-Id: I549940c7afb2f744ab293ff8bb283967e7551a11
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/10763
Tested-by: kokoro <noreply+kokoro@google.com>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>

9 files changed, 386 insertions, 10 deletions

diff --git a/src/mem/cache/tags/SConscript b/src/mem/cache/tags/SConscript
index c654bf2eb..324f938d6 100644
--- a/src/mem/cache/tags/SConscript
+++ b/src/mem/cache/tags/SConscript
@@ -34,6 +34,8 @@ SimObject('Tags.py')
 
 Source('base.cc')
 Source('base_set_assoc.cc')
+Source('compressed_tags.cc')
 Source('fa_lru.cc')
 Source('sector_blk.cc')
 Source('sector_tags.cc')
+Source('super_blk.cc')
diff --git a/src/mem/cache/tags/Tags.py b/src/mem/cache/tags/Tags.py
index 9ac240d13..476536660 100644
--- a/src/mem/cache/tags/Tags.py
+++ b/src/mem/cache/tags/Tags.py
@@ -101,6 +101,21 @@ class SectorTags(BaseTags):
     replacement_policy = Param.BaseReplacementPolicy(
         Parent.replacement_policy, "Replacement policy")
 
+class CompressedTags(SectorTags):
+    type = 'CompressedTags'
+    cxx_header = "mem/cache/tags/compressed_tags.hh"
+
+    # Maximum number of compressed blocks per tag
+    max_compression_ratio = Param.Int(2,
+        "Maximum number of compressed blocks per tag.")
+
+    # We simulate superblock as sector blocks
+    num_blocks_per_sector = Self.max_compression_ratio
+
+    # We virtually increase the number of data blocks per tag by multiplying
+    # the cache size by the compression ratio
+    size = Parent.size * Self.max_compression_ratio
+
 class FALRU(BaseTags):
     type = 'FALRU'
     cxx_class = 'FALRU'
diff --git a/src/mem/cache/tags/compressed_tags.cc b/src/mem/cache/tags/compressed_tags.cc
new file mode 100644
index 000000000..cc799df24
--- /dev/null
+++ b/src/mem/cache/tags/compressed_tags.cc
@@ -0,0 +1,118 @@
+/*
+ * Copyright (c) 2018 Inria
+ * 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: Daniel Carvalho
+ */
+
+/**
+ * @file
+ * Definitions of a base set associative compressed superblocks tag store.
+ */
+
+#include "mem/cache/tags/compressed_tags.hh"
+
+#include "mem/cache/replacement_policies/base.hh"
+#include "mem/cache/tags/indexing_policies/base.hh"
+#include "params/CompressedTags.hh"
+
+CompressedTags::CompressedTags(const Params *p)
+    : SectorTags(p)
+{
+}
+
+void
+CompressedTags::tagsInit()
+{
+    // Create blocks and superblocks
+    blks = std::vector<CompressionBlk>(numBlocks);
+    superBlks = std::vector<SuperBlk>(numSectors);
+
+    // Initialize all blocks
+    unsigned blk_index = 0;          // index into blks array
+    for (unsigned superblock_index = 0; superblock_index < numSectors;
+         superblock_index++)
+    {
+        // Locate next cache superblock
+        SuperBlk* superblock = &superBlks[superblock_index];
+
+        // Link block to indexing policy
+        indexingPolicy->setEntry(superblock, superblock_index);
+
+        // Associate a replacement data entry to the block
+        superblock->replacementData = replacementPolicy->instantiateEntry();
+
+        // Initialize all blocks in this superblock
+        superblock->blks.resize(numBlocksPerSector, nullptr);
+        for (unsigned k = 0; k < numBlocksPerSector; ++k){
+            // Select block within the set to be linked
+            SectorSubBlk*& blk = superblock->blks[k];
+
+            // Locate next cache block
+            blk = &blks[blk_index];
+
+            // Associate a data chunk to the block
+            blk->data = &dataBlks[blkSize*blk_index];
+
+            // Associate superblock to this block
+            blk->setSectorBlock(superblock);
+
+            // Associate the superblock replacement data to this block
+            blk->replacementData = superblock->replacementData;
+
+            // Set its index and sector offset
+            blk->setSectorOffset(k);
+
+            // Update block index
+            ++blk_index;
+        }
+    }
+}
+
+void
+CompressedTags::forEachBlk(std::function<void(CacheBlk &)> visitor)
+{
+    for (CompressionBlk& blk : blks) {
+        visitor(blk);
+    }
+}
+
+bool
+CompressedTags::anyBlk(std::function<bool(CacheBlk &)> visitor)
+{
+    for (CompressionBlk& blk : blks) {
+        if (visitor(blk)) {
+            return true;
+        }
+    }
+    return false;
+}
+
+CompressedTags *
+CompressedTagsParams::create()
+{
+    return new CompressedTags(this);
+}
diff --git a/src/mem/cache/tags/compressed_tags.hh b/src/mem/cache/tags/compressed_tags.hh
new file mode 100644
index 000000000..0bf96b55e
--- /dev/null
+++ b/src/mem/cache/tags/compressed_tags.hh
@@ -0,0 +1,121 @@
+/*
+ * Copyright (c) 2018 Inria
+ * 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: Daniel Carvalho
+ */
+
+/**
+ * @file
+ * Declaration of a compressed set associative tag store using superblocks.
+ */
+
+#ifndef __MEM_CACHE_TAGS_COMPRESSED_TAGS_HH__
+#define __MEM_CACHE_TAGS_COMPRESSED_TAGS_HH__
+
+#include <vector>
+
+#include "mem/cache/tags/sector_tags.hh"
+#include "mem/cache/tags/super_blk.hh"
+
+class BaseCache;
+struct CompressedTagsParams;
+
+/**
+ * A CompressedTags cache tag store.
+ * @sa  \ref gem5MemorySystem "gem5 Memory System"
+ *
+ * The Compression Ratio (CR) of a superblock is defined by
+ *     CR = uncompressed_size / compressed_size.
+ *
+ * The CompressedTags placement policy divides the cache into s sets of w
+ * superblocks (ways). Each superblock can then contain up to CR compressed
+ * blocks.
+ *
+ * For each tag entry there can be multiple data blocks. We have the same
+ * number of tags a conventional cache would have, but we instantiate the
+ * maximum number of data blocks (according to the compression ratio) per
+ * 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.
+ */
+class CompressedTags : public SectorTags
+{
+  private:
+    /** The cache blocks. */
+    std::vector<CompressionBlk> blks;
+    /** The cache superblocks. */
+    std::vector<SuperBlk> superBlks;
+
+  public:
+    /** Convenience typedef. */
+     typedef CompressedTagsParams Params;
+
+    /**
+     * Construct and initialize this tag store.
+     */
+    CompressedTags(const Params *p);
+
+    /**
+     * Destructor.
+     */
+    virtual ~CompressedTags() {};
+
+    /**
+     * Initialize blocks as SuperBlk and CompressionBlk instances.
+     */
+    void tagsInit() override;
+
+    /**
+     * Visit each sub-block in the tags and apply a visitor.
+     *
+     * The visitor should be a std::function that takes a cache block.
+     * reference as its parameter.
+     *
+     * @param visitor Visitor to call on each block.
+     */
+    void forEachBlk(std::function<void(CacheBlk &)> visitor) override;
+
+    /**
+     * Find if any of the sub-blocks satisfies a condition.
+     *
+     * The visitor should be a std::function that takes a cache block
+     * reference as its parameter. The visitor will terminate the
+     * traversal early if the condition is satisfied.
+     *
+     * @param visitor Visitor to call on each block.
+     */
+    bool anyBlk(std::function<bool(CacheBlk &)> visitor) override;
+};
+
+#endif //__MEM_CACHE_TAGS_COMPRESSED_TAGS_HH__
diff --git a/src/mem/cache/tags/sector_blk.hh b/src/mem/cache/tags/sector_blk.hh
index 264836ca2..ca0d9a806 100644
--- a/src/mem/cache/tags/sector_blk.hh
+++ b/src/mem/cache/tags/sector_blk.hh
@@ -49,7 +49,7 @@ class SectorBlk;
  */
 class SectorSubBlk : public CacheBlk
 {
-  private:
+  protected:
     /**
      * Sector block associated to this block.
      */
@@ -144,7 +144,7 @@ class SectorSubBlk : public CacheBlk
  */
 class SectorBlk : public ReplaceableEntry
 {
-  private:
+  protected:
     /**
      * Sector tag value. A sector's tag is the tag of all its sub-blocks.
      */
diff --git a/src/mem/cache/tags/sector_tags.cc b/src/mem/cache/tags/sector_tags.cc
index 0cd73719e..06093e997 100644
--- a/src/mem/cache/tags/sector_tags.cc
+++ b/src/mem/cache/tags/sector_tags.cc
@@ -52,9 +52,8 @@ SectorTags::SectorTags(const SectorTagsParams *p)
       sequentialAccess(p->sequential_access),
       replacementPolicy(p->replacement_policy),
       numBlocksPerSector(p->num_blocks_per_sector),
-      numSectors(numBlocks / p->num_blocks_per_sector), blks(numBlocks),
-      secBlks(numSectors), sectorShift(floorLog2(blkSize)),
-      sectorMask(numBlocksPerSector - 1)
+      numSectors(numBlocks / numBlocksPerSector),
+      sectorShift(floorLog2(blkSize)), sectorMask(numBlocksPerSector - 1)
 {
     // Check parameters
     fatal_if(blkSize < 4 || !isPowerOf2(blkSize),
@@ -66,6 +65,10 @@ SectorTags::SectorTags(const SectorTagsParams *p)
 void
 SectorTags::tagsInit()
 {
+    // Create blocks and sector blocks
+    blks = std::vector<SectorSubBlk>(numBlocks);
+    secBlks = std::vector<SectorBlk>(numSectors);
+
     // Initialize all blocks
     unsigned blk_index = 0;       // index into blks array
     for (unsigned sec_blk_index = 0; sec_blk_index < numSectors;
diff --git a/src/mem/cache/tags/sector_tags.hh b/src/mem/cache/tags/sector_tags.hh
index 8e389a6a6..84c721ef7 100644
--- a/src/mem/cache/tags/sector_tags.hh
+++ b/src/mem/cache/tags/sector_tags.hh
@@ -57,6 +57,12 @@ class ReplaceableEntry;
  */
 class SectorTags : public BaseTags
 {
+  private:
+    /** The cache blocks. */
+    std::vector<SectorSubBlk> blks;
+    /** The cache sector blocks. */
+    std::vector<SectorBlk> secBlks;
+
   protected:
     /** The allocatable associativity of the cache (alloc mask). */
     unsigned allocAssoc;
@@ -73,11 +79,6 @@ class SectorTags : public BaseTags
     /** The number of sectors in the cache. */
     const unsigned numSectors;
 
-    /** The cache blocks. */
-    std::vector<SectorSubBlk> blks;
-    /** The cache sector blocks. */
-    std::vector<SectorBlk> secBlks;
-
     // Organization of an address:
     // Tag | Placement Location | Sector Offset # | Offset #
     /** The amount to shift the address to get the sector tag. */
diff --git a/src/mem/cache/tags/super_blk.cc b/src/mem/cache/tags/super_blk.cc
new file mode 100644
index 000000000..3e8835625
--- /dev/null
+++ b/src/mem/cache/tags/super_blk.cc
@@ -0,0 +1,44 @@
+/**
+ * Copyright (c) 2018 Inria
+ * 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: Daniel Carvalho
+ */
+
+/** @file
+ * Implementation of a simple superblock class. Each superblock consists of a
+ * number of compressed cache blocks limited by the maximum compression factor
+ * that may or may not be present in the cache.
+ */
+
+#include "mem/cache/tags/super_blk.hh"
+
+#include "base/logging.hh"
+
+CompressionBlk::CompressionBlk()
+    : SectorSubBlk()
+{
+}
diff --git a/src/mem/cache/tags/super_blk.hh b/src/mem/cache/tags/super_blk.hh
new file mode 100644
index 000000000..45c7f1a66
--- /dev/null
+++ b/src/mem/cache/tags/super_blk.hh
@@ -0,0 +1,72 @@
+/**
+ * Copyright (c) 2018 Inria
+ * 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: Daniel Carvalho
+ */
+
+/** @file
+ * Definition of a simple superblock class. Each superblock consists of a
+ * number of compressed cache blocks limited by the maximum compression
+ * factor that may or may not be present in the cache.
+ */
+
+#ifndef __MEM_CACHE_TAGS_SUPER_BLK_HH__
+#define __MEM_CACHE_TAGS_SUPER_BLK_HH__
+
+#include "mem/cache/tags/sector_blk.hh"
+
+class SuperBlk;
+
+/**
+ * A superblock is composed of sub-blocks, and each sub-block has information
+ * regarding its superblock and a pointer to its superblock tag. A superblock
+ * can be seen as a variation of a sector block, and therefore we use a sector
+ * nomenclature.
+ */
+class CompressionBlk : public SectorSubBlk
+{
+  public:
+    CompressionBlk();
+    CompressionBlk(const CompressionBlk&) = delete;
+    CompressionBlk& operator=(const CompressionBlk&) = delete;
+    ~CompressionBlk() {};
+};
+
+/**
+ * A basic compression superblock.
+ * Contains the tag and a list of blocks associated to this superblock.
+ */
+class SuperBlk : public SectorBlk
+{
+  public:
+    SuperBlk() : SectorBlk() {}
+    SuperBlk(const SuperBlk&) = delete;
+    SuperBlk& operator=(const SuperBlk&) = delete;
+    ~SuperBlk() {};
+};
+
+#endif //__MEM_CACHE_TAGS_SUPER_BLK_HH__