This PR aims to improve the bitwidth synthesized for counters in Foreach. Counters are all initialized to I32 at the moment, which is not optimal since for many cases there can be a much tighter bitwidth bound, and therefore, much resource can be saved and timing can be improved. This idea has been mentioned by @mattfel1 in #288 .
An motivating example that this type of optimization can be adopted:
Foreach(N by 1) { i => F(i) }
Here, suppose N is a constant or its boundary is statically known, we can then calculate the minimum bitwidth required for the counter that counts from 0 to N-1, simply by floor(log2(N)) + 1.
Implementation
To implement this optimization, I'm thinking of adding a new Transformer pass during compilation, CounterBitwidthTransformer, which iterates the program, finds all the OpForeach, and replaces their CounterNew with a new instance that has reduced bitwidth.
There are some questions though, mostly due to my insufficient knowledge on Spatial internals:
Is there any other transform that may replace CounterNew without inheriting its data type, i.e., replace our updated CounterNew[T] by CounterNew[I32], where T is the optimized data type?
Is CounterNew the only counter we should take care of?
Is there any function can be reused that maps bitwidth to CounterNew[T] with specified T?
Test plan
There is a new app (will be deleted later) TestCounterBitwidth that simply iterates a SRAM and updates its content using Foreach. If we can notice the CounterNew can be updated to one that has shorter bitwidth, and its generated hardware uses less resource, we may assume that this optimization pass is helpful.
I can also implement unit tests later once I figure out how to do that.
Schedule
The initial version of this work will come out in the next two weeks, and we can finalize other details and make improvements in the following weeks.
Introduction
This PR aims to improve the bitwidth synthesized for counters in
Foreach
. Counters are all initialized toI32
at the moment, which is not optimal since for many cases there can be a much tighter bitwidth bound, and therefore, much resource can be saved and timing can be improved. This idea has been mentioned by @mattfel1 in #288 .An motivating example that this type of optimization can be adopted:
Here, suppose
N
is a constant or its boundary is statically known, we can then calculate the minimum bitwidth required for the counter that counts from 0 toN-1
, simply byfloor(log2(N)) + 1
.Implementation
To implement this optimization, I'm thinking of adding a new
Transformer
pass during compilation,CounterBitwidthTransformer
, which iterates the program, finds all theOpForeach
, and replaces theirCounterNew
with a new instance that has reduced bitwidth.There are some questions though, mostly due to my insufficient knowledge on Spatial internals:
CounterNew
without inheriting its data type, i.e., replace our updatedCounterNew[T]
byCounterNew[I32]
, whereT
is the optimized data type?CounterNew
the only counter we should take care of?CounterNew[T]
with specifiedT
?Test plan
There is a new app (will be deleted later)
TestCounterBitwidth
that simply iterates a SRAM and updates its content usingForeach
. If we can notice theCounterNew
can be updated to one that has shorter bitwidth, and its generated hardware uses less resource, we may assume that this optimization pass is helpful.I can also implement unit tests later once I figure out how to do that.
Schedule
The initial version of this work will come out in the next two weeks, and we can finalize other details and make improvements in the following weeks.