Skip to content

Channel size optimizations #573

Description

@taktoa

Currently, we have no optimizations that affect the size of data travelling over a channel. In the presence of proc inlining such optimizations may cover some of the benefit of the optimizations in #561. In other multiproc implementation strategies, this can reduce the widths of FIFOs. Examples:

  1. If the set of values sent over a given channel has size one, replace that channel with a single-bit channel.
  2. Use range or ternary analysis to figure out the set of possible values sent over a given channel, and narrow it before sending and then unnarrow after receiving.
  3. Use BDD analysis to find redundant bits in the values sent over the channel.
  4. Find tagged union type data structures in the values sent over the channel. For example, if the channel has type (bits[1], bits[32], bits[64]) and when the bits[0] element is 0 the bits[64] is always 0, and when the bits[0] element is 1 the bits[64] is always 0, this can be reduced to (bits[1], bits[64]) where the bits[32] is sliced out of the bits[64] when it is nonzero. Simply supporting anonymous unions could be easier than doing this analysis, though it would only help in the case of the DSLX frontend, which does not support ADTs yet.

Doing this work interprocedurally before proc inlining has the benefit of doing less work overall, but the detriment of requiring more conservatism around any static analyses done.

Activity

  1. added
    optimizerRelated to IR optimization or analysis
    on Feb 9, 2022
  2. taktoa commented on Sep 27, 2022

    @taktoa
    CollaboratorAuthor

    Another idea: if you have a send in A that is received by a receive in B, look at all the nodes that depend on the receive in B, and restrict to the ones where the critical path between the receive and them is less than the cycle time minus the maximum critical path between a pipeline stage register and the send in A. Then do a min s,t-cut on this subgraph and move the nodes in the s-part of the cut over to A, so that the cut edges become the new channel bitwidth.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    good first issueGood for newcomersoptimizerRelated to IR optimization or analysis

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions