Resource utilization with Equivalent Tiles

[acomodi]

After #941 got merged, I have been working on implementing the Equivalent Tiles placement (described in this issue).

The problem I came across regards resource utilization after the packing stage.

To give more details, the packer instantiates a set of logical block types to implement the netlist. With Equivalent sites placement, these blocks could potentially be placed in different physical tiles, therefore, this causes a possible issue when analyzing the resources that are being used after packing.

Proposed Behaviour

The packer outputs only the number of the requested logical blocks, even though the physical tile strictly related to that block does not have enough locations (in fact, there should be a check that, if the logical block can be placed elsewhere, the packer should not exit with a failure).

Than, it is the turn of the placer to assign a physical location to the various logical blocks and, only after this step, the exact resource utilization analysis is output to the user.

[acomodi]

@kmurray @litghost FYI

[kmurray]

If I follow correctly the issue is that since there is no longer a 1:1 correspondence between logical/physical blocks it isn't clear what should be reported to the user.

@acomodi Can you clarify whether this is just a reporting issue, or if there is actually a correctness/functionality issue involved?

[kmurray]

From a reporting perspective, I think it makes sense to report both the logical block used (i.e. produced by packing), and the physical tiles used (i.e. after placement). Both pieces of information would be helpful.

[acomodi]

@kmurray This is both a reporting and correctness issue involved.

At the moment, the packing stage checks, before going through placement, that all the pb_types instances can fit the target architecture. With more complex equivalent_sites definitions, understanding whether the packed solution can fit the arch could become a non-trivial task IMO.

My suggestion is to only report the before-placement resources utilization and the after-placement actual used resources:

E.g.:

(Before Placement)
Netlist:
      40 LAB
      10 LABM
Architecture:  (this are the possible physical resources where to place the 10 LAB)
      50 LAB
      20 LABM

(After Placement) 
40 LAB      ->     35 LAB and 5 LABM
10 LABM     ->     10 LABM

Final resources utilization:
0.7     LAB
0.75    LABM

If the packing is unfeasible, the error will be produced during the initial placement step

[kmurray]

If the packing is unfeasible, the error will be produced during the initial placement step

Yep, I agree. Packing should no longer check whether the packing is 'feasible'. Initial placement is the correct place to do that error check. I can imagine cases where it may be complicated to find a feasible initial placement (due to complex interactions between multiple different equivalent sites). But that is really a problem that initial placement should be handling; not the packer.

There is currently code in the packer which re-tries packing at higher density if it can't fit on the target device. That will need to be re-worked. It still makes sense to re-pack at higher density if needed, but that decision will probably need to be moved further-up outside of the packer.

[acomodi]

@kmurray All right, I will remove the blocking error from the packer to the initial placement, maintaining though the packer reports on the required resources.

I am going to open a PR soon with the WIP branch I am working on. I have still some troubles with the pin mappings, and it would be great if you could take a quick look at that and give me an preliminary feedback whether the direction I took is the correct one.

[acomodi]

@kmurray I am also thinking to add an additional attribute to the equivalent sites tags.
The problem is that there are the equivalence of the sites is not bidirectional: in fact, a LABM cannot be placed in a LAB tile.

This means that, for the initial placement, the resources must be allocated in a sort of priority order, instead of randomly select a possible location (e.g. LABM or LAB tiles for the LAB logical block), first all the initial tiles must correspond to the logical block. E.g. all the LAB logical blocks must be initially placed in the LAB tiles, if there are no more free locations than also the LABM will be used.

To do so, I am thinking of the following solution:

<tiles>
    <tile name="MLAB_tile" width="1" height="1" area="XXX"> <!-- Note: capacity no longer a tile attribute -->
        <input name="inputs" num_pins="50"/>
        <input name="clk" num_pins="2"/>
        <output name="outputs" num_pins="50"/>
        <pinlocations ...>
        <fc ...>
        <mode>
            <site pb_type="LAB" priority="1">
                <direct from="MLAB_tile.inputs" to="LAB.inputs"/> <!-- Note LAB inputs are equivalent -->
                <direct from="MLAB_tile.clk" to="LAB.clk"/>
                <direct from="LAB.outputs" to="MLAB_tile.outpus"/>
            </site>
        </mode>
        <mode>
            <site pb_type="MLAB" priority="0">
                <direct from="MLAB_tile.inputs[19:0]" to="MLAB.addr"/> <!-- Note MLAB inputs are not equivalent -->
                <direct from="MLAB_tile.inputs[29:20]" to="MLAB.data_in"/>
                <direct from="MLAB_tile.clk" to="MLAB.clk"/>
                <direct from="MLAB.data_out" to="MLAB_tile.outputs[9:0]"/>
            </site>
        </mode>
        </equivalent_sites>
    </tile>

    <tile name="LAB_tile">
        <input name="inputs" num_pins="50" equivalnce="full"/>
        <input name="clk" num_pins="2"/>
        <output name="outputs" num_pins="50"/>
        <pinlocations ...>
        <fc ...>
        <mode>
            <site pb_type="LAB" priority="0">
                <direct from="MLAB_tile.inputs" to="LAB.inputs"/> <!-- Note LAB inputs are equivalent -->
                <direct from="MLAB_tile.clk" to="LAB.clk"/>
                <direct from="LAB.outputs" to="MLAB_tile.outputs"/>
            </site>
        </mode>
    </tile>
</tiles>

Where the priority attribute is going from 0 (highest priority) to N (lowest priority). What do you think?

[kmurray]

Where the priority attribute is going from 0 (highest priority) to N (lowest priority). What do you think?

Without thinking too deeply about it, it seems like this is something that should be left up to the tool to decide. That is, I think this should be handled entirely by initial placement. The initial placement problem is then to find a mapping of logical pb_types to the available physical tiles.

I could envision more complex scenarios (e.g. more than two equivalent sites per tile, giving multiple possible ways to map a logical pb_type, for multiple logical pb_types in a particular design), where a simple priority would be insufficient to produce a legal initial placement.

I think instead we should make the initial placement algorithm more intelligent. To start, I'm not that concerned about it. If the current initial placement doesn't do such a great job and just fails (can't find a legal initial placement) that's OK. Its not a show stopper, it just means it needs a larger device. It then becomes an optimization (rather than correctness) issue to improve the initial placer's effectiveness.

[github-actions]

This issue has been inactive for a year and has been marked as stale. It will be closed in 15 days if it continues to be stale. If you believe this is still an issue, please add a comment.

[github-actions]

This issue has been marked stale for 15 days and has been automatically closed.