diff options
author | Clifford Wolf <clifford@clifford.at> | 2018-06-13 16:52:21 +0200 |
---|---|---|
committer | Clifford Wolf <clifford@clifford.at> | 2018-06-13 16:52:21 +0200 |
commit | aa4fedfd54c111383608857e4c5ba30330bdfbbe (patch) | |
tree | 1d5fe66a6594d003874a648c644723b486462d2f | |
parent | 4a85cd57c0fabfba5b3851361c000ae801cb43f7 (diff) | |
download | nextpnr-aa4fedfd54c111383608857e4c5ba30330bdfbbe.tar.gz nextpnr-aa4fedfd54c111383608857e4c5ba30330bdfbbe.tar.bz2 nextpnr-aa4fedfd54c111383608857e4c5ba30330bdfbbe.zip |
Add A*-like optimizations to router
Signed-off-by: Clifford Wolf <clifford@clifford.at>
-rw-r--r-- | common/place.cc | 2 | ||||
-rw-r--r-- | common/route.cc | 87 | ||||
-rw-r--r-- | common/route.h | 2 | ||||
-rw-r--r-- | ice40/cells.cc | 3 | ||||
-rw-r--r-- | ice40/cells.h | 2 | ||||
-rw-r--r-- | ice40/chip.cc | 2 | ||||
-rw-r--r-- | ice40/main.cc | 8 | ||||
-rw-r--r-- | ice40/pack.cc | 22 |
8 files changed, 97 insertions, 31 deletions
diff --git a/common/place.cc b/common/place.cc index 007fc748..92c09e78 100644 --- a/common/place.cc +++ b/common/place.cc @@ -40,6 +40,8 @@ void place_design(Design *design) std::set<IdString>::iterator not_found, element; std::set<BelType> used_bels; + log_info("Placing..\n"); + // Initial constraints placer for (auto cell_entry : design->cells) { CellInfo *cell = cell_entry.second; diff --git a/common/route.cc b/common/route.cc index ca76024f..4af5f60f 100644 --- a/common/route.cc +++ b/common/route.cc @@ -17,6 +17,7 @@ * */ +#include <cmath> #include <queue> #include "log.h" @@ -28,21 +29,26 @@ struct QueuedWire { WireId wire; PipId pip; - DelayInfo delay; + + float delay = 0, togo = 0; struct Greater { bool operator()(const QueuedWire &lhs, const QueuedWire &rhs) const noexcept { - return lhs.delay.avgDelay() > rhs.delay.avgDelay(); + return (lhs.delay + lhs.togo) > (rhs.delay + rhs.togo); } }; }; -void route_design(Design *design) +void route_design(Design *design, bool verbose) { auto &chip = design->chip; + int itercnt = 0, netcnt = 0; + float maxDelay = 0.0; + + log_info("Routing..\n"); for (auto &net_it : design->nets) { auto net_name = net_it.first; @@ -51,17 +57,22 @@ void route_design(Design *design) if (net_info->driver.cell == nullptr) continue; - log("Routing net %s.\n", net_name.c_str()); + if (verbose) + log("Routing net %s.\n", net_name.c_str()); + netcnt++; - log(" Source: %s.%s.\n", net_info->driver.cell->name.c_str(), - net_info->driver.port.c_str()); + if (verbose) + log(" Source: %s.%s.\n", net_info->driver.cell->name.c_str(), + net_info->driver.port.c_str()); auto src_bel = net_info->driver.cell->bel; + auto src_pos = chip.getBelPosition(src_bel); if (src_bel == BelId()) log_error("Source cell is not mapped to a bel.\n"); - log(" Source bel: %s\n", chip.getBelName(src_bel).c_str()); + if (verbose) + log(" Source bel: %s\n", chip.getBelName(src_bel).c_str()); auto src_wire = chip.getWireBelPin( src_bel, portPinFromId(net_info->driver.port)); @@ -70,7 +81,8 @@ void route_design(Design *design) log_error("No wire found for port %s on source bel.\n", net_info->driver.port.c_str()); - log(" Source wire: %s\n", chip.getWireName(src_wire).c_str()); + if (verbose) + log(" Source wire: %s\n", chip.getWireName(src_wire).c_str()); std::unordered_map<WireId, DelayInfo> src_wires; src_wires[src_wire] = DelayInfo(); @@ -78,15 +90,22 @@ void route_design(Design *design) chip.bindWire(src_wire, net_name); for (auto &user_it : net_info->users) { - log(" Route to: %s.%s.\n", user_it.cell->name.c_str(), - user_it.port.c_str()); + if (verbose) + log(" Route to: %s.%s.\n", user_it.cell->name.c_str(), + user_it.port.c_str()); auto dst_bel = user_it.cell->bel; + auto dst_pos = chip.getBelPosition(dst_bel); if (dst_bel == BelId()) log_error("Destination cell is not mapped to a bel.\n"); - log(" Destination bel: %s\n", chip.getBelName(dst_bel).c_str()); + if (verbose) { + log(" Destination bel: %s\n", + chip.getBelName(dst_bel).c_str()); + log(" Path delay estimate: %.2f\n", + chip.estimateDelay(src_pos, dst_pos)); + } auto dst_wire = chip.getWireBelPin(dst_bel, portPinFromId(user_it.port)); @@ -95,8 +114,9 @@ void route_design(Design *design) log_error("No wire found for port %s on destination bel.\n", user_it.port.c_str()); - log(" Destination wire: %s\n", - chip.getWireName(dst_wire).c_str()); + if (verbose) + log(" Destination wire: %s\n", + chip.getWireName(dst_wire).c_str()); std::unordered_map<WireId, QueuedWire> visited; std::priority_queue<QueuedWire, std::vector<QueuedWire>, @@ -107,13 +127,16 @@ void route_design(Design *design) QueuedWire qw; qw.wire = it.first; qw.pip = PipId(); - qw.delay = it.second; + qw.delay = it.second.avgDelay(); + qw.togo = chip.estimateDelay(chip.getWirePosition(qw.wire), + dst_pos); queue.push(qw); visited[qw.wire] = qw; } while (!queue.empty()) { + itercnt++; QueuedWire qw = queue.top(); queue.pop(); @@ -122,15 +145,28 @@ void route_design(Design *design) continue; WireId next_wire = chip.getPipDstWire(pip); + float next_delay = + qw.delay + chip.getPipDelay(pip).avgDelay(); + + if (visited.count(next_wire)) { + if (visited.at(next_wire).delay <= next_delay + 1e-3) + continue; + if (verbose) + log("Found better route to %s. Old vs new delay " + "estimate: %.2f %.2f\n", + chip.getWireName(next_wire).c_str(), + visited.at(next_wire).delay, next_delay); + } - if (visited.count(next_wire) || - !chip.checkWireAvail(next_wire)) + if (!chip.checkWireAvail(next_wire)) continue; QueuedWire next_qw; next_qw.wire = next_wire; next_qw.pip = pip; - next_qw.delay = qw.delay + chip.getPipDelay(pip); + next_qw.delay = next_delay; + next_qw.togo = chip.estimateDelay( + chip.getWirePosition(next_wire), dst_pos); visited[next_qw.wire] = next_qw; queue.push(next_qw); @@ -149,13 +185,19 @@ void route_design(Design *design) chip.getWireName(src_wire).c_str(), chip.getWireName(dst_wire).c_str()); - log(" Route (from destination to source):\n"); + if (verbose) + log(" Final path delay: %.2f\n", visited[dst_wire].delay); + maxDelay = fmaxf(maxDelay, visited[dst_wire].delay); + + if (verbose) + log(" Route (from destination to source):\n"); WireId cursor = dst_wire; while (1) { - log(" %8.2f %s\n", visited[cursor].delay.avgDelay(), - chip.getWireName(cursor).c_str()); + if (verbose) + log(" %8.2f %s\n", visited[cursor].delay, + chip.getWireName(cursor).c_str()); if (src_wires.count(cursor)) break; @@ -164,11 +206,14 @@ void route_design(Design *design) chip.bindWire(cursor, net_name); chip.bindPip(visited[cursor].pip, net_name); - src_wires[cursor] = visited[cursor].delay; + src_wires[cursor] = chip.getPipDelay(visited[cursor].pip); cursor = chip.getPipSrcWire(visited[cursor].pip); } } } + + log_info("routed %d nets, visited %d wires.\n", netcnt, itercnt); + log_info("longest path delay: %.2f\n", maxDelay); } NEXTPNR_NAMESPACE_END diff --git a/common/route.h b/common/route.h index d9c240b3..edb9a53e 100644 --- a/common/route.h +++ b/common/route.h @@ -24,7 +24,7 @@ NEXTPNR_NAMESPACE_BEGIN -extern void route_design(Design *design); +extern void route_design(Design *design, bool verbose = false); NEXTPNR_NAMESPACE_END diff --git a/ice40/cells.cc b/ice40/cells.cc index 604baccb..a8200d76 100644 --- a/ice40/cells.cc +++ b/ice40/cells.cc @@ -166,7 +166,8 @@ void nxio_to_sb(CellInfo *nxio, CellInfo *sbio) } } -bool is_global_net(NetInfo *net) { +bool is_global_net(NetInfo *net) +{ return bool(net_driven_by(net, is_gbuf, "GLOBAL_BUFFER_OUTPUT")); } diff --git a/ice40/cells.h b/ice40/cells.h index 660c7265..db0aa3d1 100644 --- a/ice40/cells.h +++ b/ice40/cells.h @@ -51,7 +51,7 @@ inline bool is_ff(const CellInfo *cell) inline bool is_sb_io(const CellInfo *cell) { return cell->type == "SB_IO"; } // Return true if a cell is a global buffer -inline bool is_gbuf(const CellInfo *cell) {return cell->type == "SB_GB"; } +inline bool is_gbuf(const CellInfo *cell) { return cell->type == "SB_GB"; } // Convert a SB_LUT primitive to (part of) an ICESTORM_LC, swapping ports // as needed. Set no_dff if a DFF is not being used, so that the output diff --git a/ice40/chip.cc b/ice40/chip.cc index 8bbdf5a4..87428339 100644 --- a/ice40/chip.cc +++ b/ice40/chip.cc @@ -304,7 +304,7 @@ PosInfo Chip::getPipPosition(PipId pip) const float Chip::estimateDelay(PosInfo src, PosInfo dst) const { - return fabsf(src.x - dst.x) + fabsf(src.x - dst.x); + return fabsf(src.x - dst.x) + fabsf(src.y - dst.y); } // ----------------------------------------------------------------------- diff --git a/ice40/main.cc b/ice40/main.cc index 8ccec77b..094e6a75 100644 --- a/ice40/main.cc +++ b/ice40/main.cc @@ -60,12 +60,14 @@ int main(int argc, char *argv[]) { namespace po = boost::program_options; int rc = 0; + bool verbose = false; std::string str; log_files.push_back(stdout); po::options_description options("Allowed options"); options.add_options()("help,h", "show help"); + options.add_options()("verbose,v", "verbose output"); options.add_options()("gui", "start gui"); options.add_options()("svg", "dump SVG file"); options.add_options()("pack-only", @@ -125,6 +127,10 @@ int main(int argc, char *argv[]) return 1; } + if (vm.count("verbose")) { + verbose = true; + } + ChipArgs chipArgs; if (vm.count("lp384")) { @@ -217,7 +223,7 @@ int main(int argc, char *argv[]) pack_design(&design); if (!vm.count("pack-only")) { place_design(&design); - route_design(&design); + route_design(&design, verbose); } } diff --git a/ice40/pack.cc b/ice40/pack.cc index e8876283..853ef8ca 100644 --- a/ice40/pack.cc +++ b/ice40/pack.cc @@ -30,6 +30,8 @@ NEXTPNR_NAMESPACE_BEGIN // Pack LUTs and LUT-FF pairs static void pack_lut_lutffs(Design *design) { + log_info("Packing LUT-FFs..\n"); + std::unordered_set<IdString> packed_cells; std::vector<CellInfo *> new_cells; for (auto cell : design->cells) { @@ -85,6 +87,8 @@ static void pack_lut_lutffs(Design *design) // Pack FFs not packed as LUTFFs static void pack_nonlut_ffs(Design *design) { + log_info("Packing non-LUT FFs..\n"); + std::unordered_set<IdString> packed_cells; std::vector<CellInfo *> new_cells; @@ -132,6 +136,8 @@ static void set_net_constant(NetInfo *orig, NetInfo *constnet, bool constval) // Pack constants (simple implementation) static void pack_constants(Design *design) { + log_info("Packing constants..\n"); + CellInfo *gnd_cell = create_ice_cell(design, "ICESTORM_LC", "$PACKER_GND"); gnd_cell->params["LUT_INIT"] = "0"; NetInfo *gnd_net = new NetInfo; @@ -180,6 +186,8 @@ static void pack_io(Design *design) std::unordered_set<IdString> packed_cells; std::vector<CellInfo *> new_cells; + log_info("Packing IOs..\n"); + for (auto cell : design->cells) { CellInfo *ci = cell.second; if (is_nextpnr_iob(ci)) { @@ -225,21 +233,25 @@ static void pack_io(Design *design) // Simple global promoter (clock only) static void promote_globals(Design *design) { + log_info("Promoting globals..\n"); + std::unordered_map<IdString, int> clock_count; for (auto net : design->nets) { NetInfo *ni = net.second; if (ni->driver.cell != nullptr && !is_global_net(ni)) { clock_count[net.first] = 0; for (auto user : ni->users) { - if (user.cell != nullptr && is_ff(user.cell) && user.port == "C") + if (user.cell != nullptr && is_ff(user.cell) && + user.port == "C") clock_count[net.first]++; } } } - auto global_clock = std::max_element(clock_count.begin(), clock_count.end(), []( - const std::pair<IdString, int> &a, const std::pair<IdString, int> &b) { - return a.second < b.second; - }); + auto global_clock = std::max_element(clock_count.begin(), clock_count.end(), + [](const std::pair<IdString, int> &a, + const std::pair<IdString, int> &b) { + return a.second < b.second; + }); if (global_clock->second > 0) { NetInfo *clknet = design->nets[global_clock->first]; CellInfo *gb = create_ice_cell(design, "SB_GB"); |