search

calyxir / calyx

Intermediate Language (IL) for Hardware Accelerator Generators
https://calyxir.org
MIT License
502 stars 51 forks source link

Queues: benchmark specialized queues against binary heap variants #2221

Closed anshumanmohan closed 2 months ago

anshumanmohan commented 4 months ago

We have a small clutch of queue implementations now, and those have different capabilities. In increasing order of expressivity:

  1. Round-Robin (resp. Strict) PIFOs can orchestrate n flows in a round-robin (resp. strict) policy. These are not strictly PIFOs: they cannot actually accept an item and a rank and enqueue that item with that rank.
  2. Stable binary heaps can actually simulate PIFOs in a general sense. They take a value and a rank, and enqueue the value with that rank. Atop of stable binary heaps, we have built little layers of logic that grant ranks to values, such that {the layer of logic + the binary heap below it} together instruments a scheduling policy. We have such layers of logic for FIFO and PIFO policies.

We have long had this vague notion that the simpler kinds of queues will be more performant. This issue seeks to test that for real. We will likely want to chat with @calebmkim, who has a little repository to measure LUTs, cycle counts, etc for a given design under a given set of inputs.

The first few concrete steps (just to get a comparison between 1 and 2 going) are:

This work does not strictly have to happen during flag day, but I've put it in the flag day list because we will probably benefit from the tidying of flag day. Also, it kinda feels like this sort of benchmarking is "good housekeeping" when building multiple gadgets that have similar functionality.

anshumanmohan commented 4 months ago

@polybeandip just wondering if you'd like to poke around some of this, especially as the main near-term development work is on stable binary heaps!

polybeandip commented 4 months ago

Happy to work on this; looks fun!

anshumanmohan commented 2 months ago

Just to record this in writing: #2276 makes great strides towards closing this, but does not mess with PIEOs yet. @polybeandip is going to refactor this issue into two issues. One of those will be the non-PIEO work, which is exactly solved by #2276. The other will remain open