From d52516756cf32ecb53b75e8a6f032ebeeb427a71 Mon Sep 17 00:00:00 2001
From: Maciej Kurc <mkurc@antmicro.com>
Date: Fri, 9 Jul 2021 15:40:06 +0200
Subject: Working site LUT mapping cache
Signed-off-by: Maciej Kurc <mkurc@antmicro.com>
---
fpga_interchange/arch.cc | 7 ++
fpga_interchange/arch.h | 2 +
fpga_interchange/luts.cc | 107 +++++++++++++++---
fpga_interchange/luts.h | 12 +-
fpga_interchange/site_lut_mapping_cache.cc | 172 +++++++++++++++++++++++++++++
fpga_interchange/site_lut_mapping_cache.h | 130 ++++++++++++++++++++++
fpga_interchange/site_router.cc | 82 +++++++++-----
7 files changed, 470 insertions(+), 42 deletions(-)
create mode 100644 fpga_interchange/site_lut_mapping_cache.cc
create mode 100644 fpga_interchange/site_lut_mapping_cache.h
(limited to 'fpga_interchange')
diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc
index 901725d4..33720e98 100644
--- a/fpga_interchange/arch.cc
+++ b/fpga_interchange/arch.cc
@@ -813,6 +813,10 @@ bool Arch::place()
getCtx()->attrs[getCtx()->id("step")] = std::string("place");
archInfoToAttributes();
+ // Print site LUT mapping caching stats
+ log_info("Site LUT mapping cache miss ratio: %.1f%%\n",
+ getCtx()->site_lut_mapping_cache.getMissRatio() * 100.0f);
+
getCtx()->check();
return true;
@@ -836,6 +840,9 @@ static void prepare_sites_for_routing(Context *ctx)
// pins to ensure a routeable pin choice.
ctx->site_routing_cache.clear();
+ // Clear the LUT mapping cache
+ ctx->site_lut_mapping_cache.clear();
+
// Have site router bind site routing (via bindPip and bindWire).
// This is important so that the pseudo pips are correctly blocked prior
// to handing the design to the generalized router algorithms.
diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h
index 896a603a..de7232d4 100644
--- a/fpga_interchange/arch.h
+++ b/fpga_interchange/arch.h
@@ -41,6 +41,7 @@
#include "pseudo_pip_model.h"
#include "site_router.h"
#include "site_routing_cache.h"
+#include "site_lut_mapping_cache.h"
NEXTPNR_NAMESPACE_BEGIN
@@ -1130,6 +1131,7 @@ struct Arch : ArchAPI<ArchRanges>
Lookahead lookahead;
mutable RouteNodeStorage node_storage;
mutable SiteRoutingCache site_routing_cache;
+ mutable SiteLutMappingCache site_lut_mapping_cache;
bool disallow_site_routing;
CellParameters cell_parameters;
diff --git a/fpga_interchange/luts.cc b/fpga_interchange/luts.cc
index 0156d379..2ac3b6da 100644
--- a/fpga_interchange/luts.cc
+++ b/fpga_interchange/luts.cc
@@ -22,6 +22,8 @@
#include "log.h"
#include "nextpnr.h"
+#include "site_lut_mapping_cache.h"
+
//#define DEBUG_LUT_ROTATION
NEXTPNR_NAMESPACE_BEGIN
@@ -253,7 +255,7 @@ uint32_t LutMapper::check_wires(const std::vector<std::vector<int32_t>> &bel_to_
return vcc_mask;
}
-bool LutMapper::remap_luts(const Context *ctx, pool<const LutBel *, hash_ptr_ops> *blocked_luts)
+bool LutMapper::remap_luts(const Context *ctx, SiteLutMappingResult* lut_mapping, pool<const LutBel *, hash_ptr_ops> *blocked_luts)
{
dict<NetInfo *, LutPin, hash_ptr_ops> lut_pin_map;
std::vector<const LutBel *> lut_bels;
@@ -377,6 +379,94 @@ bool LutMapper::remap_luts(const Context *ctx, pool<const LutBel *, hash_ptr_ops
}
}
+ // Not all LUT inputs are used
+ uint32_t vcc_pins = 0;
+ if (cells.size() != element.lut_bels.size()) {
+ // Look to see if wires can be run from element inputs to unused
+ // outputs. If not, block the BEL pin by tying to VCC.
+ //
+ // FIXME: The assumption is that unused pins are tied VCC.
+ // This is not generally true.
+ //
+ // Use Arch::prefered_constant_net_type to determine what
+ // constant net should be used for unused pins.
+ vcc_pins = check_wires(bel_to_cell_pin_remaps, lut_bels, used_pins, blocked_luts);
+#if defined(DEBUG_LUT_ROTATION)
+ log_info("vcc_pins = 0x%x", vcc_pins);
+ for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
+ CellInfo *cell = cells[cell_idx];
+ log(", %s => %s", ctx->nameOfBel(cell->bel), cell->name.c_str(ctx));
+ }
+ log("\n");
+#endif
+ }
+
+ // Fill in the LUT mapping result
+
+ // Push new cell -> BEL pin maps out to cells now that equations have been
+ // verified!
+ lut_mapping->cells.reserve(cells.size());
+ for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
+ CellInfo *cellInfo = cells[cell_idx];
+ auto &lutBel = *lut_bels[cell_idx];
+
+ // Add the cell data
+ SiteLutMappingResult::Cell cell;
+ cell.belIndex = cellInfo->bel.index;
+
+ // Cell to BEL pin map
+ for (size_t pin_idx = 0; pin_idx < cellInfo->lut_cell.pins.size(); ++pin_idx) {
+ IdString cellPin = cellInfo->lut_cell.pins[pin_idx];
+ IdString belPin = lutBel.pins[cell_to_bel_pin_remaps[cell_idx][pin_idx]];
+ cell.belPins[cellPin] = belPin;
+ }
+
+ cell.lutCell.vcc_pins.clear();
+
+ // All LUT inputs used
+ if (cells.size() == element.lut_bels.size()) {
+ for (size_t bel_pin_idx = 0; bel_pin_idx < lutBel.pins.size(); ++bel_pin_idx) {
+ if ((used_pins & (1 << bel_pin_idx)) == 0) {
+ NPNR_ASSERT(bel_to_cell_pin_remaps[cell_idx][bel_pin_idx] == -1);
+ cell.lutCell.vcc_pins.emplace(lutBel.pins.at(bel_pin_idx));
+ }
+ }
+ }
+ // Only some LUT inputs used
+ else {
+ for (size_t bel_pin_idx = 0; bel_pin_idx < lutBel.pins.size(); ++bel_pin_idx) {
+ if ((vcc_pins & (1 << bel_pin_idx)) != 0) {
+ NPNR_ASSERT(bel_to_cell_pin_remaps[cell_idx][bel_pin_idx] == -1);
+ auto pin = lutBel.pins.at(bel_pin_idx);
+ cell.lutCell.vcc_pins.emplace(pin);
+ }
+ }
+ }
+
+ lut_mapping->cells.push_back(cell);
+ }
+
+/*
+#ifdef DEBUG_LUT_ROTATION
+ log_info("Final mapping:\n");
+ for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
+ CellInfo *cell = cells[cell_idx];
+ for (auto &cell_pin_pair : cell->cell_bel_pins) {
+ log_info("%s %s %s =>", cell->type.c_str(ctx), cell->name.c_str(ctx), cell_pin_pair.first.c_str(ctx));
+ for (auto bel_pin : cell_pin_pair.second) {
+ log(" %s", bel_pin.c_str(ctx));
+ }
+ log("\n");
+ }
+ }
+#endif
+*/
+
+
+
+
+/*
+
// Push new cell -> BEL pin maps out to cells now that equations have been
// verified!
for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
@@ -434,20 +524,7 @@ bool LutMapper::remap_luts(const Context *ctx, pool<const LutBel *, hash_ptr_ops
}
}
}
-
-#ifdef DEBUG_LUT_ROTATION
- log_info("Final mapping:\n");
- for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
- CellInfo *cell = cells[cell_idx];
- for (auto &cell_pin_pair : cell->cell_bel_pins) {
- log_info("%s %s %s =>", cell->type.c_str(ctx), cell->name.c_str(ctx), cell_pin_pair.first.c_str(ctx));
- for (auto bel_pin : cell_pin_pair.second) {
- log(" %s", bel_pin.c_str(ctx));
- }
- log("\n");
- }
- }
-#endif
+*/
return true;
}
diff --git a/fpga_interchange/luts.h b/fpga_interchange/luts.h
index cbb817c9..7b6ce758 100644
--- a/fpga_interchange/luts.h
+++ b/fpga_interchange/luts.h
@@ -31,6 +31,8 @@ NEXTPNR_NAMESPACE_BEGIN
struct CellInfo;
struct Context;
+struct SiteLutMappingResult;
+
enum LogicLevel
{
LL_Zero,
@@ -66,6 +68,14 @@ struct LutBel
int32_t max_pin;
};
+struct SiteLutMapping
+{
+ struct LutCellMapping {
+ LutCell lut_cell;
+ };
+};
+
+
// Work forward from cell definition and cell -> bel pin map and check that
// equation is valid.
void check_equation(const LutCell &lut_cell, const dict<IdString, IdString> &cell_to_bel_map, const LutBel &lut_bel,
@@ -89,7 +99,7 @@ struct LutMapper
std::vector<CellInfo *> cells;
- bool remap_luts(const Context *ctx, pool<const LutBel *, hash_ptr_ops> *blocked_luts);
+ bool remap_luts(const Context *ctx, SiteLutMappingResult* lut_mapping, pool<const LutBel *, hash_ptr_ops> *blocked_luts);
// Determine which wires given the current mapping must be tied to the
// default constant.
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<CellInfo*> 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<IdString, int32_t> 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<Context*>(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
+
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<IdString, int32_t> 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<Cell> 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<IdString, IdString> belPins; // Cell to BEL pin mapping
+ };
+
+ bool isValid; // Validity flag
+ std::vector<Cell> cells; // Cell data
+
+ pool<std::pair<IdString, IdString>> 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<SiteLutMappingKey, SiteLutMappingResult> cache_;
+
+ size_t numHits = 0;
+ size_t numMisses = 0;
+};
+
+
+NEXTPNR_NAMESPACE_END
+
+#endif /* SITE_LUT_MAPPING_CACHE_H */
diff --git a/fpga_interchange/site_router.cc b/fpga_interchange/site_router.cc
index 92176d86..bcfe4539 100644
--- a/fpga_interchange/site_router.cc
+++ b/fpga_interchange/site_router.cc
@@ -1041,42 +1041,71 @@ static void apply_routing(Context *ctx, const SiteArch &site_arch, pool<std::pai
static bool map_luts_in_site(const SiteInformation &site_info, pool<std::pair<IdString, IdString>> *blocked_wires)
{
const Context *ctx = site_info.ctx;
- const std::vector<LutElement> &lut_elements = ctx->lut_elements.at(site_info.tile_type);
- std::vector<LutMapper> lut_mappers;
- lut_mappers.reserve(lut_elements.size());
- for (size_t i = 0; i < lut_elements.size(); ++i) {
- lut_mappers.push_back(LutMapper(lut_elements[i]));
- }
- for (CellInfo *cell : site_info.cells_in_site) {
- if (cell->lut_cell.pins.empty()) {
- continue;
- }
+ // Create a site LUT mapping key
+ SiteLutMappingKey key = SiteLutMappingKey::create(site_info);
- BelId bel = cell->bel;
- const auto &bel_data = bel_info(ctx->chip_info, bel);
- if (bel_data.lut_element != -1) {
- lut_mappers[bel_data.lut_element].cells.push_back(cell);
- }
- }
+ // Get the solution from cache. If not found then compute it
+ SiteLutMappingResult lutMapping;
+ if (!ctx->site_lut_mapping_cache.get(key, &lutMapping)) {
- blocked_wires->clear();
- for (LutMapper lut_mapper : lut_mappers) {
- if (lut_mapper.cells.empty()) {
- continue;
+ const std::vector<LutElement> &lut_elements = ctx->lut_elements.at(site_info.tile_type);
+ std::vector<LutMapper> lut_mappers;
+ lut_mappers.reserve(lut_elements.size());
+ for (size_t i = 0; i < lut_elements.size(); ++i) {
+ lut_mappers.push_back(LutMapper(lut_elements[i]));
}
- pool<const LutBel *, hash_ptr_ops> blocked_luts;
- if (!lut_mapper.remap_luts(ctx, &blocked_luts)) {
- return false;
+ for (CellInfo *cell : site_info.cells_in_site) {
+ if (cell->lut_cell.pins.empty()) {
+ continue;
+ }
+
+ BelId bel = cell->bel;
+ const auto &bel_data = bel_info(ctx->chip_info, bel);
+ if (bel_data.lut_element != -1) {
+ lut_mappers[bel_data.lut_element].cells.push_back(cell);
+ }
}
- for (const LutBel *lut_bel : blocked_luts) {
- blocked_wires->emplace(std::make_pair(lut_bel->name, lut_bel->output_pin));
+ bool res = true;
+
+ lutMapping.blockedWires.clear();
+ for (LutMapper lut_mapper : lut_mappers) {
+ if (lut_mapper.cells.empty()) {
+ continue;
+ }
+
+ pool<const LutBel *, hash_ptr_ops> blocked_luts;
+ if (!lut_mapper.remap_luts(ctx, &lutMapping, &blocked_luts)) {
+ res = false;
+ break;
+ }
+
+ for (const LutBel *lut_bel : blocked_luts) {
+ lutMapping.blockedWires.emplace(std::make_pair(lut_bel->name, lut_bel->output_pin));
+ }
}
+
+ lutMapping.isValid = res;
+
+ // Add the solution to the cache
+ ctx->site_lut_mapping_cache.add(key, lutMapping);
}
- return true;
+ // Apply the solution if valid
+ if (lutMapping.isValid) {
+
+ lutMapping.apply(site_info);
+
+ blocked_wires->clear();
+ blocked_wires->insert(
+ lutMapping.blockedWires.begin(),
+ lutMapping.blockedWires.end()
+ );
+ }
+
+ return lutMapping.isValid;
}
// Block outputs of unavailable LUTs to prevent site router from using them.
@@ -1246,6 +1275,7 @@ bool SiteRouter::checkSiteRouting(const Context *ctx, const TileStatus &tile_sta
// Because site routing checks are expensive, cache them.
// SiteRouter::bindBel/unbindBel should correctly invalid the cache by
// setting dirty=true.
+
if (!dirty) {
return site_ok;
}
--
cgit v1.2.3
From 044c9ba2d4e66cf34214fdfd62fb90a872da64b1 Mon Sep 17 00:00:00 2001
From: Maciej Kurc <mkurc@antmicro.com>
Date: Fri, 16 Jul 2021 13:28:40 +0200
Subject: LUT mapping cache optimizations 1
Signed-off-by: Maciej Kurc <mkurc@antmicro.com>
---
fpga_interchange/site_lut_mapping_cache.cc | 28 ++++++++++++----
fpga_interchange/site_lut_mapping_cache.h | 52 +++++++++++++++---------------
2 files changed, 48 insertions(+), 32 deletions(-)
(limited to 'fpga_interchange')
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];
}
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<IdString, int32_t> 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<Cell> 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<MAX_LUT_INPUTS; ++i) {
+ hash_ = mkhash(hash_, cell.conns[i]);
+ }
+ }
+ }
bool operator == (const SiteLutMappingKey &other) const {
- return (tileType == other.tileType) &&
+ return (hash_ == other.hash_) &&
+ (tileType == other.tileType) &&
(siteType == other.siteType) &&
(cells == other.cells);
}
bool operator != (const SiteLutMappingKey &other) const {
- return (tileType != other.tileType) ||
+ return (hash_ != other.hash_) ||
+ (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;
+ return hash_;
}
};
--
cgit v1.2.3
From 0336f55b16373874cf4ac5661d9724d0a358454c Mon Sep 17 00:00:00 2001
From: Maciej Kurc <mkurc@antmicro.com>
Date: Fri, 16 Jul 2021 13:55:19 +0200
Subject: LUT mapping ceche optimizations 2
Signed-off-by: Maciej Kurc <mkurc@antmicro.com>
---
fpga_interchange/luts.cc | 80 ------------------------------
fpga_interchange/site_lut_mapping_cache.cc | 9 ++--
fpga_interchange/site_lut_mapping_cache.h | 21 +++++---
3 files changed, 17 insertions(+), 93 deletions(-)
(limited to 'fpga_interchange')
diff --git a/fpga_interchange/luts.cc b/fpga_interchange/luts.cc
index 2ac3b6da..9c68739e 100644
--- a/fpga_interchange/luts.cc
+++ b/fpga_interchange/luts.cc
@@ -446,86 +446,6 @@ bool LutMapper::remap_luts(const Context *ctx, SiteLutMappingResult* lut_mapping
lut_mapping->cells.push_back(cell);
}
-/*
-#ifdef DEBUG_LUT_ROTATION
- log_info("Final mapping:\n");
- for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
- CellInfo *cell = cells[cell_idx];
- for (auto &cell_pin_pair : cell->cell_bel_pins) {
- log_info("%s %s %s =>", cell->type.c_str(ctx), cell->name.c_str(ctx), cell_pin_pair.first.c_str(ctx));
- for (auto bel_pin : cell_pin_pair.second) {
- log(" %s", bel_pin.c_str(ctx));
- }
- log("\n");
- }
- }
-#endif
-*/
-
-
-
-
-/*
-
- // Push new cell -> BEL pin maps out to cells now that equations have been
- // verified!
- for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
- CellInfo *cell = cells[cell_idx];
- auto &lut_bel = *lut_bels[cell_idx];
-
- for (size_t pin_idx = 0; pin_idx < cell->lut_cell.pins.size(); ++pin_idx) {
- auto &bel_pins = cell->cell_bel_pins[cell->lut_cell.pins[pin_idx]];
- bel_pins.clear();
- bel_pins.push_back(lut_bel.pins[cell_to_bel_pin_remaps[cell_idx][pin_idx]]);
- }
- }
-
- if (cells.size() == element.lut_bels.size()) {
- for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
- CellInfo *cell = cells[cell_idx];
- auto &lut_bel = *lut_bels[cell_idx];
- cell->lut_cell.vcc_pins.clear();
- for (size_t bel_pin_idx = 0; bel_pin_idx < lut_bel.pins.size(); ++bel_pin_idx) {
- if ((used_pins & (1 << bel_pin_idx)) == 0) {
- NPNR_ASSERT(bel_to_cell_pin_remaps[cell_idx][bel_pin_idx] == -1);
- cell->lut_cell.vcc_pins.emplace(lut_bel.pins.at(bel_pin_idx));
- }
- }
- }
- } else {
- // Look to see if wires can be run from element inputs to unused
- // outputs. If not, block the BEL pin by tying to VCC.
- //
- // FIXME: The assumption is that unused pins are tied VCC.
- // This is not generally true.
- //
- // Use Arch::prefered_constant_net_type to determine what
- // constant net should be used for unused pins.
- uint32_t vcc_pins = check_wires(bel_to_cell_pin_remaps, lut_bels, used_pins, blocked_luts);
-#if defined(DEBUG_LUT_ROTATION)
- log_info("vcc_pins = 0x%x", vcc_pins);
- for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
- CellInfo *cell = cells[cell_idx];
- log(", %s => %s", ctx->nameOfBel(cell->bel), cell->name.c_str(ctx));
- }
- log("\n");
-#endif
-
- for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
- CellInfo *cell = cells[cell_idx];
- auto &lut_bel = *lut_bels[cell_idx];
- cell->lut_cell.vcc_pins.clear();
- for (size_t bel_pin_idx = 0; bel_pin_idx < lut_bel.pins.size(); ++bel_pin_idx) {
- if ((vcc_pins & (1 << bel_pin_idx)) != 0) {
- NPNR_ASSERT(bel_to_cell_pin_remaps[cell_idx][bel_pin_idx] == -1);
- auto pin = lut_bel.pins.at(bel_pin_idx);
- cell->lut_cell.vcc_pins.emplace(pin);
- }
- }
- }
- }
-*/
-
return true;
}
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<IdString, int32_t> 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
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<Cell> 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<numCells; ++j) {
+ const auto& cell = cells[j];
hash_ = mkhash(hash_, cell.type.index);
hash_ = mkhash(hash_, cell.belIndex);
for (size_t i=0; i<MAX_LUT_INPUTS; ++i) {
@@ -68,14 +71,16 @@ struct SiteLutMappingKey {
return (hash_ == other.hash_) &&
(tileType == other.tileType) &&
(siteType == other.siteType) &&
- (cells == other.cells);
+ (numCells == other.numCells) &&
+ (!memcmp(cells, other.cells, sizeof(Cell) * numCells));
}
bool operator != (const SiteLutMappingKey &other) const {
return (hash_ != other.hash_) ||
(tileType != other.tileType) ||
(siteType != other.siteType) ||
- (cells != other.cells);
+ (numCells != other.numCells) ||
+ (memcmp(cells, other.cells, sizeof(Cell) * numCells));
}
unsigned int hash () const {
--
cgit v1.2.3
From 857961a6bb9302847ecf605971015f1610dae476 Mon Sep 17 00:00:00 2001
From: Maciej Kurc <mkurc@antmicro.com>
Date: Fri, 16 Jul 2021 14:55:45 +0200
Subject: Migrated C arrays to std::array containers.
Signed-off-by: Maciej Kurc <mkurc@antmicro.com>
---
fpga_interchange/site_lut_mapping_cache.cc | 3 +--
fpga_interchange/site_lut_mapping_cache.h | 37 ++++++++++++++++++++++++------
2 files changed, 31 insertions(+), 9 deletions(-)
(limited to 'fpga_interchange')
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) {
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<int32_t, MAX_LUT_INPUTS> 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<Cell, MAX_LUT_CELLS> 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<numCells; ++i) {
+ if (cells[i] != other.cells[i]) {
+ return false;
+ }
+ }
+ return true;
+ }
+
bool operator == (const SiteLutMappingKey &other) const {
return (hash_ == other.hash_) &&
(tileType == other.tileType) &&
(siteType == other.siteType) &&
- (numCells == other.numCells) &&
- (!memcmp(cells, other.cells, sizeof(Cell) * numCells));
+ compareCells(other);
}
bool operator != (const SiteLutMappingKey &other) const {
return (hash_ != other.hash_) ||
(tileType != other.tileType) ||
(siteType != other.siteType) ||
- (numCells != other.numCells) ||
- (memcmp(cells, other.cells, sizeof(Cell) * numCells));
+ !compareCells(other);
}
unsigned int hash () const {
--
cgit v1.2.3
From c95aa86a8e4fe290bdb030977b7ca40e619a0c30 Mon Sep 17 00:00:00 2001
From: Maciej Kurc <mkurc@antmicro.com>
Date: Fri, 16 Jul 2021 15:16:31 +0200
Subject: Fixed assertion typos
Signed-off-by: Maciej Kurc <mkurc@antmicro.com>
---
fpga_interchange/site_lut_mapping_cache.cc | 4 ++--
1 file changed, 2 insertions(+), 2 deletions(-)
(limited to 'fpga_interchange')
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 <mkurc@antmicro.com>
Date: Fri, 16 Jul 2021 15:53:00 +0200
Subject: Added computing and reporting LUT mapping cache size
Signed-off-by: Maciej Kurc <mkurc@antmicro.com>
---
fpga_interchange/site_lut_mapping_cache.cc | 15 +++++++++++++++
fpga_interchange/site_lut_mapping_cache.h | 22 ++++++++++++++++++++++
2 files changed, 37 insertions(+)
(limited to 'fpga_interchange')
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<IdString, IdString>);
+
+ 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,
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<SiteLutMappingKey, SiteLutMappingResult> cache_;
--
cgit v1.2.3
From 8fc16a57c9dee5e7e0f83752a62612f70f18a38e Mon Sep 17 00:00:00 2001
From: Maciej Kurc <mkurc@antmicro.com>
Date: Fri, 16 Jul 2021 16:01:21 +0200
Subject: Added more code comments, formatted the code
Signed-off-by: Maciej Kurc <mkurc@antmicro.com>
---
fpga_interchange/arch.cc | 6 +-
fpga_interchange/luts.cc | 5 +-
fpga_interchange/luts.h | 7 +-
fpga_interchange/site_lut_mapping_cache.cc | 69 ++++++-------
fpga_interchange/site_lut_mapping_cache.h | 155 +++++++++++++++--------------
fpga_interchange/site_router.cc | 5 +-
6 files changed, 124 insertions(+), 123 deletions(-)
(limited to 'fpga_interchange')
diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc
index 33720e98..64eef2ad 100644
--- a/fpga_interchange/arch.cc
+++ b/fpga_interchange/arch.cc
@@ -814,8 +814,10 @@ bool Arch::place()
archInfoToAttributes();
// Print site LUT mapping caching stats
- log_info("Site LUT mapping cache miss ratio: %.1f%%\n",
- getCtx()->site_lut_mapping_cache.getMissRatio() * 100.0f);
+ log_info("Site LUT mapping cache stats:\n");
+ log_info(" miss ratio: %.1f%%\n", getCtx()->site_lut_mapping_cache.getMissRatio() * 100.0f);
+ log_info(" peak size : %zuMB (%zu items)\n", getCtx()->site_lut_mapping_cache.getSizeMB(),
+ getCtx()->site_lut_mapping_cache.getCount());
getCtx()->check();
diff --git a/fpga_interchange/luts.cc b/fpga_interchange/luts.cc
index 9c68739e..d9e17ca9 100644
--- a/fpga_interchange/luts.cc
+++ b/fpga_interchange/luts.cc
@@ -255,7 +255,8 @@ uint32_t LutMapper::check_wires(const std::vector<std::vector<int32_t>> &bel_to_
return vcc_mask;
}
-bool LutMapper::remap_luts(const Context *ctx, SiteLutMappingResult* lut_mapping, pool<const LutBel *, hash_ptr_ops> *blocked_luts)
+bool LutMapper::remap_luts(const Context *ctx, SiteLutMappingResult *lut_mapping,
+ pool<const LutBel *, hash_ptr_ops> *blocked_luts)
{
dict<NetInfo *, LutPin, hash_ptr_ops> lut_pin_map;
std::vector<const LutBel *> lut_bels;
@@ -417,7 +418,7 @@ bool LutMapper::remap_luts(const Context *ctx, SiteLutMappingResult* lut_mapping
// Cell to BEL pin map
for (size_t pin_idx = 0; pin_idx < cellInfo->lut_cell.pins.size(); ++pin_idx) {
IdString cellPin = cellInfo->lut_cell.pins[pin_idx];
- IdString belPin = lutBel.pins[cell_to_bel_pin_remaps[cell_idx][pin_idx]];
+ IdString belPin = lutBel.pins[cell_to_bel_pin_remaps[cell_idx][pin_idx]];
cell.belPins[cellPin] = belPin;
}
diff --git a/fpga_interchange/luts.h b/fpga_interchange/luts.h
index 7b6ce758..8f33507a 100644
--- a/fpga_interchange/luts.h
+++ b/fpga_interchange/luts.h
@@ -70,12 +70,12 @@ struct LutBel
struct SiteLutMapping
{
- struct LutCellMapping {
+ struct LutCellMapping
+ {
LutCell lut_cell;
};
};
-
// Work forward from cell definition and cell -> bel pin map and check that
// equation is valid.
void check_equation(const LutCell &lut_cell, const dict<IdString, IdString> &cell_to_bel_map, const LutBel &lut_bel,
@@ -99,7 +99,8 @@ struct LutMapper
std::vector<CellInfo *> cells;
- bool remap_luts(const Context *ctx, SiteLutMappingResult* lut_mapping, pool<const LutBel *, hash_ptr_ops> *blocked_luts);
+ bool remap_luts(const Context *ctx, SiteLutMappingResult *lut_mapping,
+ pool<const LutBel *, hash_ptr_ops> *blocked_luts);
// Determine which wires given the current mapping must be tied to the
// default constant.
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<CellInfo*> lutCells;
+ std::vector<CellInfo *> 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<IdString, int32_t> 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<Context*>(siteInfo.ctx);
+ Context *ctx = const_cast<Context *>(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<IdString, IdString>);
- 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
-
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<int32_t, MAX_LUT_INPUTS> 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<Cell, MAX_LUT_CELLS> 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<numCells; ++j) {
- const auto& cell = cells[j];
+ for (size_t j = 0; j < numCells; ++j) {
+ const auto &cell = cells[j];
hash_ = mkhash(hash_, cell.type.index);
hash_ = mkhash(hash_, cell.belIndex);
- for (size_t i=0; i<MAX_LUT_INPUTS; ++i) {
+ for (size_t i = 0; i < MAX_LUT_INPUTS; ++i) {
hash_ = mkhash(hash_, cell.conns[i]);
}
}
}
- bool compareCells (const SiteLutMappingKey &other) const {
+ // Compares cell data of this and other key
+ bool compareCells(const SiteLutMappingKey &other) const
+ {
if (numCells != other.numCells) {
return false;
}
- for (size_t i=0; i<numCells; ++i) {
+ for (size_t i = 0; i < numCells; ++i) {
if (cells[i] != other.cells[i]) {
return false;
}
@@ -96,68 +101,70 @@ struct SiteLutMappingKey {
return true;
}
- bool operator == (const SiteLutMappingKey &other) const {
- return (hash_ == other.hash_) &&
- (tileType == other.tileType) &&
- (siteType == other.siteType) &&
+ bool operator==(const SiteLutMappingKey &other) const
+ {
+ return (hash_ == other.hash_) && (tileType == other.tileType) && (siteType == other.siteType) &&
compareCells(other);
}
- bool operator != (const SiteLutMappingKey &other) const {
- return (hash_ != other.hash_) ||
- (tileType != other.tileType) ||
- (siteType != other.siteType) ||
+ bool operator!=(const SiteLutMappingKey &other) const
+ {
+ return (hash_ != other.hash_) || (tileType != other.tileType) || (siteType != other.siteType) ||
!compareCells(other);
}
- unsigned int hash () const {
- return hash_;
- }
+ unsigned int hash() const { return hash_; }
};
// Site LUT mapping result data
-struct SiteLutMappingResult {
+struct SiteLutMappingResult
+{
// LUT cell data
- struct Cell {
- int32_t belIndex; // BEL in tile index
- LutCell lutCell; // LUT mapping data
- dict<IdString, IdString> belPins; // Cell to BEL pin mapping
+ struct Cell
+ {
+ int32_t belIndex; // BEL in tile index
+ LutCell lutCell; // LUT mapping data
+ dict<IdString, IdString> belPins; // Cell to BEL pin mapping
};
- bool isValid; // Validity flag
- std::vector<Cell> cells; // Cell data
+ bool isValid; // Validity flag
+ std::vector<Cell> cells; // Cell data
- pool<std::pair<IdString, IdString>> blockedWires;
+ pool<std::pair<IdString, IdString>> 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<SiteLutMappingKey, SiteLutMappingResult> cache_;
+ private:
+ dict<SiteLutMappingKey, SiteLutMappingResult> 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 */
diff --git a/fpga_interchange/site_router.cc b/fpga_interchange/site_router.cc
index bcfe4539..4094b331 100644
--- a/fpga_interchange/site_router.cc
+++ b/fpga_interchange/site_router.cc
@@ -1099,10 +1099,7 @@ static bool map_luts_in_site(const SiteInformation &site_info, pool<std::pair<Id
lutMapping.apply(site_info);
blocked_wires->clear();
- blocked_wires->insert(
- lutMapping.blockedWires.begin(),
- lutMapping.blockedWires.end()
- );
+ blocked_wires->insert(lutMapping.blockedWires.begin(), lutMapping.blockedWires.end());
}
return lutMapping.isValid;
--
cgit v1.2.3
From 580a45485afe48a77272f44f8aa99875cdd4d441 Mon Sep 17 00:00:00 2001
From: Maciej Kurc <mkurc@antmicro.com>
Date: Thu, 22 Jul 2021 14:07:35 +0200
Subject: Added an option to disable the LUT mapping cache
Signed-off-by: Maciej Kurc <mkurc@antmicro.com>
---
fpga_interchange/arch.cc | 10 ++++++----
fpga_interchange/arch.h | 3 ++-
fpga_interchange/main.cc | 2 ++
fpga_interchange/site_lut_mapping_cache.h | 2 +-
fpga_interchange/site_router.cc | 7 +++++--
5 files changed, 16 insertions(+), 8 deletions(-)
(limited to 'fpga_interchange')
diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc
index 64eef2ad..3b0572fa 100644
--- a/fpga_interchange/arch.cc
+++ b/fpga_interchange/arch.cc
@@ -814,10 +814,12 @@ bool Arch::place()
archInfoToAttributes();
// Print site LUT mapping caching stats
- log_info("Site LUT mapping cache stats:\n");
- log_info(" miss ratio: %.1f%%\n", getCtx()->site_lut_mapping_cache.getMissRatio() * 100.0f);
- log_info(" peak size : %zuMB (%zu items)\n", getCtx()->site_lut_mapping_cache.getSizeMB(),
- getCtx()->site_lut_mapping_cache.getCount());
+ if (!getCtx()->arch_args.disable_lut_mapping_cache) {
+ log_info("Site LUT mapping cache stats:\n");
+ log_info(" miss ratio: %.1f%%\n", getCtx()->site_lut_mapping_cache.getMissRatio() * 100.0f);
+ log_info(" peak size : %zuMB (%zu items)\n", getCtx()->site_lut_mapping_cache.getSizeMB(),
+ getCtx()->site_lut_mapping_cache.getCount());
+ }
getCtx()->check();
diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h
index de7232d4..36f6a7dc 100644
--- a/fpga_interchange/arch.h
+++ b/fpga_interchange/arch.h
@@ -39,9 +39,9 @@
#include "dedicated_interconnect.h"
#include "lookahead.h"
#include "pseudo_pip_model.h"
+#include "site_lut_mapping_cache.h"
#include "site_router.h"
#include "site_routing_cache.h"
-#include "site_lut_mapping_cache.h"
NEXTPNR_NAMESPACE_BEGIN
@@ -51,6 +51,7 @@ struct ArchArgs
std::string package;
bool rebuild_lookahead;
bool dont_write_lookahead;
+ bool disable_lut_mapping_cache;
};
struct ArchRanges
diff --git a/fpga_interchange/main.cc b/fpga_interchange/main.cc
index 64a15e62..5423c17d 100644
--- a/fpga_interchange/main.cc
+++ b/fpga_interchange/main.cc
@@ -57,6 +57,7 @@ po::options_description FpgaInterchangeCommandHandler::getArchOptions()
specific.add_options()("package", po::value<std::string>(), "Package to use");
specific.add_options()("rebuild-lookahead", "Ignore lookahead cache and rebuild");
specific.add_options()("dont-write-lookahead", "Don't write the lookahead file");
+ specific.add_options()("disable-lut-mapping-cache", "Disable caching of LUT mapping solutions in site router");
return specific;
}
@@ -76,6 +77,7 @@ std::unique_ptr<Context> FpgaInterchangeCommandHandler::createContext(dict<std::
ArchArgs chipArgs;
chipArgs.rebuild_lookahead = vm.count("rebuild_lookahead") != 0;
chipArgs.dont_write_lookahead = vm.count("dont_write_lookahead") != 0;
+ chipArgs.disable_lut_mapping_cache = vm.count("disable-lut-mapping-cache") != 0;
if (!vm.count("chipdb")) {
log_error("chip database binary must be provided\n");
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
diff --git a/fpga_interchange/site_router.cc b/fpga_interchange/site_router.cc
index 4094b331..820b8d68 100644
--- a/fpga_interchange/site_router.cc
+++ b/fpga_interchange/site_router.cc
@@ -1041,13 +1041,14 @@ static void apply_routing(Context *ctx, const SiteArch &site_arch, pool<std::pai
static bool map_luts_in_site(const SiteInformation &site_info, pool<std::pair<IdString, IdString>> *blocked_wires)
{
const Context *ctx = site_info.ctx;
+ bool enable_cache = !ctx->arch_args.disable_lut_mapping_cache;
// Create a site LUT mapping key
SiteLutMappingKey key = SiteLutMappingKey::create(site_info);
// Get the solution from cache. If not found then compute it
SiteLutMappingResult lutMapping;
- if (!ctx->site_lut_mapping_cache.get(key, &lutMapping)) {
+ if (!enable_cache || !ctx->site_lut_mapping_cache.get(key, &lutMapping)) {
const std::vector<LutElement> &lut_elements = ctx->lut_elements.at(site_info.tile_type);
std::vector<LutMapper> lut_mappers;
@@ -1090,7 +1091,9 @@ static bool map_luts_in_site(const SiteInformation &site_info, pool<std::pair<Id
lutMapping.isValid = res;
// Add the solution to the cache
- ctx->site_lut_mapping_cache.add(key, lutMapping);
+ if (enable_cache) {
+ ctx->site_lut_mapping_cache.add(key, lutMapping);
+ }
}
// Apply the solution if valid
--
cgit v1.2.3