114089Sodanrc@yahoo.com.br/* 214089Sodanrc@yahoo.com.br * Copyright (c) 2018 Inria 314089Sodanrc@yahoo.com.br * All rights reserved. 414089Sodanrc@yahoo.com.br * 514089Sodanrc@yahoo.com.br * Redistribution and use in source and binary forms, with or without 614089Sodanrc@yahoo.com.br * modification, are permitted provided that the following conditions are 714089Sodanrc@yahoo.com.br * met: redistributions of source code must retain the above copyright 814089Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer; 914089Sodanrc@yahoo.com.br * redistributions in binary form must reproduce the above copyright 1014089Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer in the 1114089Sodanrc@yahoo.com.br * documentation and/or other materials provided with the distribution; 1214089Sodanrc@yahoo.com.br * neither the name of the copyright holders nor the names of its 1314089Sodanrc@yahoo.com.br * contributors may be used to endorse or promote products derived from 1414089Sodanrc@yahoo.com.br * this software without specific prior written permission. 1514089Sodanrc@yahoo.com.br * 1614089Sodanrc@yahoo.com.br * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1714089Sodanrc@yahoo.com.br * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1814089Sodanrc@yahoo.com.br * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1914089Sodanrc@yahoo.com.br * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2014089Sodanrc@yahoo.com.br * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2114089Sodanrc@yahoo.com.br * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2214089Sodanrc@yahoo.com.br * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2314089Sodanrc@yahoo.com.br * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2414089Sodanrc@yahoo.com.br * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2514089Sodanrc@yahoo.com.br * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2614089Sodanrc@yahoo.com.br * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2714089Sodanrc@yahoo.com.br * 2814089Sodanrc@yahoo.com.br * Authors: Daniel Carvalho 2914089Sodanrc@yahoo.com.br */ 3014089Sodanrc@yahoo.com.br 3114089Sodanrc@yahoo.com.br/** @file 3214089Sodanrc@yahoo.com.br * Implementation of the CPack cache compressor. 3314089Sodanrc@yahoo.com.br */ 3414089Sodanrc@yahoo.com.br 3514089Sodanrc@yahoo.com.br#include "mem/cache/compressors/cpack.hh" 3614089Sodanrc@yahoo.com.br 3714089Sodanrc@yahoo.com.br#include <algorithm> 3814089Sodanrc@yahoo.com.br#include <cstdint> 3914089Sodanrc@yahoo.com.br 4014089Sodanrc@yahoo.com.br#include "debug/CacheComp.hh" 4114089Sodanrc@yahoo.com.br#include "params/CPack.hh" 4214089Sodanrc@yahoo.com.br 4314089Sodanrc@yahoo.com.brCPack::CompData::CompData(const std::size_t dictionary_size) 4414089Sodanrc@yahoo.com.br : CompressionData() 4514089Sodanrc@yahoo.com.br{ 4614089Sodanrc@yahoo.com.br} 4714089Sodanrc@yahoo.com.br 4814089Sodanrc@yahoo.com.brCPack::CompData::~CompData() 4914089Sodanrc@yahoo.com.br{ 5014089Sodanrc@yahoo.com.br} 5114089Sodanrc@yahoo.com.br 5214089Sodanrc@yahoo.com.brCPack::CPack(const Params *p) 5314089Sodanrc@yahoo.com.br : BaseCacheCompressor(p), dictionarySize(2*blkSize/8) 5414089Sodanrc@yahoo.com.br{ 5514089Sodanrc@yahoo.com.br dictionary.resize(dictionarySize); 5614089Sodanrc@yahoo.com.br 5714089Sodanrc@yahoo.com.br resetDictionary(); 5814089Sodanrc@yahoo.com.br} 5914089Sodanrc@yahoo.com.br 6014089Sodanrc@yahoo.com.brvoid 6114089Sodanrc@yahoo.com.brCPack::resetDictionary() 6214089Sodanrc@yahoo.com.br{ 6314089Sodanrc@yahoo.com.br // Reset number of valid entries 6414089Sodanrc@yahoo.com.br numEntries = 0; 6514089Sodanrc@yahoo.com.br 6614089Sodanrc@yahoo.com.br // Set all entries as 0 6714089Sodanrc@yahoo.com.br std::array<uint8_t, 4> zero_word = {0, 0, 0, 0}; 6814089Sodanrc@yahoo.com.br std::fill(dictionary.begin(), dictionary.end(), zero_word); 6914089Sodanrc@yahoo.com.br} 7014089Sodanrc@yahoo.com.br 7114089Sodanrc@yahoo.com.brstd::unique_ptr<CPack::Pattern> 7214089Sodanrc@yahoo.com.brCPack::compressWord(const uint32_t data) 7314089Sodanrc@yahoo.com.br{ 7414089Sodanrc@yahoo.com.br // Split data in bytes 7514089Sodanrc@yahoo.com.br const std::array<uint8_t, 4> bytes = { 7614089Sodanrc@yahoo.com.br static_cast<uint8_t>(data & 0xFF), 7714089Sodanrc@yahoo.com.br static_cast<uint8_t>((data >> 8) & 0xFF), 7814089Sodanrc@yahoo.com.br static_cast<uint8_t>((data >> 16) & 0xFF), 7914089Sodanrc@yahoo.com.br static_cast<uint8_t>((data >> 24) & 0xFF) 8014089Sodanrc@yahoo.com.br }; 8114089Sodanrc@yahoo.com.br 8214089Sodanrc@yahoo.com.br // Start as a no-match pattern. A negative match location is used so that 8314089Sodanrc@yahoo.com.br // patterns that depend on the dictionary entry don't match 8414089Sodanrc@yahoo.com.br std::unique_ptr<Pattern> pattern = 8514089Sodanrc@yahoo.com.br PatternFactory::getPattern(bytes, {0, 0, 0, 0}, -1); 8614089Sodanrc@yahoo.com.br 8714089Sodanrc@yahoo.com.br // Search for word on dictionary 8814089Sodanrc@yahoo.com.br for (std::size_t i = 0; i < numEntries; i++) { 8914089Sodanrc@yahoo.com.br // Try matching input with possible patterns 9014089Sodanrc@yahoo.com.br std::unique_ptr<Pattern> temp_pattern = 9114089Sodanrc@yahoo.com.br PatternFactory::getPattern(bytes, dictionary[i], i); 9214089Sodanrc@yahoo.com.br 9314089Sodanrc@yahoo.com.br // Check if found pattern is better than previous 9414089Sodanrc@yahoo.com.br if (temp_pattern->getSizeBits() < pattern->getSizeBits()) { 9514089Sodanrc@yahoo.com.br pattern = std::move(temp_pattern); 9614089Sodanrc@yahoo.com.br } 9714089Sodanrc@yahoo.com.br } 9814089Sodanrc@yahoo.com.br 9914089Sodanrc@yahoo.com.br // Update stats 10014089Sodanrc@yahoo.com.br patternStats[pattern->getPatternNumber()]++; 10114089Sodanrc@yahoo.com.br 10214089Sodanrc@yahoo.com.br // Push into dictionary 10314089Sodanrc@yahoo.com.br if ((numEntries < dictionarySize) && pattern->shouldAllocate()) { 10414089Sodanrc@yahoo.com.br dictionary[numEntries++] = bytes; 10514089Sodanrc@yahoo.com.br } 10614089Sodanrc@yahoo.com.br 10714089Sodanrc@yahoo.com.br return pattern; 10814089Sodanrc@yahoo.com.br} 10914089Sodanrc@yahoo.com.br 11014089Sodanrc@yahoo.com.brstd::unique_ptr<BaseCacheCompressor::CompressionData> 11114089Sodanrc@yahoo.com.brCPack::compress(const uint64_t* data, Cycles& comp_lat, Cycles& decomp_lat) 11214089Sodanrc@yahoo.com.br{ 11314089Sodanrc@yahoo.com.br std::unique_ptr<CompData> comp_data = 11414089Sodanrc@yahoo.com.br std::unique_ptr<CompData>(new CompData(dictionarySize)); 11514089Sodanrc@yahoo.com.br 11614089Sodanrc@yahoo.com.br // Compression size 11714089Sodanrc@yahoo.com.br std::size_t size = 0; 11814089Sodanrc@yahoo.com.br 11914089Sodanrc@yahoo.com.br // Reset dictionary 12014089Sodanrc@yahoo.com.br resetDictionary(); 12114089Sodanrc@yahoo.com.br 12214089Sodanrc@yahoo.com.br // Compress every word sequentially 12314089Sodanrc@yahoo.com.br for (std::size_t i = 0; i < blkSize/8; i++) { 12414089Sodanrc@yahoo.com.br const uint32_t first_word = ((data[i])&0xFFFFFFFF00000000) >> 32; 12514089Sodanrc@yahoo.com.br const uint32_t second_word = (data[i])&0x00000000FFFFFFFF; 12614089Sodanrc@yahoo.com.br 12714089Sodanrc@yahoo.com.br // Compress both words 12814089Sodanrc@yahoo.com.br std::unique_ptr<Pattern> first_pattern = compressWord(first_word); 12914089Sodanrc@yahoo.com.br std::unique_ptr<Pattern> second_pattern = compressWord(second_word); 13014089Sodanrc@yahoo.com.br 13114089Sodanrc@yahoo.com.br // Update total line compression size 13214089Sodanrc@yahoo.com.br size += first_pattern->getSizeBits() + second_pattern->getSizeBits(); 13314089Sodanrc@yahoo.com.br 13414089Sodanrc@yahoo.com.br // Print debug information 13514089Sodanrc@yahoo.com.br DPRINTF(CacheComp, "Compressed %08x to %s\n", first_word, 13614089Sodanrc@yahoo.com.br first_pattern->print()); 13714089Sodanrc@yahoo.com.br DPRINTF(CacheComp, "Compressed %08x to %s\n", second_word, 13814089Sodanrc@yahoo.com.br second_pattern->print()); 13914089Sodanrc@yahoo.com.br 14014089Sodanrc@yahoo.com.br // Append to pattern list 14114089Sodanrc@yahoo.com.br comp_data->entries.push_back(std::move(first_pattern)); 14214089Sodanrc@yahoo.com.br comp_data->entries.push_back(std::move(second_pattern)); 14314089Sodanrc@yahoo.com.br } 14414089Sodanrc@yahoo.com.br 14514089Sodanrc@yahoo.com.br // Set final compression size 14614089Sodanrc@yahoo.com.br comp_data->setSizeBits(size); 14714089Sodanrc@yahoo.com.br 14814089Sodanrc@yahoo.com.br // Set compression latency (Accounts for pattern matching, length 14914089Sodanrc@yahoo.com.br // generation, packaging and shifting) 15014089Sodanrc@yahoo.com.br comp_lat = Cycles(blkSize/8+5); 15114089Sodanrc@yahoo.com.br 15214089Sodanrc@yahoo.com.br // Set decompression latency (1 qword per cycle) 15314089Sodanrc@yahoo.com.br decomp_lat = Cycles(blkSize/8); 15414089Sodanrc@yahoo.com.br 15514089Sodanrc@yahoo.com.br // Return compressed line 15614089Sodanrc@yahoo.com.br return std::move(comp_data); 15714089Sodanrc@yahoo.com.br} 15814089Sodanrc@yahoo.com.br 15914089Sodanrc@yahoo.com.bruint32_t 16014089Sodanrc@yahoo.com.brCPack::decompressWord(const Pattern* pattern) 16114089Sodanrc@yahoo.com.br{ 16214089Sodanrc@yahoo.com.br std::array<uint8_t, 4> data; 16314089Sodanrc@yahoo.com.br 16414089Sodanrc@yahoo.com.br // Search for matching entry 16514089Sodanrc@yahoo.com.br std::vector<std::array<uint8_t, 4>>::iterator entry_it = 16614089Sodanrc@yahoo.com.br dictionary.begin(); 16714089Sodanrc@yahoo.com.br std::advance(entry_it, pattern->getMatchLocation()); 16814089Sodanrc@yahoo.com.br 16914089Sodanrc@yahoo.com.br // Decompress the match. If the decompressed value must be added to 17014089Sodanrc@yahoo.com.br // the dictionary, do it 17114089Sodanrc@yahoo.com.br if (pattern->decompress(*entry_it, data)) { 17214089Sodanrc@yahoo.com.br dictionary[numEntries++] = data; 17314089Sodanrc@yahoo.com.br } 17414089Sodanrc@yahoo.com.br 17514089Sodanrc@yahoo.com.br // Return word 17614089Sodanrc@yahoo.com.br return (((((data[3] << 8) | data[2]) << 8) | data[1]) << 8) | data[0]; 17714089Sodanrc@yahoo.com.br} 17814089Sodanrc@yahoo.com.br 17914089Sodanrc@yahoo.com.brvoid 18014089Sodanrc@yahoo.com.brCPack::decompress(const CompressionData* comp_data, uint64_t* data) 18114089Sodanrc@yahoo.com.br{ 18214089Sodanrc@yahoo.com.br const CompData* cpack_comp_data = static_cast<const CompData*>(comp_data); 18314089Sodanrc@yahoo.com.br 18414089Sodanrc@yahoo.com.br // Reset dictionary 18514089Sodanrc@yahoo.com.br resetDictionary(); 18614089Sodanrc@yahoo.com.br 18714089Sodanrc@yahoo.com.br // Decompress every entry sequentially 18814089Sodanrc@yahoo.com.br std::vector<uint32_t> decomp_words; 18914089Sodanrc@yahoo.com.br for (const auto& entry : cpack_comp_data->entries) { 19014089Sodanrc@yahoo.com.br const uint32_t word = decompressWord(&*entry); 19114089Sodanrc@yahoo.com.br decomp_words.push_back(word); 19214089Sodanrc@yahoo.com.br 19314089Sodanrc@yahoo.com.br // Print debug information 19414089Sodanrc@yahoo.com.br DPRINTF(CacheComp, "Decompressed %s to %x\n", entry->print(), word); 19514089Sodanrc@yahoo.com.br } 19614089Sodanrc@yahoo.com.br 19714089Sodanrc@yahoo.com.br // Concatenate the decompressed words to generate the cache lines 19814089Sodanrc@yahoo.com.br for (std::size_t i = 0; i < blkSize/8; i++) { 19914089Sodanrc@yahoo.com.br data[i] = (static_cast<uint64_t>(decomp_words[2*i]) << 32) | 20014089Sodanrc@yahoo.com.br decomp_words[2*i+1]; 20114089Sodanrc@yahoo.com.br } 20214089Sodanrc@yahoo.com.br} 20314089Sodanrc@yahoo.com.br 20414089Sodanrc@yahoo.com.brvoid 20514089Sodanrc@yahoo.com.brCPack::regStats() 20614089Sodanrc@yahoo.com.br{ 20714089Sodanrc@yahoo.com.br BaseCacheCompressor::regStats(); 20814089Sodanrc@yahoo.com.br 20914089Sodanrc@yahoo.com.br // We store the frequency of each pattern 21014089Sodanrc@yahoo.com.br patternStats 21114089Sodanrc@yahoo.com.br .init(Pattern::getNumPatterns()) 21214089Sodanrc@yahoo.com.br .name(name() + ".pattern") 21314089Sodanrc@yahoo.com.br .desc("Number of data entries that were compressed to this pattern.") 21414089Sodanrc@yahoo.com.br ; 21514089Sodanrc@yahoo.com.br 21614089Sodanrc@yahoo.com.br for (unsigned i = 0; i < Pattern::getNumPatterns(); ++i) { 21714089Sodanrc@yahoo.com.br patternStats.subname(i, Pattern::getName(i)); 21814089Sodanrc@yahoo.com.br patternStats.subdesc(i, "Number of data entries that match pattern " + 21914089Sodanrc@yahoo.com.br Pattern::getName(i)); 22014089Sodanrc@yahoo.com.br } 22114089Sodanrc@yahoo.com.br} 22214089Sodanrc@yahoo.com.br 22314089Sodanrc@yahoo.com.brCPack* 22414089Sodanrc@yahoo.com.brCPackParams::create() 22514089Sodanrc@yahoo.com.br{ 22614089Sodanrc@yahoo.com.br return new CPack(this); 22714089Sodanrc@yahoo.com.br} 228