YosysHQ / apicula

Project Apicula 🐝: bitstream documentation for Gowin FPGAs
MIT License
474 stars 66 forks source link

Add Functions for Concise Tile Parsing #237

Closed Seyviour closed 6 months ago

Seyviour commented 6 months ago

This pull request adds two functions (parse_tile_exact and exact_table_cover) to fuse_h4x.py. The parse_tile_exact reports an exact cover over the rows in a table, computed using the exact_table_cover function that are 'active' in a bitstream.

These functions come from the realization that the problem of determining what rows in a table were actually used can be conceptualized as an exact cover problem, assuming that no two active rows ever share fuses. So far, this assumption seems to hold up.

These functions are quite effective at cutting out 'noise'. Consider the following comparison between the output of parse_tile and parse_tile_exact for the same tile.

parse_tile

         [2, 10, (0, 35)]
     [3, 10, (0, 35), (0, 34)]
     [8, 10, (0, 34)]
     [81, 3, (0, 48), (0, 45)]
     [82, 3, (0, 47), (0, 45)]
     [93, 3, (0, 48), (0, 36)]
     [94, 3, (0, 47), (0, 36)]
     [121, 3, (0, 48), (0, 45), (0, 47), (0, 36)]
     [122, 3, (0, 48), (0, 45), (0, 36)]
     [172, 3, (0, 45), (0, 47), (0, 36)]
     [278, 3, (0, 48), (0, 45), (0, 47), (0, 36)]

parse_tile_exact

         [3, 10, (0, 34), (0, 35)]
     [278, 3, (0, 36), (0, 45), (0, 47), (0, 48)]

The xcover package (github.com/john/xcover) makes all this possible. However, as it depends on numba and numpy, the import to xcover is 'hidden' within the exact_table_cover function. The reasoning here is that since these functions are really only useful to developers, the developer can bear the responsibility of making the xcover package available. If the xcover package is not installed, a call to exact_table_cover raises a ModuleNotFoundError exception, with a message on how the xcover package may be installed.

pepijndevos commented 6 months ago

Thank you!

Seyviour commented 6 months ago

It's my pleasure. Thanks for merging!