search

circify / compiler

Superseded by https://github.com/circify/circ
https://github.com/circify/circ
5 stars 2 forks source link

Benes/Waksman network impl for memory #16

Closed kwantam closed 3 years ago

kwantam commented 3 years ago

WIP PR to implement Waksman routing for memory impl

kwantam commented 3 years ago

@alex-ozdemir libsnark doesn't want to build on my machine and I don't feel like fighting it tonight, so I couldn't actually run proof tests. I'll pick this back up tomorrow, but in the meantime the code is at least ready for review.

(If you have a second and want to run the benes proof tests on your machine, that would be great! but no worries if not)

alex-ozdemir commented 3 years ago

Wow! Tests look good to me. I tried a baby test and the 8 by 8 pointer chasing test. I've added the latter to the end-to-end test script.

Typically when I implement something new and run end-to-end tests the first time, something breaks. I'm impressed & envious :).

I'm a little too tired to review right now, but I'll take care of it tomorrow.

Do you mind if I just fix little nits myself, instead of poking you about it? If you'd prefer to go back and forth we can totally do that.

kwantam commented 3 years ago

Do you mind if I just fix little nits myself, instead of poking you about it? If you'd prefer to go back and forth we can totally do that.

Totally fine either way --- whichever you prefer!

alex-ozdemir commented 3 years ago

I'm going to go ahead and merge this. There are a few more things I'd like to change (e.g. making the routing network generic), but I'm happy to do that in the future. I'd like to get this stuff into the paper first.

kwantam commented 3 years ago

Ah, right, meant to mention this in my initial message.

I think it'll be easy to make the routing network generic, but it looked like this change would ripple out a bit. Maybe the right approach is to construct a type that the routing network machinery uses, and have that type convert to/from what's used elsewhere. That would let us handle packing/unpacking at the input/output of the routing network, without needing to make changes elsewhere.

This would require four functions: convert to, convert from, extract address, build crossbar switch.

If it turns out we need this for efficiency I'm happy to take a crack at it.

Also: I think xJsnark might suggest one or two small optimizations. We can take a look at that when the time comes.

alex-ozdemir commented 3 years ago

This would require four functions: convert to, convert from, extract address, build crossbar switch.

Makes sense

If it turns out we need this for efficiency I'm happy to take a crack at it.

Happily, it seems like we do not need this yet (at least to beat pequin). I'll take some time to inspect the output, but as of now our ptrchase is 2x better than pequin's, on large arrays (on small arrays the difference is even more pronounced, per our earlier discussions)