Circuit Transformations, Loop Fusion, and Inductive Proof

Posted by matt_d 3 days ago

Comments

Comment by discarded1023 17 hours ago

There's a tonne of work done in this space, e.g. Mary Sheeran's µFP from the early 1980s [1], at least for classical synchronous digital circuits. Some googling will dig up a survey or two on modelling circuits with functions and a variety of systems in various languages. BlueSpec was and perhaps is interesting too but is quite a different approach.

[1] see e.g. https://www.jucs.org/jucs_11_7/hardware_design_and_functiona...

Comment by ngruhn 8 hours ago

> A classic compiler optimisation is to fuse these two loops together, so that you only iterate over a once

Honest question: why is that true? If x is the cost of running one iteration of the first loop and y is the cost for the second loop then the total cost is:

    n*x + n*y

After fusing, the cost is:

    n*(x+y)

which is the same.

Comment by rowanG077 7 hours ago

Because two loops is really:

n*(x + c) + n*(y + c) => n*x + n*y + 2*n*c

Where c is some loop overhead, such as loading the arguments and work variables into registers and storing them back, checking the loop end condition, increasing the counters etc.

So if you fuse you get:

n*x + n*y + n*c