Daniel Carvalho has uploaded this change for review. (
https://gem5-review.googlesource.com/11105
Change subject: mem-cache: Create CPack compressor
......................................................................
mem-cache: Create CPack compressor
Implementation of C-Pack, as described in "C-Pack: A High-
Performance Microprocessor Cache Compression Algorithm".
C-Pack uses pattern matching schemes to detect and compress
frequently appearing data patterns. As in the original paper,
it divides the input in 32-bit words, and uses 6 patterns to
match with its dictionary.
For the patterns, each letter represents a byte: Z is a null
byte, M is a dictionary match, X is a new value. The patterns
are ZZZZ, XXXX, MMMM, MMXX, ZZZX, MMMX.
Change-Id: I2efc9db2c862620dcc1155300e39be558f9017e0
---
M src/mem/cache/compressors/Compressors.py
M src/mem/cache/compressors/SConscript
A src/mem/cache/compressors/cpack.cc
A src/mem/cache/compressors/cpack.hh
4 files changed, 400 insertions(+), 0 deletions(-)
diff --git a/src/mem/cache/compressors/Compressors.py
b/src/mem/cache/compressors/Compressors.py
index b67f638..1901758 100644
--- a/src/mem/cache/compressors/Compressors.py
+++ b/src/mem/cache/compressors/Compressors.py
@@ -38,6 +38,11 @@
line_size = Param.Int(Parent.cache_line_size,
"Cache line size in bytes")
+class CPack(BaseCacheCompressor):
+ type = 'CPack'
+ cxx_class = 'CPack'
+ cxx_header = "mem/cache/compressors/cpack.hh"
+
class NoCompressor(BaseCacheCompressor):
type = 'NoCompressor'
cxx_class = 'NoCompressor'
diff --git a/src/mem/cache/compressors/SConscript
b/src/mem/cache/compressors/SConscript
index 3c6cfce..8c05f16 100644
--- a/src/mem/cache/compressors/SConscript
+++ b/src/mem/cache/compressors/SConscript
@@ -33,4 +33,5 @@
SimObject('Compressors.py')
Source('base.cc')
+Source('cpack.cc')
Source('no_compressor.cc')
diff --git a/src/mem/cache/compressors/cpack.cc
b/src/mem/cache/compressors/cpack.cc
new file mode 100644
index 0000000..b896460
--- /dev/null
+++ b/src/mem/cache/compressors/cpack.cc
@@ -0,0 +1,213 @@
+/*
+ * 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 the CPack cache compressor.
+ */
+
+#include "mem/cache/compressors/cpack.hh"
+
+#include <algorithm>
+#include <cstdint>
+
+#include "params/CPack.hh"
+
+CPack::CPackCompData::CPackCompData(std::size_t dictionary_size,
+ const uint8_t* cache_line)
+ : CompressionData(dictionary_size/2, cache_line),
+ compWords(dictionary_size, 0)
+{
+}
+
+CPack::CPackCompData::~CPackCompData()
+{
+}
+
+CPack::CPack(const Params *p)
+ : BaseCacheCompressor(p), dictionarySize(2*lineSize)
+{
+ dictionary.resize(dictionarySize);
+
+ resetDictionary();
+}
+
+void
+CPack::resetDictionary()
+{
+ // Reset number of valid entries
+ numEntries = 0;
+
+ // Set all entries as 0
+ std::fill(dictionary.begin(), dictionary.end(), 0);
+}
+
+std::size_t
+CPack::compressWord(uint32_t data, uint64_t& comp_word)
+{
+ std::size_t size; // Size of the compressed word
+ std::size_t numBMatch = 0; // Number of bytes matched so far
+
+ // Pattern matching (zzzz and zzzx)
+ if ((data & 0xFFFFFF00) == 0x00000000){
+ // Matched zzzx
+ if (data & 0x000000FF){
+ comp_word = (patternData[ZZZX].code<<8) | (data & 0x000000FF);
+ return patternData[ZZZX].length;
+ // Matched zzzz
+ } else {
+ comp_word = patternData[ZZZZ].code;
+ return patternData[ZZZZ].length;
+ }
+ }
+
+ // Default as uncompressed
+ comp_word = (static_cast<uint64_t>(patternData[XXXX].code) << 32) |
data;
+ size = patternData[XXXX].length;
+
+ // Dictionary matching
+ for (std::size_t i = 0; i < numEntries; i++){
+ // Check if matched mmmm
+ if (dictionary[i] == data){
+ comp_word = (patternData[MMMM].code << dictWidth) | i;
+ size = patternData[MMMM].length;
+
+ // There's nothing better than a full match, so stop search
+ break;
+ // Check if matched mmmx
+ } else if ((numBMatch < 3) &&
+ ((dictionary[i] & 0xFFFFFF00) == (data & 0xFFFFFF00))){
+ numBMatch = 3;
+ comp_word = (((patternData[MMMX].code << dictWidth) | i) << 8)
|
+ (data & 0x000000FF);
+ size = patternData[MMMX].length;
+ // Check if matched mmxx
+ } else if ((numBMatch < 2) &&
+ ((dictionary[i] & 0xFFFF0000) == (data & 0xFFFF0000))){
+ numBMatch = 2;
+ comp_word = (((patternData[MMXX].code << dictWidth) | i) <<
16) |
+ (data & 0x0000FFFF);
+ size = patternData[MMXX].length;
+ }
+ }
+
+ // Push into dictionary
+ if (numEntries < dictionarySize) dictionary[numEntries++] = data;
+
+ return size;
+}
+
+std::unique_ptr<CompressionData>
+CPack::compress(const uint8_t* cache_line, Cycles& lat)
+{
+ std::unique_ptr<CPackCompData> comp_data =
std::unique_ptr<CPackCompData>(
+ new CPackCompData(dictionarySize, cache_line));
+
+ // Compression size
+ std::size_t size = 0;
+
+ // Reset dictionary
+ resetDictionary();
+
+ // Compress every word sequentially
+ for (std::size_t i = 0; i < dictionarySize/2; i++) {
+ uint32_t firstWord = (cache_line[i]&0xFFFFFFFF00000000) >> 32;
+ uint32_t secondWord = cache_line[i]&0x00000000FFFFFFFF;
+
+ size += compressWord(firstWord, comp_data->compWords[2*i]);
+ size += compressWord(secondWord, comp_data->compWords[2*i+1]);
+ }
+
+ // Change size from bits to bytes
+ size = std::ceil(size/8);
+
+ // Set final compression size
+ comp_data->setSize(size);
+
+ // @todo Set compression latency
+ lat = Cycles(0);
+
+ // Return compressed line
+ return comp_data;
+}
+
+uint32_t
+CPack::decompressWord(uint64_t comp_data)
+{
+ // Check if matches xxxx
+ if (comp_data & 0x0000000100000000){
+ dictionary[numEntries] = comp_data;
+ return dictionary[numEntries++];
+ // Check if matches mmxx
+ } else if (comp_data & 0xF00000){
+ dictionary[numEntries] = (dictionary[(comp_data & 0xF0000) >> 16] &
+ 0xFFFF0000) | (comp_data & 0x0000FFFF);
+ return dictionary[numEntries++];
+ // Check if matches mmmx
+ }else if (comp_data & 0xF000){
+ dictionary[numEntries] = (dictionary[(comp_data & 0xF00) >> 8] &
+ 0xFFFFFF00) | (comp_data & 0x000000FF);
+ return dictionary[numEntries++];
+ // Check if matches zzzx
+ } else if (comp_data & 0xF00) return comp_data & 0xFF;
+ // Check if matches mmmm
+ else if (comp_data & 0xF0){
+ dictionary[numEntries] = dictionary[comp_data & 0xF];
+ return dictionary[numEntries++];
+ // Matches zzzz
+ } else return 0;
+}
+
+Cycles
+CPack::decompress(const CompressionData* comp_data, uint8_t* cache_line)
+{
+ const CPackCompData* cpack_comp_data =
+ static_cast<const CPackCompData*>(comp_data);
+
+ // Reset dictionary
+ resetDictionary();
+
+ // Decompress every word sequentially
+ for (std::size_t i = 0; i < dictionarySize/2; i+=8) {
+ uint32_t firstWord =
decompressWord(cpack_comp_data->compWords[2*i]);
+ uint32_t secondWord = decompressWord(
+ cpack_comp_data->compWords[2*i+1]);
+ cache_line[i] = (static_cast<uint64_t>(firstWord) << 32) |
secondWord;
+ }
+
+ // @todo Return decompression latency
+ return Cycles(0);
+}
+
+
+CPack*
+CPackParams::create()
+{
+ return new CPack(this);
+}
diff --git a/src/mem/cache/compressors/cpack.hh
b/src/mem/cache/compressors/cpack.hh
new file mode 100644
index 0000000..c310971
--- /dev/null
+++ b/src/mem/cache/compressors/cpack.hh
@@ -0,0 +1,181 @@
+/*
+ * 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 the CPack cache compressor.
+ */
+
+#ifndef __MEM_CACHE_COMPRESSORS_CPACK_HH__
+#define __MEM_CACHE_COMPRESSORS_CPACK_HH__
+
+#include <cstdint>
+#include <vector>
+
+#include "base/types.hh"
+#include "mem/cache/compressors/base.hh"
+
+struct CPackParams;
+
+/**
+ * Implementation of CPack compression, from "C-Pack: A High-Performance
+ * Microprocessor Cache Compression Algorithm".
+ *
+ * The dictionary is composed of 32-bit entries.
+*/
+class CPack : public BaseCacheCompressor {
+ private:
+ /**
+ * Compression data for CPack. It consists of a vector of words.
+ */
+ class CPackCompData : public CompressionData {
+ public:
+ /**
+ * The compressed data, stored word by word.
+ */
+ std::vector<uint64_t> compWords;
+
+ public:
+ /**
+ * Default constructor.
+ *
+ * @param dictionary_size Number of 32-bit entries in the
dictionary.
+ * @param cache_line Cache line to which compression is applied.
+ */
+ CPackCompData(std::size_t dictionary_size, const uint8_t*
cache_line);
+
+ /**
+ * Default destructor.
+ */
+ ~CPackCompData();
+ };
+
+ /**
+ * Bits used to represent the index of a dictionary entry
+ * ((log of the number of entries in the dictionary) - 1).
+ */
+ static const std::size_t dictWidth = 4;
+
+ /**
+ * The patterns proposed in the paper. Each letter represents a byte:
+ * Z is a null byte, M is a dictionary match, X is a new value.
+ * These are used as indexes to reference the pattern data.
+ */
+ enum Pattern {ZZZZ, XXXX, MMMM, MMXX, ZZZX, MMMX};
+
+ /**
+ * The pattern data. Each pattern consists of an encoding and the size
of
+ * its compressed data.
+ */
+ struct PatternData{
+ /**
+ * The opcode.
+ */
+ const uint32_t code;
+
+ /**
+ * Length, in bits (including metadata).
+ */
+ const uint32_t length;
+ } patternData[6] = {{0x0, 2}, {0x1, 34}, {0x2, 6}, {0xC, 24}, {0xD,
12},
+ {0xE, 16}};
+
+ /**
+ * The dictionary.
+ */
+ std::vector<uint32_t> dictionary;
+
+ /**
+ * Dictionary size.
+ */
+ const std::size_t dictionarySize;
+
+ /**
+ * Number of valid entries in the dictionary.
+ */
+ std::size_t numEntries;
+
+ /**
+ * Compress a word.
+ *
+ * @param data Word to be compressed.
+ * @param comp_word Word after compression.
+ * @return Size of the compressed word.
+ */
+ std::size_t compressWord(uint32_t data, uint64_t& comp_word);
+
+ /**
+ * Decompress a word.
+ *
+ * @param comp_data The data to be decompressed.
+ * @return The decompressed word.
+ */
+ uint32_t decompressWord(uint64_t comp_data);
+
+ /**
+ * Clear all dictionary entries.
+ */
+ void resetDictionary();
+
+ public:
+ /** Convenience typedef. */
+ typedef CPackParams Params;
+
+ /**
+ * Default constructor.
+ */
+ CPack(const Params *p);
+
+ /**
+ * Default destructor.
+ */
+ ~CPack() {};
+
+ /**
+ * Apply compression.
+ *
+ * @param cache_line The cache line to be compressed.
+ * @param Compression latency in number of cycles.
+ * @return Cache line after compression.
+ */
+ std::unique_ptr<CompressionData> compress(const uint8_t* cache_line,
+ Cycles& lat) override;
+
+ /**
+ * Decompress data.
+ *
+ * @param comp_data Compressed cache line.
+ * @param cache_line The cache line to be decompressed.
+ * @return Decompression latency in number of cycles.
+ */
+ Cycles decompress(const CompressionData* comp_data, uint8_t*
cache_line)
+
override;
+};
+
+#endif
--
To view, visit https://gem5-review.googlesource.com/11105
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: master
Gerrit-Change-Id: I2efc9db2c862620dcc1155300e39be558f9017e0
Gerrit-Change-Number: 11105
Gerrit-PatchSet: 1
Gerrit-Owner: Daniel Carvalho <oda...@yahoo.com.br>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list
gem5-dev@gem5.org
http://m5sim.org/mailman/listinfo/gem5-dev
