113944Sodanrc@yahoo.com.br/* 213944Sodanrc@yahoo.com.br * Copyright (c) 2018 Inria 313944Sodanrc@yahoo.com.br * All rights reserved. 413944Sodanrc@yahoo.com.br * 513944Sodanrc@yahoo.com.br * Redistribution and use in source and binary forms, with or without 613944Sodanrc@yahoo.com.br * modification, are permitted provided that the following conditions are 713944Sodanrc@yahoo.com.br * met: redistributions of source code must retain the above copyright 813944Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer; 913944Sodanrc@yahoo.com.br * redistributions in binary form must reproduce the above copyright 1013944Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer in the 1113944Sodanrc@yahoo.com.br * documentation and/or other materials provided with the distribution; 1213944Sodanrc@yahoo.com.br * neither the name of the copyright holders nor the names of its 1313944Sodanrc@yahoo.com.br * contributors may be used to endorse or promote products derived from 1413944Sodanrc@yahoo.com.br * this software without specific prior written permission. 1513944Sodanrc@yahoo.com.br * 1613944Sodanrc@yahoo.com.br * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1713944Sodanrc@yahoo.com.br * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1813944Sodanrc@yahoo.com.br * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1913944Sodanrc@yahoo.com.br * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2013944Sodanrc@yahoo.com.br * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2113944Sodanrc@yahoo.com.br * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2213944Sodanrc@yahoo.com.br * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2313944Sodanrc@yahoo.com.br * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2413944Sodanrc@yahoo.com.br * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2513944Sodanrc@yahoo.com.br * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2613944Sodanrc@yahoo.com.br * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2713944Sodanrc@yahoo.com.br * 2813944Sodanrc@yahoo.com.br * Authors: Daniel Carvalho 2913944Sodanrc@yahoo.com.br */ 3013944Sodanrc@yahoo.com.br 3113944Sodanrc@yahoo.com.br/** @file 3213944Sodanrc@yahoo.com.br * Implementation of the BDI cache compressor. 3313944Sodanrc@yahoo.com.br */ 3413944Sodanrc@yahoo.com.br 3513944Sodanrc@yahoo.com.br#include "mem/cache/compressors/bdi.hh" 3613944Sodanrc@yahoo.com.br 3713944Sodanrc@yahoo.com.br#include <algorithm> 3813944Sodanrc@yahoo.com.br#include <climits> 3913944Sodanrc@yahoo.com.br#include <cstring> 4013944Sodanrc@yahoo.com.br#include <type_traits> 4113944Sodanrc@yahoo.com.br 4213944Sodanrc@yahoo.com.br#include "debug/CacheComp.hh" 4313944Sodanrc@yahoo.com.br#include "params/BDI.hh" 4413944Sodanrc@yahoo.com.br 4513944Sodanrc@yahoo.com.br// Number of bytes in a qword 4613944Sodanrc@yahoo.com.br#define BYTES_PER_QWORD 8 4713944Sodanrc@yahoo.com.br 4813944Sodanrc@yahoo.com.br// Declare BDI encoding names 4913944Sodanrc@yahoo.com.brconst char* BDI::ENCODING_NAMES[] = 5013944Sodanrc@yahoo.com.br {"Zero", "Repeated_Values", "Base8_1", "Base8_2", "Base8_4", "Base4_1", 5113944Sodanrc@yahoo.com.br "Base4_2", "Base2_1", "Uncompressed"}; 5213944Sodanrc@yahoo.com.br 5313944Sodanrc@yahoo.com.brBDI::BDICompData::BDICompData(const uint8_t encoding) 5413944Sodanrc@yahoo.com.br : CompressionData(), _encoding(encoding) 5513944Sodanrc@yahoo.com.br{ 5613944Sodanrc@yahoo.com.br} 5713944Sodanrc@yahoo.com.br 5813944Sodanrc@yahoo.com.bruint8_t 5913944Sodanrc@yahoo.com.brBDI::BDICompData::getEncoding() const 6013944Sodanrc@yahoo.com.br{ 6113944Sodanrc@yahoo.com.br return _encoding; 6213944Sodanrc@yahoo.com.br} 6313944Sodanrc@yahoo.com.br 6413944Sodanrc@yahoo.com.brstd::string 6513944Sodanrc@yahoo.com.brBDI::BDICompData::getName() const 6613944Sodanrc@yahoo.com.br{ 6713944Sodanrc@yahoo.com.br return ENCODING_NAMES[_encoding]; 6813944Sodanrc@yahoo.com.br} 6913944Sodanrc@yahoo.com.br 7013944Sodanrc@yahoo.com.brBDI::BDICompDataZeros::BDICompDataZeros() 7113944Sodanrc@yahoo.com.br : BDICompData(ZERO) 7213944Sodanrc@yahoo.com.br{ 7313944Sodanrc@yahoo.com.br // Calculate compressed size 7413944Sodanrc@yahoo.com.br calculateCompressedSize(); 7513944Sodanrc@yahoo.com.br} 7613944Sodanrc@yahoo.com.br 7713944Sodanrc@yahoo.com.bruint64_t 7813944Sodanrc@yahoo.com.brBDI::BDICompDataZeros::access(const int index) const 7913944Sodanrc@yahoo.com.br{ 8013944Sodanrc@yahoo.com.br return 0; 8113944Sodanrc@yahoo.com.br} 8213944Sodanrc@yahoo.com.br 8313944Sodanrc@yahoo.com.brvoid 8413944Sodanrc@yahoo.com.brBDI::BDICompDataZeros::calculateCompressedSize() 8513944Sodanrc@yahoo.com.br{ 8613944Sodanrc@yahoo.com.br // Number of bits used by Encoding 8713944Sodanrc@yahoo.com.br std::size_t size = encodingBits; 8813944Sodanrc@yahoo.com.br 8913944Sodanrc@yahoo.com.br setSizeBits(size); 9013944Sodanrc@yahoo.com.br} 9113944Sodanrc@yahoo.com.br 9213944Sodanrc@yahoo.com.brBDI::BDICompDataRep::BDICompDataRep(const uint64_t rep_value) 9313944Sodanrc@yahoo.com.br : BDICompData(REP_VALUES) 9413944Sodanrc@yahoo.com.br{ 9513944Sodanrc@yahoo.com.br // Set base value 9613944Sodanrc@yahoo.com.br base = rep_value; 9713944Sodanrc@yahoo.com.br 9813944Sodanrc@yahoo.com.br // Calculate compressed size 9913944Sodanrc@yahoo.com.br calculateCompressedSize(); 10013944Sodanrc@yahoo.com.br} 10113944Sodanrc@yahoo.com.br 10213944Sodanrc@yahoo.com.bruint64_t 10313944Sodanrc@yahoo.com.brBDI::BDICompDataRep::access(const int index) const 10413944Sodanrc@yahoo.com.br{ 10513944Sodanrc@yahoo.com.br return base; 10613944Sodanrc@yahoo.com.br} 10713944Sodanrc@yahoo.com.br 10813944Sodanrc@yahoo.com.brvoid 10913944Sodanrc@yahoo.com.brBDI::BDICompDataRep::calculateCompressedSize() 11013944Sodanrc@yahoo.com.br{ 11113944Sodanrc@yahoo.com.br // Number of bits used by Encoding 11213944Sodanrc@yahoo.com.br std::size_t size = encodingBits; 11313944Sodanrc@yahoo.com.br 11413944Sodanrc@yahoo.com.br // Number of bits used by Base 11513944Sodanrc@yahoo.com.br size += sizeof(base)*CHAR_BIT; 11613944Sodanrc@yahoo.com.br 11713944Sodanrc@yahoo.com.br setSizeBits(size); 11813944Sodanrc@yahoo.com.br} 11913944Sodanrc@yahoo.com.br 12013944Sodanrc@yahoo.com.brBDI::BDICompDataUncompressed::BDICompDataUncompressed( 12113944Sodanrc@yahoo.com.br const uint64_t* data, const std::size_t blk_size) 12213944Sodanrc@yahoo.com.br : BDICompData(UNCOMPRESSED), blkSize(blk_size), 12313944Sodanrc@yahoo.com.br _data(data, data + blk_size/CHAR_BIT) 12413944Sodanrc@yahoo.com.br{ 12513944Sodanrc@yahoo.com.br // Calculate compressed size 12613944Sodanrc@yahoo.com.br calculateCompressedSize(); 12713944Sodanrc@yahoo.com.br} 12813944Sodanrc@yahoo.com.br 12913944Sodanrc@yahoo.com.bruint64_t 13013944Sodanrc@yahoo.com.brBDI::BDICompDataUncompressed::access(const int index) const 13113944Sodanrc@yahoo.com.br{ 13213944Sodanrc@yahoo.com.br return _data[index]; 13313944Sodanrc@yahoo.com.br} 13413944Sodanrc@yahoo.com.br 13513944Sodanrc@yahoo.com.brvoid 13613944Sodanrc@yahoo.com.brBDI::BDICompDataUncompressed::calculateCompressedSize() 13713944Sodanrc@yahoo.com.br{ 13813944Sodanrc@yahoo.com.br // Number of bits used by Encoding 13913944Sodanrc@yahoo.com.br std::size_t size = encodingBits; 14013944Sodanrc@yahoo.com.br 14113944Sodanrc@yahoo.com.br // Number of bits used by uncompressed line 14213944Sodanrc@yahoo.com.br size += blkSize*CHAR_BIT; 14313944Sodanrc@yahoo.com.br 14413944Sodanrc@yahoo.com.br setSizeBits(size); 14513944Sodanrc@yahoo.com.br} 14613944Sodanrc@yahoo.com.br 14713944Sodanrc@yahoo.com.brtemplate <class TB, class TD> 14813944Sodanrc@yahoo.com.brBDI::BDICompDataBaseDelta<TB, TD>::BDICompDataBaseDelta(const uint8_t encoding, 14913944Sodanrc@yahoo.com.br const std::size_t blk_size, const std::size_t max_num_bases) 15013944Sodanrc@yahoo.com.br : BDICompData(encoding), maxNumBases(max_num_bases) 15113944Sodanrc@yahoo.com.br{ 15213944Sodanrc@yahoo.com.br // Reserve the maximum possible size for the vectors 15313944Sodanrc@yahoo.com.br bases.reserve(maxNumBases); 15413944Sodanrc@yahoo.com.br bitMask.reserve(blk_size/sizeof(TD)); 15513944Sodanrc@yahoo.com.br deltas.reserve(blk_size/sizeof(TD)); 15613944Sodanrc@yahoo.com.br 15713944Sodanrc@yahoo.com.br // Push virtual base 0 to bases list 15813944Sodanrc@yahoo.com.br bases.push_back(0); 15913944Sodanrc@yahoo.com.br} 16013944Sodanrc@yahoo.com.br 16113944Sodanrc@yahoo.com.brtemplate <class TB, class TD> 16213944Sodanrc@yahoo.com.brvoid 16313944Sodanrc@yahoo.com.brBDI::BDICompDataBaseDelta<TB, TD>::calculateCompressedSize() 16413944Sodanrc@yahoo.com.br{ 16513944Sodanrc@yahoo.com.br // Number of bits used by Encoding 16613944Sodanrc@yahoo.com.br std::size_t size = encodingBits; 16713944Sodanrc@yahoo.com.br 16813944Sodanrc@yahoo.com.br // Number of bits used by BitMask 16914269Sodanrc@yahoo.com.br size += bitMask.size()*std::ceil(std::log2(maxNumBases)); 17013944Sodanrc@yahoo.com.br 17113944Sodanrc@yahoo.com.br // Number of bits used by Bases. bases[0] is implicit in a hardware 17213944Sodanrc@yahoo.com.br // implementation, therefore its size is 0 17313944Sodanrc@yahoo.com.br size += (maxNumBases-1)*sizeof(TB)*CHAR_BIT; 17413944Sodanrc@yahoo.com.br 17513944Sodanrc@yahoo.com.br // Number of bits used by Deltas 17613944Sodanrc@yahoo.com.br size += deltas.size()*sizeof(TD)*CHAR_BIT; 17713944Sodanrc@yahoo.com.br 17813944Sodanrc@yahoo.com.br CompressionData::setSizeBits(size); 17913944Sodanrc@yahoo.com.br} 18013944Sodanrc@yahoo.com.br 18113944Sodanrc@yahoo.com.brtemplate <class TB, class TD> 18213944Sodanrc@yahoo.com.brbool 18313944Sodanrc@yahoo.com.brBDI::BDICompDataBaseDelta<TB, TD>::addBase(const TB base) 18413944Sodanrc@yahoo.com.br{ 18513944Sodanrc@yahoo.com.br // Can't add base if reached limit of number of bases 18613944Sodanrc@yahoo.com.br if (bases.size() >= maxNumBases) { 18713944Sodanrc@yahoo.com.br return false; 18813944Sodanrc@yahoo.com.br } 18913944Sodanrc@yahoo.com.br 19013944Sodanrc@yahoo.com.br // Push new base to end of bases list 19113944Sodanrc@yahoo.com.br bases.push_back(base); 19213944Sodanrc@yahoo.com.br 19313944Sodanrc@yahoo.com.br // New delta is 0, as it is a difference between the new base and itself 19413944Sodanrc@yahoo.com.br addDelta(bases.size() - 1, 0); 19513944Sodanrc@yahoo.com.br 19613944Sodanrc@yahoo.com.br return true; 19713944Sodanrc@yahoo.com.br} 19813944Sodanrc@yahoo.com.br 19913944Sodanrc@yahoo.com.brtemplate <class TB, class TD> 20013944Sodanrc@yahoo.com.brvoid 20113944Sodanrc@yahoo.com.brBDI::BDICompDataBaseDelta<TB, TD>::addDelta(const std::size_t base_index, 20213944Sodanrc@yahoo.com.br const TD delta) 20313944Sodanrc@yahoo.com.br{ 20413944Sodanrc@yahoo.com.br // Insert new delta with respect to the given base 20513944Sodanrc@yahoo.com.br bitMask.push_back(base_index); 20613944Sodanrc@yahoo.com.br 20713944Sodanrc@yahoo.com.br // Insert new delta 20813944Sodanrc@yahoo.com.br deltas.push_back(delta); 20913944Sodanrc@yahoo.com.br} 21013944Sodanrc@yahoo.com.br 21113944Sodanrc@yahoo.com.brtemplate <class TB, class TD> bool 21213944Sodanrc@yahoo.com.brBDI::BDICompDataBaseDelta<TB, TD>::compress(const uint64_t* data, 21313944Sodanrc@yahoo.com.br const std::size_t blk_size) 21413944Sodanrc@yahoo.com.br{ 21513944Sodanrc@yahoo.com.br // Parse through data in a sizeof(TB) granularity 21613944Sodanrc@yahoo.com.br for (std::size_t byte_start = 0; byte_start < blk_size; 21713944Sodanrc@yahoo.com.br byte_start += sizeof(TB)) 21813944Sodanrc@yahoo.com.br { 21913944Sodanrc@yahoo.com.br // Get current value 22013944Sodanrc@yahoo.com.br TB curValue; 22113944Sodanrc@yahoo.com.br std::memcpy(&curValue, ((uint8_t*)data) + byte_start, 22213944Sodanrc@yahoo.com.br sizeof(TB)); 22313944Sodanrc@yahoo.com.br 22413944Sodanrc@yahoo.com.br // Iterate through all bases to search for a valid delta 22513944Sodanrc@yahoo.com.br bool foundDelta = false; 22613944Sodanrc@yahoo.com.br for (int base_index = 0; base_index < bases.size(); base_index++) { 22713944Sodanrc@yahoo.com.br // Calculate delta relative to currently parsed base 22813944Sodanrc@yahoo.com.br typename std::make_signed<TB>::type delta = curValue - 22913944Sodanrc@yahoo.com.br bases[base_index]; 23013944Sodanrc@yahoo.com.br 23113944Sodanrc@yahoo.com.br // Check if the delta is within the limits of the delta size. If 23213944Sodanrc@yahoo.com.br // that is the case, add delta to compressed data and keep parsing 23313944Sodanrc@yahoo.com.br // the input data 23413944Sodanrc@yahoo.com.br typename std::make_signed<TB>::type limit = 23513944Sodanrc@yahoo.com.br ULLONG_MAX>>((BYTES_PER_QWORD-sizeof(TD))*CHAR_BIT+1); 23613944Sodanrc@yahoo.com.br if ((delta >= -limit) && (delta <= limit)) { 23713944Sodanrc@yahoo.com.br addDelta(base_index, delta); 23813944Sodanrc@yahoo.com.br foundDelta = true; 23913944Sodanrc@yahoo.com.br break; 24013944Sodanrc@yahoo.com.br } 24113944Sodanrc@yahoo.com.br } 24213944Sodanrc@yahoo.com.br 24313944Sodanrc@yahoo.com.br // If we cannot find a base that can accommodate this new line's data, 24413944Sodanrc@yahoo.com.br // add this value as the new base and insert its respective delta of 0. 24513944Sodanrc@yahoo.com.br // If the new base can't be added, it means that we reached the base 24613944Sodanrc@yahoo.com.br // limit, so line is uncompressible using the given encoding 24713944Sodanrc@yahoo.com.br if (!foundDelta && !addBase(curValue)) { 24813944Sodanrc@yahoo.com.br return false; 24913944Sodanrc@yahoo.com.br } 25013944Sodanrc@yahoo.com.br } 25113944Sodanrc@yahoo.com.br 25213944Sodanrc@yahoo.com.br // Calculate compressed size 25313944Sodanrc@yahoo.com.br calculateCompressedSize(); 25413944Sodanrc@yahoo.com.br 25513944Sodanrc@yahoo.com.br return true; 25613944Sodanrc@yahoo.com.br} 25713944Sodanrc@yahoo.com.br 25813944Sodanrc@yahoo.com.brtemplate <class TB, class TD> 25913944Sodanrc@yahoo.com.bruint64_t 26013944Sodanrc@yahoo.com.brBDI::BDICompDataBaseDelta<TB, TD>::access(const int index) const 26113944Sodanrc@yahoo.com.br{ 26213944Sodanrc@yahoo.com.br // We decompress all base-delta pairs that form the 64-bit entry 26313944Sodanrc@yahoo.com.br // corresponding to the given 64-bit-array index 26413944Sodanrc@yahoo.com.br uint64_t value = 0; 26513944Sodanrc@yahoo.com.br 26613944Sodanrc@yahoo.com.br // Get relationship between the size of an uint64_t base and size of TB 26713944Sodanrc@yahoo.com.br const std::size_t size_diff = sizeof(uint64_t)/sizeof(TB); 26813944Sodanrc@yahoo.com.br 26913944Sodanrc@yahoo.com.br // Mask for a base entry 27013944Sodanrc@yahoo.com.br const uint64_t mask = ULLONG_MAX>>((BYTES_PER_QWORD-sizeof(TB))*CHAR_BIT); 27113944Sodanrc@yahoo.com.br 27213944Sodanrc@yahoo.com.br // Size, in bits, of a base entry. Cant be const because compiler will 27313944Sodanrc@yahoo.com.br // optimize and create a 64 bit instance, which will generate a shift size 27413944Sodanrc@yahoo.com.br // compilation error 27513944Sodanrc@yahoo.com.br int base_size_bits = sizeof(TB)*CHAR_BIT; 27613944Sodanrc@yahoo.com.br 27713944Sodanrc@yahoo.com.br // Concatenate all base-delta entries until they form a 64-bit entry 27813944Sodanrc@yahoo.com.br for (int delta_index = size_diff * (index + 1) - 1; 27913944Sodanrc@yahoo.com.br delta_index >= (int)(size_diff * index); delta_index--) { 28013944Sodanrc@yahoo.com.br // Get base and delta entries corresponding to the current delta 28113944Sodanrc@yahoo.com.br assert(delta_index < deltas.size()); 28213944Sodanrc@yahoo.com.br const TD delta = deltas[delta_index]; 28313944Sodanrc@yahoo.com.br const int base_index = bitMask[delta_index]; 28413944Sodanrc@yahoo.com.br assert(base_index < bases.size()); 28513944Sodanrc@yahoo.com.br const TB base = bases[base_index]; 28613944Sodanrc@yahoo.com.br 28713944Sodanrc@yahoo.com.br // Concatenate decompressed value 28813944Sodanrc@yahoo.com.br value <<= base_size_bits; 28913944Sodanrc@yahoo.com.br value |= static_cast<uint64_t>((base + delta) & mask); 29013944Sodanrc@yahoo.com.br } 29113944Sodanrc@yahoo.com.br 29213944Sodanrc@yahoo.com.br return value; 29313944Sodanrc@yahoo.com.br} 29413944Sodanrc@yahoo.com.br 29513944Sodanrc@yahoo.com.brBDI::BDI(const Params *p) 29613944Sodanrc@yahoo.com.br : BaseCacheCompressor(p), useMoreCompressors(p->use_more_compressors), 29713944Sodanrc@yahoo.com.br qwordsPerCacheLine(blkSize/BYTES_PER_QWORD) 29813944Sodanrc@yahoo.com.br{ 29913944Sodanrc@yahoo.com.br static_assert(sizeof(ENCODING_NAMES)/sizeof(char*) == NUM_ENCODINGS, 30013944Sodanrc@yahoo.com.br "Number of encodings doesn't match the number of names"); 30113944Sodanrc@yahoo.com.br} 30213944Sodanrc@yahoo.com.br 30313944Sodanrc@yahoo.com.brbool 30413944Sodanrc@yahoo.com.brBDI::isZeroPackable(const uint64_t* data) const 30513944Sodanrc@yahoo.com.br{ 30613944Sodanrc@yahoo.com.br return std::all_of(data, data + qwordsPerCacheLine, 30713944Sodanrc@yahoo.com.br [](const uint64_t entry){ return entry == 0; }); 30813944Sodanrc@yahoo.com.br} 30913944Sodanrc@yahoo.com.br 31013944Sodanrc@yahoo.com.brbool 31113944Sodanrc@yahoo.com.brBDI::isSameValuePackable(const uint64_t* data) const 31213944Sodanrc@yahoo.com.br{ 31313944Sodanrc@yahoo.com.br // We don't want to copy the whole array to the lambda expression 31413944Sodanrc@yahoo.com.br const uint64_t rep_value = data[0]; 31513944Sodanrc@yahoo.com.br return std::all_of(data, data + qwordsPerCacheLine, 31613944Sodanrc@yahoo.com.br [rep_value](const uint64_t entry) 31713944Sodanrc@yahoo.com.br {return entry == rep_value;}); 31813944Sodanrc@yahoo.com.br} 31913944Sodanrc@yahoo.com.br 32013944Sodanrc@yahoo.com.brtemplate <class TB, class TD> 32113944Sodanrc@yahoo.com.brstd::unique_ptr<BDI::BDICompData> 32213944Sodanrc@yahoo.com.brBDI::tryCompress(const uint64_t* data, const uint8_t encoding) const 32313944Sodanrc@yahoo.com.br{ 32413944Sodanrc@yahoo.com.br // Instantiate compressor 32513944Sodanrc@yahoo.com.br auto temp_data = std::unique_ptr<BDICompDataBaseDelta<TB, TD>>( 32613944Sodanrc@yahoo.com.br new BDICompDataBaseDelta<TB, TD>(encoding, blkSize)); 32713944Sodanrc@yahoo.com.br 32813944Sodanrc@yahoo.com.br // Try compressing. Return nullptr if compressor can't compress given line 32913944Sodanrc@yahoo.com.br if (temp_data->compress(data, blkSize)) { 33013944Sodanrc@yahoo.com.br return std::move(temp_data); 33113944Sodanrc@yahoo.com.br } else { 33213944Sodanrc@yahoo.com.br return std::unique_ptr<BDICompData>{}; 33313944Sodanrc@yahoo.com.br } 33413944Sodanrc@yahoo.com.br} 33513944Sodanrc@yahoo.com.br 33613944Sodanrc@yahoo.com.brvoid 33713944Sodanrc@yahoo.com.brBDI::decompress(const BaseCacheCompressor::CompressionData* comp_data, 33813944Sodanrc@yahoo.com.br uint64_t* data) 33913944Sodanrc@yahoo.com.br{ 34013944Sodanrc@yahoo.com.br // Decompress and go back to host endianness 34113944Sodanrc@yahoo.com.br for (std::size_t i = 0; i < qwordsPerCacheLine; i++) 34213944Sodanrc@yahoo.com.br data[i] = static_cast<const BDICompData*>(comp_data)->access(i); 34313944Sodanrc@yahoo.com.br} 34413944Sodanrc@yahoo.com.br 34513944Sodanrc@yahoo.com.brstd::unique_ptr<BaseCacheCompressor::CompressionData> 34613944Sodanrc@yahoo.com.brBDI::compress(const uint64_t* data, Cycles& comp_lat, Cycles& decomp_lat) 34713944Sodanrc@yahoo.com.br{ 34813944Sodanrc@yahoo.com.br std::unique_ptr<BDICompData> bdi_data; 34913944Sodanrc@yahoo.com.br 35013944Sodanrc@yahoo.com.br // Check if it is a zero line 35113944Sodanrc@yahoo.com.br if (isZeroPackable(data)) { 35213944Sodanrc@yahoo.com.br bdi_data = std::unique_ptr<BDICompData>(new BDICompDataZeros()); 35313944Sodanrc@yahoo.com.br 35413944Sodanrc@yahoo.com.br // Set compression latency (compare 1 qword per cycle) 35513944Sodanrc@yahoo.com.br comp_lat = Cycles(qwordsPerCacheLine); 35613944Sodanrc@yahoo.com.br // Check if all values in the line are the same 35713944Sodanrc@yahoo.com.br } else if (isSameValuePackable(data)) { 35813944Sodanrc@yahoo.com.br bdi_data = std::unique_ptr<BDICompData>(new BDICompDataRep(data[0])); 35913944Sodanrc@yahoo.com.br 36013944Sodanrc@yahoo.com.br // Set compression latency (compare 1 qword per cycle) 36113944Sodanrc@yahoo.com.br comp_lat = Cycles(qwordsPerCacheLine); 36213944Sodanrc@yahoo.com.br } else { 36313944Sodanrc@yahoo.com.br // Initialize compressed data as an uncompressed instance 36413944Sodanrc@yahoo.com.br bdi_data = std::unique_ptr<BDICompData>( 36513944Sodanrc@yahoo.com.br new BDICompDataUncompressed(data, blkSize)); 36613944Sodanrc@yahoo.com.br 36713944Sodanrc@yahoo.com.br // Base size-delta size ratio. Used to optimize run and try to 36813944Sodanrc@yahoo.com.br // compress less combinations when their size is worse than the 36913944Sodanrc@yahoo.com.br // current best. It does not reflect the compression ratio, as 37013944Sodanrc@yahoo.com.br // it does not take the metadata into account. 37113944Sodanrc@yahoo.com.br int base_delta_ratio = 2; 37213944Sodanrc@yahoo.com.br 37313944Sodanrc@yahoo.com.br // Check which base-delta size combination is the best. This is 37413944Sodanrc@yahoo.com.br // optimized by giving priority to trying the compressor that would 37513944Sodanrc@yahoo.com.br // generate the smallest compression size. This way we waste less 37613944Sodanrc@yahoo.com.br // simulation time by not doing all possible combinations 37713944Sodanrc@yahoo.com.br for (int ratio = 8; ratio >= base_delta_ratio; ratio/=2) { 37813944Sodanrc@yahoo.com.br for (int base_size = 8; base_size >= ratio; base_size/=2) { 37913944Sodanrc@yahoo.com.br // If using more compressors, parse all delta sizes from 1 to 38013944Sodanrc@yahoo.com.br // one size smaller than the base size, otherwise just parse 38113944Sodanrc@yahoo.com.br // highest possible delta. When we only instantiate one delta 38213944Sodanrc@yahoo.com.br // size per base size, we use less area and energy, at the 38313944Sodanrc@yahoo.com.br // cost of lower compression efficiency 38413944Sodanrc@yahoo.com.br const int delta_size = base_size/ratio; 38513944Sodanrc@yahoo.com.br if (!useMoreCompressors && delta_size != base_size/2) { 38613944Sodanrc@yahoo.com.br continue; 38713944Sodanrc@yahoo.com.br } 38813944Sodanrc@yahoo.com.br 38913944Sodanrc@yahoo.com.br std::unique_ptr<BDICompData> temp_bdi_data; 39013944Sodanrc@yahoo.com.br 39113944Sodanrc@yahoo.com.br // Get the compression result for the current combination 39213944Sodanrc@yahoo.com.br if ((base_size == 8)&&(delta_size == 4)) { 39313944Sodanrc@yahoo.com.br temp_bdi_data = tryCompress<uint64_t, int32_t>(data, 39413944Sodanrc@yahoo.com.br BASE8_4); 39513944Sodanrc@yahoo.com.br } else if ((base_size == 8)&&(delta_size == 2)) { 39613944Sodanrc@yahoo.com.br temp_bdi_data = tryCompress<uint64_t, int16_t>(data, 39713944Sodanrc@yahoo.com.br BASE8_2); 39813944Sodanrc@yahoo.com.br } else if ((base_size == 8)&&(delta_size == 1)) { 39913944Sodanrc@yahoo.com.br temp_bdi_data = tryCompress<uint64_t, int8_t>(data, 40013944Sodanrc@yahoo.com.br BASE8_1); 40113944Sodanrc@yahoo.com.br } else if ((base_size == 4)&&(delta_size == 2)) { 40213944Sodanrc@yahoo.com.br temp_bdi_data = tryCompress<uint32_t, int16_t>(data, 40313944Sodanrc@yahoo.com.br BASE4_2); 40413944Sodanrc@yahoo.com.br } else if ((base_size == 4)&&(delta_size == 1)) { 40513944Sodanrc@yahoo.com.br temp_bdi_data = tryCompress<uint32_t, int8_t>(data, 40613944Sodanrc@yahoo.com.br BASE4_1); 40713944Sodanrc@yahoo.com.br } else if ((base_size == 2)&&(delta_size == 1)) { 40813944Sodanrc@yahoo.com.br temp_bdi_data = tryCompress<uint16_t, int8_t>(data, 40913944Sodanrc@yahoo.com.br BASE2_1); 41013944Sodanrc@yahoo.com.br } else { 41113944Sodanrc@yahoo.com.br fatal("Invalid combination of base and delta sizes."); 41213944Sodanrc@yahoo.com.br } 41313944Sodanrc@yahoo.com.br 41413944Sodanrc@yahoo.com.br // If compressor was successful, check if new compression 41513944Sodanrc@yahoo.com.br // improves the compression factor 41613944Sodanrc@yahoo.com.br if (temp_bdi_data && 41713944Sodanrc@yahoo.com.br (bdi_data->getSizeBits() > temp_bdi_data->getSizeBits())) 41813944Sodanrc@yahoo.com.br { 41913944Sodanrc@yahoo.com.br bdi_data = std::move(temp_bdi_data); 42013944Sodanrc@yahoo.com.br base_delta_ratio = ratio; 42113944Sodanrc@yahoo.com.br } 42213944Sodanrc@yahoo.com.br 42313944Sodanrc@yahoo.com.br // Clear temp pointer 42413944Sodanrc@yahoo.com.br temp_bdi_data.reset(nullptr); 42513944Sodanrc@yahoo.com.br } 42613944Sodanrc@yahoo.com.br } 42713944Sodanrc@yahoo.com.br 42813944Sodanrc@yahoo.com.br // Set compression latency. A successful compressor will stop all 42913944Sodanrc@yahoo.com.br // other compressors when it knows no other will generate a better 43013944Sodanrc@yahoo.com.br // compression. However, this requires either hard-coding, or a complex 43113944Sodanrc@yahoo.com.br // function that can calculate the exact size of every compressor for 43213944Sodanrc@yahoo.com.br // every cache line size. We decide to take a conservative 43313944Sodanrc@yahoo.com.br // optimization: assume that all compressors with a given base size 43413944Sodanrc@yahoo.com.br // delta size ratio (no-metadata ratio) must wait for each other. 43513944Sodanrc@yahoo.com.br // In the worst case scenario the data is left uncompressed, so 43613944Sodanrc@yahoo.com.br // it loses the time of the worst base size (2 bytes per cycle) 43713944Sodanrc@yahoo.com.br comp_lat = Cycles(blkSize/base_delta_ratio); 43813944Sodanrc@yahoo.com.br } 43913944Sodanrc@yahoo.com.br 44013944Sodanrc@yahoo.com.br // Update stats 44113944Sodanrc@yahoo.com.br encodingStats[bdi_data->getEncoding()]++; 44213944Sodanrc@yahoo.com.br 44313944Sodanrc@yahoo.com.br // Pack compression results (1 extra cycle) 44413944Sodanrc@yahoo.com.br comp_lat += Cycles(1); 44513944Sodanrc@yahoo.com.br 44613944Sodanrc@yahoo.com.br // Set decompression latency (latency of an adder) 44713944Sodanrc@yahoo.com.br decomp_lat = Cycles(1); 44813944Sodanrc@yahoo.com.br 44913944Sodanrc@yahoo.com.br // Print debug information 45013944Sodanrc@yahoo.com.br DPRINTF(CacheComp, "BDI: Compressed cache line to encoding %s (%d bits)\n", 45113944Sodanrc@yahoo.com.br bdi_data->getName(), bdi_data->getSizeBits()); 45213944Sodanrc@yahoo.com.br 45313944Sodanrc@yahoo.com.br return std::move(bdi_data); 45413944Sodanrc@yahoo.com.br} 45513944Sodanrc@yahoo.com.br 45613944Sodanrc@yahoo.com.brvoid 45713944Sodanrc@yahoo.com.brBDI::regStats() 45813944Sodanrc@yahoo.com.br{ 45913944Sodanrc@yahoo.com.br BaseCacheCompressor::regStats(); 46013944Sodanrc@yahoo.com.br 46113944Sodanrc@yahoo.com.br // We store the frequency of each encoding 46213944Sodanrc@yahoo.com.br encodingStats 46313944Sodanrc@yahoo.com.br .init(NUM_ENCODINGS) 46413944Sodanrc@yahoo.com.br .name(name() + ".encoding") 46513944Sodanrc@yahoo.com.br .desc("Number of data entries that were compressed to this encoding.") 46613944Sodanrc@yahoo.com.br ; 46713944Sodanrc@yahoo.com.br 46813944Sodanrc@yahoo.com.br for (unsigned i = 0; i < NUM_ENCODINGS; ++i) { 46913944Sodanrc@yahoo.com.br encodingStats.subname(i, ENCODING_NAMES[i]); 47013944Sodanrc@yahoo.com.br encodingStats.subdesc(i, "Number of data entries that match " \ 47113944Sodanrc@yahoo.com.br "encoding " + std::string(ENCODING_NAMES[i])); 47213944Sodanrc@yahoo.com.br } 47313944Sodanrc@yahoo.com.br} 47413944Sodanrc@yahoo.com.br 47513944Sodanrc@yahoo.com.brBDI* 47613944Sodanrc@yahoo.com.brBDIParams::create() 47713944Sodanrc@yahoo.com.br{ 47813944Sodanrc@yahoo.com.br return new BDI(this); 47913944Sodanrc@yahoo.com.br} 48013944Sodanrc@yahoo.com.br 48113944Sodanrc@yahoo.com.br#undef BYTES_PER_QWORD 482