From 2285c8dbbdbc5b7e718fa849952c560bef69a8fc Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Thu, 28 Jan 2021 15:40:26 -0800 Subject: Initial refactoring of placer API. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- docs/archapi.md | 43 +++++++++++++++++++++++++++++++++++++++---- 1 file changed, 39 insertions(+), 4 deletions(-) (limited to 'docs') diff --git a/docs/archapi.md b/docs/archapi.md index a9c38589..481448e3 100644 --- a/docs/archapi.md +++ b/docs/archapi.md @@ -377,7 +377,7 @@ the given dst wire. This should return a low upper bound for the fastest route from `src` to `dst`. Or in other words it should assume an otherwise unused chip (thus "fastest route"). -But it only produces an estimate for that fastest route, not an exact +But it only produces an estimate for that fastest route, not an exact result, and for that estimate it is considered more acceptable to return a slightly too high result and it is considered less acceptable to return a too low result (thus "low upper bound"). @@ -463,21 +463,57 @@ Cell Delay Methods Returns the delay for the specified path through a cell in the `&delay` argument. The method returns false if there is no timing relationship from `fromPort` to `toPort`. -### TimingPortClass getPortTimingClass(const CellInfo *cell, IdString port, int &clockInfoCount) const +### TimingPortClass getPortTimingClass(const CellInfo \*cell, IdString port, int &clockInfoCount) const Return the _timing port class_ of a port. This can be a register or combinational input or output; clock input or output; general startpoint or endpoint; or a port ignored for timing purposes. For register ports, clockInfoCount is set to the number of associated _clock edges_ that can be queried by getPortClockingInfo. -### TimingClockingInfo getPortClockingInfo(const CellInfo *cell, IdString port, int index) const +### TimingClockingInfo getPortClockingInfo(const CellInfo \*cell, IdString port, int index) const Return the _clocking info_ (including port name of clock, clock polarity and setup/hold/clock-to-out times) of a port. Where ports have more than one clock edge associated with them (such as DDR outputs), `index` can be used to obtain information for all edges. `index` must be in [0, clockInfoCount), behaviour is undefined otherwise. +Partition Methods +----------------- + +Partitions are used by analytic placement to seperate types of BELs during +placement. Typical partitions are: + - All LUT BELs + - All FF BELs + - All multipliers BELs + - All block RAM BELs + - etc. + +The general rule here is to include all BELs that are roughly interchangable +during placement. + +### const\_range\ getPartitions() const + +Return a list of all partitions on the device. + +### IdString partitionName(PartitionId partition) const + +Return the name of the partition. + +### PartitionId partitionForBel(BelId bel) const + +Returns the partition for a particular cell type. + +### const\_range\ partitionForBel(PartitionId partition) const + +Return the list of BELs within a partition. + Placer Methods -------------- +### bool isValidBelForCellType(IdString cell\_type, BelId bel) const + +Returns true if the given cell can be bound to the given BEL. This check +should be fast, compared with isValidBelForCell. This check should always +return the same value regardless if other cells are placed within the fabric. + ### bool isValidBelForCell(CellInfo \*cell, BelId bel) const Returns true if the given cell can be bound to the given bel, considering @@ -489,7 +525,6 @@ a certain number of different clock signals allowed for a group of bels. Returns true if a bell in the current configuration is valid, i.e. if `isValidBelForCell()` would return true for the current mapping. - ### static const std::string defaultPlacer Name of the default placement algorithm for the architecture, if -- cgit v1.2.3 From f3a7c691a317fafd48b9142ff0c688e75bbb6424 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Thu, 28 Jan 2021 16:03:14 -0800 Subject: Make some partition names consistent. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- 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 481448e3..3a0efcce 100644 --- a/docs/archapi.md +++ b/docs/archapi.md @@ -493,15 +493,15 @@ during placement. Return a list of all partitions on the device. -### IdString partitionName(PartitionId partition) const +### IdString getPartitionName(PartitionId partition) const Return the name of the partition. -### PartitionId partitionForBel(BelId bel) const +### PartitionId getPartitionForBel(BelId bel) const Returns the partition for a particular cell type. -### const\_range\ partitionForBel(PartitionId partition) const +### const\_range\ getBelsForPartition(PartitionId partition) const Return the list of BELs within a partition. -- cgit v1.2.3 From b4160c228e789639dc9f434100976c5eb1f95d8d Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Thu, 28 Jan 2021 16:48:22 -0800 Subject: Add archcheck for partition methods. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- docs/archapi.md | 23 ++++++++++++++++++++--- 1 file changed, 20 insertions(+), 3 deletions(-) (limited to 'docs') diff --git a/docs/archapi.md b/docs/archapi.md index 3a0efcce..53132bd9 100644 --- a/docs/archapi.md +++ b/docs/archapi.md @@ -88,6 +88,14 @@ Get Z dimension for the specified tile for bels. All bels with at specified X an Get Z dimension for the specified tile for pips. All pips with at specified X and Y coordinates must have a Z coordinate in the range `0 .. getTileDimZ(X,Y)-1` (inclusive). +Cell Methods +----------- + +### const\_range\ getCellTypes() const + +Get list of cell types that this architecture accepts. + + Bel Methods ----------- @@ -478,8 +486,8 @@ information for all edges. `index` must be in [0, clockInfoCount), behaviour is Partition Methods ----------------- -Partitions are used by analytic placement to seperate types of BELs during -placement. Typical partitions are: +Partitions are subsets of BelIds and cell types used by analytic placement to +seperate types of BELs during placement. Typical partitions are: - All LUT BELs - All FF BELs - All multipliers BELs @@ -487,7 +495,8 @@ placement. Typical partitions are: - etc. The general rule here is to include all BELs that are roughly interchangable -during placement. +during placement. Partitions should form an exact cover over all BelIds and +cell types. ### const\_range\ getPartitions() const @@ -497,8 +506,16 @@ Return a list of all partitions on the device. Return the name of the partition. +### PartitionId getPartitionByName(IdString partition\_name) const + +Return the partition for the specified partition name. + ### PartitionId getPartitionForBel(BelId bel) const +Returns the partition for a particular BEL. + +### PartitionId getPartitionForCell(IdString cell\_type) const + Returns the partition for a particular cell type. ### const\_range\ getBelsForPartition(PartitionId partition) const -- cgit v1.2.3 From 878fcdd22dfab32234f2537892ae844b2b4495f3 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Thu, 28 Jan 2021 18:32:42 -0800 Subject: Implement partitioning in placer_heap. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- docs/archapi.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'docs') diff --git a/docs/archapi.md b/docs/archapi.md index 53132bd9..855796d6 100644 --- a/docs/archapi.md +++ b/docs/archapi.md @@ -486,7 +486,7 @@ information for all edges. `index` must be in [0, clockInfoCount), behaviour is Partition Methods ----------------- -Partitions are subsets of BelIds and cell types used by analytic placement to +Partitions are subsets of BelIds and cell types used by analytic placer to seperate types of BELs during placement. Typical partitions are: - All LUT BELs - All FF BELs -- cgit v1.2.3 From 11c80c048b31261da14c04f79566b9e1debb29f9 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Fri, 29 Jan 2021 14:28:46 -0800 Subject: Update documentation. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- docs/archapi.md | 54 +++++++++++++++++++++++++++++++++--------------------- docs/coding.md | 54 +++++++++++++++++++++++++++++++++++++++++++----------- docs/faq.md | 1 + 3 files changed, 77 insertions(+), 32 deletions(-) (limited to 'docs') diff --git a/docs/archapi.md b/docs/archapi.md index 855796d6..f7246f08 100644 --- a/docs/archapi.md +++ b/docs/archapi.md @@ -40,6 +40,10 @@ A type representing a wire name. `WireId()` must construct a unique null-value. A type representing a pip name. `PipId()` must construct a unique null-value. Must provide `==`, `!=`, and `<` operators and a specialization for `std::hash`. +### BelBucketId + +A type representing a BEL bucket. `BelBucketId()` must construct a unique null-value. Must provide `==`, `!=`, and `<` operators and a specialization for `std::hash`. + ### GroupId A type representing a group name. `GroupId()` must construct a unique null-value. Must provide `==` and `!=` operators and a specialization for `std::hash`. @@ -483,44 +487,52 @@ Return the _clocking info_ (including port name of clock, clock polarity and set port. Where ports have more than one clock edge associated with them (such as DDR outputs), `index` can be used to obtain information for all edges. `index` must be in [0, clockInfoCount), behaviour is undefined otherwise. -Partition Methods ------------------ +BEL Buckets Methods +------------------- -Partitions are subsets of BelIds and cell types used by analytic placer to -seperate types of BELs during placement. Typical partitions are: +BEL buckets are subsets of BelIds and cell types used by analytic placer to +seperate types of BELs during placement. The buckets should form an exact +cover over all BelIds and cell types. + +Each BEL bucket should be BelIds and cell types that are roughly +interchangable during placement. Typical buckets are: - All LUT BELs - All FF BELs - All multipliers BELs - All block RAM BELs - etc. -The general rule here is to include all BELs that are roughly interchangable -during placement. Partitions should form an exact cover over all BelIds and -cell types. +The BEL buckets will be used during analytic placement for spreading prior to +strict legality enforcement. It is not required that all BELs within a bucket +are strictly equivelant. + +Strict legality step will enforce those differences, along with additional +local constraints. `isValidBelForCell`, `isValidBelForCellType`, and +`isBelLocationValid` are used to enforce strict legality checks. -### const\_range\ getPartitions() const +### const\_range\ getBelBuckets() const -Return a list of all partitions on the device. +Return a list of all BEL buckets on the device. -### IdString getPartitionName(PartitionId partition) const +### IdString getBelBucketName(BelBucketId bucket) const -Return the name of the partition. +Return the name of this BEL bucket. -### PartitionId getPartitionByName(IdString partition\_name) const +### BelBucketId getBelBucketByName(IdString bucket\_name) const -Return the partition for the specified partition name. +Return the BelBucketId for the specified bucket name. -### PartitionId getPartitionForBel(BelId bel) const +### BelBucketId getBelBucketForBel(BelId bel) const -Returns the partition for a particular BEL. +Returns the bucket for a particular BEL. -### PartitionId getPartitionForCell(IdString cell\_type) const +### BelBucketId getBelBucketForCell(IdString cell\_type) const -Returns the partition for a particular cell type. +Returns the BEL bucket for a particular cell type. -### const\_range\ getBelsForPartition(PartitionId partition) const +### const\_range\ getBelsInBucket(BelBucketId bucket) const -Return the list of BELs within a partition. +Return the list of BELs within a bucket. Placer Methods -------------- @@ -533,9 +545,9 @@ return the same value regardless if other cells are placed within the fabric. ### bool isValidBelForCell(CellInfo \*cell, BelId bel) const -Returns true if the given cell can be bound to the given bel, considering +Returns true if the given cell can be bound to the given BEL, considering other bound resources. For example, this can be used if there is only -a certain number of different clock signals allowed for a group of bels. +a certain number of different clock signals allowed for a group of BELs. ### bool isBelLocationValid(BelId bel) const diff --git a/docs/coding.md b/docs/coding.md index b8025f8b..0db269a6 100644 --- a/docs/coding.md +++ b/docs/coding.md @@ -14,9 +14,9 @@ This document aims to provide an overview into the philosophy behind nextpnr's c An architecture in nextpnr is described first and foremost as code. The exact details are given in the [Arch API reference](archapi.md); this aims to explain the core concept. -By choosing this approach; this gives architectures significant flexibility to use more advanced database representations than a simple flat database - for example deduplicated approaches that store similar tiles only once. +By choosing this approach; this gives architectures significant flexibility to use more advanced database representations than a simple flat database - for example deduplicated approaches that store similar tiles only once. -Architectures can also implement custom algorithms for packing (or other initial netlist transformations) and specialized parts of placement and routing such as global clock networks. This is because architectures provide the `pack()`, `place()` and `route()` functions, although the latter two will normally use generic algorithms (such as HeAP and router1) to do most of the work. +Architectures can also implement custom algorithms for packing (or other initial netlist transformations) and specialized parts of placement and routing such as global clock networks. This is because architectures provide the `pack()`, `place()` and `route()` functions, although the latter two will normally use generic algorithms (such as HeAP and router1) to do most of the work. Another important function provided by architectures is placement validity checking. This allows the placer to check whether or not a given cell placement is valid. An example of this is for iCE40, where 8 logic cells in a tile share one clock signal - this is checked here. @@ -24,13 +24,13 @@ This function allows architectures in nextpnr to do significantly less packing t Additionally to this; architectures provide functions for checking the availability and conflicts between resources (e.g. `checkBelAvail`, `checkPipAvail`, etc). This enables arbitrary constraints between resource availability to be defined, for example: - - where a group of Pips share bitstream bits, only one can be used at a time - - Pips that represent LUT permutation are not available when the LUT is in memory mode - - only a certain total number of Pips in a switchbox can be used at once due to power supply limitations + - where a group of PIPs share bitstream bits, only one can be used at a time + - PIPs that represent LUT permutation are not available when the LUT is in memory mode + - only a certain total number of PIPs in a switchbox can be used at once due to power supply limitations ## `IdString`s -To avoid the high cost of using strings as identifiers directly; almost all "string" identifiers in nextpnr (such as cell names and types) use an indexed string pool type named `IdString`. Unlike Yosys, which has a global garbage collected pool, nextpnr has a per-Context pool without any garbage collection. +To avoid the high cost of using strings as identifiers directly; almost all "string" identifiers in nextpnr (such as cell names and types) use an indexed string pool type named `IdString`. Unlike Yosys, which has a global garbage collected pool, nextpnr has a per-Context pool without any garbage collection. `IdString`s can be created in two ways. Architectures can add `IdString`s with constant indices - allowing `IdString` constants to be provided too - using `initialize_add` at startup. See how `constids.inc` is used in iCE40 for an example of this. The main way to create `IdString`s, however, is at runtime using the `id` member function of `BaseCtx` given the string to create from (if an `IdString` of that string already exists, the existing `IdString` will be returned). @@ -39,26 +39,58 @@ Note that `IdString`s need a `Context` (or `BaseCtx`) pointer to convert them ba ## Developing CAD algorithms - packing Packing in nextpnr could be done in two ways (if significant packing is done at all): - - replacing multiple cells with a single larger cell that corresponds to a bel + - replacing multiple cells with a single larger cell that corresponds to a BEL - combining smaller cells using relative placement constraints -In flows with minimal packing the main task of the packer is to transform cells into common types that correspond to a bel (e.g. convert multiple flipflop primitives to a single common type with some extra parameters). The packer will also have to add relative constraints for fixed structures such as carry chains or LUT-MUX cascades. +The packer will also have to add relative constraints for fixed structures such as carry chains or LUT-MUX cascades. There are several helper functions that are useful for developing packers and other passes that perform significant netlist modifications in `util.h`. It is often preferable to use these compared to direct modification of the netlist structures due to the "double linking" nextpnr does - e.g. when connecting a port you must update both the `net` field of the ports and the `driver`/`users` of the net. +### Cell to BEL mapping + +There is an Arch API choice when it comes to representing the relationship +between cell types and BEL types. One option is to transform cells into +common types that correspond to a BEL (e.g. convert multiple flipflop +primitives to a single common type with some extra parameters). In Arch APIs +designed like this, packer transformations are required to convert input cell +types into nextpnr specific cell types that have a 1 to 1 relationship with +BEL types. + +For Arch APIs of this type, the method `isValidBelForCellType` reduces to: + +``` +bool isValidBelForCellType(IdString cell_type, BelId bel) const { + return cell_type == getBelType(bel); +} +``` + +The alternative is to implement a fast `isValidBelForCellType` method that +determines if this cell type can be bound to this BEL. + ## Developing CAD algorithms - placement -The job of the placer in nextpnr is to find a suitable bel for each cell in the design; while respecting legality and relative constraints. +The job of the placer in nextpnr is to find a suitable BEL for each cell in the design; while respecting legality and relative constraints. -Placers might want to create their own indices of bels (for example, bels by type and location) to speed up the search. +Placers might want to create their own indices of BELs (for example, BELs by type and location) to speed up the search. -As nextpnr allows arbitrary constraints on bels for more advanced packer-free flows and complex real-world architectures; placements must be checked for legality using `isValidBelForCell` (before placement) or `isBelLocationValid` (after placement) and the placement rejected if invalid. For analytical placement algorithms; after creating a spread-out AP solution the legality of placing each cell needs to be checked. In practice, the cost of this is fairly low as the architecture should ensure these functions are as fast as possible. +As nextpnr allows arbitrary constraints on BELs for more advanced packer-free flows and complex real-world architectures; placements must be checked for legality using `isValidBelForCell` (before placement) or `isBelLocationValid` (after placement) and the placement rejected if invalid. For analytical placement algorithms; after creating a spread-out AP solution the legality of placing each cell needs to be checked. In practice, the cost of this is fairly low as the architecture should ensure these functions are as fast as possible. There are several routes for timing information in the placer: - sink `PortRef`s have a `budget` value annotated by calling `assign_budget` which is an estimate of the maximum delay that an arc may have - sink ports can have a criticality (value between 0 and 1 where 1 is the critical path) associated with them by using `get_criticalities` and a `NetCriticalityMap` - `predictDelay` returns an estimated delay for a sink port based on placement information + +### BEL Buckets + +The BEL Bucket Arch APIs can be used by an analytical placer (AP) for getting +groups of BELs and cell types placed together. This grouping is important for +algorithms like HeAP which typically want to do operate on subsets of the +design for some portions of the placement. + +The HeAP implementation allows for multiple BEL buckets to be placed on +together, see the "cellGroups" field. + ## Routing The job of the router is to ensure that the `wires` map for each net contains a complete routing tree; populated using the Arch functions to bind wires and pips. The ripup invariants in the [FAQ](faq.md) are important to bear in mind; as there may be complex constraints on the usage of wires and pips in some architectures. diff --git a/docs/faq.md b/docs/faq.md index 8a1b3f6a..14785430 100644 --- a/docs/faq.md +++ b/docs/faq.md @@ -23,6 +23,7 @@ For nextpnr we are using the following terminology. - **Wire**: a fixed physical connection inside the FPGA between Pips and/or Bel pins. - **Alias**: a special automatic-on Pip to represent a permanent connection between two wires - **Group**: a collection of bels, pips, wires, and/or other groups +- **BelBucket**: a collection of BELs and cell types. All of the BEL buckets form a set cover of BELs and cell types. ### Flow Terminology -- cgit v1.2.3 From 01509ec7c991f0ec674fd933095dfe52be28b46f Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Mon, 1 Feb 2021 07:27:35 -0800 Subject: Make BELs/PIPs lowercase as bels/pips per review comment. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- docs/archapi.md | 38 +++++++++++++++++++------------------- docs/coding.md | 32 ++++++++++++++++---------------- docs/faq.md | 2 +- 3 files changed, 36 insertions(+), 36 deletions(-) (limited to 'docs') diff --git a/docs/archapi.md b/docs/archapi.md index f7246f08..49183c63 100644 --- a/docs/archapi.md +++ b/docs/archapi.md @@ -42,7 +42,7 @@ A type representing a pip name. `PipId()` must construct a unique null-value. Mu ### BelBucketId -A type representing a BEL bucket. `BelBucketId()` must construct a unique null-value. Must provide `==`, `!=`, and `<` operators and a specialization for `std::hash`. +A type representing a bel bucket. `BelBucketId()` must construct a unique null-value. Must provide `==`, `!=`, and `<` operators and a specialization for `std::hash`. ### GroupId @@ -487,23 +487,23 @@ Return the _clocking info_ (including port name of clock, clock polarity and set port. Where ports have more than one clock edge associated with them (such as DDR outputs), `index` can be used to obtain information for all edges. `index` must be in [0, clockInfoCount), behaviour is undefined otherwise. -BEL Buckets Methods +Bel Buckets Methods ------------------- -BEL buckets are subsets of BelIds and cell types used by analytic placer to -seperate types of BELs during placement. The buckets should form an exact +Bel buckets are subsets of BelIds and cell types used by analytic placer to +seperate types of bels during placement. The buckets should form an exact cover over all BelIds and cell types. -Each BEL bucket should be BelIds and cell types that are roughly +Each bel bucket should be BelIds and cell types that are roughly interchangable during placement. Typical buckets are: - - All LUT BELs - - All FF BELs - - All multipliers BELs - - All block RAM BELs + - All LUT bels + - All FF bels + - All multipliers bels + - All block RAM bels - etc. -The BEL buckets will be used during analytic placement for spreading prior to -strict legality enforcement. It is not required that all BELs within a bucket +The bel buckets will be used during analytic placement for spreading prior to +strict legality enforcement. It is not required that all bels within a bucket are strictly equivelant. Strict legality step will enforce those differences, along with additional @@ -512,11 +512,11 @@ local constraints. `isValidBelForCell`, `isValidBelForCellType`, and ### const\_range\ getBelBuckets() const -Return a list of all BEL buckets on the device. +Return a list of all bel buckets on the device. ### IdString getBelBucketName(BelBucketId bucket) const -Return the name of this BEL bucket. +Return the name of this bel bucket. ### BelBucketId getBelBucketByName(IdString bucket\_name) const @@ -524,30 +524,30 @@ Return the BelBucketId for the specified bucket name. ### BelBucketId getBelBucketForBel(BelId bel) const -Returns the bucket for a particular BEL. +Returns the bucket for a particular bel. ### BelBucketId getBelBucketForCell(IdString cell\_type) const -Returns the BEL bucket for a particular cell type. +Returns the bel bucket for a particular cell type. ### const\_range\ getBelsInBucket(BelBucketId bucket) const -Return the list of BELs within a bucket. +Return the list of bels within a bucket. Placer Methods -------------- ### bool isValidBelForCellType(IdString cell\_type, BelId bel) const -Returns true if the given cell can be bound to the given BEL. This check +Returns true if the given cell can be bound to the given bel. This check should be fast, compared with isValidBelForCell. This check should always return the same value regardless if other cells are placed within the fabric. ### bool isValidBelForCell(CellInfo \*cell, BelId bel) const -Returns true if the given cell can be bound to the given BEL, considering +Returns true if the given cell can be bound to the given bel, considering other bound resources. For example, this can be used if there is only -a certain number of different clock signals allowed for a group of BELs. +a certain number of different clock signals allowed for a group of bels. ### bool isBelLocationValid(BelId bel) const diff --git a/docs/coding.md b/docs/coding.md index 0db269a6..5cbaef01 100644 --- a/docs/coding.md +++ b/docs/coding.md @@ -24,9 +24,9 @@ This function allows architectures in nextpnr to do significantly less packing t Additionally to this; architectures provide functions for checking the availability and conflicts between resources (e.g. `checkBelAvail`, `checkPipAvail`, etc). This enables arbitrary constraints between resource availability to be defined, for example: - - where a group of PIPs share bitstream bits, only one can be used at a time - - PIPs that represent LUT permutation are not available when the LUT is in memory mode - - only a certain total number of PIPs in a switchbox can be used at once due to power supply limitations + - where a group of pips share bitstream bits, only one can be used at a time + - Pips that represent LUT permutation are not available when the LUT is in memory mode + - only a certain total number of pips in a switchbox can be used at once due to power supply limitations ## `IdString`s @@ -39,22 +39,22 @@ Note that `IdString`s need a `Context` (or `BaseCtx`) pointer to convert them ba ## Developing CAD algorithms - packing Packing in nextpnr could be done in two ways (if significant packing is done at all): - - replacing multiple cells with a single larger cell that corresponds to a BEL + - replacing multiple cells with a single larger cell that corresponds to a bel - combining smaller cells using relative placement constraints The packer will also have to add relative constraints for fixed structures such as carry chains or LUT-MUX cascades. There are several helper functions that are useful for developing packers and other passes that perform significant netlist modifications in `util.h`. It is often preferable to use these compared to direct modification of the netlist structures due to the "double linking" nextpnr does - e.g. when connecting a port you must update both the `net` field of the ports and the `driver`/`users` of the net. -### Cell to BEL mapping +### Cell to bel mapping There is an Arch API choice when it comes to representing the relationship -between cell types and BEL types. One option is to transform cells into -common types that correspond to a BEL (e.g. convert multiple flipflop +between cell types and bel types. One option is to transform cells into +common types that correspond to a bel (e.g. convert multiple flipflop primitives to a single common type with some extra parameters). In Arch APIs designed like this, packer transformations are required to convert input cell types into nextpnr specific cell types that have a 1 to 1 relationship with -BEL types. +bel types. For Arch APIs of this type, the method `isValidBelForCellType` reduces to: @@ -65,15 +65,15 @@ bool isValidBelForCellType(IdString cell_type, BelId bel) const { ``` The alternative is to implement a fast `isValidBelForCellType` method that -determines if this cell type can be bound to this BEL. +determines if this cell type can be bound to this bel. ## Developing CAD algorithms - placement -The job of the placer in nextpnr is to find a suitable BEL for each cell in the design; while respecting legality and relative constraints. +The job of the placer in nextpnr is to find a suitable bel for each cell in the design; while respecting legality and relative constraints. -Placers might want to create their own indices of BELs (for example, BELs by type and location) to speed up the search. +Placers might want to create their own indices of bels (for example, bels by type and location) to speed up the search. -As nextpnr allows arbitrary constraints on BELs for more advanced packer-free flows and complex real-world architectures; placements must be checked for legality using `isValidBelForCell` (before placement) or `isBelLocationValid` (after placement) and the placement rejected if invalid. For analytical placement algorithms; after creating a spread-out AP solution the legality of placing each cell needs to be checked. In practice, the cost of this is fairly low as the architecture should ensure these functions are as fast as possible. +As nextpnr allows arbitrary constraints on bels for more advanced packer-free flows and complex real-world architectures; placements must be checked for legality using `isValidBelForCell` (before placement) or `isBelLocationValid` (after placement) and the placement rejected if invalid. For analytical placement algorithms; after creating a spread-out AP solution the legality of placing each cell needs to be checked. In practice, the cost of this is fairly low as the architecture should ensure these functions are as fast as possible. There are several routes for timing information in the placer: - sink `PortRef`s have a `budget` value annotated by calling `assign_budget` which is an estimate of the maximum delay that an arc may have @@ -81,14 +81,14 @@ There are several routes for timing information in the placer: - `predictDelay` returns an estimated delay for a sink port based on placement information -### BEL Buckets +### Bel Buckets -The BEL Bucket Arch APIs can be used by an analytical placer (AP) for getting -groups of BELs and cell types placed together. This grouping is important for +The bel Bucket Arch APIs can be used by an analytical placer (AP) for getting +groups of bels and cell types placed together. This grouping is important for algorithms like HeAP which typically want to do operate on subsets of the design for some portions of the placement. -The HeAP implementation allows for multiple BEL buckets to be placed on +The HeAP implementation allows for multiple bel buckets to be placed on together, see the "cellGroups" field. ## Routing diff --git a/docs/faq.md b/docs/faq.md index 14785430..085b2bd7 100644 --- a/docs/faq.md +++ b/docs/faq.md @@ -23,7 +23,7 @@ For nextpnr we are using the following terminology. - **Wire**: a fixed physical connection inside the FPGA between Pips and/or Bel pins. - **Alias**: a special automatic-on Pip to represent a permanent connection between two wires - **Group**: a collection of bels, pips, wires, and/or other groups -- **BelBucket**: a collection of BELs and cell types. All of the BEL buckets form a set cover of BELs and cell types. +- **BelBucket**: a collection of bels and cell types. All of the bel buckets form a set cover of bels and cell types. ### Flow Terminology -- cgit v1.2.3