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/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 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 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> &bel_to_ return vcc_mask; } -bool LutMapper::remap_luts(const Context *ctx, pool *blocked_luts) +bool LutMapper::remap_luts(const Context *ctx, SiteLutMappingResult* lut_mapping, pool *blocked_luts) { dict lut_pin_map; std::vector lut_bels; @@ -377,6 +379,94 @@ bool LutMapper::remap_luts(const Context *ctx, pool %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, poolcell_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 &cell_to_bel_map, const LutBel &lut_bel, @@ -89,7 +99,7 @@ struct LutMapper std::vector cells; - bool remap_luts(const Context *ctx, pool *blocked_luts); + bool remap_luts(const Context *ctx, SiteLutMappingResult* lut_mapping, pool *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 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 + 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 */ 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> *blocked_wires) { const Context *ctx = site_info.ctx; - const std::vector &lut_elements = ctx->lut_elements.at(site_info.tile_type); - std::vector 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 &lut_elements = ctx->lut_elements.at(site_info.tile_type); + std::vector 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 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 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