search

0xPolygonMiden / miden-vm

STARK-based virtual machine
MIT License
632 stars 161 forks source link

`DYN`: don't issue a hash request #1523

Open plafer opened 1 month ago

plafer commented 1 month ago

_Originally posted by @plafer in https://github.com/0xPolygonMiden/miden-vm/pull/1516#discussion_r1781552482_

It seems like DYN could not issue any hash request, and also not have an associated END, since we're only hashing dummy values? So DYN would still populate the block hash table, but have no other effect on the trace.

bobbinth commented 1 month ago

To clarify, is the issue here that we could optimize things a bit more by not filling the hasher chiplet with rows to compute hash of of zeros?

plafer commented 1 month ago

Exactly. We will basically save 8 hasher chiplet rows per DYN (and 1 main trace row from not having a corresponding END)

plafer commented 1 month ago

Also, I believe DYN could be made an operation that is included in basic blocks then?

In #1091, we need the decoder helper registers to save the word loaded from memory (for the chiplets bus and block hash table). However, technically, since DYN is currently a control block, we shouldn't be using its helper registers.

bobbinth commented 1 month ago

Exactly. We will basically save 8 hasher chiplet rows per DYN (and 1 main trace row from not having a corresponding END)

Makes sense. One other thing we can try to do in the future is to use multiplicities somehow in the hasher chiplet so that we would not need to have a trace for computing the same hash more than once.

I believe DYN could be made an operation that is included in basic blocks then?

This would be tricky as basic blocks don't have children and DYN could invoke an arbitrary block (e..g, a JOIN block). So, we'd need to end the current basic block, then execute the dynamic block, and then execute the rest basic block - but this would be basically the same thing as having DYN be its own node (i.e., not in basic block).