From b8a4a911eed17315320a6948d369f791617adfeb Mon Sep 17 00:00:00 2001 From: "Daniel R. Carvalho" Date: Mon, 29 Jul 2019 16:36:59 +0200 Subject: [PATCH] mem-cache: Implement a multi compressor Implement a compressor that contains multiple sub-compressors and choses the one that provides the best compression results for each compression. Change-Id: I758cf67c84bd85edbea16b2a07b2068b00454461 Signed-off-by: Daniel R. Carvalho Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/21158 Reviewed-by: Jason Lowe-Power Maintainer: Jason Lowe-Power Tested-by: kokoro --- src/mem/cache/compressors/Compressors.py | 10 ++ src/mem/cache/compressors/SConscript | 1 + src/mem/cache/compressors/base.hh | 6 + src/mem/cache/compressors/multi.cc | 185 +++++++++++++++++++++++ src/mem/cache/compressors/multi.hh | 116 ++++++++++++++ 5 files changed, 318 insertions(+) create mode 100644 src/mem/cache/compressors/multi.cc create mode 100644 src/mem/cache/compressors/multi.hh diff --git a/src/mem/cache/compressors/Compressors.py b/src/mem/cache/compressors/Compressors.py index 607491ad4..c3fcd2317 100644 --- a/src/mem/cache/compressors/Compressors.py +++ b/src/mem/cache/compressors/Compressors.py @@ -99,6 +99,16 @@ class FPCD(BaseDictionaryCompressor): dictionary_size = 2 +class MultiCompressor(BaseCacheCompressor): + type = 'MultiCompressor' + cxx_class = 'MultiCompressor' + cxx_header = "mem/cache/compressors/multi.hh" + + # Dummy default compressor list. This might not be an optimal choice, + # since these compressors have many overlapping patterns + compressors = VectorParam.BaseCacheCompressor([CPack(), FPCD()], + "Array of compressors") + class RepeatedQwordsCompressor(BaseDictionaryCompressor): type = 'RepeatedQwordsCompressor' cxx_class = 'RepeatedQwordsCompressor' diff --git a/src/mem/cache/compressors/SConscript b/src/mem/cache/compressors/SConscript index 517ec522a..c3f22b8b6 100644 --- a/src/mem/cache/compressors/SConscript +++ b/src/mem/cache/compressors/SConscript @@ -38,5 +38,6 @@ Source('base_delta.cc') Source('bdi.cc') Source('cpack.cc') Source('fpcd.cc') +Source('multi.cc') Source('repeated_qwords.cc') Source('zero.cc') diff --git a/src/mem/cache/compressors/base.hh b/src/mem/cache/compressors/base.hh index 19dec0fd3..ea40b8dab 100644 --- a/src/mem/cache/compressors/base.hh +++ b/src/mem/cache/compressors/base.hh @@ -53,6 +53,12 @@ struct BaseCacheCompressorParams; */ class BaseCacheCompressor : public SimObject { protected: + /** + * This compressor must be able to access the protected functions of + * its sub-compressors. + */ + friend class MultiCompressor; + /** * Forward declaration of compression data. Every new compressor must * create a new compression data based on it. diff --git a/src/mem/cache/compressors/multi.cc b/src/mem/cache/compressors/multi.cc new file mode 100644 index 000000000..a032f8334 --- /dev/null +++ b/src/mem/cache/compressors/multi.cc @@ -0,0 +1,185 @@ +/* + * 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 the a multi compressor that choses the best compression + * among multiple compressors. + */ + +#include "mem/cache/compressors/multi.hh" + +#include +#include + +#include "base/bitfield.hh" +#include "debug/CacheComp.hh" +#include "params/MultiCompressor.hh" + +MultiCompressor::MultiCompData::MultiCompData(unsigned index, + std::unique_ptr comp_data) + : CompressionData(), index(index), compData(std::move(comp_data)) +{ + setSizeBits(compData->getSizeBits()); +} + +uint8_t +MultiCompressor::MultiCompData::getIndex() const +{ + return index; +} + +MultiCompressor::MultiCompressor(const Params *p) + : BaseCacheCompressor(p), compressors(p->compressors) +{ + fatal_if(compressors.size() == 0, "There must be at least one compressor"); +} + +MultiCompressor::~MultiCompressor() +{ + for (auto& compressor : compressors) { + delete compressor; + } +} + +std::unique_ptr +MultiCompressor::compress(const uint64_t* cache_line, Cycles& comp_lat, + Cycles& decomp_lat) +{ + struct Results + { + unsigned index; + std::unique_ptr compData; + Cycles decompLat; + uint8_t compressionFactor; + + Results(unsigned index, + std::unique_ptr comp_data, + Cycles decomp_lat, std::size_t blk_size) + : index(index), compData(std::move(comp_data)), + decompLat(decomp_lat) + { + const std::size_t size = compData->getSize(); + // 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 + compressionFactor = (size > blk_size) ? 1 : + alignToPowerOfTwo(std::floor(blk_size / (double) size)); + } + }; + struct ResultsComparator + { + bool + operator()(const std::shared_ptr& lhs, + const std::shared_ptr& rhs) const + { + const std::size_t lhs_cf = lhs->compressionFactor; + const std::size_t rhs_cf = rhs->compressionFactor; + + if (lhs_cf == rhs_cf) { + // When they have similar compressed sizes, give the one + // with fastest decompression privilege + return lhs->decompLat < rhs->decompLat; + } + return lhs_cf < rhs_cf; + } + }; + + // Find the ranking of the compressor outputs + std::priority_queue, + std::vector>, ResultsComparator> results; + Cycles max_comp_lat; + for (unsigned i = 0; i < compressors.size(); i++) { + Cycles temp_decomp_lat; + auto temp_comp_data = + compressors[i]->compress(cache_line, comp_lat, temp_decomp_lat); + results.push(std::make_shared(i, std::move(temp_comp_data), + temp_decomp_lat, blkSize)); + max_comp_lat = std::max(max_comp_lat, comp_lat); + } + + // Assign best compressor to compression data + const unsigned best_index = results.top()->index; + std::unique_ptr multi_comp_data = + std::unique_ptr( + new MultiCompData(best_index, std::move(results.top()->compData))); + DPRINTF(CacheComp, "Best compressor: %d\n", best_index); + + // Set decompression latency of the best compressor + decomp_lat = results.top()->decompLat; + + // Update compressor ranking stats + for (int rank = 0; rank < compressors.size(); rank++) { + rankStats[results.top()->index][rank]++; + results.pop(); + } + + // Set compression latency (compression latency of the slowest compressor + // and 1 cycle to pack) + comp_lat = Cycles(max_comp_lat + 1); + + return multi_comp_data; +} + +void +MultiCompressor::decompress(const CompressionData* comp_data, + uint64_t* cache_line) +{ + const MultiCompData* casted_comp_data = + static_cast(comp_data); + compressors[casted_comp_data->getIndex()]->decompress( + casted_comp_data->compData.get(), cache_line); +} + +void +MultiCompressor::regStats() +{ + BaseCacheCompressor::regStats(); + + rankStats + .init(compressors.size(), compressors.size()) + .name(name() + ".rank") + .desc("Number of times each compressor had the nth best compression.") + ; + + for (int compressor = 0; compressor < compressors.size(); compressor++) { + rankStats.subname(compressor, std::to_string(compressor)); + rankStats.subdesc(compressor, "Number of times compressor " + + std::to_string(compressor) + " had the nth best compression."); + for (unsigned rank = 0; rank < compressors.size(); rank++) { + rankStats.ysubname(rank, std::to_string(rank)); + } + } +} + +MultiCompressor* +MultiCompressorParams::create() +{ + return new MultiCompressor(this); +} diff --git a/src/mem/cache/compressors/multi.hh b/src/mem/cache/compressors/multi.hh new file mode 100644 index 000000000..d9d470d56 --- /dev/null +++ b/src/mem/cache/compressors/multi.hh @@ -0,0 +1,116 @@ +/* + * 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 the a multi compressor that choses the best compression + * among multiple compressors. + */ + +#ifndef __MEM_CACHE_COMPRESSORS_MULTI_HH__ +#define __MEM_CACHE_COMPRESSORS_MULTI_HH__ + +#include +#include + +#include "base/types.hh" +#include "mem/cache/compressors/base.hh" + +struct MultiCompressorParams; + +class MultiCompressor : public BaseCacheCompressor +{ + protected: + /** + * Compression data for the multi compressor. It contains the compression + * data of the best compressor, along with its index in the list of + * sub-compressors. + */ + class MultiCompData; + + /** List of sub-compressors. */ + std::vector compressors; + + /** + * @defgroup CompressionStats Compression specific statistics. + * @{ + */ + + /** Number of times each compressor provided the nth best compression. */ + Stats::Vector2d rankStats; + + /** + * @} + */ + + public: + /** Convenience typedef. */ + typedef MultiCompressorParams Params; + + /** Default constructor. */ + MultiCompressor(const Params *p); + + /** Default destructor. */ + ~MultiCompressor(); + + void regStats() override; + + std::unique_ptr compress( + const uint64_t* data, Cycles& comp_lat, Cycles& decomp_lat) override; + + void decompress(const CompressionData* comp_data, uint64_t* data) override; +}; + +class MultiCompressor::MultiCompData : public CompressionData +{ + private: + /** Index of the compressor that provided these compression results. */ + const uint8_t index; + + public: + /** Compression data of the best compressor. */ + std::unique_ptr compData; + + /** + * Default constructor. + * + * @param index Index of the compressor that provided this compression. + * @param comp_data Compression data of the best compressor. + */ + MultiCompData(unsigned index, + std::unique_ptr comp_data); + + /** Default destructor. */ + ~MultiCompData() = default; + + /** Get the index of the best compressor. */ + uint8_t getIndex() const; +}; + +#endif //__MEM_CACHE_COMPRESSORS_MULTI_HH__ -- 2.30.2