Circuit Transformations, Loop Fusion, and Inductive Proof(natetyoung.github.io)
natetyoung.github.io
Circuit Transformations, Loop Fusion, and Inductive Proof
https://natetyoung.github.io/carry_save_fusion/
3 コメント
> 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:
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
n*(x+y)
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
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
[1] see e.g. https://www.jucs.org/jucs_11_7/hardware_design_and_functiona...