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.cc | 172 +++++++++++++++++++++++++++++ 1 file changed, 172 insertions(+) create mode 100644 fpga_interchange/site_lut_mapping_cache.cc (limited to 'fpga_interchange/site_lut_mapping_cache.cc') diff --git a/fpga_interchange/site_lut_mapping_cache.cc b/fpga_interchange/site_lut_mapping_cache.cc new file mode 100644 index 00000000..bcde7621 --- /dev/null +++ b/fpga_interchange/site_lut_mapping_cache.cc @@ -0,0 +1,172 @@ +/* + * 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. + * + */ + +#include "nextpnr.h" +#include "archdefs.h" +#include "site_arch.h" +#include "site_lut_mapping_cache.h" + +NEXTPNR_NAMESPACE_BEGIN + +// ============================================================================ + +SiteLutMappingKey SiteLutMappingKey::create (const SiteInformation& siteInfo) { + const Context *ctx = siteInfo.ctx; + + // Look for LUT cells in the site + std::vector lutCells; + lutCells.reserve(siteInfo.cells_in_site.size()); + + for (CellInfo* cellInfo : siteInfo.cells_in_site) { + + // Not a LUT cell + if (cellInfo->lut_cell.pins.empty()) { + continue; + } + + // Not bound to a LUT BEL + BelId bel = cellInfo->bel; + const auto &bel_data = bel_info(ctx->chip_info, bel); + if (bel_data.lut_element == -1) { + continue; + } + + lutCells.push_back(cellInfo); + } + + // Sort cells by BEL indices to maintain always the same order + std::sort(lutCells.begin(), lutCells.end(), + [](const CellInfo* a, const CellInfo* b) + { + return a->bel.index > b->bel.index; + }); + + // Initialize the key + SiteLutMappingKey key; + key.tileType = siteInfo.tile_type; + key.siteType = ctx->chip_info->sites[siteInfo.site].site_type; + key.cells.reserve(lutCells.size()); + + // Get bound nets. Store localized (to the LUT cluster) net indices only + // to get always the same key for the same LUT port configuration even + // when the actual global net names are different. + dict netMap; + for (CellInfo* cellInfo : lutCells) { + + SiteLutMappingKey::Cell cell; + cell.type = cellInfo->type; + cell.belIndex = cellInfo->bel.index; + + for (const auto& port : cellInfo->ports) { + const auto& portInfo = port.second; + if (portInfo.net != nullptr) { + auto netInfo = portInfo.net; + int32_t netId = -1; + + auto it = netMap.find(netInfo->name); + if (it != netMap.end()) { + netId = it->second; + } + else { + netId = (int32_t)netMap.size(); + netMap[netInfo->name] = netId; + } + + cell.conns[portInfo.name] = netId; + } + } + + // Add the cell entry + key.cells.push_back(cell); + } + + return key; +} + +// ============================================================================ + + +bool SiteLutMappingResult::apply (const SiteInformation& siteInfo) { + + Context *ctx = const_cast(siteInfo.ctx); + TileStatus &tileStatus = ctx->get_tile_status(siteInfo.tile); + + for (auto& cell : cells) { + + // Get the bound cell + CellInfo* cellInfo = tileStatus.boundcells[cell.belIndex]; + NPNR_ASSERT(cellInfo); + + // Double check BEL binding + NPNR_ASSERT(cellInfo->bel.tile = siteInfo.tile); + NPNR_ASSERT(cellInfo->bel.index = cell.belIndex); + + // Cell <-> BEL pin map + size_t numPins = cellInfo->lut_cell.pins.size(); + for (size_t pinIdx = 0; pinIdx < numPins; ++pinIdx) { + IdString cellPin = cellInfo->lut_cell.pins[pinIdx]; + auto &belPins = cellInfo->cell_bel_pins[cellPin]; + + belPins.resize(1); + belPins[0] = cell.belPins[cellPin]; + } + + // LUT data + // FIXME: Is there any other info that is being updated than vcc_pins ? + cellInfo->lut_cell.vcc_pins = std::move(cell.lutCell.vcc_pins); + } + + return true; +} + +// ============================================================================ + +void SiteLutMappingCache::add (const SiteLutMappingKey& key, + const SiteLutMappingResult& result) +{ + cache_[key] = result; +} + +bool SiteLutMappingCache::get (const SiteLutMappingKey& key, + SiteLutMappingResult* result) +{ + if (cache_.count(key) == 0) { + numMisses++; + return false; + } + + numHits++; + *result = cache_[key]; + return true; +} + +void SiteLutMappingCache::clear () { + cache_.clear(); + clearStats(); +} + +void SiteLutMappingCache::clearStats () { + numHits = 0; + numMisses = 0; +} + +// ============================================================================ + +NEXTPNR_NAMESPACE_END + -- 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.cc | 28 ++++++++++++++++++++++------ 1 file changed, 22 insertions(+), 6 deletions(-) (limited to 'fpga_interchange/site_lut_mapping_cache.cc') diff --git a/fpga_interchange/site_lut_mapping_cache.cc b/fpga_interchange/site_lut_mapping_cache.cc index bcde7621..03ef03be 100644 --- a/fpga_interchange/site_lut_mapping_cache.cc +++ b/fpga_interchange/site_lut_mapping_cache.cc @@ -73,29 +73,44 @@ SiteLutMappingKey SiteLutMappingKey::create (const SiteInformation& siteInfo) { cell.type = cellInfo->type; cell.belIndex = cellInfo->bel.index; + memset((void*)cell.conns, 0, + sizeof(int32_t) * SiteLutMappingKey::MAX_LUT_INPUTS); + + size_t portId = 0; for (const auto& port : cellInfo->ports) { const auto& portInfo = port.second; + + // Consider only LUT inputs + if (portInfo.type != PORT_IN) { + continue; + } + + // Assign net id if any + int32_t netId = 0; if (portInfo.net != nullptr) { auto netInfo = portInfo.net; - int32_t netId = -1; auto it = netMap.find(netInfo->name); if (it != netMap.end()) { netId = it->second; } else { - netId = (int32_t)netMap.size(); + netId = (int32_t)netMap.size() + 1; netMap[netInfo->name] = netId; } - - cell.conns[portInfo.name] = netId; } + + NPNR_ASSERT(portId < SiteLutMappingKey::MAX_LUT_INPUTS); + cell.conns[portId++] = netId; } // Add the cell entry key.cells.push_back(cell); } + // Compute hash + key.computeHash(); + return key; } @@ -120,9 +135,10 @@ bool SiteLutMappingResult::apply (const SiteInformation& siteInfo) { // Cell <-> BEL pin map size_t numPins = cellInfo->lut_cell.pins.size(); for (size_t pinIdx = 0; pinIdx < numPins; ++pinIdx) { - IdString cellPin = cellInfo->lut_cell.pins[pinIdx]; - auto &belPins = cellInfo->cell_bel_pins[cellPin]; + const IdString& cellPin = cellInfo->lut_cell.pins[pinIdx]; + auto &belPins = cellInfo->cell_bel_pins[cellPin]; + // There is only one pin belPins.resize(1); belPins[0] = cell.belPins[cellPin]; } -- cgit v1.2.3 From 0336f55b16373874cf4ac5661d9724d0a358454c Mon Sep 17 00:00:00 2001 From: Maciej Kurc 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.cc | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) (limited to 'fpga_interchange/site_lut_mapping_cache.cc') diff --git a/fpga_interchange/site_lut_mapping_cache.cc b/fpga_interchange/site_lut_mapping_cache.cc index 03ef03be..44a72772 100644 --- a/fpga_interchange/site_lut_mapping_cache.cc +++ b/fpga_interchange/site_lut_mapping_cache.cc @@ -61,7 +61,7 @@ SiteLutMappingKey SiteLutMappingKey::create (const SiteInformation& siteInfo) { SiteLutMappingKey key; key.tileType = siteInfo.tile_type; key.siteType = ctx->chip_info->sites[siteInfo.site].site_type; - key.cells.reserve(lutCells.size()); + key.numCells = 0; // Get bound nets. Store localized (to the LUT cluster) net indices only // to get always the same key for the same LUT port configuration even @@ -69,7 +69,9 @@ SiteLutMappingKey SiteLutMappingKey::create (const SiteInformation& siteInfo) { dict netMap; for (CellInfo* cellInfo : lutCells) { - SiteLutMappingKey::Cell cell; + NPNR_ASSERT(key.numCells < SiteLutMappingKey::MAX_LUT_CELLS); + auto& cell = key.cells[key.numCells++]; + cell.type = cellInfo->type; cell.belIndex = cellInfo->bel.index; @@ -103,9 +105,6 @@ SiteLutMappingKey SiteLutMappingKey::create (const SiteInformation& siteInfo) { NPNR_ASSERT(portId < SiteLutMappingKey::MAX_LUT_INPUTS); cell.conns[portId++] = netId; } - - // Add the cell entry - key.cells.push_back(cell); } // Compute hash -- cgit v1.2.3 From 857961a6bb9302847ecf605971015f1610dae476 Mon Sep 17 00:00:00 2001 From: Maciej Kurc 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.cc | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'fpga_interchange/site_lut_mapping_cache.cc') diff --git a/fpga_interchange/site_lut_mapping_cache.cc b/fpga_interchange/site_lut_mapping_cache.cc index 44a72772..3796d7ab 100644 --- a/fpga_interchange/site_lut_mapping_cache.cc +++ b/fpga_interchange/site_lut_mapping_cache.cc @@ -75,8 +75,7 @@ SiteLutMappingKey SiteLutMappingKey::create (const SiteInformation& siteInfo) { cell.type = cellInfo->type; cell.belIndex = cellInfo->bel.index; - memset((void*)cell.conns, 0, - sizeof(int32_t) * SiteLutMappingKey::MAX_LUT_INPUTS); + cell.conns.fill(0); size_t portId = 0; for (const auto& port : cellInfo->ports) { -- cgit v1.2.3 From c95aa86a8e4fe290bdb030977b7ca40e619a0c30 Mon Sep 17 00:00:00 2001 From: Maciej Kurc Date: Fri, 16 Jul 2021 15:16:31 +0200 Subject: Fixed assertion typos Signed-off-by: Maciej Kurc --- fpga_interchange/site_lut_mapping_cache.cc | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'fpga_interchange/site_lut_mapping_cache.cc') diff --git a/fpga_interchange/site_lut_mapping_cache.cc b/fpga_interchange/site_lut_mapping_cache.cc index 3796d7ab..86f39f2c 100644 --- a/fpga_interchange/site_lut_mapping_cache.cc +++ b/fpga_interchange/site_lut_mapping_cache.cc @@ -127,8 +127,8 @@ bool SiteLutMappingResult::apply (const SiteInformation& siteInfo) { NPNR_ASSERT(cellInfo); // Double check BEL binding - NPNR_ASSERT(cellInfo->bel.tile = siteInfo.tile); - NPNR_ASSERT(cellInfo->bel.index = cell.belIndex); + NPNR_ASSERT(cellInfo->bel.tile == siteInfo.tile); + NPNR_ASSERT(cellInfo->bel.index == cell.belIndex); // Cell <-> BEL pin map size_t numPins = cellInfo->lut_cell.pins.size(); -- cgit v1.2.3 From ccf2bb123c4c2f52142c82c3b6338856df4fbb80 Mon Sep 17 00:00:00 2001 From: Maciej Kurc 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.cc | 15 +++++++++++++++ 1 file changed, 15 insertions(+) (limited to 'fpga_interchange/site_lut_mapping_cache.cc') diff --git a/fpga_interchange/site_lut_mapping_cache.cc b/fpga_interchange/site_lut_mapping_cache.cc index 86f39f2c..7edb0818 100644 --- a/fpga_interchange/site_lut_mapping_cache.cc +++ b/fpga_interchange/site_lut_mapping_cache.cc @@ -149,6 +149,21 @@ bool SiteLutMappingResult::apply (const SiteInformation& siteInfo) { return true; } +size_t SiteLutMappingResult::getSizeInBytes () const { + + size_t size = 0; + + size += sizeof(SiteLutMappingResult); + size += blockedWires.size() * sizeof(std::pair); + + for (const auto& cell : cells) { + size += sizeof(Cell); + size += cell.belPins.size() * sizeof(decltype(cell.belPins)::value_type); + } + + return size; +} + // ============================================================================ void SiteLutMappingCache::add (const SiteLutMappingKey& key, -- 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.cc | 69 ++++++++++++++---------------- 1 file changed, 32 insertions(+), 37 deletions(-) (limited to 'fpga_interchange/site_lut_mapping_cache.cc') diff --git a/fpga_interchange/site_lut_mapping_cache.cc b/fpga_interchange/site_lut_mapping_cache.cc index 7edb0818..0cf741f2 100644 --- a/fpga_interchange/site_lut_mapping_cache.cc +++ b/fpga_interchange/site_lut_mapping_cache.cc @@ -17,23 +17,22 @@ * */ -#include "nextpnr.h" -#include "archdefs.h" -#include "site_arch.h" #include "site_lut_mapping_cache.h" +#include "nextpnr.h" NEXTPNR_NAMESPACE_BEGIN // ============================================================================ -SiteLutMappingKey SiteLutMappingKey::create (const SiteInformation& siteInfo) { +SiteLutMappingKey SiteLutMappingKey::create(const SiteInformation &siteInfo) +{ const Context *ctx = siteInfo.ctx; // Look for LUT cells in the site - std::vector lutCells; + std::vector lutCells; lutCells.reserve(siteInfo.cells_in_site.size()); - for (CellInfo* cellInfo : siteInfo.cells_in_site) { + for (CellInfo *cellInfo : siteInfo.cells_in_site) { // Not a LUT cell if (cellInfo->lut_cell.pins.empty()) { @@ -52,10 +51,7 @@ SiteLutMappingKey SiteLutMappingKey::create (const SiteInformation& siteInfo) { // Sort cells by BEL indices to maintain always the same order std::sort(lutCells.begin(), lutCells.end(), - [](const CellInfo* a, const CellInfo* b) - { - return a->bel.index > b->bel.index; - }); + [](const CellInfo *a, const CellInfo *b) { return a->bel.index > b->bel.index; }); // Initialize the key SiteLutMappingKey key; @@ -67,19 +63,19 @@ SiteLutMappingKey SiteLutMappingKey::create (const SiteInformation& siteInfo) { // to get always the same key for the same LUT port configuration even // when the actual global net names are different. dict netMap; - for (CellInfo* cellInfo : lutCells) { + for (CellInfo *cellInfo : lutCells) { NPNR_ASSERT(key.numCells < SiteLutMappingKey::MAX_LUT_CELLS); - auto& cell = key.cells[key.numCells++]; + auto &cell = key.cells[key.numCells++]; - cell.type = cellInfo->type; - cell.belIndex = cellInfo->bel.index; + cell.type = cellInfo->type; + cell.belIndex = cellInfo->bel.index; cell.conns.fill(0); size_t portId = 0; - for (const auto& port : cellInfo->ports) { - const auto& portInfo = port.second; + for (const auto &port : cellInfo->ports) { + const auto &portInfo = port.second; // Consider only LUT inputs if (portInfo.type != PORT_IN) { @@ -89,13 +85,12 @@ SiteLutMappingKey SiteLutMappingKey::create (const SiteInformation& siteInfo) { // Assign net id if any int32_t netId = 0; if (portInfo.net != nullptr) { - auto netInfo = portInfo.net; + auto netInfo = portInfo.net; auto it = netMap.find(netInfo->name); if (it != netMap.end()) { netId = it->second; - } - else { + } else { netId = (int32_t)netMap.size() + 1; netMap[netInfo->name] = netId; } @@ -114,27 +109,27 @@ SiteLutMappingKey SiteLutMappingKey::create (const SiteInformation& siteInfo) { // ============================================================================ +bool SiteLutMappingResult::apply(const SiteInformation &siteInfo) +{ -bool SiteLutMappingResult::apply (const SiteInformation& siteInfo) { - - Context *ctx = const_cast(siteInfo.ctx); + Context *ctx = const_cast(siteInfo.ctx); TileStatus &tileStatus = ctx->get_tile_status(siteInfo.tile); - for (auto& cell : cells) { + for (auto &cell : cells) { // Get the bound cell - CellInfo* cellInfo = tileStatus.boundcells[cell.belIndex]; + CellInfo *cellInfo = tileStatus.boundcells[cell.belIndex]; NPNR_ASSERT(cellInfo); // Double check BEL binding - NPNR_ASSERT(cellInfo->bel.tile == siteInfo.tile); + NPNR_ASSERT(cellInfo->bel.tile == siteInfo.tile); NPNR_ASSERT(cellInfo->bel.index == cell.belIndex); // Cell <-> BEL pin map size_t numPins = cellInfo->lut_cell.pins.size(); for (size_t pinIdx = 0; pinIdx < numPins; ++pinIdx) { - const IdString& cellPin = cellInfo->lut_cell.pins[pinIdx]; - auto &belPins = cellInfo->cell_bel_pins[cellPin]; + const IdString &cellPin = cellInfo->lut_cell.pins[pinIdx]; + auto &belPins = cellInfo->cell_bel_pins[cellPin]; // There is only one pin belPins.resize(1); @@ -149,14 +144,15 @@ bool SiteLutMappingResult::apply (const SiteInformation& siteInfo) { return true; } -size_t SiteLutMappingResult::getSizeInBytes () const { +size_t SiteLutMappingResult::getSizeInBytes() const +{ size_t size = 0; size += sizeof(SiteLutMappingResult); size += blockedWires.size() * sizeof(std::pair); - for (const auto& cell : cells) { + for (const auto &cell : cells) { size += sizeof(Cell); size += cell.belPins.size() * sizeof(decltype(cell.belPins)::value_type); } @@ -166,14 +162,12 @@ size_t SiteLutMappingResult::getSizeInBytes () const { // ============================================================================ -void SiteLutMappingCache::add (const SiteLutMappingKey& key, - const SiteLutMappingResult& result) +void SiteLutMappingCache::add(const SiteLutMappingKey &key, const SiteLutMappingResult &result) { cache_[key] = result; } -bool SiteLutMappingCache::get (const SiteLutMappingKey& key, - SiteLutMappingResult* result) +bool SiteLutMappingCache::get(const SiteLutMappingKey &key, SiteLutMappingResult *result) { if (cache_.count(key) == 0) { numMisses++; @@ -185,17 +179,18 @@ bool SiteLutMappingCache::get (const SiteLutMappingKey& key, return true; } -void SiteLutMappingCache::clear () { +void SiteLutMappingCache::clear() +{ cache_.clear(); clearStats(); } -void SiteLutMappingCache::clearStats () { - numHits = 0; +void SiteLutMappingCache::clearStats() +{ + numHits = 0; numMisses = 0; } // ============================================================================ NEXTPNR_NAMESPACE_END - -- cgit v1.2.3