From d52516756cf32ecb53b75e8a6f032ebeeb427a71 Mon Sep 17 00:00:00 2001 From: Maciej Kurc Date: Fri, 9 Jul 2021 15:40:06 +0200 Subject: Working site LUT mapping cache Signed-off-by: Maciej Kurc --- fpga_interchange/site_lut_mapping_cache.h | 130 ++++++++++++++++++++++++++++++ 1 file changed, 130 insertions(+) create mode 100644 fpga_interchange/site_lut_mapping_cache.h (limited to 'fpga_interchange/site_lut_mapping_cache.h') diff --git a/fpga_interchange/site_lut_mapping_cache.h b/fpga_interchange/site_lut_mapping_cache.h new file mode 100644 index 00000000..4a81711f --- /dev/null +++ b/fpga_interchange/site_lut_mapping_cache.h @@ -0,0 +1,130 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2021 Symbiflow Authors + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#ifndef SITE_LUT_MAPPING_CACHE_H +#define SITE_LUT_MAPPING_CACHE_H + +#include "idstring.h" +#include "nextpnr_namespaces.h" + +NEXTPNR_NAMESPACE_BEGIN + +// Key structure used in site LUT mapping cache +struct SiteLutMappingKey { + + // LUT Cell data + struct Cell { + IdString type; // Cell type + int32_t belIndex; // Bound BEL index + + // Port to net assignments. These are local net ids generated during + // key creation. This is to abstract connections from actual design + // net names. + dict conns; + + bool operator == (const Cell& other) const { + return (type == other.type) && + (belIndex == other.belIndex) && + (conns == other.conns); + } + + bool operator < (const Cell& other) const { + return belIndex < other.belIndex; + } + }; + + int32_t tileType; // Tile type + int32_t siteType; // Site type in that tile type + std::vector cells; // LUT cell data + + static SiteLutMappingKey create (const SiteInformation& siteInfo); + + bool operator == (const SiteLutMappingKey &other) const { + return (tileType == other.tileType) && + (siteType == other.siteType) && + (cells == other.cells); + } + + bool operator != (const SiteLutMappingKey &other) const { + return (tileType != other.tileType) || + (siteType != other.siteType) || + (cells != other.cells); + } + + unsigned int hash () const { + unsigned int h = 0; + h = mkhash(h, tileType); + h = mkhash(h, siteType); + for (const auto& cell : cells) { + h = mkhash(h, cell.type.index); + h = mkhash(h, cell.belIndex); + for (const auto& conn : cell.conns) { + h = mkhash(h, conn.first.index); + h = mkhash(h, conn.second); + } + } + return h; + } +}; + +// Site LUT mapping result data +struct SiteLutMappingResult { + + // LUT cell data + struct Cell { + int32_t belIndex; // BEL in tile index + LutCell lutCell; // LUT mapping data + dict belPins; // Cell to BEL pin mapping + }; + + bool isValid; // Validity flag + std::vector cells; // Cell data + + pool> blockedWires; + + // Applies the mapping result to the site + bool apply (const SiteInformation& siteInfo); +}; + +// Site LUT mapping cache object +class SiteLutMappingCache { +public: + + void add (const SiteLutMappingKey& key, const SiteLutMappingResult& result); + bool get (const SiteLutMappingKey& key, SiteLutMappingResult* result); + + void clear (); + void clearStats (); + + float getMissRatio () const { + return (float)numMisses / (float)(numHits + numMisses); + } + +private: + + dict cache_; + + size_t numHits = 0; + size_t numMisses = 0; +}; + + +NEXTPNR_NAMESPACE_END + +#endif /* SITE_LUT_MAPPING_CACHE_H */ -- cgit v1.2.3 From 044c9ba2d4e66cf34214fdfd62fb90a872da64b1 Mon Sep 17 00:00:00 2001 From: Maciej Kurc Date: Fri, 16 Jul 2021 13:28:40 +0200 Subject: LUT mapping cache optimizations 1 Signed-off-by: Maciej Kurc --- fpga_interchange/site_lut_mapping_cache.h | 52 +++++++++++++++---------------- 1 file changed, 26 insertions(+), 26 deletions(-) (limited to 'fpga_interchange/site_lut_mapping_cache.h') diff --git a/fpga_interchange/site_lut_mapping_cache.h b/fpga_interchange/site_lut_mapping_cache.h index 4a81711f..b07e3e77 100644 --- a/fpga_interchange/site_lut_mapping_cache.h +++ b/fpga_interchange/site_lut_mapping_cache.h @@ -28,6 +28,11 @@ NEXTPNR_NAMESPACE_BEGIN // Key structure used in site LUT mapping cache struct SiteLutMappingKey { + // Maximum number of LUT cells + static constexpr size_t MAX_LUT_CELLS = 8; + // Maximum number of LUT inputs per cell + static constexpr size_t MAX_LUT_INPUTS = 6; + // LUT Cell data struct Cell { IdString type; // Cell type @@ -35,51 +40,46 @@ struct SiteLutMappingKey { // Port to net assignments. These are local net ids generated during // key creation. This is to abstract connections from actual design - // net names. - dict conns; - - bool operator == (const Cell& other) const { - return (type == other.type) && - (belIndex == other.belIndex) && - (conns == other.conns); - } - - bool operator < (const Cell& other) const { - return belIndex < other.belIndex; - } + // net names. the Id 0 means unconnected. + int32_t conns [MAX_LUT_INPUTS]; }; int32_t tileType; // Tile type int32_t siteType; // Site type in that tile type std::vector cells; // LUT cell data + unsigned int hash_; // Precomputed hash + static SiteLutMappingKey create (const SiteInformation& siteInfo); + + void computeHash () { + hash_ = mkhash(0, tileType); + hash_ = mkhash(hash_, siteType); + for (const auto& cell : cells) { + hash_ = mkhash(hash_, cell.type.index); + hash_ = mkhash(hash_, cell.belIndex); + for (size_t i=0; i Date: Fri, 16 Jul 2021 13:55:19 +0200 Subject: LUT mapping ceche optimizations 2 Signed-off-by: Maciej Kurc --- fpga_interchange/site_lut_mapping_cache.h | 21 +++++++++++++-------- 1 file changed, 13 insertions(+), 8 deletions(-) (limited to 'fpga_interchange/site_lut_mapping_cache.h') diff --git a/fpga_interchange/site_lut_mapping_cache.h b/fpga_interchange/site_lut_mapping_cache.h index b07e3e77..df1ce474 100644 --- a/fpga_interchange/site_lut_mapping_cache.h +++ b/fpga_interchange/site_lut_mapping_cache.h @@ -28,7 +28,7 @@ NEXTPNR_NAMESPACE_BEGIN // Key structure used in site LUT mapping cache struct SiteLutMappingKey { - // Maximum number of LUT cells + // Maximum number of LUT cells per site static constexpr size_t MAX_LUT_CELLS = 8; // Maximum number of LUT inputs per cell static constexpr size_t MAX_LUT_INPUTS = 6; @@ -44,18 +44,21 @@ struct SiteLutMappingKey { int32_t conns [MAX_LUT_INPUTS]; }; - int32_t tileType; // Tile type - int32_t siteType; // Site type in that tile type - std::vector cells; // LUT cell data + int32_t tileType; // Tile type + int32_t siteType; // Site type in that tile type + size_t numCells; // LUT cell count + Cell cells[MAX_LUT_CELLS]; // LUT cell data - unsigned int hash_; // Precomputed hash + unsigned int hash_; // Precomputed hash static SiteLutMappingKey create (const SiteInformation& siteInfo); void computeHash () { hash_ = mkhash(0, tileType); hash_ = mkhash(hash_, siteType); - for (const auto& cell : cells) { + hash_ = mkhash(hash_, numCells); + for (size_t j=0; j Date: Fri, 16 Jul 2021 14:55:45 +0200 Subject: Migrated C arrays to std::array containers. Signed-off-by: Maciej Kurc --- fpga_interchange/site_lut_mapping_cache.h | 37 +++++++++++++++++++++++++------ 1 file changed, 30 insertions(+), 7 deletions(-) (limited to 'fpga_interchange/site_lut_mapping_cache.h') diff --git a/fpga_interchange/site_lut_mapping_cache.h b/fpga_interchange/site_lut_mapping_cache.h index df1ce474..42a10ba7 100644 --- a/fpga_interchange/site_lut_mapping_cache.h +++ b/fpga_interchange/site_lut_mapping_cache.h @@ -41,13 +41,25 @@ struct SiteLutMappingKey { // Port to net assignments. These are local net ids generated during // key creation. This is to abstract connections from actual design // net names. the Id 0 means unconnected. - int32_t conns [MAX_LUT_INPUTS]; + std::array conns; + + bool operator == (const Cell& other) const { + return (type == other.type) && + (belIndex == other.belIndex) && + (conns == other.conns); + } + + bool operator != (const Cell& other) const { + return (type != other.type) || + (belIndex != other.belIndex) || + (conns != other.conns); + } }; int32_t tileType; // Tile type int32_t siteType; // Site type in that tile type size_t numCells; // LUT cell count - Cell cells[MAX_LUT_CELLS]; // LUT cell data + std::array cells; // LUT cell data unsigned int hash_; // Precomputed hash @@ -66,21 +78,32 @@ struct SiteLutMappingKey { } } } - + + bool compareCells (const SiteLutMappingKey &other) const { + if (numCells != other.numCells) { + return false; + } + + for (size_t i=0; i Date: Fri, 16 Jul 2021 15:53:00 +0200 Subject: Added computing and reporting LUT mapping cache size Signed-off-by: Maciej Kurc --- fpga_interchange/site_lut_mapping_cache.h | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) (limited to 'fpga_interchange/site_lut_mapping_cache.h') diff --git a/fpga_interchange/site_lut_mapping_cache.h b/fpga_interchange/site_lut_mapping_cache.h index 42a10ba7..b4c074c7 100644 --- a/fpga_interchange/site_lut_mapping_cache.h +++ b/fpga_interchange/site_lut_mapping_cache.h @@ -65,6 +65,10 @@ struct SiteLutMappingKey { static SiteLutMappingKey create (const SiteInformation& siteInfo); + size_t getSizeInBytes () const { + return sizeof(SiteLutMappingKey); + } + void computeHash () { hash_ = mkhash(0, tileType); hash_ = mkhash(hash_, siteType); @@ -128,6 +132,9 @@ struct SiteLutMappingResult { // Applies the mapping result to the site bool apply (const SiteInformation& siteInfo); + + // Returns size in bytes + size_t getSizeInBytes () const; }; // Site LUT mapping cache object @@ -144,6 +151,21 @@ public: return (float)numMisses / (float)(numHits + numMisses); } + size_t getCount () const { + return cache_.size(); + } + + size_t getSizeMB () const { + size_t size = 0; + for (const auto& it : cache_) { + size += it.first.getSizeInBytes(); + size += it.second.getSizeInBytes(); + } + + const size_t MB = 1024L * 1024L; + return (size + MB - 1) / MB; // Round up to megabytes + } + private: dict cache_; -- cgit v1.2.3 From 8fc16a57c9dee5e7e0f83752a62612f70f18a38e Mon Sep 17 00:00:00 2001 From: Maciej Kurc Date: Fri, 16 Jul 2021 16:01:21 +0200 Subject: Added more code comments, formatted the code Signed-off-by: Maciej Kurc --- fpga_interchange/site_lut_mapping_cache.h | 155 +++++++++++++++--------------- 1 file changed, 80 insertions(+), 75 deletions(-) (limited to 'fpga_interchange/site_lut_mapping_cache.h') diff --git a/fpga_interchange/site_lut_mapping_cache.h b/fpga_interchange/site_lut_mapping_cache.h index b4c074c7..0025b889 100644 --- a/fpga_interchange/site_lut_mapping_cache.h +++ b/fpga_interchange/site_lut_mapping_cache.h @@ -20,75 +20,80 @@ #ifndef SITE_LUT_MAPPING_CACHE_H #define SITE_LUT_MAPPING_CACHE_H -#include "idstring.h" #include "nextpnr_namespaces.h" +#include "idstring.h" +#include "site_arch.h" NEXTPNR_NAMESPACE_BEGIN // Key structure used in site LUT mapping cache -struct SiteLutMappingKey { +struct SiteLutMappingKey +{ // Maximum number of LUT cells per site - static constexpr size_t MAX_LUT_CELLS = 8; + static constexpr size_t MAX_LUT_CELLS = 8; // Maximum number of LUT inputs per cell static constexpr size_t MAX_LUT_INPUTS = 6; // LUT Cell data - struct Cell { - IdString type; // Cell type - int32_t belIndex; // Bound BEL index - + struct Cell + { + IdString type; // Cell type + int32_t belIndex; // Bound BEL index + // Port to net assignments. These are local net ids generated during // key creation. This is to abstract connections from actual design // net names. the Id 0 means unconnected. std::array conns; - bool operator == (const Cell& other) const { - return (type == other.type) && - (belIndex == other.belIndex) && - (conns == other.conns); + bool operator==(const Cell &other) const + { + return (type == other.type) && (belIndex == other.belIndex) && (conns == other.conns); } - bool operator != (const Cell& other) const { - return (type != other.type) || - (belIndex != other.belIndex) || - (conns != other.conns); + bool operator!=(const Cell &other) const + { + return (type != other.type) || (belIndex != other.belIndex) || (conns != other.conns); } }; - int32_t tileType; // Tile type - int32_t siteType; // Site type in that tile type - size_t numCells; // LUT cell count + int32_t tileType; // Tile type + int32_t siteType; // Site type in that tile type + size_t numCells; // LUT cell count std::array cells; // LUT cell data - unsigned int hash_; // Precomputed hash + unsigned int hash_; // Precomputed hash - static SiteLutMappingKey create (const SiteInformation& siteInfo); + // Creates a key from the given site state + static SiteLutMappingKey create(const SiteInformation &siteInfo); - size_t getSizeInBytes () const { - return sizeof(SiteLutMappingKey); - } + // Returns size in bytes of the key + size_t getSizeInBytes() const { return sizeof(SiteLutMappingKey); } - void computeHash () { + // Precomputes hash of the key and stores it within + void computeHash() + { hash_ = mkhash(0, tileType); hash_ = mkhash(hash_, siteType); hash_ = mkhash(hash_, numCells); - for (size_t j=0; j belPins; // Cell to BEL pin mapping + struct Cell + { + int32_t belIndex; // BEL in tile index + LutCell lutCell; // LUT mapping data + dict belPins; // Cell to BEL pin mapping }; - bool isValid; // Validity flag - std::vector cells; // Cell data + bool isValid; // Validity flag + std::vector cells; // Cell data - pool> blockedWires; + pool> blockedWires; // Set of blocked wires // Applies the mapping result to the site - bool apply (const SiteInformation& siteInfo); + bool apply(const SiteInformation &siteInfo); // Returns size in bytes - size_t getSizeInBytes () const; + size_t getSizeInBytes() const; }; // Site LUT mapping cache object -class SiteLutMappingCache { -public: - - void add (const SiteLutMappingKey& key, const SiteLutMappingResult& result); - bool get (const SiteLutMappingKey& key, SiteLutMappingResult* result); - - void clear (); - void clearStats (); - - float getMissRatio () const { - return (float)numMisses / (float)(numHits + numMisses); - } - - size_t getCount () const { - return cache_.size(); - } - - size_t getSizeMB () const { +class SiteLutMappingCache +{ + public: + // Adds an entry to the cache + void add(const SiteLutMappingKey &key, const SiteLutMappingResult &result); + // Retrieves an entry from the cache. Returns false if not found + bool get(const SiteLutMappingKey &key, SiteLutMappingResult *result); + + // Clears the cache + void clear(); + // Clears statistics counters of the cache + void clearStats(); + + // Return get() miss ratio + float getMissRatio() const { return (float)numMisses / (float)(numHits + numMisses); } + + // Returns count of entries in the cache + size_t getCount() const { return cache_.size(); } + + // Returns size of the cache rounded upwards to full MBs. + size_t getSizeMB() const + { size_t size = 0; - for (const auto& it : cache_) { + for (const auto &it : cache_) { size += it.first.getSizeInBytes(); size += it.second.getSizeInBytes(); } @@ -166,15 +173,13 @@ public: return (size + MB - 1) / MB; // Round up to megabytes } -private: - - dict cache_; + private: + dict cache_; // The cache - size_t numHits = 0; - size_t numMisses = 0; + size_t numHits = 0; // Hit count + size_t numMisses = 0; // Miss count }; - NEXTPNR_NAMESPACE_END #endif /* SITE_LUT_MAPPING_CACHE_H */ -- cgit v1.2.3 From 580a45485afe48a77272f44f8aa99875cdd4d441 Mon Sep 17 00:00:00 2001 From: Maciej Kurc Date: Thu, 22 Jul 2021 14:07:35 +0200 Subject: Added an option to disable the LUT mapping cache Signed-off-by: Maciej Kurc --- fpga_interchange/site_lut_mapping_cache.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'fpga_interchange/site_lut_mapping_cache.h') diff --git a/fpga_interchange/site_lut_mapping_cache.h b/fpga_interchange/site_lut_mapping_cache.h index 0025b889..7b1d60a4 100644 --- a/fpga_interchange/site_lut_mapping_cache.h +++ b/fpga_interchange/site_lut_mapping_cache.h @@ -20,8 +20,8 @@ #ifndef SITE_LUT_MAPPING_CACHE_H #define SITE_LUT_MAPPING_CACHE_H -#include "nextpnr_namespaces.h" #include "idstring.h" +#include "nextpnr_namespaces.h" #include "site_arch.h" NEXTPNR_NAMESPACE_BEGIN -- cgit v1.2.3