From d2bdb670c0be9e18722f79c170fc99d7f41768f1 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Sun, 11 Nov 2018 11:34:38 +0100 Subject: Add getConflictingPipWire() arch API, router1 improvements Signed-off-by: Clifford Wolf --- docs/archapi.md | 24 +++++++++++++++++------- 1 file changed, 17 insertions(+), 7 deletions(-) (limited to 'docs') diff --git a/docs/archapi.md b/docs/archapi.md index 73443c15..1bfb7c5c 100644 --- a/docs/archapi.md +++ b/docs/archapi.md @@ -217,12 +217,12 @@ Return the net a wire is bound to. ### NetInfo \*getConflictingWireNet(WireId wire) const -If this returns a non-nullptr, then unbinding that net +If this returns a non-nullptr, then unbinding the wire from that net will make the given wire available. This returns nullptr if the wire is already available, -or if there is no single net that can be unbound to make this -wire available. +or if there is no net that can be unbound from the wire to make it +available. ### DelayInfo getWireDelay(WireId wire) const @@ -289,11 +289,21 @@ Return the net this pip is bound to. ### NetInfo \*getConflictingPipNet(PipId pip) const Return the net that needs to be unbound in order to make this -pip available. +pip available. Note that it may be neccessary to unroute that +entire net to make the pip available. -This does not need to (but may) return the conflicting wire if the conflict is -limited to the conflicting wire being bound to the destination wire for this -pip. +This returns nullptr if the pip is already available, +or if there is no single net that can be unrouted to make +the pip available. + +### WireId getConflictingPipWire(PipId pip) const + +Return the single wire that needs to be unbound in order to make this pip +available. + +This returns WireId() if the pip is already available, +or if there is no single wire that can be unbound to make +the pip available. ### const\_range\ getPips() const -- cgit v1.2.3 From f93129634b479ba54d8e33186eb79f412eaeb4a9 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Sun, 11 Nov 2018 17:28:41 +0100 Subject: Add getConflictingWireWire() arch API, streamline getConflictingXY semantic Signed-off-by: Clifford Wolf --- docs/archapi.md | 36 ++++++++++++++++-------------------- 1 file changed, 16 insertions(+), 20 deletions(-) (limited to 'docs') diff --git a/docs/archapi.md b/docs/archapi.md index 1bfb7c5c..85bc6ccd 100644 --- a/docs/archapi.md +++ b/docs/archapi.md @@ -215,14 +215,15 @@ Return true if the wire is available, i.e. can be bound to a net. Return the net a wire is bound to. -### NetInfo \*getConflictingWireNet(WireId wire) const +### WireId getConflictingWireWire(WireId wire) const -If this returns a non-nullptr, then unbinding the wire from that net +If this returns a non-WireId(), then unbinding that wire will make the given wire available. -This returns nullptr if the wire is already available, -or if there is no net that can be unbound from the wire to make it -available. +### NetInfo \*getConflictingWireNet(WireId wire) const + +If this returns a non-nullptr, then unbinding that entire net +will make the given wire available. ### DelayInfo getWireDelay(WireId wire) const @@ -282,28 +283,23 @@ This method must also update `NetInfo::wires`. Returns true if the given pip is available to be bound to a net. +Users must also check if the pip destination wire is available +with `checkWireAvail(getPipDstWire(pip))` before binding the +pip to a net. + ### NetInfo \*getBoundPipNet(PipId pip) const Return the net this pip is bound to. -### NetInfo \*getConflictingPipNet(PipId pip) const - -Return the net that needs to be unbound in order to make this -pip available. Note that it may be neccessary to unroute that -entire net to make the pip available. - -This returns nullptr if the pip is already available, -or if there is no single net that can be unrouted to make -the pip available. - ### WireId getConflictingPipWire(PipId pip) const -Return the single wire that needs to be unbound in order to make this pip -available. +If this returns a non-WireId(), then unbinding that wire +will make the given pip available. + +### NetInfo \*getConflictingPipNet(PipId pip) const -This returns WireId() if the pip is already available, -or if there is no single wire that can be unbound to make -the pip available. +If this returns a non-nullptr, then unbinding that entire net +will make the given pip available. ### const\_range\ getPips() const -- cgit v1.2.3 From 06e0e1ffeec9b06cecc213728c279b9235316df9 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Tue, 13 Nov 2018 05:03:46 +0100 Subject: Various router1 fixes, Add BelId/WireId/PipId::operator<() Signed-off-by: Clifford Wolf --- docs/archapi.md | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'docs') diff --git a/docs/archapi.md b/docs/archapi.md index 85bc6ccd..40eabd9d 100644 --- a/docs/archapi.md +++ b/docs/archapi.md @@ -30,15 +30,15 @@ delay_t maxDelay() const { return delay; } ### BelId -A type representing a bel name. `BelId()` must construct a unique null-value. Must provide `==` and `!=` operators and a specialization for `std::hash`. +A type representing a bel name. `BelId()` must construct a unique null-value. Must provide `==`, `!=`, and `<` operators and a specialization for `std::hash`. ### WireId -A type representing a wire name. `WireId()` must construct a unique null-value. Must provide `==` and `!=` operators and a specialization for `std::hash`. +A type representing a wire name. `WireId()` must construct a unique null-value. Must provide `==`, `!=`, and `<` operators and a specialization for `std::hash`. ### PipId -A type representing a pip name. `PipId()` must construct a unique null-value. Must provide `==` and `!=` operators and a specialization for `std::hash`. +A type representing a pip name. `PipId()` must construct a unique null-value. Must provide `==`, `!=`, and `<` operators and a specialization for `std::hash`. ### GroupId -- cgit v1.2.3 From 23218b3378ec57915f321e22ae7060ea454b65aa Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Tue, 13 Nov 2018 16:08:04 +0100 Subject: Add some architecture API FAQ items Signed-off-by: Clifford Wolf --- docs/faq.md | 88 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 87 insertions(+), 1 deletion(-) (limited to 'docs') diff --git a/docs/faq.md b/docs/faq.md index d440bba6..63869240 100644 --- a/docs/faq.md +++ b/docs/faq.md @@ -38,7 +38,93 @@ For nextpnr we are using the following terminology. Adding new architectures to nextpnr ----------------------------------- -TBD +### Implementing new architectures + +Each nextpnr architecture must implement the *nextpnr architecture API*. +See [archapi.md](archapi.md) for a complete reference of the architecture API. + +### Delay Estimates + +Each architecture must implement a `estimateDelay()` method that estimates the expected delay for a path from given `src` to `dst` wires. +*It is very important that this method slightly overestimates the expected delay.* Otherwise there will be performance issues with the router. + +The delays estimates returned by that method should also be as fine-grain as possible. It definitely pays off to spend some time improving the `estimateDelay()` +for your architecture once implementing small designs work. + +### Ripup Information + +The `getConflictingWireWire()`, `getConflictingWireNet()`, `getConflictingPipWire()`, and `getConflictingPipNet()` methods are used by the router +to determine which resources to rip up in order to make a given routing resource (wire or pip) available. + +The architecture must guanrantee that the following invariants hold. + +**Invariant 1:** + +``` + if (!ctx->checkWireAvail(wire)) { + WireId w = getConflictingWireWire(wire); + if (w != WireId()) { + ctx->unbindWire(w); + assert(ctx->checkWireAvail(wire)); + } + } +``` + +**Invariant 2:** + +``` + if (!ctx->checkWireAvail(wire)) { + NetInfo *n = getConflictingWireNet(wire); + if (n != nullptr) { + for (auto &it : n->wires) + ctx->unbindWire(it.first); + assert(ctx->checkWireAvail(wire)); + } + } +``` + +**Invariant 3:** + +``` + if (!ctx->checkPipAvail(pip)) { + WireId w = getConflictingPipWire(pip); + if (w != WireId()) { + ctx->unbindWire(w); + assert(ctx->checkPipAvail(pip)); + } + } +``` + +**Invariant 4:** + +``` + if (!ctx->checkPipAvail(pip)) { + NetInfo *n = getConflictingPipNet(pip); + if (n != nullptr) { + for (auto &it : n->wires) + ctx->unbindWire(it.first); + assert(ctx->checkPipAvail(pip)); + } + } +``` + +**Invariant 5:** + +``` + if (ctx->checkWireAvail(wire)) { + // bind is guaranteed to succeed + ctx->bindWire(wire, net, strength); + } +``` + +**Invariant 6:** + +``` + if (ctx->checkPipAvail(pip) && ctx->checkWireAvail(ctx->getPipDstWire(pip))) { + // bind is guaranteed to succeed + ctx->bindPip(pip, net, strength); + } +``` Nextpnr and other tools ----------------------- -- cgit v1.2.3 From caca485cfff7f999a19e86e2f00187550b0c92f4 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Tue, 13 Nov 2018 17:30:49 +0100 Subject: Minor router1 debug log improvements Signed-off-by: Clifford Wolf --- docs/faq.md | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'docs') diff --git a/docs/faq.md b/docs/faq.md index 63869240..7b358187 100644 --- a/docs/faq.md +++ b/docs/faq.md @@ -46,7 +46,8 @@ See [archapi.md](archapi.md) for a complete reference of the architecture API. ### Delay Estimates Each architecture must implement a `estimateDelay()` method that estimates the expected delay for a path from given `src` to `dst` wires. -*It is very important that this method slightly overestimates the expected delay.* Otherwise there will be performance issues with the router. +*It is very important that this method slightly overestimates the expected delay.* Furthermore, it should overestimate the expected delay +by a slightly larger margin for longer paths than for shorter paths. Otherwise there will be performance issues with the router. The delays estimates returned by that method should also be as fine-grain as possible. It definitely pays off to spend some time improving the `estimateDelay()` for your architecture once implementing small designs work. -- cgit v1.2.3