pub struct CellShare { /* private fields */ }
Expand description
Given a LiveRangeAnalysis that specifies the “share” and “state_share” cells alive at each group, minimizes the cells used for each component.
This works by constructing an interference graph for each alive “state_share” cell. If two cells are ever alive at the same time, then there is an edge between them in the interference graph. Additionally, if two cells are different prototypes, then there is an edge between them.
A greedy graph coloring algorithm on the interference graph is used to assign each cell a name.
By default, this pass will share a given cell as many times as possible. However,
by passing a command line argument, we can limit the number of times a given
cell is reused. The rationale behind this option is that, in certain cases,
if you share a given component too much, the logic to determine when that
component should be activated ends up being more expensive than just using
a separate component. To pass this command line argument, you give three numbers:
The number of times a given combinational component can be shared, the number
of times a given register can be shared, and the number of times all other
components can be shared. Generally we would want settings such that 1 < 2 < 3,
since a given share of a 3) would save more hardware than a share of a 2), and
a share of a 2) would save more hardware than a share of a 1).
The exact command line syntax to use: if we had a file, “x.futil” and ran:
cargo run x.futil -x cell-share:bounds=2,4,8
, then we would only share a
given combinational component at most twice, a given register at most 4 times,
and all other components at most 8 times. If you wanted to do something with
fud then run fud e ... -s calyx.flags " -x cell-share:bounds=2,4,8"
. Finally
if you do not want to bound the sharing for a particular cell type,
you can pass -1 as a bound. So for example if you passed
-x cell-share:bounds=2,-1,3
this means that you will always share registers.
Note: The no spaces are important.
Also, if you pass the following flag: -x cell-share:print-share-freqs=file-name
this pass will write a json to file-name
. If want to print into stdout
then just set the file-name to be “stdout” (you don’t need the quotes
when you actually pass in the argument, so run -x cell-share:print-share-freqs=stdout
),
and if you want to print to stderr then just set the file-name to be “stderr”.
The json will map an integer (say n) to the number of cells in the new design (i.e.,
the design after sharing has been performed) that were shared
exactly n times. So the key n = 2 will be mapped to the number of cells in the
new design that are shared exactly twice.
Other flags: print_par_timing: prints the par-timing-map calyx_2020: shares using the Calyx 2020 settings: unlimited sharing of combinational components and registers, but no sharing of anything else
This pass only renames uses of cells. crate::passes::DeadCellRemoval should be run after this to actually remove the definitions.
Trait Implementations
sourcefn from(ctx: &Context) -> CalyxResult<Self>
fn from(ctx: &Context) -> CalyxResult<Self>
sourcefn clear_data(&mut self)
fn clear_data(&mut self)
fn get_opts(ctx: &Context) -> LinkedHashMap<&'static str, ParseVal>where
Self: Named,
sourcefn description() -> &'static str
fn description() -> &'static str
The algorithm that runs is:
- instantiate conflict graph using all component cells that satisfy
cell_filter
- use [ScheduleConflicts] to find groups/invokes that run in parallel with each other
- for each tuple combination of cells that return true on cell_filter(), c1 and c2
- first determine if their live ranges overlap. If so, then insert a conflict between c1 and c2
- if c1 and c2 don’t have overlapping live ranges, check if c1 and c2 are ever live at within the same par block, and they are live at different children of the par block. If the parent par is not static, then add a conflict. If the parent par is static, then we can use the static_par_timing analysis to check whether the cells’ liveness actually overlaps.
- perform graph coloring using
self.ordering
to define the order of the greedy coloring - use coloring to rewrite group assignments, continuous assignments, and conditional ports.
sourcefn start(
&mut self,
comp: &mut Component,
sigs: &LibrarySignatures,
_comps: &[Component]
) -> VisResult
fn start(
&mut self,
comp: &mut Component,
sigs: &LibrarySignatures,
_comps: &[Component]
) -> VisResult
sourcefn precondition(_ctx: &Context) -> Option<String>where
Self: Sized,
fn precondition(_ctx: &Context) -> Option<String>where
Self: Sized,
sourcefn start_context(&mut self, _ctx: &mut Context) -> VisResult
fn start_context(&mut self, _ctx: &mut Context) -> VisResult
ir::Context
before visiting the components.sourcefn finish_context(&mut self, _ctx: &mut Context) -> VisResult
fn finish_context(&mut self, _ctx: &mut Context) -> VisResult
ir::Context
after visiting the components.sourcefn iteration_order() -> Orderwhere
Self: Sized,
fn iteration_order() -> Orderwhere
Self: Sized,
sourcefn traverse_component(
&mut self,
comp: &mut Component,
signatures: &LibrarySignatures,
components: &[Component]
) -> CalyxResult<()>where
Self: Sized,
fn traverse_component(
&mut self,
comp: &mut Component,
signatures: &LibrarySignatures,
components: &[Component]
) -> CalyxResult<()>where
Self: Sized,
sourcefn do_pass(&mut self, context: &mut Context) -> CalyxResult<()>where
Self: Sized + ConstructVisitor + Named,
fn do_pass(&mut self, context: &mut Context) -> CalyxResult<()>where
Self: Sized + ConstructVisitor + Named,
ir::Context
.
The function mutably borrows the control
program in each component and
traverses it. Read more