Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Reduce number of bus receives to one per machine (instead of operation) #2407

Open
georgwiese opened this issue Jan 29, 2025 · 0 comments
Open

Comments

@georgwiese
Copy link
Collaborator

#2359 reduced the number of bus receives from one per incoming connection to one per operation. I think we can reduce it further to one per machine.

Example

Suppose we have two operations:

    operation foo<42> a, b -> c;
    operation_bar<123> d -> e;

This currently compiles to two bus receives:

    map(selectors, std::utils::force_bool);

    Constr::PhantomBusInteraction(-selectors[0], ID_FOO, [operation_id, a, b, c], selectors[0]);
    Constr::PhantomBusInteraction(-selectors[1], ID_BAR, [operation_id, d, e], selectors[1]);

Instead, we should be able to compile to:

    map(selectors, std::utils::force_bool);
    std::utils::force_bool(sum(selectors));

    Constr::PhantomBusInteraction(
        -(selectors[0] + selectors[1]),
        ID_MACHINE,
        [
            selectors[0] * 42 + selectors[1] * 123,
            selectors[0] * a + selectors[1] * d,
            selectors[0] * b + selectors[1] * e,
            selectors[0] * c
        ],
        selectors[0] + selectors[1]
    );

    // The operation_id column is now a bit redundant, could be removed.
    operation_id = selectors[0] * 42 + selectors[1] * 123;

I am pretty sure that witgen wouldn't work for this, because it wouldn't be able to figure out which selector to set (but there is a unique assignment for a given operation ID!), but it would be sound.

Remarks

  1. Note that this is possible even though the length of the parameter list is different. This works, because a fingerprint of the tuple $(a, b, c)$ is equal to the fingerprint of the tuple $(a, b, c, 0, 0, 0, ...)$ (you can pad any amount of zeros to the right), see Reverse fingerprint order #2405. As a result, the machine would receive a payload of a length corresponding to the largest operation. No change of the bus send is required, it can simply send a shorter payload.
  2. I think the same trick would even be possible with a lookup or permutation: If you have two lookups / permutations connecting the same two machines, you can remove one. The RHS of the collapsed would look similar to the collapsed receive above.
  3. We'd still have one selector per operation. Actually, because of this, the whole concept of an "operation ID" is redundant, as the example above shows.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant