From b7223e0976dddc797babc6cbcaa44aa42ecca4f9 Mon Sep 17 00:00:00 2001 From: "Daniel R. Carvalho" Date: Mon, 22 Jul 2019 19:59:18 +0200 Subject: [PATCH] mem-cache: Implement a perfect compressor Implement a perfect compressor that always manages to compresses data exactly to its maximum allowed compression ratio. This allows tracking a compression upper bound. Change-Id: Ibc68bf2dc84b75207795d5ba6304b9ed6dbeae8f Signed-off-by: Daniel R. Carvalho Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/21160 Tested-by: kokoro Maintainer: Nikos Nikoleris Reviewed-by: Bobby R. Bruce --- src/mem/cache/compressors/Compressors.py | 12 ++++ src/mem/cache/compressors/SConscript | 1 + src/mem/cache/compressors/perfect.cc | 88 +++++++++++++++++++++++ src/mem/cache/compressors/perfect.hh | 89 ++++++++++++++++++++++++ 4 files changed, 190 insertions(+) create mode 100644 src/mem/cache/compressors/perfect.cc create mode 100644 src/mem/cache/compressors/perfect.hh diff --git a/src/mem/cache/compressors/Compressors.py b/src/mem/cache/compressors/Compressors.py index f95824ec6..a1d881392 100644 --- a/src/mem/cache/compressors/Compressors.py +++ b/src/mem/cache/compressors/Compressors.py @@ -100,6 +100,18 @@ class MultiCompressor(BaseCacheCompressor): compressors = VectorParam.BaseCacheCompressor([CPack(), FPCD()], "Array of compressors") +class PerfectCompressor(BaseCacheCompressor): + type = 'PerfectCompressor' + cxx_class = 'PerfectCompressor' + cxx_header = "mem/cache/compressors/perfect.hh" + + max_compression_ratio = Param.Int(2, + "Maximum compression ratio allowed") + compression_latency = Param.Cycles(1, + "Number of cycles to perform data compression") + decompression_latency = Param.Cycles(1, + "Number of cycles to perform data decompression") + class RepeatedQwordsCompressor(BaseDictionaryCompressor): type = 'RepeatedQwordsCompressor' cxx_class = 'RepeatedQwordsCompressor' diff --git a/src/mem/cache/compressors/SConscript b/src/mem/cache/compressors/SConscript index 23464dd6c..6467e583e 100644 --- a/src/mem/cache/compressors/SConscript +++ b/src/mem/cache/compressors/SConscript @@ -38,5 +38,6 @@ Source('base_delta.cc') Source('cpack.cc') Source('fpcd.cc') Source('multi.cc') +Source('perfect.cc') Source('repeated_qwords.cc') Source('zero.cc') diff --git a/src/mem/cache/compressors/perfect.cc b/src/mem/cache/compressors/perfect.cc new file mode 100644 index 000000000..a0475c5e9 --- /dev/null +++ b/src/mem/cache/compressors/perfect.cc @@ -0,0 +1,88 @@ +/* + * Copyright (c) 2019 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 perfect compressor, which compresses data to its + * maximum allowed compression ratio. + */ + +#include "mem/cache/compressors/perfect.hh" + +#include + +#include "debug/CacheComp.hh" +#include "params/PerfectCompressor.hh" + +PerfectCompressor::CompData::CompData(const uint64_t* data, + std::size_t num_entries) + : CompressionData(), entries(data, data + num_entries) +{ +} + +PerfectCompressor::PerfectCompressor(const Params *p) + : BaseCacheCompressor(p), + compressedSize(8 * blkSize / p->max_compression_ratio), + compressionLatency(p->compression_latency), + decompressionLatency(p->decompression_latency) +{ +} + +std::unique_ptr +PerfectCompressor::compress(const uint64_t* cache_line, Cycles& comp_lat, + Cycles& decomp_lat) +{ + // Compress every word sequentially + std::unique_ptr comp_data( + new CompData(cache_line, blkSize/8)); + + // Set relevant metadata + comp_data->setSizeBits(compressedSize); + comp_lat = compressionLatency; + decomp_lat = decompressionLatency; + + return comp_data; +} + +void +PerfectCompressor::decompress(const CompressionData* comp_data, + uint64_t* data) +{ + // Decompress every entry sequentially + const std::vector& entries = + static_cast(comp_data)->entries; + assert(entries.size() == (blkSize/8)); + std::copy(entries.begin(), entries.end(), data); +} + +PerfectCompressor* +PerfectCompressorParams::create() +{ + return new PerfectCompressor(this); +} diff --git a/src/mem/cache/compressors/perfect.hh b/src/mem/cache/compressors/perfect.hh new file mode 100644 index 000000000..8d1d08ba7 --- /dev/null +++ b/src/mem/cache/compressors/perfect.hh @@ -0,0 +1,89 @@ +/* + * Copyright (c) 2019 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 perfect compressor, that always manages to compress to + * its maximum compression ratio. + */ + +#ifndef __MEM_CACHE_COMPRESSORS_PERFECT_COMPRESSOR_HH__ +#define __MEM_CACHE_COMPRESSORS_PERFECT_COMPRESSOR_HH__ + +#include +#include +#include + +#include "base/types.hh" +#include "mem/cache/compressors/base.hh" + +struct PerfectCompressorParams; + +class PerfectCompressor : public BaseCacheCompressor +{ + protected: + class CompData; + + /** Size to which this compressor always compresses. */ + const int compressedSize; + + /** Number of cycles needed to perform compression. */ + const Cycles compressionLatency; + + /** Number of cycles needed to perform decompression. */ + const Cycles decompressionLatency; + + std::unique_ptr compress(const uint64_t* cache_line, + Cycles& comp_lat, Cycles& decomp_lat) override; + + void decompress(const CompressionData* comp_data, uint64_t* data) override; + + public: + typedef PerfectCompressorParams Params; + PerfectCompressor(const Params *p); + ~PerfectCompressor() {}; +}; + +class PerfectCompressor::CompData : public CompressionData +{ + public: + /** The original data is simply copied over to this vector. */ + std::vector entries; + + /** + * Default constructor that creates a copy of the original data. + * + * @param data The data to be compressed. + * @param num_entries The number of qwords in the data. + */ + CompData(const uint64_t* data, std::size_t num_entries); + ~CompData() = default; +}; + +#endif //__MEM_CACHE_COMPRESSORS_PERFECT_COMPRESSOR_HH__ -- 2.30.2