From 433d710c680dd4c2f178cf8c11880247ea868e7d Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Mon, 5 Apr 2021 11:47:17 -0700 Subject: Initial device resources doc. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- docs/device_resources.md | 224 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 224 insertions(+) create mode 100644 docs/device_resources.md diff --git a/docs/device_resources.md b/docs/device_resources.md new file mode 100644 index 0000000..9770440 --- /dev/null +++ b/docs/device_resources.md @@ -0,0 +1,224 @@ +## Device Resources + +The device resources schema is intended to be a complete description of an +island-based FPGA design. It is made of many components, but the core +description of the device is shown below. + +``` +┌─────────────────┐ +│ Device │ +│ ┌─────────────┐ │ +│ │ Tile │ │ +│ │ ┌─────────┐ │ │ +│ │ │ Site │ │ │ +│ │ │ ┌─────┐ │ │ │ +│ │ │ │ BEL │ │ │ │ +│ │ │ └─────┘ │ │ │ +│ │ │ │ │ │ +│ │ └─────────┘ │ │ +│ │ │ │ +│ └─────────────┘ │ +│ │ +└─────────────────┘ +``` + +That is: + - A device contains tiles + - Tiles contains sites + - Sites contains BELs + +The schema contains the required information to answer questions such as: + - Where are tiles are located? + - How are sites connected to the routing graph? + - How are BELs connected to the boundry of the site? + - How can cells be placed at BELs? + +## Terminology + +- Device - A set of tiles and package pins. +- Tiles - An instance of a tile type which contains wires and sites +- Package pin - A boundry between the "interior" of the device and what is "outside" the package. Generally corrisponds to a pin on a package, e.g. pin 1 on SOP-8 or A1 on CSG324. +- Wire - Also known as a "tile wire" . A wire is a piece of conductive material totally contained within a tile. Wires can be part of nodes. Wires can connect to PIPs or site pins. +- Node - A node is a set of 1 or more wires that are connected. Nodes can span multiple tiles. Nodes connect to PIPs or site pins via the wires that are part of the node. +- PIP - PIP is an abreviation for programable interconnect point. A PIP provides a connection between two wires. PIPs can be unidirectional or bidirectional. Unidirectional PIPs always connect wire0 to wire1. Bidirectional PIPs can connect wire0 to wire1 or wire1 to wire0. +- Site - A collection of site pins, site wires and BELs. +- Site pin - The connect between a site and a wire. Site pins may connect to 0 or more site port BELs. +- Site wire - A piece of conductive material that connects to at most 1 output BEL pin and 0 or more input or inout BEL pins. +- BEL - BEL is an abreviation of basic logic element. A BEL can be one of 3 types, site port, logic, routing. A BEL contains 1 or more BEL pins. +- BEL pin - A connection between a BEL and a site wire. +- Logic BEL - A placable logic element. May be subject to 0 or more placement constraints. +- Site port BEL - A site port BEL represents a connection to a site pin contained within the parent tile of the site. See [Site port BEL](#site_port_bel). +- Routing BEL - A routing BEL connects at most 1 input BEL pin to the output BEL pin. See [Routing BEL](#routing_bel). +- Site PIP - A pair of input and output BEL pins belonging to a BEL that represents a logically connection. +- Cell - A logical element of a design that some number of cell ports and some number of cell instances, and some number of nets. +- Cell port - The boundry between the interior of a cell and the containing cell (if any). +- Cell instance - A instance of a cell. The cell ports of may be connected to nets within the parent cell. +- Net - A set of logically connected cell ports. + +## The place and route problem + +The device resources schema is intended to provide a description for a tool +solving the place and route problem. The definition of the problem used by +this schema is described below: + +There exists exactly 1 **cell instance** (the **top** instance) that contains 1 or +more leaf **cell instances** that must be placed at **BELs**, such that no +**constraints** are violated and the **nets** between the **cell instances** are +**routable**. **Routable** means that **site wires**, **site PIPs**, **nodes**, **PIPs** +can be assigned to at most 1 **net** such that each **net driver BEL pin** can +reach each every **net sink BEL pin** on the **net**. + +The device resource format describes how **cell instances** can be legally +placed at **BELs** and how **cell pins** relate to **BEL pins**. When a +**cell instance** is placed at a **BEL**, it may be subject to 0 or more +**constraints**. + +**Nets** are divided into 3 categories. A **signal** net represents a signal +that is not either the constant logical 0 or constant logical 1 net. +The constant logical 0 and constant logical 1 nets are special because they +can have multiple drivers in the device description. Routing resources that +are always part of the constant logical 0 or constant logical 1 net are +explicitly defined in the device resources scheam. The constant logical 0 net +is listed in the schema as the "gnd" type. The constant logical 1 net is +listed in the schema as the "vcc" type. + +### Rules for routing + +Fully routed signal nets always begin at a output/inout BEL pin, and always +end at an input/inout BEL pin. If a net enters a site, that net **must** end +at an input/inout BEL pin. It is not legal for a net to enter and leave a +site. If such a path is required, a pseudo PIP should be added to the schema. + +## Details + +### Net routing summary + +Each net start at the driver output/inout BEL pin. The BEL pin will be +connected to exactly 1 site wire. If the net sink can be reached within the +site, then the net can use site PIPs (through a routing BEL) to reach a site +wire connected to the input/inout BEL pin. + +If the net sink is in another site, then the net must first reach a site port +input BEL pin using site PIPs to reach the site wire connected to the site +port. From there the net leaves the site via the site port and is now on the +first node via the site pin matching the site port. + +From there the net must use PIPs to expand to new nodes until arriving at a +node attached to valid site pin for the sink. This would be a site pin that +is part of the same site that the sink BEL is part of, and that the site port +wire can reach the sink BEL pin (via 0 or more site PIPs). The site can be +entered via the site port corrisponding to the site pin. The first site wire +in the site will be the site wire attached to the output BEL pin of the site +port. From there site routing continues per above. + +![Wire and nodes](https://symbiflow.readthedocs.io/projects/arch-defs/en/latest/_images/rrgraph-wire.svg) + +### Tile Types and site types + +To reduce data duplication in the device schema, both tiles and sites have a +type. Most of the definition of the tile and site is in the type rather than +repeated at each instance. This does cause some more complicated +indirection, so the following section provides some additional explaination +here. + +#### Sites, site types and alternative site types + +The most complicated relationship in the schema is likely the relationship +between sites, site types and alternative site types. + +Most of the site type description is independent of the tile / tile type that +the site type is within. See the "SiteType" struct definition for +the independent portion of the schema. The important exception is the +relationship between wires and site pins. + +Each site within a tile has a "primary site type", which is found in the +"SiteTypeInTileType" struct definition, contained in the "TileType" struct. +The site within the tile will specify which "SiteTypeInTileType" to use for +that particular site. + +The primary site type contains a list of "alternative" site types that may be +used ("altSiteTypes" in "SiteType"). The primary site type must always +contains the complete list of site pins used in any of the alternative site +types. + +The site pins to wire relationship is always done via the primary site type. +When an alternative site type is used, the site pins of that alternative site +type must be first be mapped to a site pin of the primary site type. + +The "SiteTypeInTileType" defines the relationship between the primary site +type and the wires. It also defines the relationship from the alternative +site type to the primary site type. + +It first defines the primary site type ("primaryType"). It defines a map +between the site pins in the primary site type and wires in the tile type that +contains the site ("primaryPinsToTileWires"). Last it defines +the map between the alternative site pin and the primary site pin +("altPinsToPrimaryPins"). + +Important: When solving the place and route problem, only the primary or one +of the alternative site types can be used at a time for a particular site. + +### Routing BEL + +A routing BEL represents statically configurable site routing by connecting a +site wire connected to one of the input BEL pins to the output BEL pin of +the BEL. Routing BELs may only have 1 output BEL pin. + +#### Inverting routing BELs + +Some routing BELs can invert signals that pass through them. Defined the +"inverting" field in the "BEL" struct with the BEL pins that invert and do +not invert. + +### Site port BEL + +A site port BEL represents a connection to a site pin contained within the +parent tile of the site. Site port BELs have exactly 1 BEL pin. The BEL name +and pin name should be the same. The name of the BEL should match the name of +the site pin that the site port connects too. The direction of the BEL pin +should be the opposite of the site pin direction. + +Examples: + +An input site pin "I0" would have a site port BEL named "I0" with 1 BEL +output pin named "I0". + +## Additional topics + +The device resources schema also covers some important data required for +handling common cases found in island based FPGAs. + +### Signal inversions + +It is fairly common for fabrics to contain site local signal inverters. +Depending on the architecture, the place and route tool may be expected to +leverage inverters or may even require it. The device resources schemas +provides a description for how cells express inversion and how to use site +local inverters to implement the requested inversion. + +### LUT definitions + +LUTs are common to every island-based FPGA, and many place and route tasks +depend on having knowledge of how the LUTs are arranged. The LUT definition +section of the device resources defines where LUTs exist as BELs and what +cells can be placed at those BELs. This is important is at least two place +and route tasks. The first is that LUTs can be trivially turned into site pips +from the input of the LUT to the output of the LUT, subject to **constraints** +and LUT equation sharing. The second is that LUTs can be trivially turned +into constant sources from the output pin. + +### Parameters + +Some parameters attached to cell instances may be relevant for the place and +route problem. A common example is LUT equation sharing, which can happen on +fracturable LUTs. See the schema for details. + +### Pseudo PIPs + +It may be important within a device to represent PIPs that "route-thru" +one or more BELs. This can be modelled as placing a cell in a particular +configuration at a BEL, subject to the normal cell placement rules. The +"PseudoCell" struct defines what resources are used by using PIPs. + +All pseudo PIPs must define at least 1 pseudo cell. Pseudo cells should +include the site port BEL that the pseudo PIP used to enter the site. -- cgit v1.2.3 From 32c03693c0cd683ef26d16d3051ec8a4031831e6 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Mon, 5 Apr 2021 13:47:15 -0700 Subject: Iterate DeviceResources doc with feedback from review. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- docs/device_resources.md | 137 +++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 134 insertions(+), 3 deletions(-) diff --git a/docs/device_resources.md b/docs/device_resources.md index 9770440..1d8efec 100644 --- a/docs/device_resources.md +++ b/docs/device_resources.md @@ -89,14 +89,145 @@ end at an input/inout BEL pin. If a net enters a site, that net **must** end at an input/inout BEL pin. It is not legal for a net to enter and leave a site. If such a path is required, a pseudo PIP should be added to the schema. +## Site example + +The following is an example site for a SLICE for a non-existant device. + +``` + ▲ + CO│ │ + ┌──────────────────────────┼─────────────────────────────────────┼──────┐ + │ │ │ │ + B0│ I0┌───────┐ │ BLUT ┌───────┐ ▼ CLK │ +─────┼────►│ │ ┌────────o─────────────────┬────►│ │ ┌────┐ │ + B1│ I1│ │O │ │ │XOR │ │D D│ │Q │ FFOUT +─────┼────►│ BLUT3 ├───┤ │ ┌────────┬──o────►│ FFMUX ├──►│ FF ├───┼───► + B2│ I2│ │ │ │ │ │ |ALUT │ │ │ │ │ +─────┼────►│ │ │ │ │ ┌──┬──o──o────►│ │ └────┘ │ + │ └───────┘ │ ┌───┴───┐ │ │ │ │ │ └───────┘ │ + │ │ SI│ │ │ │ │ │ │ │ + │ └───►│ ├─┘ │ │ │ │ │ + │ DX│ CARRY │ O │ │ │ │ │ + │ ┌───►│ │ │ │ │ │ │ + A0│ I0┌───────┐ │ └───┬───┘ │ │ │ │ ┌────────┐ │ +─────┼────►│ │ │ │ │ │ │ │ BLUT │ │ │ + A1│ I1│ │O │ │ │ │ │ └─────►│ │OUT │ OUT +─────┼────►│ ALUT3 ├───┴────────o────────┘ │ │ XOR │ OUTMUX ├──────────┼────► + B2│ I2│ │ │ │ └────────►│ │ │ +─────┼────►│ │ │ │ ALUT │ │ │ + │ └───────┘ │ └───────────►└────────┘ │ + │ │ │ + │ │ │ + └──────────────────────────┼────────────────────────────────────────────┘ + CI│ + │ +``` + +In the above example, there 17 BELs: + +| BEL Name | Category | # Input | # Output | +|----------|-----------|---------|----------| +| ALUT3 | Logic | 3 | 1 | +| BLUT3 | Logic | 3 | 1 | +| CARRY | Logic | 3 | 2 | +| FF | Logic | 2 | 1 | +| FFMUX | Routing | 3 | 1 | +| OUTMUX | Routing | 3 | 1 | +| A0 | Site port | 0 | 1 | +| A1 | Site port | 0 | 1 | +| A2 | Site port | 0 | 1 | +| B0 | Site port | 0 | 1 | +| B1 | Site port | 0 | 1 | +| B2 | Site port | 0 | 1 | +| CI | Site port | 0 | 1 | +| CLK | Site port | 0 | 1 | +| CO | Site port | 1 | 0 | +| FFOUT | Site port | 1 | 0 | +| OUT | Site port | 1 | 0 | + +Each site port BEL has a site pin, so the site pins are: + +| Site Pin Name | Direction | +|---------------|-----------| +| A0 | In | +| A1 | In | +| A2 | In | +| B0 | In | +| B1 | In | +| B2 | In | +| CI | In | +| CLK | In | +| CO | Out | +| FFOUT | Out | +| OUT | Out | + +The BEL BLUT3 has 4 BEL pins: + +| BEL pin name | Direction | +|--------------|-----------| +| I0 | In | +| I1 | In | +| I2 | In | +| O | Out | + +The BEL A0 has 1 BEL pin: + +| BEL pin name | Direction | +|--------------|-----------| +| A0 | Out | + +The BEL OUTMUX has 4 BEL pins: + +| BEL pin name | Direction | +|--------------|-----------| +| BLUT | In | +| XOR | In | +| ALUT | In | +| OUT | Out | + + +There are 12 site PIPs: + +| BEL name | In pin | Out pin | +|----------|--------|---------| +| BLUT3 | I0 | O | +| BLUT3 | I1 | O | +| BLUT3 | I2 | O | +| ALUT3 | I0 | O | +| ALUT3 | I1 | O | +| ALUT3 | I2 | O | +| FFMUX | ALUT | D | +| FFMUX | XOR | D | +| FFMUX | BLUT | D | +| OUTMUX | ALUT | OUT | +| OUTMUX | XOR | OUT | +| OUTMUX | BLUT | OUT | + + +The site wire BLUT3\_O has 4 BEL pins: + +| BEL Name | Pin | +|----------|------| +| BLUT3 | O | +| CARRY | SI | +| FFMUX | BLUT | +| OUTMUX | BLUT | + +The site wire B0 has 2 BEL pins: + +| BEL Name | Pin | +|----------|-----| +| B0 | B0 | +| BLUT3 | I0 | + ## Details ### Net routing summary Each net start at the driver output/inout BEL pin. The BEL pin will be connected to exactly 1 site wire. If the net sink can be reached within the -site, then the net can use site PIPs (through a routing BEL) to reach a site -wire connected to the input/inout BEL pin. +site, then the net can use site PIPs to reach a site wire connected to the +input/inout BEL pin. If the net sink is in another site, then the net must first reach a site port input BEL pin using site PIPs to reach the site wire connected to the site @@ -162,7 +293,7 @@ of the alternative site types can be used at a time for a particular site. A routing BEL represents statically configurable site routing by connecting a site wire connected to one of the input BEL pins to the output BEL pin of -the BEL. Routing BELs may only have 1 output BEL pin. +the BEL. Routing BELs must have 1 output BEL pin. #### Inverting routing BELs -- cgit v1.2.3 From bd9bd09d9370550faa5d13b8441192509b3c3cb1 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Mon, 5 Apr 2021 15:22:29 -0700 Subject: Spelling check for device_resources doc. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- docs/device_resources.md | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) diff --git a/docs/device_resources.md b/docs/device_resources.md index 1d8efec..76096ff 100644 --- a/docs/device_resources.md +++ b/docs/device_resources.md @@ -30,28 +30,28 @@ That is: The schema contains the required information to answer questions such as: - Where are tiles are located? - How are sites connected to the routing graph? - - How are BELs connected to the boundry of the site? + - How are BELs connected to the boundary of the site? - How can cells be placed at BELs? ## Terminology - Device - A set of tiles and package pins. - Tiles - An instance of a tile type which contains wires and sites -- Package pin - A boundry between the "interior" of the device and what is "outside" the package. Generally corrisponds to a pin on a package, e.g. pin 1 on SOP-8 or A1 on CSG324. +- Package pin - A boundry between the "interior" of the device and what is "outside" the package. Generally corresponds to a pin on a package, e.g. pin 1 on SOP-8 or A1 on CSG324. - Wire - Also known as a "tile wire" . A wire is a piece of conductive material totally contained within a tile. Wires can be part of nodes. Wires can connect to PIPs or site pins. - Node - A node is a set of 1 or more wires that are connected. Nodes can span multiple tiles. Nodes connect to PIPs or site pins via the wires that are part of the node. -- PIP - PIP is an abreviation for programable interconnect point. A PIP provides a connection between two wires. PIPs can be unidirectional or bidirectional. Unidirectional PIPs always connect wire0 to wire1. Bidirectional PIPs can connect wire0 to wire1 or wire1 to wire0. +- PIP - PIP is an abbreviation for programable interconnect point. A PIP provides a connection between two wires. PIPs can be unidirectional or bidirectional. Unidirectional PIPs always connect wire0 to wire1. Bidirectional PIPs can connect wire0 to wire1 or wire1 to wire0. - Site - A collection of site pins, site wires and BELs. - Site pin - The connect between a site and a wire. Site pins may connect to 0 or more site port BELs. - Site wire - A piece of conductive material that connects to at most 1 output BEL pin and 0 or more input or inout BEL pins. -- BEL - BEL is an abreviation of basic logic element. A BEL can be one of 3 types, site port, logic, routing. A BEL contains 1 or more BEL pins. +- BEL - BEL is an abbreviation of basic logic element. A BEL can be one of 3 types, site port, logic, routing. A BEL contains 1 or more BEL pins. - BEL pin - A connection between a BEL and a site wire. - Logic BEL - A placable logic element. May be subject to 0 or more placement constraints. - Site port BEL - A site port BEL represents a connection to a site pin contained within the parent tile of the site. See [Site port BEL](#site_port_bel). - Routing BEL - A routing BEL connects at most 1 input BEL pin to the output BEL pin. See [Routing BEL](#routing_bel). - Site PIP - A pair of input and output BEL pins belonging to a BEL that represents a logically connection. - Cell - A logical element of a design that some number of cell ports and some number of cell instances, and some number of nets. -- Cell port - The boundry between the interior of a cell and the containing cell (if any). +- Cell port - The boundary between the interior of a cell and the containing cell (if any). - Cell instance - A instance of a cell. The cell ports of may be connected to nets within the parent cell. - Net - A set of logically connected cell ports. @@ -78,7 +78,7 @@ that is not either the constant logical 0 or constant logical 1 net. The constant logical 0 and constant logical 1 nets are special because they can have multiple drivers in the device description. Routing resources that are always part of the constant logical 0 or constant logical 1 net are -explicitly defined in the device resources scheam. The constant logical 0 net +explicitly defined in the device resources schema. The constant logical 0 net is listed in the schema as the "gnd" type. The constant logical 1 net is listed in the schema as the "vcc" type. @@ -91,7 +91,7 @@ site. If such a path is required, a pseudo PIP should be added to the schema. ## Site example -The following is an example site for a SLICE for a non-existant device. +The following is an example site for a SLICE for a non-existent device. ``` ▲ @@ -238,7 +238,7 @@ From there the net must use PIPs to expand to new nodes until arriving at a node attached to valid site pin for the sink. This would be a site pin that is part of the same site that the sink BEL is part of, and that the site port wire can reach the sink BEL pin (via 0 or more site PIPs). The site can be -entered via the site port corrisponding to the site pin. The first site wire +entered via the site port corresponding to the site pin. The first site wire in the site will be the site wire attached to the output BEL pin of the site port. From there site routing continues per above. @@ -249,7 +249,7 @@ port. From there site routing continues per above. To reduce data duplication in the device schema, both tiles and sites have a type. Most of the definition of the tile and site is in the type rather than repeated at each instance. This does cause some more complicated -indirection, so the following section provides some additional explaination +indirection, so the following section provides some additional explanation here. #### Sites, site types and alternative site types -- cgit v1.2.3 From 081064e8973cee660e21fdec37bc2f3195ccb18e Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Tue, 6 Apr 2021 10:29:41 -0700 Subject: Fix review comments for device_resources doc. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- docs/device_resources.md | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/docs/device_resources.md b/docs/device_resources.md index 76096ff..8e42c44 100644 --- a/docs/device_resources.md +++ b/docs/device_resources.md @@ -28,7 +28,7 @@ That is: - Sites contains BELs The schema contains the required information to answer questions such as: - - Where are tiles are located? + - Where are tiles located? - How are sites connected to the routing graph? - How are BELs connected to the boundary of the site? - How can cells be placed at BELs? @@ -42,7 +42,7 @@ The schema contains the required information to answer questions such as: - Node - A node is a set of 1 or more wires that are connected. Nodes can span multiple tiles. Nodes connect to PIPs or site pins via the wires that are part of the node. - PIP - PIP is an abbreviation for programable interconnect point. A PIP provides a connection between two wires. PIPs can be unidirectional or bidirectional. Unidirectional PIPs always connect wire0 to wire1. Bidirectional PIPs can connect wire0 to wire1 or wire1 to wire0. - Site - A collection of site pins, site wires and BELs. -- Site pin - The connect between a site and a wire. Site pins may connect to 0 or more site port BELs. +- Site pin - The connection between a site and a wire. Site pins may connect to 0 or more site port BELs. - Site wire - A piece of conductive material that connects to at most 1 output BEL pin and 0 or more input or inout BEL pins. - BEL - BEL is an abbreviation of basic logic element. A BEL can be one of 3 types, site port, logic, routing. A BEL contains 1 or more BEL pins. - BEL pin - A connection between a BEL and a site wire. @@ -50,7 +50,7 @@ The schema contains the required information to answer questions such as: - Site port BEL - A site port BEL represents a connection to a site pin contained within the parent tile of the site. See [Site port BEL](#site_port_bel). - Routing BEL - A routing BEL connects at most 1 input BEL pin to the output BEL pin. See [Routing BEL](#routing_bel). - Site PIP - A pair of input and output BEL pins belonging to a BEL that represents a logically connection. -- Cell - A logical element of a design that some number of cell ports and some number of cell instances, and some number of nets. +- Cell - A logical element of a design that contains some number of cell ports and some number of cell instances, and some number of nets. - Cell port - The boundary between the interior of a cell and the containing cell (if any). - Cell instance - A instance of a cell. The cell ports of may be connected to nets within the parent cell. - Net - A set of logically connected cell ports. @@ -123,7 +123,7 @@ The following is an example site for a SLICE for a non-existent device. │ ``` -In the above example, there 17 BELs: +In the above example, there are 17 BELs: | BEL Name | Category | # Input | # Output | |----------|-----------|---------|----------| -- cgit v1.2.3