Add Placement Constraints to VPR

[vaughnbetz]

Currently VPR can only lock down the placement of I/Os (in the pads file), and there isn't a direct way to control the clusterer with constraints.

1. We should have a method to lock any primitives to a specific (x,y,z) location on the device (not just I/O pads).

2. This constraint should affect not only placement, but also packing. Primitives with the same (x,y,z) should be packed together. This allows end users to use primitive names (which are more stable) to control placement, rather than post-packing names.

3. We would also like to be able to constrain primitives to a portion of the chip. Specifying a set of (xmin,ymin) to (xmax,ymax) regions that are legal places to place a primitive accomplishes this. In the common case there will be 0 rectangles (no constraint) or 1 rectangle, but we should support the union of multiple rectangles as the placement constraint so that more complex floorplans can be created.

Constraint options:

The above constraints could be implemented as two separate constraints: (x,y.z) and region.
Or they could be one constraint: a set of (xmin,ymin,zmin) to (xmax,ymax,zmax) rectangles. Placing at a specific (x,y,z) would then be achieved by having xmin=xmax,ymin=ymax,zmin=zmax in the constraint. I suspect one more general constraint is easier to document, so probably that is best.

Possible Solution

1. Constraint file: we could have a constraints.xml file that has a section for placement constraints and specifies these constraints. An alternative we've discussed is to re-use the .pad file, but that may be confusing as currently that file constrains only the placer, so I think a new constraints.xml file is more clear.

The names of primitives used in this file should support wildcards, so you can match all the primitives in some part of your design easily (key for floorplanning); e.g. my_processor|alu32|*. There is code in the sdc parser to do this already (vpr/src/timing/read_sdc.cpp).

2. Packer:

• do not pack things with region constraints that don't intersect together.
• after packing, check if any regions are too fill (more clusters of a certain type assigned to them than exist in the region). If there are any such regions, re-try clustering with all primitives in those regions having a high attraction to each other to force a more dense packing of that region.

3. Placer:

   • Compute a placement constraint by intersecting the region constraints of all primitives in a cluster together. Also propagate any resulting placement constraint to other member of a place_macro (carry chain, etc.).
   • Initial placement must place only with the legal region for each cluster
   • The move generator must not propose (or must immediately reject) any move that violates a region constraint.

4. Placement checking:

   • A new check should be added to the packing legality and placement legality checkers that checks these region constraints were respected (should never fire unless there is a bug in the optimizers, but very good to have to catch tricky optimization bugs).

Context

Constraints are necessary for multiple reasons:

• I/Os are locked down by the board design
• The chip is an SoC and some other parts are locked down
• The end user needs to control placement of some blocks to improve speed
• Floorplans are being used to allow modular design (multiple designers to finish different parts of the physical designs) or for partial reconfiguration, or in an attempt to improve performance.

Possible future work

• Store constraints in Tcl instead of or in addition to xml
• Add a fourth dimension to the constraints: sub_location. This would specify the index (or could be a unique string id) of the primitive-level pb_type within a cluster to which some primitive should be allocated during clustering. This would allow extremely detailed control of the clustering. Most likely this would be used for saving part of a prior compile (write out the very detailed constraints for some previously implemented part of the design) but it would also be fine for a very controlling user to specify them by hand.

[kmurray]

Here is a possible file format for the constraints based on something I drafted up a while ago:

    <vpr_constraints>

        <partition_list>
            <!-- A partition consists of a unique identifier, and a set of
                 atom primitives.

                 Note: in the limit each atom could be in a separate partition -->
            <partition name="partition_name_or_id">
                <!-- Adds all the atoms whose name match the regex to the enclosing partition -->
                <add_atoms name_pattern="my_primitive1"/> <!-- name_pattern can be an explicit name -->
                <add_atoms name_pattern="my_processor/alu32/*/"> <!-- name pattern could also be a regex pattern -->
            </partition>
        </partition_list>

        <placement_constraints>
            <!-- Force a particular partition to be placed within a specific region -->
            <placement_region partition_pattern="regex"> <!-- partition_patern may be wild-carded and could match multiple partitions -->
                <!-- The region is defined as a union of rectangles -->
                <rect xlow="int" ylow="int" zlow="int" xhigh="int" yhigh="int" zhigh="int">
                <rect xlow="int" ylow="int" zlow="int" xhigh="int" yhigh="int" zhigh="int">
            </placement_region>
        </placement_constraints>

    </vpr_constraints>

This is only a draft, so any comments or feedback are welcome!

[vaughnbetz]

Thanks Kevin. If we go with the one type of constraint option above -- (xmin,ymin,zmin) to (xmax,ymax,zmax) -- then I think it would also be good to allow a shortcut in the placement_region definition where you use a regex directly instead of having to define a partition name.

<placement_region partion_pattern="regex" || atom_name="regex"> --> the atom_name option would create a partition with a unique name automatically (probably p0_regex or some such) and then set the placement_region constraint on it.

[mithro]

@litghost + @acomodi + @mkurc-ant

[mithro]

Could we use SDC / XDC constraints here? That is what existing tools use.

Examples at https://www.xilinx.com/support/documentation/sw_manuals/xilinx2018_1/ug903-vivado-using-constraints.pdf - See Placement Constraints section.

[mithro]

Related SymbiFlow Issues

• https://github.com/SymbiFlow/symbiflow-arch-defs/issues/1000
• https://github.com/SymbiFlow/ideas/issues/2

[vaughnbetz]

We could use tcl format constraints (what Quartus and Vivado use). The syntax of each is a bit different and not standardized like SDC is for timing, so I'd say this would be a tcl interface to essentially the same information. I was thinking xml first since it should be easy to parse / hopefully can use the new xml parser generator. But I don't have any particularly strong opinion about also doing Tcl or doing Tcl instead. Once the constraints are parsed, they should create the same in memory objects in any case which guide clustering, placement and routing in the same way.

[vaughnbetz]

Edited the original constraint description to capture the possible future work of having a fourth, within-cluster index or id, that allows precise control within the cluster as well for those making very detailed constraints.

[mkurc-ant]

For me it also makes sense to control the placement from the design itself. For example we could add support for attributes of BLIF cells that would provide those constraints.

Like that:

.subckt CELL_NAME I0=net_0 I1=net_1 O=net_o
.attr XMIN 10
.attr XMAX 12

Another idea is to something like "location names" to top-level tiles. Setting those in arch. definition would make it possible to make the VPR compatible with other P&R tools in terms of specifying placements. For example in the <layout> section we can do:

<single type="CLB_TILE" priority="1" x="22" y="33"/>
  ...
  <loc_name>
    CLB_X22Y33
  </loc_name>
</single>

and then in the design (BLIF):

.subckt CLB I0=net_0 I1=net_1 O=net_o ...
.attr LOC CLB_X22Y33

That would also allow to control placement from level of the HDL design (eg. verilog) through cell attributes.

[kmurray]

For example we could add support for attributes of BLIF cells that would provide those constraints.

While I can see the potential convenience of this, I think it mixes two separate concerns together:

1. The definition of the design logic
2. How the design logic should be mapped to the device (constraints)

Since those are two conceptually separate things, I think its better to keep them independent.

For instance, using BLIF attributes means the netlist is now very tied to a very specific to a single device, so a different device can't be targeted with the same BLIF. It also makes it challenging to edit the constraints, since the attributes of every constrained primitives needs to be edited directly. I prefer a higher-level set of constraints (like the wild-cards in the proposal) which are set on groups of blocks, and more easily human edited.

[vaughnbetz]

I agree with Kevin. The trend has been to move constraints out of HDL and into separate files, to keep functionality separate from device implementation constraints. For example, Vivado wants most constraints in Tcl files (which they call xdc). Some constraints they still want in HDL, but I suspect those are older constraints they didn't port to Tcl. See https://forums.xilinx.com/t5/Synthesis/Which-constraints-does-Vivado-accepts-in-HDL/td-p/410037

Intel/Altera specify constraints in Tcl too, but allow some to be specified (generally using the same Tcl syntax) as comments in HDL: see https://www.intel.com/content/www/us/en/programmable/support/support-resources/knowledge-base/solutions/rd05162013_635.html

Given limited development resources, I'd focus on supporting separate files (xml or Tcl). HDL comment support could be added at some point (using the same syntax as the standalone files for clarity) if necessary, but I would say it isn't a high priority. If that enhancement were done, I think the HDL parser should pass the constraints on by making a Tcl file or xml constraint file automatically for the next tool to handle.